نكاتي در مورد ساختمان داده(آرايه-صف-پشته-ليست-درخت-گراف)

[Y@SiN]

صف (queue):

صف لیست مرتبی است که عمل اضافه کردن (نوشتن) از یک طرف آن به نام انتهای صف (rear) و عمل خواندن (حذف کردن) از طرف دیگر صف به نام ابتدای صف (Front) می شود. ساختار صف به صورت FIFO است. (First In First Out). یکی از کاربردهای مهم صف در زمانبدی برنامه ها در سیستم عامل هستش. ساده ترین راه نمایش صف استفاده از یک آرایه یک بعدی به طول n می باشد.
برای کار با صف معمولی به دو اشاره گر نیاز داریم: یکی Front که همیشه به یک عنصر قبل از عنصر ابتدایی اشاره می کنه و rear که همیشه به آخرین عنصر اشاره داره.
دامنه تغییرات front و rear از 0 تا n هست و مقادیر اولیه اونها 0 قرار می گیره.
شرط خال بودن صف عبارت است از :
if front = rear
و شرط پر بودن صف عبارت است از :
if rear = n

[Y@SiN]

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

کد:

 
{
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=5 داده را در یک صف 5 خانه ای ریخته و سپس آنها را بخوانیم در حالتی که r=f=5 داریم:
صف خالی است چون: r=f
صف پر است چون: r=n=5

[Y@SiN]

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

[Y@SiN]

فرم کلی گره ها در زبان 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 می توان یک نود جدید را در زنجیر ساخت.


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

[Y@SiN]

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

[Y@SiN]

هر لیست پیوندی با اشاره گر سر لیست مشخص می شود که معمولا آن رابا (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) ) = ?     (بی معنی)

[Y@SiN]

براي دوستاني كه مي خوان همزمان با پيشروي تاپيك مطالعاتي هم داشته باشند، يه سري اسلايد اينجا قرار ميدم.

Ds-1: مبناها
ds-2: آرايه - مرتب سازي - جستجو
ds-3: پشته و صف و كاربرد آنها
ds-4: ليست پيوندي و انواع آن
ds-5: درخت و گراف و كاربرد آنها

[sedigheh 69]

سلام
چند وقتي بود ميخواستم يه تاپيك در مورد ساختمان داده بزنم و مطالب مفيد مربوط به ساختمان داده رو با كمك دوستان تو اون جمع كنيم تا يه تاپيك جالبي به وجود بياد. من خودم كه چيز زيادي بلد نيستم فقط الگوريتمها و ... تو دانشگاه گفتن رو بلدم كه اونارو هم يكي يكي ميذارم.
از دوستان خواهش ميكنم اگه مطلبي دارن كه مفيد ميتونه باشه دريغ نكنند. با تشكر

اطلاعاتی راجعه به شرط پر یا خالی بودن پشته میخوام؟

[Borna66]

اطلاعاتی راجعه به شرط پر یا خالی بودن پشته میخوام؟

اده ترین روش برای نمایش پشته استفاده از یک آرایه 1 بعدی به طول n می باشد. در کنار آرایه متغیری به نام top وجود دارد که به عنصر بالایی اشاره دارد. top در ابتدای کار صفر است و از 0 تا n تغییر می کند.
شرط خالی بودن پشته عبارت است از : if top=0
شرط پر بودن پشته عبارت است از : if top= n
زیر برنامه های حذف از پشته (pop) و اضافه کردن به پشته یا نوشتن در آن (push) در زبان C به صورت زیر است:
کد:

void push (item k)
{
if (top ==n-1)
stackfull ();
else
;stack[++top]=k
}


items pop()
}
if (top==-1)
stackempty();
else return stack [top--];
{

اما اگر فقط نیاز به دو پشته در برنامه داشته باشیم راه حل ساده است. برای این منظور از یک آرایه n خانه ای استفاده می کنیم. [ s[1 ابتدای پشته اول و [ s[n ابتدای پشته دوم را نشان می دهد و پشته ها به سمت همدیگر می توانند رشد کنند. بدین ترتیب از حافظه موجد به صورت بهینه استفاده می شود.
ولی اگر بخواهیم بیش از دو پشته داشته باشیم، روش فوق قابل استفاده نیست. در این حال برای نمایش n پشته حافظه [ s[1..n را به n قسمت تقسیم می کنیم. تقسیم بندی آرایه ها متناسب با نیازها باشد. در این حالت مقادیر به صورت زیر خواهد بود:

b=t=[m/n](i-1)+1

که در آن n تعداد پشته ها و m حد بالای آرایه است.در اینجا میبینید که دیگر نیازی به استفاده از top نیست.