لیست پیوندی

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


لیست پیوندی یا linked list:

در لیست پیوندی هر عنصر آدرس عنصر بعدی را در خود نگه می دارد نحوه دسترسی آن به این صورت است که اگر بخواهیم به عنصر سوم برسیم ابتدا به عنصر اول و سپس به عنصر دوم و بعد به عنصر سوم خواهیم رسید. لیست پیوندی ساختمانی است که یکی از اجزایش اشاره گری از همان ساختمان است. به عنصر اول لیست، سر لیست یا head و به عنصر آخر لیست tail می گویند. اشاره گر عنصر آخر لیست به null اشاره می کند.

L1.PNG

typeof struct student{

char name[20];

char family[20];

int id;

float avg;

struct student *next;

}std;

آدرس شروع لیست را درون یک اشاره گر به نام head می ریزیم و آن را دستکاری نمی کنیم.

head = آدرس اولین عنصر

آدرس دومین عنصر = head->next

عنصر دوم = آدرس سومین عنصر->next

حذف یک رکورد خاص:

ابتدا باید بدانیم که رکورد در کجای لیست قرار دارد. یک رکورد در یکی از موقعیت های زیر است:

1- اولین عنصر لیست یا head باشد. باید head را یک عنصر به جلو ببریم.

2- لیست فقط یک عنصر داشته باشد که ابتدا و انتهای لیست همان باشد. در این حالت head و tail هر دو به null اشاره می کند.

3- یکی از عناصر وسط لیست باشد. در این حالت باید عنصر قبلی را به عنصر بعدی که بعد از عنصر مورد نظر است وصل کنیم.

4- آخرین عنصر لیست یا tail باشد. در این حالت باید tail را یک عنصر قبل متصل کنیم.

مثال: تابعی بنویسید که رکورد خاص را به عنوان ورودی گرفته و رکورد متناظر را در لیست پیوندی حذف کند.


#include <iostream>
#include <conio.h>

typeof struct{
char name[20];
char family[20];
int id;
float avg;
struct student * next;
}std;

int delete(std tmp)
 {
  int i=0;
  std * previos = null;
  std * temp = head;
  if (head == null)
   return i;
  else
  {
   while (temp != null)
   {
    if (strcmp(temp->family,tmp.family)== 0)
     {
      if (temp == head && temp == tail)
       head = tail = null;
     }
     else if (temp == head)
       head = head->next;
     else if (temp == tail)
      {
       tail = previous;
       previous->next = null;
      }
     else
       previous->next = temp-> next;
     delete temp;
     i=1;
     break;
   }
    previous = temp;
    temp = temp->next;
  }
  return i;
 }

جستجو کردن در لیست:

مثال: تابعی بنویسید که فامیلی را به عنوان ورودی گرفته و درون لیست جستجو می کند و آدرس عنصری که فامیل آن با فامیل رکورد ورودی مساوی باشد را برگرداند.


#include <iostream>
#include <conio.h>
std * find(char * family)
 {
  std * temp = head;
  while (temp != null)
  {
   if(strcmp(family,temp->family)==0)
    break;
   temp = temp-> next;
  }
  return temp;
 }