آموزش و تحلیل و بررسی و کد سورس لیست پیوندی در برنامه سازی پیشرفته

[Borna66]

مبحث لیست‌های پیوندی یکی از شاخه‌های ساختمان داده‌ها است که حرف اول را در آن آشنایی با اشاره‌گرها و مفهوم آن می‌زند. برای این که بتوانید در مباحث مختلف ساختمان داده‌ها از قبیل لیست‌های پیوندی، صف، پشته و به ویژه درخت موفق باشید، باید مفهوم اشاره‌گرها را خوب متوجه شده باشید.



در مطالب قبلی اشاره شد که آرایه‌های ایستا با توجه به ویژگی‌هایی که دارند، نمی‌توانند در همه مواقع نیاز ما را برآورده کنند. به همین خاطر آرایه‌های پویا را به خدمت می‌گیریم. اما آرایه‌های پویا هم معایبی دارند. بزرگترین مشکل آرایه‌ها - چه ایستا و چه پویا - این است که اندازه ثابتی دارند و امکان تغییر اندازه پس از تعریف آنها وجود ندارد. این ویژگی گاهی چندان مهم نیست. مثلا فرض کنید قصد داریم یک ماتریس با ابعاد نامشخص را در یک آرایه دو بعدی به گونه‌ای قرار دهیم که با مشکل کمبود فضا و یا فضای اضافی مواجه نشویم. آرایه ایستا در این مورد کمکی به ما نمی‌کند. اما آرایه پویا به خوبی این مشکل را برطرف می‌کند.



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



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

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




struct person
{
unsigned id;

string name;
string tel;
person *next;
};

اشاره‌گر next به متغیری از نوع خود ساختمان اشاره می‌کند. در واقع ما آدرس گره بعدی را در این اشاره‌گر قرار می‌دهیم. با این روش یک لیست کامل به دست می‌آید. اولین داده که وارد شد، اشاره‌گر next آن را تهی قرار می‌دهیم. وقتی داده دوم وارد شد، آدرس آن را در فیلد next داده اول قرار می‌دهیم، و فیلد next خود آن را تهی می‌کنیم، و الی آخر.
تذکر: تهی قرار دادن فیلد next آخرین گره برای تشخیص انتهای لیست ضروری است.
با این روش می‌توان یک لیست پیوندی با هر تعداد گره تشکیل داد. تنها محدودیت موجود حافظه کامپیوتر است. علاوه بر این، لیست پیوندی این خاصیت را دارد، که بر خلاف آرایه‌ها، داده‌های ذخیره شده در آن لزوما به صورت پیوسته در حافظه قرار نمی‌گیرند. آرایه‌ها به صورت پیوسته هستند. یعنی اگر طول آرایه 1000 باشد، همه 1000 خانه آن به صورت متوالی و پشت سر هم در حافظه کامپیوتر قرار می‌گیرند. این مساله محدودیت‌هایی را پیش می‌آورد. مثلا اگر در کامپیوتر 10000 خانه حافظه خالی داشته باشید که حداکثر 500 خانه آن به صورت پیوسته هستند، تنها می‌توانید آرایه‌ای به طول 500 تعریف کنید. لیست پیوندی این نقص را بر طرف کرده است. چرا که هر گره خود به صورت مستقل در حافظه ذخیره می‌شود. البته این خاصیت یک مزیت خوب را هم از بین می‌برد؛ و آن قابلیت اندیس‌گذاری داده‌ها است. به عناصر آرایه با استفاده از اندیس می‌توان دسترسی داشت؛ اما در لیست پیوندی مثلا برای دسترسی به عنصر پنجم باید از ابتدای لیست شروع کرده و چهار گره پیش برویم.
در ادامه این بحث فرض می‌گیریم گره‌های لیست از نوع myrec - شامل عنصری به نام next از نوع اشاره گر به خود - هستند.
در ابتدا، همیشه باید دو اشاره‌گر عمومی (مثلا به نامهای first و last) تعریف کنید که یکی به ابتدای لیست و دیگری به انتهای آن اشاره کنند. در لیست‌های پیوندی اگر آدرس عنصر اول را داشته باشید، می‌توانید به همه عناصر دسترسی پیدا کنید. عنصر آخر هم زمان اضافه کردن گره جدید به کار می‌آید. با داشتن آدرس این گره در زمان اضافه کردن گره جدید، لازم نیست لیست را از ابتدا تا انتها برای یافتن آخرین گره پیمایش کنید. پس وجود این اشاره‌گرها مهم بوده و حتما باید تعریف شوند. در تعریف این اشاره‌گرها باید به دو نکته توجه کرد:
1- باید عمومی تعریف شوند. اگر از کلاس استفاده می‌کنید، باید عضو مستقیم و خصوصی کلاس باشند.
2- باید در زمان تعریف با تهی (NULL برای ++C) مقداردهی شوند. مانند عبارت‌های زیر:


myrec *first = NULL;

myrec *last = NULL;

یادآوری: برای دسترسی به عناصر یک ساختمان توسط اشاره‌گر دو روش وجود دارد:



first->next

(*first).next
این دو دستور معادل هستند، اما اولی کمی بامسماتر است.

اضافه کردن گره به لیست پیوندی
وظیفه تابع 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 = temp;
last->next = NULL;
}
}

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

حذف یک گره از لیست پیوندی
رکوردهای اطلاعاتی عموما فیلد منحصر بفردی دارند که آنها را از هم متمایز می‌کند. مانند شماره دانشجویی، شماره شناسنامه، کد عضویت، کد کتاب. چنین فیلدی را کلید رکورد می‌نامند. از کلید برای تشخیص رکورد و ایندکس کردن استفاده می‌شود. فرض کنیم رکوردهای ما هم کلیدی به نام 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;
}

این تابع ابتدا گره با id مورد نظر را در لیست جستجو می‌کند. اگر چنین گرهی پیدا نشد، بدون انجام عمل دیگری از تابع خارج می‌شود. اشاره‌گر cur به گره حذف‌شدنی اشاره دارد و اشاره‌گر prior به گره قبل از cur. چهار حالت برای گره حذف‌شدنی وجود دارد:
1- هم گره اول باشد و هم گره آخر.
2- تنها گره اول باشد.
3- تنها گره آخر باشد.
4- نه گره اول باشد و نه گره آخر.
کد بالا برای هر چهار حالت عملیاتی را که لازم است انجام می‌دهد. برای درک بهتر عملکرد تابع فوق، آن را به صورت خط به خط به ازای گره‌هایی که در چهار وضعیت ذکر شده قرار دارند ردیابی کنید.
ما به اشاره‌گر prior نیاز داریم تا بتوانیم گره‌های قبل و بعد از cur را به هم متصل کنیم. حذف یک گره از لیست مانند آن است که حلقه‌ای را از وسط زنجیر جدا کنید. بعد از حذف حلقه، دو تکه زنجیر را باید به هم وصل کرد تا زنجیر کامل به دست بیاید.
آخرین خط تابع فضای cur را نیز که دیگر نیازی به آن نداریم آزاد می‌کند.

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


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;
}

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

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



void deleteall( )
{
myrec *temp, *cur = first;
while( cur != NULL )
{
temp = cur;
cur = cur->next;
delete temp;
}
first = NULL;
last = NULL;
}

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



void deleteall( )
{
myrec *cur = first;
while( cur != NULL )
{
del( cur->id );
cur = cur->next;
}
}

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