صف ADT در پایتون

  • دسته بندی: آموزش پایتون
  • ۰ دیدگاه
  • منتشر شده در تاریخ
  • آپدیت شده در ۱۵اردیبهشت, ۱۳۹۷
  • 1 Star2 Stars3 Stars4 Stars5 Stars (No Ratings Yet)
    Loading...
صف ADT در پایتون

صف ADT

صف ADT در پایتون  با عملیات زیر تعریف شده است:

__init :__یک صف جدید تهی را مقداردهی اولیه میکند.
insert :یک قلم داده جدید به صف اضافه میکند.
remove :یک قلم داده را از صف حذف میکند و برمیگردانـد. آن قلـم دادای کـه برگردانـده
شده، اولین قلم دادهای است که اضافه شده بود.
isEmpty :بررسی میکند که آیا صف تهی است یا نه.

صف پیوندی

اولین پیادهسازی ADT صفی که ما میخواهیم ببینیم، صف پیوندی نامیـده مـیشـود، زیـرا از
یک سری شیء Node به هم پیوسته تشکیل شده است. در اینجا تعریف کلاس را میبینید:

متدهای isEmpty و remove معادل متدهای isEmpty و removeFirst لیستهـای
پیوندی هستند. متد insert جدید و کمی پیچیدهتر است.
ما میخواهیم یک قلم داده جدید به آخر لیست اضافه کنیم. اگر تهی باشد، مـا فقـط head را
برای اشاره به گره جدید تنظیم میکنیم.

درآمد تلگرام از کجاست؟
مشاهده مطلب

در غیر اینصورت، ما لیستها را تا گره آخر پیمایش میکنیم و گـره جدیـد را بـه آخـر لیسـت
ضمیمه میکنیم. ما میتوانیم گره آخر را از جایی که مشخصۀ next آن None است، تشخیص دهیم.
برای یک شیء Queue خوشفرم و خوشحالت، دو نامتغیر وجود دارد. مقـدار length بایـد
تعداد گرههای صف باشد و گره آخر باید یک مشخصۀ next برابر با None داشته باشد.

ویژگیهای کارکرد

معمولاً وقتی یک متد را احضار میکنیم، نگران جزئیات پیادهسازی آن نیستیم. اما ممکن است
که یک «نکتۀ ظریف» وجود داشته باشد که بخواهیم بدانیم: ویژگیهـای کـارکرد. همچنـانکـه تعـداد
اقلام درون مجموعه افزایش مییابد، مدت زمان اجرا چقدر خواهد بود و به چه صورت تغییر میکند؟

ابتدا به remove نگاه کنید. هیچ حلقه یا فراخوانی تابعی در اینجا وجـود نـدارد، یعنـی زمـان
اجرای این متد همواره یکسان است. چنین متدی یـک عملیـات ثابـت-زمـانی نامیـده مـیشـود. در
حقیقت ممکن است که متد وقتی لیست خالی است اندکی سریعتر باشد چراکه از بدنۀ شـرطهـا عبـور
میکند، اما این تفاوت چندان قابل توجه نیست.

کارکرد insert بسیار متفاوت است. در حالت کلی، ما مجبـوریم بـرای پیـدا کـردن آخـرین
عضو، لیست را پیمایش کنیم. این پیمایش بسته به طول لیست وقتگیر است. از آنجـا کـه زمـان اجـرا
یک تابع خطی از طول است، این متد زمان-خطی نامیده میشود و در مقایسه بـا متـدهـای عملیـات
ثابت-زمانی بسیار بد است.

صف پیوندی اصلاح شده

ما مایلیم یک پیادهسازی ADT صف بتواند همۀ عملیات را به صورت ثابـت-زمـانی انجـام دهـد.
یک راه برای انجام این کار تغییر دادن کلاس صف بهطوری است که آدرسی به اولین و آخـرین گـره را نگهداری کند.

واقعیت افزوده و کاربردهای آن
مشاهده مطلب

پیادهسازی صف اصلاحشده به این صورت است:

تاکنون تنها تغییر مشخصۀ last است که در متـدهای remove و insert اسـتفاده شـده
است:

از آنجا که last رد آخرین گره را نگه میدارد، مـا مجبـور نیسـتیم آن را جسـتجو کنـیم. در
نتیجه این متد ثابت-زمانی است. برای بدست آوردن این سرعت باید هزینـهای پرداخـت. مـا مجبـوریم
برای متغیر last به None در زمانی که آخزین گره حذف شده است بـه remove حالـت خاصـی را
اضافه کنیم:

این پیادهسازی نسبت به پیادهسازی صف پیوندی پیچیـدهتـر و اثبـات آن هـم دشـوارتر اسـت.
نتیجه این است که ما به هدفمان دست یافتیم؛ هر دو متد insert و remove عملیات ثابت-زمـانی
هستند.

آشنایی با ابزارها و سایت های ساخت برنامه اندروید
مشاهده مطلب

تمرین :

یک پیادهسازی از ADT صف را با استفاده از لیستهای پایتون بنویسـید. کـارائی
این پیاده سازی را با کلاس ImprovedQueue برای محدودهای از طولهـای صـف مقایسـه
کنید.

صفحه بیسیک کده در اینستاگرام
مارا در اینستاگرام دنبال کنید
فالو می کنم
کانال تلگرام بیسیک کده
راهی آسانتر برای ارتباط با شما

پکیج های آموزشی

مطالب مرتبط

نظرات کاربران
  • درخواست شما پس از تایید در سایت نمایش داده می شود. از ارسال پرسش تکراری خودداری نمایید.

دیدگاه بگذارید

avatar
  Subscribe  
Notify of