لیست حلقوی

[lighting]

سلام به دوستان عزیز

لطفا تو نوشتن الگوریتم این برنامه کمکم کنید:

سوال: فرض کنید در یک لیست حلقوی به جای ادرس اولین گره ادرس اخرین گره نگهداری شود توابع لازم برای اعمال درج و حذف این لیست را تعریف کنید.
یه چیزایی ازش نوشتم ولی هر کاری می کنم درست در نمی اد

ممنون

 

[lighting]

برای این که بگیم ادرس اخرین گره رو نگهداری می کنه باید اشاره گر node اخر رو در نظر بگیریم بعد درج و خذفش مثل لیست حلقوی

می شه که ادرس اولین گره رو نگهداری می کنه؟؟؟؟؟؟؟؟؟؟

 

[the_king]

برای این که بگیم ادرس اخرین گره رو نگهداری می کنه باید اشاره گر node اخر رو در نظر بگیریم بعد درج و خذفش مثل لیست حلقوی

می شه که ادرس اولین گره رو نگهداری می کنه؟؟؟؟؟؟؟؟؟؟

در لیست حلقوی آخرین گره (rear) به اولین گره (front) اشاره می کنه، الگوریتم ها معمول بر این اساس اند که آدرس
اولین گره (front) را می دانید، اما حالا شما فرض را بر این قرار داده اید که آدرس آخرین گره (rear) را می دانیم،
خوب وقتی شما آدرس آخرین گره رو دارید و لیست هم حلقوی است پس گره بعدی اش همون گره ابتدای لیسته
(rear -> next)

هر جای الگوریتم از front استفاده شده بجایش از rear -> next استفاده کنید.
در ضمن موقعی که عنصری به ابتدای حلقه اضافه میشه یا از ابتدای حلقه حذف میشه یک بررسی خاص انجام میشه
چون مقدار front باید تغییر می کنه تا ابتدای حلقه را گم نکنیم. شما باید بجای این دو حالت خاص وضعیتی را بررسی
خواهید کرد که بخواهید به انتهای حلقه عنصری رو اضافه کنید یا از انتهای حلقه عنصری را حذف کنید چون rear با این
دو عملیات باید تغییر کنه.

 

[lighting]

اقا خیلی ممنون از توضیحتون یعنی این جا دیگه نیازی نیست یه الگوریتم جدا برای نگهداری ادرس اخرین گره نوشت فقط کافی الگوریتم های درج و حذف از انتهای لیست حلقوی رو نوشت (که الگوریتمش مثل درج و حذف از انتهای لیست پیوندی یک طرفه است) بعد فقط تمام front ها رو تبدیل به rear -> next کرد؟؟؟

 

[the_king]

اقا خیلی ممنون از توضیحتون یعنی این جا دیگه نیازی نیست یه الگوریتم جدا برای نگهداری ادرس اخرین گره نوشت فقط کافی الگوریتم های درج و حذف از انتهای لیست حلقوی رو نوشت (که الگوریتمش مثل درج و حذف از انتهای لیست پیوندی یک طرفه است) بعد فقط تمام front ها رو تبدیل به rear -> next کرد؟؟؟

بله، فقط دقت کنید که مقدار rear نگهداری میشه، اما هر موقع به start نیاز داشته باشید از rear -> next
استفاده می کنید، این معنی اش این نیست که برای نگهداری rear کدی نوشته نشه، هر جایی که آخرین عضو
حلقه رو حذف می کنید یا به انتهای حلقه عضوی اضافه می کنید مقدار rear جدید ثبت میشه.

 

[lighting]

این الگوریتم رو برای درج نوشتم درسته؟؟؟

[LEFT]void AddNode (node*last , elementtype item)
new p= getnode();
new p ->info=item
if(last==Null)
last=new p
new p->next=new p;
else
new p->next=last->next;
last->next=new p;
}
}[/LEFT]

 

[lighting]

این هم الگوریتم حذف درسته؟

voide Delete (node *pred)
node*p;
if (pred=null  OR rear-> next=rear->next->next)
return;
p=pred->next
pred->next=p->next
delete p;
}

 

[the_king]

این الگوریتم رو برای درج نوشتم درسته؟؟؟

[LEFT]void AddNode (node*last , elementtype item)
new p= getnode();
new p ->info=item
if(last==Null)
last=new p
new p->next=new p;
else
new p->next=last->next;
last->next=new p;
}
}[/LEFT]

درسته ولی توصیه می کنم بجای new p از new_p و بجای getnode از create_node یا new_node استفاده کنید.

این هم الگوریتم حذف درسته؟

voide Delete (node *pred)
node*p;
if (pred=null  OR rear-> next=rear->next->next)
return;
p=pred->next
pred->next=p->next
delete p;
}

یه ایرادی داره، شما می خواهید عضو بعد از pred رو حذف کنید، درسته؟ حالا اگر اون عضو بعدی همون last
باشه شما باید مقدار جدید last رو مشخص کنید، وگرنه موقعیت انتهای حلقه رو از دست خواهید داد.

if (p=last)
    last = pred;

 

[lighting]

ممنون از نکته هاتون
می تونم توی الگوریتمی که برای درج نوشتم اینجوری هم بنویسم

new *p=new *node

بعد از اون جای تمام new p ها بنویسم new *p

 

[lighting]

اها یعنی باید توی الگوریتم این if رو هم بنویسم تا موقعیت انتهای حلقه از دست نره؟

 

[the_king]

اها یعنی باید توی الگوریتم این if رو هم بنویسم تا موقعیت انتهای حلقه از دست نره؟

بله، هر زمانی که به هر علتی موقعیت آخرین عضو حلقه تغییر کرد باید موقعیت جدید رو در اون متغیر (last یا rear)
ثبت کنید.

 

[lighting]

ممنون از نکته هاتون
می تونم توی الگوریتمی که برای درج نوشتم اینجوری هم بنویسم

 new *p=new *node

بعد از اون جای تمام new p ها بنویسم new *p

 

[the_king]

ممنون از نکته هاتون
می تونم توی الگوریتمی که برای درج نوشتم اینجوری هم بنویسم

 new *p=new *node

بعد از اون جای تمام new p ها بنویسم new *p

اینطوری اون کسی رو که کد رو مطالعه می کنه بدتر سر در گم می کنید، وقتی new رو با فاصله جدا می نویسید
به ظاهر شبیه کلمه کلیدی میاد تا بخشی از اسم متغیر، اسم متغیر ها نباید شامل کاراکتر فاصله باشه.
به همین جهت توصیه کردم که از new_p استفاده کنید. اون * هم برای اشاره گر در زبان برنامه نویسی و عملگر ضرب
بکار میره، در اسم متغیر ننویسیدش، در ضمن وجودش در الگوریتم ضروری نیست چون شما دارید شبه کد می نویسید.

 

[asenat76]

سلام ببخشید می تونید تکه کدی برای نمایش لیست حلقوی بزارید ممنون.