تنفيذ ADTs باستخدام المصفوفات.
| English | العربية |
|---|---|
| overflow/ˌəʊvəˈfləʊ/ | الانحياز (overflow) |
| underflow/ˌʌndəˈfləʊ/ | انحدار |
| circular array/ˈsɜːkjʊlə əˈreɪ/ | مصفوفة دائرية |
| free list/friː lɪst/ | قائمة حرة |
لا يوجد شيء اسمه مكدس في الذاكرة
- افتح جهاز كمبيوتر وابحث عن المكدس. لن تجده. الذاكرة مصفوفة ضخمة واحدة من الخلايا المرقمة، وهذا كل ما يوجد.
- كل مكدس، وكل طابور، وكل قائمة مرتبطة هي تلك المصفوفة بالإضافة إلى متغيرين أو ثلاثة أرقام صحيحين يتذكرون أين الأشياء. Push هو "أضف واحد إلى رقم واحفظ"؛ dequeue هو "اقرأ خلية وأضف واحد إلى رقم مختلف".
- الدرس بأكمله هو إدارة حسابات: أي المؤشرات، أي الفحوصات، وما يحدث عند الحواف.
- الامتحان يطلب منك وصف Declarations، تمرير المؤشرات عبر عدة عمليات، وشرح سبب وجود الفحوصات.
مكدس في مصفوفة
- احتفظ بالعناصر في
Stack[1:MaxSize]مع عدد صحيحTop، 0 عندما يكون المكدس فارغاً. - Push(x): إذا
Top = MaxSizeكان المكدس ممتلئاً، فائض; وإلاTop ← Top + 1وStack[Top] ← x. - Pop(): إذا
Top = 0كان المكدس فارغاً، نقصان; وإلا ارجعStack[Top]وTop ← Top − 1.
المصفوفة لا تتحرك أبداً؛ فقط Top يفعل
إدراج عنصر في مكدس ممتلئ مسبقاً يسبب_overflow_ في المكدس ______.
Overflow = الإدراج عندما يكون Top = MaxSize؛ الإزالة من مكدس فارغ (Top = 0) هي underflow.
طابق كل حالة لمكدس مصفوفة بما تعنيه.
Top يعدد العناصر: 0 = فارغ، MaxSize = ممتلئ؛ حالتا الخطأ هما underflow و overflow.
مثال محلول: الإعلان والتهيئة للمكدس
- وصف الإعلانات والتهيئة اللازمة لتنفيذ مكدس يصل إلى 50 عدد صحيح باستخدام مصفوفة. [5]
- مصفوفة من 50 عنصراً من نوع
INTEGER،DECLARE Stack : ARRAY[1:50] OF INTEGER، لحفظ العناصر. - ثابت أو متغير
MaxSizeمضبوط على 50، بحيث يمكن لـpush اختبار امتلاءه. - مؤشر
INTEGERلقمة المكدس،Top، مُهيَّأ على 0 لإظهار أن المكدس فارغ؛ يختبره pop للنقصان، ويقارنه push معMaxSizeللفائض.
أي مما يلي ينتمي لإعلان وتهيئة مكدس قائم على مصفوفة؟ اختر جميع ما ينطبق.
المكدس يحتاج مؤشراً واحداً، Top. مؤشر الأمام ينتمي للطابور.
طابور في مصفوفة عادية
- مؤشران:
Frontللعنصر التالي المغادر،Rearللمساحة الحرة التالية. Enqueue يخزن عندRearويحرّكه؛ dequeue يقرأ عندFrontويحرّكه. - كلا المؤشرين يتحركان دائماً للأمام، لذا بعد بعض العمليات يسيران خارج نهاية المصفوفة بينماCells في البداية تبقى فارغة وغير مستخدمة.
- الحل هو السماح للمؤشرات بالتفاف حول.
المصفوفة الدائرية
- المصفوفة الدائرية تُعيد توجيه المؤشر إلى الخلية الأولى عند تجاوز الأخيرة: مع فهارس 1-based،
Rear ← (Rear MOD MaxSize) + 1. - Enqueue(x): تحقق من عدم الامتلاء؛
Rear ← (Rear MOD MaxSize) + 1؛Queue[Rear] ← x. Dequeue(): تحقق من عدم الفراغ؛ ارجعQueue[Front]؛Front ← (Front MOD MaxSize) + 1. - احتفظ بعدد منفصل: عندما يكون الطابور ممتلئاً تماماً وعندما يكون فارغاً تماماً، يكون المؤشران في نفس الوضع النسبي، لذا المؤشرات وحدها لا يمكنها التمييز بين الحالتين.
بعد الخلية الأخيرة تأتي الخلية الأولى
تنفيذ ADTs باستخدام المصفوفات.
FIFO.
الطابور يعمل بنظام أول دخل أول خروج — إضافة في الخلف، وإزالة من الأمام.
لماذا استخدام مصفوفة دائرية للطابور؟
الطابور الخطي يهدر خلايا البداية بينما يتقدم Front؛ الدوران باستخدام MOD يعيد استخدامها.
الطابور الدائري يستخدم MOD بحيث تدور مؤشرات الأمام/الخلف وتعيد استخدام الخلايا المحرزة في بداية المصفوفة.
(pointer MOD MaxSize) + 1 يعيد الفهرس إلى الخلية الأولى، sehingga لا يهدر الطابور الخطي خلايا تجاوزها Front.
مثال محلول: تتبع المؤشرات
- مع
MaxSize = 6: إذاRear = 5، فإن(5 MOD 6) + 1 = 6، لذا العنصر التالي يوضع في الخلية 6. إذاRear = 6، فإن(6 MOD 6) + 1 = 1: المؤشر يعود إلى الخلية 1. - يُحفظ طابور دائري في مصفوفة بحجم 5، مؤشراتها من 0 إلى 4، مع
Front = 3،Rear = 3وعنصر واحد مخزن. تمت إضافة عنصرين، ثم إزالة اثنين. باستخدام مؤشرات تبدأ من 0، كل حركة هي(pointer + 1) MOD 5. - الإضافة مرتين تحرك
Rear: 3 → 4، ثم 4 → 0، لأن (4 + 1) MOD 5 = 0. الإزالة مرتين تحركFront: 3 → 4 → 0. بقي عنصر واحد، عند الفهرس 0، وأعيد استخدام الخلايا التي أُفرغت في بداية المصفوفة.
الطابور الدائري يستخدم خلايا 1 إلى 6 و Rear = 6. بعد Rear ← (Rear MOD 6) + 1، أين سيذهب العنصر القادم؟
6 MOD 6 = 0، زائد 1 يعطي 1. المؤشر يدور لبداية المصفوفة.
مثال محلول: خوارزمية الإدراج بالكلمات
- صِف خوارزمية إضافة عنصر إلى طابور دائري. [4]
- إذا كان العدد مساويًا للحجم، أبلغ أن الطابور ممتلئ وتوقف.
- وإلا، أضف واحدًا إلى مؤشر الخلف؛ إذا تجاوز الآن آخر فهرس، ضعه عند أول فهرس.
- احفظ العنصر عند مؤشر الخلف وأضف واحدًا إلى العدد.
رتّب خطوات الإضافة إلى الطابور الدائري بالترتيب.
التحقق، التحريك، الدوران، التخزين، العد. الدوران هو ما يجعل المصفوفة دائرية.
قائمة مترابطة في مصفوفة
- استخدم مصفوفة من سجلات العقد، كل منها مؤشر
Next؛-1يُشكّل النهاية. مؤشرHeadيُشكّل أول عقدة،-1إذا كانت القائمة فارغة. - الشقوق غير المستخدمة مشبوكة في قائمة فراغية من
FreeListHead، تمامًا كما تشبك القائمة البياناتية المستخدمة.
TYPE TNode
DECLARE Value : INTEGER
DECLARE Next : INTEGER // index of the next node, or -1
ENDTYPE
DECLARE Nodes : ARRAY[1:MaxSize] OF TNode
DECLARE Head : INTEGER // -1 when empty
DECLARE FreeListHead : INTEGER // first unused slot
- الإدراج: خذ الشق عند
FreeListHead، حددValueوNextالخاص به، ثم أعد توصيلNextأوHeadللعقدة السابقة. الحذف: افصل العقدة وأعد شقها إلى مقدمة القائمة الفراغية.
قائمتان تشاركان مصفوفة واحدة: قائمة البيانات وقائمة الفراغ
في القائمة المرتبطة القائمة على المصفوفة، قائمة الفراغ:
تربط قائمة الفراغ بالخانات الفارغة، بحيث يمكن للإدراج الحصول على واحدة ولالحذف إرجاع واحدة — كقائمة مرتبطة ثانية من الخانات الفارغة.
مثال محلول: إدراج في القائمة المحفوظة بالمصفوفة
- مصفوفتا
DataوPointerتحملان القائمة 1 → 3 → 4، معStart = 1؛ الفهرس 1 يحتوي علىD40، الفهرس 3 يحتوي علىD32، الفهرس 4 يحتوي علىD11مع مؤشر فارغ. قائمة الفراغ تبدأ من الفهرس 2 وتستمر 2 → 5. أدخلD6بينD32وD11. - خذ أول عقدة فارغة، الفهرس 2، وحدد
FreeStartبمؤشره، 5. احفظD6فيData[2]. - حدد
Pointer[2]بالقيمةPointer[3]المحتواة، وهي 4. ثم حددPointer[3]بـ 2. - تصبح القائمة الآن 1 → 3 → 2 → 4 وقائمة الفراغ هي 5 → فارغ. التنفيذ، إذا طُلب: مصفوفة للبيانات، مصفوفة موازية (أو حقل سجل) للمؤشرات، مؤشر بداية، ومؤشر لقائمة الفراغ.
في المثال المحلول، بعد إدراج D6 تبدأ قائمة الفراغ عند الفهرس ____.
تم استخلاص الفهرس 2 من قائمة الفراغ، لذا ينتقل FreeStart إلى ما أشار إليه الفهرس 2، وهو 5.
عند الإدراج في القائمة، يجب تغيير مؤشر العقدة السابقة قبل تعيين مؤشر العقدة الجديدة.
ضع مؤشر العقدة الجديدة في العقدة التالية القديمة أولاً. إعادة توصيل العقدة السابقة أولاً يفقد عنوان باقي القائمة.
علامات ضائعة
- التحقق يأتي أولاً: الامتلاء قبل الدفع أو الإدراج الدائري، والفراغ قبل السحب أو الإخراج الدائري. صِفهم؛ فهم درجات.
- معادلة العودة تعتمد على المؤشرات:
(Rear MOD MaxSize) + 1للمؤشرات بدءاً من 1،(Rear + 1) MOD Sizeللمؤشرات بدءاً من 0. طابق حدود السؤال. - العدد هو ما يُميز الطابور الدائري الممتلئ عن الفارغ. المؤشرات وحدها لا تستطيع ذلك.
- حدد
Nextللعقدة الجديدة قبل إعادة توصيل العقدة السابقة، وأعد شق عقدة محذوفة إلى قائمة الفراغ، أو تمتلئ المصفوفة ببطء بخلايا غير قابلة للوصول.
لقد فهمت الأمر
- كومة في مصفوفة:
Stack[1:MaxSize]وTopمؤشر يبدأ من 0؛Top = MaxSizeهو Overflow،Top = 0هو Underflow - طابور دائري:
FrontوRearيعودان معMOD؛ عدد منفصل يُميز الممتلئ عن الفارغ - قائمة مترابطة في مصفوفة: سجلات عقد بها مؤشر
Next، وHead، وقائمة فراغية تشبك الشقوق الزائدة - كل عملية هي التحقق، ثم حساب المؤشرات، ثم الحفظ أو القراءة؛ سلوك ADT يبقى دون تغيير بغض النظر عن طريقة حفظه