لیست های پیوندی

لیست های پیوندی

اسلاید 1: ليست هاي پيونديدانشگاه پیام نور زرین شهر پاییز 91

اسلاید 2: نقايص کار با آرايه ها به صورت ترتيبیبازگشت ناپذير بودن حافظه بعد از گرفتن آنلازم بودن پيش بينی بيشترين حافظه مورد نيازپر هزينه بودن اضافه کردن عنصرپر هزينه بودن حذف کردن عنصر

اسلاید 3: پر هزينه بودن اضافه کردن عنصرمی خواهيم C را به آن اضافه کنيم به طوری که ترتيب آن الفبايی بماند. 0 1 2 3 4 5Shift 

اسلاید 4: پر هزينه بودن اضافه کردن عنصر-ادامه 0 1 2 3 4 5سوال:مرتبه الگوريتم بالا چيست؟O(n)

اسلاید 5: پر هزينه بودن حذف کردن عنصراگر بخواهيم B را از آرايه ی قبلی حذف کنيم بايد تمام عناصر بعد از آن را يکی به عقب بياوريم 0 1 2 3 4 5 مرتبه اين الگوریتم نيز (n)O است. shift

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

اسلاید 7: - عمليات ليست پيوندي- ايجاد ليست - درج گره در ليست- حذف گره از ليست- جستجو در ليست- مرتب سازي ليست- معكوس كردن ليست- و ...

اسلاید 8: ليست پيونديليست پيوندي خطی ليست پيوندي عمومیليست پيوندي حلقویلیست پیوندی دو طرفه

اسلاید 9: ليست هاي پيوندي خطی:فرض كنيد عناصر پشته ، صف و یا آرایه در داخل خودشان آدرس عنصر بعدي را داشته باشند چنين ترتيبي يك ساختمان داده اي به نام ليست پيوندي خطي راايجاد مي كند هريك ازعناصرتشكيل دهنده ليست و یا گره نام دارد .Node پيوندي شكل ساده اي از يك گــره : : اطلاعات مورد نظر ما را نگه داري مي كند infoبخش : يك اشاره گر است كه به گره ي بعدي در ليست پيوندي اشاره مي كند .Nextبخش يك ليست پيوندي خطي معمولا به شكل زير است:

اسلاید 10: براي دسترسي به ليست پيوندي از يك اشاره گر خارجي به اولين گره در ليست پيوندي اشاره مي كند استفاده مي كنيم.يا تهي دارد اين بدان معنا است كه پس از اين گره ،گره Null نكته: اشاره گر در آخرين گره مقدار ديگري در ليست پيوندي وجود ندارد.نكته: براي پياده سازي گره مي توان از يك ساختمان كمك گرفت به عنوان مثال ساختمان زير گره اي است.Char در آن از نوع infoرا تشريح مي كند كه بخش Struct node { Char info; Node * next; };) در گره را مشخص مي كند و منظور Info (قسمت اطلاعاتيpinfo اشاره گر به گره باشد pاگر اشاره گري است كه از آن گره خارج مي شود. P next از فرض كنيم خواسته باشيم گــره را به ليست پيوندي اضافه كنيم برا ي اين كار ابتدا مي بايست گره وجود دارد كه وظيفه ي ايجاد گره ي جديد Get nodeجديدي را ايجاد كنيم فرض كنيد تابعي به نام آن را مقداردهي Info , Next و توليد آدرس آن را به عهده دارد پس از ايجاد گره جديد بخش هاي مي كنيم.

اسلاید 11: پياده سازي تابع Get node :در زبان C تابعي وجود دارد به نام malloc كاربرد اين تابع بدين صورت است كه به اندازه عددذكر شده درپرانتزجلوي آن حافظه رابه شمااختصاص مي دهد براي اينكه بتوانيم به اندازه ی يك گره فضا بگيريم از اين تابع به شكل زير استفاده مي كنيم.Malloc (size of (node))فضاي اختصاص داده شده مي بايست در قالب يك گره پيكربندي شود بدين منظور مي بايست بنويسيم:Node *malloc (size of (node))*ذكــر شده جلوی node بدين خاطر است كه آدرس حافظه ي اختصاص داده شده توليد شده و نهايتا به وسيله ي تابع Get node برگشت داده شود شکل تابع get node براساس آنچه گفته شدبه صورت زیر است:Node *get node( ) {Return (node *malloc (size of (node)) }

اسلاید 12: پياده سازي تابع Empty:Int empty (node *p) {If (p==Null) Return (1);Else Return (0);}

اسلاید 13: اضافه کردن عنصر جديدالبته برای کاربردهای مختلف اضافه کردن فرق می کند.ما در اينجا اضافه کردن عنصر جديد بعد از يک عنصر مشخص را نشان می دهيم.مراحل کار:1) ایجاد عنصر جديد2) تنظيم اشاره گرهای مربوط به عنصر جديد

اسلاید 14: firstcurNode0 اضافه کردن عنصر جديد بعد از curNode

اسلاید 15: firstcurNode0newNodeCBADEnewNode  link = curNode  link ;curNode  link = newNode ;

اسلاید 16: first0CnewNodecurNodeABDEInsafter (curNode, x){ newNode=Get node (); newNodeInfo = x; newNodeNext = curNode next; curNode Next = newNode;}

اسلاید 17: اضافه کردن به ابتدای ليستبدين دليل اين حالت خاص را بررسی می کنیم که بعد از اضافه کردن عنصر بايد اشاره گر first به ابتدای ليست اشاره کند.مراحل کار1) ایجاد عنصر جديد2) اشاره دادن اشاره گر first به عنصر جديد

اسلاید 18: اضافه کردن به ابتدای ليستfirst00newNodeABCDEnewNode=getNode()newNode  link = first;first = newNode;

اسلاید 19: اضافه کردن به ابتدای ليست-ادامهfirstnewNode0ABCDEnewNode =get node ( );newNode info=A;newNode next=first;first= newNode;

اسلاید 20: حذف عنصر از ليست پيوندیمراحل کار:1) تنظيم اشاره گرها2) حذف کردن گره (آزاد کردن حافظه)

اسلاید 21: firstcurNode0ِAِBCِDِEحذف عنصری که curNode به آن اشاره میکندtempیافتن عنصر قبل از curNode تنظیم اشاره گرهاحذف گرهNode *temp = first;

اسلاید 22: firstcurNode0ِAِBCِDِEحذف عنصر از ليست پيوندی-ادامهtempwhile( temp  link != curNode) temp = temp  link;

اسلاید 23: حذف عنصر از ليست پيوندی-ادامهfirstcurNode0ِAِBCِDِEtemptemp  link = cur  link;Free(curNode);

اسلاید 24: firstcurNode0ِAِBCِDِEحذف عنصر از ابتدای ليست پيوندیNode *curNodecurNode=first;

اسلاید 25: first0curNodeِAِBCِDِEحذف عنصر از ليست پيوندی-ادامهfirst = curNode link;Free(curNode)

اسلاید 26: شبه كدي بنویسید كه در يك ليست پيوندي اگر pبه گره اي اشاره كــرده با شدگره بعداز آن را حذف كند :Delafter (p) {If ( p next ==Null) Print f (can not remove )Else{q= p next;P next= q next;Free (q);} }ABCEDqp

اسلاید 27: ليست مرتب:ليستي كه درآن عناصر کوچکترقبل ازعناصر بزرگتر قرار گرفته باشند . بنابراين اگر بخواهيم عنصر جديدي به آن اضافه كنيم مي بايست به گونه ای باشد كه ترتيبش هم نخورد.می خواهيم شبه كدي براي درج يك عنصر جديد در داخل ليست مرتب بنويسيم .-1 عنصر جديد از تمامي عناصر ليست كوچكتر است .-2 مقدار جديد به گونه اي است كه در ميان ليست قرار مي گيرد.-3 عنصر جديد از تمام عناصر ليست بزرگتر است.

اسلاید 28: If (x< list info) Insfirst(list, x);Else{ p=list; q=list  Next; } While (qinfo < x && q! =Null) { p=p Next; q=q Next; }Insafter (p, x) }

اسلاید 29: لیست پیوندی خطی با گره راسدر برخي مواقع براي اينكه درج يكسان درآيد ( همواره به صورت insafter) يك گره اضافه به نام گره راس درابتداي ليست درنظرمي گيريم حتي زماني كه ليست پيوندي تهي است وگره راس موجود است.بخش Info درگره راس دربرخي موارد بلااستفاده قرار مي گيرد و در برخي ديگر از موارد اطلاعاتي از ليست پيوندي در گره قرار مي گيرد مثلا مي توان تعداد گره هاي موجود را در آن ثبت كنيم.و در برخي ديگر گره راس مي تواند دو اشاره گر يكي به ابتدا و ديگري به انتها ي ليست پيوندي داشته باشد.

اسلاید 30: لیست عمومیلیست عمومی لیست پیوندی است که فیلد اطلاعات در هر یک از گره های آن می تواند بر حسب نیاز اشاره گر باشد. ساختار هر گره این نوع لیست به صورت زیر است:Tag =0  info else link لیست های عمومی را می توان به فرم پرانتزی نمایش داد. شکل صفحه 150معمولا لیست های عمومی برای نمایش درخت ها به کار میروند. taginfo/DlinkLink

اسلاید 31: چندین مورد از کاربردهای لیست پیوندینمایش چند جمله ای ها به صورت لیست پیوندیپیاده سازی پشته به کمک لیست پیوندی پیاده سازی صف به کمک لیست پیوندی

اسلاید 32: نمایش چند جمله ای ها به صورت لیست پیوندیاز ليست هاي پيوندي مي توان براي پياده سازي چند جمله ايها استفاده كرد در اين صورت هر گره شامل سه بخش خواهد بود.فرض كنيد دو چند جمله اي داريد و مي خواهيد آنها را با هم جمع كنيد.7x^5 + 3x^3 – 6x^2+ 45x^6-4x^5+2x^4+2x^2-xهنگام جمع دو چند جمله اي حالتهاي زير مي تواند وجود داشته باشد :1)دو جمله اي كه با آن مواجه هستيم هم توان باشند :ضرايب با هم جمع شوند وهردوجمله راپشت سرمی گذاریم.2)يكي از جملات توان بيشتري دارد آن جمله انتخاب شده و پشت سر گذاشته مي شود .

اسلاید 33: p=list1;q=list2;List3=Get node ();If ( p t = = q t){List3 t= p tList3 z=p z + q z;p=p  Next;q=q  Next;}Else if (p t > q t){List3 t=p t;List3 z=p z;p=p Next;

اسلاید 34: }Else {List3 t=q t;List3 z=q z;q=q next;r=list3;While (p! =Null && q! =Null){If (p t==q t){Insafter (r, p z + q z, p t); p= p Next; q= q next; r = r Next;}

اسلاید 35: Else if (p t >q t) {Insafter (r, p z, p t);r=r Next;p= p Next; }Else{Insafter (r, q z, q t);r=r Next;q= q next;} }//whileIf (p! =Null){While (p! =Null) {Insafter (r, p t, p z);

اسلاید 36: r= r Next;p=p Next;} }If (q! =Null){ While (q! =Null);{Insafter (r, q t, q z);r= r Next;q= q Next;}//while }

اسلاید 37: پياده سازي پشته ها با استفاده از ليست هاي پيوندي خطي:عمل افزودن يك عنصر به ابتداي ليست پيوندي مانند اضافه كردن عنصري در بالاي پشته است و عمل حذف اولين عنصر از لیست پيوندي مانند حذف عنصر بالاي پشته مي باشد بنابراين توابع push , pop را مي توان به شكل زير پياده سازي كرد.

اسلاید 38: پشته های پيوندیبا استفاده از ليست پيوندی اين استراتژی را پياده سازی کنیم.همان طور که می دانید در پشته ورود و خروج داده ها از يک طرف انجام می شود.top0

اسلاید 39: درج در پشتهپياده سازي تابع Push:Void push (node *Top, char x) { Node *p; P=Get node (); Pinfo=x; P next=Top; Top=p; }topAXDCB0topBAEDC0P

اسلاید 40: topBAEDC0حذف از پشتهtemp = top;temp

اسلاید 41: topBADC0EtempDtopCBA0حذف از پشته-ادامهdelete temp;

اسلاید 42: پياده سازي تابع Pop:Char pop (node *Top){Node *temp;Char x;If (empty (Top)) Print f (stack is empty); Else { temp=Top; Top= Top next; x=tempinfo; Free (temp); Return (x); }}

اسلاید 43: صف های پيوندیهمان طور که می دانيد در استراتژی صف ورود اطلاعات از يک طرف و خروج اطلاعات از طرف ديگر است.به اين دليل به دو اشاره گر به نام های rear و front نياز داريم.front0rearStruct queue { Elemnttype info; Queue *next; };Queue *front,*rear;

اسلاید 44: پياده سازي صف ها به كمك ليست ها ي پيوندي خطي :اگر ليست پيوندي خطي به گونه اي مديريت شود كه اولين عنصر ورودي ، اولين عنصر خروجي باشد مي توان گفت يك صف پياده سازي شده است .در نتيجه مجبوريم از يك طرف ليست پيوندي عمل حذف و در طرف ديگر آن عمل درج را انجام دهيم.

اسلاید 45: پياده سازي تابع Insert:Void Insert (node *r , char x){ Node *P; P=Get node (); Pinfo=x; P next=Null;If (r==Null) { f=P; r=P; }Else { r next=P; r =P; } }front0rearp0x

اسلاید 46: پياده سازي تابع Remove:Char Remove (node *front ){ Node *ptr; Ptr=front; Front=front next; Free(ptr);}

اسلاید 47: معايب پياده سازي صف و پشته با استفاده از ليست هاي پيوندي:-1هر گره در ليست پيوندي از هر سلول آرايه فضاي بيشتري تلف مي كند.-2مديريت ليست هاي پيوندي نسبت به آرايه مشكل تر است.مزاياي ليست پيوندي نسبت به آرايه ها :علاوه بر آنچه كه گفته شد در ليست هاي پيوندي درج و حذف از ميا نه ي ليست پيوندي به سادگي امكان پذير است اما در آرايه ها هر عمل درج و هر عمل حذف نياز به Shift دادن عناصر آرايه دارد مزاياي آرايه نسبت به ليست پيوندي :دسترسي به هر يك از عناصر آرايه به شكل مستقيم انجام مي شود اما در ليست های پيوندي براي رسيدن به گره nام مي بايست n-1 گره پشت سر آن پيمايش شده باشد .

اسلاید 48: ليست هاي پيوندي حلقوی:اگر اشاره گر خارج شده از آخرين گره به جاي Null به گره ابتدايي اشاره كند ساختار جديدي به نام ليست پيوندي حلقوی پديد مي آيد.در ليست هاي پيوندي حلقوی به خاطر بسته بودن ليست مي توان از هر نقطه ليست به نقاط ديگر دسترسي پيدا كرد.براي آنكه مديريت ليست ساده تر انجام شود اشاره گر خارجي به ليست را روي آخرين گره فرض مي کنیم در نتيجه گره ي بعد از آن، گره ي اول خواهد بود.به وسيله ي ليست هاي دايره اي ميتوان پشته ها وصف ها را پياده سازي كرد.پشته ها درليست هاي پيوندي دايره اي :ABC

اسلاید 49: شبه كدي براي تابع Push :Void push (stack, x){p=Get node ( );p info=x;If (stack! =Null){p Next =stack next;Stack next=p;}Else{p Next=p;Stack=p;} }

اسلاید 50: شبه كدي براي تابع Pop :Char pop (stack){If (stack == Null)Print f (stack is empty);Else{P= stack Next;Stack Next=p Next;X=p info;If (p==stack)Stack=Null;Free (p);Return (x);} }

اسلاید 51: پياده سازي صف ها با استفاده از ليست هاي پیوندی دایره ای پياده سازي تابع Insert :Void Insert (queue, x) { p=Get node ( ); p  info = x;If (queue! =Null){p Next = queue Next;queue Next=p;}Else {queue =p; queue Next= queue; }} nullBfrACqqqq

اسلاید 52: پياده سازي تابع Remove :Char remove (queue){If (queue == Null) Print f (queue is empty);Else { p=queue Next; queuenext=p Next; X=p Info; If (p==queue) queue == Null; Free (p);Return (x); }}

اسلاید 53: ليست هاي پيوندي دوطرفه:يكي از مشكلات بزرگ ليست هاي یک پيوندي (خواه خطي باشد خواه دايره اي ) آن است كه امكان پيمايش معكوس در آن ها وجود ندارد اين مشكل به وسيله ي ليست هاي دو پيوندي قابل حل است.نكته : ليست هاي دو پيوندي را گاهي ليست هاي پيوندي دو طرفه نيز مي گويند.شكل هر گره در ليست هاي دو پيوندي به شكل زير است.نكته : اشاره گر هاي Left, Right را در بعضي كتاب ها به ترتيب Prev , Next تعريف كرده اند.همان طور كه گفته شد در ليست ها ي دو پيوندي مي توان از هر نقطه به گره بعدي ويا قبلي دسترسي پيدا كرد.از جمله كارهايي كه به سادگي مي توان روي ليست هاي دو طرفه انجام داد حذف مستقيم گره اي است كه p بدان اشاره مي كند.به عنوان مثال در يك ليست دو پيوندي مجموعه دستورات زير باعث حذف گره p مي شود.

اسلاید 54: L=p left;R=p right;L right =r;R left=l;X=p info;Free (p);فرض كنيد خواسته باشيد در يك ليست دو پيوندي سمت راست گره ای که به آن اشاره شده گره جديدي را درج كنيم.Q=Get node ();Q Info=x;r= p right;Q Right=r;Q Left=p;P right=q;R left=q;rrQ

اسلاید 55: 0ABCDfirstE0curحذف از ليست دوطرفه بدون تعریف اشاره گر

اسلاید 56: A0BCDfirst0Ecur( cur  right)  left= cur  left;حذف از ليست دوطرفه بدون تعریف اشاره گر

اسلاید 57: ( cur  left)  right= cur  right;0ABCDfirstE0curحذف از ليست دوطرفه بدون تعریف اشاره گر

اسلاید 58: 0ArightleftBrightleftDrightfirstleftE0حذف از ليست دوطرفه بدون تعریف اشاره گر

اسلاید 59: 0ArightleftBrightleftDrightfirstleftE0حذف از ليست دوطرفه بدون تعریف اشاره گر

اسلاید 60: سوالاگر بخواهيم عنصر ابتداي ليست را حذف كنيم؟اگر بخواهيم عنصر انتهای ليست را حذف كنيم؟

اسلاید 61: پایان