PDA

View Full Version : سوال: چاپ یک متغییر در لیست پیوندی



hercool
پنج شنبه 02 دی 1389, 19:00 عصر
با سلام این سوال مربوط به مثالی حل شده در کتاب ساختمان داده هست و من در رابطه با اون مشکل دارم
مثال
لیست پیوندی خطی داریم که در اولین حافظه head وجود دارم و از دومین اندیس عنصر ها قرار میگیرند و اخر به عنصر n ام که دارای اشاره گر null هست ختم می شود
بر روی این لیست قطعه کد زیر اجرا می شود (head به سر لیست اشاره می کند):



list=head->next;
while (list!=null)
{
p=list;
while(p!=null)
{p=p->next;
cout<<"data";
}
list=list->next;
}




اگر لیست n عنصر داشته باشد کلمه data چند بار در خروجی چاپ می شود.
حل:
جواب رو دادن n(n+1)/2 حالا برای من سوال هست چرا این جواب

حالا من پیمایش می کنم منتظر نظر و راهنمایی دوستان هستم
هدر به خانه بعدی اشاره می کند و ان را داخل متغییر لیست قرار می دهد سپس
شرطی قرار می دهیم که تا زمانی که لیست نامساوی صفر هست شرط برقرار باشد
حالا لیست را داخل متغییر p می گذاریم سپس برای p هم هیمن شرط نامساوی صفر را قرار می دهیم
سپس در هر بار که p برابر صفر نبود p یک خانه به جلو برود و داخل متغییر p بریزد یعنی کل خانه ها را تا زمانی که p پر است پیمایش کرده و کلمه data را به خروجی بدهد
سپس بعد از اینکه p به صفر خورد
list به خانه جلو اشاره کند و خود را در داخل متغییر لیست قرار بدهد در کل یک خانه به جلو برود

سوال من اینجاست که p , list هر دو دارند به یک لیست پیوندی اشاره می کنند پس تنها n-1 بار دیتا چاپ می شود نه این مقدرا ممنون میشم راهنمایی کنید؟

سعیدسعید
پنج شنبه 02 دی 1389, 19:29 عصر
سلام دوست عزیز
اول از همه بذار بگم که جواب n(n+1)/2 خواهد بود. روشی که شما در بالا پیمایش کردید درسته اما بعد از اینکه p به آخر لیست رسید و list هم یک خانه به جلو رفت، لیست پیوندی دوباره با p پیمایش می شود و در نهایت به تعداد n(n+1)/2 بار کلمه data چاپ می شود. من فکر میکنم که شما احتمالا بعد از جلو بردن متغیر list، لیست پیوندی را با مقدار جدید p دوباره پیمایش نمیکنید. دقت کنید که کل الگوریتم در داخل حلقه while(list!=null) قرار دارد.

اینجور مسائل رو حتما با مثال حل کنید. با فرمول و اینا یکمی سخت میشه. یک لیست پیوندی با تعداد عناصر دلخواه بکشید و الگوریتم مورد نظر رو روش اعمال کنید بعد رابطه تعداد جواب بدست امده را با n مشخص کنید که جواب مسئله هم به راحتی پیدا خواهد شد.

امیدوارم که مطالب فوق کمکی بهت کرده باشه. بازهم اگر سوالی بود برادرت در خدمتت هست :لبخندساده:

hercool
پنج شنبه 02 دی 1389, 21:55 عصر
یعنی من لیست پیوندی موجود را با استفاده از متغییر p به تعداد عناصر لیست پیوندی پیمایش می کنم درسته
یعنی اگر من در لیست پیوندی خود 10 عنصر دارم در بار اول من 10 بار دیتا چاپ می کنم و در مرحله دوم 9 بار و الی اخر درسته؟

ایا لیست و p هر دو به یک لیست پیوندیاشاره نمی کنند ؟

سعیدسعید
جمعه 03 دی 1389, 17:29 عصر
سلام
متغیرهای list و p هر دو به یک لیست اشاره می کنند
اگر لیست شما دارای 10 عنصر باشد بار اول 9 بار عبارت data چاپ می شود و بار دوم 8 بار و همین طور الی آخر. دلیل این کار این است که اگر در کد نوشته شده دقت کنید ابتدا p=p->next شده سپس data چاپ می شود. پس بعد از اینکه p به list اشاره کرد (یعنی هر دو به اولین عنصر اشاره می کنند) اول p به جلو کشیده شده (یعنی به عنصر دوم اشاره می کند) سپس data چاپ می شود.

hercool
شنبه 04 دی 1389, 07:11 صبح
یعنی تقریبا دو بار چاپ می کنند یا بهتر بگم یک حلقه تو در تو میسازد
درسته؟

سعیدسعید
سه شنبه 07 دی 1389, 19:07 عصر
بله تقریبا مثل حلقه های تو در تو کار می کند