ساختمان داده با صف و پشته

صفحه 1:
يس اختهحمات داده ها يا ننى تشار ديه 0 Data Structures 

صفحه 2:
رت درس ساختمان داده ها پشته: ساختمان دای است که عمل حذف و اضاقه از یک انتتباى آن به نام بالاى يشته [10[0) صورت مى كيرد. 51لا قرار ثلان اطلاعات در بالاى يشته 0 برداشتن اطلاعات از بالای پشته ‎te‏ اعداد ۲۰۱ و۳ را ورد یک پشتهمی‌کنم وبه ریب ۳ ۲و | آ‌ا راز شتهخارج م‌کنيم. ‎3 ‎2 2 2 1 1 1 1 1 ‏كسم ب‎ 1 push2 push3 pop3 ۱02 1 ‎1,2,3 1 ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 3:
موضوع : پشته درس ساختمان داده ها ۲ با پشته 01 لیستی است که اعمال ورودی و خروجی یا اضافه و حذف در آن از یک طرف لیست انجام می‌شود. به این ‎First Owt (IFO) cd gl 4 cae‏ 110 184 می‌گویند. بدین معنی که آخرین ورودی به پشته , اولین خروجی خواهد بود. عنصر بالابی پشته را 10 پشته می‌گویند. با افزودن داده روی پشته , متغیر ]0 یکی زیاد شده و داده در محل 00) از پشته قرار می‌گیرد. برای خارج کردن یک عنصر از پشته نیز دادهای که در محل 108 قرار گرفته از ‎٩1۵016‏ خارج م ىكردد و متغير 16 یکی کم می‌شود. مقدار اولیه 105 صفر است و با افزودن داده به یک پشته 1 عضوی , 100 می‌تواند تا پشته خالی است ‎Top =0 SS‏ يشته يراست 4217 ‎Top =n‏ مقدار 2 تغيير كند. 

صفحه 4:
موضوع : درس ساختمان داده ها پشته (اهدای) پشته یک نوع داده مجرد (۵۳7) است که در اکثر زبان‌های برنامه‌نویسی کاربرد رایجی دارد. دلیل این که این نوع داده. پشته نامیده شده. این است که از نظر ظاهری شبیه پشته است. یعنی به یک دسته از بشقاب‌های روی هم شیاهت دارد یک پشته در دتیای واقعی امکان انجام کارها را تدها از یک سمت فراهم می‌کند. برای نموته شما تنها می‌توانید کارت‌ها را روی دسته کارت‌ها بگذارید يا از روی آن بردارید. به طور مهایه ۸07 یهته نیز امکان اجرای عملیات‌های روی داده را تنها در یک سمت ارائه می‌کند. ما در هر زمان تنها به عناصر فوقاتی پشته دسترسی داریم. اين ويزكى باعت می‌شود که پشته یک ساختار داده ۱۱۴۵ باشد. ۱۱۴0 اختصاری برای عبارت ‎Lastintirst-out‏ ‏است بعتی ورودیآخر خروجیاول. در اصطلاح‌شناسی یشته عملیات درج به نام عملیات ۴۸5۲۱ نامیده و عملیات حذق به نام ۳08 خوانده می‌شود. 

صفحه 5:
موضوع : صف درس ساختمان داده ها صف: ساختمان دادهای است که عمل حذف از یک انتهای آن به نام سر صف (۲0130) و عمل اضافه کردن از انتهای دیگر آن به نام ته صف (11621) صورت می‌گیرد. اولين عنصرى که وارد صف مى شود اولين عنصرى است كه از صف خارج مىشود. بنابراين عناصر به همان ترتيبى كه به صف اضافه مىشوند از آن حذف مىشوند. به همين دليل به صف ليست [ 15151 ,111511 ogo. af 5 Out) FIFO سرصف > FIFO First In, First Out 

صفحه 6:
موضوع : صف درس ساختمان داده ها صف ليستى است كه عمل افزودن دادهها درون آن از يك طرف ليست يا انتهاى ليست و عمل حذف ها از سمت ديكريا ابتداى ليست انجام می‌شود. صف را لیست ‎(First In First Out) FIFO‏ می‌نامند: زیرا اولین عتصر وزودی , اولین عنصر خروجی از صف نیز هست. در ساختمان داده صف دو متفیز ات و عععد به عرتیب برأی نشان دادن جلو. و اتتهای صف یکار می‌روند. ضف: را می‌توان:با استفاده از آرایه‌ها یا لیست‌های پیوندی پیاده سازی کرد. اگر صف را آرایه‌ای 0 عضوی از عناصر بدانیم مقادیر 00101 و 1682 می‌تواند از صفر تا 10 تغییر کند که برای صف در ابتدا مقادیر اولیه صفر را برای 1۳0101 و 1:61 تعریف می کنیم. 0 = ‎front = rear‏ در صورتیکه متفیر 170101 با 1685 برایر باشد صف خالی است و در صورتیکه ۲087 برایر با 0 باشد صف rear =n ‏بسع لانت جح‎ front = rear god I Js پر است. 

صفحه 7:
انیت 29 صف یک ساختار داده است که تا حدودی شبیه پشته محسوب می‌شود؛ اما بر خلاف » صف از هر دو سمت باز است. از یک سمت همواره برای درح داده‌ها و از سمت دیکر برای حذف داده‌ها استفاده می‌شود صف از روش ۴۱۴0 (ورودی اول-خروجی اول) استفاده می‌کند. در این روش هر داده‌های که اول در صف ذخیره شود. هنكام خروج نيز قبل از همه خارج می‌شود > تت نمونه‌ای از صف در دنیای واقعی می‌تواند یک خیابان یک‌طرفه باضد که در آن وسایل نقلیه‌ای که اول وارد خیابان شده باشند. قبل از بقیه از آن خارج می‌شوند. متال‌ها زیادی از صف در دنیای واقعی می‌توان مشاهده كرد. از صف‌های خرید بلیت تا ایستگاه‌های اتوبوس, ن داده ه 

صفحه 8:
رها( درس ساختمان داده ها کاربردهای پشته و صف : ۱- دریافت و نمایش مقادیر با ورود و خروج داده های محدود و تصادفی ۲- سیستم عامل و هوش مصنوعی و شبیه سازی و شبکه های کامپیوتری ۳- محاسبات عبارتهای حسابی با ریاضی 

صفحه 9:
کار شمه در ‎i)‏ عباراتة بكى أ[ كا بردهاى ميم بشته ‎cle aula oll abl‏ به سه شكل توشنه م شوند به ‎gly» ee gs‏ جمع لو متي أو لأ در نظ بكيريلة ‎ale ba loses aug Slee olnfx) ibe ce‏ ۸۱۶ ۸۱+. ‏در سمت راست عملوندهاى خوذ قرار‎ alas {POsttix) uigay Le FAB ‏عبارت ييشوندى [(2]011]: عملون در سمت چپ عملندهای خود رز دار‎ 

صفحه 10:
رت وج درس ساختمان داده ها در ادامه نمودار يك يشته و عملياتهاى آن ارائه شده است: ب هر ‎Last In - First Out‏ | ‎Pop‏ Push پشته می‌تواند به وسیله آرایه‌ها. ساختار. اشاره‌گر و لیست پیوندی نمایش بابد. پشته می‌تواند دارای آندازه ثابت ‎AY‏ و یا اندازه آن به طور دینامیک تغییر یاید. 

صفحه 11:
درس ساختمان داده ها عملیات‌های ابتدایی ] سم> [ردی بشته) عملیات‌های ابتدابی ممکن است شامل راه‌اندازی اولیه پشته. استفاده و تخریب آن باشد. علاوه بر آن وفتی عنصری در پشته قرار می‌کیرد. معمولاً از اين دو عملیات ابتدایی استفاده می‌شود: ۰ (۳۵: خهیرفسازی یک غتضر در یهده * ()۳۵2: حذف (دسترسی به) یک عنصر پشته برای استقاده بهینه از یک پشت باید وضعیت آن نیز بررسی شود. به این منظور کارکردهای زیر به پشته اصاقه شده‌اند ۶ ۳۵۵۲۵ دریافت بالاترين عنصر يشته بدون حذف أن ‎TOFU) ©‏ بررسی بر بودن يشته ‏* 5۴۳۵ا: بررسی خالی بودن يشتم ما باید هر زمان یک اشاره‌گر به آخرین داده ۵50 شده به يشته در اختیار داشته باشیم. از آنجا که این اشاره‌گر ‏همواره به عنصر فوقانی پشته اشاره می‌کند. نام آن ۱02 تعیین شده است. اشاره‌گر 100 بالاترین مقدار پشته را ‏بدون حذف آن به دست می‌دهد ‎ 

صفحه 12:
موضوع : بشته درس ساختمان داده ها قرایتد قرار دادن یک عتصر جدید در پشته به نام عملیات دم شناخته می‌شود. عملیات پوش شامل یک سری از مراحل است: * گام ۱: بررسی کن که پشته پر است یا نه. * کام ۰۲ اگر يشته پر باهد. اعلام خطا کرده و خارج شو * کام ۳: آگر يشته یر نبود. مقدار 16 را یک واحد افزایض بده تا به فضای خالی بعدی اشاره کند. * عنصر داده‌ای را به موقعیت مورد نظر در پشته اضاقه كن. 0 ‏ا‎ Push Operation * کام ۵: يام موفقيت را بركردان. 

صفحه 13:
سرت درس ساختمان داده ها یک الگوریتم ساده برای ععلیات «ادنام را می‌توان به صورت زیر توشت: پیاده‌سازی الگوربتم در زبان 6 0 24 £ top = tep + 4: stack[top] = data; y else f printf€"Could aot insert data, Stack 1s full n>; 

صفحه 14:
سرت درس ساختمان داده ها عملیا دسترسی به محتوای پشته در هنگام حذف آن. به نام عملیات 5۲م شناخته می‌شود. در پیاده‌سازی آرابه‌ای از عملیات ۴۵۴00 عنصر داده‌ای واقعاً حذف نمی‌شود. بلکه به جای آن مقدار ۶۵۶ یک واحد کاهش می‌یاید تا به مقدار کمتری در پشته اشاره کند. اما در پیاده‌سازی لیست پیوندی عملیات (0680 واقعاً عنصر داده‌ای را از قضای تخصیص يافته پشته پاک می‌کند. یک عملیات 86۳ می‌تواند شامل گام‌های زیر باشد: » كام ‎:١‏ بررسی کن که پشته خالی است یا نه کام ۲: اکر پشته خالی بود يك خطا اعلام كن و خارج شور كام ۳: اگر پشته الى تبود: عتصر دادماى را كه 00 مورد اهاره قرار می‌دهد برگردان. كام ©: مقدار 50۳ را یک واحد کم کن. كام ©: يمام موفقييت را بازكردان. Pop Operation Ff = top 

صفحه 15:
بر وتا درس ساختمان داده ها الگوریتم عملیات ۲۳ یک الگوریتم ساده برای عملیات 292 می‌تواند به شکل زبر باشد. پیاده‌سازی الکوریتم در زیان 0 Stack 1s empty.\n">: int postine dated £ > سیم تممص م - ممه - ممع د ‎sop‏ return data: teu’ DrEnceC"Could not retrieve data. 

صفحه 16:
عملیات‌های صف می‌تواند شامل راه‌اندازی یا تعریف استفاده و سپس حذف کامل آن از حافظه باشد. در ادامه تلاش خواهيم كرد تا عملیات‌های 1 ابی مرتبط با صف‌ها را بررسی کنیم: * (6006/060: یک آیتم را به صف اضافه (ذخیرم) می‌کند. * (0عباعبوعاه: یک آینم را از صف حذف می‌کند (مورد دسترسی قرار می‌دهد). چند کارکرد دیکر نیز هستند که برای کارآمدسازی عملیات‌های فوق در صف ضروری هستند: * (الاگاز پر بودن صف را بررسی مي‌کند. ‎:isempty() ©‏ خالی بدون_صف را بررسی_مي‌کند. ‏در صف همواره با استفاده از اشاره‌گر *۲08] داده‌ها را حذف می‌کنيم (مورد دسترسی قرار می‌دهیم) و با استفاده از اشاره‌گر ۲۵۵۲ آن‌ها را اصافه می‌کنيم. ابتدا کارکردهای پشتییانی یک صف را بررسی می‌کنیم: ‎ ‎ 

صفحه 17:
موضوع : صف درس ساختمان داده ها اپیاده سازی صف با آرایه: صف را می‌توان توسط یک آرایه یک بعدی پیاه‌سازی کرد. به دو متفیر 3101 و 1162 برای مشخص كردن ابتدا و انتهاى صف نياز است. هر گاه عنصری به صف اضافه شود 1160۲ یک گام به جلو حرکت می‌کند و هر گاه که عنصری را از صف حذف می‌شود ۳0116[ یک واحد افزایش می‌یابد. چون اندازه آرایه از قبل تعریف می‌شوده هنگام اضافه کردن عنصری به صف ابتدا باید اطمینان حاصل کرد که هنوز ظرفیت پذیرش داده را دارد. اگر 18601 برابر با ظرفیت کل آرایه شود صف پر در نظر گرفته می‌شود. اگر ابتدا و انتهای صف برابر ‎Soe cou! Ib Go Qe (Front = Rear) srg‏ حذف روی صف خالی انجام نمی‌گیرد. طول صف يا تعداد عتاصر موجود در صف برابر با ‎cus! Rear-Front+1‏ ‎ols (Front) f‏ اندیس خانه خالی در صف است. 11-1 ۲ (3631]): شامل اندیس خانه پر ته صف است. 

صفحه 18:
موضوع : صف درس ساختمان داده ها صف‌ها دو اشارگر داده را نگه‌داری می‌کنند که ۲۳۵6 و 0۵۴ دام دارند. از آين رو پیاده‌سازی عملیات‌های آننها نسبت به يشتدها كاملا پیچیدمتر است. در ادامه گام‌هایی که برای ذخیرمسازی با درج یک داده در صف مورد نماز است را می‌بینید © كام 1: بررسی کن که آبا صف پر است با نه. کام ۷+ کر ضف ير يود خطای ‎overflow‏ را صادر کرده و خارج شفر * کام ۱۳ کر صف پر نبود.مقداراشاهکر ۵۵۲ را یک واحد افزایش بده تا به ای خالی بعدی ‎AS hl‏ کام ۴: عنصر داده‌ای را یه موقعیت صف که اشارهگر ۲6۵1 نشان می‌دهد. اضافه کی * کام ۵ ام موفقیت يا بانكيدان. Queue Enqueue 

صفحه 19:
int f=r=-1; void InsertQueue (int Q{] ; int n; intx) i if ((f== (C+ 1) %n) || (f==-1 &&r==n-1)) { cout << "Queue is Full"; return; } ۲< )۲+ 1( 0 ۲ Qh] =x; 

صفحه 20:
موضوع : صف درس ساختمان داده ها GARE ley Sate Gas ene oa ae pha a) Uae ios gos oes eee ‏خوط بد‎ ‏دسترسى. كامهاى زبر براى اجراى عمليات عناصاو02 مورد بر هستند.‎ * کم بررسی کن که صف خالی است با * كام :اک صف خابی بود ای +۵۳۵ را صادرکرده و خارج شور + کام :کر صف خالی نیو به ناذماى كه اشاردكز 19004 نشان ميدهد. دسترسی ایجاد كن * كام ؟: ‎ola‏ 9400 را يك واحد افزايش بذه تا به موقعيت بعدى اقاره ند » كام 6: ييام موظيت را بازكردان. Queue Dequeue 

صفحه 21:
موضوع : صف درس ساختمان داده ها ‎int RemoveQueue (int QJ] ; int n)‏ 1 ‎if (f==r)‏ { ‎cout << "Queue is Empty";‏ ‎cexit ();‏ } f=(f+1)%n; return Q[f]; 

صفحه 22:
موضوع : پشته و صف درس ساختمان داده ها تجزیه عبارت‌های حسابی روش نگارش عبارت‌های حسابی به نام نمادگذاری (0016005) نامیده می‌شود. عبارت‌های حسابی را می‌توان به سه روش نمادگذاری مختلف؛ اما معادل هم نوشت. يعنى بدون تغيير دادن مفهوم يا خروجى عبارت. اين نمادگذاری‌ها به صورت زیر هستند: * نمادگذاری میانوندی (0) * نمادگذاری پیشوندی (۶1۵10) مسسسسته * نمادگذاری پسوندی (۳۵9/7) مسر 

صفحه 23:
موضوع : پشته و صف درس ساختمان داده ها تمادگذاری میاتوتدی ما زمانی از نمادگذاری میانوندی برای دوشتن عبارت‌های حسابی خود استفاده می‌کنيم که عملگرهای مورد. استفاده میان عملوندها قرار گرفته باشتد. برای مقال ۵ + 5 + 8. نوشتن و خواندن عبارت‌های حسابی به روش میاتوندی برای ما به عنوان اتسان آسان‌تر است؛ اما در مورد ماشین‌های محاسباتی این وضع کمی فرق می‌کند. یک الگوریتم برای پردازش نمادگذاری میانوندی. بر حسب زمان و فضای مورد تیا برای محاسیات هرهوید»: اس این نوع از تمادگذاری به نام نمادگذاری لهستانی معکوس نیز شناخته می‌شود. در این سیک از نمادگذاری. عملكر يه عنوان یسوتدی برای عملوندها در نظر گرفته می‌شود. یسسی عملگر يس از عملوند توشته می‌شود. برای متال ۵5+ که معادل روش نمادگذاری میانوندی 9 + ۵ است و به نام نمادگذاری لهستانی دیز شناخته می‌شود. اين سبك از نمادگذاری به نام لهستانی معکوس نامیده می‌شود. در این روش. عملگر به صورت پسوند عملوندها توشته می‌شود. یعنی عملگر یس از عملوتد قرار می‌گیرد. برای مثال +28 معادل نماد گذاری میانوندی ط + و است. 

صفحه 24:
موضوع : يشته درس ساختمان داده ها infix postfix prefix ۱- پرانتز گذاری براى تبدیل به پیشوندی , درون هر پرانتز عملگر را به سمت چپ منتقل می‌کنیم. براى تبديل به پسوندی , درون هر پرانتز عمگلر را به سمت راست منتقل می‌کنیم. پرانتزها را حذف می‌کنيم. 

صفحه 25:
۲- برانتز بازرا در پشته تلا می‌کنيم. ۳- عملوندها را در خروجی می‌نویسیم. ؟- در صورتيكه به يك عملكر رسیدیم اگر 10 يشته داراى عملكرى با اولویتبیشتر یا مساوی نبود آنرا الا[ می‌کنیم در غیر ایتصورت عملگر ۱00 پشته را 001 كرده و در خروجى می‌نویسیم. - هركاه به يرانتز بسته رسيديم أنقدر 0010 مىكنيم تا به اولين برانتز باز برسيم. 

صفحه 26:
ا درس ساختمان داده ها ‎lms GLO IS‏ دردیب "عملگرهای یک عبات ‎coli‏ را با استفاده: از پانتز تغییرآداد برای نمونه در عبارت ه * 5 + ۵ بخش ۰ * ط ابتدا ارزیابی می‌شود. چون ضرب نسبت به جمع نقدم دارد. اما اکر به صورتزیر از پرانتز استفاده کنیم. می‌توانیم کاری کنیم که ۵ + 8 ابتدا ارزیابی شود: (atb)*e ایتک می‌توانیم الکوریتم روش ارزیابی نمادگذاری پسوندی را بررسی کنیم: * گام ۱: عبارت را از سمت چپ شروع به اسکن ‎OF‏ ‏* کام ۲: اکر عملوندی وجود داشت. آن را به یشته بفرست. کام ۳: اکر یک عملگر وجود داشت. عملوند را از پشنه فراخواتی کرده و عملیات را اجرا کن. گام ۴: حروجی گام ۳ را دوباره در پشته ذخیره کن. کام ۵: عبارت را تا زمانی که همه عملوندها مصرف ودند ادامه بده. کام ۶ عملیات 260 را روی پشته انجام بده و عملیات را تکمیل کن. 

صفحه 27:
متسر مثال: ارزیابی عبارات محاسباتی درس ساختمان داده ها ‎i‏ 3 مال ل) براى عبارت میانوندی زیر عبارت پسوندی و پیشوندی را بنویسید. 

صفحه 28:
موضوع : پشته و صف بد مت postfix = ۳ cay) x+(be)/)= abea Tx +be/- prefix = —+axb Pca/be 

صفحه 29:
موضوع : پشته و صف درس ساختمان داده ها سه روش نمادگذاری نماد گذاری پسوندی نماد گذاری پیشوندی ‎tab‏ ‎(atbyec‏ ‎a*(b+0)‏ ‏2۵ ‏(۵ +ع) +( +6 (@+b)+e)-d