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

صفحه 1:
‎le‏ د ‎ ‏دانشكاه ييام نور زرین شهر پاییز 66 

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

صفحه 3:
اااي ير هزينه بودن اضافه كردن عنصر مى خواهيم 0 را به آن اضافه كنيم به طورى كه ترتيب آن الفبايى بماند. 

صفحه 4:
با ‎SS‏ ‏ير هزينه بودن اضافه كردن عنصر-ادامه Telelololele * سوال:مرتبه الكوريتم بالا جيست؟(5) © 

صفحه 5:
ااا يي ير هزينه بودن حذف كردن عنصر 8 اگر بخواهیم ) را از آرایه ی قبلی حذف کنیم باید تمام عناصر بعد از آن را یکی به عقب بیاوریم 0 1 2 3 4 ۴ | ۶ |01 |6101 م مس مس € shh " مرتبه اين الككوريتم 333 ‎cael O(n)‏ 

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

صفحه 7:
= Fred ۳ ‏هم‎ sy | sey} “en 28 ‏هد‎ (| (en ‏عم‎ ۲ ‏حلا‎ 222059 | | SS ‏چله|‎ ‎Feb 26 ۷5 J A linked tise 

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

صفحه 9:
:ليست هاي پيوندي خطی فرض کنید عناصر پشته » صف و يا آرايه در داخل خودشان آدرس عنصر بعدي را داشته باشند جنين ترتيبي يك ساختمان داده اي به نام ليست بيوندي خطي راايجاد مي كند هريك از عناصرتشکیل دهنده أيسث پيوندي عطلی(). و یا گره نام دارد : شکل ساده اي از يك گره بخثرج, لطلاعات‌مورد نظر ما را نگه داري‌مي‌کند : بخشری(). يك لشارم گر لستکه بسه گرم ي بسعدی‌در ليستپيوندي‌لشارم مي‌کند : :يك لیست پيوندي خطي معمولا به شکل زیر است ‎CHE > Null‏ 169 5 5 عط ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‏گام كره جهايم ‎ee‏ گر نوم گره لول ‎ ‎ ‎ ‎ ‎ 

صفحه 10:
براي دسترسي به ليست پيوندي از يك اشاره گر خارجي به اولین گره در لیست پيوندي اشاره مي کند استفاده مي کنیم نکته: اشاره گر در آخرین گره مقدار 00 یا تهي دارد اين بدان معنا است که پس از اين گره »گره .ديگري در لیست پيوندي وجود ندارد انكته: براي بياده سازي كره مي توان از يك ساختمان كمك كرفت به عنوان مثال ساختمان زير كره اي ارا تشريح مي كند كه بخش در آن از نوع -0.است Oru wide :صخلم ‎Ober‏ ‎Onde * vex;‏ ‎hk‏ ‏ای کپ گرد اج و سبططاهه ی ت كبري را سرمي ‎Juste‏ ‏۳ ‏از مح © .اشاره گري است که از آن گره خارج مي شود فرض کنیم خواسته باشیم گره را به ليست پيوندي اضافه کنیم برا ي اين کار ابتدا مي بایست گره جديدي را ایجاد کنیم فرض كنيد تابعي به نامطسی بع9) وجود دارد که وظیفه ي ایجاد گره ي جدید و تولید آدرس آن را به عهده دارد پس از ایجاد گره جدید بخش هاي وم( , 1-0 آن را مقداردهي .مي كنيم 

صفحه 11:
بياده سازي تابع ‎Bet corde‏ 1 در زبان 0 تابعي وجود دارد به نام قد كاربرد اين تابع بدين صورت است كه به اندازه عدد ذکر شده درپرانتزجلوي آن حافظه رابه شمااختصاص مي دهد براي اینکه بتوانیم به اندازه ی يك گره فضا بكيريم از اين تابع به شكل زير استفاده مي كنيم. ° ((طس) ج سم 0 فضاي اختصاص داده شده مي بایست در قالب يك گره پيكربندي شود بدین منظور مي بایست بنویسیم: ‎Orde *wdlor (otze oF (axe)‏ *ذکر شده جلوی سرب بدین خاطر است که آدرس حافظه ي اختصاص داده شده تولید شده و نهایتا به وسيله ي تابع ‎Det cond‏ برگشت داده شود شكل تابع فدح بسي براساس آنچه كفته شدبه صورت زير است: ‎QDode *yet wee )‏ { ‎Retwa (code *wulor (sta oP (arde))‏ } 

صفحه 12:
پیاده سازي تایع بوسه: ‎(code *)‏ زمره بو ٩۳ (p==Oul) Qetura @); Qetura (O); 

صفحه 13:
اضافه کردن عنصر جدید * البته برای کاربردهای مختلف اضافه كردن فرق مى كند. 8 ما در اینجا اضافه کردن عنصر جدید بعد از یک عنصر مشخص را نشان می دهیم. 8 مراحل کار: 0) ایجاد عنصر جدید 3) تنظیم اشاره گرهای مربوط به عنصر جدید 

صفحه 14:
اضافه كردن عنصر جدید بعد از ‎curNode‏ curtinds first ‘| 0 

صفحه 15:
وهو امي ‎first A B +] D E|0‏ ex newNode_+| ¢ newNode > link = curNode > link ; curNode > link = newNode ; 

صفحه 16:
curNode—— 8751 ۸ B 60 | یه ‘eoPer (ow Ord, x) weuDode=Cet wrk (); weuode>IePo = x; ‎nwo Deen;‏ = )یلح( ری ‎>On = wuDods;‏ »)مه ‎ ‎ ‎ 

صفحه 17:
اضافه كردن به ابتداى ليست "ا بدين دليل اين حالت خاص را بررسى مى كنيم كه بعد از اضافه كردن عنصر باید اشاره گر جما به ابتداى ليست اشاره كند. " مراحل كار 6) ايجاد عنصر جديد ©) اشاره دادن اشاره كر جه" به عنصر جديد 

صفحه 18:
Se ‏اضافه كردن به ابتداى ليست‎ men Node: — first - B Cc D E/0 newNode=getNode() newNode > link = first; first = newNode; 

صفحه 19:
Se ‏اضافه کردن به ابتدای لیست.-ادامه‎ newhnde— first A B Cc 1D E/0 newNode =cgt wee ( ); newNode Po=@; newNode rex Fret; Pre= newNode; 

صفحه 20:
A ‏حذف عنصر از لیست پیوندی‎ ‏مراحل کار‎ # 0) تنظيم اشارء أكزها ©) حذف كردن كره (آزاد كردن حافظه) 

صفحه 21:
SS ‏با‎ حذف عنصری که 61277006 به آن اشاره میکند 0) یافتن عنصر قبل از ۳006 ©) تنظيم اشاره گرها ©) حذف كره ‎curNode——‏ ‎first)“ 9 0 oD oF] 0‏ temp Node *temp = first; 

صفحه 22:
2 حذف عنصر از لیست پیوندی-ادامه curNode—— 89] ‏همه‎ 05 6 oD oE| 0 temp while( temp > link != curNede) temp = temp > link; 

صفحه 23:
a حذف عنصر از لیست پیوندی-ادامه curNode—— 89] ‏-ك إؤزه- همه‎ ١ 6 0 oE| 0 ‏او‎ ‎temp temp > link = cur > link; Free(curNode); 

صفحه 24:
Se حذف عنصر از ابتدای لیست پیوندی ——eurNode 9 8] ‏همه‎ 98 15 oD oE| 0 Node *curNode curNode=fret; 

صفحه 25:
a حذف عنصر از لیست پیوندی-ادامه ۳ curNode first ‏اذه‎ 8 6 oD oE| 0 لا first = curNode ‏تعلصتاجد‎ ‎Free(curNode) 

صفحه 26:
8 شبه كدي بنويسيد كه در يك ليست بيوندي اكر ديه كره اي اشاره کرده با شدگره بعداز آن را حذف کند { *P (p Doon ==Ou) Prt P ("con wot recover") ۲ Oke | { lise] oy Se 0 {o 6 ‏سوبلم‎ ‎EP Dex; 1 @ Due ‏ی 3 و‎ 3 Pree (9); } } 

صفحه 27:
:ليست مريتب ليستي كه درآن عناصر كوجكترقبل ازعناصر بزركتر قرار كرفته باشند . بنابراين اكر بخولهيم عنصر جديدي به آن لضافه کنیم مي بایست به گونه ای باشد که ترتییش هم نخورد. > Null مى خولهيم شبه كدي براي درج يك عنصر جديد در داخل ليست مرتب بنويسيم . -1) عنصر جديد از تمامي عناصر ليست كوجكتر است . -© مقدار جديد به كونه اي است كه در ميان ليست قرار مي كيرد. >| 18 | 15 > 12 -© عنصر جدید از تمام عناصر لیست بزرگتر است. list] 

صفحه 28:
SS ‏با‎ ‏(دم حصا عم مه‎ ‏وت تا‎ ‏ع2‎ ‎1 ‎Pelt, ‎et > Dex; } Ohde (gD iePo < x && gf =u) { pP=p 00: Fu Orn; } keer (7, x) } 

صفحه 29:
SS ets wr ‏ليست پیوندی خطی با گره راس‎ ‏در برخي مواقع براي اينکه درج یکسان درآید ( همواره به صورت جوالب) يك گره اضافه به نام‎ ‏گره راس درابتداي لیست درنظرمي گیریم حتي زماني که لیست پيوندي تهي است وگره راس‎ ‏موچود است.‎ ‎he‏ | 2 10 6 1 5 میور ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‏بخش 10427 دركره راس دربرخي موارد بلااستفاده قرار مي كيرد و در برخي ديكر از موارد اطلاعاتي ‏از ليست بيوندي در كره قرار مي كيرد مثلا مي توان تعداد كره هاي موجود را در آن ثبت كنيم. ‏و در برخي ديكر كره راس مي تواند دو اشاره كر يكي به ابتدا و ديكري به لنتها ي ليست بيوندي داشته باشد. ‎ ‎ ‎ 

صفحه 30:
Sh ‏ليست عمومى‎ ليست عمومى ليست بيوندى است كه فيلد اطلاعات در هر يك از كره هاى آن مى تواند بر حسب نیاز اشاره كر باشد. ساختار هر كره اين نوع ليست به صورت زير است: علط وه ۰ 3 2۵ بو لیست های عمومی را می توان به فرم پرانتزی نمایش داد. شکل صفحه 060 معمولا لیست های عمومی برای نمایش درخت ها به کار میروند. 

صفحه 31:
Se ‏چندین مورد از کاربردهای لیست پیوندی‎ ‏نمايش چند جمله ای ها به صورت ليست ييوندى‎ #* پیاده سازی پشته به کمک لیست پیوندی * پیاده سازی صف به کمک لیست پیوندی 

صفحه 32:
7۳۳۳۳22 نمایش چند جمله ای ها به صورت ليست ييوندى از لیست هاي پيوندي مي توان براي پیاده سازي چند جمله ایها استفاده کرد در اين صورت هر گره شامل سه بخش خواهد بود. هلام ستول فرض كنيد دو جند جمله أي دلريد و مي خواهيد آنها را با هم جمع كنيد. 7] بر 46+0- ونين + وم 5 33 ‏بل‎ 2 4 Nutt 3 4] ‏بلاء‎ > 2] 2 A) 7 PL na OP O-PLO+OPPIOLE tot] > : هنگام جمع دو چند جمله اي حالتهاي زیر مي تواند وجود داشته باشد دو جمله ليکه با آن‌مولجهه هستیم هم توان‌باشند «ضرلیببا هم جمع. شوند وهردوجمله راپشه .سرمىكذاريم . یکیاز جملاتتوانب يشتريبارد آن‌جمله لتخاببشده و پشتسر گذلشته می‌شود(0 لاه | 4 بل ۶ |بلا2 4+ او م2 3۳3 6 5 ‎Hist]‏ 

صفحه 33:
Se pated; Fe; beO=Crt wee (); ٩۴ ‏و << م)‎ ( { ‎Dep >‏ مسر بو پ + و جرحید هصر 0 < محم ‎a> Dent, ‎} ‎Cte P (Pp D> 9 D1) { ‎Fp >t;‏ درا << معود ‎be‏ ‏:0< محم 

صفحه 34:
Se } be { ‏و-< هونا‎ < ‏بو پحرد مسر‎ ‏وتو‎ << bO; Ode (p! =O && o! =Oul) { AP (p DE =q D1) { thor (r, 7p Dz +492, 7 >); ‏مرحم‎ <0 a Dw, ‏عردم‎ <0 

صفحه 35:
Se Obe P (p Dt>q D1) { ‘eoPer (r, 7 D2, 7 D1); r=r> Orn, ‎Orn;‏ م عم ‎} ‎Ober ‎{ ‏و شتا‎ 32,991); ‏کر‎ 04 ‏تسم‎ ‎} ‎Whokde ‎“P (p! =u) ‎{ ‎Ode (p! =Oud) ‏{ ‏زد و راو ور لت 

صفحه 36:
SS ‏با‎ :0< عر حر ‎Orn;‏ < مجم } } *P (gl Oud) { ‎(a! =Oul);‏ ع ‎(r, 5 1,45 D2);‏ لیا ‎r=r Orn;‏ 2004 و که ابا( } 

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

صفحه 38:
پشته های پیوندی * با استفاده از لیست پیوندی این استراتژی را پیاده سازی کنیم. ‎Glas "‏ طور که می دانید در پشته ورود و خروج داده ها از یک طرف انجام می شود. top 0 

صفحه 39:
ج در پشته درج در با ‎es‏ ‎x a‏ GL top D c B 2۱0 top E 1D 0 B Alo پیاده سازي تابع ا۳): ‎pusk (ade *T op, olrar x)‏ و0 { ‎Onde *p;‏ ‎@=Crt we ();‏ محوی جح ‎P Dvext=Top}‏ ‎‘P=;‏ 

صفحه 40:
حذف از پشته top 

صفحه 41:
حذف از پشته-ادامه top E D 09 |B 5۱0 top D 6 B A|O delete temp; 

صفحه 42:
Pop ‏پیاده سازي تابع‎ co (sede *Top) Qo *texnp; Oker x} “P (ew (Top) ‏بمب‎ P ("stacks t erp"); ‏عط‎ ‎1 ‏ات‎ ‎Vop= Top > vex; x=tewp > KP; Cree (tewp); Returc (x); } 

صفحه 43:
صف های پیوندی 8 همان طور که می دانید در استراتژی صف ورود اطلاعات از یک طرف و خروج اطلاعات از طرف دیگر است. * به اين دلیل به دو اشاره گر به نام های و و مرس نیاز داریم. ront rear ۱ 

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

صفحه 45:
پیاده سازي تابع بح ‎Ovid ewert (ade *r , char x)‏ { Onde *P; ‎front] rear‏ :0 طح د0د© ح- ‎PDnPo=x;‏ ‎CP Dux, *P (==Ou) ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ye a7 ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 46:
Rewove ‏پیاده سازي تا‎ Ober Rewove (ate “Prow) Qode *pr; CrovProd Doe; Pree(prr); 

صفحه 47:
معايب بياده سازي صف و يشته با استفاده از ليست هاي بيوندي:. ‎ad‏ كره در ليست بيوندي از هر سلول آرايه فضاي ب -©مديريت ليست هاي بيوندي نسبت به آرايه مشكل تر است. مزاياي ليست بيوندي نسبت به آرايه ها : علاوه بر آنچه که كفته شد در ليست هاي بيوندي درج و حذف از ميا نه ي ليست بيوندي به سادگي امکان پذیر است اما در آرایه ها هر عمل درج و هر عمل حذف نیاز به 94 دادن عناصر آرایه دارد مزاياي آرایه نسبت به ليست بيوندي : sepa ‏شكل مستي امأ مي 5و أها در إويمت‎ ed ae ‏رسيدن به كره ام مي بایست مب گره پشت سر آن پیمایش شده باشد‎ 

صفحه 48:
اي ‎EE‏ ‏:ليست هاي پيوندي حلقوی اگر اشاره گر خارج شده از آخرین گره به جاي ان( به گره ابتدليي اشاره کند ساختار جديدي به نام ليست بيوندي حلقوى يديد مي آيد. در ليست هاي بيوندي حلقوى به خاطر بسته بودن ليست مي توان لز هر نقطه ليست به نقاط ديكر دسترسي بيدا كرد. a ar ‏براي آنكه مدیریت لیست ساده تر انجام شود اشاره گر خارجي به لیست را روي آخرین گره فرض مي‎ ‏کنیم در نتیجه گره ي بعد از آن» گره ي اول خواهد بود.‎ ‏به وسیله ي لیست هاي دایره اي میتوان پشته ها وصف ها را پیاده سازي کرد.‎ : ‏پشته ها درلیست هاي پيوندي دایره اي‎ 9۰ 

صفحه 49:
Obtd pusts (etacts, x) p=Bet wde (); 

صفحه 50:
Cher pop (pth) { stack AP (stack == Oul) 7 1 a 1 a Orict P (“stack t& exopty); Oke { stack @= vtack Orn; a tha Grack DOexep > Orn; ‏بطم < مدلا‎ stack AP (p==stack) = Grack=Oul; (Ww) rez (P); Retura (x); stack } } 

صفحه 51:
۹۹۰۰۰۰ پیاده سازي صف ها با استفاده از لیست هاي پیوندی دایره لی پیاده سازي تابع بو : ۳ 1 3 سح تا مه : [ 1212 یی ‎po Kot x -‏ 4 آم ‎4B (que! =Oul)‏ 7 002 2 ‏صصب‎ Orn; 9 0 

صفحه 52:
بياده سازي تابع ‎Rewove‏ 1 Oke rower (qe) ۴ ‏صهم)‎ << 0( rit P ("queue ts ewe"); 04 صصمکم ‎ee wx 04‏ :6< مدلا (صصجححم) ع4 :ك0 <د عصو ‎Pree ();‏ ‎Retws (x);‏ 

صفحه 53:
EEE ‏:ليست هاي پيوندي دوطرفه‎ ‏يكي از مشكلات بزرك ليست هاي يك بيوندي (خواه خطي باشد خواه دايره اي ) آن است كه امكان‎ ‏بيمايش معكوس در آن ها وجود ندارد اين مشكل به وسيله ي ليست هاي دو بيوندي قابل حل است.‎ ‏ليست هاي دو بيوندي را كاهي ليست هاي بيوندي دو طرفه نيز مي كويند.‎ : = شكل هر كره در ليست هاي دو بيوندي به شكل زير است. 14 او« ‎Jette‏ نکته : اشاره گر هاي ‎6٩:‏ ,درا را در بعضي کتاب ها به ترتیب مرو( , ‎od Prov‏ کرده اند. همان طور که گفته شد در لیست ها ي دو پيوندي مي توان از هر نقطه به گره بعدي ویا قبلي دسترسي بيدا کرد.لز جمله كارهايي که به سادگي مي توان روي ليست هاي دو طرفه انجام داد حذف مستقيم كره اي است كه م بدان اشاره مي كند. به عنوان مثال در يك ليست دو بيوندي مجموعه دستورات زير باعث حذف كره م مي شود. 

صفحه 54:
طاح مدب ماب مه ‎b Dright =r; =| al ۳ aw‏ 5 4 53 R Dera; Xp < ‏بوم‎ ‏سب‎ )۲( فرض كنيد خواسته باشید در يك لیست دو پيوندي سمت راست گره ای که به آن اشاره شده گره جديدي .را درج كنيم :() ع 9-60 بحو 1< © ‎tH‏ ان انس 5 2 و عر ‎i r+‏ 7 7 هچ و 5 ماد و برد 7 ماد 6 3 

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

صفحه 56:
(cur > right) > left= cur > left; first 

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

صفحه 58:
حذف از ليست دوطرفه بدون تعریف اشاره گر 1 ١ ‏شالك‎ 4 

صفحه 59:
حذف از ليست دوطرفه بدون تعریف اشاره گر cy 2 ۳ 

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

صفحه 61: