مشاهده پست های بی پاسخ | مشاهده موضوعهای فعال تاریخ امروز یکشنبه 21 اکتبر, 2018 7:05 pm



پاسخ به موضوع  [ 5 پست ] 
 لیست های پیوندی ( Linked List ) در ساختمان داده ها 
نویسنده پیام

عضو: پنجشنبه 03 آوریل, 2008 12:29 pm
پست ها: 146
پست لیست های پیوندی ( Linked List ) در ساختمان داده ها
این نوع ساختار داده ها ساختاری پویا Dynamic است . یعنی به هنگام نیاز به استفاده از حافظه اصلی با درخواستی كه مینماییم بخشی در اختیارمان قرار میگیرد . و در صورت عدم نیاز با رها سازی ان بخش به مجموعه حافظه قابل استفاده باز میگردد .

یادآوری میکنم که ساختار ایستا یا آرایه ساختاری است که توانایی كم و زیاد شدن حافظه در ساختار مربوطه را نداریم. تفاوت لیست پیوندی با آرایه در ان است كه اعضا در لیست پیوندی پراكنده هستند .

هر عنصر لیست پیوندی در كنار خود حداقل یك بخش جهت حفظ آدرس عضو بعدی وجود دارد . در نتیجه یك خانه دو قسمتی است :
كه خانه سمت راست آدرس لیست پیوندی بعد از خود را نشان میدهد . ( اشاره گریست به خانه بعد از خود ) و خانه سمت چپ اطلاعات را نگهداری میكند .
برای نمایش خانه سمت چپ و اینكه محتویات این عنصر چیست از (Info(Address مثل (Info(345H برای نمایش خانه سمت راست عنصر و اینكه این عنصر به كدام خانه بعد از خود اشاره میكند از (Link(Address مثل (Link(354H استفاده میكنیم .
در این لیست ها كه لیست های یكطرفه Single Link List گفته میشود اطلاعات تنها یك آدرس حفظ میشود . آدرس شروع در این ساختمان داده ای بسیار مهم است كه ان را در متغیری كمكی به نام First نگهداری میكنیم .


محدوده موجودیت Availability Area
محدوده ایست كه در آن عناصر لیست های پیوندی در اختیار قرار میگیرند . در ساختارهای پیوندی درج و حذف اطلاعات فیزیكی است به منظور درك بهتر عملیات را خود انجام میدهیم . باین منظور فرض میكنیم مجموعه موجودیت عناصرش روی هم stack شده اند . بنابراین مجموعه stack گونه ای را ایجاد نموده اند ( Availability Stack ) گویند . اشاره پیكان ها میتواند به هر نقطه ای باشد . به نقطه بالایی این محیط Avail گوییم .


آخرین بار توسط Expert در چهارشنبه 11 ژوئن, 2008 10:29 am ویرایش شده است و در کل 1 بار ویرایش شده.



چهارشنبه 11 ژوئن, 2008 10:22 am
مشخصات شخصی

عضو: پنجشنبه 03 آوریل, 2008 12:29 pm
پست ها: 146
پست Re: لیست های پیوندی ( Linked List ) در ساختمان داده ها
در اینجا الگوریتمی برای درج عضو جدید در ابتدای یك لیست پیوندی ارائه می کنیم:
ضمیمه:
data1.JPG

الگوریتم فوق را اینگونه فراخوانی كرده ایم : (First = Insert(X,First كه در آن X مقداریست كه میخواهیم در لیست اضافه كنیم . First اشاره گریست به خانه اول لیست .

در گام اول الگوریتم چك كرده ایم كه آیا حافظه ما خانه خالی دارد ؟ اگر ندارد عملیاتی انجام ندهد و همان first را دست نخورده بازگرداند .
در گام دوم به new میگوییم به همان خانه ایكه Avail اشاره میكند اشاره كند .
در گام سوم مقدار (Link(Avail را به Avail میریزیم تا یك خانه از حافظه ما برای عملیات آزاد شود . یعنی Avail یك خانه در حافظه فرضی ما پایین امده است .
در مرحله چهارم X را به اطلاعات New و سپس (Link(New را گوییم كه به first اشاره كند . در نهایت مقدار new به جای First برگرداننده میشود .


برای مشاهده تصاویر و دانلود فایل های ضمیمه ، لازم است در سایت ثبت نام کرده و با نام کاربری خود وارد شوید. در حال حاضر ثبت نام در سایت رایگان است.


چهارشنبه 11 ژوئن, 2008 10:25 am
مشخصات شخصی

عضو: پنجشنبه 03 آوریل, 2008 12:29 pm
پست ها: 146
پست Re: لیست های پیوندی ( Linked List ) در ساختمان داده ها
الگوریتم درج یك عضو در انتهای یك لیست پیوندی

ضمیمه:
data2.JPG

سه مرحله اول از این الگوریتم دقیقا مانند الگوریتم قبل است .
در مرحله چهار عنصر جدید مقدار دهی میشود وچون قرار است اخر لیست قرار بگیرد مقدار null در ادرس ان قرار میدهیم .
در مرحله پنجم چك میشود كه آیا لیست پیوندی اصلا عضوی دارد ؟ اگر ندارد new بعنوان first بازگردانده میشود .
مرحله ششم به save میگوییم كه به first اشاره كند . چراكه همانطور كه گفتیم مقدار first حیاتی ترین مقدار در لیست پیوندی است لذا یك كپی از ان بر میداریم و به ادامه كارمیپردازیم .
مرحله هفتم میگوید تا وقتی كه اشاره گر save به null اشاره نكرده است save را یك مقدار به جلو بدهد .
در مرحله هشتم (link(save را میگوییم كه به new اشاره كند تا الگوریتم به پایان برسد .


برای مشاهده تصاویر و دانلود فایل های ضمیمه ، لازم است در سایت ثبت نام کرده و با نام کاربری خود وارد شوید. در حال حاضر ثبت نام در سایت رایگان است.


چهارشنبه 11 ژوئن, 2008 10:31 am
مشخصات شخصی

عضو: پنجشنبه 03 آوریل, 2008 12:29 pm
پست ها: 146
پست Re: لیست های پیوندی ( Linked List ) در ساختمان داده ها
الگوریتم درج در یك لیست پیوندی مرتب ( صعودی )
ضمیمه:
data3.JPG


در این مرحله از الگوریتم مقدار x را در مقدار (info(new میریزیم .

کد:
5.[check is the list empty ?]
if first=null
   then link(new):=null
   return(new)


در این مرحله چك میشود كه ایا اصلا لیست عضوی دارد اگر ندارد لینك new پوچ شود و مقدار new بعنوان first به برنامه فراخوان Postback شود .

کد:
6.[does the new node proceed of the others ? ]
IF info(new)<=info(first)
   link(new):=first
   return(new)


در این مرحله تست میشود كه ایا عضو اول ما از مقدار جدید كه قرار است اضافه شود كوچكتر است یا خیر در غیر اینصورت new ما first لیست شود .

کد:
7.[initialize search for last node]
  save:=first


باز هم یك كپی از first بر میداریم .

کد:
8.[search for prodecessor of new node ? ]
   repeat while link(save)<> null and info(link(save))<=info(new)
   save:=link(save)


تا وقتی كه لیست به پایان نرسیده است و محتویات link(save) از محتویات new كوچكتر نشده است به كار خود ادامه دهد . و مداما save را بروز برساند و به عنصر بعدی اشاره كند

کد:
9.[set link fields of new node and its prodecessor]
   link(new):=link(save)
   link(save):=new
10.[return first node pointer]
return(first)


برای مشاهده تصاویر و دانلود فایل های ضمیمه ، لازم است در سایت ثبت نام کرده و با نام کاربری خود وارد شوید. در حال حاضر ثبت نام در سایت رایگان است.


چهارشنبه 11 ژوئن, 2008 10:38 am
مشخصات شخصی

عضو: پنجشنبه 03 آوریل, 2008 12:29 pm
پست ها: 146
پست Re: لیست های پیوندی ( Linked List ) در ساختمان داده ها
الگوریتم حذف یك عنصر :

این الگوریتم را میتوان به شیوه های گوناگونی نوشت كه اینگونه شاید واضح ترین ان باشد .
ضمیمه:
data4.JPG


برای مشاهده تصاویر و دانلود فایل های ضمیمه ، لازم است در سایت ثبت نام کرده و با نام کاربری خود وارد شوید. در حال حاضر ثبت نام در سایت رایگان است.


چهارشنبه 11 ژوئن, 2008 10:40 am
مشخصات شخصی
مشاهده پست های قبلی:  نمایش بر اساس  
پاسخ به موضوع   [ 5 پست ] 

افراد آنلاین

کاربر حاضر در این تالار : - و 1 مهمان


شما نمی توانید در این تالار موضوع جدید باز کنید
شما نمی توانید در این تالار به موضوع ها پاسخ دهید
شما نمی توانید در این تالار پست های خود را ویرایش کنید
شما نمی توانید در این تالار پست های خود را حذف کنید
شما نمی توانید در این تالار ضمیمه ارسال کنید

جستجو برای:
پرش به:  
cron
استفاده و نقل از مباحث سایت، فقط با ذکر منبع و لینک سایت میکرورایانه مجاز است.
Copyright © 2006 - 2010 MicroRayaneh - Powered by phpBB © phpBB Group
Valid CSS2 Valid XHTML 1.0
طراحی سایت : میکرو رایانه