آموزش ساختمان داده قسمت هشتم
سلام عرض میکنم خدمت همه ی شما دوستان عزیز و ارجمند. روز طبیعت رو به همه ی شما عزیزان تبریک عرض میکنم و امید وارم شاد و پیروز و تندرست و سربلند باشید . ضیادید هستم با جلسه ی هشتم از سری آموزش های ساختمان داده ها در خدمت شما خواهم بود.
در جلسه ی گذشته مطالبی رو عنوان کردیم درباره ی صف های حلقوی و ارزشیابی عبارت و کمی هم درباره ی لیست های پیوندی صحبت کردیم . انشاءالله در این جلسه قصد داریم بحث پیرامون موضوع "لیست های پیوندی" رو ادامه بدیم .
همونطور که در جلسه ی گذشته صحبت کردیم ، لیست پیوندی، یکی از ساختار هایی هست که برای ذخیره سازی انواع داده ها در حافظه اصلی مورد استفاده قرار میگیره . اصولا یک لیست پیوندی دارای عناصری از حافظه ی پویا هست که لزوما در کنار هم قرار نگرفتن . به این عناصر اصطلاحا "رکورد" ، "گره" و "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 مورد دسترسی واقع شود
لیست های پیوندی معمولا میتونن به دو شکل یکطرفه و دوطرفه مورد استفاده قرار بگیرن و تعریف بشن. در لیست های پیوندی یکطرفه، در هرگره فقط یک فیلد اشاره گر هست که توی اونهم آدرس گره ی بعدی وجود داره.توی لیست های پیوندی دوطرفه هم توی هر گره دو فیلد اشاره گر وجود داره که یکی از اونها به گره ی بعدی و اون یکی هم به گره ی قبلی اشاره میکنه
لیست پیوندی یک طرفه ی خطی
لیست پیوندی دو طرفه ی خطی
اما دوستان یک مفهومی مشابه اون چیزی که درباره ی صف های معمولی و صف های حلقوی گفتیم ، درباره ی لیست های خطی و دوری هم برقرار هست . بنابراین میتونیم لیست های دوری یا لیست های حلقوی رو هم معرفی کنیم . این نوع لیست هم دو نوع یک طرفه و دو طرفه داره . درلیست حلقوی یا دوری یک طرفه ، اشاره گر گره ی آخر ، به گره ی اول اشاره میکنه و در لیست حلقوی دو طرفه هم اشاره گر سمت راست گره ی آخر به گره ی اول و اشاره گر سمت چپ گره ی اول به گره ی آخر اشاره خواهد کرد .
لیست حلقوی یا دوری یکطرفه
لیست حلقوی یا دوری دو طرفه
خب دوستان .. خسته نباشید ..
برای این جلسه کافیه .. انشاءالله در جلسه ی بعدی ، همین مباحث رو ادامه خواهیم داد انشاءالله
تا دیداری دیگر خدانگهدا
نظرات کاربران