تنفيذ خوارزميات المصفوفات
| English | العربية |
|---|---|
| traversal/træˈvɜːsl/ | المرور |
| index/ˈɪndeks/ | فهرس |
| linear search/ˈlɪnɪə sɜːtʃ/ | البحث الخطي |
خوارزميات المصفوفة القياسية
- معظم مهام المصفوفات هي مرور زائد أحد أنماط قياسية قليلة.
- المجموع / المتوسط: اجمع المجموع الكلي، ثم اقسمه على
length. - العدّ: زد العداد عندما يطابق العنصر شرطاً معيناً.
- الأصغر / الأكبر: تتبع أصغر أو أكبر قيمة شوهدت حتى الآن.
إيجاد القيمة العظمى
- ابدأ بـ
max = a[0](العنصر الأول)، ثم مرر بدءاً من الفهرس1. if (a[i] > max) { max = a[i]; }داخل الحلقة.- بعد انتهاء الحلقة، يحتوي
maxعلى أكبر قيمة في المصفوفة. - ابدأ من العنصر الأول، لا
0— لأن0قد يكون أكبر من كل القيم.
البحث عن قيمة
- للتحقق من وجود قيمة، مرر وقارن كل عنصر.
- أعد الفهرس الذي تم العثور عليه، أو
-1إذا انتهت الحلقة دون تطابق. if (a[i] == target) return i;داخل الحلقة؛return -1;بعدها.- هذا بحث خطي (وحدات 4.14 تناقشه بتعمق).
الإزاحة والتعديل
- بعض الخوارزميات تحرك أو تغير العناصر — مثال: إزاحة الجميع يساراً، أو مضاعفة كل قيمة.
- التعديل يتطلب الحلقة المؤشرة لكي تتمكن من تعيين
a[i] = .... - انتبه للحدود عند قراءة
a[i+1]— الفهرس الأخير ليس له جاور. - تتبع الفهارس بعناية لتجنب الوصول خارج النطاق.
ابدأ بحث الأصغر/الأكبر بالعنصر الأول، لا 0. int max = 0; يفشل إذا كانت كل القيم سالبة (سيبلغ خاطئاً عن 0). استخدم int max = a[0]; وابدأ الحلقة من الفهرس 1. وعند قراءة خوارزمية لـ a[i+1]، أوقف الحلقة عند i < a.length - 1، وإلا ستقرأ الحلقة الأخيرة خارج النهاية.
إيجاد القيمة العظمى في a:
int max = a[0];for (int i = 1; i < a.length; i++) { if (a[i] > max) max = a[i]; }- بالنسبة لـ
a = {3, 9, 5}: تصبح القيمة العظمى9.
خوارزميات المصفوفة تجمع بين المرور ونمط: مجموع/متوسط، عدّ، أصغر/أكبر، أو بحث (إعادة الفهرس أو -1). ابدأ الأصغر/الأكبر بالعنصر الأول، لا 0. تعديل العناصر يتطلب الحلقة المؤشرة، وقراءة a[i+1] تتطلب حداً أضيق للبقاء ضمن النطاق.
إيجاد القيمة العظمى
max يبدأ بـ a[0]=3، يصبح 9، ثم يبقى كما هو (a = {3,9,5}).
لإيجاد القيمة العظمى لمصفوفة، يجب أن تبدأ max بـ...
بدءًا من 0 يفشل إذا كانت جميع القيم سالبة.
للمصفوفة a = {3, 9, 5}؛ ما هي القيمة العظمى؟
9 هو أكبر عنصر.
ماذا ترجع عملية البحث الخطي إذا لم يتم العثور على الهدف؟
بال convention، -1 تعني 'لم يتم العثور عليه'.
الخوارزمية التي تقرأ a[i+1] يجب أن تتكرر طالما...
التوقف مبكرًا بدرجة واحدة يحافظ على a[i+1] داخل النطاق.
تعديل عناصر المصفوفة (a[i] = ...) يتطلب الحلقة ذات الفهرس، وليس for-each.
لا يمكن لـ for-each إعادة assignment داخل المصفوفة.