نكاتي در مورد ساختمان داده

[آبجی]

زیر برنامه های اضافه کردن و حذف کردن از پشته i ام در پشته های چندگانه:

     void addq(items k)
{
    if (rear==n-1)
        queufull();
    else
        q[++rear]=k;
} 

     void delq()
{
    if (front==rear)
        queuempty();
    else
        reaturn q[++front];
} 

مشکل اصلی صف ها در این است که صف در یک لحظه می تونه پر و خالی (همزمان) باشه. مثلاً اگر n=5 داده را در یک صف 5 خانه ای ریخته و سپس آنها را بخوانیم در حالتی که r=f=5 داریم:
صف خالی است چون: r=f
صف پر است چون: r=n=5

[آبجی]

صف حلقوی:
صف حلقوی همون صف ساده است ولی با این تفاوت که مشکل فوق رو نداره. تمام مقادیر اون با صف ساده یکسان هست مگر شرط پر بودن آن که به شکل زیر هست:
if Front=(Rear+1) mod n
زیر برنامه های حذف و اضافه کرن به صف حلقوی عبارتند از:

     void delq()
{
    if (front==rear)
        queuempty();
    else {
        front=(front+1)%n;        
         reaturn q[front];
} 
     کد:
     void addq(items k)
{
    if (front==(rear+1)%n)
        queufull();
    else {
        rear=(rear+1)%n;        
         q[rear]=k;
} 

در صف حلقوی در هر لحظه حداکثر n-1 عنصر وجود داره و بدین ترتیب می توان بین حالت پر و خالی تمایز قائل شد.

[آبجی]

مفهوم لیست پیوندی:
غالباً برای ذخیره تعداد زیادی داده ها از آرایه استفاده می کنند. ولی به دلیل ایستا بودن ساختار آرایه و محدودیت کار با آن از ساختار دیگه ای استفاده می شه به نام linked list یا همون لیست پیوندی.
عناصر لیست پیوندی از نوع پویا بوده و عناصر اون الزاماً در کنارهم نمی باشند. (بر عکس آرایه) . به همین دلیل اعمال درج و حذف در اون به راحتی و سریعتر از آرایه است. در مقابل برخی از اعمال مثل جستجو یا مرتب سازی در آرایه سریع تر از لیست پیوندی است.
هر عنصر یا گره (node) حداقل از دو فیلد داده (Data)و اشاره گری به گره بعدی (Link) تشکیل شده است.

[آبجی]

فرم کلی گره ها در زبان c:

typedef struct NODE *p_node;
typedef struct NODE{
  char name[21];
  int num;
  p_node link;
} 

ایجاد زنجیر و دستیابی به فیلدها:

در تکه کد زیر مفهوم زنجیر و طرز ایجاد آنرا بیان می کنیم:

var 
   x,y,z:p_node;
begin
   new(x);
   x^.name:='ali';
   x^.num:=123;
   x^link:=nil;

   z:=x;
   
   new (y);
   y^.name:='mohsen';
   y^.num:=456;
   y^link:=nil;
   x^.link=y;
end. 

با دستور new می توان یک نود جدید را در زنجیر ساخت.
در انتهای برنامه دو نود داریم . نود اول با نام ali و نود دوم با نام mohsen.
لیست ها را از 3 من ظر می توان تقسیم کرد:
1- یا یکطرفه هستند یا دو طرفه.
2- یا خطی هستند یا حلقوی.
3- یا بدون Head هستند یا Head دارند.

[آبجی]

انواع ليست پيوندي
1)ليست پيوندي يك طرفه خطي
2)ليست پيوندي يك طرفه حلقوي
3)ليست پيوندي دوطرفه خطي
4) ليست پيوندي دوطرفه حلقوي

[آبجی]

هر لیست پیوندی با اشاره گر سر لیست مشخص می شود که معمولا آن رابا (First) یا (Head) مشخص می کنند .(First) یا (Head) اشاره گری است که آدرس گره اول لیست پیوندی را مشخص می کند ، همچنین آخرین گره از لیست پیوندی بخش اشاره گرش (Link) مقدار تهی خواهد داشت که در زبان پاسکال با (Nil) ودر زبان C با (Null) مشخص می شود. (شكل 1 رو ببينيد بزرگه)
به مثال زير توجه كنيد.( شكل 2 رو ببينيد كوچيكه)

Data (X) = ?                       (70)
Link (X) = ?                         (Y)
Data ( Link (x) ) = ?           (60)
Link ( Link (w) ) = ?           (Y)
Link (Z) = ?                     (Null)
Data ( First ) = ?                 (50)
Link ( First ) = ?                  (X) 
Link ( Data (y) ) = ?    بی معنی