عبارت زیر درسته بچه ها؟
"حذف عنصر آخر در یک لیست زنجیره ای یک طرفه، با داشتن اشاره گره های First و Last از مرتبه (۱) O است."
اگه لیست فقط یه دونه گره داشته باشه، یعنی گره اول همون گره آخر باشه این عمل در زمان (۱) O انجام نمیشه؟
یه جا این جمله رو درست در نظر گرفته یه جا غلط!!
ممنون میشم راهنماییم کنید.
سلام سارا جان وقت بخیر.
ببین به نظرم غلطه.و از مرتبه n میشه.
چون شما آدرس آخر لیست که به دردت نمیخوره. باید یه اشاره گر از اول بیاری به آخر لیست روی عنصر یکی مونده با آخر و بعد اشاره گر next اون خونه رو nil کنی. که انجام این کار یعنی آوردن یه اشاره گر از اول به اخر لیست وابسته اس به تعداد عناصر لیست و بنابراین از مرتبه O(n) هست.
Sent from my Google Galaxy Nexus using Tapatalk 2.4
میشه یه پیاده سازی برای حذف عنصر داشت که [tex]\Theta (1)[/tex] باشه اما بعیده که طراح سوال این پیاده سازی رو مد نظر قرار بده!
میشه یه بیت حذف به ساختمان داده اضافه کرد(به هر نود یک بیت اضفه کنید) و برای حذف کردن گره آخر فقط کافیه این بیت برای گره ای که last در حال اشاره به اونه برابر مقدار حذف(مثلا ۱) قرار بگیره و last به عنصر اول لیست اشاره کنه و first هم به عنصر بعد خودش . حالا هر بار که در پیمایش به رأسی رسیدیم که رأس بعدی اون علامت حذف داشت ترتیب حذف کامل رو میدیم!
حالا اگه یه عنصر داشتیم که سریعا اشاره گر last و first رو null میکنیم.
البته این پیاده سازی برای صف که عنصر اول و آخر مهم اند بدرد نمیخوره و فقط برای لیست کار برد داره!
Amir V ممنونم بابت توضیحات
چرا بن شدی؟
javadem ممنونم.
پس کلاً غلطه دیگه این جمله؟!
فقط در یک حالت خاص امکان پذیره اونم باید توی ساختمان داده تغییر ایجاد کنیم که معمولا توی تست ها این اجازه رو نداریم . پس بله اشتباست
ممنونم بابت توضیحاتتون.
موفق باشید.