پاورپوینت صف ها (pptx) 26 اسلاید
دسته بندی : پاورپوینت
نوع فایل : PowerPoint (.pptx) ( قابل ویرایش و آماده پرینت )
تعداد اسلاید: 26 اسلاید
قسمتی از متن PowerPoint (.pptx) :
بنام خدا
Queues صف ها
صف ها Queues
صف ساختمان داده یست که مانند صفی از مردم که منتظر دریافت خدماتند، مدل شده.همچون پشته ها، صف ها یکی از ساده ترین انواع ساختمان داده ها می باشند. این فصل ویژگی های صف ها، تحلیل چگونگی بکار بستن آنها، و امتحان کردن پیاده سازی های متفاوت را بسط وتوسعه میدهد.
صف ها Queues
کاربردها
کاربردهای صف، تقریبا تمام کاربردهای پشته، یا حتی معمول تر ازکاربردهای پشته، است.
تعاریف
صف لیستی است که تمام عناصر اضافه شونده از یک طرف به لیست اضافه شوند و تمام عناصر حذف شونده از طرف دیگر حذف شوند.
اولین عنصر یک صف که آماده ی سرویس گیری است جلوی صف نامیده می شود. آخرین عنصر صف، یعنی، آخرین عنصر اضافه شده، عقب(یا دم) صف نامیده می شود.
صف ها Queues
عملیات صف
باید صف هایی را پیاده سازی کنیم که ورودی های آنها نوع عمومی دارند، که به آنها ورودی صف می گوییم. اولین عملی که هنگام کاربا هر صفی باید انجام دهیم این است که از یک سازنده برای مقداردهی اولیه استفاده کنیم تا در کاربردهای بعدی از آن استفاده کنیم:
صف ها Queues
تعریف کلاس C++
class Queue {
public:
Queue( );
bool empty( ) const;
Error_code append(const Queue_entry &x);
Error_code serve( );
Error_code retrieve(Queue_entry &x) const;
// Additional members will represent queue data
};
سه عملیات برای صف ها بسیار مفید است. اولی clear است، که یک صف را که قبلا ساخته شده را می گیرد و آن را خالی می کند. دومی تابع size است، که تعداد عناصر موجود در صف را بر می گرداند. سومی تابع serve_and_retrieve است، که نتایج serve و retrieve را ترکیب می کند.
کلاس های مشتق شده
اکنون رابطه بین کلاس Queue و کلاس مشتق شده Extended_queue را با یک دیاگرام سلسله مراتبی نشان می دهیم یک پیکان از کلاس مشتق شده به کلاس اصلی اشاره می کند
صف ها Queues
class Extended_queue: public Queue {
public:
bool full( ) const;
int size( ) const;
void clear( );
Error_code serve_and_retrieve(Queue_entry &item);
};
کلمه کلیدی public در اولین خط تعریف کلاس نشان می دهد که هر عضو ارثی از یک Extended_queue در حقیقت همان قابلیت دید(visibility) (برای کاربر) را دارد که به عنوان عضوی از Queue دارد.
روش پیاده سازی صف ها Queues
دراین روش یک آرایه ی خطی با ابتدایی همیشه در خانه ی اول داریم یک ورودی میتواند همانگونه که به پشته ها ورودی را می افزاییم و براحتی با افزایش شمارنده ی انتهای صف افزوده شود. و هرگاه ابتدا حذف شود همه عناصر در آرایه بالا میروند.بطور کلی این یک روش نامناسب در کامپیوتر است.
یک آرایه ی خطی با دو اندیسهای ابتدا و انتهایی که همواره افزایش میابند. میدهیم.برای حذف یک عنصر آن را از محل در ابتدای صف برمیداریم و ابتدا را یکی افزایش میدهیم و برای افزودن عنصر به صف به سادگی مقدار انتها را یکی افزایش میدهیم این این روش مناسبیست اگر بشود تمام صف را در یک آن خالی نمود.
یک آرایه حلقوی شبیه ماربرای نمایش صف ها داریم .برای پیاده سازی باید محلهای آرایه را شماره گذاری شده از 0 تا max-1 تصورکنیم،که max مقدار نهایی عناصر در آرایه ی حلقوی است . جابجایی اندیس ها مانند محاسبات مدوله است:وقتی ما یک ایندکس را بعدmax-1 افزایش میدهیم دوباره از 0 شروع میکنیم.
پیاده سازی و اجرای خطی:
پیاده سازی آرایه های حلقوی:
مدل فیزیکی :
صف ها Queues
حالات مرزی نشاندهنده ی اینست که یک صف خالی یا پر است. است.اگر دقیقا یک عنصر در صف باشد ابتدا و انتها برابرند.وقتی این یک عنصر حذف شود، ابتدای صف یکی افزایش می یابد،پس یک صف نشان داده میشود وقتی که انتهای صف یکی قبل از ابتداست. وقتی که صف پر است انتها یکی قبل از ابتدا قرار میگیرد.پس ما یک مشکل دیگر داریم: اندیسهای ابتدا و انتها در صف خالی و پر در یک وضعیت مکانی قرار دارند. راهی برای تشخیص اینکه صف پر یا خالیست تنها با نگاه کردن به آرایه ها وجود ندارد.
حالات مرزی