ParsX.com
پذیرش پروژه از دانشجویی ... تا سازمانی 09376225339
 
   ProfileProfile   Log in to check your private messagesLog in to check your private messages  |  FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups Log inLog in   RegisterRegister 

ساختار داده اي ليست پيوندي Linked List

 
Post new topic   Reply to topic    ParsX.com Forum Index -> اصول ساختمان داده ها
View previous topic :: View next topic  
Author Message
vahid
بي تو هرگز


Joined: 26 Nov 2004
Posts: 3067
Location: Tehran

PostPosted: Wed May 04, 2005 7:19 am    Post subject: ساختار داده اي ليست پيوندي Linked List Reply with quote

ساختار داده اي ليست پيوندي Linked List
اين ساختار ‍ ساختاري پويا Dynamic است . يعني به هنگام نياز به استفاده از حافظه اصلي با درخواستي كه مينماييم بخشي در اختيارمان قرار ميگيرد . و در صورت عدم نياز با رها سازي ان بخش به مجموعه حافظه قابل استفاده باز ميگردد .
يادآوري ( ايستايي )‌:‌( آرايه )‌در صورتي كه توانايي كم و زياد شدن حافظه در ساختار مربوطه را نداشته باشيم .
تفاوت ليست پيوندي با آرايه در ان است كه اعضا در ليست پيوندي پراكنده هستند .
هر عنصر ليست پيوندي در كنار خود حداقل يك بخش جهت حفظ آدرس عضو بعدي وجود دارد . در نتيجه يك خانه دو قسمتي است :
كه خانه سمت راست آدرس ليست پيوندي بعد از خود را نشان ميدهد . ( اشاره گريست به خانه بعد از خود . )
و خانه سمت چپ اطلاعات را نگهداري ميكند .
براي نمايش خانه سمت چپ و اينكه محتويات اين عنصر چيست از Info(Address) مثل Info(345H)
براي نمايش خانه سمت راست عنصر و اينكه اين عنصر به كدام خانه بعد از خود اشاره ميكند از Link(Address) مثل Link(354H) استفاده ميكنيم .
در اين ليست ها كه ليست هاي يكطرفه Single Link List گفته ميشود اطلاعات تنها يك آدرس حفظ ميشود . آدرس شروع در اين ساختمان داده اي بسيار مهم است كه ان را در متغيري كمكي به نام First نگهداري ميكنيم .
محدوده موجوديت Availability Area
محدوده ايست كه در آن عناصر ليست هاي پيوندي در اختيار قرار ميگيرند . در ساختار پيوندي درج و حذف اطلاعات فيزيكي است .
به منظور درك بهتر عمليات را خود انجام ميدهيم . باين منظور فرض ميكنيم مجموعه موجوديت عناصرش روي هم stack شده اند . بنابراين مجموعه stack گونه اي را ايجاد نموده اند و بناربراين به ان Availability Stack گويند . اشاره پيكان ها ميتواند به هر نقطه اي باشد . به نقطه بالايي اين محيط Avail گوييم .
الگوريتمي بنويسيد براي درج عضو جديد در ابتداي يك ليست پيوندي :
Function Insert(X,First)
1.[UnderFlow?]
   IF Avail=null
   Then write('availability stack,  UnderFlow ')
   return(first)
2.[obtain Address Of Free Node ]
   new := Avail
3.[remove node from availability stack]
  Avail:=Link(Avail)
4.[Set Fields of new]
  Info(New):=X
  Link(New):=First
5.[Exit]
return(new)

الگوريتم فوق را اينگونه فراخواني كرده ايم :‌ First = Insert(X,First) كه در آن X مقداريست كه ميخواهيم در ليست اضافه كنيم . و First اشاره گريست به خانه اول ليست .
در گام اول الگوريتم چك كرده ايم كه آيا حافظه ما خانه خالي دارد ؟ اگر ندارد عملياتي انجام ندهد و همان first را دست نخورده بازگرداند .
در گام دوم به new ميگوييم به همان خانه ايكه Avail اشاره ميكند اشاره كند .
در گام سوم مقدار Link(Avail) را به Avail ميريزيم تا يك خانه از حافظه ما براي عمليات آزاد شود . يعني Avail يك خانه در حافظه فرضي ما پايين امده است .
در مرحله چهارم X را به اطلاعات New و سپس Link(New) را گوييم كه به first اشاره كند . در نهايت مقدار new به جاي First برگرداننده ميشود .
الگوريتم درج يك عضو در انتهاي يك ليست پيوندي
Function InsEnd(X,First)
1.[UnderFlow?]
IF Avail=Null
   Then write('Availability Stack UnderFlow')
   return(First)
2.[obtain Address Of free node]
  New:=Avail
3.[Remove Node from availability stack]
Avail:=Link(Avail)
4.[set fields of new node]
  Info(new):=X
  Link(new):=null
5.[is the list empty ? ]
  If First=Null
   Then return(new)
6.[Initialize seach for last node]
  save:=first
7.[search for end of list]
repeat while link(save)<>null
   save:=link(save)
8.[set link field of last node to new]
link(save):=new
9.[finished]
  return(first)

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

الگوريتم درج در يك ليست پيوندي مرتب ( صعودي )
Function InsOrd(X,First)
1.[underflow?]
   IF avail=null
   then write('availability stack underflow')
   return(first)
2.[obtain address of free node]
  new:=avail
3[remove node from availability stack]
avail:=link(avail)
4.[copy information info(new)]
   info(new):=x
در اين مرحله از الگوريتم مقدار 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)


الگوريتم حذف از يك عنصر :
Procedure Delete(X,First)
1.[empty first?]
  IF first=null
   Then write('UnderFlow?')
   Exit
2.[initialize search for X ]
   empty:=first
3.[find x]
repeat thru step5 while link(temp) <> null and temp<>x
4.[update prodecessor marker]
   pred:=temp
5.[move to next node]
   temp:=link(temp)
6.[end of first ?]
if temp<>x
   then write('node not found')
   exit
7.[delete x]
if x=first
   then first:=link(first)
   else link(pred):=link(x)
8.[return node to availability stack]
link(x):=avail
avail:=x
exit

اين الگوريتم را ميتوان به شيوه هاي گوناگوني نوشت كه اينگونه شايد واضح ترين ان باشد .
Back to top
vahid
بي تو هرگز


Joined: 26 Nov 2004
Posts: 3067
Location: Tehran

PostPosted: Wed May 04, 2005 7:27 am    Post subject: Reply with quote

Back to top
Display posts from previous:   
Post new topic   Reply to topic    ParsX.com Forum Index -> اصول ساختمان داده ها All times are GMT + 3.5 Hours
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum