View Full Version : لطفا معکوس کردن یک لیست را برام تشریح کنید ( از کتاب هوریتز)
csharpprogramer88
سه شنبه 08 آذر 1390, 21:25 عصر
سلام
این کد را از صفحه 182 کتاب هوریتز گرفتم که یک لیست را معکوس میکند
لطفا برایم تشریح کنید چگونه این عمل انجام میگیرد
tamplate <class type>
void list <type>::invert()
{
listnode<type>*p=first,*q=0;
whili(p)
{
listnode<type>*r=q;q=p;
p=p--->link;
q--->link=r;
}
first=q;
}
اگر با رسم شکل توضیح بدید عالی میشه با تشکر
مسعود اقدسی فام
چهارشنبه 09 آذر 1390, 00:59 صبح
سلام
این کد را از صفحه 182 کتاب هوریتز گرفتم که یک لیست را معکوس میکند
لطفا برایم تشریح کنید چگونه این عمل انجام میگیرد
tamplate <class type>
void list <type>::invert()
{
listnode<type>*p=first,*q=0;
whili(p)
{
listnode<type>*r=q;q=p;
p=p--->link;
q--->link=r;
}
first=q;
}
اگر با رسم شکل توضیح بدید عالی میشه با تشکر
q یه اشارهگره که آخر هر مرحله ابتدای لیست جدید رو نگه میداره.
p اشارهگریه که از ابتدای لیست فعلی شروع میشه و یکی یکی پیش میره.
r اشارهگر موقتیه که برای عملیات استفاده میشه.
اول q داخل r و p داخل q قرار میگیره. بعد p یه گره به جلو پیش میره. در آخر گره بعدی q، گره r معرفی میشه. شروع تکرار بعدی گره q داخل r و گره بعدی لیست فعلی داخل q قرار میگیره. خط آخر حلقه این گره رو به ابتدای لیست اضافه میکنه. چون عنصر بعدیش رو r قرار میده که مرحله قبل عنصر اول بود.
در واقع لیست معکوس از آخر به اول ساخته میشه. یعنی آخرین گره این لیست اول از همه بهش اضافه میشه و همهی گرهها به ابتدای اون وارد میشن.
نمیدونم چقدر توضیحات کمکتون کرده. ولی اگه با یه لیست سادهی چهار گرهی این عملیات رو به صورت دستی روی کاغذ پیادهسازی کنید، الگوریتم دستتون مییاد.
فقط توجه داشته باشید که ترتیب مقدار دهی مقادیر سطر اول داخل حلقه مهم هستن. یعنی اول q وارد r میشه، و بعد p وارد q میشه. اما جای دو سطر بعدی رو میتونید عوض کنید. چون هیچ ارتباطی به هم ندارن.
در انتها هم first برابر q قرار داده میشه که به آخرین گره اضافه شده به لیست اشاره میکنه. همونطور که گفتم لیست از آخر به اول پر شده. به همین خاطر آخرین گره اضافه شده اولین گره از ابتدا خواهد بود.
vBulletin® v4.2.5, Copyright ©2000-1403, Jelsoft Enterprises Ltd.