آموزش جامع لیست های پیوندی :: تک بست

آموزش جامع لیست های پیوندی

خب دوستان در دوره آموزش زبان سی با مفهوم ساختارها (structure) آشنا شدید. در اینجا قصد داریم شما را با یکی از کاربردهای بسیار جالب ساختارها و اشاره گرها (Pointer) که عموما در درس ساختمان های داده مطرح میشود،آشنا کنیم.

با ما در آموزش لیست های پیوندی (Linked lists) همراه باشید.

مقدمه )

آموختیم که میتوانیم با استفاده از ساختارها نوع داده جدیدی را با ترکیب چند نوع داده موجود مانند اعداد صحیح یا رشته ها ایجاد کنیم :

__________________

| int a |

| char s |

__________________

حالا فرض کنید دو نمونه از این نوع داده درست کنیم مثلا :

__________________

| int a |

| char s |

__________________

| int a |

| char s |

__________________

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

مفهوم اصلی لیست های پیوندی )

به نظر شما برای پیوند این دو بسته به همدیگر باید چه کار کنیم؟
برای اتصال این دو بسته , به ساختار اصلی مراجعه میکنیم و یک اشاره گر تعریف میکنیم , اما یک لحظه صبر کنید! در بخش اشاره گر ها دیدیم که برای تعریف یک اشاره گر به یک متغیر باید نوع آن متغیر را برای کامپایلر مشخص کنیم. مثلا :


int* p;

یعنی قصد داریم به یک متغیر از نوع عدد صحیح (integer) اشاره کنیم.

خوب حالا که میخواهیم در این بسته ها اشاره گری به دیگری داشته باشیم و هر دوی این بسته ها از نوع این ساختار جدید هستند چه؟
احتمالا حدس زدید که باید در این ساختار اشاره گری به نوع همان ساختار داشته باشیم! اگر متوجه نشدید به کد زیر توجه کنید:

struct box 
{
         int a ;
         int b ;
         struct box *link ;
} ;

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

با تعریف این اشاره گر و اشاره دادن آن(!) به بسته دیگر , بسته های ما به شکل زیر در می آیند :

------------------ ----------------

| int a | | int a |

| char s | ------------ > | char s |

| box *p | | box *p |

------------------- ----------------

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

قطعا اول کار باید یک ساختار درست کنیم :


struct node 
{
         int data ;
         struct node *link ;
};

همونطور که توضیح دادم اون اشاره گر (*link) برای پیوند گره ها ایجاد شد.
خوب چون حال نداریم (!) همین ابتدای کار با استفاده از typedef اسم ساختار را کوتاه میکنیم :


typedef struct node 
{
         int data ; 
         struct node *link ;
} node;

در لیست پیوندی گره ها با استفاده از اشاره گر به یکدیگر متصل اند اما گره اول چطور؟ باید یک اشاره گر به گره اول هم ایجاد کنیم:


node *start = NULL ;

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


start = (node*) malloc (sizeof(node)) ;

حالا داریم به گره اول اشاره میکنیم. این گره چی داشت؟ بله یک عدد صحیح و یک اشاره گر :


start -> data = 2 ; 

start -> link = NULL ;

دقت کنید که چون با اشاره گر ها کار میکنیم از علامت "<- " استفاده میکنیم و همچنین فعلا فرض کردیم که این گره , آخرین گره است (NULL). حالا گره بعدی :


start->link = (node*) malloc (sizeof(node)) ;
start->link ->data = 3 ;
start -> link -> link = NULL ;

همینطور که متوجه شدید این روش کاربردی نیست چرا که اگر تعداد گره ها زیاد باشد , کار اضافه کردن گره ها به صورت دستی عملا غیر ممکن میشود. پس باید برای این کار یک تابع در نظر بگیریم. اما برای این کار احتیاج داریم که به نحوی لیست پیوندی را پیمایش کنیم :


node *current  = start ;
while (current->link != NULL)
{
      current = current -> link ;
}

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


void push (int num)
{
      if (start == NULL) // اگر گره اول ایجاد نشده بود
     {
         start = (node *) malloc (sizeof(node)) ;
         start->data = num ;
         start->link = NULL ;
     }
     else // برای گره های 2 به بعد 
     {
         node *current = start ; 
         while (current->link != NULL)
         {
             current = current->link ; //پیمایش تا آخرین گره 
          }
         current->link = (node*) malloc (sizeof(node));   // یک گره بعد از آخرین گره اضافه میکنیم
         current->link->data = num ;
         current->link -> link = NULL ;
      }
}

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

مثال 1 ) تابع پاک کردن گره از لیست پیوندی :
برای پاک کردن یک گره باید سه حالت را در نظر بگیریم:

1 – گره مورد نظر اولین گره باشد.
2 – گره ما آخرین گره باشد.
3 – هیچ یک از دو مورد بالا رخ ندهد.

تابع شماره ی گره را میگیرد و آن را پاک میکند (دقت کنید که ما از 1 شماره گذاری کردیم) :


void delete (int num)
{
      int i ;
      if (num ==1) // گره اول
     {
         node* temp = start ; // آدرس گره اول را ذخیره میکنیم
         start = start -> link ; // ارتباط با گره اول از بین میرود
         free (temp) ; // گره اول را از حافظه آزاد میکنیم
     }
     else   // گره دو به بعد 
   {   
        node *current = start ;
        for (i = 1 ; i <(num -1) ; i++)
        {
           current = current->link ;
        } 
       if (current->link->link == NULL) //گره آخر
       {
            free (current->link) ;
            current -> link = NULL ;
       }
       else    // گره وسط
       {
          node* temp = current -> link ;
          current->link = current->link->link ;
          free (temp) ;
         }
     }
}

دقت کنید که بعد از حذف یک گره از لیست آن گره در حافظه باقی می ماند پس بهتر است آن را آزاد کنیم.

مثال 2 ) اضافه کردن به ابتدای لیست پیوندی :


void add_beginning (int a)
{
    node *temp = (node *) malloc (sizeof(node)) ;
    temp -> data = a ;
    temp -> link = start ;
    start = temp ; 
}

دقت کنید که یک گره جدید ساختیم و اول گفتیم گره جدید به جایی که اشاره گر start اشاره میکند (گره اول) اشاره کند , سپس start به گره جدید اشاره کند اگر بر عکس عمل میکردیم و ابتدا start را به گره جدید اشاره میدادیم , ارتباط با گره اول و در نتیجه کل گره قطع میشد و کلا کار خراب میشد!

مثال 3 ) جستجو در لیست پیوندی :

برای جستجو در لیست پیوندی روال کار به این شکل هست :

1 – مقداری که کاربر قصد جستجوی آن را دارد، میگیریم.
2 – شروع به پیمایش لیست از گره ی اول میکنیم.
3 – در هر گره که مقدار مورد نظر ما موجود باشد به نتیجه رسیده ایم.


void search(int find)
{
    int numberOfNode = 1 ;
    node *current = start ;
    while (current != NULL) //پیمایش لیست
    {
       if (find == cuurrent->data)
       {
              printf("Found it in the %dth Node" , numberOfNode) ;
              break ; // اگر مقدار پیدا شد کار تمام است
        }
       current = current->link ;  // اگر مقدار مورد نظر در این گره نبود یک گره جلو میرویم
       numberOfNode++ ; // در مورد این عبارت در زیر توضیح داده شده
     }
}

سه نکته مهم در این مثال وجود دارد که در توابع قبل نبود (بسیار مهم!):

1– اگر به شرط while دقت کنید با شرط پیمایش توابع دیگر تفاوت کوچکی دارد. در واقع در توابع دیگر فقط میخواستیم به گره آخر برسیم به همین خاطر وقتی به گره آخر میرسیدیم (current->link != NULL) حلقه تمام میشد. اما در اینجا نه تنها میخواهیم به حلقه آخر برسیم بلکه باید روی آن عملیاتی را انجام دهیم پس حلقه باید روی گره آخر هم اعمال شود در واقع با این شرط جدید حلقه یک بار بیشتر از قبل ایجاد میشود. اگر شرط را مثل قبل بنویسید چه میشود؟ تابع گره آخر را جستجو نمیکند و به محض اینکه به گره آخر میرسد حلقه تمام می شود.

2– به متغیر numberOfNodes دقت کنید. کار این متغیر این است که مشخص کند که شماره گره ای که الان current به آن اشاره میکند چیست در واقع با این کار چیزی شبیه به Index در آرایه ها ایجاد کردیم. نحوه ایجادش فکر خاصی نمیخواد! فقط هر جا یک گره جلو رفتیم (current = current->link) این متغیر را هم زیاد میکنیم. اگر این متغیر را تعریف نکنیم چه میشود؟ نمیتوانیم به کاربر اعلام کنیم که مقدار پیدا شده در چه گره ای وجود دارد.

3– به بدنه while دقت کنید. در while یک if وجود دارد و یک پیمایش به جلو. بعضا دیده می شود که افرادی که تازه کار با لیست پیوندی را شروع کرده اند به اشتباه ابتدا عبارت پیمایش به جلو را مینویسند و بعد شرط را چک میکنند که این کار اشتباه است. اگر این اشتباه را انجام دهید چه میشود؟ تابع گره اول را جستجو نمیکند!

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

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

هرگونه کپی برداری از این مقاله منع اخلاقی دارد!!

نویسنده : saman.r

بازبینی و تدوین : ali.e