لیست پیوندی

 باسلام. 

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

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

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

                                   

یک داده در پیوندی مزیت دیگه ای هم داره اون اینه که میتونه تعداد بیشتر از یکی داده و حتی توابع رو هم در خودش نگه داره و این تو نوشتن برنامه های بزرگ خیلی مفیده. 

بقیه را در ادامه مطلب ببینید....

                                  

برای طراحی یک لیست پیوندی ساده اول یک گره تعریف میکنیم.گره نوع داده ای هست که همون عضو ما هست و داخل خودش یک اشاره گر داره.(لطفا به نوت پد کپی کنید)  

class node
{
friend class list;

  public:
       node(int);
  node *link;
  int  value;
}
     node::node(int n)
        {value=n;} 

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

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

class list
{
  public:
       list();
  node *first;
  int data;

  void insert(); 

} 

  برای کنترل لیست یک اشاره گر به خانه اول داخل کلاس تعریف شده first و برای انتها هم اشاره گره آخری رو null میکنیم.

list::list()
      {
        first=NULL;
        cout<<"\ninsert list";
        while(data!=0)
     insert();
      } 

تابع insert در این کلاس اشاره گرهای گره را کنترل میکند.مثلا برای ساختن یک گره جدید اول یک اشاره گر به گره میسازیم و بعد با دستور newint یک داده از اون نوع رو میسازیم.حالا میتونیم گره دیگری هم بسازیم و اشاره گر داخل این گره را به گره های دیگر پیوند بزنیم. 

void list::insert()
             {
               node *leaf;
               cout<<"\ndata?";
               cin>>data;
               leaf=new node(data);

               node *p=first; 
               node *q=first; 

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

               if(first==NULL)
                   {
                     first=leaf;  
                     leaf->link=NULL;
                   } 

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

               else if(first->value > data)
                  {
                    leaf->link=first;
                    first=leaf;
                  }
              else
                 {
     while(data >= p->value)
                             {
                               q=p;
                               p=p->link;
                               if(q->link==NULL)
                                    break;
                             }
                   q->link=leaf;
                     leaf->link=p; 

                 }
             
              } 

برای مثال هم چند برنامه اینجا گذاشتم.اینجا یه برنامه برای درج-حذف-و نمایش آبجکت های node (گره).هر آبجکت گره یه اشاره گر به آبجکت بعدی داره و هر آبجکت شامل یه داده int  _اسم نود_ است. کار اظافه کردن و حذف و نمایش رو کلاس list انجام میده.اینم برنامش:

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

  

این هم یک لیست حلقوی:  

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