آموزش ساختمان داده قسمت هفتم
به نام خدا
سلام عرض میکنم خدمت همه ی شما دوستان عزیز و ارجمند
ضیادید هستم و در خدمت شما خواهم بود با تقدیم قسمت هفتم آموزش ساختمان داده ها از سری آموزش های برنامه نویسی
در جلسه ی گذشته بحث پشته و صف رو ادامه دادیم و عبارات مختلف رو مورد بررسی قرار دادیم .
در این جلسه قصد داریم دو روش رو برای تبدیل عبارات پیشوندی و پسوندی به میانوندی بگیم به صورت خلاصه .. همچنین کمی درباره ی صف های حلقوی صحبت میکنیم و در آخر هم مقدمات لیست های پیوندی رو مطح میکنیم که موضوع جلسه ی بعدی ما خواهد بود .
2 روش رو در این جلسه میخوایم توضیح بدیم به طور خلاصه .. این روش ها عبارت هستند از روش پرانتز گذاری و روش پشته
برای روش پرانتز گذاری به صورت زیر عمل می کنیم :
1) اول کنترل میکنیم که تعداد عملوند ها یک واحد بیشتر از عملگر ها هست یا نه . اگه اینطور نباشه در عبارت ، عملگر یکانی وجود داره و ارزشیابی شرایط دیگه و خاصی خواهد داشت .
2- عبارت رو از سمتی بررسی می کنیم که با عملوند شروع میشه . در پسوندی از چپ و توی پیشوندی از راست بررسی می کنیم .
3- با رسیدن به هر عملگر ، دو عملوند برای اون در نظر می گیریم .
4- برای دو عملوند ، عملگر رو بین اونها قرار میدیم و براشون پرانتز در نظر میگیریم.
5- عبارت رو از سمت چپ به راست به ترتیب شامل عملوند ها و عملگرهای بین عملوند ها ارزیابی می کنیم.
اما روش دیگه ای که برای اینکار استفاده میشه ، روش پشته هست . با فرض دودویی یا باینری بودن عملگر ها ، به صورت زیر عمل میکنیم توی این روش :
1- عبارت رو از سمتی بررسی می کنیم که با عملوند شروع میشه . در پسوندی از چپ و در پیشوندی از راست.
2- عملوند ها رو توی پشته قرار میدیم و با رسیدن به هر عملگر (البته به جز آخرین عملگر) دو عملوند خارج میکنیم و بعد از محاسبه ، حاصل عبارت رو داخل پشته قرار میدیم .
3- به عملگر آخر که رسیدیم بعد از خارج کردن دو عملوند آخر و محاسبه ، اون رو دیگه توی پشته قرار نمیدیم و حاصلش رو در خروجی می نویسیم .
اما بحث بعدی این جلسه ، ارائه ی مطالبی درباره ی صف حلقوی هست . ببینید دوستان ، ما ممکنه اطلاعاتی درباره ی صف های معمولی یا همون صف های خطی داشته باشیم . اما در کنار تمام این اطلاعات باید این رو هم بدونیم که صف های خطی یک مشکلی دارن و اونم اینه که وقتی عناصر به سمت انتهای صف میرن ، ما امکان استفاده از خونه های ابتدای صف رو نداریم . درحالی که بعضی از خونه های ابتدایی صف ممکن هست با حذف عناصر موجود در خودشون خالی بشن و آمادگی ورود عناصر جدید رو داشته باشن.
روش هایی برای رهایی از این مشکل وجود داره که ما اینجا به دوتا اشاره می کنیم :
1- شیفت دادن خونه های انتهای صف به سمت ابتدای صف
2- استفاده از مفهومی به این شکل که وقتی به انتهای صف رسیدیم ، عمل درج رو دوباره از ابتدای صف انجام بدیم و این روند به صورت چرخشی باشه .
روش اول در بعضی جاها دارای هزینه ی بسیار بالایی خواهد بود و اونهم جاهایی هست که تعداد خونه های ما بسیار زیاد باشن . خب مشخص هست که شیفت دادن تعداد زیادی از خونه ها اونهم به مقدار زیاد ، ممکنه سخت و پر هزینه باشه .
روش دوم هم که به صرفه تر هست و در بیشتر جاها به روش اول ترجیح داده میشه در این مورد ، همون استفاده از صف حلقویه .
آرایه ی n تایی Q[0..n-1] رو میشه یک صف حلقوی در نظر گرفت به این شکل که توی این صف زمانیکه rear برابر با n-1 بود ، عنصر بعدی توی خونه ی 0 درج بشه . شکل زیر تقریبا میتونه معرف صف حلقوی باشه :
البته شکل بالا برای این هست که مفهوم حلقوی بودن و چرخشی بودن رو بتونیم راحت تر درک کنیم . شکل پایین هم مفهوم صف حلقوی رو خواهد داشت.
به وضوح مشخص هست که با این ساختار یا بهتره بگیم با این شکل از ساختار داده ای صف ، میتونیم تا حد زیادی مشکل صف های معمولی رو برطرف کنیم :
نکته ی زیر هم میتونه در بسیاری از آزمون های تستی دارای اهمیت زیادی باشه :
⚡️شرط خالی بودن صف حلقوی
front=rear
⚡️شرط پر بودن صف حلقوی
rear -1 mod n = front
برای مثال تست زیر رو درنظر بگیرید که برای یکی از آزمون های سال 1383 هست :
با توجه به مطالبی که گفته شد ، جواب درست ، گزینه ی 1 هست
در زیر عملیات حذف از صف حلقوی و درج در صف حلقوی رو هم مشاهده خواهید کرد :
حذف از صف حلقوی
درج در صف حلقوی
اما بریم سراغ لیست های پیوندی .
البته این موضوع جلسه ی آینده ی ما هست و ما فقط میخوایم درباره ی مقدماتش صحبت کنیم . قبل از اینکه مقدمات لیست های پیوندی رو بگیم ، برمیگردیم به ساختار داده ای "آرایه" ها و یکسری از ویژگی های آرایه ها رو ذکر می کنم
ببینید دوستان ، آرایه ها ویژگی های زیر رو دارن :
1- تعداد عناصر هر آرایه همیشه محدود ، مشخص و ایستا هست و در طول برنامه ثابت میمونه .
2- عملیات حذف و درج یک داده ی دلخواه در ناحیه ای مشخص از آرایه نیاز به شیفت خواهد داشت .
3- عملیات جست و جوی یک داده ی دلخواه در آرایه ها با روش های زیر انجام میشه :
⚡️روش جست و جوی خطی در همه نوع آرایه ها با پیچیدگی زمانی n
⚡️روش جست و جوی دودویی در آرایه های مرتب با پیچیدگی زمانی log n بر مبنای 2
4- دسترسی به داده های هر آرایه به صورت تصادفی و دلخواه به راحتی توسط اندیس آرایه ها انجام میشه و دسترسی مستقیم دارای پیچیدگی زمانی از مرتبه ی 1 خواهد بود .
5- روش های گوناگون و متنوعی برای مرتب سازی آرایه ها وجود داره مثل مرتب سازی حبابی ، انتخابی ، سریع ، درجی و ......
البته موارد 1 و 2 جزء معایب آرایه ها و موارد 3و4و5 جزء مزایای آرایه ها به حساب میان .
اما یکم درباره ی لیست های پیوندی صحبت کنیم :
لیست پیوندی ، ساختاری هست شامل دنباله‌ای از عناصر که هر عنصر دارای اشاره‌گری به عنصر بعدی در دنباله هست . لیست پیوندی جزء ساده‌ترین و رایج‌ترین ساختارهای داده ای به حساب میاد . مزیت مهم لیست های پیوندی نسبت به آرایه‌ها این هست که ترتیب قرار گرفتن داده‌ها توی لیست های پیوندی با ترتیب قرار گرفتن اونها توی حافظه متفاوت هست. واسه همین ،لیست پیوندی دارای این ویژگی هست که درج و حذف گره‌ها تو هر جایی از لیست ، با تعداد ثابتی از عملیات ها ممکن خواهد بود .اما لیست های پیوندی اجازه دستیابی تصادفی به داده ها یا هرگونه اندیس گذاری رو نمیدن. در نتیجه بسیاری از اعمال ابتدایی مثل به دست آوردن آخرین عنصر لیست ، پیدا کردن عنصر شامل داده ی مورد نظر، یا مشخص کردن مکان درج یک عنصر جدید ممکنه نیازمند بررسی اکثر عناصر لیست باشه.
لازم به ذکر هست که منظور از "گره" هر عنصر موجود در لیست پیوندی هست و اینکه هر گره دارای دو فیلد هست .. یکی به عنوان کلید و دیگری به عنوان اشاره گر .
انشاءالله درباره ی این مفاهیم در جلسه ی آینده بیشتر صحبت خواهیم کرد .
خب دوستان عزیز . برای این جلسه کافیه . در این جلسه یکی دو روش برای تبدیل عبارات پیشوندی و پسوندی به میانوندی رو گفتیم ، نکاتی رو درباره ی صف های حلقوی مطرح کردیم و در آخر مطالبی رو درباره ی آرایه ها و لیست های پیوندی گفتیم و ارائه کردیم .
به امید خداوند متعال در جلسه ی بعدی مبحث "لیست های پیوندی" رو ادامه خواهیم داد .
شاد و سربلند باشید . تا دیداری دیگر بدرود
نظرات کاربران