time1

Linked List القوائم المتصلة

20 ردود في هذا الموضوع

Linked List

القوائم المتصلة :

هي نوع من هياكل البيانات وتتألف من مجموعة من الخلايا المترابطة بينها وكل عنصر فيها يسمى عقدة وهذه العقدة فيها حقلين , الحقل الأول يستخدم لتسجيل القيم , اما الحقل الثاني فهو مؤشر يؤشر لعنوان العقدة التالية او السابقة او NULL في حال كانت هذه الحلقة هي الحلقة الاخيرة .

post-82612-1203740576_thumb.jpg

* يجب التنويه بأنه لا يشترط او ليس من الضروري ان تكون العقد مرتبة بشكل متتالي في الذاكرة , فهي تكون مبعثرة في الذاكرة , والسبب في ذلك :

ان من يقوم بعملية الحجز في الذاكرة هو جهاز الحاسب وليس المستخدم , لكنها متصلة في ما بينها عن طريق المؤشرات كما يظهر بالشكل :

post-82612-1203740705_thumb.jpg

انشاء تركيبة القائمة المتصلة :

كما قلنا بان القائمة المتصلة هي عبارة عن سلسلة من الحلقات وتسمى كل حلقة عقدة ( 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

post-82612-1203740767_thumb.jpg

الان لدينا داخل العنوان first ثلاثة عناصر :

num ونساويها بـالوسيط n

name ونساويها بالوسيط name

next وهو المؤشر الذي يؤشر للحلقة التاليه ونساويه بـ NULL

2- الاضافة إلى نهاية القائمة :

انتهينا من النقطة رقم 1 ولدينا الان حلقة ومؤشرها يؤشر إلى NULL كما هو بالصورة :

post-82612-1203740826_thumb.jpg

خطوات اضافة حلقة من النهاية :

1- ننشأ حلقة جديدة ونجعلها تؤشر إلى NULL

post-82612-1203740871_thumb.jpg

2 - نجعل العقدة الاولى بدلا من ان تأشر إلى NULL تأشر إلى العقدة الجديدة :

post-82612-1203741095_thumb.jpg

دعونا نرى هذا الكود :

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 , الان لنفترض فعلا وجود هذه القائمة كما هو موضح في الصورة

post-82612-1203741121_thumb.jpg

سنقول اولا : p=first

first هو عنوان القائمة اي عنوان اول عقدة في القائمة , والان اصبح المتغير p يحمل هذا العنوان .

الان نقول :

	while(p->next!=NULL)
{
p=p->next;
}

كرر طالما ان next لا يساوي NULL , سنطبق هذا المثال على القائمة التي افترضناها :

post-82612-1203741142_thumb.jpg

الان عندما نقول :

p=p->next

هذا يعني ان p قد تقدم خطوة إلى الامام واصبح الان بالعقدة التاليه .

post-82612-1203741165_thumb.jpg

هل p->next لاتساوي NULL ؟

نعم لاتساوي NULL لانها تساوي عنوان العقدة 3 اي انها تؤشر للعقدة 3

p=p->next

post-82612-1203741188_thumb.jpg

هل 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 اي عنوان اول عقدة بالقائمة اي عنوان بداية القائمة نفسها

post-82612-1203741212_thumb.jpg

2- temp يقوم بانشاء عقدة جديدة ويجعلها تؤشر لاول عقدة بالقائمة اي q

post-82612-1203741232_thumb.jpg

4- الاضافة من الوسط :

تكمن الفكرة بأن نعثر عن قيمة تدل على العقدة التي نريد ان نضيف بعدها , مثل ان نبحث عن العقدة التي بها رقم الطالب 50 ونضيف بينها وبين العقدة التي تليها عقدة جديدة ولاتمام ذلك نقول :

1- لدينا قائمة من العقد , نبحث عن العقدة التي نريد ان نضيف بعدها .

post-82612-1203741256_thumb.jpg

2- ننشأ عقدة جديدة ونجعلها تؤشر إلى العقدة التي تلي العقدة المقصودة.

post-82612-1203741300_thumb.jpg

3- نجعل العقدة المقصودة تؤشر إلى العقدة الجديدة .

post-82612-1203741321_thumb.jpg

الان دعونا نرى هذه الدالة :

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-نجعل العقدة المقصودة تؤشر إلى العقدة الجديدة .

إلى هنا اكون قد انتهيت من درسي الاول والذي هو جزء من بحث قدمته عن تراكيب البيانات :

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

تم تعديل بواسطه time1
4

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه

أخي Time الصور لا تعمل ، والموقع يعرض رساله :

Bandwidth Limit Exceeded

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

http://www.arabteam2000-forum.com/index.php?showtopic=126887

وفي انتظار التكمله ، جزاك الله خيرا

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه

تعمل عندي !

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه

شرح جميل جدا اخي time ..

ولكن بالفعل انا ولا صورة ضهرت عندي .. تاكد من ذلك لكي يستفيد منها بقية الاعضاء ..

تحياتي العطرة ....

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه

تم تعديل الصور ورفعها على السيرفر

وسأكمل باقي الدروس , تحياتي

تحياتي

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه

السلام عليكم

لم أحب القوائم المتصلة أنا أعربها الحلقات المتسلسلة

لدي مجموعة مقالات كتبتها عنها لكنها بالجافا وكتبتها لفصل تراكيب البيانات لأكاديمية شباب IT وعلى مدونتي

لن أضع وصلة لكي لا يقتلني الأخ عبد العزيز

لكني فقط أحببت التنويه إلى التعريب

بالمناسبة أنا لم أقرأ الدرس لكن بالتأكيد منظره مغر جداً

كما عهدناك أخ time1 مبدع دائماً

تحياتي

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه

شكرا جزيلا ومستنيين البحث داخل القائمة المتصلة على ناااااااااااااااااااااااااااااااار

Searching in Linked Lists is Very important Pleeeeeeeeeeeeeeeaaase

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه

تابع اخي الــــدرس الثــــاني يحتوي على آلية البحث لكن لم اتطرق للبحث نفسه وانما تطرقت للتعديل وهي شبيهه بالبحث , فالتعديل يقوم بالبحث عن العقدة المقصودة وتعديل محتواها .

تحياتي .. .

1

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه

UP

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه

بســم الله الـرحمــن الرحيــم

شكراً لك اخي الكريم و جزاك الله خيرا ووفقك :lol:

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه

السلام عليكــم ورحمـة الله وبركاتــه ،،

شكرا كتييييير اخي time1

الشرح واضح ومفهوم وارجوا ان تكمل لنا الشرح باقرب وقت

وفقك الله ، ;)

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه

استاذي الفاضل

شكرا على الشرح الجميل

وبعد اذنك ممنكن طلب

بدي شرح انشاء القائمة وعليه مثال لو سمحت وشكرا جزيلا

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه

معلش سؤال تاني

اسفة تعبتك

لو تعرف شيء عن ( تمثيل القوائم بالمصفوفات الاحادية # اضافة قيم جديدة الى المصفوفات الاحادية # حذف القيم من المصفوفات الاحادية )

وشكرا جزيلا

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه

رجاء ساعدوني في موضوعي رفع الله قدركم

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه

onm ,, السؤال غير واضح

لكن هل هذا ماتعنيه ؟

class LLA
{
public:
LLA();
void AddFirst();
void AddLast();
void Display();
private:
int *Array;
int Size;
};
LLA::LLA()
{Array=NULL;Size=0;}
void LLA::AddFirst()
{
int x;
cout<<"Enter node data:"<<endl;
cin>> x;

int *p=new int[Size+1];
p[0]=x;
for(int i=1;i<Size+1;i++)
p[i]=Array[i-1];

delete []Array;
Array=p;
Size++;

}
void LLA::AddLast()
{
int x;
cout<<"Enter node data:"<<endl;
cin>> x;


int *p=new int[Size+1];
p[Size]=x;
for(int i=0;i<Size;i++)
p[i]=Array[i];

delete []Array;
Array=p;
Size++;

}

void LLA::Display()
{
cout<<"List Size:"<<Size<<endl;
cout<<"List Data:"<<endl;
for(int i=0;i<Size;i++)
cout<<"node "<<i<<": "<<Array[i]<<endl;
cout<<"\n\n";
}




int main()
{
LLA a;
int c;
again: cout<<"WHAT DO YOU WANT TO DO? "<<endl
<<"\t*******************************************\n";

cout<<"\t1- Insert - Last:"<<endl;
cout<<"\t2- Insert - First:"<<endl;
cout<<"\t3- Display List:"<<endl
<<"\t*******************************************\n";
cin>>c;
switch(c)
{
case 1:
a.AddLast();
goto again;
break;
case 2:
a.AddFirst();
goto again;
break;
case 3:
a.Display();
goto again;
break;
default:
goto again;
break;
}


return 0;
}

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
onm ,, السؤال غير واضح

لكن هل هذا ماتعنيه ؟

class LLA
{
public:
LLA();
void AddFirst();
void AddLast();
void Display();
private:
int *Array;
int Size;
};
LLA::LLA()
{Array=NULL;Size=0;}
void LLA::AddFirst()
{
int x;
cout<<"Enter node data:"<<endl;
cin>> x;

int *p=new int[Size+1];
p[0]=x;
for(int i=1;i<Size+1;i++)
p[i]=Array[i-1];

delete []Array;
Array=p;
Size++;

}
void LLA::AddLast()
{
int x;
cout<<"Enter node data:"<<endl;
cin>> x;


int *p=new int[Size+1];
p[Size]=x;
for(int i=0;i<Size;i++)
p[i]=Array[i];

delete []Array;
Array=p;
Size++;

}

void LLA::Display()
{
cout<<"List Size:"<<Size<<endl;
cout<<"List Data:"<<endl;
for(int i=0;i<Size;i++)
cout<<"node "<<i<<": "<<Array[i]<<endl;
cout<<"\n\n";
}




int main()
{
LLA a;
int c;
again: cout<<"WHAT DO YOU WANT TO DO? "<<endl
<<"\t*******************************************\n";

cout<<"\t1- Insert - Last:"<<endl;
cout<<"\t2- Insert - First:"<<endl;
cout<<"\t3- Display List:"<<endl
<<"\t*******************************************\n";
cin>>c;
switch(c)
{
case 1:
a.AddLast();
goto again;
break;
case 2:
a.AddFirst();
goto again;
break;
case 3:
a.Display();
goto again;
break;
default:
goto again;
break;
}


return 0;
}

شكرا كتير على المثال

بس لو تحطلي سؤال على هذا المثال

وشكرا

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه

onm :

هذا مثال Class يحاكي بعض العمليات التي تتم على القوائم المتصلة ( الاضافة من الاول ومن الاخير وطباعة العناصر ) على مصفوفة احادية .

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه

شكرا جزيلا

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
زوار
This topic is now closed to further replies.

  • يستعرض القسم حالياً   0 members

    لا يوجد أعضاء مسجلين يشاهدون هذه الصفحة .