هياكل البيانات Data Structures

وسنتناول فيها المواضيع التالية:
المكدس Stack
الطابور Queues
القوائم المرتبطة Linked List
الاشجار Trees
والمخططات Graph
ال Hash Table

:: Search & Sort , Template , STL


سنستخدم لغة البرمجة C++/C ، اي
سنفرق بين كود سي وسي ++ ، وذلك لايضاح الفرق بين اللغتين ، وكذلك لتكون
حافز لمبرمجي السي (عاشقي السي ) الى الانتقال الى العالم الاوسع ،،
عالم ال OOP.

+++++++++++++++++++++++++++++
Data Structure + هياكل البيانات او تراكيب البيانات
Class + فئة او طبقة او نوع او صنف ،، بصراحة لا أدري ما هو الافضل
Stack + الرصة او المكدس
Queue + الطابور او الصف
+++++++++++++++++++++++++++++


ما هي هياكل البيانات Data Structures:
هي عبارة عن اوعية "حاويات" للبيانات ، تتبع طرق معينة لتخزين البيانات فيها
والمقصود بالوعاء هو مساحة تخرين.

و اول مثال لهياكل البيانات (والتي لا تحتاج الى تعريف definition ) هي المصفوفات Arrays
المصفوفة
هي عبارة عن حاوية للبيانات ،، حجمها ثابت ،، ويجب ان يكون معلوم في وقت
الترجمة .وجميع محتوياتها من نفس النوع . كلام جميل
اعلان عن مصفوفة A :

CODE:
int A[5];



هنا قمنا بحجز مساحة لتخزين 5 اعداد صحيحة ،، ونستطيع استخدامها دون اي مشاكل تذكر.

طيب هممممممممم ما هي الحاجة الى هياكل "تراكيب" بيانات اخرى ! ما دام ان المصفوفة تعمل ؟!

الاجابة:
المصفوفة غير مرنة ،، بمعنى انك لا تستطيع اضافة عنصر اخر وقت تشغيل البرنامج
وكذلك لا تستطيع حذف عنصر وقت التشغيل ،، اي تجعلها مكونة من 3 اعداد صحيحة فقط
وكذلك لا تستطيع ان تجعل عدد عناصرها مجهول ، يحدده المستخدم مثلا او تحدده قيمة متغير اخر.
كل هذه اسباب تجعل المبرمجين يلجؤون الى التفكير بهياكل اخرى.

اعتقد
انك راح تفكر في ان نجعل المصفوفة كبيرة ،، وذلك حتى لا نحتاج الى اضافة
"فهي كبيرة بما تكفي" ، وبالنسبة للحذف راح تدبر اي طريقة للتلاعب "لانه
لا يمكن حذف اي عنصر من المصفوفة"

الاجابة:
المصفوفة الكبيرة تعنى استهلاك كمية من الذاكرة ،، صحيح ان الذاكرة لدي كبيرة ، ولكن هل هي كذلك عند س من الناس ؟

الامر
الاخر وهو الاهم عند الجميع هو سرعة البحث !! ذاكرة كبيرة يعني ان البحث
سيكون ابطأ ، ونحن كمبرمجين نريد ان نعطي المستخدم ذاكرة على قدر حاجته .

امر اخير عن المصفوفات ،، ليس فيها اي نوع حماية ، للاسف
جرب باستخدام مصفوفتنا الكريمة A ان تدخل اكثر من 5 اعداد ، وشاهد النتجية

كذلك هناك مشاكل كثيرة problems لايمكن حلها باستخدام المصفوفات العادية ،،
وراح نتطرق لبعض المشاكل عندما نتقدم قليلا بالدروس.

اعتقد ان الان وضح سبب الحاجة الى ال Data Structures

الان راح تقول : تبا للمصفوفات،، وعطنا اللي عندك
الاجابة : المصفوفات هي الاساس في معظم هياكل البيانات

قبل ما نبدأ بتطوير برنامج المكدس السابق ،، احب ان اشرح بعض النقاط
والتي لم اوضحهها سابقا .

العمليات على المكدس :
حتى الان لدينا عملتين two operations وهم :
1- عملية ادخال العناصر الى المكدس وسميناها push
2- عملية اخراج العناصر من المكدس وسميناها pop

العملية push تقوم بادخال العنصر الى المكدس ،، هذا العنصر سيقوم المستخدم بتمريره الى الدالة ()push
اي اذا اردنا ادخال العنصر 7 مثلا الى المكدس ، كل ما علينا هو استدعاء الدالة وتمرير العنصر 7 اليها كالاتي:

CODE:
push(7);



العملية الاخرى وهي pop تقوم بسحب العناصر من المكدس ،، ولتنفيذ هذه العملية يجب ان تستدعي الدالة
pop() ووضع متغير لكي يحمل قيمة العنصر الذي تم سحبه من المكدس، بهذا الشكل:

CODE:
int var=pop();



+++++++++++++++++++

خلينا الحين نتتبع برنامجنا السابق ،،لكي نعرف طريقة عمله ،، وراح اتحدث عن النسخة المكتوبة بلغة سي++
واذا في احد ما فهم اللي بالسي يقولنا ،،

على طول ندخل بالدالة الرئسية :

CODE:
- int main()
2- {
3- Stack s;

4- // push numbers 2,4,8
5- s.push(2);
6- cout<<"\n2 is pushed\n";
7- s.push(4);
8- cout<<"\n4 is pushed\n";
9- s.push(8);
10- cout<<"\n8 is pushed\n";

11- // pop numbers
12- cout<<"\n"<<s.pop()<<" is poped"<<endl;
13- cout<<s.pop()<<" is poped"<<endl;
14- cout<<s.pop()<<" is poped"<<endl;
15- return 0;
16- }



===========================

في السطر 3 قمنا بعمل متغير من النوع Stack .
الان ما الذي سيحدث هنا !!
طبعا سيتم حجز مساحة للمتغير s وكذلك استدعاء الدالة Stack() بشكل تلقائي ، تعمل هذه الدالة على
تهيئة المتغير s ، اي اعطائه قيمة ابتدائية ، قبل ان نستخدمه . للمعلومية الدالة stack تسمى بال constructor.
واذا ذهبنا الى المتغير s في الذاكرة ، راح نشوف انه يتكون من :

"مصفوفه ثابتة حجمها 10 عناصر وهي array + عدد صحيح وهو top"

ما يهمنا الان هو القيمة الابتدائية ل top والتي سوف تكون -1 ،، انظر الى ال constructor جيدا .

+++++++++++++++

في السطر 5 قمنا باستدعاء الدالة push وتمرير العدد الصحيح 2 ، وذلك حتى ندفعه الى المكدس.
كيف سيتم ذلك ؟؟

اولا سوف تقوم الدالة push بعمل اختبار ،، هل المصفوفة ذات ال 10 خانات ممتلئة ام لا ؟؟
اذا
كانت الاجابة نعم ، راح تطلع لك رسالة تنبيه وينتهي البرنامج "طبعا هذا حل
غير عملي ، ولكن هذا لغرض التوضيح والتركيز على المشكلة الاساسية "

واذا كانت الاجابة لا ،، اي ان هناك مساحة خالية لاستقبال عناصر ، فسوف يتم ادخال العدد 2 الى المكدس
دون مشكلة.

الاسئلة التي تدور بذهنك حاليا هي:
كيف نعرف ان المصفوفة ممتلئة او خالية ؟؟
كيف يتم ادخال العنصر 2 الى المكدس ؟؟

الفكرة كلها تتمحور حول المتغير top ،، وسوف نطلق عليه الدليل او index .

كيف يتم ادخال العنصر 2 الى المكدس ؟؟
الاجابة:
كما ذكرنا سابقا ،، المكدس يحوي على "مصفوفة من 10 خانات ومتغير top "اطلقنا عليه اسم دليل ذو قيمة ابتدائية -1.
بالنسبة للمصفوفة فهي تستخدم لتخزين العناصر التي تقوم بتمريرها بواسطة الدالة push

اما
الدليل فهو الذي يخبرنا ان المصفوفة خالية ام لا ؟ وايضا من خلاله نستطيع
ادخال العناصر الى المصفوفة اي ان الدليل يعمل ك index للمصفوفة ، وسوف
نرى كيف يتم ذلك.

نرجع الى اجابة السؤال ؟؟ كيف يتم ادخال العنصر 2 الى المكدس ؟؟
شوف الدالة push


CODE:
push(int i)
{
if(isFull())
{
cout<<"\nArray is Full";
exit(1);
}

else
{
++top;
array[top]=i;
}

}




اولا
تقوم الدلة باجراء اختبار للتأكد من ان المصفوفة ممتلئة ام لا ، لانها لو
امتلئت فلا نستطيع ادخال عناصر اخرى،ولنفرض ان المصفوفة خالية.
بعد ذلك سيتم زيادة المتغير top او الدليل بمقدار واحد "وحط مليون خط على كلمة زيادة"
اذا ستكون قيمة الدليل هي : -1 + 1 = كم ... اين الالة الحاسبة ، نعم = 0

وبعدها سيتم ادخال العنصر "وفي مثالنا 2" داخل المصفوفة وبالتحديد داخل array[0]


+++++++++++++++++++++++

الاسطر 7 و 9 بنفس الاسلوب السابق ،
ستكون قمية المتغير top الدليل بعد تنفيذ هذه الاسطر هي 2 ، وذلك لاننا ادخلنا عنصرين الى المكدس.

اذا سوف تكون لدينا 3 عناصر داخل المصفوفة ، وقيمة الدليل الحالية هي 2.

++++++++++++++++++++++++

اعتقد اننا تجاهلنا هذا السؤال؟ كيف نعرف ان المصفوفة ممتلئة او خالية ؟؟
الاجابة:
تكون خالية اذا كانت قيمة الدليل هي -1 "اي لم ندخل اي عدد"
وتكون ممتلئة اذا كانت قيمة الدليل تساوي "قيمة اكبر عدد من العناصر يمكن ادخاله في المصفوفة ".
اي اذا كان الدليل يساوي 9 ،، وهو اكبر عدد من العناصر يمكن ادخاله في المصفوفة .

++++++++++++++++++++++

السطر 12و13و14 كلها تعمل بنفس النمط.
قمنا باستدعاء الدالة pop والتي لديها قيمة معادة ،وهي قيمة العنصرالذي سيتم سحبه من المكدس.

كيف سيتم ذلك ؟؟ اي كيف سيتم سحب العناصر من المكدس ؟؟
قبل ان اجاوب على السؤال يجب ان تعرف شيء مهم جدا ،، اعتقد اني تحدثت عنه في احد مواضيع الاخ storm-man
لا يوجد شيء اسمه حذف قيمة من الذاكرة . يوجد عملية تعيين ، وعملية استعادة
ولكن حذف فلا يوجد .

خذ مثال:

CODE:
int x;
cout<<x;



لما لم تحذف هذه القيمة ؟؟ ما السر في هذا ؟؟
ببساطة شديدة عندما تحجز مساحة لمتغير وتقوم باعطاء المتغير قيمة :
int x=1;
ثم قمت بتحرير الذاكرة ،، مثلا انتهى نطاق المتغير scope ، فان الذاكرة ستكون غير محجوزة ،ولكن عليها قيمة grabage
وهي 1 ،، وممكن تتغير ،، اذا جاء برنامج اخر وطلب هذه الذاكرة (بدون كتشب) ثم استغنى عنها .

نرجع الى السؤال ؟كيف سيتم سحب العناصر من المكدس ؟؟
كما ذكرت سابقا ،، المكدس هو مصفوفة +دليل "سنغير التعريف عندما نتقدم "
ولكن الان :

CODE:
while(there is no new lesson)
{
cout<<"المكدس هو مصفوفة + دليل ";
}



المصفوفة تستخدم لحفظ العناصر او الاعداد التي يدخلها المستخدم (10 اعداد في مثالنا )
والدليل يعمل على اخبارنا بان هناك مساحة خالية ام لا ؟ هل المصفوفة ممتلئة ام لا ؟
وكذلك يعمل ك index في المصفوفة .

نشوف الدالة pop :

CODE:
pop()
{
int number;

if(isEmpty())
{
cout<<"\nArray is Empty";
exit(1);
}

else
{
number=array[top];
top--;

}

return number;

}



اولا تختبر هل المصفوفة خالية ام لا ؟ لانها ان كانت خالية ، فماذا سنسحب !!
وستكون خالية اذا كانت قيمة المتغير top الدليل هي -1 ،، وما عدا هذه القيمة فهي ليست خالية.

الان نفرض ان المصفوفة تحوي العناصر التي ادخلناها سابقا باستخدام push ، وان top يساوي 2.

انظر الى هذا الامر جيدا:


CODE:
number=array[top];



سيعمل top كدليل في المصفوفة ، اي ستكون هذا الجملة عند اول استدعاء للدالة بهذا الشكل:


CODE:
number=array[2];



وبعدها سينقص top بمقدار واحد ، اي سيصبح 1.
وكهذا تم سحب العنصر من المصفوفة ووضعه في متغير اخر .

وبنفس الطريقة مع باقي الاستدعاءات.
++++++++++++++++++++++

سؤال للاعضاء :

CODE:
Stack s;
s.push(10);
s.push(20);
s.pop();
s.push(30);



كم عدد العناصر داخل المكدس بعد تنفيذ هذه الجمل ؟ وماهي ؟
كم قيمة المتغير top ؟

+++++++++++++++++++++

الى هنا انتيهنا من شرح النسخة الاولى لبرنامج المكدس !!
وسنعمل على تطويرها الان ،، وذلك لانها لاتقبل الا عدد معين من العناصر .
اتمنى ان اكون قد وفقت في ايصال المعلومة ،،
اي اخطاء ؟؟ اي سؤال ؟؟

تابع معنا النسخة المطورة ..

المشكلة الاساسية في النسخة السابقة هو عدد العناصر ثابت .
يعني قيمة ثابتة 10 عناصر او 3 او 200 .
ومعظم البرامج تستخدم 10 ، ولكن السؤال ؟ هل 10 تكفي لكل انواع واشكال البرامج ؟
طبعا لا والف لا .

اذا تفضل وخذ نسختك المجانية من المكدس المطور ،، وللعلم انها ايضا لا تطبق بشكل كبير في الواقع !!

سوال : انت ذكرت ان النسخة السابقة غير مفيدة بسبب ان عدد العناصر محدود ، وذكرت ان نسختك المطورة هي الحل !!
الاجابة :
النسخة
المطورة هي حل جيد ، فهي تقوم بحل المشكلة الرئسية في النسخة السابقة ،
حيث تجعل المستخدم هو الذي سيدخل عدد العناصر، وليس الشخص الذي قام بكتابة
ال class .
اي اذا اردت ان يكون عدد العناصر 7 فهو كذلك ، 20 ايضا ، 1 ، على كيفك.

سؤال : واااااااااو انتهت المشاكل ، ؟ اذا لماذا لا تطبق في الواقع ؟
الاجابة : طيب لنفرض يا عزيزي المحترم جاء مستخدم وطلب 20 عنصر ، اوكي.
فجأة غير رأيه وقال :20 لاتكفي اريد 30 . هنا المشكلة الاولى .
المشكلة الثانية : ان المستخدم من الاول لا يعرف كم يحتاج ، واحد او 10 او 53 .

هذه النسخة تتطلب من المستخدم ان يدخل عدد العناصر التي يحتاج اليها ، بدون تغيير الرأي
يعني كلمتك تكون كلمة رجال

اذا سنحتاج الى نسخة ثالثة واخيرة "ابسط يا عم " تطبق في الواقع بكل المقاييس .
ولكن قبل النسخة الاخيرة ، يجب ان ندرس هذه النسخة اولا ،، لانها مفيدة جدا وبسيطة جدا ولكن بشرط "بسيط ايضا ":
وهو ان تدخل عدد العناصر التي تحتاج اليها بالضبط.

النسخة المطورة : Stack v0.1 :


CODE:
// Stack v0.1 using OOD
#include <iostream>
#include <stdlib.h>
using namespace std;

class Stack
{
private:
enum { MAX=10,MIN=-1};// MAXIMUM,MINIMUM STACK CONTENT
int *pArray; // pointer to array.
int top; //Contains location of Top most Data pushed onto Stack
int size; // contain the number of item(integer) you want

public:
Stack(int n=MAX);
~Stack();
void push(int); // push number to array
int pop(); // pop it from array
bool isEmpty(); // check if array is Empty!
bool isFull(); // check if it full

};

Stack::Stack(int n):
top(MIN),size(n)
{
pArray=new int[n];
}

Stack::~Stack()
{
delete pArray;
pArray=0;
}


bool Stack::isEmpty()
{
return (top==MIN?ture:false);
}

bool Stack::isFull()
{
return (top==size -1 ?ture:false);
}


void Stack::push(int i)
{
if(isFull())
{
cout<<"\nArray is Full";
exit(1);
}

else
{
++top;
*(pArray+top)=i;
// or use this : pArray[top]=i;
}
}


int Stack::pop()
{
int number;
if(isEmpty())
{
cout<<"\nArray is Empty";
exit(1);
}

else
{
number=pArray[top];
//or use this: number=*(pArray+top);
top--;
}
return number;

}


int main()
{
int number;
cout<<"\nEnter The Number you want\n\t\t>> ";
cin>>number;

Stack s(number);

// push numbers 2,4,8
s.push(2);
cout<<"\n2 is pushed\n";
s.push(4);
cout<<"\n4 is pushed\n";
s.push(8);
cout<<"\n8 is pushed\n";

// pop numbers
cout<<"\n"<<s.pop()<<" is poped"<<endl;
cout<<s.pop()<<" is poped"<<endl;
cout<<s.pop()<<" is poped"<<endl;
return 0;
}



فكرة هذه النسخة هي نفس الفكرة السابقة ، اي نفس الدالة push و pop وكذلك نفس الدليل top
الاختلاف الوحيد هو في المصفوفة .
في المثال السابق كانت مصفوفة ثابتة


CODE:
array[10];
[color=blue]



اما هنا فاصبحت مؤشر لمصفوفة ديناميكية !!
ديناميكية يعني ان حجزها يتم في وقت التنفيذ ،، يعني البرنامج بيشتغل عادي الى ان يصل الى الاعلان:


CODE:
pArray=new int[x];[color=blue]



ثم
يقوم بحجز المساحة المطلوبة ،، لاحظ في المصفوفة الديناميكية Dynamic
Array ان حجمها هو عدد غير ثابت !!يستطيع المستخدم ان يدخله .
اذا المصفوفة الدينامييكية dynamic هي السبب في النسخة المطورة

طيب ما هو الفرق بين المصفوفة الثابتة static array والمصفوفة الديناميكية dynamic array ؟؟

"قبل
ما اجاوب ،، احب اذكر عشاق لغة السي الى ان المصفوفة الديناميكية يتم
الاعلان عنها باستخدام الدالة malloc والوجودة في الملف الراسي stdlib.h ".

الفرق الاول هو ان المصفوفة الثابتة يتم حجزها وقت ترجمة البرنامج ،، اي قبل التشغيل ،، لذلك يجب ان تكون ثابتة الحجم.
وبالنسبة للمصفوفة الديناميكية فيتم حجزها وقت التشغيل ،، وبالتحديد عندما يصل البرنامج الى الامر ، مثلا :

CODE:
int x=2;
if(x==3)
int a=new int;[color=blue]



في هذا المثال لن يتم حجز ذاكرة ديناميكية للمتغير a ، مسكين

ولكن في هذا المثال:


CODE:
int x=2;
if(x==3)
int a;[color=blue]



سيتم حجز ذاكرة للمتغير a ،، وقت ترجمة البرنامج .


الفرق الثاني والاهم ، وهو ان المصفوفة الثابتة يتم حجزها في ذاكرة تسمى stack
هذه
الذاكرة stack "هي من التطبيقات على موضوعنا ،تعمل بنفس طريقتنا ، لكن لا
دخل لنا بها " يتم بها حجز اي متغير ،واي وسيط في دالة ، وكذلك مصفوفتنا
الثابتة.
وما يميزها هو ان المتغيرات التي بداخلها تحذف بمجرد خروج المتغير من المدى scope تلقائيا ، شوف مثال على الطاير:


CODE:
int main()
{
int x=2;

{
int y=4;
}

cout<<x;
cout<<y;

return 0;
}



هذا البرنامج لن يعمل ،، والسبب هو ان المتغير y قد تم حذفه تلقائيا وذلك لانه خرج من المدى scope

اما بالنسبة للمصفوفة الديناميكية (او المتغير الديناميكي )فيتم حجزها على ذاكرة تسمى ب المخزن الحر free store او heap
وما يميز هذا ال heap هو ان المتغيرات التي بداخله لا تحذف الا عندما تقوم انت بحذفها ، او عند انتهاء البرنامج .
يعني مواضيع ال scope هذه لا تخص الheap
شوف المثال :

CODE:
int main()
{
int x=2;
int *y;
{
y=new int;
*y=4;
}

cout<<x;
cout<<*y;
delete y;

return 0;
}



هذا البرنامج سيعمل 100% .
تم حجز مساحة ديناميكية للمتغير y ،، واعطائها القيمة 4 .
هذه المساحة لن تحذف حتى لو طلعنا من المدى .

اغتقد ان بعض الناس راح يسألو ؟؟ ليه ما كتبت داخل ال block الامر :

CODE:
int *y=new int;



اي لماذا فصلت الاعلان عن المتغير y وعن حجز الذاكرة ؟؟
قبل ما اجاوب اقرأ الملاحظة :

"عدم سدادك لفاتورة الهاتف سيؤدي الى .... " اووو معليش ،، اصل التلفون قاطع


"عدم حذفك للذاكرة يسبب احد الاخطاء المعروفة ب "تسرب الذاكرة " Memory Leak
وهو خطأ قاتل fatal error
ولكن في مثالنا البيسط اللى فوق لا يوجد داعي لحذف المتغير y لان البرنامج سوف يتنهي ، ويقوم بحذفه تلقائيا ."

طيب لو تجاوبنا مع اخينا السائل ،، وكتبنا البرنامج بهذا الشكل :

CODE:
int main()
{
int x=2;

{
int *y=new int;
*y=4;
}

cout<<x;
cout<<*y;

return 0;
}



الاجابة : يوجد مشكلتين كبيرتين :
الاولى :المؤشر y تم حجزه داخل ال block ،، وتم استخدامه خارجها . تذكر انه قد تم حجزه على ال stack
المشكلة الثانية :
عندما نطلع من ال block مين حيقدر يحرر الذاكرة الديناميكية ، المؤشر y قد
مات "اهئ اهئ " بعد الخروج من ال block وهو الوحيد الذي كان يستطيع ان
يقوم بحذف الذاكرة .

بهذا الشرح الغير مباشر ،، اتمنى ان تكون
النسخة المطوره من برنامج المكدس قد وضحت،، واي احد عنده سؤال فلا يتردد ،
او يريد شرح مباشر على الهوا ، ايضا لا يتردد.
وبالنسبة للنسخة الاخيرة ،، فراح نأجلها كمان جلستين او ثلاث ، وذلك لانها تتعلق بال linked List
وهي النسخة المفضلة للجميع ،، وللناس اللى حابه تعرف شكلها ، شوف المثال:

CODE:
int main()
{
Stack s;
s.push(2);
s.push(4);

s.push(8);

...etc

// pop numbers

return 0;}




يعني راح نحل مشكلة ادخال عدد العناصر ،،
وكل ماعليك هو ان تدخل الاعداد ، تسحب ، على كيفك .
وكمان راح نعمل منها واحدة سوبر "او خليها كمبو "
والتي
تستخدم حاليا ،، في كل التطبيقات .بحيث تقبل منك اعداد ، حروف ، سلاسل
نصية ، قطط ، طائرات ،...الخ.وذلك بواسطة الملكة template

الى ذلك الحين ، نستودعكم الله ،، والى اللقاء في حلقة قادمة مع اخو المكدس وهو" ال Queue وبالعربي الطابور وتلفظ كيو".

وقبل ما انسى ،، من المفروض حاليا ان اضع الاسئلة "المسخنة" على المكدس ،، ولكني سأنتظر حتى يجهز الجميع.
طبعا سنحاول حلها مع بعض اذا لم يتمكن احد من حلها ،، ولكن ان شاء الله الجميع سوف يحلونها

اليوم راح نتحدث عن ال Queue : "و تلفظ كيو وليس كيوي "

ما هو ال Queue ؟؟
لا ارى اجابات !!

طيب ،، نترجم السؤال بالعربي : ما هو الطابور ؟؟
ماشاء الله ،، كمية من الاجابات .

يقول احدهم : هذا طابور المقصف !!
ويقول العامل : هذا طابور الجوازات !!
ويقول واحد "مسوي خبير" هذا الطابور الموجود داخل ال CPU والذي يقوم المعالج بأخذ الاوامر منه وتنفيذها واحدة تلو الاخرى .

الاجابات كلها صحيحة ،، ولكنها ناقصة شيء بسيط :
ال
Queue هو عبارة عن هيكل بيانات Data Structure ،، يستخدم لتخزين البيانات
"لغرض المعالجة " بحيث ان العنصر "البيانات" الذي يدخل اولا الى هذا
الطابور هو الذي يخرج اولا او "هو الذي يتم معالجته اولا " ، الا في حالات
خاصة .

وراح نأخذ مثال اخونا العامل لكي نوضح التعريف : طابور الجوازات :
اخونا
العامل ،، جاء الساعة السابعة صباحا الى الجوازات لكي يخلص مبكرا ،، ولكنه
فوجيء بأن الطابور ممتلئ بكمية من البشر ، حاول ان يتجاوز الصف "الطابور"
ويذهب الى الامام ،، ولكن هيهات .
شروط الطابور ان اي شخص "او عنصر" يأتي اليه ،، سوف يدخل في اخره "عملية الادخال تسمى Enqueue".

يعد حوالي نصف ساعة ،، تحرك الصف خطوة الى الامام ،، لماذا ؟؟
اكيد لان اول شخص "او عنصر" قد جاء دروه لكي يتم معالجته ، لذا خرج من هذا الصف الممل.
"عملية اخراج العنصر من الطابور تسمى Dequeue "

بعد فترة بسيطة ، جاء واحد جديد الى هذا الطابور ، واصبح خلف اخونا العامل ، فجأة ،، وبدون سابق انذار
تحرك هذا الرجل الجديد الى بداية الطابور !!

العامل يصيح بأعلى صوته ،، لماذا قد تقدم عليه هذا الشخص !!
تقدم اليه احد الحراس وقال:اصمت هذا ابوه "مدير الجوازات" !!


هممممممممممم ،، بعد هذا المثال الحزين ،، اكيد انك قلت : ياريت كنت تعطينا مثال المعالج CPU
لا فيه ظلم ولا شيء ،، العنصر الذي يأتي اولا سيخرج اولا ، حتى وان كان خلفه شيطان.


استنتاج بسيط : يوجد نوعين من الطوابير :
طابور "فيتامين و " ، وطابور عادي .

الاول يطلق عليه ال Priority Queue "طابور الاولية او طابور الاسبقية "
ولكن خلينا نسميه " طابور الواسطة "

والثاني يطلق عليه طابور فيفو FIFO .
مين هو فيفو ؟؟
هذا ليس شخص ،، وانما طريقة عمل وهي اختصار ل first in first out
اي العنصر الذي يأتي اولا ،، هو الذي يخرج اولا .

النوع الاول اشمل من الثاني ،، لانه يعمل بمبدأ FIFO ويزيد عليه مبدأ الاسبقية ،،
اي ان العنصر الذي يأتي اولا ،، هو الذي سيخرج اولا "اذا وفقط اذا " لم يوجد عنصر اعلى في الاسبقية.
يعني طابور الاسبقية هذا كيف يعمل ؟؟
يقوم بفحص اولوية كل عنصر في الطابور ،، ويقوم باخراجهم اولا .
وبعد ذلك بيرجع FIFO عادي .

الاولوية تحدد بأي شيء تريده ،، ولكن راح نعملها قيمة متغير مثلا .

الى هنا نكون قد اعطينا مقدمة جيدة عن ال Queue وانواعه ،، وراح نتحدث حاليا عن النوع الثاني
وهو FIFO Queue .

++++++++++++++++++++++++++++++++

بعد هذا المقدمة البسيطة ،، بقي ان نذكر اين تستخدم ال Queue عمليا !!

الاجابة : في اي برنامج يطلب معالجة العناصر بحسب الترتيب الذي دخلت به ،، والامثلة كثيرة ، ناخذ مثلا ،، برنامج لمطعم "بيتزا هت " راح يستخدم طابور ،، بحيث ان الزبون الذي يطلب اولا هو الذي سيحصل على طلبه اولا .

اي راح يوجد داخل البرنامج طابور "مماثل للذي راح نتكتبه ان شاء الله "، يحوي على رقم الطلب والطلب نفسه .
شوف شكل تخيلي للطابور: الطلب ، "الرقم"

"بيتزا صغير"،"بيبسي"،125 -> "بيتزا كبير بدون مشروم "،"مياه"،124 ->"بيتزا وسط"،123

صورة توضيحية :


طابور مشهي
وكذلك برامج تسجيل الطلاب ،، وبرامج المعاملات ،، و...والخ.

+++++++++++++++++++++++++

تطبيق ال Queue :
بنفس فكرة المكدس ،، يمكن ان نتطبق ال Queue باستخدام المصفوفات ، او باستخدام القوائم المرتبطة.
وراح نتحدث عن تطبيقها باستخدام المصفوفات حاليا ،،


العمليات على Queue :
العمليات كثيرة ،، ولكن لغرض التوضيح سنستخدم العمليات الاساسية ، وهما اثنين :
عملية ادخال العنصر وتسمى Enqueue
عملية اخراج العنصر وتسمى dequeue

وقبل ان ندخل في الحديث عن هذه العمليات ،، يجب ان نذكر ،، ماهي مكونات ال Queue :
يتكون ال Queue في شكله العام من:

مصفوفة + دليلين "وليس واحد كما هو الحال مع المكدس".

المصفوفة تستخدم لتخزين العناصر.
الدليل الاول وراح نسميه front وهذا متغير يدلنا على بداية الصف.
اما الدليل الثاني فهو back وهذا ايضا متغير يدلنا على نهاية الصف.

راح نؤجل الحديث عن العمليات ،، لاني وجدت صعوبة في الوصف ،،
لذلك سأضع الكود ،، وبعدها سنشرح العمليات.
لكن للتذكر : ان الادخال في الطابور يتم من اللخلف ،، والاخراج من الامام .

وبالنسبة
لكود السي ،، فما راح اضعه الان ،، حتى ما يثقل الصفحة ،، وحتى ما يتلخبط
الاعضاء، وان شاء الله مع نهاية الدورة سأضع كل الاكواد للتحميل C ,C++
مع انه بسيط جدا ، لكن اذا اراد احد كود سي الان فليطلب وحنا امرين

=====================

كود مبدئي للطابور FIFO Queue بلغة C++:


CODE:
#include <iostream>
#include <stdlib.h>

using namespace std;


class Queue
{
private:
enum {MAX=10};
int array[MAX];
int back,front;

public:
Queue();

void enqueue(int e);
int dequeue();
bool isFull();
bool isEmpty();
};


Queue::Queue():
back(0),front(0)
{}

void Queue::enqueue(int e)
{
if(isFull())
{
cout<<"\nQueue is Full";
exit(1);
}

back=(back+1)%MAX;
array[back]=e;
}


int Queue::dequeue()
{
if(isEmpty())
{
cout<<"\nQueue is Empty";
exit(1);
}

front=(front+1)%MAX;
return array[front];
}


bool Queue::isFull()
{
if( (back+1)%MAX == front )
return true;
else
return false;
}

bool Queue::isEmpty()
{
if( back == front )
return true;
else
return false;
}


int main()
{
Queue q;
cout<<"\nenqueue(2)";
q.enqueue(2);
cout<<"\nenqueue(4)";
q.enqueue(4);
cout<<"\nenqueue(6)";
q.enqueue(6);

cout<<"\nDequeue elements\n";

cout<<"dequeue: "<<q.dequeue()<<endl;
cout<<"dequeue: "<<q.dequeue()<<endl;
cout<<"dequeue: "<<q.dequeue()<<endl;

return 0;
}



نفس مشكلة برنامج المكدس المبدئي ،، وهو عدد العناصر ثابت ،، سنحل المشكلة بالنسخة المطورة فورا،
ارجع الى المكدس لتعرف المزيد.

=====================

الكود المطور للبرنامج ال Queue:

CODE:
#include <iostream>
#include <stdlib.h>

using namespace std;


class Queue
{
private:
enum {MAX=10};
int *pArray;
int back,front;
int size;

public:
Queue(int s=MAX);
~Queue();

void enqueue(int e);
int dequeue();
bool isFull();
bool isEmpty();
};


Queue::Queue(int s):
size(s),back(0),front(0)
{
pArray=new int[s];
}

Queue::~Queue()
{
delete [] pArray;
pArray=0;
}

void Queue::enqueue(int e)
{
if(isFull())
{
cout<<"\nQueue is Full";
exit(1);
}

back=(back+1)%size;
pArray[back]=e;
}


int Queue::dequeue()
{
if(isEmpty())
{
cout<<"\nQueue is Empty";
exit(1);
}

front=(front+1)%size;
return pArray[front];
}


bool Queue::isFull()
{
if( (back+1)%size == front )
return true;
else
return false;
}

bool Queue::isEmpty()
{
if( back == front )
return true;
else
return false;
}


int main()
{
Queue q(10);
cout<<"\nenqueue(2)";
q.enqueue(2);
cout<<"\nenqueue(4)";
q.enqueue(4);
cout<<"\nenqueue(6)";
q.enqueue(6);

cout<<"\nDequeue elements\n";

cout<<"dequeue: "<<q.dequeue()<<endl;
cout<<"dequeue: "<<q.dequeue()<<endl;
cout<<"dequeue: "<<q.dequeue()<<endl;

return 0;
}





الشرح ::

ندخل بالدالة main على طول:

CODE:
1-int main()
2-{
3- Queue q(10);
4- cout<<"\nenqueue(2)";
5- q.enqueue(2);
6- cout<<"\nenqueue(4)";
7- q.enqueue(4);
8- cout<<"\nenqueue(6)";
9- q.enqueue(6);

10- cout<<"\nDequeue elements\n";

11- cout<<"dequeue: "<<q.dequeue()<<endl;
12- cout<<"dequeue: "<<q.dequeue()<<endl;
13- cout<<"dequeue: "<<q.dequeue()<<endl;

14- return 0;
15-}



في السطر الثالث ،، تم عمل كائن من النوع Queue.
الدالة البانية او ال constrcutor سوف تعمل تلقائيا وذلك لاعطاء q قيم ابتدائية.
المتغير q يتكون من:
مؤشر لمصفوفة ديناميكية + متغير front + متغير back + متغير size

المصفوفة الديناميكية يتم بها تخزين العناصر ،، والمؤشر pArray هو الوحيد القادر على الوصول الى هذه المصفوفة الديناميكية.

المتغير front يعمل كدليل الى بداية الطابور ، بمعنى انه يحمل رقم اول خانة في الطابور
اما المتغير back فهو يحمل رقم اخر خانة في الطابور

والقيم الابتدائية لهم هي الصفر.

اما المتغير size فهو يحمل عدد العناصر التي يحتاج اليها المستخدم.

صورة توضيحية :



++++++++++++++++++++++++++

السطر 5 ،، وهي اول عملية ادخال enqueue ،، حيث تم ادخال العدد 2 .
دعنا ندخل الى تفاصيل هذه العملية ، شاهد الكود :


CODE:
void Queue::enqueue(int e)
{
if(isFull())
{
cout<<"\nQueue is Full";
exit(1);
}

back=(back+1)%size;
pArray[back]=e;
}




صورة توضيحة قبل الادخال :


اولا تقوم الدالة بعمل اختبار لكي تعرف ان المصفوفة ممتلئة ام لا ، واذا كانت الاجابة نعم ، فسوف تطلع رسالة تنبيه ويخرج البرنامج.
اما اذا كانت الاجابة لا ،،
قبل ما نشوف ماذا سيحدث ،،
هل تتذكر مثال العامل في الجوازات !! اين وقف العامل في الطابور؟؟ واين وقف الرجل الذي اتي اخيرا؟
الاجابة : في المؤخرة back
"اي عنصر يأتي جديد سوف يدخل في اخر الطابور" وهو ما اطلقنا عليه back.

نرجع الى الكود.
بما ان العدد 2 جاء الى الطابور ، فيجب ان يدخل في اخر الطابور ،راقب كيف يحدث ذلك :
يتم زيادة الدليل back بمقدار واحد "انسى حاليا الجزء الباقي وهو %size "
اي ستصبح قيمة الدليل = 0 + 1 = 1 .
اذا back=1 , front =0

بعد ذلك سيتم ادخال العدد 2 في المصفوفة ، وبالتحديد عند العنصر pArray[back] اي في

CODE:
pArray[1]



وهذا هو اول واحد في الطابور.



ناتي الان للسطر 7 ،، وهي عملية ادخال العنصر 4 ،، راقب كيف يحدث ذلك :
اولا الاختبار سيفشل ،، لماذا ؟؟ كيف نعرف ان المصفوفة ممتلئة ؟؟
راح نأجل الاجابة ،، ونكمل على فرض ان المصفوفة ليست ممتلئة ،،

سيتم زيادة الدليل back بمقدار واحد ايضا ،،
اي سيصبح back=2 ,front=0



ارجو منكم ان تقوموا برسم توضيحي للمصفوفة على الورق + الدليلين ،، وتقوموا بتتبع البرنامج.

الان سنفرض اننا ادخلنا العديد من العنصر داخل الطابور ، بهذا الشكل:



واردنا ادخال عنصر جديد ،، مالذي سيحدث !!
طبعا لاحظ ان المصفوفة امتلئت !!
وان قيمة الدليل back تساوي حجم المصفوفة ناقص واحد
اي
اذا كانت مصفوفتنا من 10 عناصر فان الدليل back راح يساوي 9 ،، وهو اخر
شيء يمكن ادخاله في المصفوفه ،، لاننا نعلم ان المصفوفة ترقم من الصفر
وليس من الواحد.

الاجابة : لن يسمح لك بالادخال ، راح يعطيك رسالة تنيبه بان المصفوفة امتلئت وينتهي البرنامج.
وطيب كيف عرف ان المصفوفة امتلئت !!
انظر الشرط التالي داخل الدالة isFull() :

CODE:
if( (back+1)%size == front )



اذا كان الدليل front يقع بعد الدليل back فهذا يعني ان المصفوفة امتلئت .
او بمعنى اخر اذا كان back+1 == front

طيب لماذا استخدمنا معامل الباقي من القسمة؟؟
الاجابة لاننا ان لم نستخدمه راح يحصل خطأ كبير .
الان بفرض ان back=9 وهو اخر خانة في المصفوفة
اذا قمنا بكتابة الشرط بهذه الطريقة :

CODE:
if( back+1 == front )




فان
المتغير back راح تكون قيمته تساوي 9+1=10 وهو خارج حدود المصفوفة out of
boundary لذلك استخدمنا هذا المعامل "لكي نضمن اننا داخل حدود المصفوفة "

اتمنى ان تكون عملية الادخال enqueue قد وضحت ، وكما ذكرت قم بالرسم + التطبيق على الجهاز للحصول على افضل نتيجة

++++++++++++++++++++++++++++

نتنقل الى العملية الاخرى وهي سحب العناصر dequeue من الطابور:
السطر 11و12و13 :

طيب لنفرض ان مصفوفتنا تحوي الثلاث عناصر.
والدليل back=3 , front=0
انظر الصورة:


الان نريد سحب (اخراج) اول عنصر ،، طبعا سيكون 2 .
بكل بساطة نستدعي الدالة dequeue والتي ترجع بالعدد الاول في الطابور.
خلينا نشوف الدالة dequeue اثناء العمل :


CODE:
int Queue::dequeue()
{
if(isEmpty())
{
cout<<"\nQueue is Empty";
exit(1);
}

front=(front+1)%size;
return pArray[front];
}



اولا ستختبر المصفوفة ، هل هي خالية ام لا ..
اذا نعم ،، سوف ينتهي البرنامج ، واذا لا :

سوف تقوم بسحب العناصر من المقدمة "كما هو الحال في الطوابير ، يخرج من في الامام اولا"
لذلك سوف يتم زيادة الدليل front بمقدار واحد ، واستخدام ال % كما ذكرت للتأكد من اننا داخل حدود المصفوفة.
وبعد ذلك تقوم بارجاع العنصر الموجود في pArray[front];

شاهد الصورة ، بعد الاخراج العنصر الاول:


اخراج العنصر الثاني:


اخراج العنصر الثالث :


المزيد من السحب:
طبعا لن يتم ،، لان الشرط سيصبح صحيح اي ان المصفوفة ستكون خالية.
كيف نعرف انها خالية :
انظر الشرط داخل الدالة isEmpty()

CODE:
if(back == front)



اذا الدليلين اصبحوا متساويين ،، فهذا يعني بأن الطابور قد اصبح خالي.

+++++++++++++++++++++++++


ملاحظات:
* فكرة المكدس كانت تعتمد على مصفوفة ودليل ، اما الطابور فيعتمد على مصفوفة ودليلين.
* الدليل يعمل ك index للمصفوفة.
* سنقوم بانشاء المكدس و الطابور باستخدام القوائم المرتبطة ، وهي اسهل وافضل واكثر كفاءة.

الى هنا ينتهي موضوع الطابور ،، ولكن احس انه الشرح ما مفهوم !!
لاني كتبت هذا الدرس على أساس انك انتهيت من تطبيق الدرس السابق وهو المكدس!!
فاي واحد يريد ان يسأل فليتفضل ،،

هل اضع بعض الاسئلة على المكدس والطابور الان ،، ام انتظر حتى تنتهون من تطبيق الدروس !!!

اتمنى ان اي واحد خلص من القراءة فليخبرنا ،،

الى اللقاء مع اجمل موضوع في عالم هياكل البيانات Linked List.

ما هي القائمة المتصلة !!
قبل ما نذكر الاجابة ،، نسوي refresh بسيط لاول موضوع تحدثنا وهو المصفوفات ،،
شوف صورة توضيحية :


كما ذكرنا العيب الاساسي وهو انها ليست مرنة ،، بمعنى انها ليست قابلة للزيادة او النقصان وقت تشغيل البرنامج.

هنا جاء دور القائمة المتصلة لكي تحل لنا هذه المشكلة !!

انظر الصور التوضيحية :




القائمة المتصلة هي عبارة عن هيكل بيانات مكون من عقد nodes مرتطبة مع بعضها البعض ، ولها بداية ونهاية.

التعريف جميل بعض الشيء ،، ولكن اول سؤال يبرز هنا ؟؟ ما هي العقدة ؟؟ ولماذا ترتبط مع بعضها ؟ واين البداية والنهاية ؟؟

العقدة هي "عنصر في القائمة المتصلة" ، ومجموعة العقد تكون لنا "قائمة متصلة" .
بنفس فكرة المصفوفة ،، فكل عنصر فيها يسمى" عنصر في المصفوفة "، ومجموعة العناصر تكون لنا "مصفوفة" .

كل عقده تحوي حاجتين :
1- بيانات data
2- مؤشر الى عقدة اخرى pointer to node

نشوف العقدة في صورة توضيحية :



وكما ذكرت : مجموعة العقد تكون لنا قائمة متصلة ،،

اما بالنسبة للسؤال : لماذا ترتبط العقد مع بعضها ؟
وذلك حتى تكون لنا قائمة متصلة .

بقي شيء مهم لم نذكره في الصورة الاولى للقائمة المتصلة: head , NULL

اولا :ال head هو مؤشر لاول عقدة في القائمة المتصلة ،، واذا كانت القائمة خالية فانه سيشير الى NULL والتي تعني فارغ او 0
صور توضيحية "انفع اصير مصمم ؟؟،، "







طيب
انتهينا من التعريف ،، لكن احب اقول مرة ثانية ان المؤشر head هو مؤشر
لاول عقدة ،، واول عقدة تشير الى الثانية ،،والعقدة الثانية تشير الى
العقدة الثالثة ،و... وهكذا حتى نصل الى عقدة تشير الى NULL والتي راح
تكون هي العقدة الاخيرة في القائمة بتاعتنا .

اين الخطورة هنا !!
الخطورة تكمن في المؤشر head !!
لانه لو انحذف او تبدلت قيمته ما راح نستطيع التعامل مع هذه القائمة ،، وراح تظهر لنا مشكلة تسرب الذاكرة !!
شوف الصورة "وش رايكم نقلب الدروس صور "
هذه الصورة لقائمة بدون مشاكل :



اما هذه:


هنا تأتي الكارثة !!
المؤشر head وهو الذي كان يشير الي اول عقدة ،، اصبح يشير الى شيء اخر !!
حاليا في هذا الوضع المخيف ،، ما راح نقدر نوصل للقائمة بتاعتنا ،، وما راح نقدر نحذفها .

ما هو الحل :
الحل في انك تتذكر ما هي القيمة التي سوف تكون للمؤشر head في كل سطر تقوم بكتابته


سؤال: ما هي عدد العقد التي نستطيع انشائها ؟؟
عدد
كبير جدا ، يعتمد بالمقام الاول على حجم الذاكرة عندك ،، وماهو الجزء الذي
خصص للذاكرة heap ، فكل العقد راح نعملها في ال heap ،، وقد تحدثنا عنها
سابقا .

سوال ثاني: القائمة المتصلة تشبه المصفوفات باستثناء الروابط بين العقد ؟؟
نعم
، القائمة تشبه المصفوفة ،، والذي جعلها مرنه هي الروابط ، حيث تستطيع حذف
العقدة "بتغيير الروابط" وكذلك انشاء عقدة جديدة "ايضا بتغيير الروابط ".


وقبل ان ننهي هذه المقدمة ،، اريد التحدث قليلا عن ذاكرة ال heap ::

كيف تعمل ال heap :

ال heap هي منطقة من الذاكرة RAM ،، وغالبا مساحتها اكبر من المنطقة Stack
ونستطيع تخيلها بالصورة :



طيب كيف نحجز مساحة للعدد 5 مثلا.
الاجابة : بما ان العدد 5 هو int ،، اذن راح نحجز مساحة من النوع int.

احد
الفروق بين حجز ذاكرة في ال heap وبين الحجز في ال stack ، هو ان حجز
الذاكرة في ال stack لا يتم بدون وجود اسم معرف identifier ، اي لابد من
اعطاء اسم للمتغير ، مثلا

CODE:
int x;



فلا يمكن ان نقول :
CODE:
int



وكذلك يمكن الوصول للمتغير x عن طريق اسمه او عن طريق عنوانه ،، شوف :
CODE:
x=3;



او:
CODE:
int *p=&x;
*p=3;



النتيجة هي نفسها في البرنامجين .


اما بالنسبة لل heap ، فحجز الذاكرة يتم بدون اسم معرف ،،فكل ما عليك تحديده هو نوع المتغير الذي تريد ان تحجزله مساحة، شوف:

CODE:
int *p=new int;
*p=3;



طيب لماذا استخدمنا new و *p ؟؟
السبب لاننا نريد ذاكرة في الheap وذلك لا يتم الا عن طريق المعامل new
وهذا المعامل يقوم بارجاع عنوان المساحة التي قام بحجزها .

صورة توضيحية ،، مهمة جدا :




طيب اين المشكلة ؟؟ لماذا الصورة مهمة جدا !!
الاجابة:
هل تذكر المؤشر head والذي يشير لاول عقدة في القائمة المتصلة !! ماذا يحدث لو تغيرت قيمته ؟؟
هي نفس القصة الان.
لو تغيرت قيمة المؤشر p واصبح يشير الى شيء اخر ،، او طلع من المدى scope الموجود فيه "تذكر انه محجوز على ال stack"
لحدثت كارثة ،، تسمى .... تسرب الذاكرة .

ما الذي يمنع من تسرب الذاكرة Memory Leak ؟؟
الاجابة :
حذف الذاكرة الموجودة على ال heap ،، ويتم ذلك بالمعامل delete ،، كالاتي:

CODE:
delete p;



الان منعنا من تسرب الذاكرة ،، ولكن يوجد مش.... خلينا نشوف صورة



كما ذكرت الصورة ،،
المؤشر p يشير الى منطقة محذوفة ،، ما هو المصطلح العلمي لهذا الشيء ؟؟
الموشر الطائش او المؤشر الضال stray pointer ؟؟
ما هو ال stary pointer ؟
هو مؤشر يشير الى منطقة من الذاكرة ،، لا تخص برنامجنا !!
مثل المؤشر p والذي يشير الى ذاكرة تم التخلص منها ، اي ليست ملكنا .
ولكي نهديه من الضلال ،، يجب ان نعمل له عملية تعيين .
يعني يا نستخدمه لكي يؤشر الى اي متغير لدينا ، او نعطيه قيمة NULL
شوف الصورة بعد التعيين:



معليش يا شباب ،، بس في ملاحظة "صغنونة " قبل ما ننهي المقدمة ،، مع انها مكررة مرتين ، وهذه الثالثة :

المؤشر
p هو الذي يملك الحرية في التخلص من مشكلة تسرب الذاكرة ،، لذلك يجب ان
ننتبه اليه ، حتى لا يخرج من المدى او تتغير قيمته ،، ويصبح لدينا تسرب
للذاكرة ،، والذي لا خلاص منه الا عندما ينتهي البرنامج ، صورة اخيرة :







تااااااااااااااابع ،، المزيد

* تطبيق المكدس باستخدام القائمة المتصلة.
* تطبيق الطابور باستخدام القائمة المتصلة .

اولا : تطبيق المكدس stack باستخدام القائمة المتصلة linked list

مسبقا ،، تحدثنا عن نسخة مطورة "كمبو دبل مكدس " باستخدام القائمة المتصلة ،،
والتي ذكرنا انها تطبق في معظم البرامج ،، ولا غبار عليها .

وفكرتها باختصار :
نفس القائمة المتصلة اللى فوق ،، بس راح يكون في دالتين فقط ، وليست ستة دوال ،،
الدالة الاولى فهي لادخال العقد الى اخر القائمة واللى اطلقنا عليها addLast
والثانية هي لسحب العقد من اخر القائمة المتصلة واللي اطلقنا عليها removeLast

وهذه الدوال توافق فكرة المكدس : "الادخال يتم من اعلى ، والسحب ايضا من اعلى "


كتابة الكود ،،
"نسخ+لصق" من كود القائمة المتصلة ، مع تغيير اسم الدالة addLast الى push
وتغيير اسم الدالة removeLast الى pop


CODE:
// Stack using Linked List, by Ahmad Essam.

#include <iostream>
using namespace std;

/////// Node Class //////

class Node
{
private:
int data;
Node *pNext;
Node *pPrevious;

public:
Node(int d):data(d),pNext(NULL),pPrevious(NULL){}

int getData()const{return data;}
void setData(int d){data=d;}

Node * getNext()const{return pNext;}
void setNext(Node *p){pNext=p;}

Node * getPrevious()const {return pPrevious;}
void setPrevious(Node *p){pPrevious=p;}

};

/////// LinkedStack class ///////

class LinkedStack
{
protected:
Node *pHead; //pointer to the first node
Node *pTail; //pointer to the last node
int nodeCounter; // count the number of nodes

Node * makeNode(int data); // make & return new node
void remove(Node *tmp); // remove node from linked list

public:
LinkedStack();
~LinkedStack();

// operations
void push(int data);
void pop();
void destroyList();
int getSize()const{return nodeCounter;}
int top()const
{
if (pTail == NULL)
return 0;
return pTail->getData();
}
};


LinkedStack::LinkedStack():
pHead(NULL),pTail(NULL),nodeCounter(0)
{}


LinkedStack::~LinkedStack()
{
destroyList();
}


Node * LinkedStack::makeNode(int data)
{
nodeCounter++;
return new Node(data);
}


void LinkedStack::push(int data)
{
// make new node
Node *pNew=makeNode(data);

// make the new node as the last node in the linked list

//if there is no node in the linked list , add node.
//otherwise move the new node to the last.

if( !pHead )
pHead=pTail=pNew;

else
{
pTail->setNext(pNew);
pNew->setPrevious(pTail);

pTail=pNew;
}
}


void LinkedStack::remove(Node *tmp)
{
delete tmp;
nodeCounter--;
};


void LinkedStack::pop()
{
if( !pHead )
{
cerr<<"\nThere is no any node to remove!!";
return ;
}

Node *pTmp=pTail;
pTail=pTail->getPrevious();

if(pTail)
pTail->setNext(NULL);

else
pTail=pHead=NULL;

remove(pTmp);
}



void LinkedStack::destroyList()
{
Node *pTmp=pHead;
Node *pCur;

while( pTmp != NULL)
{
pCur=pTmp;
pTmp=pTmp->getNext();
remove(pCur);
}

}

/////// main //////////

int main()
{
LinkedStack *stack=new LinkedStack;

for(int i=0;i<5;i++)
stack->push(2*i+1);

for(int i=0;i<5;i++)
{
cout<<"\npop: "<<stack->top();
stack->pop();

}


return 0;
}



من فهم القائمة المتصلة جيدا ،، سيجد ان تطبيق القائمة المتصلة ، اشمل من تطبيق المكدس باستخدام القائمة المتصلة .
فلا يوجد اي اضافات باستثناء الدالة top ،، وانما حذفنا العديد من الدوال ، وكذلك قمنا بتغيير بعض الاسماء ،
مثلا اسم الطبقة تم تغييره من LinkedList الى LinkedStack
وكذلك الدوال pop و push.

وبالنسبة للدالة top فهي تقوم بارجاع قيمة العقدة الاخيرة .


ثانيا : تطبيق الطابور Queues باستخدام القائمة المتصلة LinkedList
اعتقد انك تستطيع تخمين الكود الان .
نحتاج الى دالتين من القائمة المتصلة ، هما
دالة ادخال العناصر الى اول القائمة المتصلة addFirst
ودالة سحب العناصر من اخر القائمة المتصلة removeLast

وراح نطلق عليهم ، enQueue و deQueue


CODE:
// LinkedQueue , by Ahmad Essam.

#include <iostream>
using namespace std;

/////// Node Class //////

class Node
{
private:
int data;
Node *pNext;
Node *pPrevious;

public:
Node(int d):data(d),pNext(NULL),pPrevious(NULL){}

int getData()const{return data;}
void setData(int d){data=d;}

Node * getNext()const{return pNext;}
void setNext(Node *p){pNext=p;}

Node * getPrevious()const {return pPrevious;}
void setPrevious(Node *p){pPrevious=p;}

};

/////// LinkedQueue class ///////

class LinkedQueue
{
protected:
Node *pHead; //pointer to the first node
Node *pTail; //pointer to the last node
int nodeCounter; // count the number of nodes

Node * makeNode(int data); // make & return new node
void remove(Node *tmp); // remove node from linked list

public:
LinkedQueue();
~LinkedQueue();

// operations

void enQueue(int data);
void deQueue();
void destroyList();
int getSize()const{return nodeCounter;}
int top()const
{
if (pTail == NULL)
return 0;
return pTail->getData();
}
};


LinkedQueue::LinkedQueue():
pHead(NULL),pTail(NULL),nodeCounter(0)
{}


LinkedQueue::~LinkedQueue()
{
destroyList();
}




Node * LinkedQueue::makeNode(int data)
{
nodeCounter++;
return new Node(data);
}


void LinkedQueue::enQueue(int data)
{
// make new node
Node *pNew=makeNode(data);

// make the new node as the first node in the linked list

if( !pHead ) // if linkedlist is empty
pHead=pTail=pNew;

else // if there are nodes
{
pNew->setNext(pHead);
pHead->setPrevious(pNew);

pHead=pNew;
}
}


void LinkedQueue::remove(Node *tmp)
{
delete tmp;
nodeCounter--;
};


void LinkedQueue::deQueue()
{
if( !pHead )
{
cerr<<"\nThere is no any node to remove!!";
return ;
}

Node *pTmp=pTail;
pTail=pTail->getPrevious();

if(pTail)
pTail->setNext(NULL);

else
pTail=pHead=NULL;


remove(pTmp);
}



void LinkedQueue::destroyList()
{
Node *pTmp=pHead;
Node *pCur;

while( pTmp != NULL)
{
pCur=pTmp;
pTmp=pTmp->getNext();
remove(pCur);
}

}

/////// main //////////

int main()
{
LinkedQueue *queue=new LinkedQueue;

for(int i=0;i<5;i++)
queue->enQueue(2*i+1);


for(int i=0;i<5;i++)
{
cout<<"\ndeQueue: "<<queue->top();
queue->deQueue();

}

return 0;
}



لاحظ ان المشاكل القديمة اتحلت ،، هنا نستطيع ادخال اي عدد من العناصر

استخدام التوارث Inheritance لتسهيل التعديلات والتحديثات :

طبعا لاحظتوا ان تطبيق المكدس stack والطابور Queue باستخدام القائمة المتصلة ،،
افضل بكثير من التطبيق باستخدام المصفوفات بنوعيها العادية والديناميكية dynamic .

تطبيق المكدس و الطابور باستخدام القائمة المتصلة لايختلف كثيرا عن القائمة المتصلة نفسها ،
اللهم الا تغيير بسيط في الدوال.

الطريقة التي استخدمناها وهي اعادة كتابة القائمة المتصلة مع المكدس و الطابور غير محبذة !! لماذا ؟؟

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

لذلك سنستخدم تقنية التوارث !!
حيث سيقوم المكدس والطابور بوراثة جميع خصائص القائمة المتصلة ، ومن ثم نقوم بتعديل ما يلزم .

الان لو حصل تغيير في القائمة المتصلة ،، فلا يوجد داعي لتغيير المكدس ولا الطابور ،، لانهما سوف يرثان التعديلات

وسوف
نستخدم التوارث الخاص وليس العام ، لان التوارث العام سيجعل مستخدم المكدس
او الطابور لدية القدرة على استخدام اي دالة سواءا كانت داخل نفس الفئة او
الفئة الاب وهي LinkedList.

اما التوارث الخاص private inheritance فيسمنعك من استدعاء دالة ليست موجودة في الفئة المشتقة.

نشوف الاكواد كاملة ، وان شاء الله تكون واضحة ،،
وراح اقسمها الى ملفات متتعدة ،، لكي نقوم بعمل مكتبة خاصة بهياكل البيانات.

اولا ملفات الرأس Header Files

ملف Node.h

]CODE:
#ifndef NODE_H
#define NODE_H

class Node
{
private:
int data;
Node *pNext;
Node *pPrevious;

public:
Node(int d=0);

int getData()const;
void setData(int);

Node * getNext()const;
void setNext(Node *p);

Node * getPrevious()const;
void setPrevious(Node *p);

};

#endif




ملف LinkedList.h

CODE:
#ifndef LINKEDLIST_H
#define LINKEDLIST_H

#include "Node.h"

class LinkedList
{
protected:
Node *pHead; //pointer to the first node
Node *pTail; //pointer to the last node
int nodeCounter; // count the number of nodes

Node * makeNode(int data); // make & return new node
void remove(Node *tmp); // remove node from linked list

public:
LinkedList();
~LinkedList();

// operations

void addFirst(int data);
void addLast(int data);
void addBefore(int index,int data);

void removeFirst();
void removeLast();

void displayInOrder()const;
void displayInReverseOrder()const;

void destroyList();
int getSize()const{return nodeCounter;}
};

#endif



ملف LinkedStack.h

CODE:
#ifndef LINKEDSTACK_H
#define LINKEDSTACK_H

#include "LinkedList.h"

class LinkedStack:private LinkedList
{
public:
// operations
void push(int data);
void pop();
int top()const;
void display()const;
};

#endif



ملف LinkedQueue.h

CODE:
#ifndef LINKEDQUEUE_H
#define LINKEDQUEUE_H

#include "LinkedList.h"

class LinkedQueue :private LinkedList
{

public:
// operations
void enQueue(int data);
void deQueue();
int top()const;
void display()const;
};

#endif




ثانيا: ال Implementation :

ملف Node.cpp

CODE:
#include "Node.h"
#include <iostream>

Node::Node(int d):
data(d),pNext(NULL),pPrevious(NULL)
{}

int Node::getData()const
{
return data;
}

void Node::setData(int d)
{
data=d;
}


Node* Node:: getNext()const
{
return pNext;
}

void Node::setNext(Node *p)
{
pNext=p;
}


Node* Node::getPrevious()const
{
return pPrevious;
}


void Node::setPrevious(Node *p)
{
pPrevious=p;
}





ملف LinkedList.cpp

CODE:
#include "Node.h"
#include "LinkedList.h"
#include <iostream>

using std::cout;
using std::endl;
using std::cerr;

LinkedList::LinkedList():
pHead(NULL),pTail(NULL),nodeCounter(0)
{}


LinkedList::~LinkedList()
{
destroyList();
}


void LinkedList::displayInOrder()const
{
if( !pHead )
{
cout<<"\nNULL";
return ;
}

for(Node *cur=pHead;cur!=NULL;cur=cur->getNext())
cout<<cur->getData()<<" -> ";

cout<<"NULL"<<endl;
}

void LinkedList::displayInReverseOrder()const
{
if( !pHead )
{
cout<<"\nNULL";
return ;
}

for(Node *cur=pTail;cur!=NULL;cur=cur->getPrevious())
cout<<cur->getData()<<" -> ";

cout<<"NULL"<<endl;
}


Node * LinkedList::makeNode(int data)
{
nodeCounter++;
return new Node(data);
}


void LinkedList::addFirst(int data)
{
// make new node
Node *pNew=makeNode(data);

// make the new node as the first node in the linked list

if( !pHead ) // if linkedlist is empty
pHead=pTail=pNew;

else // if there are nodes
{
pNew->setNext(pHead);
pHead->setPrevious(pNew);

pHead=pNew;
}
}


void LinkedList::addLast(int data)
{
// make new node
Node *pNew=makeNode(data);

// make the new node as the last node in the linked list

//if there is no node in the linked list , add node.
//otherwise move the new node to the last.

if( !pHead )
pHead=pTail=pNew;

else
{
pTail->setNext(pNew);
pNew->setPrevious(pTail);

pTail=pNew;
}
}



void LinkedList::addBefore(int index,int data)
{
// check the index to see if it's legal

if( index <1 || index > getSize() )
{
cerr<<"\nError: index is too hight/low ";
return;
}

if(index == 1)
{
addFirst(data);
return ;
}

// make new Node
Node *pNew=makeNode(data);
Node *pCur=pHead;

for(int i=1;i<index -1;i++,pCur=pCur->getNext());

pNew->setNext(pCur->getNext());
pCur->setNext(pNew);

}



void LinkedList::removeFirst()
{
if( !pHead )
{
cerr<<"\nThere is no any node to remove!!";
return ;
}

Node *pTmp=pHead;
pHead=pHead->getNext();

if(pHead)
pHead->setPrevious(NULL);
else
pHead=pTail=NULL;
remove(pTmp);

}


void LinkedList::remove(Node *tmp)
{
delete tmp;
nodeCounter--;
};


void LinkedList::removeLast()
{
if( !pHead )
{
cerr<<"\nThere is no any node to remove!!";
return ;
}

Node *pTmp=pTail;
pTail=pTail->getPrevious();

if(pTail)
pTail->setNext(NULL);
else
pHead=pTail=NULL;

remove(pTmp);
}



void LinkedList::destroyList()
{
Node *pTmp=pHead;
Node *pCur;

while( pTmp != NULL)
{
pCur=pTmp;
pTmp=pTmp->getNext();
remove(pCur);
}

}





ملف LinkedStack.cpp

CODE:
#include "LinkedStack.h"
#include <iostream>

int LinkedStack::top()const
{
if (pTail == NULL)
return 0;
return pTail->getData();
}


void LinkedStack::push(int data)
{
addLast(data);
}


void LinkedStack::pop()
{
removeLast();
}

void LinkedStack::display()const
{
displayInOrder();
}





ملف LinkedQueue.cpp

CODE:
#include "LinkedQueue.h"
#include <iostream>

int LinkedQueue::top()const
{
if (pTail == NULL)
return 0;
return pTail->getData();
}


void LinkedQueue::enQueue(int data)
{
addFirst(data);
}


void LinkedQueue::deQueue()
{
removeLast();
}

void LinkedQueue::display()const
{
displayInOrder();
}





ثالثا: ال Driver program

والمقصود به هو الملف الذي يحوي الدالة main
وراح اكتب ثلاثة نسخ ،،
الاولى تستخدم ال Linked List
والثانية تستخدم ال Stack
والثالثة تستخدم ال Queue

ملف linkedListDriverProgram.cpp :


CODE:
#include <iostream>
using namespace std;

#include "LinkedList.h"

int main()
{
LinkedList *list=new LinkedList;

for(int i=0;i<5;i++)
{
cout<<"\nadd "<<i+1<<" to list";
list->addLast(i+1);
}

cout<<"\nDisplay list\n";
list->displayInOrder();

cout<<"remove First element in the list\n";
list->removeFirst();

cout<<"add 300 to the last\n";
list->addLast(300);

cout<<"Display list\n";
list->displayInOrder();

cout<<"Display list in reverse\n";
list->displayInReverseOrder();

return 0;
}




ملف StackDriverProgram.cpp :

CODE:
#include <iostream>
using namespace std;

#include "LinkedStack.h"

int main()
{
LinkedStack *stack=new LinkedStack;

for(int i=0;i<5;i++)
{
cout<<"\npush "<<i+1<<" to stack";
stack->push(i+1);
}

cout<<"\nDisplay stack\n";
stack->display();

cout<<"pop two elements from the stack\n";
stack->pop();
stack->pop();

cout<<"push 300 to the stack\n";
stack->push(300);

cout<<"Display stack\n";
stack->display();


return 0;
}




ملف QueueDriverProgram.cpp :

CODE:
#include <iostream>
using namespace std;

#include "LinkedQueue.h"

int main()
{
LinkedQueue *queue=new LinkedQueue;

for(int i=0;i<5;i++)
{
cout<<"\nenqueue "<<i+1<<" to queue";
queue->enQueue(i+1);
}

cout<<"\nDisplay queue\n";
queue->display();

cout<<"dequeue two elements from queue\n";
queue->deQueue();
queue->deQueue();

cout<<"enqueue 300 to the queue\n";
queue->enQueue(300);

cout<<"Display queue\n";
queue->display();

return 0;
}



لترجمة البرنامج ،، اولا عليك انشاء مجلد جديد وليكن :dataStructures
وبعد ذلك قم بنسخ الاكواد ووضعها في ملفات .cpp كما هو موضح.
ولكن لا تستخدم الثلاث نسخ من ال driver program في ان واحد ، حتى لا يكون عندك ثلاث دوال main
وهذا خطأ .

ثم نفذ:
CODE:
g++ *.cpp



ولتشغيل البرنامج

CODE:
./a.out



واذا كنت تستخدم انظمة ويندوز فراجع ملفات ال help التي تاتي مع المترجم عن كيفية ترجمة عدة ملفات .

او استخدم المترجم g++ من خلال تنزيل الباكج MinGw


تاااااااااابع ،،