۰
subtitle
ارسال: #۱
  
آی تی- سراسری ۸۵
عبارت زیر درسته بچه ها؟
"حذف عنصر آخر در یک لیست زنجیره ای یک طرفه، با داشتن اشاره گره های First و Last از مرتبه (۱) O است."
اگه لیست فقط یه دونه گره داشته باشه، یعنی گره اول همون گره آخر باشه این عمل در زمان (۱) O انجام نمیشه؟
یه جا این جمله رو درست در نظر گرفته یه جا غلط!!
ممنون میشم راهنماییم کنید.
"حذف عنصر آخر در یک لیست زنجیره ای یک طرفه، با داشتن اشاره گره های First و Last از مرتبه (۱) O است."
اگه لیست فقط یه دونه گره داشته باشه، یعنی گره اول همون گره آخر باشه این عمل در زمان (۱) O انجام نمیشه؟
یه جا این جمله رو درست در نظر گرفته یه جا غلط!!
ممنون میشم راهنماییم کنید.
۰
ارسال: #۲
  
Re: آی تی- سراسری ۸۵
سلام سارا جان وقت بخیر.
ببین به نظرم غلطه.و از مرتبه n میشه.
چون شما آدرس آخر لیست که به دردت نمیخوره. باید یه اشاره گر از اول بیاری به آخر لیست روی عنصر یکی مونده با آخر و بعد اشاره گر next اون خونه رو nil کنی. که انجام این کار یعنی آوردن یه اشاره گر از اول به اخر لیست وابسته اس به تعداد عناصر لیست و بنابراین از مرتبه O(n) هست.
Sent from my Google Galaxy Nexus using Tapatalk 2.4
ببین به نظرم غلطه.و از مرتبه 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 میکنیم.
البته این پیاده سازی برای صف که عنصر اول و آخر مهم اند بدرد نمیخوره و فقط برای لیست کار برد داره!
میشه یه بیت حذف به ساختمان داده اضافه کرد(به هر نود یک بیت اضفه کنید) و برای حذف کردن گره آخر فقط کافیه این بیت برای گره ای که last در حال اشاره به اونه برابر مقدار حذف(مثلا ۱) قرار بگیره و last به عنصر اول لیست اشاره کنه و first هم به عنصر بعد خودش . حالا هر بار که در پیمایش به رأسی رسیدیم که رأس بعدی اون علامت حذف داشت ترتیب حذف کامل رو میدیم!
حالا اگه یه عنصر داشتیم که سریعا اشاره گر last و first رو null میکنیم.
البته این پیاده سازی برای صف که عنصر اول و آخر مهم اند بدرد نمیخوره و فقط برای لیست کار برد داره!
۰
ارسال: #۴
  
RE: آی تی- سراسری ۸۵
Amir V ممنونم بابت توضیحات
چرا بن شدی؟
javadem ممنونم.
پس کلاً غلطه دیگه این جمله؟!
چرا بن شدی؟
javadem ممنونم.
پس کلاً غلطه دیگه این جمله؟!
۰
ارسال: #۵
  
آی تی- سراسری ۸۵
فقط در یک حالت خاص امکان پذیره اونم باید توی ساختمان داده تغییر ایجاد کنیم که معمولا توی تست ها این اجازه رو نداریم . پس بله اشتباست
۰
موضوعهای مرتبط با این موضوع... |
|||||
موضوع: | نویسنده | پاسخ: | بازدید: | آخرین ارسال | |
۸۵۵ نرم افزار | farhad_vr32 | ۴ | ۲,۹۶۶ |
۲۱ تیر ۱۳۹۵ ۱۲:۵۱ ب.ظ آخرین ارسال: farhad_vr32 |
|
۸۵۲ آی تی و تجارت. ۲۰۰۰ امنیت و شبکه، پشت کنکوری همچنان!!!! | م. رجبی | ۲ | ۳,۹۸۲ |
۱۱ آبان ۱۳۹۲ ۱۲:۳۹ ق.ظ آخرین ارسال: م. رجبی |
|
تناقض در پاسخ به تست کنکور ۸۵و۸۶ در کتب پارسه و پوران | tredex | ۱ | ۲,۳۷۳ |
۱۲ آبان ۱۳۹۰ ۰۸:۴۸ ب.ظ آخرین ارسال: Masoud05 |
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close