دانلود فایل پاورپوینت Queues صف ها

بخشی از پاورپوینت

--- پاورپوینت شامل تصاویر میباشد ----

اسلاید 1 :

صف ها Queues

صف ساختمان داده یست که مانند صفی از مردم که منتظر دریافت خدماتند، مدل شده.همچون پشته ها، صف ها یکی از ساده ترین انواع ساختمان داده ها می باشند. این فصل ویژگی های صف ها، تحلیل چگونگی بکار بستن آنها، و امتحان کردن پیاده سازی های متفاوت را بسط وتوسعه میدهد.

اسلاید 2 :

تعاریف

صف لیستی است که تمام عناصر اضافه شونده از یک طرف به لیست اضافه شوند و تمام عناصر حذف شونده از طرف دیگر حذف شوند.

اولین عنصر یک صف که آماده ی سرویس گیری است جلوی صف نامیده می شود. آخرین عنصر صف، یعنی، آخرین عنصر اضافه شده، عقب(یا دم) صف نامیده می شود.

کاربردها

کاربردهای صف، تقریبا تمام کاربردهای پشته، یا حتی معمول تر ازکاربردهای پشته، است.

اسلاید 3 :

عملیات صف

باید صف هایی را پیاده سازی کنیم که ورودی های آنها نوع عمومی دارند، که به آنها ورودی صف می گوییم. اولین عملی که هنگام کاربا هر صفی باید انجام دهیم این است که از یک سازنده برای مقداردهی اولیه استفاده کنیم تا در کاربردهای بعدی از آن استفاده کنیم:

اسلاید 4 :

تعریف کلاس 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 را با یک  دیاگرام سلسله مراتبی نشان می دهیم یک پیکان از کلاس مشتق شده به کلاس اصلی اشاره می کند

اسلاید 5 :

class Extended_queue: public Queue {

public:

bool full( ) const;

int size( ) const;

void clear( );

Error_code serve_and_retrieve(Queue_entry &item);

};

nکلمه کلیدی public در اولین خط تعریف کلاس نشان می دهد که هر عضو ارثی از یک Extended_queue در حقیقت همان قابلیت دید(visibility) (برای کاربر) را دارد که به عنوان عضوی از Queue دارد.

اسلاید 6 :

روش پیاده سازی صف ها  Queues

دراین روش یک آرایه ی خطی با ابتدایی همیشه در خانه ی اول داریم  یک ورودی میتواند همانگونه که به پشته ها ورودی را  می افزاییم و براحتی با افزایش شمارنده ی انتهای صف افزوده شود. و هرگاه ابتدا حذف شود همه عناصر در آرایه بالا میروند.بطور کلی این یک روش نامناسب در کامپیوتر است.

یک آرایه ی خطی با دو اندیسهای ابتدا و انتهایی که همواره افزایش میابند. میدهیم.برای حذف یک عنصر آن را از محل در ابتدای صف برمیداریم و ابتدا را یکی افزایش میدهیم و برای افزودن عنصر به صف به سادگی مقدار انتها را یکی افزایش میدهیم این این روش مناسبیست اگر بشود تمام صف را در یک آن خالی نمود.

یک آرایه حلقوی شبیه ماربرای نمایش صف ها داریم .برای پیاده سازی باید محلهای آرایه را شماره گذاری شده از 0 تا max-1 تصورکنیم،که max مقدار نهایی عناصر در آرایه ی حلقوی است . جابجایی اندیس ها مانند محاسبات مدوله است:وقتی ما یک ایندکس را بعدmax-1 افزایش میدهیم دوباره از 0 شروع میکنیم.

اسلاید 7 :

• حالات مرزی

حالات مرزی نشاندهنده ی اینست که یک صف خالی یا پر است. است.اگر دقیقا یک عنصر در صف باشد ابتدا و انتها برابرند.وقتی این یک عنصر حذف شود، ابتدای صف یکی افزایش می یابد،پس یک صف نشان داده میشود وقتی که انتهای صف یکی قبل از ابتداست. وقتی که صف پر است انتها یکی قبل از ابتدا قرار میگیرد.پس ما یک مشکل دیگر داریم: اندیسهای ابتدا و انتها در صف خالی و پر در یک وضعیت مکانی قرار دارند. راهی برای تشخیص اینکه صف پر یا خالیست تنها با نگاه کردن به آرایه ها وجود ندارد.

اسلاید 8 :

nراه حل های ممکن برای حل این مشکل:

یک آرایه حلقوی با اندیسهای ابتدا و انتهایی و یک flag برای نشان دادن خالی یا پر بودن در نظر بگیرید.

یک آرایه حلقوی با اندیسهای ابتدا و انتها و یک متغیر صحیح که عناصر رامیشمارد درنظر بگیرید.

یک آرایه حلقوی با اندیسهای ابتدا و انتهایی که برای نشان دادن خالی بودن مقادیر خاصی میگیرنددرنظر بگیرید.

آرایه های خطی در C++

nدر C++ ما میتوانیم اندیس I یک آرایه حلقوی را با استفاده از اپراتور سه تایی ?: افزایش دهیم و بنویسیم:

i = ((i + 1) == max) ? 0 : (i + 1);

این استفاده ی اپراتور سه تایی ?: هم ارز با کد زیر است:

if ((i + 1) == max) i = 0; else i = i + 1;

همچنین ما میتوانیم از اپراتور باقیمانده ای استفاده کنیم وبنویسیم:

i = (i + 1)%max

(شما باید چک کنید که نتیجه ی عبارت اخیر همواره بین 0 و max-1 باشد.

اسلاید 9 :

 پیادهسازیحلقوی صف ها Queues در c++

nپیاده سازی در یک  آرایه ی حلقوی که از یک شمارنده برای شمارش عناصر ورودی در صف  استفاده می کند صف را ذخیره شده در یک آرایه با اندیس از 0 تا maxqueue-1 که ورودی هایی از نوع عنصر- صف دارند می گیریم. تعریف کلاس برای یک صف به صورت زیر است  که به اعضای داده ای صف رویت  Protected را به جای Private را میدهیم

اسلاید 10 :

nتوابع عضو  از کلاس های مشتق شده  اجازه دارند به عضوهای Protected کلاس اصلی دسترسی داشته باشند. بنابراین وقتی ما متدها را برای کلاسهای مشتق صف گسترده مینویسیم کد ما قادر به استفاده اعضای داده ای کلاس صف خواهد بود.

nمتدها برای اضافه برای اضافه و حذف کردن از یک صف گسترده  بحث قبلی مارادنبال میکنند.فقطموارد زیر را در نظر می گیریم:

ابتداصف خالی تعریف میشودQueue :: Queue( )                                                        

اگر صف خالی باشد مقدار صحیح و در غیر این صورت غلط را باز میگرداند

count = 0; bool Queue :: empty( ) const

}return count == 0; {

در صورتی که صف پر باشد پیغام خطای سرریز میدهد و صف بدون تغییر میماند 

Error_code Queue :: append(const Queue_entry &item)

if (count >= maxqueue) return overflow;

ابتدای صف حذف شده است اگر صف خالی باشد پیغام خطا میدهد

Error_code Queue :: serve( )

if (count <= 0) return underflow;

ابتدای صف مقدار آیتم خروجی را میگیرد اگر صف خالی باشد پیغام خطای سرریز میدهد.

Error_code Queue :: retrieve(Queue_entry &item) const

if (count <= 0) return underflow;