Linked List
القوائم المتصلة :
هي نوع من هياكل البيانات وتتألف من مجموعة من الخلايا المترابطة بينها وكل عنصر فيها يسمى عقدة وهذه العقدة فيها حقلين , الحقل الأول يستخدم لتسجيل القيم , اما الحقل الثاني فهو مؤشر يؤشر لعنوان العقدة التالية او السابقة او NULL في حال كانت هذه الحلقة هي الحلقة الاخيرة .
* يجب التنويه بأنه لا يشترط او ليس من الضروري ان تكون العقد مرتبة بشكل متتالي في الذاكرة , فهي تكون مبعثرة في الذاكرة , والسبب في ذلك :
ان من يقوم بعملية الحجز في الذاكرة هو جهاز الحاسب وليس المستخدم , لكنها متصلة في ما بينها عن طريق المؤشرات كما يظهر بالشكل :
انشاء تركيبة القائمة المتصلة :
كما قلنا بان القائمة المتصلة هي عبارة عن سلسلة من الحلقات وتسمى كل حلقة عقدة ( node) اذا سنقوم الان ببناء تركيبة لتمثل هذه العقد , وقلنا بان كل node تحتوي على قسمين , قسم البيانات , وقسم هو عبارة عن مؤشر لحلقة اخرى او لـ null , الان سنأخذ مثال على تركيبة بيانات تمثل لنا العقدة التي نرغب بتصميمها , وهي عبارة عن عقدة تحتوي على قسم البيانات : اسم الطالب , ورقم الطالب , قسم المؤشر .
struct node{
int num;
char name[10];
node * next;
};
typedef node *node_ptr;فيما سبق قمنا بتعريف بنية Struct اسمها node تحتوي على ثلاثة متغيرات , الاول هو متغير num لتخزين ارقام الطلاب , والمتغير الثاني هو name لتخزين اسماء الطلاب , والمتغير الثالث next وهو مؤشر من نوع التركيبة نفسها node وسنستخدمه للتأشير على العقد الاخرى .
بعد التركيبه قمنا باستخدام الامر typedef بتعريف نوع بيانات من نوع اخر وهو node_ptr من *node ,
شرح اكثر حول typedef :
الامر typedef يقوم يتعريف نوع من نوع اخر وفقا للصيغة :
typedef النوع المغير له النوع الاصلي;
مثلا :
typedef int INT;
عندها نستطيع ان نقول :
INT a;
حتى الان كل ماقمنا به هو انشاء التركيبه التي تمثل لنا العقدة وسنرى بالفقره القادمة ماهي العمليات التي نستطيع ان نجريها على القائمة المتصلة :
التصريح عن القائمة في الدالة الرئيسية main :
node_ptr q=NULL;
تم الان التصريح عن القائمة q والتي تشير إلى NULL لانه لايوجد بها حتى الان اي عقدة .
العمليات على القائمة :
هناك العديد من العمليات التي يمكن ان تتم على القائمة مثل :
- الاضافة - التعديل - الحذف - عرض العناصر -البحث- التعداد .
نبدا اولا بالاضافة .
الاضافة ولها اربعة طرق :
1-اضافة اول حلقة .
2- الاضافة من اليمين ( النهاية )
3- الاضافة من اليسار ( البداية )
4- الاضافة من الوسط .
اولا : اضافة اول عقدة :
الان , لايوجد لدينا قائمة , وننوي انشاء قائمة عن طريق انشاء اول عقدة بهذه القائمة , ونتذكر باننا انشئنا تركيبة لكل حلقة ( في مثالنا السابق كل عقدة تحتوي على : البيانات ( اسم الطالب ورقم الطالب ) والمؤشر ) .
دعونا ننظر إلى هذه الدالة :
void firstNode(node_ptr &first,int n,char name[10])
{
if(first==NULL)
{
first=( node* )malloc(sizeof(node));
first->num=n;
strcpy(first->name,name);
first->next=NULL;
}
else
{
cout<<"Error:";
}
}هذه الدالة وظيفتها اضافة اول عقدة للقائمة وهذا يعني انه لايوجد حتى الان قائمة , اي ان q يشير إلى NULL , دعونا ننتقل للشرح لتوضيح ماهو مبهم :
الشرح :
تأخذ الدالة الوسائط (Prameters) التاليه :
first & : ويمثل لنا عنوان القائمة .
n : لتخزين درجة الطالب.
name: اسم الطالب .
بعد ذلك تم اختبار فيما اذا كانت first هل تساوي null ام لا ؟ , بمعنى اخر , اختبار ما ااذا كانت القائمة تحتوي على حلقات ام انها فارغه , الوسيط first سيقابل عند اسناد القيم المتغير q اي عنوان القائمة, ونتذكر باننا عند التصريح عن القائمة قمنا بأسناد العنوان NULL إلى المتغير q
اذا تحقق الشرط ننشأ العقدة ماعدا ذلك نظهر رسالة Error وذلك لان القائمة تحتوي على عقدة اصلا .
بعد ذلك نقوم باستخدام الدالة malloc بحجز موقع بحجم التركيبه node داخل الذاكرة وارجاع العنوان إلى first
الان لدينا داخل العنوان first ثلاثة عناصر :
num ونساويها بـالوسيط n
name ونساويها بالوسيط name
next وهو المؤشر الذي يؤشر للحلقة التاليه ونساويه بـ NULL
2- الاضافة إلى نهاية القائمة :
انتهينا من النقطة رقم 1 ولدينا الان حلقة ومؤشرها يؤشر إلى NULL كما هو بالصورة :
خطوات اضافة حلقة من النهاية :
1- ننشأ حلقة جديدة ونجعلها تؤشر إلى NULL
2 - نجعل العقدة الاولى بدلا من ان تأشر إلى NULL تأشر إلى العقدة الجديدة :
دعونا نرى هذا الكود :
void append (node_ptr &first,int n,char name[10])
{
node_ptr p,q;
p=first;
while(p->next!=NULL)
{
p=p->next;
}
q=(node *)malloc(sizeof(node));
q->num=n;
strcpy(q->name,name);
q->next=NULL;
p->next =q;
}الشرح:
1- انشأنا متغيرين q ,p من النوع node_ptr ليمثل المتغير q الحلقة الجديدة , اما المتغير p للتنقل عبر حلقات القائمة.
2-جعلنا p يساوي عنوان first اي عنوان القائمة .
3-حلقة تكرار للتنقل عبر العقد القائمة, تستمر حلقة التكرار طالما ان العقدة لاتؤشر إلى NULL :
تحتاج هذه المسألة شيئا من التفصيل ,
ان طريقة التنقل عبر العقد داخل الحلقة تستخدم هذه الطريقة , فمثلا للوصول إلى نهاية الحلقة نكتب شرط التكرار هو ان يستمر التقدم حتى نصل إلى العقدة التي تؤشر إلى NULL مثلا:
p=first;
while(p->next!=NULL)
{
p=p->next;
}لنفترض وجود قائمة تحتوي على 3 عقد ونريد الوصول إلى اخر عقدة , اذا عندها سنمشي على القائمة حتى نصل إلى العقدة التي تؤشر إلى NULL , الان لنفترض فعلا وجود هذه القائمة كما هو موضح في الصورة
سنقول اولا : p=first
first هو عنوان القائمة اي عنوان اول عقدة في القائمة , والان اصبح المتغير p يحمل هذا العنوان .
الان نقول :
while(p->next!=NULL)
{
p=p->next;
}كرر طالما ان next لا يساوي NULL , سنطبق هذا المثال على القائمة التي افترضناها :
الان عندما نقول :
p=p->next
هذا يعني ان p قد تقدم خطوة إلى الامام واصبح الان بالعقدة التاليه .
هل p->next لاتساوي NULL ؟
نعم لاتساوي NULL لانها تساوي عنوان العقدة 3 اي انها تؤشر للعقدة 3
p=p->next
هل p->next لاتساوي NULL ؟
لا , انها تساوي NULL اذا انتهت حلقة التكرار واصبحنا الان بالعقدة الاخيرة .
q=(node *)malloc(sizeof(node)); q->num=n; strcpy(q->name,name); q->next=NULL;
اما q فأصبح يؤشر إلى عقدة جديدة من خلال الكود السابق .
p->next =q
الان اصبحت العقدة الاخيرة بدلا من ان تؤشر إلى NULL تؤشر إلى عنوان العقدة الجديدة .
3- الاضافة من البداية :
هنا الوضع مختلف قليلا , واسهل بكثير , وتقوم الفكرة على انشاء عقدة جديدة , ونجعلها تؤشر إلى اول عقدة من القائمة , ثم نجعل عنوان القائمة هو العقدة الجديدة :
void appfirst(node_ptr & first,int n ,char * name)
{
node_ptr temp,q;
q=first;
temp=(node*) malloc(sizeof(node));
temp->num=n;
strcpy(temp->name,name);
temp->next=q;
first=temp;
}قمنا بالتصريح عن temp,q والتي من خلالها نمثل العقدة الجديدة temp و q الذي يمثل لنا عنوان القائمة .
1- q يساوي first اي عنوان اول عقدة بالقائمة اي عنوان بداية القائمة نفسها
2- temp يقوم بانشاء عقدة جديدة ويجعلها تؤشر لاول عقدة بالقائمة اي q
4- الاضافة من الوسط :
تكمن الفكرة بأن نعثر عن قيمة تدل على العقدة التي نريد ان نضيف بعدها , مثل ان نبحث عن العقدة التي بها رقم الطالب 50 ونضيف بينها وبين العقدة التي تليها عقدة جديدة ولاتمام ذلك نقول :
1- لدينا قائمة من العقد , نبحث عن العقدة التي نريد ان نضيف بعدها .
2- ننشأ عقدة جديدة ونجعلها تؤشر إلى العقدة التي تلي العقدة المقصودة.
3- نجعل العقدة المقصودة تؤشر إلى العقدة الجديدة .
الان دعونا نرى هذه الدالة :
void appMid (node_ptr &first,int m,int n,char name[10])
{
node_ptr p,q;
p=first;
while(p->num!=m && p->next!=NULL)
{
p=p->next;
}
q=(node *)malloc(sizeof(node));
q->num=n;
strcpy(q->name,name);
q->next=p->next;
p->next =q;
}1- p يساوي بداية القائمة .
2- ندخل في حلقة تكرار وشرطها طالما ان num لايساوي القيمة المراد البحث عنهاm و لم نصل إلى نهاية القائمة.
3 - ننشأ العقدة الجديدة q ونجعلها تؤشر إلى العقدة التاليه من العقدة المقصودة.
4-نجعل العقدة المقصودة تؤشر إلى العقدة الجديدة .
إلى هنا اكون قد انتهيت من درسي الاول والذي هو جزء من بحث قدمته عن تراكيب البيانات :
ولي عودة لتكملة الدرس على باقي العمليات مع شرح الامثلة وذكر مثال شامل معالج من الاخطاء المنطقية .
