View Full Version : link list
سایان گستر
پنج شنبه 20 اردیبهشت 1386, 12:13 عصر
با سلام
اگه میشه درباره ی لیست های پیوندی در زبان c کمی توضیح دهید:لبخندساده:
mzjahromi
پنج شنبه 20 اردیبهشت 1386, 12:21 عصر
درباره چه قسمتی از لیستهای پیوندی؟
به نظرم در این باره از کتابهای مربوطه استفاده کنید بهتر نتیجه میگیرید
سایان گستر
پنج شنبه 20 اردیبهشت 1386, 12:24 عصر
در مورد حذف یک عنصر از یک لیست پیوندی دو طرفه
emad_67
پنج شنبه 20 اردیبهشت 1386, 12:35 عصر
اینجا رو ببین در مورد حذف عنصر توضیحی داده ولی برای یک طرفه فکر کنم باشه اگه اینو بفهمی خودت میتونی دو طرفه هم بنویسی
http://www.aachp.ir/post.aspx?no=37
mzjahromi
پنج شنبه 20 اردیبهشت 1386, 12:37 عصر
اینجور مسائل عینا در کتابهای ساختمان داده ها حل شده با این حال
اگر P آدرس لینکی باشه که میخواد حذف بشه
P->R->l=P->l
P->l->R=P->R
free(P)
باز هم توصیه میکنم کتابها رو بررسی کنید
سایان گستر
پنج شنبه 20 اردیبهشت 1386, 12:46 عصر
مثلا توی کدوم کتاب ساختمان داده
لطفا اون کتابه رو معرفی کنید تا من اونارو بخونم
اخه من ترم دویی هستم و درس ساختمان داده ندارم
atilla snowman
چهارشنبه 16 خرداد 1386, 23:32 عصر
برای ساختمان داده کتاب Horwitz توی C و ++C به درد می خورند که ترجمه هم شدند. راحت می تونی گیرشون بیاری . جوابتم حتما توشون هست. من PDF اونا رو دارم . اگه پیداشون نکردی بهم mail بزن.
rezapazahr
یک شنبه 03 تیر 1386, 15:48 عصر
با سلام
من در مورد پیاده سازی دو تابع search, add اطلاعات مختصری دارم:
ابتدا توضیحاتی کلی در مورد دو تابع search , add میدهم و بعد هم برنامه اونها رو نشون میدم:
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 رو مورد بررسی قرار می دهمhttp://forum.p30world.com/images/smiles-icone/smilingsmiley.gif)
پیاده سازی 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 باشد(چه پیدا نشده باشد))از طریق آرگومان خروجی تابع سرچ به تابع مین ارسال کن
ان شاءالله از توضیحاتی که در مورد پیاده سازی توابع add, search راضی شده باشید
اگر در پیاده سازی با دیگر برنامه هایی که با لیست پیوندی نوشته می شدند هم اشکال داشتید باهام در میون بذارید
vBulletin® v4.2.5, Copyright ©2000-1404, Jelsoft Enterprises Ltd.