الDouble Sorted Linked-List أو DSLL هو بناء تتم الإضافة إليه بالترتيب سواء أكان ذلك تصاعدياً أم تنازلياً وذلك بالإعتماد على قيم العناصر المراد اضافتها.
يحتاج هذا البناء إلى مؤشر واحد لكي يشير الى العنصر ذو أكبر قيمة في حال كان الترتيب تنازلياً أو يشير الى العنصر ذو أقل قيمة في حال كان الترتيب تصاعدياً وعادةً يسمى هذا المؤشر head ,, ونحتاج أيضاً الى متغير واحد يُعبر عن عدد العناصر الموجودة في الDSLL وعادةً يسمى هذا المُتغير length.
تتميز العناصر في الDSLL بأن لكل عنصر مؤشرين وهما الnext والback ,, ويمتلك العنصر أيضاً متغيراً واحداً يعبر عن القيمة المخزنة في العنصر وعادةً يسمى data.
لتوضيح عملية الإضافة والحذف إلى الDSLL .. تأمل الكود التالي والذي يحتوي على الmain الخاص بclass لتمثيل بناء الDSLL ,, التعليمات المكتوبة في الmain تعمل على إنشاء object من الDSLL بإسم test بحيث تتم اضافة خمس عناصر 2, 5, 1, 4, 3 ليتم ترتيبها تصاعدياً ثم تقوم بطباعة جميع الأعداد ومن ثم تحذف العناصر ذات القيم 3, 5, 1 من الtest ثم تطبع الأعداد الموجودة مرة اخرى ...
بعد تنفيذ التعليمات المكتوبة داخل الmain فإن ناتج البرنامج أعلاه سيكون كالتالي ...
لمعرفة كيفية ظهور الناتج ,, تتبع تسلسل تنفيذ التعليمات ...
**************************************************
DSLL test <Int> = new DSLL (); //to declare an object test of class DSLL
عند انشاء الobject المسمى test فإن البرنامج يقوم باستدعاء الdefault constructor تلقائياً بحيث يعمل هذا الconstructor على تهيئة الDSLL عن طريق تخزين القيمة 0 في المتغير length وجعل المؤشر head يشير إلى NULL.
**************************************************
DSLL.insert(2); //to insert the element with value 2 into test
عند اضافة أول عنصر الى test وهو العنصر ذو قيمة 2 ,, نجعل الnext والback الخاصين بهذا العنصر يشيران إلى NULL newnode->next = newnode->back = NULL ونزيد قيمة المتغير length بمقدار 1 ,, ثم نجعل المؤشر head يشير الى العنصر الجديد بدلاً من الإشارة إلى NULL بحيث head = newnode.
**************************************************
DSLL.insert(5); //to insert the element with value 5 into test
عند إضافة ثاني عنصر الى test وهو العنصر ذو قيمة 5 ,, نجعل الnext الخاص بالعنصر الجديد يؤشر إلى NULL newnode-> next = NULL ونجعل الback الخاص بالعنصر الجديد يشير إلى العنصر الذي يؤشر إليه الhead بحيث newnode->back = temp وذلك لأن العنصر المضاف يحمل قيمة أكبر من قيمة العنصر الموجود ,, ثم نزيد قيمة المتغير length بمقدار 1 ونغير الnext الخاص بالعنصر الذي يؤشر عليه الhead بحيث يؤشر إلى العنصر الجديد بدلاً من الإشارة إلى NULL وذلك عن طريق head->next = newnode.
**************************************************
DSLL.insert(1); //to insert the element with value 1 into test
بما أن الtest الان يحتوي على عنصرين ولكي نضيف العنصر الجديد قبل العنصر الذي يعلوه في القيمة فإننا سنحتاج لتعريف مؤشر مؤقت يسمى temp بحيث يبحث عن العنصر ذو القيمة الأعلى من قيمة العنصر المراد إضافته وستتم عملية البحث عن طريق جملة for ,, سيبدأ temp البحث من العنصر الذي يشير اليه الhead بحيث temp = head وفي كل مرة سيقارن قيمة العنصر المراد اضافته مع قيمة العنصر الذي يشير إليه الtemp بحيث info >= temp->data فإذا كانت القيمة أكبر من القيمة الموجودة سيجعل الtemp يؤشر على العنصر الذي يليه temp = temp->next ,, سيستمر حتى يجد عنصر ذو قيمة اكبر من قيمة العنصر المراد اضافته.
في هذه الحالة فإن ال1 أقل من 2 ,, نجعل الnext الخاص بالعنصر المضاف يشير إلى العنصر الذي يؤشر إليه الhead بحيث newnode->next = head ونجعل الback الخاص بالعنصر المضاف يشير إلى NULL بحيث newnode->back = NULL ,, نزيد قيمة المتغير length بمقدار 1 ونغير الback الخاص بالعنصر الذي يشير إليه الhead بحيث يؤشر إلى العنصر الجديد head->back = newnode ,, اخيراً نغير الhead بحيث يشير إلى العنصر ذو أقل قيمة head = head->back .
**************************************************
DSLL.insert(4); //to insert the element with value 4 into test
لإضافة العنصر ذو قيمة 4 نقوم بنفس خطوات إضافة ال1 وذلك بإنشاء المؤشر المؤقت temp.
سيصل المؤشر temp إلى العنصر ذو القيمة 5 ,, نجعل الnext الخاص بالعنصر المضاف يشير إلى العنصر الذي يؤشر إليه الtemp بحيث newnode->next = temp ونجعل الback الخاص بالعنصر المضاف يشير إلى ما يشير إليه الback الخاص بالtemp بحيث newnode->back = temp->back وذلك للحفاظ على اتصال عناصر الtest ببعضها البعض ,, ونزيد قيمة المتغير length بمقدار 1 ,, ثم نجعل الnext الخاص بالعنصر الذي يسبق العنصر المضاف يؤشر ألى العنصر المضاف newnode->back->next = newnode ونجعل الback الخاص بالtemp يؤشر على العنصر الجديد temp->back = newnode.
**************************************************
DSLL.insert(3); //to insert the element with value 3 into test
لإضافة العنصر ذو قيمة 3 نقوم بنفس خطوات إضافة ال4 وذلك بإنشاء المؤشر المؤقت temp.
سيصل المؤشر temp إلى العنصر ذو القيمة 5 ,, نجعل الnext الخاص بالعنصر المضاف يشير إلى العنصر الذي يؤشر إليه الtemp بحيث newnode->next = temp ونجعل الback الخاص بالعنصر المضاف يشير إلى ما يشير إليه الback الخاص بالtemp بحيث newnode->back = temp->back وذلك للحفاظ على اتصال عناصر الtest ببعضها البعض ,, ونزيد قيمة المتغير length بمقدار 1 ,, ثم نجعل الnext الخاص بالعنصر الذي يسبق العنصر المضاف يؤشر ألى العنصر المضاف newnode->back->next = newnode ونجعل الback الخاص بالtemp يؤشر على العنصر الجديد temp->back = newnode.
**************************************************
DSLL.printAll(); //to print the values of all elements in test
لطباعة قيم جميع العناصر في الtest ننشىء مؤشر مؤقت بإسم temp ونجعله يشير إلى ما يشير إليه الhead بحيث temp = head ومن ثم ندخل الtemp الى جملة for بحيث تنتهي جملة الfor عندما يشير الtemp إلى NULL بحيث ان temp != NULL تعمل على استمرار الfor ,, في كل مرة يتم طباعة قيمة العنصر الذي يؤشر إليه الtemp بحيث cout << temp-> data ,, ومن ثم نقوم بتغيير الtemp ليؤشر إلى العنصر التالي عن طريق temp = temp-> next.
**************************************************
DSLL.delete(3); //to delete the element with value 3 from test
نقوم بعمل مؤشر مؤقت بإسم temp يؤشر على ما يؤشر عليه الhead بمعنى temp = head بحيث يقوم بالبحث عن العنصر المراد حذفه من خلال جملة for ينتهي تنفيذها عند إيجاد العنصر المطلوب info == temp->data وما لم يتم إيجاد العنصر المراد حذفه يتغير الtemp لكي يشير إلى العنصر التالي temp = temp->next.
عند إيجاد العنصر فإن أهم خطوة هي الحفاظ على ترابط عناصر الtest مع بعضها البعض ,, لذلك نجعل الnext الخاص بالعنصر الذي يسبق العنصر المراد حذفه يشير إلى العنصر الذي يلي العنصر المراد حذفه temp->back->next = temp->next ونجعل الback الخاص بالعنصر الذي يلي العنصر المراد حذفه يشير الى العنصر الذي يسبق العنصر المراد حذفه temp->next->back = temp->back ,, ثم نحذف العنصر delete temp ,, ننقص من قيمة المتغير length بمقدار 1.
**************************************************
DSLL.delete(5); //to delete the element with value 5 from test
**************************************************
DSLL.delete(1); //to delete the element with value 1 from test
**************************************************
DSLL.printAll(); //to print the values of all elements in test
لطباعة قيم جميع العناصر في الtest ننشىء مؤشر مؤقت بإسم temp ونجعله يشير إلى ما يشير إليه الhead بحيث temp = head ومن ثم ندخل الtemp الى جملة for بحيث تنتهي جملة الfor عندما يشير الtemp إلى NULL بحيث ان temp != NULL تعمل على استمرار الfor ,, في كل مرة يتم طباعة قيمة العنصر الذي يؤشر إليه الtemp بحيث cout << temp-> data ,, ومن ثم نقوم بتغيير الtemp ليؤشر إلى العنصر التالي عن طريق temp = temp-> next.
**************************************************
سامر المناصرة
لتوضيح عملية الإضافة والحذف إلى الDSLL .. تأمل الكود التالي والذي يحتوي على الmain الخاص بclass لتمثيل بناء الDSLL ,, التعليمات المكتوبة في الmain تعمل على إنشاء object من الDSLL بإسم test بحيث تتم اضافة خمس عناصر 2, 5, 1, 4, 3 ليتم ترتيبها تصاعدياً ثم تقوم بطباعة جميع الأعداد ومن ثم تحذف العناصر ذات القيم 3, 5, 1 من الtest ثم تطبع الأعداد الموجودة مرة اخرى ...
بعد تنفيذ التعليمات المكتوبة داخل الmain فإن ناتج البرنامج أعلاه سيكون كالتالي ...
لمعرفة كيفية ظهور الناتج ,, تتبع تسلسل تنفيذ التعليمات ...
**************************************************
DSLL test <Int> = new DSLL (); //to declare an object test of class DSLL
عند انشاء الobject المسمى test فإن البرنامج يقوم باستدعاء الdefault constructor تلقائياً بحيث يعمل هذا الconstructor على تهيئة الDSLL عن طريق تخزين القيمة 0 في المتغير length وجعل المؤشر head يشير إلى NULL.
**************************************************
DSLL.insert(2); //to insert the element with value 2 into test
عند اضافة أول عنصر الى test وهو العنصر ذو قيمة 2 ,, نجعل الnext والback الخاصين بهذا العنصر يشيران إلى NULL newnode->next = newnode->back = NULL ونزيد قيمة المتغير length بمقدار 1 ,, ثم نجعل المؤشر head يشير الى العنصر الجديد بدلاً من الإشارة إلى NULL بحيث head = newnode.
**************************************************
DSLL.insert(5); //to insert the element with value 5 into test
عند إضافة ثاني عنصر الى test وهو العنصر ذو قيمة 5 ,, نجعل الnext الخاص بالعنصر الجديد يؤشر إلى NULL newnode-> next = NULL ونجعل الback الخاص بالعنصر الجديد يشير إلى العنصر الذي يؤشر إليه الhead بحيث newnode->back = temp وذلك لأن العنصر المضاف يحمل قيمة أكبر من قيمة العنصر الموجود ,, ثم نزيد قيمة المتغير length بمقدار 1 ونغير الnext الخاص بالعنصر الذي يؤشر عليه الhead بحيث يؤشر إلى العنصر الجديد بدلاً من الإشارة إلى NULL وذلك عن طريق head->next = newnode.
**************************************************
DSLL.insert(1); //to insert the element with value 1 into test
بما أن الtest الان يحتوي على عنصرين ولكي نضيف العنصر الجديد قبل العنصر الذي يعلوه في القيمة فإننا سنحتاج لتعريف مؤشر مؤقت يسمى temp بحيث يبحث عن العنصر ذو القيمة الأعلى من قيمة العنصر المراد إضافته وستتم عملية البحث عن طريق جملة for ,, سيبدأ temp البحث من العنصر الذي يشير اليه الhead بحيث temp = head وفي كل مرة سيقارن قيمة العنصر المراد اضافته مع قيمة العنصر الذي يشير إليه الtemp بحيث info >= temp->data فإذا كانت القيمة أكبر من القيمة الموجودة سيجعل الtemp يؤشر على العنصر الذي يليه temp = temp->next ,, سيستمر حتى يجد عنصر ذو قيمة اكبر من قيمة العنصر المراد اضافته.
في هذه الحالة فإن ال1 أقل من 2 ,, نجعل الnext الخاص بالعنصر المضاف يشير إلى العنصر الذي يؤشر إليه الhead بحيث newnode->next = head ونجعل الback الخاص بالعنصر المضاف يشير إلى NULL بحيث newnode->back = NULL ,, نزيد قيمة المتغير length بمقدار 1 ونغير الback الخاص بالعنصر الذي يشير إليه الhead بحيث يؤشر إلى العنصر الجديد head->back = newnode ,, اخيراً نغير الhead بحيث يشير إلى العنصر ذو أقل قيمة head = head->back .
**************************************************
DSLL.insert(4); //to insert the element with value 4 into test
لإضافة العنصر ذو قيمة 4 نقوم بنفس خطوات إضافة ال1 وذلك بإنشاء المؤشر المؤقت temp.
سيصل المؤشر temp إلى العنصر ذو القيمة 5 ,, نجعل الnext الخاص بالعنصر المضاف يشير إلى العنصر الذي يؤشر إليه الtemp بحيث newnode->next = temp ونجعل الback الخاص بالعنصر المضاف يشير إلى ما يشير إليه الback الخاص بالtemp بحيث newnode->back = temp->back وذلك للحفاظ على اتصال عناصر الtest ببعضها البعض ,, ونزيد قيمة المتغير length بمقدار 1 ,, ثم نجعل الnext الخاص بالعنصر الذي يسبق العنصر المضاف يؤشر ألى العنصر المضاف newnode->back->next = newnode ونجعل الback الخاص بالtemp يؤشر على العنصر الجديد temp->back = newnode.
**************************************************
DSLL.insert(3); //to insert the element with value 3 into test
لإضافة العنصر ذو قيمة 3 نقوم بنفس خطوات إضافة ال4 وذلك بإنشاء المؤشر المؤقت temp.
سيصل المؤشر temp إلى العنصر ذو القيمة 5 ,, نجعل الnext الخاص بالعنصر المضاف يشير إلى العنصر الذي يؤشر إليه الtemp بحيث newnode->next = temp ونجعل الback الخاص بالعنصر المضاف يشير إلى ما يشير إليه الback الخاص بالtemp بحيث newnode->back = temp->back وذلك للحفاظ على اتصال عناصر الtest ببعضها البعض ,, ونزيد قيمة المتغير length بمقدار 1 ,, ثم نجعل الnext الخاص بالعنصر الذي يسبق العنصر المضاف يؤشر ألى العنصر المضاف newnode->back->next = newnode ونجعل الback الخاص بالtemp يؤشر على العنصر الجديد temp->back = newnode.
**************************************************
DSLL.printAll(); //to print the values of all elements in test
لطباعة قيم جميع العناصر في الtest ننشىء مؤشر مؤقت بإسم temp ونجعله يشير إلى ما يشير إليه الhead بحيث temp = head ومن ثم ندخل الtemp الى جملة for بحيث تنتهي جملة الfor عندما يشير الtemp إلى NULL بحيث ان temp != NULL تعمل على استمرار الfor ,, في كل مرة يتم طباعة قيمة العنصر الذي يؤشر إليه الtemp بحيث cout << temp-> data ,, ومن ثم نقوم بتغيير الtemp ليؤشر إلى العنصر التالي عن طريق temp = temp-> next.
**************************************************
DSLL.delete(3); //to delete the element with value 3 from test
نقوم بعمل مؤشر مؤقت بإسم temp يؤشر على ما يؤشر عليه الhead بمعنى temp = head بحيث يقوم بالبحث عن العنصر المراد حذفه من خلال جملة for ينتهي تنفيذها عند إيجاد العنصر المطلوب info == temp->data وما لم يتم إيجاد العنصر المراد حذفه يتغير الtemp لكي يشير إلى العنصر التالي temp = temp->next.
عند إيجاد العنصر فإن أهم خطوة هي الحفاظ على ترابط عناصر الtest مع بعضها البعض ,, لذلك نجعل الnext الخاص بالعنصر الذي يسبق العنصر المراد حذفه يشير إلى العنصر الذي يلي العنصر المراد حذفه temp->back->next = temp->next ونجعل الback الخاص بالعنصر الذي يلي العنصر المراد حذفه يشير الى العنصر الذي يسبق العنصر المراد حذفه temp->next->back = temp->back ,, ثم نحذف العنصر delete temp ,, ننقص من قيمة المتغير length بمقدار 1.
**************************************************
DSLL.delete(5); //to delete the element with value 5 from test
**************************************************
DSLL.delete(1); //to delete the element with value 1 from test
**************************************************
DSLL.printAll(); //to print the values of all elements in test
لطباعة قيم جميع العناصر في الtest ننشىء مؤشر مؤقت بإسم temp ونجعله يشير إلى ما يشير إليه الhead بحيث temp = head ومن ثم ندخل الtemp الى جملة for بحيث تنتهي جملة الfor عندما يشير الtemp إلى NULL بحيث ان temp != NULL تعمل على استمرار الfor ,, في كل مرة يتم طباعة قيمة العنصر الذي يؤشر إليه الtemp بحيث cout << temp-> data ,, ومن ثم نقوم بتغيير الtemp ليؤشر إلى العنصر التالي عن طريق temp = temp-> next.
**************************************************
سامر المناصرة
4K+
100+
ليست هناك تعليقات:
إرسال تعليق