المصفوفات
| English | العربية |
|---|---|
| array/əˈreɪ/ | المصفوفة (array) |
| element/ˈelɪmənt/ | عنصر |
| index/ˈɪndeks/ | فهرس |
| lower bound/ˈləʊə baʊnd/ | الحد الأدنى |
| upper bound/ˈʌpə baʊnd/ | الحد الأعلى |
| dimension/daɪˈmenʃn/ | البُعد |
| nested loops/ˈnestɪd luːps/ | حلقات متداخلة |
| linear search/ˈlɪnɪə sɜːtʃ/ | البحث الخطي |
| bubble sort/ˈbʌbl sɔːt/ | فرز الفقاعات |
مقعد 14C
- دار سينما بها 300 مقعد. نظام الحجز لديها لا يحتوي على 300 متغير باسم
Seat1A،Seat1B،Seat1C. بل لديه مصفوفة واحدة، وتذكرة التذاكر هي عنوان بداخلها: الصف 14، المقعد C. - اسم واحد، مئات القيم، كل منها يُوجد برقم. أضف صفاً ولن يتغير الكود؛ كرر الحلقات فوق الأرقام وستتحقق من كل مقعد.
- تقريباً كل خوارزمية في ورقة 2 تمر على مصفوفة: البحث فيها، جمعها، ترتيبها، إيجاد أكبر قيمة فيها.
- هذا الدرس هو المفردات، والإعلانات، والأربع خوارزميات التي يطلبها الممتحن بالكود الوهمي وبالكلمات.
مفردات
- المصفوفة هي بنية بيانات تحتوي على عدد ثابت من العناصر من نفس نوع البيانات تحت معرّف واحد، يتم الوصول إليها بواسطة فهرس.
- الحد الأدنى والحد الأعلى هما أول وأخر فهرس صالح. عدد العناصر = الحد الأعلى − الحد الأدنى + 1.
- البُعد هو عدد الفهارس التي يحتاجها العنصر: واحد للقائمة، اثنيان للجدول.
- في
ThisArray[n] ← 42المصفوفة لها بُعد واحد، والفهرس هو المتغيرINTEGERn، والعنصر عند ذلك الفهرس يستقبل42.
معرف واحد، فهرس لكل عنصر، حدود في كلا الطرفين
تخزن المصفوفة:
المصفوفة مجموعة مرتبة من عناصر من نفس النوع يتم الوصول إليها بالفهرس. (السجل يجمع أنواعاً مختلفة.)
المصفوفة بنية بيانات تحتوي على قيم عديدة من نوع ______ تحت اسم واحد.
يتم الوصول إلى كل قيمة عبر فهارسها.
DECLARE Marks : ARRAY[0:99] OF INTEGER يعلن مصفوفة من ____ عنصر.
الحد العلوي ناقص الحد السفلي زائد واحد: 99 − 0 + 1 = 100. كلا الحدين مؤشرات صالحة.
مثال محلل: إعلان المصفوفة التي تحتاجها المهمة
- الإعلان يحتاج المعرّف، والحدود ونوع البيانات.
- 120 قراءة قد تحتوي على منزلة عشرية:
DECLARE Data : ARRAY[1:120] OF REAL - جدول من 150 صف وعمودين من النص:
DECLARE Names : ARRAY[1:150, 1:2] OF STRING - قل العدد إذا طُلب منك:
[0:99]يحتوي على 100 عنصر، وليس 99.
أي إعلان يحتوي على جدول 150 من الصفوف و2 من الأعمدة من النصوص؟
بعدين، لكل منهما حد أدنى وحد أعلى، ونوع العنصر. الخيار الثاني هو قائمة واحدة طويلة؛ الثالث لا يحتوي على نوع؛ الرابع لا يحتوي على حدود سفلى.
معالجة مصفوفة 1-D
DECLARE Names : ARRAY[1:5] OF STRING
Names[3] ← "Cara"
FOR i ← 1 TO 5
OUTPUT Names[i]
NEXT i
- حلقة
FORمن الحد الأدنى إلى الحد الأعلى تزور كل عنصر مرة واحدة. - لمجموع، عد، أو حد أقصى/أدنى، ضع متغيراً متراكماً قبل الحلقة وتحديثه داخلها.
مصفوفات 2-D
DECLARE Grid : ARRAY[1:3, 1:4] OF INTEGER
Grid[2, 3] ← 99 // row 2, column 3
- الفهرس الأول هو الصف، والثاني هو العمود. الحلقات المتداخلة تزور كل خلية: الحلقة الخارجية للصفوف، والداخلية للأعمدة.
- استخدم 1-D لتسلسل واحد و2-D عندما تكون البيانات ذات بعدين طبيعيين، مثل شبكة مقاعد أو جدول درجات حسب طالب ومادة.
Grid[row, column]، دائماً بنفس الترتيب
فهرس مصفوفة 2-A بـ [صف، عمود]
المصفوفة 2-A هي شبكة. Grid[row, column] تصل إلى خلية واحدة — غيّر الصف والعمود لترى أي قيمة ستصل إليها.
في Grid[2, 3]، أي خلية يتم الوصول إليها؟
الفهرس الأول يمثل الصف، والثاني يمثل العمود — لذا الصف 2، العمود 3.
مثال محلل: بحث خطي يمكنه قول "لم يُوجد"
- البحث الخطي يتحقق من كل عنصر بالتتابع من الأول حتى يُوجد المستهدف أو يُنتهى.
FoundAt ← -1
FOR i ← 1 TO n
IF A[i] = Target THEN
FoundAt ← i
ENDIF
NEXT i
IF FoundAt = -1 THEN
OUTPUT "Not found"
ELSE
OUTPUT "Found at ", FoundAt
ENDIF
-1لا يمكن أبداً أن يكون فهرساً صالحاً، لذا يعني "لم يُوجد". قم بتهيئته قبل الحلقة واختبره بعد. البحث الذي لا يقول أبداً "لم يُوجد" يفقد درجة.
يبحث البحث الخطي عن قيمة عن طريق:
يفحص البحث الخطي العناصر واحداً تلو الآخر من البداية حتى يجد الهدف (أو يصل إلى النهاية).
تعيين FoundAt بـ -1 قبل البحث الخطي يسمح للبرنامج بإبلاغ "لم يتم العثور" بعد انتهاء الحلقة.
-1 ليس فهرساً صالحاً أبداً، لذا إذا بقي كما هو بعد الحلقة لم يكن الهدف في المصفوفة.
أكبر قيمة، وأين تقع
Largest ← A[1]
Position ← 1
FOR i ← 2 TO n
IF A[i] > Largest THEN
Largest ← A[i]
Position ← i
ENDIF
NEXT i
OUTPUT Largest, " at ", Position
- ابدأ
Largestمن العنصر الأول، لا تبدأ من 0: قد تكون المصفوفة كلها سالبة. - نفس الشكل يعدّ أو يُخرج العناصر غير الفارغة: قارن كل عنصر مع العلامة الخاصة بالغير مستخدم،
""أو-1، وعدّ فقط تلك التي تختلف.
فرز الفقاعات
- فرز الفقاعات يقوم بمرات متعددة عبر المصفوفة لمقارنة الأزواج المتجاورة وتبديل تلك غير المرتبة، حتى لا يتم تبديل أي عنصر في مرور ما.
- بعد كل مرور، يكون أكبر قيمة غير مرتبة قد صعدت إلى النهاية، لذا يمكن للمرة التالية التوقف قبل نهاية واحدة.
REPEAT
Swapped ← FALSE
FOR Index ← 1 TO Limit - 1
IF Data[Index] > Data[Index + 1] THEN
Temp ← Data[Index]
Data[Index] ← Data[Index + 1]
Data[Index + 1] ← Temp
Swapped ← TRUE
ENDIF
NEXT Index
Limit ← Limit - 1
UNTIL Swapped = FALSE
كل مرة تحمل أكبر قيمة متبقية إلى النهاية
رتّب خطوات مرور واحد من ترتيب الفقاعات، ونهايته، بالترتيب.
أعد تعيين العلم، والتمرير والتبديل، وتقليص الحد، وتوقف عندما لم يحدث تبديل خلال مرور كامل.
مثال محلول: حيث توجد علامات فرز الفقاعات
- الحلقة الخارجية التي تتكرر حتى لا يتم تبديل أي عنصر في مرور ما؛ تم إعادة تعيين علم
SwappedإلىFALSEفي بداية كل مرور وتم تعيينهTRUEداخلIF. - عملية التبديل ذات الأسطر الثلاثة عبر متغير مؤقت. خطان يفقدان قيمة.
- الحد المتناقص، أقل بمقدار واحد في كل مرور، لأن أكبر قيمة قد وصلت بالفعل إلى النهاية.
- بالكلمات، لسؤال التحسين التدريجي: كرر حتى يتم الترتيب؛ في كل مرور قارن الأزواج المتجاورة؛ قلب أي زوج غير مرتب؛ بعد كل مرور تكون أكبر قيمة غير مرتبة في النهاية.
أي ميزات تكسب علامات في ترتيب الفقاعات الفعال؟ حدد كل ما ينطبق.
العلم، التبديل بالمؤقت، تقليص الحد: هذه هي العلامات. نسخ المصفوفة ليس جزءاً من الخوارزمية.
مثال محلول: إزالة وإدراج
- إزالة عنصر: أوجد فهرسه باستخدام بحث خطي؛ حرك كل عنصر لاحق مكانًا واحدًا نحو البداية لإغلاق الفراغ؛ حدد العنصر الأخير بأنه غير مستخدم، أو قلل العداد.
- الإدراج في مصفوفة مرتبة: أوجد أول فهرس يكون عنصره أكبر؛ حرك ذلك العنصر وكل عنصر لاحق مكانًا واحدًا نحو النهاية، بدءًا من الأخيرة؛ احفظ القيمة الجديدة في الفراغ.
- تحرك من النهاية عند فتح فراغ ومن البداية عند إغلاقه، وإلا ستقوم بتجاوز القيمة التي تنوي نقلها.
المصفوفة تحتفظ بالعديد من العناصر من نفس النوع يمكن الوصول إليها بالفهرس، بينما تجمع السجل حقولاً من أنواع (ربما) مختلفة يمكن الوصول إليها بالاسم.
مصفوفة 2-A مناسبة لشبكة (صف × عمود)؛ السجل مناسب لشيء واحد توصفه حقول متعددة مسماة.
علامات ضائعة
[0:99]يحتوي على 100 عنصر. عدّ كلا الحدين.- الفهرس هو
INTEGER؛ Declarations تتطلب النوع بالإضافة إلى الحدود. Grid[row, column]: الصف أولاً. تبديلهم يقرأ الخلية الخطأ في كل حلقة متداخلة.- التبديل يحتاج متغير مؤقت؛ البحث يحتاج مسار "لم يُعثر"؛ ينتهي فرز الفقاعات عندما لا يتم تبديل أي عنصر في مرور ما، وليس بعد عدد ثابت من المرات.
لقد فهمت الأمر
- مصفوفة تحتوي على عدد ثابت من العناصر من نفس النوع تحت معرف واحد، تُصل إليه عبر فهرس بين الحد الأدنى والحد الأعلى؛ العدد = الحد الأعلى − الحد الأدنى + 1
- 1-D هي قائمة، 2-D هي جدول
[row, column]يُمشى بحلقات متداخلة؛ أعلنه بالحدود والنوع - بحث خطي:
FoundAt ← -1، حلقة، احفظ الفهرس، اختبر بعد الحلقة؛ أكبر قيمة: ابدأ منA[1]، احتفظ بالموقع - فرز الفقاعات: مرات لمقارنة-تبديل متجاورة مع متغير مؤقت، علم
Swapped، حد متناقص، حتى لا يتم تبديل أي عنصر في مرور ما