حل مشكلات مربوط به كار با ليست پيوندي

واضح آرشیو وب فارسی:سایت ریسک: rezapazahr25-06-2007, 09:04 PMسلام به همگي :10: از آنجاييكه انتظار ميرفت براي كار با ليست پيوندي وحل مشكلات مربوط به اون يسئوالات متنوعي مطرح بشه به اين فكر افتادم تا بحث جديدي پيرامون اون ايجاد كنم و ان شاءالله به كمك دوستان بتوانيم به گوشه اي از سئوالاتي كه مطرح ميكنيد پاسخ دهيم. در ابتدا براي آشنايي نكاتي در مورد ليست پيوندي و توابع add , search عرض ميكنم كه ان شاءالله مفيد قرار گيرد: اول يه سري مفاهيم رو معرفي ميكنم وبعد به سراغ اصل كار مي پردازيم. ================================================== ============= در ليست پيوندي گاهي اوقات head=null تعريف ميشه اينكار به چه معني است؟ يعني بيا اشاره گر حاوي آدرس اولين نود(node)(يا ليست يا استراكت) رو برابر نال كن ودر واقع با اين دستور ميگيم هد به هيچ جايي اشاره نكنه سئوال: واسه چي همچين كاري رو با هد ميكنيم؟ براي پاسخ به اين سئوال قبلش يه سئوال ديگه مطرح ميكنم: به چه دليل مقدار متغيري رو قبل از اينكه مثلا تو يه حلقه قرار بگيره مقدار دهي مي كرديم؟ خوب معلومه ديگه به اين دليل كه قبل از اينكه كاري با اون متغير انجام بگيره يه مقدار اوليه داشته باشه (مثلا مقدار0 يعني اينكه هنوز مقداري واردش نشده وفعلا هيچ مقداري نداره )ورايانه با ديدن اون متغير بدون مقدار اوليه متعجب نشه. حالا به سئوال اصليمان جواب ميديم: به اين دليل مقدار هد رو در اولين مرحله برابر نال ميكنيم كه بگيم تا الان هيچ ليست جديدي مانساختيم كه بياييم بگيم هد ما به اون اشاره كنه(0ليست داريم) سئوال مگه تو هد چي بايد هميشه قرار بگيره؟ هد هميشه حاوي آدرس نود(ليست)اوله سئوال : چرا بايد آدرس اولين نود رو يه جايي حفظش كنيم؟ جواب وقتي ما malloc مي كنيم در واقع سيستم مياد يه حافظه براي نود ما كنار ميذاره(مثلا آدرس 1000 رو كنار ميذاره تا ما توش اطلاعات وارد كنيم وبريزيم) خوب اين آدرسي كه كنار ميذاره نبايد اونو يه جايي محفوظ نگهش داريم (چون بعده ها مي خواهينم از طريق اين آدرس به محتواي اون حافظه (كه همون حافظه نودمونه)دست پيدا بكنيم) جواب:بله بايد آدرشو تو يه اشاره گر بذاريم پس مي آييم آدرس نودي رو كه malloc برامون تو سيستم كنار گذاشته يه جايي ذخيره ميكنيم تااگه بعدا مورد نياز بود ازش استفاده كنيم نكته:مقادير را ما تو متغير ذخيره مي كرديم ولي آدرس ها رو تو اشاره گرها ذخيره مي كنند در ضمن اشاره گرها رو مثل متغير ها بايد از قبل (معمولا ابتداي برنامه) تعريف كرد پس اشاره گر هد كه حاويه آدرس نوده اوله رو از قبل بايد تعريف كرده باشيم.كه براي تعريف بايدبگيم : node *head (يعني هديه اشاره گره حاويه آدرسه يه نوده) تعريف ليست پيوندي: ليست پيوندي ساختمان داده ايه كه اساسه كارش بر مبناي استراكته و به هر استراك يه آدرس تعلق گرفته(باmalloc كردن) كه معرف شماره اون استراكت هست(يا بهتر بگيم آدرس اون استراكت) پس ليست پيوندي ازچند ليست(استراكت)كه هر استراكت يه خانه پيوند(خونه لينك) داره تشكيل شده است شايد اين سئوال پيش بياد كه اين استراكت ها چطور با هم در ارتباطند؟ توي خونه ديتا هر نود اطلاعات اون نود قرار گرفته و تو خونه لينكش آدرس نود بعدي قرار گرفته كه همين موضوع باعث ميشه ما به آدرس نود بعدي دسترسي پيدا كنيم و ار آنجا به محتويات خونه ديتايش دسترسي پيدا كنيم سئوال با چه دستوري به خونه ديتا وخونه لينك ليست پيوندي دسترسي پيدا ميكنند؟ جواب: با دستورp->data (كه p اسم اون نوده وميتونه ali ويا reza ويا new و... باشه) وبا دستور p->link به خونه لينك كه حاويه آدرس نوده بعديه دست پيدا ميكنند. (ان شاءالله كه تا اينجا خسته نشده باشيد) ((new=(struct name *)malloc(sizeof(struct name : name اي كه شما تو دستوره malloc ازش استفاده كرديد همون ساختمان داده ايه كه ما داريم ازش تو برنامه نويسي استفاده ميكنيم كه اون ساختمان داده چيزي نيست مگر struct ويا نودي كه تو صحبتهام در موردش صحبت مي كردم ودر واقع شما داريد يه نود رو در سيستم ايجاد ميكنيد هر موقع يه نود ايجاد ميكنيد بايد آدرس اون نود ساخته شده رو در يه اشاره گر بريزيد كه شما اون رو new معرفي كرديد(پس از الان به بعد new حاويه آدرس هر نوده جديدمان است)كه اگه اين اولين نوديه كه داريد ايجاد ميكنيد طبق صحبت هاي قبلي بايد مقدار new در head قرار بگيره(در واقع آدرس اولين نود رو ميآييم تو head مي ريزيم) حال راهكارهاي رسيدن به نتيجه دلخواه(پياده سازي add و search ) رو مورد بررسي قرار مي دهم:) پياده سازي add : كاري كه شما بايد انجام بديد اينه كه هر بار كه تابع add فراخواني ميشه يك نود به ليست اضافه بشه كه قطعا با malloc كردن اينكار انجام ميشه و نيز بااينكار آدرس نودمان وارد اشاره گر new ميشه حال چون اين نود, نود اوله پس مياييم آدرس اولين نود رو تو head قرار ميديم و در ضمن يك شرط قبل ميگذاريم كه اگه اين نود , نود اوله بياد آدرسشو تو head هم قرار بده ( يعني head = new )(با اين دستور آدرس نود اول تو هد (اشاره گري كه به نود اول اشاره ميكنه)قرار ميگيره) توجه شود كه تا ما اشاره گري رو حاويه آدرسي كرديم اون اشاره گر مياد به اون حافظه (كه تو اينجا نوده )اشاره ميكنه سئوال : گفتيم يه شرط قبل ميذاريم كه اگه نود اوله بياد head رو برار new كنه حال اين سئوال پيش مياد كه به رايانه چطور بفهمونيم اين نود اوله؟ كافيه بگيم: (if(head==null head=new new->link=null ودر ضمن خونه لينك نود اول رو نال ميكنيم يعني اين نودنوداول يا آخره(فعلا) ونود ديگه اي ايجاد نشده كه ما آدرس نود دوم رو تو خونه لينك نود اول قرار بديم پس مقدار شو نال فعلا ميذاريم پس بااين شرط رايانه متوجه ميشه كه اين نود نوده اول بوده و آدرسشو تو هد قرار ميده درضمن توجه شود كه اون زمانيكه نود رو با mallocاايجادكرديم اطلاعات نودرو از كاربر بگيريم وتو نود خونه ديتايش قرار بديم يعني new->data=item كه تو اينجا item حاويه اطلاعات نودمان است(كه ميتونه نمره يه دانشجو يا شماره دانشجويي او ويا نام يه شخص و... باشد) واز كاربر گرفته شده است نكته مهم: از حالا به بعد به اشاره گر ديگري نياز داريم كه هر بار كه نود جديدي به نود ها اضافه شد اشاره گري هم به نود قبلش اشاره كرده باشه وبتوان با استفاده از اون آدرس نود جديد رو داخله خونه لينك نود قبل قرار داد داريم ليست هاي پيوندي ايجاد ميكنيم نه ليست هاي منفرد وجدا از هم وقرار دادن آدرس نود جديد تو خونه لينك نود قبله كه باعث ميشه هر نود با نود بعدش در ارتباط باشه پس: ((new= (struct*)malloc(sizeof(struct new->data=item (if(head==null head=new previos=new new->link=null else previos->link=new new->link=null previos=new دليل: چرا previos=new? به اين دليل كه هر بار كه يه نود ساخته شد previos رو نود قبل قرار داشته باشه و به اون اشاره كرده باشه وبتوان آدرس نود جديد رو در خونه لينك نود قبل(كهprevios داره بهش اشاره ميكنه) قرار داد اما چرا ميگم head=new (وتنها وتنها بار اول يعني وقتي نود اول ساخته ميشه ونه زماني ديگر!) چون اگه قرار باشه new=head بشه هربار كه يه نود ايجاد ميشه و مقدار اشاره گر new حاويه آدرس نود جديد ميشه هد هم به همون جا اشار ميكنه و هر بار شاهد اين هستيم كه هد يكي يكي جلو مياد(چون يكي يكي نود جديد به نود ها اضافه ميشه) و هدف اصلي هد تو برنامه كه نگهداري آدرس اولين نوده عملي نميشه وما آدرس اولين نود رو از دست خواهيم داد ودر ضمن با دستور new=previos آدرس پرويو تو نيو قرار ميگيره كه درست نيست هر نود كه توليد ميشه هر بار جلو تر ازپرويو است پس وقتي كه آدرس نود جدبد تو خونه لينك پرويو قرار گرفت وديگه كاري با نود قبل نداشتيم پرويو رو به جلو مي بريم با دستور previos=new تا توي مرحله بعد كه يه نود جديد اضافه ميشه (در جلوي پرويو)بتونه آدرس اونو تو خونه لينكش قرار بده قبل از نوشتن تابع سرچ توضيحاتي كلي در مورد نحوه پياده سازي اين تابع عرض ميكنم: تابع سرچ تابعيه كه يه داده از كاربر ميگيره و سرچ ميكنه آيا اين داده تو خونه ديتاي ليست هاي پيوندي قرار داره يا نه؟ براي مثال فرض كنيم ميخواهيم بببينيم آيا تو ليست پيوندي هامون داده اي با مقدار 100(ميتونه شماره دانشجويي يا اسم اشخاص يا ...موضوع مورد سرچ باشه)پيدا ميشه يا خير؟ به نظر شما چه الگوريتمي ميتواند وجود يا عدم وجود يه داده رو تو مسئله قبل برامون مشخص كنه؟ جواب: راهي رو كه براي حل مسئله قبل پيشنهاد ميكنم اينه كه بياييم تا زماني كه استراكت داريم بگرديم وچك كنيم تك تك خونه هاي ديتاي نود هارو و وجود و يا عدم وجود داده مورد نظر رو در ليستها بررسي كنيم نكته : به متغيري نياز داريم (مثل found ) كه اگه داده مورد نظر تو نودها وجود داشت ويافت شد مقدارش برابر 1( يعني دادهمون تو ليست ها موجود بوده)بشه براي چك كردن تك تك نودها به يه حلقه نياز داريم.اما سئوال : اين حلقه تا كي كار بررسي تك تك نود ها رو انجام ميده(ميخواهيم ببينيم شرط حلقمون تو برنامه چي بايد باشه؟) سريعترين جوابي كه به ذهنمون ميرسه اينه كه تاوقتي حلقمون در حال تست تك تك نود ها باشه كه ديگه نود نداشته باشيم.ميگيم درست اما اگه داده مورد نظر تو نود ها يافت شد آيا باز بايد حلقمون به بررسي بقيه نود ها بپردازه؟ (قرارشد تابعمون ببينه آيا داده مورد نظر تو نود ها قرار داره يا نه؟(همينكه داده مورد جستجو تو نودها پيدا شد كار تابع تموم شده)(بررسي وجود يا عدم وجود داده در ليست پيوندي)) ميگيم علاوه بر اينكه شرط ميكنيم تا اتمام تمامي نود هاي ليست پيوندي عمليات سرچ رو انجام بده علاوه بر اون اگه داده مورد نظر يافت شد(يعنيfound=1) پس ديگه از حلقه بيا بيرون. توجه شود كه شرط حلقمون شد شرط اولي && شرط دومي يعني هم بايد حلقمون نه به انتهاي خود (اتمام نود )رسيده باشد وهم تا وقتي حلقه برقراره كه داده مورد نظز يافت نشده باشه(يعني چون ميگيم هم اين وهم آن پس از عملگر اند(&&) استفاده ميكنيم) پس بالايي ميشه شرط حلقه اما تو خود حلقه يه شرط (if) قرار ميديم كه اگه داده مورد نظر يافت شد ((if (p->data==m)( كه m همون داده مورد نظره)مقدار found رو برابر 1 ( يعني داده پيدا شده)كن واگر found==0 شد (يعني داده هنوز پيدا نشده)بيا به سراغ نود بعدي برو(حتما ميدانيم كه يه اشاره گر براي اينكه بتونه هربار به نود بعدي اشاره كنه بايد حاويه آدرس نود بعدي بشه(يعني حاويه آدرس خونه لينكش بشه))(من باب ياد آوري)پس تو اين حالت ميگيم بايد p=p->link بشه سئوال: مقدار اوليه found رو در ابتداي برنامه قبل از اينكه وارد حلقه بشه برابر چند در نظر بگيريم؟ جواب: طبيعتا بايد برابر 0 باشد كه بگيم داده مون تاالان پيدا نشده ونيز اگه حلقه اي كه تمام نود هارو چك ميكنه رسيد به انتهاش و داده مورد نظر يافت نشده بود چون found=1 تو حلقه نشده پس مقدار فوند برابر 0 باقي خواهد ماند پس ما تالان آمديم و p رو برابر آدرس اولين نود(head)كرديم(قبل از شروع حلقه ) وتو حلقه آورديمش اين اشاره گر رو و هربا برابر آدرس موجود تو خونه لينكش كرديم(يعني هر با به جلو برديمش) و عمليات سرچ داده مورد نظر رو تا وقتي به انتهاي نود ها نرسيده باشيم ونيز داده مورد نظر يافت نشده باشد انجام داديم اما سئوال بسيار مهم واساسي: فرض كنيم كه برنامه رو نوشتيم وركامپايلر(مفسر) رسيدبه عبارت p=head (اين دستور رو براي اين نوشتيم كه پي حاويه آدرس نود اول بشه وبتونه يكي يكي به جلو بره(در اصطلاح بتونه عمليات پيمايش رو بتونه انجام بده)) حال اين سئوال بزرگ براي كامپايلر پيش ميآيد كه: 1- head ديگه چيه؟ 2-حالا هد هر چي كه هست باشه مقدارش چيه كه بيام طبق فرمايش برنامه نويس تو پي بذارم؟ براي پاسخ به دو سئوال قبل بايد اولا هد يه جايي تعريف بايد بشه و دوما مقدارشو از تو تابع add(چون تو اين تابع مقدار دار شده ) ازطريق خروجي اش(آرگومان خروجيش) به تابع مين واز آنجا با ارسال به ورودي تابع سرچ(آرگومان ورودي تابع) عمل كرده ومشكل رو برطرف كنيم. پس تو ( )search ( )كه خط اول برنامه مينويسيمش بايد تو آرگومانها مقدار ورودي وخروجي تابع رو ذكر كنيم.(به ترتيب تو آرگومان(پرانتز) سمت راست ورودي تابع وتو آرگومان سمت چپ خروجي تابع رو مي نويسيم) كه ميدونيم ورودي هاي تابع سرچ عبارتند از: الف)head : اشاره گر حاويه آدرس نود اول(كه هد از تابع اد به تابع مين واز تابع مين به تابع سرچ پرتاب شده است.) ب) ورودي ديگري كه ما بايد به تابع سرچ ارسال كنيم m (همون مقداره هستش كه قراره تو نود ها سرچ بشه)(واين مقدار رو تنها از تابع مين به تابع سرچ ارسال ميكنيم) توجه:(در مورد اينكه خروجي اين تابع دارد يا خير؟) در نهايت بايد جواب وجود ويا عدم وجود داده m تو تابع سرچ رو به تابع مين ارسال كنيم(با دستور return found اين كار رو ميتونيم انجام بديم) اما دستورات برنامه search : (int search (struct *head,int m } ;int found=0 ;struct *p ;p=head ((while((!found)&&(p!=null (if(p->data==m ;found=1 (if(found ;p=p->link { ;return found { اما توضيحاتي در مورد اين 13 خط: تو خط اول ورودي هاي تابع سرج يكي هد هستش كه از تابع اد به تابع مين واز آنجا به تابع سرچ ارسال شده است وديگر ورودي تابع سرچ m هستش (توجه گردد كه در آرگومان ورودي تابع اد نيز هد را قرار دهيد(چرا؟چون هد رو بشه از تابع اد به مين و از آنجا به تابع سرچ ارسال كرد)و اين چيزي كه توي اين پرانتز الان عنوان شد به تابع اد حتما بايد اضافه كنيد وگرنه تابع سرچ كار نمي كند) نكته اساسي ديگه اينه كه دستور توي خط بعد هم به دستورات توي مين اضافه شود(در غير اينصورت تابع سرچ كار نمي كند)و همونطور كه ميبينيد از تابع مين به وسيله اين دستور به تابع سرچ m ارسال مي شود: (search(&head,&m ) توجه: نوع هر ورودي ويا حتي خروجي بايد در آرگومان تابع ذكر گردد(مثلا struct *head ويا int m ) كه ميبينيد در تابع سرچ نوع ورودي ها (يكي head ويكي m )ونيز نوع خروجي (خروجيمون found است كه بايد به تابع مين ارسال گردد ونوع اين خروجي int است) تو آرگومان هاي اين تابع ذكر شده استوبايد هميشه ذكر گردد تو خط سوم مقدار found رو 0 بنا به دلايلي كه در بالا گفته شد مقدار دهي كرديم تو خط چهارم پي رو از جنس اشاره گري به يك استراكت ويا نود(كه آدرس يه نود رو هر بار داره) معرفي كرديم تو خط پنجم آدرس نود اول رو تو پي قرار داديم(پي رو مقدار دهي اوليه كرديم تا بتواند عمل پيمايش را انجام دهد)كه كاملا واضحه آدرس هد از تابع اد به تابع مين واز آنجا به تابع سرچ ارسال ميشه و اين مقدار از تو هد وارد پي ميشه قبل از اجراي حلقه. تو خط ششم هم گفتيم مادامي كه نات فاند(يعني نات0 كه ميشه 1 )(مادامي كه داده مون تو نود ها پيدا نشده)و پي مخالف نال است(يعني اشاره گر پي به خارج حلقه نرسيده و بدانجا نرفته (توجه شود كه وقتي در مرحله آخر اشاره گر پي به پي خونه لينك اشاره كرد چون پي خونه لينك آخرين نود ناله پس پي برابر نال ميشه و ديگه اين شرطي كه ما قرار داديم ( پي مخالف نال ) مانع ادامه روند اجراي حلقه ميشود) بيا: خط هفتم:اگه پي خونه ديتا برابر ام شد(يعني داده مورد نظر پيدا شد )بيا: خط هشتم:فاند رو برابر يك كن(يعني داده پيدا شده) خط نهم:واگر براي فاند (يعني داده پيدا نشده) خط دهم: بيا پي رو پيمايش كن (يكي به جلو ببر)) خط دوازدهم:بيا مقدار فاند رو (چه 1 باشد (چه پيدا شده باشد) وچه 0 باشد(چه پيدا نشده باشد))از طريق آرگومان خروجي تابع سرچ به تابع مين ارسال كن ان شاءالله تا اينجا اين مطالب نظر شما را جلب كرده باشد. يا حق سایت ما را در گوگل محبوب کنید با کلیک روی دکمه ای که در سمت چپ این منو با عنوان +1 قرار داده شده شما به این سایت مهر تأیید میزنید و به دوستانتان در صفحه جستجوی گوگل دیدن این سایت را پیشنهاد میکنید که این امر خود باعث افزایش رتبه سایت در گوگل میشود

این صفحه را در گوگل محبوب کنید

[ارسال شده از: سایت ریسک]

[مشاهده در: www.ri3k.eu]

[تعداد بازديد از اين مطلب: 545]