پشته و صف پیوندی

صفحه 1:
پشته و صة پیوندی 

صفحه 2:
رئوس مطالب *مشگل: چه کار کنیم که لیستهای پیوندی کارآمدتر شوند؟ " لیستهای دو پیوندی " پیاده‌سازی لیست پیوندی پشته *پیاده‌سازی ‎cand‏ پیوندی صف دقت کنید که قبلاً نسخه ی آرایه ای صف و پشته را دیده‌ایم. 

صفحه 3:
مشكلات ليست تک ‎Sign‏ head tail فقط در یک جهت می توان حرکت کرد. *_ درهنگام حذف با اضافه کردن باید نود قبلی را به خاطر داشته باشیم. *_ در کدنویسی باید حواسمان به ابتدا و انتهای لیست باشد که منجر به توليد 14 های زیادی می شود. 

صفحه 4:
Oo) ‏هو‎ ji. ou | ۱ previ 5 (106 

صفحه 5:
بود:‌ساخنگی “اعمال حذف و افزودن راحتتر خواهند بود. چون هميشه در وسط ليست اتفاق مى افتند. dummy head dummy tail node node 

صفحه 6:
ایجاد یک لیست پیوندی دوپیوندی *نودهای ‎head‏ وا را ایجاد کنید. * tNode.prev = hNode * hNode.next = tNode 

صفحه 7:
ادامه ... (ایجاد لیست دو پیوندی)) مقدار 7620 را برابر ۱۵06 و 2 را برابر 6 قرار دهید. 

صفحه 8:
افزودن یک نود جدید اضافه كردن نود جديد بعد از نود م. tail New node 

صفحه 9:
ادامه ... (افزودن یک نود جدید) * مقدار پیوند 076۷ نود جدید را برابر 2 قرار دهید. p tail New node 

صفحه 10:
ادامه ... (افزودن یک نود جدید) ؟ مقدار 71626 نود جدید را برابر 0.06۷۶ قرار دهید. ite im! New node 

صفحه 11:
ادامه ... (افزودن یک نود جدید) * مقدار 0./166:/0۲6۵۷ را برابر نود جدید قرا دهید. tail 

صفحه 12:
ادامه ... (افزودن یک نود جدید) " مقدار 0.77626 را برابر نود جدید قرار دهید. 

صفحه 13:
کد مربوط ‎a:‏ افزودن نود جدید public void Insert(DNode p, Object item) 1 DNode newNode = new Dnode(p, p.next, item); newNode.next.prev = newNode; p.next = newNode; count ++; 

صفحه 14:


صفحه 15:
ادامه ... (حذف یک نود) " مقدار 0./162.076۷ را برابر ۵.0۲6۷ قرار دهید. p tail 

صفحه 16:
ادامه ... (حذف یک نود) ؟ مقدار 0۰۵۲۵۷۰76۵۲۴ را برابر ۵.06۷ قرار دهید. p tail 

صفحه 17:
ادامه ... (حذف یک نود) " حال می توانید نود 0 را حذف کنید. tail 

صفحه 18:
کد حذف نود Object remove(DNode p) 1 Object item = p.value; p.next.prev = p.prev; p.prev.next = p.next; count --; return item; 

صفحه 19:
ليست مدور *آخرين لينك به اولين لينى بر مى كردد. - يعنى بيوند آخرين لينك به اولين نود اشاره مى كند. 

صفحه 20:
بیاده‌زساری رلیست پجوندی یه 9 دیگر نیازی به دانستن حداکثر اندازه ی پشته نداریم. © هرجا لازم شد به نود جديد حافظه تخصيص مى دهيم. 9 م رد "اب 0 3 top .يشته همراه با افزومن يا حذف بزرگ و کوچک می شود stack 

صفحه 21:
پیاآده‌ساری لسیب :پیویدی بطلجه. " نودها به ابتدا اضافه می شوند. " نودها از ابتدا برداشته می شوند. 

صفحه 22:
Push Joc ؟اضافه کردن یک عنصر به ابتدای پشته 

صفحه 23:
(... aolol) Push Joc * ایجاد نود جدید با مقدار ۵. *پیوند دادن نود جدید به ابتدای پشته. New node——? d null New node 

صفحه 24:
(... aolol) Push Jos * مقدار 0۴ باید به نود جدید اشاره کند. 

صفحه 25:
Pop ‏عمل‎ 

صفحه 26:
LinkedStack Implementation public class LinkedStack implements StackPT 1 //instance variables ۱۱۵۲۱۷۵۸۵ methods, classes //public methods 11 

صفحه 27:
‎ool,‏ سازى ليست ييوندى صف ‎ ‏؟دو عملکرد اساسی: ‎wae tail a492)S adlol :Enqueue *‏ ‎«auc head j19i> :Dequeue * ‏*عملکردهای دیگر: ‎isEmpty *‏ ‎isFull *‏ ندایيم. ‎5126 

صفحه 28:
خلاصه ليست ييوندى " حافظه ی مصرفی به اندازه ی مورد نیاز است. *کار با داده ها (مثل افزودن و حذف) کارآمدتر است. *از آرایه بهتر است. ؟ کار با لیست دوپیوندی راحتتر است. " می توان پشته و صف را با لیست پیوندی پیاده کرد. 

پشته و صف پیوندی رئوس مطالب °مشکل :چه کار کنیم که لیستهای پیوندی کارآمدتر شوند؟ °لیستهای دو پیوندی °پیاده‌سازی لیست پیوندی پشته °پیاده‌سازی لیست پیوندی صف °دقت کنید که قبًال نسخه ی آرایه ای صف و پشته را دیده‌ایم. مشکالت لیست تک پیوندی ‏tail ‏node3 ‏ ‏ ‏ ‏head ‏node2 ‏node1 فقط در یک جهت می توان حرک ت کرد. در هنگام حذف یا اضافه کردن باید نود قبلی را به خاطر داشته باشیم. در ک دنویسی باید حواسمان به ابتدا و انتهای لیست باشد ک ه منجر به تولید ifهای زیادی می شود. یک نود در لیست دوپیوندی .• هر نود دو ارجاع دارد Nod e previou s Node prev next followi ng Node valu e نود ساختگی °اعمال حذف و افزودن راحتتر خواهند بود .چون همیشه در وسط لیست اتفاق می افتند. ‏dummy head ‏node ‏dummy tail ‏node ‏nullnull ‏value ‏null null ایجاد یک لیست پیوندی دوپیوندی . را ایجاد کنیدtail وhead نودهای° null null null hNode null null null tNode . آنها را به هم پیوند دهید° • tNode.prev = hNode • hNode.next = tNode null null hNode null null tNode )) (ایجاد لیست دو پیوندی... ادامه را برابرtail وhNode را برابرhead مقدار° . قرار دهیدtNode tail hea d null null hNode null null tNode افزودن یک نود جدید .p اضافه کردن نود جدید بعد از نود° p head null tail node nullnull item null null New node ادامه ( ...افزودن یک نود جدید) °مقدار پیوند prevنود جدید را برابر pقرار دهید. ‏tail ‏nullnull ‏p ‏node ‏item null ‏New node ‏null ‏head ادامه ( ...افزودن یک نود جدید) °مقدار nextنود جدید را برابر p.nextقرار دهید. ‏p ‏tail ‏node ‏nullnull ‏ite ‏m ‏New node ‏null ‏head ادامه ( ...افزودن یک نود جدید) °مقدار p.next.prevرا برابر نود جدید قرا دهید. ‏tail ‏nullnull ‏p ‏node ‏ite ‏m ‏null ‏head ادامه ( ...افزودن یک نود جدید) °مقدار p.nextرا برابر نود جدید قرار دهید. ‏tail ‏nullnull ‏p ‏node ‏ite ‏m ‏null ‏head کد مربوط به افزودن نود جدید public void Insert(DNode p, Object item) { DNode newNode = new Dnode(p, p.next, item); newNode.next.prev = newNode; p.next = newNode; count ++; } حذف یک نود p حذف نود° p head null node tail nullnull ) (حذف یک نود... ادامه . قرار دهیدp.prev را برابرp.next.prev مقدار° p head null node tail nullnull ) (حذف یک نود... ادامه . قرار دهیدp.next را برابرp.prev.next مقدار° p head null node tail nullnull ادامه ( ...حذف یک نود) °حال می توانید نود pرا حذف کنید. ‏tail ‏nullnull ‏null ‏head کد حذف نود Object remove(DNode p) { Object item = p.value; p.next.prev = p.prev; p.prev.next = p.next; count --; return item; } لیست مدور °آخرین لینک به اولین لینک بر می گردد. – یعنی پیوند آخرین لینک به اولین نود اشاره می کند. ‏curre ‏nt ‏node3 ‏node2 ‏node1 پیاده سازی لیست پیوندی پشته ‏pop ‏D ‏top ‏E ‏B … 0 ‏A ‏stack پشته همراه با افزودن یا حذف بزرگ و ک وچک می .شود • دیگر نیازی به دانستن حداکثر اندازه ی پشته نداریم. • هر جا الزم شد به نود جدید حافظه تخصیص می دهیم. ‏push پیاده‌سازی لیست پیوندی پشته °نودها به ابتدا اضافه می شوند. °نودها از ابتدا برداشته می شوند. ‏pop ‏top ‏c null ‏b ‏a ‏push عمل Push °اضافه کردن یک عنصر به ابتدای پشته ‏c null ‏b ‏a ‏top عمل ( Pushادامه )... • ایجاد نود جدید با مقدار .d • پیوند دادن نود جدید به ابتدای پشته. ‏New node ‏d null ‏c null ‏a ‏b ‏d ‏top ‏New node )... (ادامهPush عمل . باید به نود جدید اشاره کندtop • مقدار top a b New node top c null d a b d c null Pop عمل حذف یک عنصر از پشته° top a top b a a b c null c null LinkedStack Implementation public class LinkedStack implements StackPT { //instance variables //private methods, classes //public methods //… } پیاده سازی لیست پیوندی صف °دو عملکرد اساسی: • :Enqueueاضافه کردن به tailصف. • :Dequeueحذف از headصف. °عملکردهای دیگر: • isEmpty • isFullنداریم. • Size خالصه لیست پیوندی °حافظه ی مصرفی به اندازه ی مورد نیاز است. °کار با داده ها (مثل افزودن و حذف) کارآمدتر است. °از آرایه بهتر است. °کار با لیست دوپیوندی راحتتر است. °می توان پشته و صف را با لیست پیوندی پیاده کرد.