الأنواع المجردة للبيانات — الكومة، الطابور، القائمة المرتبطة
| English | العربية |
|---|---|
| queue/kjuː/ | صف |
| push/pʊʃ/ | دفع |
| abstract data type/ˈæbstrækt ˈdeɪtə taɪp/ | نوع البيانات المجرد |
| stack/stæk/ | مكدس |
| linked list/lɪŋkt lɪst/ | قائمة مرتبطة |
| LIFO/ˈlaɪfəʊ/ | LIFO |
| pop/pɒp/ | إزالة |
| pointer/ˈpɔɪntə/ | مؤشر |
| FIFO/ˈfaɪfəʊ/ | FIFO. |
| enqueue/enˈkjuː/ | إضافة للصف |
| dequeue/diːˈkjuː/ | إزالة من الصف |
| node/nəʊd/ | عقدة |
| traverse/trəˈvɜːs/ | استعراض |
زر الرجوع وطابور الطابعة
- كل صفحة تزورها تُدفع فوق كومة؛ يأخذ زر الرجوع الصفحة العلوية منها. الصفحة التي تركتها مؤخراً هي الأولى التي تعود إليها.
- على طول الممر، تعمل الطابعة على المهام بالترتيب الذي وصلت فيه. المستند المُرسَل أولاً يطبع أولاً، بغض النظر عن صغر حجم المستندات التي تليه.
- هيكلايان بقواعد متعاكسة، وتستخدم كليهما قبل الاستراحة. لا أحدهما يوضح كيفية تخزينه؛ كل منهما يصف فقط ما تقوم به عملياته.
- هذا نوع بيانات مجرد. هذه الدروس الثلاثة التي يذكرها المنهج، والعمليات على كل منها، وكيفية تبرير اختيار واحد لموقف معين.
ما هو النوع المجرد للبيانات
- النوع المجرد للبيانات (ADT) هو مجموعة من البيانات معًا مصحوبة بمجموعة من العمليات على تلك البيانات. هذه الجملة الواحدة هي التعريف الذي قيمة الدرجة.
- يُعرف بـ ماذا تفعل العمليات، وليس بكيفية تخزين البيانات. التنفيذ مخفي، لذا يمكن تغييره دون التأثير على الكود الذي يستخدمه.
- الكومة، والطابور، والقائمة المرتبطة، والشجرة الثنائية، والمصفوفة هي جميعها أنواع بيانات مجردة.
يتم تعريف نوع البيانات التجريدي (ADT) بـ:
حدد ADT العمليات (الواجهة)؛ التنفيذ مخفي ويمكن تغييره بحرية.
الكومة
- الكومة هي قائمة تُضاف إليها العناصر وتُزال من نفس الطرف، وهو القمة، بحيث يكون آخر عنصر مُضاف هو أول عنصر يُزال: LIFO.
- العمليات: push (إضافة) تضيف إلى القمة، وpop (إزالة) تزيل من القمة، وpeek (استعراض) ينظر إلى القمة، واختبار الفراغ والممتلئ.
- الاستخدامات: تاريخ التراجع، زر الرجوع، عناوين إرجاع استدعاءات الدوال، التحقق من الأقواس، التتبع الخلفي.
كل شيء يحدث عند القمة
بأي ترتيب يعمل المكدس؟
المكدس LIFO: العنصر الذي تم إدراجه مؤخراً هو الأول الذي يُزال.
مثال محلول: تتبع الكومة
- تحتوي الكومة، من الأسفل، على
'P' 'N' 'Z' 'X' 'Y' 'W'؛ ومؤشر القمة عند'W'. تم تنفيذ العملياتPOP،POP،PUSH 'A'،PUSH 'B'،POP. ماذا تحتوي الكومة الآن، وأين المؤشر؟ - الإزالتان تزيلان
'W'ثم'Y'. الإضافتان تضعان'A'ثم'B'مكانهما. الإزالة الأخيرة تزيل'B'. - الكومة تحتوي على
'P' 'N' 'Z' 'X' 'A'، مع المؤشر عند'A'. العنصر الموجود في الكومة لأطول فترة هو السفلي،'P'؛ هناك خمسة إضافيات ممكنة أخرى، وسادسها سيكون خطأ، ولهذا السبب يختبر pop الفراغ أولاً.
المكدس يحتوي على P N Z X Y W (العنصر الأعلى هو W). بعد POP, POP, PUSH 'A', PUSH 'B', POP، أي عنصر أصبح في الأعلى؟
تم إخراج W وY، ثم إدخال A ثم B، ثم إخراج B. العنصر الأعلى هو A، فوق X.
الطابور
- الطابور هو قائمة تُضاف إليها العناصر من الخلف وتُزال من الأمام، بحيث يكون أول عنصر مُضاف هو أول عنصر يُزال: FIFO.
- العمليات: enqueue (إضافة) تضيف من الخلف، وdequeue (إزالة) تزيل من الأمام، واختبار الفراغ والممتلئ.
- الاستخدامات: طباعة المستندات المتراكمة، ذاكرة التخزين المؤقت للوحة المفاتيح، الجدولة، العملاء في متجر، البحث بالأعمق.
انضم من الخلف، غادر من الأمام
الكومات، الطوابير والقوائم المرتبطة
LIFO مقابل FIFO
الـ مكدس يعمل بنظام آخرهم أولاً (LIFO)؛ يتم الإدراج والإزالة من نفس الطرف (الأعلى).
الطابور يعمل بنظام أول دخل أول خروج: يتم إزالة العناصر من ______ وإضافتها في الخلف.
FIFO: إزالة من الأمام، وإضافة في الخلف — مثل طابور الأشخاص.
مثال محلول: وصف الإضافة والإزالة من طابور
- الإضافة: تحقق من أن الطابور ليس ممتلئاً؛ احفظ العنصر عند الموقع المحدد بواسطة مؤشر الخلف؛ تحرك بمؤشر الخلف للأمام (وأضف واحداً للعدّاد).
- الإزالة: تحقق من أن الطابور ليس فارغاً؛ اقرأ العنصر عند مؤشر الأمام؛ تحرك بمؤشر الأمام للأمام (وطرح واحداً من العدّاد).
- حدد约定 الذي تستخدمه: إذا كان مؤشر الخلف يشير إلى المساحة الحرة التالية، احفظ أولاً ثم تحرك؛ وإذا كان يشير إلى آخر عنصر، تحرك أولاً ثم احفظ. كلاهما يمنح الدرجة، بشرط الاتساق.
رتّب خطوات إضافة عنصر إلى الطابور بالترتيب (مؤشر الخلف يشير إلى الفراغ التالي).
يأتي التحقق أولاً؛ ثم التخزين، ثم التحريك، تحت هذا约定. حدد أي约定 تستخدم.
القائمة المرتبطة
- القائمة المرتبطة هي قائمة يحتوي فيها كل عقدة على عنصر بيانات ومؤشر إلى العقدة التالية، مع مؤشر بداية للعقدة الأولى. مؤشر العقدة الأخيرة هو مؤشر حارس مثل
NULL. - العمليات: الإدراج، الحذف، البحث، والمرور، باتباع المؤشرات من الرأس لزيارة كل عقدة بالترتيب.
- الميزة على مصفوفة: الإدراج أو الحذف رخيص، مجرد إعادة توصيل المؤشرات، والنمو حسب الحاجة. العيب: لا يوجد وصول عشوائي؛ الوصول إلى العقدة العاشرة يتطلب تتبع تسعة مؤشرات.
قيمة وسهم، مكرر
قائمة مترابطة: عقد متصلة بواسطة مؤشرات.
كل عقدة تخزن قيمة ومؤشراً إلى العقدة التالية. الإضافة أو الحذف يعيد ربط المؤشرات فقط — لا تنزح العناصر، على عكس المصفوفة.
كل عقدة في القائمة المترابطة تحتوي على:
تخزن العقدة قيمتها بالإضافة إلى مؤشر (مرجع) إلى العقدة التالية؛ الرأس يحدد البداية، والفراغ (NULL) يحدد النهاية.
القائمة المترابطة تجعل الإدراج/الحذف رخيصاً (فقط إعادة توصيل المؤشرات) لكن الوصول العشوائي بطيء (يجب اتباع المؤشرات من الرأس).
هذا هو التوازن بين المصفوفة والقائمة: تعطي المصفوفة وصولاً بالفهرس O(1)؛ القوائم تعطي إدراج/حذف رخيصاً.
مثال محلول: إضافة عقدة بترتيب
- وصف كيفية إدراج قيمة جديدة في قائمة مرتبطة تُحفظ بترتيب تصاعدي. [4]
- مرر القائمة من الرأس، باتباع المؤشرات، حتى توجد العقدة قبل الموقع: آخر عقدة قيمتها أصغر من القيمة الجديدة.
- خذ عقدة حرة واحفظ القيمة الجديدة فيها. اضبط مؤشر العقدة الجديدة على العنوان الذي يشير إليه العقدة السابقة حالياً.
- ثم اضبط مؤشر العقدة السابقة على العقدة الجديدة. إذا كانت القيمة الجديدة تنتمي للأمام، فإن مؤشر الرأس هو الذي يتغير بدلاً من ذلك.
رتّب خطوات إدخال قيمة في قائمة مترابطة مرتبة بالترتيب.
العثور، التعبئة،指向 العقدة الجديدة للأمام، ثم إعادة توصيل العقدة السابقة. عكس الأخيرين يفقد باقي القائمة.
تبرير الاختيار
- العناصر يجب معالجتها بترتيب وصولها، طباعة المستندات، ضغطات المفاتيح، العملاء: طابور، لأنه أول ما يدخل أول ما يخرج.
- يجب معالجة أحدث عنصر أولاً، التراجع، العودة، الاستدعاءات المتداخلة: مكدس، لأنه آخر ما يدخل أول ما يخرج.
- يتم إدراج أو حذف عناصر بشكل متكرر في وسط مجموعة مرتبة، والحجم غير معروف: قائمة مرتبطة، لأن المؤشرات فقط تتغير ولا يتم إزاحة شيء.
- سمِ البنية، سمِّ قاعدتها، اربط القاعدة بالموقف.
طابق كل ADT بقاعدته واستخدامه النموذجي.
المكدس = آخر دخل أول خروج؛ الطابور = أول دخل أول خروج؛ القائمة المترابطة تربط العقد بالمؤشرات.
يجب طباعة المهام المطبوعة بنفس ترتيب إرسالها. أي ADT ولماذا؟
ترتيب الوصول هو قاعدة FIFO. المكدس سيطبع أحدث مهمة أولاً.
ADT مقابل التنفيذ
- الـADT هو السلوك: الدفع والرفع،enqueue وdequeue، الإدراج والمرور.
- التنفيذ هو التخزين: في هذا المقرر، مصفوفة بالإضافة إلى بعض متغيرات المؤشرات (الدرس القادم).
- سؤال عن الـADT يطلب عمليات وقواعد؛ سؤال عن التنفيذ يطلب مصفوفات ومؤشرات وفحوصات.
علامات ضائعة
- الدفع وenqueue يختبران الممتلئ أولاً؛ الرفع وdequeue يختبران الفارغ أولاً. اكتب الفحص في الوصف.
- الإدراج في قائمة مرتبطة: اضبط مؤشر العقدة الجديدة قبل تغيير مؤشر العقدة السابقة، وإلا ستفقد باقي القائمة.
- المكدس يتغير عند طرف واحد، والطابور عند الطرفين. "أزل من أعلى الطابور" هو إجابة مكدس.
- فك الاختصارات مرة واحدة: LIFO، آخر ما يدخل أول ما يخرج؛ FIFO، أول ما يدخل أول ما يخرج.
لقد فهمت الأمر
- ADT هي مجموعة بيانات مع مجموعة من العمليات عليها؛ سلوك، وليس تخزيناً
- مكدس: إضافة وإزالة من الأعلى، LIFO، push وpop · طابور: إضافة من الخلف، إزالة من الأمام، FIFO، enqueue وdequeue
- قائمة مرتبطة: عقدات قيمة + مؤشر من مؤشر رأس؛ إدراج وحذف رخيصان، وصول عشوائي بطيء؛ المرور بتتبع المؤشرات
- برّر بالقاعدة: ترتيب الوصول → طابور؛ أحدث أولاً → مكدس؛ إدراج متكرر في الوسط → قائمة مرتبطة