سلام
برای گرفتن مینیمم در صف یا پشته پیوندی چه راهکاری دارید؟
چون ما وقتی یک داده ای رو از صف بر می گردونیم. . اشاره گر که مثلا first باشه از اول یکی میاد جلوتر و نود قبلی حذف میشه به کل.
اگر به این طریق مینیمم بگیریم کل صف خالی میشه.
راه حل شما چیست؟ چه ایده ای دارید؟
که مینبمم و ماکسیمم بگیریم و صف پابرجا باشد. واضح تر بگم:
5
9
14
3
19
درون صف هستند. (صف پیوندی) . حالا میبنمم رو بدست بیارم. بعد مقدار رو برگردونم و این نود رو حذف کنم و صف بشه
5
9
14
19
الان صف رو پیاده کردن و عنصر توش درج و حذف میکنم و مشکلی نداره. نیاز به تکمیلش هست. زبان سی شارپ
ویرایش: به دلیل بی دقتی در خوندن پست اول، کلاً جواب غلطی داده بودم. در نتیجه جواب خودم رو حذف کردم.
یه راهش اینه کل صفو پیمایش کنی یعنی از اول حذف کنی و به آخر اضافه کنی(درج) و مینیمم رو پیدا کنی و با یه پیمایش دیگه اون عنصرو حذف کنی. اگه مینیمم رو در یه متغیر ذخیره کرده باشی فقط یه پیمایش می خواد. یعنی یکی یکی از اول صف حذف می کنی و اگه مینیمم نبود به آخر صف اضافه می کنی. اگه مینیمم بود که دیگه اونو درج نمی کنی. این کارو هم به تعداد داده هات در صف انجام میدی. این طوری صفت به هم نمی خوره. شاید راه ساده تری هم باشه.
یافتن (دسترسی به ) مینیمم و ماکسیمم در صف مرتبش on هست
سلام
بله حق با شماست. در مورد ماکسیمم و مینیمم چی کار کنم؟
به نظرتون به صرفه تر نیست . بعد از اضافه کردن مقادیر به نود ها همه رو همون موقع بریزم تو یک آرایه.
از اون ور واسه حذف کردن عنصر در آرایه باز هم مکافاتش فکر نکنم کمتر از صف پیوندی بشه.
ایده کم هزینه تر و بهتر نیست؟
(24 اسفند 1391 12:20 ق.ظ)mahdiii نوشته شده توسط: [ -> ]یه راهش اینه کل صفو پیمایش کنی یعنی از اول حذف کنی و به آخر اضافه کنی(درج) و مینیمم رو پیدا کنی و با یه پیمایش دیگه اون عنصرو حذف کنی. اگه مینیمم رو در یه متغیر ذخیره کرده باشی فقط یه پیمایش می خواد. یعنی یکی یکی از اول صف حذف می کنی و اگه مینیمم نبود به آخر صف اضافه می کنی. اگه مینیمم بود که دیگه اونو درج نمی کنی. این کارو هم به تعداد داده هات در صف انجام میدی. این طوری صفت به هم نمی خوره. شاید راه ساده تری هم باشه.
یافتن (دسترسی به ) مینیمم و ماکسیمم در صف مرتبش on هست
سلام
یک بار کل صف رو میرم جلو و به فرض 6 نود داریم و مینیمم در نود 4 هست. و پیداش کردیم.و ریخیتم در متغیر min
حالا یک اشاره گر اول صف داریم یک اشاره گر اخر صف
چطور حذف کنمش؟ مثل آرایه نیست که بگم عنصر 4 رو تغیر بده.
(24 اسفند 1391 01:31 ق.ظ)irpersian20 نوشته شده توسط: [ -> ]سلام
بله حق با شماست. در مورد ماکسیمم و مینیمم چی کار کنم؟
به نظرتون به صرفه تر نیست . بعد از اضافه کردن مقادیر به نود ها همه رو همون موقع بریزم تو یک آرایه.
از اون ور واسه حذف کردن عنصر در آرایه باز هم مکافاتش فکر نکنم کمتر از صف پیوندی بشه.
ایده کم هزینه تر و بهتر نیست؟
(24 اسفند 1391 12:20 ق.ظ)mahdiii نوشته شده توسط: [ -> ]یه راهش اینه کل صفو پیمایش کنی یعنی از اول حذف کنی و به آخر اضافه کنی(درج) و مینیمم رو پیدا کنی و با یه پیمایش دیگه اون عنصرو حذف کنی. اگه مینیمم رو در یه متغیر ذخیره کرده باشی فقط یه پیمایش می خواد. یعنی یکی یکی از اول صف حذف می کنی و اگه مینیمم نبود به آخر صف اضافه می کنی. اگه مینیمم بود که دیگه اونو درج نمی کنی. این کارو هم به تعداد داده هات در صف انجام میدی. این طوری صفت به هم نمی خوره. شاید راه ساده تری هم باشه.
یافتن (دسترسی به ) مینیمم و ماکسیمم در صف مرتبش on هست
سلام
یک بار کل صف رو میرم جلو و به فرض ۶ نود داریم و مینیمم در نود ۴ هست. و پیداش کردیم.و ریخیتم در متغیر min
حالا یک اشاره گر اول صف داریم یک اشاره گر اخر صف
چطور حذف کنمش؟ مثل آرایه نیست که بگم عنصر ۴ رو تغیر بده.
من که توضیح دادم باید یکی یکی حذف کنی و به آخر اضافه کنی
(24 اسفند 1391 02:32 ق.ظ)mahdiii نوشته شده توسط: [ -> ] (24 اسفند 1391 01:31 ق.ظ)irpersian20 نوشته شده توسط: [ -> ]سلام
بله حق با شماست. در مورد ماکسیمم و مینیمم چی کار کنم؟
به نظرتون به صرفه تر نیست . بعد از اضافه کردن مقادیر به نود ها همه رو همون موقع بریزم تو یک آرایه.
از اون ور واسه حذف کردن عنصر در آرایه باز هم مکافاتش فکر نکنم کمتر از صف پیوندی بشه.
ایده کم هزینه تر و بهتر نیست؟
(24 اسفند 1391 12:20 ق.ظ)mahdiii نوشته شده توسط: [ -> ]یه راهش اینه کل صفو پیمایش کنی یعنی از اول حذف کنی و به آخر اضافه کنی(درج) و مینیمم رو پیدا کنی و با یه پیمایش دیگه اون عنصرو حذف کنی. اگه مینیمم رو در یه متغیر ذخیره کرده باشی فقط یه پیمایش می خواد. یعنی یکی یکی از اول صف حذف می کنی و اگه مینیمم نبود به آخر صف اضافه می کنی. اگه مینیمم بود که دیگه اونو درج نمی کنی. این کارو هم به تعداد داده هات در صف انجام میدی. این طوری صفت به هم نمی خوره. شاید راه ساده تری هم باشه.
یافتن (دسترسی به ) مینیمم و ماکسیمم در صف مرتبش on هست
سلام
یک بار کل صف رو میرم جلو و به فرض ۶ نود داریم و مینیمم در نود ۴ هست. و پیداش کردیم.و ریخیتم در متغیر min
حالا یک اشاره گر اول صف داریم یک اشاره گر اخر صف
چطور حذف کنمش؟ مثل آرایه نیست که بگم عنصر ۴ رو تغیر بده.
من که توضیح دادم باید یکی یکی حذف کنی و به آخر اضافه کنی
درست می فرمائید
یک دور میریم جلو و کمترین عنصر پیدا میکنیم
حالا 2 تا اشاره گر داریم اول و آخر صف . و هیچ عنصری هم حذف نشده و صف هم ترتیب سابق رو داره و فقط مینیمم پیدا شده
در صف 6 نودی . نود 4 مینیمم هست. دوره از اول یک بار دیگه بریم جلو و دنبال نود 4 بگیرم و حذفش کنیم؟
2 سری پیمایش میشه درسته؟
آره. اما اگه مینیمم رو داشته باشی(هنگام درج و حذف به روزش کنی) یه پیمایش کافیه(فقط برای حذف)
سلام
من کلا برای پیاده سازی واقعی (نه شبیه سازی فقط) الگوریتم های زمانبندی مثل sjf و rr دارم . از صف پیوندی کلا استفاده میکنم.همش از صف پیوندی.
من مثالی ندیدم ببینم بقیه چطور کار کردند.
نظر شما چیه؟ ایا ساختمان داده مناسبی هست یا هزنیه زیادی داره ؟ کار با آرایه برای این حذف و درج ها گرفتن مینیمم و ماکسیمم ها کارم سخت تر نیست؟
کلا برای پیاده سازی صف دو راه وجود داره با آرایه و با لیست پیوندی. آرایه تعداد عناصرش ثابته و نمی تونه برای حالتهای کلی و عمومی مناسب باشه اما در عوض با لیست پیوندی می تونید هر تعداد عناصر که می خواهید اضافه کنید. اگر به زبان c++ آشنا هستید، خود صف، پشته، صف دوطرفه و خیلی از این مواردو پیاده سازی کرده و شما می تونید با تعریف یک شی از نوع صف، به راحتی از توابعش استفاده کنید. (حذف و درج) یه سرچ بزنید خیلی راحت مطلب پیدا می کنید.
queue in c++
فقط یه چیزی من از مطلب شما اینو فهمیدم که شما می خواهید کوچکترین عنصر رو هر دفعه حذف کنید(در زمان حذف) اگر این طوره که باید از صف اولویت استفاده کنید که در کتابهای ساختمان داده هم بهش اشاره شده. بدین صورت که صف اولویت مثل صف عادیست تنها هنگام حذف، کوچکترین عنصر(بالاترین اولویت ) رو حذف می کنه که بهترین پیاده سازیش با هیپ هست که log ای هست اما اگه از راههای معمول می خواهید استفاده کنید همون on هست.
در ضمن در سی شارپ هم خود ساختار صف پیاده سازی شده.
من شما رو به این لینک ارجاع میدم. امیدوارم مفید باشه. من کلمه priority queue in c# رو جستجو کردم
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.