القوائم المترابطة في ++C

القوائم المترابطة

ما هي القائمة المترابطة (تسمي اختصارا "قائمة" , وبهذا الاسم تعرض في الفصل 17 Linked Lists لقد مر بنا استخدام المصفوفات لتجميع البيانات في مجموعات ويعيب هذا الأسلوب بديل أكثر مرونة من حيث عدم تطلبه هذا الشرط فبإمكانك إدخال البيانات وتتسع القائمة طبقا لاحتياجك ويتولي المؤثر new إمدادك بالمساحة المطلوبة . وتتميز عناصر القائمة المترابطة بأن كل عنصر يحتوي علي مؤشر يحمل عنوان العنصر التالي له , ولهذه الخصيصة ميزة غاية في الأهمية إذ تحرر النظام من أن شرط تخزين العناصر متجاورة ] كما في المصفوفات [ بل يمكن للعناصر أن توضع مبعثرة في الذاكرة , طالما أن كل عنصر يدل علي موضع العنصر التالي له .

سلسلة المؤشرات

في مثالنا التالي تكون القائمة برمتها كائن Li ينتمي إلي الفئة Link وكل عنصر من عناصر القائمة من نوع الهيكل يحتوي علي عنصرين متغير عدد صحيح لتخزين البيان ومؤشرا أعطي الاسم next يحمل عنوان العنصر التالي له . والقائمة نفسها تتضمن مؤشرا يحمل عنوان العنصر الأول وهو المؤشر first ويتميز أخر عنصر بأن مؤشر next به يحتوي علي الرمز ''NULL'' أنظر الشكل

شكل قائمة مترابطة

وإليك صياغة البرنامج :

linklist.cpp

// linklist.cpp

// linked list

// UCS Laboratories

#include <iostream.h>

#include <conio.h>

struct link                           // one element of list

   {

   int data;                          // data item

   link* next;                        // pointer to next link

   };

class linklist                        // a list of links

   {

   private:

      link* first;                    // pointer to first link

   public:

      linklist()                      // no-argument constructor

     { first = NULL; }            // no first link

      void additem(int d);            // add data item (one link)

      void display();                 // display all links

   };

void linklist::additem(int d)         // add data item

   {

   link* newlink = new link;          // make a new link

   newlink->data = d;                 // give it data

   newlink->next = first;             // it points to next link

   first = newlink;                   // now first points to this

   }

void linklist::display()              // display all links

   {

   link* current = first;             // set ptr to first link

   while( current != NULL )           // quit on last link

      {

      cout << endl << current->data;  // print data

      current = current->next;        // move to next link

      }

   }

void main()

   {

   linklist li;       // make linked list

   li.additem(25);    // add four items to list

   li.additem(36);

   li.additem(49);

   li.additem(64);

   li.display();      // display entire list

   getche();

   }

الفئة Linklist لها عنصر بيانات واحد هو المؤشر first وهو يستهل في بدء البرنامج بالقيمة NULL وهذا الثابت معرف في ملف mem.h (الموجود في الملف ostream.h ) علي أن قيمته = 0 .

إضافة عنصر للقائمة

تقوم الدالة additem() بإضافة عنصر جديد للقائمة فهي تنشئ كائنا يشار إليه بالمؤشر newlink وذلك بالأمر :

Link* newlink = new Link

ثم تدخل البيان المطلوب بهذا الكائن بالأمر :

Newlink->=d;

حيث يعوض عن الحرف d بالقيمة المخلة في المعامل بعد ذلك تقوم الدالة بنقل محتوي المؤشر first (القيمة NULL ) إلي المؤشر next الخاص بالعنصر الأول , ليكون هو أيضا العنصر الأخير للقائمة (يمكنك تصميم قائمة يظل العنصر المدخل أولا هو أول عنصر في القائمة ولكن الأمر سيكون أكثر تعقيدا ) بالأمر :

Newlink->next=first;

ثم ينقل عنوان العنصر للمؤشر first (طالما أنه لم يزل العنصر الأول في القائمة ) بالأمر :

First = newlink;

] إدخال العنصر التالي ينقل محتوي المؤشر first إلي المؤشر next الخاص به , فيحتوي علي عنوان العنصر السابق , ثم ينقل عنوان العنصر الجديد إلي المؤشر first [ .

إظهار عناصر القائمة

تتولي الدالة display() إظهار عناصر المصفوفة , والقيام بذلك تنشئ مؤشرا curren لتضع فيه عنوان العنصر المطلوب إظهاره وتضع فيه محتوي المؤشر first أولا , بالأمر :

Link * current = first;

ثم تبدأ الدوارة في العمل فيدخل في هذا المؤشر محتوي المؤشر next بالترتيب عنصرا يعد الأخر بالأمر :

Current = current-> next;

لإمكان إظهار العنصر التالي , إلي أن نصل إلي قيمة next=NULL .

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

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

خطأ محتمل

لاحظنا أننا قد عرفنا مؤشرا يشير لنفس نوع الهيكل Link ويمكن أيضا في تعريف فئة أن نضمن بياناتها مؤشر يشير لكائناتها كأمر من هذا القبيل :

Class sample

{

Sample* ptr;

}

ولكن لا يمكن أن تعرف بيانا في هيكل ينتمي له ولا كائنا في فئة ينتمي إليها فالأمر التالي غير مقبول :

Class sample

{

Sample obj;

}