صف پیوندی اصلاح شده به چه معناست ؟

2

صف پیوندی اصلاح شده به چه معناست ؟

کیانا ابراهیمی سوال پاسخ داده شده اکتبر 15, 2020
گذاشتن نظر
0

صف پیوندی اصلاح شده به چه معناست ؟

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

class ImprovedQueue:
def __init__(self):
self.length = 0
self.head = None
self.last = None
def isEmpty(self):
return (self.length == 0)

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

class ImprovedQueue:

def insert(self, cargo):
node = Node(cargo)
node.next = None
if self.length == 0:
# if list is empty, the new node is head and last
self.head = self.last = node
else:
# find the last node
last = self.last
# append the new node
last.next = node
self.last = node
self.length = self.length + 1

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

class ImprovedQueue:

def remove(self):
cargo = self.head.cargo
self.head = self.head.next
self.length = self.length – 1
if self.length == 0:
self.last = None
return cargo

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

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

برای اموزش های ویدیویی زبان پایتون به بستر ویدیو های اموزشی بروید

بستر اموزش های ویدویی 

کیانا ابراهیمی سوال پاسخ داده شده اکتبر 15, 2020
گذاشتن نظر
پاسخ خود را بنویسید .
  • فعال
  • بازدیدها1338 times
  • پاسخ ها1 پاسخ
ورود به متاورس | متاورس ایرانی
ورود به متاورس ایران یا همان متاورس ملی

علامت ذره بین Tutorials سمت راست به رنگ قرمز به شما کمک خواهد کرد .

جدید ترین سوالات پرسیده شده

منقضی شدن سم بتانال 1 پاسخ | 0 آرا
ایا ایدز گزفتم؟ 0 پاسخ ها | 0 آرا
انتخاب ورزش رزمی 0 پاسخ ها | 1 رای
وزارت تعاون کار و رفاه اجتماعی نماد اعتماد الکترونیک اسناد و املاک کشور مرکز آموزش ویدیویی انجمن حم فروشگاه ملی تولید کنندگان مدیریت بر مدیران حم سامانه حیوانات رسانه ملی اخبار متا دانشگاه متاورس استخدام | دانش فروشگاه حم تبلیغات ملی بازار NFT متاورس رنگ نقشه ملی سه بعدی متا املاک و مستغلات