بسم الله الرحمن الرحيم
الدرس الثاني من القوائم المترابطة Linked List :
فيما سبق تحدثنا من خلال الدرس الأول عن ماهية القوائم المترابطة , وكيفية انشاء اول عقدة في القائمة ,
وقلنا بأن هناك مجموعه كبيرة من العمليات التي يمكن تنفيذها على القوائم المترابطة على حسب رغبة المبرمج , وذكرنا بان العمليات الاساسية هي :
الاضافة - التعديل - الحذف - عرض العناصر -البحث- التعداد .
ولقد تكلمنا عن اول العمليات ( الاضافة ) بالتفصيل من خلال الدرس الاول , راجع الـــدرس الأول
سوف نكمل حديثنا اليوم عن بقية العمليات من خلال هذا الدرس .
----------------------------------------------------------------------------------------------------------------------
2 - عرض العناصر :
تكمن فكرة عرض العناصر بالوصول إلى بداية القائمة , ومن ثم التقدم خطوة خطوة إلى الامام , مع طباعة الحقل الاول من كل عقدة ( حقل القيم او البيانات ) , تحدثنا في الدرس السابق عن آلية التقدم والسير عبر عقد اي قائمة , ولكن كنا نستخدم طريقة التقدم إلى الامام وهي ماسنركز حديثنا عليه , لكن يا ترى , هل يوجد طريقة للتقدم إلى الخلف ؟ ؟
طبعا يوجد ولكن ليست محور حديثنا .
سنقوم الان بأنشاء دالة عرض العناصر Display والتي تأخذ الوسيط q , يبدأ عمل هذه الدالة بتعريف متغير اخر من نوع node_ptr نسميه p ونساويه بقيمه q وذلك لسلامة القائمة .
void Display(node_ptr&q)
{
node_ptr p;
p=q;
while(p!=NULL)
{
cout<<p->name<<":"<<p->num<<endl;
p=p->next;
}
}1- نساوي المتغير p بالمتغير q وذلك كما قلنا لسلامة القائمة .
2- ننشأ حلقة تكرار شرطها اننا لم نصل إلى نهاية القائمة NULL وذلك لأن المساواة جعلتنا في بداية القائمة كما هو مبين بالصورة السابقة .
3- نطبع القيم المراد طباعتها بالتنسيق الذي نريده .
4- ننتقل إلى العقدة التاليه .
3- التعداد :
ولها نفس الالية السابقة , ننتقل إلى بداية القائمة ومن ثم نتقدم خطوة للامام , ونحسب كل انتقال نجريه على العقد , وهكذا حتى نصل إلى نهاية القائمة .
int Count(node_ptr&q)
{
node_ptr p;
p=q;
int count=0;
while(p!=NULL)
{
count++;
p=p->next;
}
return count;
}
هذه الدالة Count تعيد قيمة من النوع int تمثل عدد العقد الموجودة ,لا اعتقد ان هذه الداله تحتاج لشرح طويل , فهي تقوم على الوصول إلى بداية القائمة ومن ثم زيادة قيمة count بواحد , ومن ثم الانتقال إلى العقدة التاليه حتى نصل إلى نهاية القائمة اي NULL .
3- الحذف :
وهو على ثلاثة انواع :
1- الحذف من اليسار ( من البداية ) .
2- الحذف من اليمين (من النهاية ) .
3- الحذف من الوسط .
هناك من يضيف تصنيف رابع على افتراض انه حذف القائمة بأكملها , ولكن تكمن هذه الفكرة باستخدام حلقة من التكرارات للحذف باستخدام الطريقة الاولى او الثانية .
1-الحذف من اليسار :
لحذف عقدة باستخدام هذه الطريقة نتبع الخطوات التاليه :
1- نجعل العقدة التاليه للعقدة الاولى هي بداية القائمة .
2- تكون العقدة الاولى حرة , عندها نقوم بحذفها .
3- تصبح القائمة الجديدة هي القائمة المعتمدة عن طريق المساواة مع القائمة القديمة.
لنأخذ هذه الدالة :
void DelFirst(node_ptr&q)
{
node_ptr d;
if(q->next!=NULL)
{
d=q->next;
d->next=q->next->next;
delete q;
q=d;
}
else
delete q;
}تحتوي هذه الدالة على الوسيط q والذي يمثل لنا القائمة , يجري بعد ذلك اختبار لحقل التأشير لنرى ما اذا كانت القائمة تحتوي على عقدة واحدة او اكثر من عقدة , راجع الدرس الأول .
على فرض ان لدينا قائمة تحتوي على ثلاثة عقد ونرغب بحذف عقدة من اليسار وباتباع الخطوات السابقة نقول :
نمثل القائمة الجديدة من خلال المتغير d والذي يبدأ من اول عقدة بعد العقدة الاولى (الخطوة الأولى ) , وذلك بواسطة حقل التأشير للعقدة الاولى :
ايضا نعدل حقل التأشير للقائمة الجديدة d ونجعله يؤشر لثاني عقدة بعد العقدة الاولى :
الان لدينا القائمة الجديدة , والتي سنساويها بعد قليل بالقائمة القديمة ( الخطوة الثالثة ) ولكن قبل ذلك لابد من تنفيذ الحذف للعقدة الحرة ( الخطوة الثانية ) :
2- الحذف من اليمين :
بهذه الطريقة , نقوم بالتنقل عبر العقد إلى ان نصل إلى العقدة التي قبل العقدة الاخيرة , لجعلها العقدة الاخيرة اولا , ومن ثم حذف العقدة الاخيرة , نلخص ذلك بما يلي :
1- تحديد العقدة التي تسبق العقدة الاخيرة .
2- جعلها تؤشر إلى NULL اي ان نجعلها العقدة الاخيرة ( راجع الدرس الأول ) .
3- حذف العقدة الاخيرة .
void DelLast(node_ptr&q)
{
node_ptr p,d;
p=q;
while(p->next->next!=NULL)
{
p=p->next;
}
d=p->next;
p->next=NULL;
delete d;
}هذه الدالة تحتوي على حلقة تكرار شرطها ان يستمر تنفيذ التكرار بالحلقة حتى نصل إلى الحلقة التي تسبق الحلقة الاخيرة ,
يمثل لنا المتغير d العقدة الاخيرة والتي نرغب بحذفها , نعدل تأشير العقدة الاخيرة الجديدة إلى NULL لنعلن بذلك انها نهاية القائمة, ( الخطوة الثانية ) ومن ثم نحذف العقدة الاخيرة القديمة ( الخطوة الثالثة ) .
3- الحذف من الوسط :
في هذه الطريقة نبحث عن العقدة المراد حذفها , مثلا نبحث بواسطة القيمة num عندها نستطيع ان نقول على سبيل المثال احذف العقدة لصاحب الرقم 50 , ......
في هذه الطريقة نتبع مايلي :
1- نحدد العقدة المراد حذفها .
2- نجعل العقدة السابقة لها تؤشر للعقدة التاليه لها .
3 - نحذف العقدة الحرة.
void DelMid(node_ptr&q,int m)
{
node_ptr p,d;
p=q;
while(p->next->num!=m &&p->next->next!=NULL)
{
p=p->next;
}
d=p->next;
p->next=d->next;
delete d;
}نستمر بالتقدم عبر العقد إلى ان نصل إلى العقدة التي تسبق العقدة المراد حذفها وذلك من خلال التقدم مالم نصل إلى قيمة البحث m او إلى نهاية القائمة NULL
يمثل لنا d العقدة المراد حذفها وذلك من خلال مساواته مع العقدةالتي يؤشر لها حقل التأشير لـ p
نجعل العقدة السابقة p للعقدة المراد حذفها تؤشر للعقدة التاليه للعقدة المراد حذفها d->next
بعد ذلك نقوم بحذف d
----------------------------------------------------------------------------------------------------------------------
4- التعديل :
فكرة التعديل مشابهه لبعض الافكار التي وردت معنا في هذا الدرس او الدرس الاول , والتي تقوم على البحث عن عقدة ما بموجب قيمة , وتعديل قيمة اخرى بالعقدة ,
على سبيل المثال : البحث عن العقدة لصاحب الرقم 50 وتعديل اسمه من Ali إلى Naser
void edit (node_ptr &first,int s,char name[10])
{
node_ptr p;
p=first;
while(p->num!=s && p->next!=NULL)
p=p->next;
if(p->next!=NULL)
strcpy(p->name,name);
}يتم التنقل عبر عناصر القائمة بشرط مالم نصل إلى نهاية القائمة او إلى القيمة المراد البحث عنها ,
عند العثور على القيمة نقوم بتعديل الاسم القديم إلى الاسم الجديد .
من العمليات ايضا البحث وهي نفس الفكرة بالاستغناء عن التعديل بأي غرض نرغب البحث من اجله .
----------------------------------------------------------------------------------------------------------------------
إلى هنا اكون قد انتهيت من درسي الثاني ,
قمت بعرض فكرة عن القوائم المتصلة وبعض العمليات التي تجري عليها ,
جميع ماذكر هي عبارة عن افكار مع عدم مراجعة الاخطاء او انشاء استثنائات لتوقع اخطاء معينة , فهذه قد تركتها للقارئ ليجربها بنفسه
مثلا : دالة الحذف من البداية , ربما تستمري اذا كانت هناك قائمة ولكن ماذا لو لم تكن ؟
يوجد بعض الامور التي تستوجب من القارء مراعاتها وتعتمد على مهارة المبرمج ,
في المرة القادمة سيكون هناك مثال شامل على العمليات ومنقح من الاخطاء , لكن لن يكون الدرس القادم , لان درسي القادم هو طرق الـ Exception Handling
B)
تحياتي
