آموزش ساختمان داده قسمت هشتم

1395/1/23 سعید ضیادید 3115

سلام عرض میکنم خدمت همه ی شما دوستان عزیز و ارجمند. روز طبیعت رو به همه ی شما عزیزان تبریک عرض میکنم و امید وارم شاد و پیروز و تندرست و سربلند باشید . ضیادید هستم با جلسه ی هشتم از سری آموزش های ساختمان داده ها در خدمت شما خواهم بود.
در جلسه ی گذشته مطالبی رو عنوان کردیم درباره ی صف های حلقوی و ارزشیابی عبارت و کمی هم درباره ی لیست های پیوندی صحبت کردیم . انشاءالله در این جلسه قصد داریم بحث پیرامون موضوع "لیست های پیوندی" رو ادامه بدیم .
همونطور که در جلسه ی گذشته صحبت کردیم ، لیست  پیوندی، یکی از ساختار هایی هست که برای ذخیره سازی انواع داده ها در حافظه اصلی مورد استفاده قرار میگیره . اصولا یک لیست پیوندی دارای عناصری از حافظه ی پویا  هست که لزوما در کنار هم قرار نگرفتن . به این عناصر اصطلاحا "رکورد" ، "گره" و "node" هم میگن و دارای حداقل 2 فیلد یا قسمت هستن که یک قسمت مربوط به "داده" هست و یک قسمت دیگه هم مربوط به "اشاره گر " خواهد بود . پس می تونیم بگیم که قطعا دو فیلد "data" و “link” رو داریم و اشاره گر هم کارش نگهداری آدرس عنصر بعدی از لیست پیوندی هست . در این مبحث دو تا تابع هم بسیار مهم هستن که معرفیشون میکنیم . یکی تابع "head" هست و دیگری تابع "tail"  خواهد بود .

Head()
Tail()

 تابعی که اشاره گر به گره ی بعد از گره ی اول لیست رو برمیگردونه.
شکل زیر هم میتونه یک شکل کلی برای هر گره در یک زبان مثل C به حساب بیاد :

ساختمان داده

در این صورت برای پیاده سازیش در زبان C خواهیم داشت

typedef     struct  node  *list
typedef     struct  node  {
   int  Data ;
   list  link ;
} ;
.
.
.
struct      node     *p;
.
.
.
p= malloc  (sizeof (struct node))

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

if     Avail=Null  then  write 'overflow' and exit

توضیح قسمت بالا :
اگر فضای خالی در heap وجود نداشته باشد ، Avail برابر با Null شده و پیغام overflow ظاهر می شود . در غیر این صورت به خط بعدی می رویم

p=Avail , Avail=link(Avail)

توضیح قسمت بالا:
اگر فضای خالی در Heap وجود داشته باشد ، Avail به عنوان یک گره ی آزاد در اختیار p قرار می گیرد . در این حالت گره ی مورد نظر می تواند توسط p مورد دسترسی واقع شود

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

آموزش ساختمان داده


لیست پیوندی یک طرفه ی خطی

آمزوش ساختمان داده


لیست پیوندی دو طرفه ی خطی


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

آموزش ساختمان داده


لیست حلقوی یا دوری یکطرفه

آموزش ساختمان داده

لیست حلقوی یا دوری دو طرفه

آموزش ساختمان داده

خب دوستان .. خسته نباشید ..
برای این جلسه کافیه .. انشاءالله در جلسه ی بعدی ، همین مباحث رو ادامه خواهیم داد انشاءالله
تا دیداری دیگر خدانگهدار

کلمات کلیدی