پاورپوینت لیست پیوندی

بخشی از پاورپوینت

اسلاید 1 :

لیست پیوندی

اسلاید 2 :

اضافه کردن يک گره به انتهاي ليست پيوندي

void attach(list_pointer first, list_pointer last, List_pointer newnode)
{
if(first==0) first=last=newnode;
else
{
last->link=newnode;
last=newnode;
}
}
عمليات روي ليست هاي پيوندي

فرض مي کنيم عضو داده اي last وجود دارد که به گره آخر ليست پيوندي اشاره مي کند

اسلاید 3 :

معکوس کردن ليست پيوندي
void Invert(list_pointer first)
{
list_pointer p=first, q=0, r=0; //q trails p
while( p) {
r=q; q=p; //r trails q
p=p->link; //p moves to next node
q->link=r; //link q to preceding node
}
first =q;
}
عمليات روي ليست هاي پيوندي

براي ليست به طول m زمان اجرا o(m)

اسلاید 4 :

اتصال دو زنجير
void Concatenate(list_pointer first_a, list_pointer first_b)
{
if (!first_a) { first_a=first_b; return;}
if (first_b) {
for (list_pointer p=first_a; p->link; p=p->link); //no body
p->link=first_b;
}
}

زمان اجرا بر حسب طول زنجير اول خطي است

اسلاید 5 :

حال اضافه/حذف از سمت چپ (انديس صفر) متفاوت با حذف و اضافه کردن بقيه نودها نيست و کد حذف/ اضافه ساده تر مي شود.

زنجير با گره سر

اسلاید 6 :

زنجير خالي با گره سر
headerNode
NULL

اسلاید 7 :

براي بررسي اينکه ايا اشاره گر current به گره آخر ليست دايره اي اشاره مي کند به جاي مقايسه (current->link==0) مقايسه ي (current->link==first) انجام مي شود.
الگوريتم هاي حذف/ اضافه کردن از/ به ليست دايره اي بايد تضمين کند که فيلد اشاره گر گره آخر به گره اول ليست اشاره کند.

ليست دايره اي

اسلاید 8 :

مي خواهيم گره جديدي به اول ليست بالا اضافه کنيم
بايد اشاره گر گره آخر (گره اي که حاوي e است) را تغيير دهيم.
بايد تا پيدا نشدن گره آخر در طول ليست حرکت کنيم.

اسلاید 9 :

هنگامي که از گره سر استفاده نميکنيم بهتر است اشارهگر دسترسي به ليست دايرهاي به جاي گره اول به گره آخر ليست اشاره کند.
در اينصورت اضافه کردن يک گره در اول و يا در آخر ليست دايرهاي در مدت زمان ثابتي انجام مي شود.

اسلاید 10 :

اضافه کردن گره اي که x به آن اشاره مي کند در اول ليست
void InsertFront(list_pointer last, list_pointer x)
// insert the node pointed at by x at the front of the circular list
// last points to the last node in the list
{
if (!last) { // empty list
last=x; x->link=x;
}
else {
x->link=last->link; last->link=x;
}
}

زمان اجرا O(1) است

اسلاید 11 :

اضافه کردن گره اي که x به آن اشاره مي کند در انتهاي ليست
void InsertRear(list_pointer last, list_pointer x)
// insert the node pointed at by x at the rear of the circular list
// last points to the last node in the list
{
if (!last) { // empty list
last=x; x->link=x;
} else {
x->link=last->link; last->link=x;
last=x;
}
}
زمان اجرا O(1) است
تفاوت با کد قبلي