لیست پیوندی دو طرفه – doubly linked list با ++C

DoubleLinkedLists

مدت ها پیش پستی در مورد لیست پیوندی یک طرفه  گذاشتم که در آن نحوه ی ایجاد  لینک لیست یک طرفه را همراه با اضافه کردن گره ، حذف گره و همین طور جست و جوی یک گره را بررسی کردیم . در این پست ما به لیست پیوندی دوطرفه همان لیست دو پیوندی می پردازیم که ارتقاع یافته لیست پیوندی یک طرفه است.

اگر با لینک لیست یک طرفه ( لیست یک پیوندی) آشنا نیستید ابتدا این پست را مطالعه نمایید :    آموزش لیست پیوندی linked list در برنامه نویسی .

نکته : این کد برای اینکه جنبه ی آموزشی دارد به ساده ترین شکل نوشته شده است  – خودتان می توانید آن را با استفاده از template باز نویسی کنید و یک  کلاس کلی برای خود بسازید.

لینک لیست دوطرفه دارای دو لینک است . یک لینک به گره بعدی خود و لینک دیگر به گره ی قبلی اشاره دارد . مانند شکل زیر :

Doubly linked List.svg

همین طور که در شکل بالا می بینید هر گره دارای دو اشارگر است . ساختار کلی یک گره را در شکل زیر می بینید:

 

structure

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

لیست پیوندی که من پیاده سازی کرده ام از دو کلاس تشکیل شده است , یکی کلاس  node و دیگری کلاس  doubled Linked List .اولی کلاسی برای  گره ها در لیست است و دومی کلاسی است برای خود لیست پیوندی .

کلاس node :

دارای سه ویژگی زیر است :

int Data : این ویژگی همان مقدار درون گره است. که می توان بر حسب نیاز تغییرش داد و گره هایی با مقادیر مورد نیاز خود بسازید.

node *next: اشاره گری به گره ی بعدی است و اگر گره ی بعدی وجود نداشت به NULL اشاره می کند.

node *pre : اشاره گری به گره ی قبلی است و اگر گره ی قبلی وجود نداشت به NULL اشاره می کند.

توابع کلاس node :

تابع زیر سازنده ی کلاس node است که مقدار Data را برابر با صفر می کند و اشارگرها را NULL میکند.

تابع زیر سازنده ی دیگر کلاس node است که یک عدد به عنوان آرگومان می گیرد و آن را در Data می گذارد و بعد اشاره گر ها را NULL می کند.

تابع زیر یک گره را را در ترمینال چاپ می کند.

 

کلاس doubled Linked List :

این کلاس دارای سه ویژگی زیر است.

int numberOfNode : تعداد گره ها در  لیست پیوندی دو طرفه را نشان می دهد.

node * first : اشاره گری است که به گره ی اول لیست پیوندی اشاره می کند.

node * last : اشاره گری است که به گره ی آخر لیست پیوندی اشاره می کند.

توابع کلاس لیست دو پیوندی :

تابع زیر سازنده این کلاس است که اعداد گره ها موجود در لیست پیوندی را برابر صفر قرار می دهد و اشاره گر به اول و آخر لیست را برابر NULL می کند.

تابع زیر تمام گره های یک لیست پیوندی را از اول تا آخر در ترمینال چاپ می کند.

تابع زیر یه عدد می گیرد و یک گره جدید با اون عد ایجاد می کندو گره ی جدید را به ته لیست اضافه می کند.

تابع زیر یک مقدار می گیرد و از اول لیست شروع به گشتن می کند تا آخر لیست در صورتی که گره ای با آن  Data  وجود داشته باشد یک اشاره گر به آن برمی گرداند در غیر این صورت NULL بر می گرداند.

تابع زیر یک عدد را می گیرد و با استفاده از تابع سرچ بالا آن را در لیست پیوندی پیدا می کند . و بعد از پیدا کردن آن را حذف می کند . حذف کردن به این صورت است که اشاره گر های next , pre گره را NULL می کنیم و همین طور اشاره گره هایی که سایر گره ها به گره ی مورد نظر دارند را اصلاح می کنیم و بعد آن گره را از حافظه پاک می کنیم. و همین طور یکی از تعداد گره ها کم می کنیم . و در آخر اگر نودی که حذف کردیم اولین یا آخرین نود بود اشاره گر به اول یا آخر لیست را اصلاح می کنیم.

تابع زیر دو اشاره گر به گره ها را می گیرد و با اصلاح اشاره گر هایی که به دو گره وارد یا خارج می شود جای آن دو را در لیست پیوندی دو طرفه عوض می کند.

مرتب سازی لیست پیوندیsort linked list ): تابع زیر با استفاده از تابع swap بالا لینک لیست را بر اساس Data سورت می کند.

 

و در آخر هم کد کلی  لیست پیوندی دوطرفه – doubled linked list را همراه تابع main آورده ام که برای نمونه در تابع main یک لینک لیست ساخته ام و توابع مختلف را روی آن تست کرده ام .

 

 

نکته :  البته خود سی پلاس پلاس یک کتابخانه برای لیست دو پیوندی دارد که با اضافه کردن آن به برنامه تان می توانید از آن استفاده کنید:

اگر کدی بهتر از این کد دارید یا این کد را با زبان دیگری نوشته اید آن را در اختیار ما قرار دهید تا به این پست اضافه اش کنیم.

Digg This
Reddit This
Stumble Now!
Buzz This
Vote on DZone
Share on Facebook
Bookmark this on Delicious
Kick It on DotNetKicks.com
Shout it
Share on LinkedIn
Bookmark this on Technorati
Post on Twitter
Google Buzz (aka. Google Reader)

۹ دیدگاه

نظر خود را بنویسید.

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *