توضیح در مورد کد حذف یک عنصر از لیست پیوندی

[csharpprogramer88]

سلام
من دارم یک برنامه کوچیک لیست پیوندی مینویسم برای درس ساختمان داده ها البته از کتاب آقای جعفر نژاد + کد های موجود سایت استفاده کردم قسمت delete برام گنگه
دوستان لطفا هر توضیحی به ذهنشان میر سه ارائه کنند
سوالاتی که به ذهن خودم میرسه :


if( nextptr->id!= idtel)
{
curptr =nextptr ;
nextptr = nextptr->next;
continue ;
}
این شرط چه کار میکنه - continue کارش چیه





void linklist::delnode()
{
node *nextptr , *curptr ;
int idtel ;
if(!first)
{
cout<<"List is empty !" ;
getch() ;
return ;
}
cout<<"\nEnter id tel for delete : " ;
cin>>idtel ;
nextptr = curptr = first ;
while( nextptr != NULL )
{
if( nextptr->id!= idtel)
{
curptr =nextptr ;
nextptr = nextptr->next;
continue ;
}
else if( nextptr == first ) {
first = nextptr->next;
free( nextptr ) ;
free(curptr) ;
break ;
}
else {
if( nextptr== last )
last = curptr ;
curptr->next=nextptr->next;
free(nextptr) ;
break ;
}
} // while
}


:لبخندساده:

[quiet_programmer]

با سلام.

if(!first) {
cout<<"List is empty !" ;
getch() ;
return ;
}


دستور ایف برسی میکنه که First که به اول لیست پیوندی اشاره میکنه Null نباشه که اگه Null باشه یعنی لیست خالیه و عبارت «لیست خالیه» رو نشون میده و با دستور return روال کار خودش رو به پایان میروسونه.
در غیر این صورت یعنی اگه لیست خالی نباشه:
cout<<"\nEnter id tel for delete : " ; cin>>idtel ;


آیتمی که باید حذف بشه رو از کاربر دریافت میکنه و توی متغیر idtel میزاره.

nextptr = curptr = first ;

همونطور که میدونین برای حذف یک گره ماباید به گره قبل و بعد گرهی که قراره حذف بشه اشاره گر داشته باشیم.
برای این کار توی این کد:
اشاره گر nextptr برای اشاره به گرهی که قراره حذف بشه اشاره خواهد کرد.
اشاره گر curptr برای اشاره به گره قبل از گرهی که قراره حذف بشه.
و nextptr->next هم به گره بعد گرهی که قراره حذف بشه اشاره میکنه.
پس اول کار nextptr و curptr به ابتدای لیست اشاره میکنن.

حالا برای پیدا کردن گره مورد نظر لیست رو تا رسیدن به گره مورد نظر یا انتهای لیست(در صورتی که مقدار وارد شده در لست وجود نداشته باشه طی کنیم)
برای همین ما از همون اول فرض رو بر این میزاریم که گره توی لیست وجود نداره و میخواییم لیست رو تا انتها پیمایش کنیم. وقتی به گره مورد نظر رسیدیم فرضمون رو نقض میکنیم و میگیم نه پیمایش تا اینجا بسه که توی کد نشون میدم.
while( nextptr != NULL )
با این حلقه میگیم تا زمانی که nextptr به آخر نرسیده حلقه رو ادامه بده که میخوام تا آخر لیست رو پیمایش کنم

if( nextptr->id!= idtel) {
curptr =nextptr ;
nextptr = nextptr->next;
continue ;
}


تو اینجا میگیم اگه گرهی که الان nextptr داره بهش اشاره میکنه، آیتمش برابر آیتمی که قراره حذف بشه، نباشه curptr به آیتم جاری اشاره کنه و nextptr یکی بره جلو و continue باعث میشه که کدهای زیرین برسی نشن. ببینید گفتم برسی نشه نه اینکه اجرا نشه چون اگه continue هم نمیزاشتیم هم اجرا نمیشد(خوب دلیلش واضحه دیگه). ولی این دستور شاید برای اینه که مثلا سرعت اجرا بره بالا. حتی میتونی این دستور رو حذف کنی.

else if( nextptr == first ) { first = nextptr->next;
free( nextptr ) ;
free(curptr) ;
break ;
}


این ایف وقتی برسی میشه که nextptr آیتمش برابر با آیتم ورودی باشه. یعنی nextptr داره به گرهی که قراره حذف بشه اشاره میکنه. بازم گفتم برسی نه اجرا.
خوب تو این حالت اگه گرهی که قراره حذف بشه گره ابتدا باشه اونوقت First به گرهی که بعد از گره شروع قرار داره اشاره میکنه(یعنی گره دوم) و با این کار گره اول که گره مورد نظر برای حذف بود حذف میشه. و فضای اشغالی با تابع free آزاد میشه و به سیستم عامل برگردونده میشه. با استفاده از دستور break از حلقه خارج میشه(یعنی دیگه پیمایش نکن و از حلقه خارج شو).

else { if( nextptr== last )
last = curptr ;
curptr->next=nextptr->next;
free(nextptr) ;
break ;
}


در صورتی که گره مورد نظر پیدا شد و گره مورد نظر گره اول نبود:
اگه گره مورد نظر گره آخر بود اونوقت last به گره قبل از گره مورد نظر اشاره کنه(همونطور که قبلا گفتیم curptr به گره قبل از گره حذفی اشاره میکنه).
در نهایت گره قبلی به گره بعد از گره حذفی اشاره کنه(یعنی حذف بشه).
و فضای اشغالی توسط تابع free آزاد بشه
و در نهایت از حلقه توسط دستور break خارج شو.

موفق باشی

[csharpprogramer88]

سلام
تشکر که جواب دادید
توضیح شما کامل بود ولی سوالی دارم درباره این if



if( nextptr->id!= idtel) {
curptr =nextptr ;
nextptr = nextptr->next;
continue ;
}


این کد داره کل لیست را پیمایش میکنه یعنی اگر برابر با آیتم نبود به نود بعدی اشاره میکند ولی اگر برابر با نود شد چرا چیزی free نمیشه ؟
اینطوری که من فهمیدم ما نیازی به آن دو else نداریم چون کل لیست داره پیمایش میشه بالاخره آیتم چه در آخر چه در اول توسط شرط اولی پیدا میشه و else اجرا نمیشه( چون توسط شرط اول پیدا شده)

فقط حذف گره است که در ابتدا یا انتها با هم فرق میکنه

[quiet_programmer]

با سلام.

ببین اگه برابر نود شد قسمت else اجرا میشه. میاد میگه نود اول لیسته؟ فرض کنیم نه تو وسط های لیسته. else دوم که یه else بدون ifه اجرا میشه. به } بعد else دوم دقت کن. یعنی با این شرایط else آخری حتما اجرا خواهد شد. تو این قسمت میگه اگه نود پیداشده آخر لیست باشه که تک دستورش اجرا بشه و بقیه کد هم اجرا بشه. اگرهم که نود آخری نباشه اونوقت بیا دستورای بعد if یعنی دستورهای زیر رو اجرا کن که باعث حذف نود از لیست میشه.

curptr->next=nextptr->next;

free(nextptr) ;

break ;


و else اجرا نمیشه( چون توسط شرط اول پیدا شده)

چرا الس اجرا نشه؟ ببین نود حتما توسط شرط اول(اگه تو لیست باشه) پیدا خواهد شد و با پیداشدن شرط ایف رو نقض میکنه یعنی فالس میشه و حتما دو تا السهای بعدی برسی میشن.

[csharpprogramer88]

با سلام.

ببین اگه برابر نود شد قسمت else اجرا میشه. میاد میگه نود اول لیسته؟ فرض کنیم نه تو وسط های لیسته. else دوم که یه else بدون ifه اجرا میشه. به } بعد else دوم دقت کن. یعنی با این شرایط else آخری حتما اجرا خواهد شد. تو این قسمت میگه اگه نود پیداشده آخر لیست باشه که تک دستورش اجرا بشه و بقیه کد هم اجرا بشه. اگرهم که نود آخری نباشه اونوقت بیا دستورای بعد if یعنی دستورهای زیر رو اجرا کن که باعث حذف نود از لیست میشه.

curptr->next=nextptr->next;

free(nextptr) ;

break ;



چرا الس اجرا نشه؟ ببین نود حتما توسط شرط اول(اگه تو لیست باشه) پیدا خواهد شد و با پیداشدن شرط ایف رو نقض میکنه یعنی فالس میشه و حتما دو تا السهای بعدی برسی میشن.



if( nextptr->id!= idtel) {
curptr =nextptr ;
nextptr = nextptr->next;
continue ;
}

شما یه توضیحی در باره این بدید آیا نودی را حذف میکنید یا نه ؟؟ آخه تو این شرط نود چه در خر یا در وسط یا اول باشه تو همین شرط پیدا میشه . ایا درست فهمیدم؟

تا اونجا که من میدونم اگر if اجرا شد دیگه esle ها اجرا نمیشن اگر جز این حرف منه توضیح بدید

با تشکر

[quiet_programmer]

بله همینطوره اگه ایف اجرا بشه دیگه الس اجرا نمیشه.

نود توسط ایف اولی پیدا شد یعنی دستور ایف نتیجه فالس رو داد و کد داخلش اجرا نشد و باید بره قسمت الس رو برسی کنه.

اصلا من این قسمت از کد رو به زبان فارسی مینویسم.

آیا نودی که الان nextptr به اون اشاره میکنه برابر عدد مورد نظر ماهست یانه:

اول بگیم نه مساوی نیست(یعنی شرط برابر true): پس دستورات ایف اجرا میشه و میگه آقای nextptr به گره بعد اشاره کن و خانوم currptr شما هم اگه زحمتی نیست به نود قبلی اشاره کن. بعد اینجاست که دیگه السها حتی برسی هم نمیشن چه برسه اجرا.

بعد بگیم بله مساویه(یعنی شرط برابر false): یعنی اینکه نود پیدا شده و باید بره حذف کنه. پس السها برسی میشن. ادامه توضیح هم تو پست شماره 4#.

افتاد؟

[csharpprogramer88]

پس با این تفاسیر این کد حذف فقط عنصر اول و آخر را حذف میکنه ؟
عنصر با آدرس P را حذف نمیکنه ؟

البته در شرط اول ما داریم عنصر p را پیدا میکنیم که پس از نقص شدن شرط ، الس اجرا میشه الس هم میگه یا عنصر اول باشه یا عنصر آخر

این برام گنگنه لطفا تشریح کنید که نود با آدرس P چطور حذف میشه
با تشکر

[quiet_programmer]

ببین همین. من تو پست چهارم گفتم که به براکت باز تو الس آخر توجه کن.

من هم اولش به اشتباه افتادم و گفتم این برنامه فقط عنصر اول و آخر رو حذف میکنه ولی اون براکت باز تو الس آخر باعث میشه که الس دیگه الس خالی بشه و نه الس ایف. یعنی اون براکت باز ایف رو از الس بالایی جدا میکنه. در نتیجه الس آخری میاد میگه در غیر این صورت حالا: اگه آخرین نوده که تک دستور من رو که کد زیر باشه رو اجرا کن

last = curptr ;

بعد سه دستور بعدی رو که مر بوط به الس هست رو اجرا کن. در صورتی که هم نود آخری نباشه تک دستور الس اجرا نمیشه و کد حذف اجرا میشه.

ببین برای اینکه بهتر متوجه بشی من کد خودت رو به صورت زیر دو باره نویسی میکنم که شاید خوانایی بهتری داشته باشه ولی در اصل همون کده.

void linklist::delnode()
{
node *nextptr , *curptr ;
int idtel ;
if(!first)
{
cout<<"List is empty !" ;
getch() ;
return ;
}
cout<<"\nEnter id tel for delete : " ;
cin>>idtel ;
nextptr = curptr = first ;
while( nextptr != NULL )
{
if( nextptr->id!= idtel)
{
curptr =nextptr ;
nextptr = nextptr->next;
continue ;
}
else if( nextptr == first )
{
first = nextptr->next;
free( nextptr ) ;
free(curptr) ;
break ;
}
else
{
(nextptr== last)?(last = curptr):NULL;
curptr->next=nextptr->next;
free(nextptr) ;
break ;
}
} // while
}

اگه باز متوجه نشدی حتما بگو. چون برام جالب شد. اینکه من نمیتونم خوب توضیح بدم یا شما به دقت جوابای منو نمیخونی.

[farghabil]

سلام بچه ها، منم یه سوال شبیه همین دارم. میشه بهم کد حذف عنصر از لیست پیوندی max heap رو بدید؟خیلی لازم دارم
ممنون میشم اگه زود بهم جواب بدید

[farghabil]

بچه ها خوشم میاد کسی جواب نمیده. 1 هفته از سوال پرسیدم میگذره. حداقل بگید نمی دونم هر روز سر نزم