Parsiland Forums
بازگشت   پارسی لند > برنامه نویسی > VB.net, VB, Delphi, C++, C# ,C, Pascal > ساير زبان های برنامه نویسی

سایت پارسی لند | Parsiland Forums



  

لیست پیوندی 9 ارديبهشت 1388   #1 (لینک)
Code::Blocks
کاربر سابق انجمن
 
Code::Blocks is banned
نوشته ها: 3,730
سپاس از دیگران: 5,273 بار
سپاس شده: 6,486 بار
دوستان من: 53 نفر
عضو پارسی لند: دي 1387
حالت من: rahat
نمایش پروفایل Code::Blocks    نمایش آلبوم های Code::Blocks   اضافه کردن Code::Blocks به لیست دوستان شما   گروه های دسته جمعی
لیست پیوندی لیست پیوندی

اینبار می خوام در مورد لیستهای پیوندی و کاربردهاش بنویسم. مبحث لیستهای پیوندی یکی از شاخه های مبحث عمومی تر ساختمان داده هاست که حرف اول رو در اون آشنایی با اشاره گرها و مفهموشون می زنه. برای اینکه بتونید در مباحث مختلف ساختمان داده ها از قبیل لیستهای پیوندی ، صف ، پشته و به ویژه درخت موفق باشید ، باید مفهوم اشاره گرها رو و البته عملیاتی رو که می شه روشون انجام داد ، خوب متوجه شده باشید. فرقی نمی کنه از چه زبان برنامه نویسی استفاده بکنید.
همونطور که قبلا بحث شده ، گاهی اوقات آرایه های ایستا با توجه به ویژگیهایی که دارن ، نمی تونن نیاز ما رو برآورده کنن. به همین خاطر آرایه های پویا رو بخدمت می گیریم. اما آرایه های پویا هم معایبی دارن. بزرگترین مشکل آرایه ها ، چه ایستا و چه پویا ، اینه که اندازه ثابتی دارن و بعد از تعریف شدن امکان تغییر اندازه وجود نداره. این ویژگی گاهی چندان مهم نیست. مثلا فرض کنید می خوایم ماتریسی رو تو یه آرایه قرار بدیم ، بطوریکه نه حافظه کم بیاریم و نه حافظه اضافی مصرف کنیم. آرایه ایستا هیچ کمکی به ما نمی کنه ، ولی فقط با دونستن تعداد سطرها و ستونهای ماتریس ، به راحتی با کمک آرایه پویا این مشکل حل می شه.
اما حالا برنامه ای رو در نظر بگیرید که قراره اسم و شماره تلفن دوستانتون رو نگه داره. شما چند تا دوست دارید؟ آیا همیشه می شه تعداد رو - و یا حتی سقف تعداد رو - مشخص کرد؟ مطمئنا نه. شما هر لحظه ممکنه اسمی رو به این لیست اضافه و یا ازش حذف کنید. اینجاست که دیگه آرایه پویا هم جوابگو نیست و باید رفت سراغ یه مفهموم دیگه: لیست پیوندی.
مفهوم لیست پیوندی با ساختمان تو ++C و رکورد تو پاسکال ارتباط داره. ساختمان یا رکورد مثال قبل به این صورته:

struct person
{
unsigned id ;
string name ;
string tel ;
} ;

person = record
id : word ;
name : string ;
tel : string ;
end ;

ما از تعاریف بالا برای مشخص کردن گرههای لیست پیوندی استفاده می کنیم. در واقع لیست پیوندی مجموعه ای از این گره هاست که به هم متصل شدن. اما چطور؟ جواب این سوال رو قبلا دادم: با استفاده از اشاره گرها. تعریفهای بالا رو کمی تغییر می دیم و یه اشاره گر به خود تعریف می کنیم:

struct person
{
unsigned id ;
string name ;
string tel ;
person *next ;
} ;

person_ptr = ^person
person = record
id : word ;
name : string ;
tel : string ;
next : person_ptr ;
end ;

اشاره گر next به متغیری از نوع خود رکورد اشاره می کنه. در واقع ما آدرس عنصر بعدی رو تو این اشاره گر قرار می دیم. با این روش ، لیست کامل به دست می یاد. اولین داده که وارد شد اشاره گر next رو تهی قرار می دیم. وقتی داده دوم وارد شد آدرسش رو تو عنصر next داده اول قرار می دیم ، و مال خودش رو تهی می کنیم. وقتی داده سوم رو خوندیم ، آدرسش رو تو عنصر next داده دوم قرار می دیم ، و عنصر متناظر خودش رو تهی می کنیم و ... تهی قرار دادن عنصر next آخرین عنصر ضروریه. چون فقط به این وسیله می شه آخر لیست رو تشخیص داد. با این روش می شه یه لیست پیوندی با هر تعداد گره تشکیل داد. تنها محدودیت موجود حافظه کامپیوتره. علاوه بر این ، لیست پیوندی یه ویژگی خیلی بزرگ داره و اون گسسته بودن گرههاست. به عبارت دیگه لازم نیست داده ها تو حافظه کامپیوتر درست پشت سر هم قرار بگیرن. آرایه ها ، چه ایستا و چه پویا ، به صورت پیوسته هستن. یعنی مثلا اگه طول آرایه 1000 باشه ، همه 1000 خونه اون به صورت متوالی و پشت سر هم قرار می گیرن. این مساله باعث می شه که علیرغم داشتن فضای خالی نشه آرایه رو تو کل حافظه گسترش داد. مثلا اگه شما تو کامپیوتر ۱۰۰۰۰ خونه حافظه خالی داشته باشین که حداکثر 500 تا خونش یه هم پیوسته هستن ، فقط می تونید آرایه ای به طول 500 تعریف کنید. لیست پیوندی این نقص رو برطرف کرده ، اما یه مزیت خوب رو هم از دست داده ، و اون قابلیت اندیس گذاریه. به عناصر آرایه با استفاده از اندیس می شه دسترسی داشت ، اما در لیست پیوندی مثلا برای دسترسی به عنصر پنجم باید از اول لیست شروع کنیم و 4 تا گره بریم جلو!
امیدوارم که خوب تونسته باشم مفهوم لیست پیوندی رو توضیح بدم. در اولین فرصت مطالب کامل کننده رو می نویسم. اینکه چطور لیست پیوندی ساخته می شه ، چطور عنصری بهش اضافه یا ازش کم می شه و ...



این مطلب با زحمات کاربرای این سایت جمع آوری شده است
اخلاق حکم می کند در صورت برداشت از سایت منبع را ذکر کنید!
 
کسی که از Code::Blocks سپاس کرد.

آخرین ارسال Code::Blocks
موضوع انجمن آخرین نویسنده پاسخ نمایش تاریخ آخرین نوشته
دانلود بازی بیلیارد Pool Hall Pro دانلود بازی pc Code::Blocks 0 1204 10 مهر 1389 14:51
دانلود بازی Prince of Persia: The Forgotten Sands با لینک مستقیم دانلود بازی pc Code::Blocks 0 957 10 مهر 1389 14:43
دانلود بازی StarCraft II: Wings of Liberty با لینک مستقیم دانلود بازی pc Golabi 2 1401 10 مهر 1389 14:35
دانلود بازی Kane & Lynch 2: Dog Days با لینک مستقیم دانلود بازی pc Code::Blocks 0 1223 10 مهر 1389 14:28
دانلود بازی مافیا 2 Mafia II با لینک مستقیم دانلود بازی pc Code::Blocks 2 979 10 مهر 1389 14:22
دانلود بازی Darksiders با لینک مستقیم دانلود بازی pc Code::Blocks 0 651 10 مهر 1389 14:12
" ترین" های سال 88 اخبار Code::Blocks 0 1121 18 اسفند 1388 19:50
حل مشکلات 5800 نرم افزارهای سامسونگ, ال جی Code::Blocks 0 1390 17 اسفند 1388 12:32
والپیپر برای 5800 با کیفیت بالا والپيپر و اسكرين سيور Code::Blocks 17 2631 17 اسفند 1388 12:01

لیست پیوندی 9 ارديبهشت 1388   #2 (لینک)
Code::Blocks
کاربر سابق انجمن
 
Code::Blocks is banned
نوشته ها: 3,730
سپاس از دیگران: 5,273 بار
سپاس شده: 6,486 بار
دوستان من: 53 نفر
عضو پارسی لند: دي 1387
حالت من: rahat
نمایش پروفایل Code::Blocks    نمایش آلبوم های Code::Blocks   اضافه کردن Code::Blocks به لیست دوستان شما   گروه های دسته جمعی
لیست پیوندی - قسمت دوم لیست پیوندی - قسمت دوم

بحث لیستهای پیوندی رو ادامه می دیم...
اینبار می خوام بگم که چطور می شه یه گره به انتهای یه لیست پیوندی اضافه کرد. توی کل این مباحث فرض می گیریم گرههای لیست از نوع myrec - شامل عنصری به نام next از نوع اشاره گر به خود - هستن. myrec_ptr هم اشاره گر به این نوع داده در نظر گرفته شده.
اول اینکه همیشه باید دو تا اشاره گر عمومی (مثلا به نامهای first و last) تعریف کنید که یکی به اول لیست و اون یکی به آخر لیست اشاره کنه. توی لیستهای پیوندی اگه آدرس عنصر اول رو داشته باشید ، می تونید به همه عناصر دسترسی پیدا کنید. عنصر آخر هم زمان اضافه کردن گره های جدید به کار می یاد. پس این اشاره گرها خیلی مهمن و حتما باید تعریف بشن. ولی دو تا نکته وجود داره: اولا باید عمومی تعریف بشن. اگه از کلاس استفاده می کنید باید عضو مستقیم و خصوصیه کلاس باشن. ثانیا باید ابتدای کار مقدار تهی بگیرن (NULL برای ++C و nil برای پاسکال). شما می تونید این کار رو اول برنامه انجام بدید ، و یا اگه از کلاسها و اشیاء استفاده می کنید ، باید توی تابع سازنده این کار رو انجام بدید. مثل عبارتهای زیر:

myrec *first = NULL ;
myrec *last = NULL ;

var
first,last : myrec_ptr ;
...
begin
first := nil ;
last := nil ;
...
end .

حالا تابع add رو می نویسیم. وظیفه این تابع اضافه کردن یه گره به آخر لیست پیوندیه. با این حساب تابع باید یه ورودی داشته باشه - اطلاعات گره جدید - و نیازی به خروجی نداره. البته می شه خروجی رو از نوع بولی تعریف کرد که نشون بده عملیات با موفقیت انجام شده یا نه. ولی ما اینجا ازش صرف نظر می کنیم.

void add ( myrec info )
{
myrec *temp ;
temp = new myrec ;
*temp = info ;
if ( first == NULL )
{
first = temp ;
first->next = NULL ;
last = first ;
}
else
{
last->next = temp ;
last = last->next ;
last->next = NULL ;
if ( first->next == NULL )
first->next = last ;
}
}

procedure add ( info : myrec ) ;
var
temp : myrec_ptr ;
begin
new ( temp ) ;
temp^ := info ;
if first = nil then
begin
first := temp ;
first^.next := nil ;
last := first ;
end
else
begin
last^.next := temp ;
last := last^.next ;
last^.next := nil ;
if first^.next = nil then
first^.next := last ;
end ;
end ;

این تابع در ابتدای کار با دستور new یه فضا برای گره جدید ایجاد می کنه و آدرسش رو تو متغیر temp قرار می ده. بعد از اون محتوی info رو در temp کپی می کنه. دستورات مهم از اینجا شروع می شن: اول چک می کنه که آیا first تهی هست یا نه. اگه تهی باشه یعنی لیست ما خالیه و گره جدید اولین گره لیسته. پس temp رو در first و last کپی می کنه (این گره هم اوله و هم آخر). اگر first تهی نبود تنها محل last رو تغییر می ده. الیته یه چکی هم می کنه که آیا عنصر بعدی first موجود هست یا نه؟ اگه نبود به مفهوم اینه که گره جدید ، گره دوم لیسته. در نتیجه عنصر next گره first رو به اون اشاره می ده.

قابل توجه برنامه نویسان ++C:
برای دسترسی به عناصر یه ساختمان توسط اشاره گر دو روش وجود داره:
first->next
(*first).next
این دو دستور معادل هستن ، اما اولی بامسماتره!!!
 
2 کاربر ازش سپاس کردند .
لیست پیوندی 9 ارديبهشت 1388   #3 (لینک)
Code::Blocks
کاربر سابق انجمن
 
Code::Blocks is banned
نوشته ها: 3,730
سپاس از دیگران: 5,273 بار
سپاس شده: 6,486 بار
دوستان من: 53 نفر
عضو پارسی لند: دي 1387
حالت من: rahat
نمایش پروفایل Code::Blocks    نمایش آلبوم های Code::Blocks   اضافه کردن Code::Blocks به لیست دوستان شما   گروه های دسته جمعی
لیست پیوندی - قسمت سوم لیست پیوندی - قسمت سوم

سمت سوم آموزش ساخت لیستهای پیوندی رو به تعریف تابعی اختصاص دادم که کلیه گرههای لیست رو حذف و فضای اختصاص یافته رو آزاد می کنه. این تابع زمانی فراخوانی می شه که کارمون با لیست تموم شده و یا به هر دلیلی می خوایم لیست رو خالی کنیم. اگه از لیستهای پیوندی کلاسی تشکیل بدید ، این تابع نقش تابع مخرب رو بازی می کنه.
void deleteall ( )
{
myrec *temp , *cur = first ;
while ( cur != NULL )
{
temp = cur ;
cur = cur->next ;
delete temp ;
}
first = NULL ;
last = NULL ;
}

procedure deleteall ;
var
temp , cur : myrec_ptr ;
begin
cur := first ;
while cur <> nil do
begin
temp := cur ;
cur := cur^.next ;
dispose ( temp ) ;
end ;
first := nil ;
last := nil ;
end ;

تابع deleteall با دو تا اشاره گر کار می کنه. اشاره گر temp به گرهی که باید حذف بشه و اشاره گر cur به گره جاری اشاره دارن. گره جاری گرهیه که بعد از گره حذف شدنی قرار داره. در هر بار اجرای حلقه یه گره حذف می شه. بعد از تموم شدن حلقه اشاره گرهای first و last تهی می شن، تا مشخص بشه که لیست خالیه.

 
2 کاربر ازش سپاس کردند .
لیست پیوندی 9 ارديبهشت 1388   #4 (لینک)
Code::Blocks
کاربر سابق انجمن
 
Code::Blocks is banned
نوشته ها: 3,730
سپاس از دیگران: 5,273 بار
سپاس شده: 6,486 بار
دوستان من: 53 نفر
عضو پارسی لند: دي 1387
حالت من: rahat
نمایش پروفایل Code::Blocks    نمایش آلبوم های Code::Blocks   اضافه کردن Code::Blocks به لیست دوستان شما   گروه های دسته جمعی
لیست پیوندی - قسمت چهارم لیست پیوندی - قسمت چهارم

این قسمت اختصاص به تابع حذف گره داره. رکوردهای اطلاعاتی عموما فیلد منحصر بفردی دارن که اونها رو از هم متمایز می کنه. مثل شماره دانشجویی ، شماره شناسنامه ، کد عضویت ، کد کتاب و ... از این فیلد برای تشخیص رکورد و ایندکس کردن استفاده می شه. فرض کنیم رکوردهای ما هم فیلدی به نام id با این ویژگی داشته باشن. از این فیلد برای پیدا کردن گرهی که باید حذف بشه استفاده می کنیم. تابع del که برای حذف گره استفاده می شه یه id رو دریافت می کنه و گره مربوطه رو حذف می کنه. اگه هیچ رکوردی با این id موجود نباشه تابع بدون انجام دادن کاری تموم می شه.

void del ( unsigned long id )
{
myrec *prior , *cur ;
cur = first ;
prior = NULL ;
while ( cur != NULL && cur->id != id )
{
prior = cur ;
cur = cur->next ;
}
if ( cur == NULL )
return ;
if ( cur == first )
{
first = first -> next ;
if ( cur == last )
last = NULL ;
}
else if ( cur == last )
last = prior ;
else
prior->next = cur->next ;
delete cur ;
}

procedure del ( id : longword ) ;
var
prior , cur : myrec_ptr ;
begin
cur := first ;
prior := nil ;
while ( cur <> nil ) and ( cur^.id <> id ) do
begin
prior := cur ;
cur := cur^.next ;
end;
if cur = nil then
exit ;
if cur = first then
begin
first := first^.next ;
if cur = last then
last:=nil;
end
else if cur = last then
last := prior
else
prior^.next := cur^.next ;
dispose ( cur ) ;
end ;

این تابع ابتدا گره با id مورد نظر رو توی لیست جستجو می کنه. اگر چنین گرهی پیدا نشد از تابع خارج می شه. اشاره گر cur به گره حذف شدنی اشاره داره و اشاره گر prior هم به گره قبل از cur. چهار حالت برای گره حذف شدنی وجود داره:
1- هم اول باشه و هم آخر
2- اول باشه ، ولی آخر نباشه
3- آخر باشه ، ولی اول نباشه
4- نه اول باشه و نه آخر
کد بالا برای هر چهار حالت عملیاتی که لازمه رو انجام می ده. در پایان هم فضای cur آزاد می شه. یعنی گره مورد نظر حذف می شه. ما به اشاره گر prior نیاز داریم تا بتونیم گرههای قبل از cur و بعد از cur رو به هم متصل کنیم. حذف یه گره مثل این می مونه که حلقه ای رو از وسط زنجیر جدا کنید. بعد از حذف حلقه ، دو تکه حلقه رو باید به هم متصل کرد تا زنجیر کامل به دست بیاد.
 
2 کاربر ازش سپاس کردند .
لیست پیوندی 9 ارديبهشت 1388   #5 (لینک)
Code::Blocks
کاربر سابق انجمن
 
Code::Blocks is banned
نوشته ها: 3,730
سپاس از دیگران: 5,273 بار
سپاس شده: 6,486 بار
دوستان من: 53 نفر
عضو پارسی لند: دي 1387
حالت من: rahat
نمایش پروفایل Code::Blocks    نمایش آلبوم های Code::Blocks   اضافه کردن Code::Blocks به لیست دوستان شما   گروه های دسته جمعی
لیست پیوندی - قسمت آخر لیست پیوندی - قسمت آخر

قسمت آخر معرفی لیستهای پیوندی رو به نوشتن تابع درج اختصاص دادم. تایع درج گرهی رو به هر نقطه دلخواه لیست اضافه می کنه. این تابع دو تا ورودی داره. ورودی اول اطلاعات گره جدید و ورودی دوم محل درج گره. محل درج گره رو با روشهای مختلفی می شه مشخص کرد. ما اینجا از id استفاده می کنیم. به این معنی که گره جدید قبل از گره با id مشخص شده قرار می گیره.

void insert ( myrec info , unsigned long id )
{
myrec *prior , *cur , *temp ;
cur = first ;
prior = NULL ;
while ( cur != NULL && cur->id != id )
{
prior = cur ;
cur = cur->next ;
}
if ( cur == NULL )
return ;
temp = new myrec ;
*temp = info ;
prior->next = temp ;
temp->next = cur ;
}

procedure insert ( info : myrec ; id : longword ) ;
var
prior , cur , temp : myrec_ptr ;
begin
cur := first ;
prior := nil ;
while ( cur <> ni l) and ( cur^.id <> id ) do
begin
prior := cur ;
cur := cur^.next ;
end ;
if cur = nil then
exit ;
new ( temp ) ;
temp^ := info ;
prior^.next := temp ;
temp^.next := cur ;
end ;

من اینجا از سه تا اشاره گر استفاده کردم. اشاره گر cur برای اشاره به گره جاری ، اشاره گر prior برای اشاره به گره قبل از cur و بالاخره اشاره گر temp برای اشاره به گره جدید. این تابع گره با id تعیین شده رو پیدا می کنه و گره جدید رو قبل از اون درج می کنه. در واقع گرهی که temp بهش اشاره داره بین گرههای cur و prior قرار می گیره.
امیدوارم تونسته باشم شما رو با لیستهای پیوندی آشنا کنم. توابع زیادی وجود داره که اینجا بررسی نشد. شما اگه مطالب ارائه شده رو خوب متوجه شده باشید نوشتن بقیه توابع واستون کاری نداره

منبع:سایت aachp.ir
نوشته شده توسط آقای مسعود اقدسی فام
 
2 کاربر ازش سپاس کردند .
برچسب ها
لیست, لیست پیوندی, پیوندی, آرایه, اشاره گر, ساختمان داده

  


کاربران در حال دیدن موضوع: 1 نفر (0 عضو و 1 مهمان)
 

(نمایش همه كاربراني كه از اين موضوع بازدید نمودند: 4 نفر
Administer, Code::Blocks, hamidsa, tab
ابزارهای موضوع جستجو در موضوع
جستجو در موضوع:

جستجوی پیشرفته
نحوه نمایش امتیاز به این موضوع
امتیاز به این موضوع:

انتخاب سریع یک انجمن


دانلود فایل,مقاله, سورس کد

Powered by vBulletin, Copyright ©2000 - 2014, Jelsoft Enterprises Ltd.
All right reserved ©2009 - 2014, Parsiland.com
کپی برداری از این سایت به هر نحو ممنوع می باشد!

Yahoo bot last visit powered by MyPagerank.Net

Parsiland Search Engine Garde