السلام عليكم ورحمة الله و بركاته
كنا قد تحدثنا في الحلقة الأولى من هذه السلسلة عن القوائم المتصلة البسيطة و يسرني أن أبدأ معكم في شرح الجزء الثاني و الذي يتعلق بالقوائم المزدوجة (Doubly Linked List).
الفهرس
- تعريف
- ͏الإعلان عن القائمة
- تهيئة القائمة (إنشاء أول عقدة)
- إضافة عقدة جديدة.
- حذف عقدة معينة.
- حساب طول القائمة.
- دمج قائمتين في قائمة واحدة
- حذف قائمة
- اختبر قدراتك
تعريف
تتميز القوائم المزدوجة بوجود مؤشرين في كل عُقدة, المؤشر الأولى يُشير إلى العُقدة السابقة و المؤشر الثاني يُشير إلى العقدة الموالية.
بشكل عام, المؤشرات هي ما يميز طبيعة الحركة في القوائم, أياً كان نوعها, و في حالتنا هذه فإن القوائم المزدوجة تتميز بالقدرة على الحركة في كلا الاتجاهين نظرا لوجود مؤشر سابق و آخر لاحق في كل عقدة.
تنويه
في بقية المقالة :
- سأقوم بتقسيم الكود الكامل إلى مجموعة دوال للتوضيح.
- إذا اجتمعت في الكود عدة دوال تشترك في نوعية الخطأ (فشل عملية الحجز مثلاً) سيتم التحقق من دالة واحدة فقط و ذلك تجنباً للتكرار.
- كل جزء من الكود سيكون مُرتبطاً بالجزء السابق له.
الإعلان عن القائمة
عند التعامل مع القوائم, يُستحسن دائما استخدام قائمة مُساعدة تأتي فائدتها في تخزين بعض المعلومات التي تخص القائمة الأصلية, مثل عناوين العُقد الرئيسية (الأولى و الأخيرة مثلاً) و طول القائمة و ما إلى ذلك ..
لتبسيط الأمور, نفترض أن القائمة التي سنعمل عليها تحوي عنصرا واحدا عبارة عن متغير من نوع int. الإعلان عن القائمة سيكون هكذا:
لا شيء جديد, فقط قمنا بالإعلان عن قائمة تحوي 3 عناصر : متغير من نوع int ومؤشر على العقدة السابقة و آخر على العقدة اللاحقة. ثم قمنا بإعطاء اسم مستعار لمؤشر القائمة.
بالنسبة للقائمة الـمُساعدة فستكون هكذا:
القائمة الـمُساعدة تحتوي على متغير من نوع int يُمثل طول القائمة و مؤشرين, الأول يُشير إلى بداية القائمة الأصلية و الثاني يُشير إلى نهايتها.
تهيئة القائمة (إنشاء أول عقدة)
نأتي الآن إلى كيفية تهيئة القائمة من خلال إنشاء عقدة جديدة و إسناد قيم ابتدائية لكافة البيانات:
الدالة init تستقبل وسيط واحد عبارة عن مرجع (Reference) للقائمة المزدوجة, في السطر الأول قمنا بحجز ذاكرة للمؤشر الذي سيُشير إلى أول عقدة في القائمة, إذا فشلت عملية الحجز ستعيد الدالة false و ينتهي الأمر, أما إذا مرت عملية الحجز بسلام فهذا يدل على أن المؤشر argDbll أصبح يُشير إلى منطقة من الذاكرة تحوي 3 عناصر (المتغير الصحيح, المؤشر السابق و المؤشر اللاحق) و في هذه الحالة سنقوم بإسناد قيمة ابتدائية لكل عنصر.
بعد تهيئة العناصر الثلاثة تقوم الدالة بإعادة true كإشارة إلى نجاح العملية.
ملاحظات هامة:
- في حالة عدم وجود العُقدة السابقة يُشير المؤشر السابق إلى NULL.
- في حالة عدم وجود العُقدة الموالية يُشير المؤشر اللاحق إلى NULL.
- إذا كانت القائمة تحتوي على عُقدة واحدة فهذا يعني دمج الملاحظتين السابقتين.
- العمليات المختلفة (تهيئة, إضافة, حذف, ..) سيتم تطبيقها على القائمة الأصلية من خلال القائمة الـمُساعدة.
نأتي الآن إلى تضمين المكتبات اللازمة بالإضافة إلى شرح مختصر لمحتوى الدالة الرئيسية :
الدالتان printf و fprintf موجودتان في المكبتة stdio.h و الماكرو EXIT_FAILURE و EXIT_SUCCESS موجود في المكتبة stdlib.h و النوع bool مُعرف في المكتبة stdbool.h لذا قمنا باستدعاء المكتبات الثلاثة معاً. في بداية الدالة الرئيسية قمنا بالإعلان عن قائمة جديدة و أسندنا لها العنوان NULL وهذه الخطوة ضرورية جدا في تهيئة المؤشرات بغض النظر عما تُشير إليه. بعد ذلك, قمنا بتمرير القائمة myDoubleList إلى الدالة init كوسيط ثم تحققنا من القيمة الـمُعادة من طرف الدالة, إذا كانت false سيتم إظهار رسالة تنبيه على الشاشة و إلا فسيتم إظهار البيانات الابتدائية للعقدة الجديدة.
و هذه صورة لـمُخرجات الكود :
لاحظ أن طول القائمة يُساوي 0, البعض يرى أن الصفر غير مناسب في هذه الحالة لأنه على الأقل تحتوي القائمة حالياً على عُقدة واحدة و بالتالي يجب أن يكون طول القائمة يُساوي واحد و ليس صفر, هذه وجهة النظر الأولى.
وجهة النظر الثانية (و هي التي أميل إليها) يقول أصحابها أنه حتى لو كانت القائمة تحتوي حالياً على عُقدة واحدة فإن هذه العُقدة خالية من المعلومات و لا تُشكل عُقدة حقيقة تُؤثر على طول القائمة و بالتالي يُمكن تجاهلها. في معظم الحالات تتم العودة لاحقاً إلى هذه الُعقدة لتعديل بياناتها إلى بيانات حقيقية عن طريق إدراج عدد جديد كقيمة للمتغير الصحيح الموجود في العقدة, و بعدها تتم زيادة طول القائمة بواحد.
بالنسبة للعناوين فمن الطبيعي جداً أن تظهر الأصفار كقيم لعناوين المؤشرات لأن المؤشر NULL يملك العنوان 0x00000000 وفي العادة يكون هذا العنوان Invalid Memory Address في أغلب نظم التشغيل. يُستخدم الـ Null Pointer للدلالة على أن المؤشر فارغ أي لم يتم حجز ذاكرة له بعد.
إضافة عقدة جديدة
لإضافة عقدة جديدة إلى القائمة, يجب أن نمر بالخطوات التالية:
- حجز مساحة من الذاكرة للعقدة الجديدة.
- تهيئة كافة عناصر العقدة.
- المؤشر السابق للعقدة الجديدة سيُشير إلى NULL.
- المؤشر اللاحق للعقدة الجديدة سيُشير إلى بداية القائمة.
- إذا كانت القائمة غير فارغة نجعل المؤشر السابق لبداية القائمة يُشير إلى العُقدة الجديدة.
- في الحالة الـمُعاكسة نجعل المؤشر last يُشير إلى العُقدة الجديدة.
- نقوم بتحديث القائمة من خلال جعل العُقدة الجديدة هي الأولى.
- نزيد طول القائمة بواحد.
و بالتالي, دالة الإضافة ستكون هكذا:
كالعادة, إذا لم تنجح عملية الحجز ستُعيد الدالة false و إلا فالقيمة الـمُعادة ستكون true, هذا من جهة. من جهة أخرى, قمنا بتطبيق الخطوات التي ذكرناها آنفا, لا أكثر و لا أقل 
نأتي الآن إلى تضمين المكتبات اللازمة بالإضافة إلى تعليق موجز حول الــ main :
في البداية, قمنا بتهيئة القائمة المزدوجة ثم استدعينا دالة الإضافة و تحققنا من القيمة الـمُعادة كما فعلنا سابقا مع دالة التهيئة, إذا تمت إعادة false نُظهر رسالة الخطأ و إلا فسنستدعي الدالة display المسئولة عن إظهار بيانات القائمة (سنشرح هذه الدالة لاحقاً).
مُخرجات الكود ستكون على هذا النحو:
لاحظ أنه لم يتم إظهار بيانات العقدة الفارغة لأنها مُحاطة بعناوين فارغة و بالتالي ستتوقف الدالة عن الإظهار عندما تصل إليها.
من ناحية أخرى, إدراج العُقدة الجديدة حدث قبل الُعقدة الأولى و هذا ما يُسمى بالإضافة في بداية القائمة, يُمكننا أيضا أن نُضيف العُقدة في نهاية القائمة أو في أي مكان آخر و هنا تكمن أحد أبرز نقاط القوة لدى القوائم و هي المرونة.
بالنسبة لإضافة العُقدة في نهاية القائمة فستكون هكذا:
نفس الخطوات السابقة مع تعديل طفيف يتمثل في :
- جعل المؤشر السابق للعقدة الجديدة يُشير إلى نهاية القائمة.
- إسناد القيمة NULL إلى المؤشر اللاحق للعقدة الجديدة.
- إذا كانت القائمة غير فارغة نجعل المؤشر اللاحق لنهاية القائمة يُشير إلى العُقدة الجديدة.
- في الحالة الـمُعاكسة نجعل المؤشر first يُشير إلى العُقدة الجديدة.
- نقوم بتحديث القائمة من خلال جعل العُقدة الجديدة هي آخر عُقدة.
- نزيد طول القائمة بواحد.
الصورة التالية تُوضح مفهوم الإضافة في نهاية القائمة المزدوجة:
يُمكننا أيضا إضافة عقدة جديدة في أي مكان من القائمة, لنفترض مثلا أننا نريد إدراج عقدة جديدة بعد عقدة أخرى يتم تحديد رقهما في القائمة. في هذه الحالة ستكون الخُطوات الـمُتبعة هي:
- الانتقال إلى العُقدة المحددة, توجد حالتان:
- إذا وصلنا إلى NULL فهذا يعني أن رقم العقدة غير موجود, حينها نقوم بإعادة false.
- في الحالة المعاكسة نقوم بالآتي:
- حجز مساحة من الذاكرة للعقدة الجديدة.
- تهيئة كافة عناصر العقدة.
- جعل المؤشر اللاحق للعقدة المحددة يُشير إلى المؤشر السابق للعقدة الجديدة.
- جعل المؤشر السابق للعقدة الجديدة يُشير إلى المؤشر اللاحق للعقدة المحددة.
- جعل المؤشر اللاحق للعقدة الجديدة يُشير إلى المؤشر الذي يُشير إليه المؤشر اللاحق للعقدة المحددة.
- جعل المؤشر السابق للعقدة التي تلي العقدة المحددة يُشير إلى المؤشر اللاحق للعقدة الجديدة.
- المؤشر first لن يتغير.
- المؤشر last يتغير فقط إذا كانت العُقدة المحددة هي آخر عقدة.
- زيادة طول القائمة بواحد.
و بالتالي دالة الإضافة ستكون هكذا:
إذا لم تنجح عملية الحجز أو لم يتم العثور على رقم العقدة ستُعيد الدالة false و إلا فستعيد الدالة true بعد أن تتم إضافة العُقدة الجديدة و تحديث القائمة.
الآن أصبح من السهل جداً كتابة دالة تقوم بتعديل بيانات عقدة مُعينة, فقط بدلا من إدراج عُقدة جديدة, نقوم بتغيير بيانات العُقدة التي توقفت عندها الحلقة for ما لم تكن تلك العقدة فارغة.
هذا مثال على استدعاء الدالة addAfterACertainNode في الــ main :
يُمكننا جعل الدالة addAfterACertainNode تعيد int و نخصص قيمة لكل خطأ فمثلا يمكننا اعتبار أن الصفر يدل على عدم وجود العقدة و 1 يدل على فشل عملية الحجز و 2 تدل على نجاح عملية الإدراج كما يُمكننا أيضا جعل الدالة تعيد void و في هذه الحالة يُستحسن إضافة رسائل الخطأ داخل جسم الدالة.
على كل حال, الـمُخرجات ستكون هكذا:
نأتي الآن إلى شرح كيفية عمل دالة الإظهار التي تقوم بعرض محتويات القائمة :
حتى لا نفقد بيانات القائمة, قمنا بتخزين نسخة من عنوان العقدة الأولى داخل المؤشر currentPointer و مادام هذا الأخير غير فارغ, سيتم إظهار العدد الموجود في العقدة الحالية و الانتقال إلى العقدة الموالية. بالنسبة للمتغير i فتأتي فائدته في ترقيم عناصر العقدة.
حذف عقدة مُعينة
كما فعلنا سابقا مع عملية الإضافة, يمكننا أيضا حذف عُقدة من البداية, النهاية أو أي مكان آخر من القائمة.
فمثلا, الدالة التالية تقوم بحذف آخر عُقدة من القائمة :
الخُطوات الـمُتبعة هي:
- نُخزن عنوان آخر عقدة في متغير مؤقت.
- إذا كانت القائمة فارغة, تتم إعادة false و ينتهي الأمر.
- في الحالة المعاكسة نقوم بالخطوات التالية:
- نجعل المؤشر اللاحق للعقدة القبل الأخيرة يُشير إلىNULL.
- نقوم بتحديث القائمة من خلال جعل العُقدة القبل الأخير هي آخر عقدة.
- ننقص طول القائمة بواحد.
- نُحرر العنوان الذي كان يُشير إلى العُقدة الأخيرة.
هذا مثال على استدعاء الدالة removeTheLast في الــ main :
إذا كانت القائمة فارغة سيتم إظهار رسالة الخطأ, في الحالة المعاكسة سيتم إظهار عناصر القائمة قبل و بعد الحذف.
الـمُخرجات ستكون هكذا:
الصورة التالية تُوضح مفهوم حذف آخر عُقدة في قائمة مزدوجة:
أما إذا أردنا حذف عقدة من بداية القائمة فستكون الخطوات كما يلي
- تخزين عنوان العقدة الأولى داخل متغير مؤقت.
- جعل مؤشر القائمة يُشير إلى العقدة الثانية.
- تحرير المؤشر الذي كان يُشير إلى العقدة الأولى.
و بالتالي دالة الحذف في هذه الحالة ستكون هكذا:
لاحظ أنه تم التأكد أن القائمة غير فارغة قبل إجراء عملية الحذف و هذا مُهم جدا إذْ يجب التأكد من مثل هذه الحالات قبل القدوم على تنفيذ العملية.
نأتي الآن إلى كيفية الحذف عن طريق تحديد قيمة المتغير elem في العقدة المُراد حذفها :
هذه المرة قمنا بالحذف على أساس العقدة التي تحمل قيمة معينة لــ elem و ليس على أساس رقم العقدة في القائمة.
الدالة السابقة بإمكانها حذف أي عُقدة من القائمة باستثناء العقدة الأولى و الأخيرة, يُمكننا إضافة شروط للتحقق من مكان العقدة فإذا كانت العقدة المراد حذفها هي العقدة الأولى نقوم باستدعاء الدالة removeTheFisrst و removeTheLast إذا كانت آخر عقدة.
بالنسبة لتفاصيل الدالة فعند الخروج من while سنكون أمام خيارين, الخيار الأول يعني أنه لا توجد عقدة تحمل القيمة elem التي تم إرسالها للدالة, حينها سنقوم بإعادة false و تنتهي المهمة, إذا تجاوزنا الــ if بسلام فهذا يعني أنه توجد عُقدة تحمل قيمة elem داخلها, لذا سنقوم بتخزين العقدة التي تُحقق الشرط في المؤشر tmpNode ثم نُحرر عنوان تلك العُقدة بعد أن نربط بين العقدتين اللتين يحيطان بالعقدة المراد حذفها.
حساب طول القائمة
هذه المرة لن نحتاج إلى كتابة دالة منفردة لحساب الطول, لأن طول القائمة مُخزن في المتغير lengthOfTheList و يتم تحديث قيمته كلما تمت إضافة أو حذف عقدة معينة.
دمج قائمتين في قائمة واحدة
دالة الدمج تستقبل وسيطين يُمثلان القائمتين الـمُراد دمجهما :
إذا كانت القائمة الأولى فارغة, فهذا يعني أن دمج القائمتين يُعطي القائمة الثانية لذا تمت إعادتها. في الحالة الـمُعاكسة نقوم بربط آخر عُقدة من القائمة الأولى بأول عُقدة من القائمة الثانية.
حذف القائمة
دالة الحذف فكرتها كالآتي : في كل مرة نقوم بتخزين عنوان العقدة الحالية في مؤشر مؤقت ثم ننتقل إلى العقدة الموالية و نحرر المؤشر و هكذا حتى نصل إلى عنوان فارغ (NULL) مما يعني أن القائمة انتهت و بالتالي نخرج من الحلقة while.
ثم نقوم بتحديث عناصر المصفوفة المساعدة (نجعل المؤشرات تُشير إلى NULL و نُسند القيمة صفر إلى المتغير الذي يحوي طول القائمة).
اختبر قدراتك
لتكن لدينا زجاجة تحتوي على 7 كرات, واحدة باللون الأحمر و اثنتين باللون الأصفر و أربعة باللون الأخضر. يقوم اللاعب بسحب كرة عشوائيا من الزجاجة, إذا كانت الكرة حمراء سيربح اللاعب 10 دولار و يخسر 5 دولار إذا كانت صفراء أما إذا كانت خضراء فسيحظى اللاعب بسحب كرة أخرى من الزجاجة (دون أن يعيد الكرة الأولى التي سحبها), إذا كانت الكرة الجديدة حمرءا سيربح 8 دولار و إلا سيخسر 4 دولار. تنتهي اللعبة عندما يصبح رصيد اللاعب يساوي صفر علما أن الرصيد الابتدائي لكل لاعب يُساوي 6 دولار.
قم بعمل برنامج صغير يُحاكي هذه اللعبة باستخدام القوائم المزدوجة.
إلى هنا أصل بك أخي القارئ إلى نهاية هذا الدرس, آمل أن تكون استفدت من هذا الدرس و تعلمتَ أشياء جديدة
تحياتي.
ممكن الايميل لي حضرتك يا استاذ احمد