مرجع دانلود پاورپوینت های درسی

حجم فایل : 366.6 KB
نوع فایل : پاور پوینت
تعداد اسلاید ها : 99
بنام خدا ليست هاي پيوندي تعريف ليست پيوندي Link List A . . . 0 Z B تعريف : مجموعه ای از گره ها که هرگره حداقل شامل يک فيلد داده ويک فيلد اشاره گر است.
اشاره گر هر گره از نوع خود گره است.
هر گره به وسيله ی اشاره گر خود به گره بعدی اشاره می کند. نقايص کار با آرايه ها به صورت ترتيبی بازگشت ناپذير بودن حافظه بعد از گرفتن آن
لازم بودن پيش بينی بيشترين حافظه مورد نياز
پر هزينه بودن اضافه کردن عنصر
پر هزينه بودن حذف کردن عنصر پر هزينه بودن اضافه کردن عنصر می خواهيم C را به آن اضافه کنيم به طوری که ترتيب آن الفبايی بماند. 0 1 2 3 4 5 Shift  پر هزينه بودن اضافه کردن عنصر-ادامه 0 1 2 3 4 5 سوال:مرتبه الگوريتم بالا چيست؟
O(n) پر هزينه بودن حذف کردن عنصر اگر بخواهيم B را از آرايه ی قبلی حذف کنيم بايد تمام عناصر بعد از آن را يکی به عقب بياوريم 0 1 2 3 4 5 مرتبه اين الگوریتم نيز (n)O است.  shift راه حل مشکلات ناشی از کار با آرايه به صورت ترتيبی استفاده ازليست پيوندی

مزايا:
مجبور نيستيم داده ها را در فواصل مشخصی ازهم قرار دهيم.
می توان حافظه ی بدون استفاده را به کامپيوتربرگرداند. - عمليات ليست پيوندي - ايجاد ليست
- درج گره در ليست
- حذف گره از ليست
- جستجو در ليست
- مرتب سازي ليست
- معكوس كردن ليست
- و ... ساختمان داده مورد نياز جهت پياده سازي لينك ليست:

استفاده از آرايه
استفاده از اشاره گر Pointer پياده سازي ليست پيوندی به وسيله ی آرايه برای ايجاد اين ليست بايد از دو آرايه استفاده کرد.
آرايه ی اول برای داده ها : اين آرايه از نوع داده ی مورد نظر انتخاب می شود (مثلا يک structure)
آرايه ی دوم برای اتصال ها : اين آرايه که از نوع int است.متناظر با داده هاست.که نشان دهنده ی آدرس داده بعدی است. پياده سازي ليست پيوندی به وسيله ی آرايه-ادامه 0 درج در ليست پيوندی درج در ليست پيوندی-ادامه درج در ليست پيوندی-ادامه درج در ليست پيوندی-ادامه درج در ليست پيوندی-ادامه مراحل درج در ليست پيوندی 1)قرار دادن داده ی لينک در آرايه ی داده ها
2)اشاره دادن عضو جديد به عضو بعد از خودش
3)اشاره دادن عضو قبل از عضو جديد به عضو جديد

نکته : هميشه ابتدا عضوجديد را در ليست قرار می دهيم سپس عضوهايی را که بايد به عضو جديد اشاره کنند به آن اشاره می دهيم. پياده سازي با اشاره گر تعريف يك نود
لازم است اين مسئله مشخص شود که فيلدهای ما چه نوع داده ای هستند.(به عنوان مثال می توان يک کاراکتر) class CharNode
{
private :
char data;
CharNode *link;
}; روش های طراحی ليست طرح اول:
متغير first را از نوع به عنوان متغير سراسری ...