القوائم المتصلة في لغة C

السلام عليكم و رحمة الله و بركاته

هذه هي الحلقة الأولى من سلسلة هياكل البيانات المتقدمة في لغة C حيث سنتطرق للمواضيع التالية تباعا :

Singly Linked List
Doubly Linked List
Stacks
Queues

و إذا وجدتُ متسعا من الوقت سأكتب عن :

Trees
Binary Trees
Hash tables
Graphs

هذه هي المقالة الأولى من هذه السلسلة و البقية تأتي ..

الفهرس

• الجانب النظري
  • تعريف
  • نبذة تاريخية
  • قالوا عن الــ Linked List
  • أيهما أفضل, المصفوفة الديناميكية أم القائمة المتصلة ؟
  • مفهوم القوائم المتصلة
• الجانب التطبيقي (العمليات الأكثر استخداما في القوائم)
  • مدخل
  • تهيئة القائمة (إنشاء أول عقدة)
  • إضافة عقدة جديدة.
  • حذف عقدة معينة.
  • حساب طول القائمة.
  • دمج قائمتين في قائمة واحدة
  • حذف قائمة
• اختبر قدراتك

لمن هذه الدروس ؟

هذه الدروس مُوجهة إلى كل من لديه معرفة بأساسيات السي مثل المصفوفات, التراكيب و المؤشرات و يتطلع إلى دراسة هياكل البيانات المتقدمة في لغة السي.

الجانب النظري

تعريف
القائمة المتصلة عبارة عن مجموعة من العُقد, مُخزنة في الذاكرة بشكل متصل و غير متسلسل و هذا أحد أبرز أوجه الخلاف بين القوائم المتصلة و المصفوفات.

نبذة تاريخية
كانت تُعرف القوائم المتصلة باسم NSS memory و تم تصميمها خلال السنتين 1955-1956, من طرف الثلاثي Allen Newell, Cliff Shaw و Herbert Simon برعاية المؤسسة الأمريكية للبحوث RAND Corporation.
كانت القوائم المترابطة هي البُنية الأساسية في لغتهم Information Processing Language (IPL) و كان المخترعون الثلاثة يستخدمون IPL لتطوير مجموعة من برامج الذكاء الاصطناعي, مثل Logic Theory Machine, General Problem Solver بالإضافة إلى Chess (لعبة الشطرنج).
نُشرت أعمال الفريق حول القوائم المتصلة في الــ IRE Transactions on Information Theory في سنة 1956 و عُقدت العديد من المؤتمرات خلال الفترة 1957 – 1959 ⁽¹⁾. أما التمثيل الحالي للقوائم المتصلة (حيث تتكون القائمة من مجموعة عقد مُرتبطة فيما بينها بواسطة أسهم) فقد تم تنشره في شهر فبراير من عام 1957 تحت عنوان Programming the Logic Theory Machine ².
في عام 1975 حصل الثنائي Allen Newell و Herbert Simon على جائزة Turing لمساهمتهم الفعالة في علم الذكاء الاصطناعي و التعامل مع القوائم.

قالوا عن الــ Linked List
بطبيعة الحال, يُمكن تعريف القوائم المتصلة بأكثر من طريقة لذا اقتطفت لكم بعض التعريفات التي وردت في أهم الكتب المتعلقة بهياكل البيانات:

• يقول Seymour Lipschutz في كتابه The data structures (Courses and problems) : “القائمة عبارة عن مجموعة خطية من عناصر البيانات”.
• بينما يرى John Rast Hubbard في كتابه Java Data Structures أن “القائمة عبارة عن حاوية متسلسلة العناصر و قادرة على إدراج و إزالة العناصر بشكل مطرد محليا, أي بغض النظر عن حجم الحاوية”.
• أما Alain-Bernard Fontaine فيرى في كتابه The C++ Standard Template Library أن “القوائم عبارة عن حاويات مُخصصة للقيام بعمليات معينة (مثل الإدراج و الإزالة) حيث تتم هذه العمليات في وقت ثابت مهما كان موقع العنصر داخل الحاوية”.
• و يعتبر الثلاثي Thomas Cormen, Charles Leiserson و Ronald Rivest في كتابهم Introduction to Algorithms أن “القائمة المتصلة عبارة عن هيكل بيانات يتم فيه ترتيب الكائنات بشكل خطي ولكن بخلاف المصفوفات التي تُحدد فيها العناصر عن طريق ترقيم الخانات, يتم تحديد عناصر القائمة المتصلة عن طريق مؤشر في كل كائن”

أيهما أفضل, المصفوفة الديناميكية أم القائمة المتصلة ؟
عادة ما يكون السؤال الذي يطرح نفسه عند المقارنة بين هياكل البيانات, هو:
ما مدى سهولة الوصول إلى عناصر المجموعة ؟ و كذا التنقل بين مختلف العناصر و إجراء العمليات الأكثر استعمالا ؟
للإجابة على هذا السؤال قُمنا بحساب التعقيد الزمني للعمليات الأكثر استعمالا:

لإضافة عنصر معين في الخانة رقم i من المصفوفة X يجب إزاحة size-i عنصر حيث size هو طول المصفوفة و بالتالي عملية الإضافة في المصفوفات تستغرق وقتاً لا يُستهان بها و يزداد الأمر سوءا كلما كثُرت العناصر. نفس الشيء يحدث مع عملية الحذف.
أما في القوائم المتصلة فعملية الحذف أو الإضافة تأخذ نفس الوقت بغض النظر عن طول القائمة أو المكان الـمُراد إضافة (حذف) العُقدة فيه (منه).
نلاحظ أن القوائم المتصلة تكون أسرع في عمليتي الإضافة و الحذف بينما تكون المصفوفة الـمُرتبة أسرع في عملية البحث و يتساوى الاثنان عند المرور على جميع العناصر.

مفهوم القوائم المتصلة

ذكرنا آنفا أن طريقة تخزين عناصر المصفوفة تختلف عن طريقة تخزين عناصر القائمة إذْ أن عناصر الأولى تُخزَّن في أماكن متتابعة في الذاكرة أما القوائم فلا يُشترط تتابع عناصرها لأن الوصول إلى أي عُقدة من القائمة يتم عن طريق مؤشر في العُقدة السابقة أما المصفوفات فيتم الوصول إلى خاناتها عن طريق الترقيم لذا لزمها تتابع الخانات.
القوائم المتصلة تنتمي إلى عائلة الــ Dynamic Data Structures لذا تجد أن عملية حجز الذاكرة تتم أثناء عمل البرنامج باستخدام malloc مثلا.

قبل أن ننتقل إلى الجانب التطبيقي, تذكر النقاط التالية جيدا لأنك ستحتاجها لفهم العمليات الأكثر استخداما في القوائم :

• تتكون القائمة المتصلة من مجموعة عُقد ترتبط فيما بينها عن طريق المؤشرات.
• كل عُقدة تحتوي على جزئين, الجزء الأول يحتوي على بيانات العقدة و الجزء الثاني عبارة عن مؤشر يُشير إلى العقدة الموالية.
• للوصول إلى عُقدة معينة, يجب الذهاب دائماً من أول عُقدة. و يتم الانتقال من العقدة الموالية عن طريق المؤشر الموجود في العُقدة السابقة.
• دائما ما يُشير المؤشر الموجود في آخر عقدة إلى NULL.
• عندما تكون أول عقدة هي آخر عُقدة, نقول أن القائمة فارغة.
• في القوائم المتصلة البسيطة (Singly Linked List) تتم الحركة في اتجاه واحد, انطلاقا من العُقدة الأولى باتجاه العقدة الأخيرة.
• إذا كنتَ تريد التحرك في كلا الاتجاهين, يُمكنك استخدام القوائم المتصلة الـمُضاعفة (Doubly Linked List).

الجانب التطبيقي

مدخل
في بقية هذه الفقرة, سنعتبر أن القائمة التي نعمل عليها تحتوي على بيانات مجموعة من الموظفين في شبكة محلية تابعة لشركة مسابقات, كل مُوظف يملك رقم دخول و بريد الكتروني, نفترض أن رقم الدخول يُميز كل موظف عن الآخر بمعنى أنه لا يُمكن أن نجد مُوظفيْن يملكان نفس رقم الدخول. كما أن أرقام الدخول يجب أن تكون أكبر تماماً من الصفر.
قامت الشركة بتنظيم المسابقة التالية لموظفيها على النحول التالي:
كل مُوظف سيختار حرف عشوائي من A إلى Z. يفوز الموظف إذا تطابق الحرف الـمُختار مع أول حرف من مُعرَّفه (الجزء الموجود قبل @ من البريد الالكتروني) و يخسر في الحالة المعاكسة.
الإعلان عن القائمة التي ستضم بيانات الموظفين سيكون هكذا:

كلما في الأمر أننا قمنا بالإعلان عن بنية باسم singlyLinkedList تحتوي على 4 عناصر, العناصر الثلاثة الأولى تُمثل بيانات الموظف و العنصر الرابع عبارة عن المؤشر الذي يُشير إلى الموظف الموالي.
الخطوة التالية تتمثل في بناء القائمة عن طريق الإعلان عن المؤشر الذي سيُشير لاحقا إلى أول عُقدة, قُمنا بإعطاء اسم مستعار لمؤشر القائمة من أجل تسهيل و تنظيم الكتابة:

تهيئة القائمة (إنشاء أول عقدة)
نأتي الآن إلى كيفية تهيئة قائمة الموظفين من خلال إنشاء حساب لموظف جديد و إسناد قيم ابتدائية لكافة البيانات:

ملاحظات هامة:

• إذا كانت P عبارة عن بنية تحوي (مثلاً) عنصرين x و y فإن الوصول إلى عناصر البنية يكون هكذا P.x Or P.y.
• إذا كان Q مؤشر لبنية من نوع P, فإن الوصول إلى عناصر البنية يكون هكذا : Q->x Or Q->y.
• لغة C لا تدعم التمرير بالمرجع (Pass by reference) على عكس C++.
• تستخدم C تمرير المؤشرات الثابتة بدلا من تمرير المراجع لكنني أفضل دائما التمرير بالمرجع و لحسن الحظ, معظم مترجمات C الحالية (الـمُحتكة بــ CPP) تدعمه.

بالنسبة للدالة init فتستقبل وسيط واحد عبارة عن مرجع (Reference) لقائمة الموظفين, في السطر الأول قمنا بحجز ذاكرة للمؤشر الذي سيُشير إلى أول عقدة في القائمة, إذا فشلت عملية الحجز ستعيد الدالة false و ينتهي الأمر, أما إذا مرت عملية الحجز بسلام فهذا يدل على أن المؤشر sll أصبح يُشير إلى منطقة من الذاكرة تحوي 4 عناصر (رقم الدخول, الحرف العشوائي, البريد الالكتروني و المؤشر) و في هذه الحالة سنقوم بإسناد قيمة ابتدائية لكل عنصر على النحو التالي:
إسناد القيمة 0 إلى المتغير Login و تخزين المسافة البيضاء داخل المتغير randomCharacter و إسناد المؤشر NULL إلى ptrNext أما المتغير email فله حالته الخاصة, لأنه عبارة عن نوع مُركب و ليس نوع بسيط مثل (int, float, char, bool, ..).
الأنواع الـمُركبة (مثل المصفوفات و التراكيب ,..) يتم التعامل معها بصفة مختلفة لذا قُمنا باستدعاء الدالة memset لتصفير الذاكرة التي يُشير إليها المؤشر email, الدالة memset تستقبل 3 معاملات, المعامل الأول هو المؤشر الـمُراد تصفير ذاكرته و المعامل الثاني هو القيمة المراد وضعها داخل المنطقة التي يشير إليها المؤشر و المعامل الثالث هو عدد البايتات أو كمية البيانات الـمُؤشر عليها.
بعد تهيئة العناصر الأربعة تقوم الدالة بإعادة true كإشارة إلى نجاح العملية.

نأتي الآن إلى تضمين المكتبات اللازمة بالإضافة إلى شرح مختصر لمحتوى الدالة الرئيسية :

الدالة printf موجودة في المكبتة stdio.h و الماكرو NULL موجود في المكتبة stdlib.h و الدالة memset موجودة في المكتبة string.h لذا قمنا باستدعاء المكتبات الثلاثة معاً.
في بداية الدالة الرئيسية قمنا بالإعلان عن قائمة جديدة و أسندنا لها العنوان NULL وهذه الخطوة ضرورية جدا في تهيئة المؤشرات أيا كانت.
بعد ذلك, قمنا بتمرير القائمة mySimpleList إلى الدالة init كوسيط ثم تحققنا من القيمة الـمُعادة من طرف الدالة, إذا كانت false سيتم إظهار رسالة تنبيه على الشاشة و إلا فسيتم إظهار البيانات الابتدائية للموظف.
و هذه صورة لمُخرجات الكود :

إضافة عقدة جديدة
لإضافة عقدة جديدة إلى القائمة, يجب أن نمر بالخطوات التالية:

• حجز مساحة من الذاكرة للعقدة الجديدة.
• تهيئة كافة عناصر العقدة بما في ذلك المؤشر.
• إضافة العقدة و تحديث القائمة.

و بالتالي, دالة الإضافة ستكون هكذا:

كالعادة, إذا لم تنجح عملية الحجز ستُعيد الدالة false و إلا فالقيمة الـمُعادة ستكون true, هذا من جهة. من جهة أخرى, تستقبل الدالة 3 وسائط, الأول عبارة عن مرجع (Reference) لقائمة الموظفين و الوسيط الثاني عبارة عن رقم دخول الموظف الجديد و الوسيط الثالث عبارة عن البريد الالكتروني. بطبيعة الحال, من غير المنطقي أن نضع الحرف العشوائي ضمن وسائط الدالة لأن قيمته تعتمد على توليد عشوائي.

في البداية, أسندنا قيمة الوسيط L إلى المتغير login ثم قمنا باختيار حرف عشوائي من المصفوفة aplphabet و أسندناه إلى المتغير randomCharacter. بعد ذلك, استخدمنا الدالة strcpy لنسخ محتوى الوسيط em داخل المصفوفة email ثم جعلنا المؤشر الحالي يُشير إلى أول عُقدة في القائمة ثم قمنا بتحديث القائمة من خلال جعل العُقدة الجديدة هي الأولى. نأتي الآن إلى تضمين المكتبات اللازمة بالإضافة إلى تعليق موجز حول الــ main :

تنويه:
قمتُ بتقسيم الكود الكامل إلى مجموعة فقرات للتوضيح, فمثلا لم أقم بتضمين المكتبات التي قمتُ بتضمينها سابقا للاختصار, لذا تجد أن كل جزء من الكود يكون مُرتبطاً بالجزء السابق.

في البداية, قمنا بتضمين المكتبة time.h لوجود كلا من rand و srand. ثم قمنا بالإعلان عن بريد الكتروني باسم mail و استدعينا دالة الإضافة ثم تحققنا من القيمة الـمُعادة كما فعلنا سابقا, إذا تمت إعادة false نُظهر رسالة الخطأ و إلا فسنستدعي الدالة display المسئولة عن إظهار بيانات الـمُوظفين (سنشرح هذه الدالة لاحقاً).
مُخرجات الكود ستكون على هذا النحو:

لاحظ أنه تم إدراج العُقدة الجديدة قبل الُعقدة الأولى و هذا ما يُسمى بالإضافة في بداية القائمة, يُمكننا أيضا أن نُضيف العُقدة في نهاية القائمة أو في أي مكان آخر و هنا تكمن أحد أبرز نقاط القوة لدى القوائم و هي المرونة. الصورة التالية تُوضح مفهوم الإضافة في بداية القائمة:

بالنسبة لإضافة العُقدة في نهاية القائمة فستكون هكذا:

لا شيء جديد, سوى إضافة الحلقة while من أجل المرور على كافة العقد وصولا إلى العقدة الأخيرة ثم ربط العقدة الجديدة بنهاية القائمة. بشكل عام, الخطوات الـمُتبعة عند إضافة عُقدة في نهاية القائمة تكون كالآتي:

• حجز مساحة من الذاكرة للعقدة الجديدة.
• تهيئة كافة عناصر العقدة بما في ذلك المؤشر.
• الانتقال إلى آخر عُقدة من القائمة.
• ربط آخر عُقدة بالعقدة الجديدة.

يُمكننا أيضا إضافة عقدة جديدة في أي مكان من القائمة, لنفترض مثلا أننا نريد إدراج مُوظف جديد بعد موظف آخر يتم تحديد رقمه. في هذه الحالة ستكون الخُطوات الـمُتبعة هي:

• البحث عن العُقدة الـمُرافقة لرقم الموظف, توجد حالتان:حجز مساحة من الذاكرة للعقدة الجديدة.
  • إذا وصلنا إلى NULL فهذا يعني أن رقم الموظف غير موجود, حينها نقوم بإعادة false.
  • إذا وصلنا إلى العُقدة المطلوبة نقوم بالآتي:
• تهيئة كافة عناصر العقدة بما في ذلك المؤشر.
• تخزين عنوان العقدة الموالية في متغير مؤقت.
• جعل العُقدة الحالية تُشير إلى العُقدة الجديدة.
• ربط عنوان العُقدة الجديدة بالمتغير المؤقت.

و بالتالي دالة الإضافة ستكون هكذا:

إذا لم تنجح عملية الحجز أو لم يتم العثور على رقم الموظف ستُعيد الدالة false و إلا فستعيد الدالة true بعد أن تتم إضافة العُقدة الجديدة و تحديث القائمة. الآن أصبح من السهل جداً كتابة دالة تقوم بتعديل بيانات مُوظف مُعين, فقط بدلا من إدراج عُقدة جديدة, نقوم بتغيير بيانات العُقدة التي توقفت عندها الحلقة while ما لم تكن تلك العقدة فارغة.

نأتي الآن إلى شرح كيفية عمل دالة الإظهار التي تقوم بعرض محتويات قائمة الـمُوظفين:

الفكرة بسيطة جداً و هي كالتالي:
حتى لا نفقد بيانات الـمُوظفين نقوم بإنشاء نُسخة من القائمة الـمُرسلة كوسيط, ما دامت العُقدة الحالية غير فارغة نقوم بالتقدم خطوة إلى الأمام بعد أن نُظهر كافة بيانات العُقدة. فقط هذا كل شيء.
يُمكننا حساب طول القائمة بنفس الفكرة, فقط بدلا من إظهار البيانات نقوم بزيادة العداد ثم نُعيد قيمة العداد عند الوصول إلى آخر عُقدة. توجد أيضا طريقة أخرى لإظهار محتوى القائمة باستخدام التراجع, سنشرحها لاحقاً.

حذف عقدة مُعينة

كما فعلنا سابقا مع عملية الإضافة, يمكننا أيضا حذف عُقدة من البداية, النهاية أو أي مكان آخر من القائمة.
فمثلا, الدالة التالية تقوم بحذف آخر عُقدة من القائمة :

الخُطوات الـمُتبعة هي:

• إنشاء نُسخة من القائمة حتى لا نفقد بيانات الموظفين.
• الانتقال إلى العُقدة القبل الأخيرة (نتقدم بخطوة واحدة إذا كانت العقدة الموالية للعقدة الموالية غير فارغة).
• تخزين عنوان العقدة الأخيرة في متغير مؤقت وجعل العُقدة القبل الأخيرة تُشير إلى NULL.
• تحرير العنوان الذي كان يُشير إلى العُقدة الأخيرة.

أما إذا أردنا حذف عقدة من بداية القائمة فستكون الخطوات كما يلي:

• تخزين عنوان العقدة الأولى داخل متغير مؤقت.
• جعل مؤشر القائمة يُشير إلى العقدة الثانية.
• تحرير المؤشر الذي يُشير إلى العقدة الأولى.

و بالتالي دالة الحذف في هذه الحالة ستكون هكذا:

لاحظ أنه تم التأكد أن القائمة غير فارغة قبل إجراء عملية الحذف و هذا مُهم جدا إذْ يجب التأكد من مثل هذه الحالات قبل القدوم على تنفيذ العملية. لم أتحقق من أشياء كهذه في الدوال السابقة نظراً لأنني افترضتُ أن استدعاء الدوال يجب أن يكون بشكل تتابعي, في هذه الحالة لن نحصل على أي خطأ. أيضاً لم أُرد إرباك القارئ من خلال مُعالجة عدة أخطاء في نفس الوقت.

نأتي الآن إلى كيفية حذف عُقدة عن طريقة تحديد رقم الـمُوظف:

إذا كان رقم المُوظف موجود في العُقدة الأولى نقوم باستدعاء الدالة removeTheFirst لأن الانتقال في while يكون بمقدار خطوتين إلى الأمام و بالتالي سيتم تجاوز العُقدة الأولى, هذا من جهة. من جهة أخرى, عند الخروج من while سنكون أمام خيارين, الخيار الأول هو عدم وجود رقم الـمُوظف حينها سنقوم بإعادة false و تنتهي المهمة, إذا تجاوزنا الــ if بسلام فهذا يعني أن رقم الـمُوظف موجود داخل القائمة, لذا سنقوم بتخزين العقدة التي يوجد فيها الرقم في المتغير delNode ثم نُحرر عنوان تلك العُقدة بعد أن نتقدم خطوة واحدة إلى الأمام.

حساب طول القائمة
الفكرة بسيطة جداً وهي كالآتي:
إذا وصلنا إلى العقدة الأخيرة نقوم بإعادة الصفر و إلا فهذا يعني أنه توجد عقدة أخرى (و هي العُقدة الحالية) بالإضافة إلى الُعقد الموجودة في بقية القائمة (إن وُجدت). و بالتالي دالة حساب الطول ستكون هكذا:

قبل أن ننتقل إلى الفقرة المُوالية, ستقوم بكتابة الدالة التي من خلالها نستطيع معرفة فوز أو خسارة مُوظف مُعين:

ينجح الـمُوظف إذا تساوى أول حرف من بريده الالكتروني مع الحرف العشوائي الخاص به و يخسر في الحالة الـمُعاكسة.

دمج قائمتين في قائمة واحدة
دالة الدمج تستقبل وسيطين يُمثلان القائمتين الـمُراد دمجهما :

إذا كانت القائمة الأولى فارغة, فهذا يعني أن دمج القائمتين يُعطي القائمة الثانية لذا تمت إعادتها. في الحالة الـمُعاكسة نقوم بالانتقال إلى آخر عُقدة من القائمة الأولى ثم نربطها بأول عُقدة من القائمة الثانية.

حذف القائمة
دالة الحذف فكرتها كالآتي : ما دامت القائمة غير فارغة, نقوم بحذف العقدة الأولى. فقط !

اختبر قدراتك

قررت الشركة كتابة برنامج صغير يُساعدها في تسيير الـمُوظفين على مرحلتين:

• ترتيب الـمُوظفين تصاعدياً حسب أرقام الدخول.
• تقسيم قائمة الـمُوظفين إلى قائمتين, الأولى تحتوي على كافة الـمُوظفين الذين فازوا في المسابقة و القائمة الثانية تحتوي على بقية الـمُوظفين.

قم بكتابة دالة خاصة بكل مرحلة ثم قم باختبار الدوال في برنامج رئيسي موجود في ملف مستقل.

إلى هنا أصل بك أخي القارئ إلى نهاية هذا الدرس, آمل أن تكون استفدت من هذا الدرس و تعلمتَ أشياء جديدة.
تحياتي.

[divider] _{(1) Proceedings of the Western Joint Computer Conference en 1957 et 1958 et Information Processing en 1959 (première réunion de l’International Conference on Information Processing de l’UNESCO)
(2) Programming the Logic Theory Machine de Allen Newell et Cliff Shaw, Proceedings of the 1957 Western Joint Computer Conference, février 1957.}