لیست مرتبط در برنامه نویسی

لیست مرتبط در برنامه نویسی

اسلاید 1: Linked List Containers

اسلاید 2: Useful Linked List Add-Onsآيا مي شود تغييراتي در پياده سازي ليست داد يا متغييرهايي اضافه کرد به نحوي که کار ما به عنوان برنامه نويس آسانتر شود؟متغييري براي مشخص کردن سايز فعلي ليستشمردن تعداد نودها در يک تابع هزينه بر است. اما نگهداري يک متغيير خيلي راحت است. اشاره گر انتهااضافه کردن به انتها را ساده مي کند.

اسلاید 3: Tail Pointersاگر هميشه به آخر ليست اضافه مي کنيم. داشتن يک اشاره گر انتها بسيار مفيد است و دسترسي مستقيم به آخرين نود ليست داريم.اليته هنگام حذف يک نود يا اضافه کردن نود جديد، اشاره گر انتها را بايد به طور مناسب تغيير دهيم.ساخت ليست: first=tail=0; اولين نود: tail = new node first == tailList1 Data1List1 Data2List1 Data3tailfirst

اسلاید 4: Circular Listsيک ايده ديگر:اشاره گر آخرين نود را به اولين نود وصل کنيد. تغييرات در پياده سازي:فهميدن اينکه در آخر ليست هستيم:از “if (current -> link == first)”به جاي “if (current->link == 0)” استفاده کنيد.اليته هنگام حذف يک نود يا اضافه کردن نود جديد، بايد اشاره گر آخرين نود را به اولين نود وصل کنيم.

اسلاید 5: Circular List Implementationمي خواهيم ليست پيوندي را براي حلقوي شدن آماده کنيم:نمي خواهيم که فقط يک اشاره گر ابتدا داشته باشيم. چرا؟اگر بخواهيم به آخر اضافه کنيم، بايد از اول ليست شروع کنيم و تا آخر ليست برويم. اگر بخواهيم به ابتداي ليست اضافه کنيم، باز هم مجبوريم تا آخر ليست برويم چون بايد اشاره گر آخرين نود را به نود جديد وصل کنيم. پياده سازي ليست حلقوي با اشاره گر انتها بسيار مؤثرتر است.داشتن دو اشاره گر (ابتدا و انتها) مازاد بر نياز است. چرا؟

اسلاید 6: Circular Linked ListsList1 Data1List1 Data2List1 Data3tailfirstمي شود به first با يک دستور از طريق tail->linkدسترسي داشت. لذا داشتن اشاره گر ابتدا ضروري نيست.

اسلاید 7: Circular Linked Listvoid insertAtFront(ListNode <Type> *x){if (tail == 0) { // empty list, tail = x; x-> link = x; // point to yourself}else{x->link = tail->link; // point new head link to old headtail->link = x; // point tail to new head}}براي پياده سازيinsertAtRear() فقط بايد دستور tail = x را در قسمت else اضافه نمود. تا انتها را برابر نود جديد قرار دهيم.

اسلاید 8: Linked List Examplesحال که ليست پيوندي را تعريف کرده ايم، ليست پيوندي چه کاربردهايي دارد؟چه کاربردهاي مي توانند از خاصيت عدم محدوديت حافظه در ليست پيوندي استفاده کنند؟چه کاربردهاي به خاصيت پويا بودن ليست پيوندي نياز دارند؟

اسلاید 9: Linked List Exampleچند جمله ايهاتعريف چند جمله اي::Y = coef_n * xexp_n + coef_n-1 * xexp_n-1 + … coef_0 * x0مثالها:3x14 + 2x8 + 18x14 – 3x10 + 10x6

اسلاید 10: Polynomialsچند جمله ايها پياده سازي ليست پيوندي بسيار مناسبي دارند:پياده سازي آرايه اي معمول: مقدار عنصر i ام آرايه برابر ضريب جمله i ام چند جمله اي باشد. مثلا مقدار محل پنجم آرايه، ضريب جمله با توان 5 است.اگر چند جمله اي پراکنده باشد، بايد براي ضرايب و توانهايي که وجود ندارند حافظه تلف کنيم. يک راه حل آرايه اي ديگر: يک آرايه از اشياء تعريف کنيد. هر شئ آرايه داراي دو قسمت توان و ضريب است. در اين صورت مشکل اتلاف حافظه حل مي شود.خواهيم ديد که اين روش يک مشکل ديگر دارد.

اسلاید 11: Polynomialsهر ترم چند جمله اي داراي دو قسمت توان و ضريب است.struct Term { int coef;int exp;void Init(int c, int e) { coef = c; exp = e;}};

اسلاید 12: Polynomialsچند جمله اي را با يک ليست پيوندي از ترمها مدل مي کنيم.class Polynomial{private:LinkedList<Term> poly;};

اسلاید 13: Polynomialsجمع چند جمله ايها3x3 + 2x + 1 + 2x3 + 3x2 + 5================= 5x3 + 3x2 + 2x + 6

اسلاید 14: Polynomialsجمع چند جمله ايها:در هر دو ليست بگرد (از ابتداي هر ليست)اگر exponent1 == exponent2,CoefficientSum = Coefficient1 + Coefficient2اگر CoefficentSum != 0 اين ترم را به جواب اضافه کنElse, توان بزرگتر را پيدا کنو ترم مربوطه را به جواب اضافه کن.

اسلاید 15: Polynomials3 32 11 02 33 25 05 33 22 16 0

اسلاید 16: Polynomialsجمع جمع چند جمله ايها جايي است که ليست پيوندي مزيت خود را نشان مي دهد. چون نمي توان تعداد ترمهاي حاصل جمع را حدس زد.تعداد ترمهاي حاصل جمع مي تواند صفر باشد.مي تواند برابر سايز چند جمله اي بزرگتر باشد.يا برابر مجموع سايز هر دو چند جمله اي باشد.نمايش آرايه اي باعث اتلاف حافظه خواهد شد.اما نمايش ليست پيوندي فقط به اندازه نياز مصرف خواهد کرد.

اسلاید 17: Polynomialsبراي انجام عمل جمع چند جمله ايها بايد عملگر + را سربارگذاري کنيد. پياده سازي در صفحه 193 کتاب

اسلاید 18: Example: Equivalence Classesيک استفاده ديگر از ليست پيوندي:پيدا کردن کلاسهاي هم ارزيتعريف:فرض کنيد يک رابطه داريم مثل (<, >, ==, …)مي گوييم که اين رابطه يک رابطه هم ارزي روي مجموعه S است اگر اين رابطه روي S بازتابي، متقارن و متعدي باشد.

اسلاید 19: Equivalence RelationsReflexiveA ? AIs < Reflexive? A < A NoIs = Reflexive?A == AYesSymmetric: If A ? B, then B ? AIs < Symmetric? A < B, then B < A NoIs = Symmetric? A = B, then B = A Yes

اسلاید 20: Equivalence RelationsTransitive If A ? B and B ? C, then A ? C Is < transitive?A < B, B < C, A < C Yes Is = transitive?A = B, B = C, A = C Yes= بازتابي، متقارن و متعدي است. پس يک رابطه هم ارزي است.< متقارن و بازتابي نيست. پس يک رابطه هم ارزي نيست.

اسلاید 21: Equivalence Classesيک رابطه هم ارزي مي تواند مجموعه S را به چند کلاس هم ارزي افراز کند. بطوريکه، به ازاي هر دو عضو يک کلاس مثل x و y داريم: x equiv y

اسلاید 22: Equivalence Classesمثال کلاسهاي هم ارزي :Let our relationship be = mod 3Reflexive5 mod 3 = 5 mod 3 => 2 = 2 YesSymmetric5 mod 3 = 8 mod 3, then 8 mod 3 = 5 mod 32 = 2, then 2 = 2 YesTransitive5 mod 3 = 8 mod 3, 8 mod 3 = 14 mod 3, then 5 mod 3 = 14 mod 32 = 2, 2 = 2, then 2 = 2, Yes

اسلاید 23: Equivalence Classesکلاسهاي هم ارزي: تمام اعدادي که باقيمانده تقسيم آنها به صفر مثل هم هست، متعلق به يک کلاس هم ارزي هستند.Mod 3 = 0Mod 3 = 1Mod 3 = 2{0,3,6,9,…}{1,4,7,10,…} {2,5,8,11,…}

اسلاید 24: Equivalence Classesهدف:تعدادي رابطه هم ارزي داده شده اند. کلاسهاي هم ارزي متناظر را پيدا کنيد. Relations: 0 = 4, 3 = 1, 6 = 10, 8 = 9, 7 = 4, 6 = 8, 3 = 5, 2= 11, 11 = 0 Classes: {0,2,4,7,11}, {1,3,5,}, {6,8,9,10}

اسلاید 25: Equivalence Classesمي توانيم يک ماتريس n در n (n تعداد عناصر) درست کنيم تا تمام هم ارزيهاي ممکن را دخيره کنيم. اما اکثر عناصر آن صفر خواهند بود.به جاي آن مي توانيم براي هر عنصر يک ليست پيوندي درست کنيم که شامل تمام اعضاي هم ارز آن در ليست هم ارزيها باشد. پس براي هر رابطه I = J :I را به ليست J اضافه کنيد.J را به ليست I اضافه کنيد.

اسلاید 26: Equivalence Classes12345678910110114311571038468601092

اسلاید 27: Equivalence Classesبراي پيدا کردن کلاسهاي هم ارزي يک آرايه به تعداد عناصر درست کنيد و با -1 پر کنيد:از اولين عنصر آرايه ليستها که علامت نخورده است (-1 است) شروع کن.X را چاپ کن و محل متناظر در آرايه را علامت بزن.براي تمام عناصري که هم ارز X هستند ( اين عناصر توي ليست پيوندي X هستند)، اگر محل عنصر در آرايه علامت نخورده بود: محل مربوطه در آرايه را علامت بزن. عنصر را چاپ کن.اين عنصر را به پشته اضافه کن.براي هر کدام از عناصر پشته مرحله 3 را تکرار کن.صفحه 205 و206 کتاب

اسلاید 28: Equivalence ClassesFirst Steps of Test Run on Previous Data

اسلاید 29: Complexity of Equivalence Class Operationsمقدار دهي اوليه: مقدار دهي آرايه ليستها و آرايه خروجي: O(n)پردازش هر جفت: 2 برابر تعداد رابطه ها: O(m)پس کلا: O(n+m)پيمايش ليست:n ليست داريم و 2m رديف در تمام ليستهادر صورتي ليست را پردازش مي کنيم که قبلا چاپ نشده باشد. پس به هر رديف آرايه ليستها يک بار نگاه مي کنيم (n). به دليل مشابه، هر رابطه هم ارزي فقط دو بار پردازش مي شود. (2m) پس کلا: O(n+m)

اسلاید 30: Doubly Linked Listsبزرگترين مشکل ما با ليست پيوندي اين است که فقط در يک جهت مي توانيم حرکت کنيم.فرض کنيد در محل هفتم هستيد. براي رسيدن به محل ششم مجبوريد که کل ليست را از اول پيمايش کنيد.در اين حالت به يک اشاره گر به سمت عقب نيازمنديم.

اسلاید 31: Doubly Linked Listsبراي حل اين مشکل مي توان براي هر نود دو اشاره گر (به قبلي و بعدي) تعريف نمود.در اين صورت الحاق و حذف از ليست و ديگر دستکاريها در ليست سخت تر هستند. چون بايد هر دو جهت ليست را تنظيم نمود.

اسلاید 32: Doubly Linked Listsتعريف:class DblList; // forward declarationclass DblListNode{friend class DblList;private:int data;DblListNode *right, *left;};

اسلاید 33: Doubly Linked Listsclass DblList{public:// list manipulationprivate: DblListNode* first;};

اسلاید 34: Doubly Linked ListsLEFTDATARIGHTLEFT10RIGHTLEFT15RIGHTLEFT29RIGHTيک نود نمونهيک ليست دوبل حلقوي با سه نود

اسلاید 35: Doubly Linked Listدقت کنيد که در اشاره گر p : p = p->left->right = p->right->leftيعني رفتن به جلو و برگشتن به عقب مثل رفتن به عقب و بازگشت به جلو است.

اسلاید 36: Doubly Linked Listvoid DblList::Insert(DblListNode *new, DblListNode *current){// insert new after xnew->left = current; new->right = current->right;current->right->left = new;current->right = new;}10LcurrentR12LRR11Lnew

اسلاید 37: Doubly Linked Listvoid DblList::Delete(DblListNode *toDelete){// delete node pointed to by toDeletetoDelete->left->right = toDelete->right;toDelete->right->left = toDelete->left;delete toDelete;}10LR12LR11LtoDelete