مدت ها پیش پستی در مورد لیست پیوندی یک طرفه گذاشتم که در آن نحوه ی ایجاد لینک لیست یک طرفه را همراه با اضافه کردن گره ، حذف گره و همین طور جست و جوی یک گره را بررسی کردیم . در این پست ما به لیست پیوندی دوطرفه همان لیست دو پیوندی می پردازیم که ارتقاع یافته لیست پیوندی یک طرفه است.
اگر با لینک لیست یک طرفه ( لیست یک پیوندی) آشنا نیستید ابتدا این پست را مطالعه نمایید : آموزش لیست پیوندی linked list در برنامه نویسی .
نکته : این کد برای اینکه جنبه ی آموزشی دارد به ساده ترین شکل نوشته شده است – خودتان می توانید آن را با استفاده از template باز نویسی کنید و یک کلاس کلی برای خود بسازید.
لینک لیست دوطرفه دارای دو لینک است . یک لینک به گره بعدی خود و لینک دیگر به گره ی قبلی اشاره دارد . مانند شکل زیر :
همین طور که در شکل بالا می بینید هر گره دارای دو اشارگر است . ساختار کلی یک گره را در شکل زیر می بینید:
خوب این سوال پیش اومده باشه که این چه مزیتی نسبت به لیست پیوندی یک طرفه دارد؟ در لینک لیست یک طرفه ما فقط می توانستیم در لیست رو به جلو حرکت کنیم چون فقط یک اشاره گر به گره ی بعدی داشتیم و نمی توانستیم به عقب برگردیم و اگر می خواستیم به عقب برگردیم باید از اول لیست را پیمایش می کردیم. به پست لینک لیست یک طرفه که لینکش را در بالا گذاشتم مراجعه کنید و به بخش حذف گره از لیست توجه کنید . در کل کار با لینک لیست دو طرفه آسان تر است و پیاده سازی آسان تری دارد.
لیست پیوندی که من پیاده سازی کرده ام از دو کلاس تشکیل شده است , یکی کلاس node و دیگری کلاس doubled Linked List .اولی کلاسی برای گره ها در لیست است و دومی کلاسی است برای خود لیست پیوندی .
کلاس node :
دارای سه ویژگی زیر است :
int Data : این ویژگی همان مقدار درون گره است. که می توان بر حسب نیاز تغییرش داد و گره هایی با مقادیر مورد نیاز خود بسازید.
node *next: اشاره گری به گره ی بعدی است و اگر گره ی بعدی وجود نداشت به NULL اشاره می کند.
node *pre : اشاره گری به گره ی قبلی است و اگر گره ی قبلی وجود نداشت به NULL اشاره می کند.
توابع کلاس node :
تابع زیر سازنده ی کلاس node است که مقدار Data را برابر با صفر می کند و اشارگرها را NULL میکند.
node::node()
{
Data = 0;
next = NULL;
per = NULL;
}
تابع زیر سازنده ی دیگر کلاس node است که یک عدد به عنوان آرگومان می گیرد و آن را در Data می گذارد و بعد اشاره گر ها را NULL می کند.
node::node(int D)
{
Data = D;
next = NULL;
per = NULL;
}
تابع زیر یک گره را را در ترمینال چاپ می کند.
void node::print()
{
cout << Data << endl;
}
کلاس doubled Linked List :
این کلاس دارای سه ویژگی زیر است.
int numberOfNode : تعداد گره ها در لیست پیوندی دو طرفه را نشان می دهد.
node * first : اشاره گری است که به گره ی اول لیست پیوندی اشاره می کند.
node * last : اشاره گری است که به گره ی آخر لیست پیوندی اشاره می کند.
توابع کلاس لیست دو پیوندی :
تابع زیر سازنده این کلاس است که اعداد گره ها موجود در لیست پیوندی را برابر صفر قرار می دهد و اشاره گر به اول و آخر لیست را برابر NULL می کند.
doubledLinkedList::doubledLinkedList()
{
numberOfNode = 0;
first = NULL;
last = NULL;
}
تابع زیر تمام گره های یک لیست پیوندی را از اول تا آخر در ترمینال چاپ می کند.
void doubledLinkedList:: display()
{
node * temp;
temp = first;
cout << "----------Display-----------"<< endl;
while (temp != NULL)
{
cout << temp->Data << endl;
temp = temp->next;
}
cout << "----------End-Display-------" << endl;
}
تابع زیر یه عدد می گیرد و یک گره جدید با اون عد ایجاد می کندو گره ی جدید را به ته لیست اضافه می کند.
void doubledLinkedList:: add(node N)
{
node *newNode = new node();
newNode->Data = N.Data;
if (numberOfNode == 0)
{
first = last = newNode;
numberOfNode++;
}
else
{
last->next = newNode;
newNode->per = last;
last = last->next;
numberOfNode++;
}
}
تابع زیر یک مقدار می گیرد و از اول لیست شروع به گشتن می کند تا آخر لیست در صورتی که گره ای با آن Data وجود داشته باشد یک اشاره گر به آن برمی گرداند در غیر این صورت NULL بر می گرداند.
node* doubledLinkedList::search( int d)
{
node *temp = first;
while (temp != NULL)
{
if (temp->Data == d)
{
return temp;
}
temp = temp->next;
}
return NULL;
}
تابع زیر یک عدد را می گیرد و با استفاده از تابع سرچ بالا آن را در لیست پیوندی پیدا می کند . و بعد از پیدا کردن آن را حذف می کند . حذف کردن به این صورت است که اشاره گر های next , pre گره را NULL می کنیم و همین طور اشاره گره هایی که سایر گره ها به گره ی مورد نظر دارند را اصلاح می کنیم و بعد آن گره را از حافظه پاک می کنیم. و همین طور یکی از تعداد گره ها کم می کنیم . و در آخر اگر نودی که حذف کردیم اولین یا آخرین نود بود اشاره گر به اول یا آخر لیست را اصلاح می کنیم.
void doubledLinkedList::delet(int data)
{
node *temp = search(data);
if (temp != NULL)
{
node *temppre = temp->per;
node *tempnext = temp->next;
if (temppre != NULL)
{
temppre->next = tempnext;
}
else
{
first = tempnext;
}
if (tempnext != NULL)
{
tempnext->per = temppre;
}
else
{
last = temppre;
}
delete temp;
numberOfNode--;
}
}
تابع زیر دو اشاره گر به گره ها را می گیرد و با اصلاح اشاره گر هایی که به دو گره وارد یا خارج می شود جای آن دو را در لیست پیوندی دو طرفه عوض می کند.
void doubledLinkedList:: swap(node* a, node* b)
{
if (a == first)
{
first = b;
}
else
{
if (b == first)
{
first = a;
}
}
if (a == last)
{
last = b;
}
else
{
if (b == last)
{
last = a;
}
}
node*temppre1 = a->per;
node*tempnext1 = a->next;
node*temppre2 = b->per;
node*tempnext2 = b->next;
if (a->next != b && a->per != b)
{
a->next = tempnext2;
a->per = temppre2;
if (temppre2 != NULL)
{
temppre2->next = a;
}
if (tempnext2 != NULL)
{
tempnext2->per = a;
}
b->next = tempnext1;
b->per = temppre1;
if (temppre1 != NULL)
{
temppre1->next = b;
}
if (tempnext1 != NULL)
{
tempnext1->per = b;
}
}
else
{
if (a->next == b)
{
b->next = a;
b->per = temppre1;
a->next = tempnext2;
a->per = b;
if (temppre1 != NULL)
{
temppre1->next = b;
}
if (tempnext2 != NULL)
{
tempnext2->per = a;
}
}
else
{
b->per = a;
b->next = tempnext1;
a->per = temppre2;
a->next = b;
if (tempnext1 != NULL)
{
tempnext1->per = b;
}
if (temppre2 != NULL)
{
temppre2->next = a;
}
}
}
}
تابع زیر با استفاده از تابع swap بالا لینک لیست را بر اساس Data سورت می کند.
void doubledLinkedList:: sort(void)
{
node* temp1 = first;
node* temp2;
node* temp3;
while (temp1->next != NULL)
{
temp2 = temp1->next;
while (temp2 != NULL)
{
if (temp2->Data < temp1->Data)
{
swap(temp1, temp2);
temp3 = temp1;
temp1 = temp2;
temp2 = temp3;
}
temp2 = temp2->next;
}
temp1 = temp1->next;
}
}
و در آخر هم کد کلی لیست پیوندی دوطرفه – doubled linked list را همراه تابع main آورده ام که برای نمونه در تابع main یک لینک لیست ساخته ام و توابع مختلف را روی آن تست کرده ام .
// Doubled linked list with template.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <iostream>
using namespace std;
//-----------------------------------node-class-------------------------------------------------
class node
{
public:
friend class doubledLinkedList;
node();
node(int);
void print();
private:
int Data;
node * next;
node * per;
};
node::node()
{
Data = 0;
next = NULL;
per = NULL;
}
node::node(int D)
{
Data = D;
next = NULL;
per = NULL;
}
void node::print()
{
cout << Data << endl;
}
//--------------------------------------double-linked-list---------------------------------------
class doubledLinkedList
{
public:
doubledLinkedList();
void display(void);//show all node
void add(node);//add node in list
node* search(int);//search in linked list and return pointer to it
void delet(int);//delete node from list
void swap(node*, node*);//swap two node in list
void sort(void);//sort Linked list
private:
int numberOfNode;
node * first;//start point of linked list
node * last;//end point of linked list
};
doubledLinkedList::doubledLinkedList()
{
numberOfNode = 0;
first = NULL;
last = NULL;
}
void doubledLinkedList:: display()
{
node * temp;
temp = first;
cout << "----------Display-----------"<< endl;
while (temp != NULL)
{
cout << temp->Data << endl;
temp = temp->next;
}
cout << "----------End-Display-------" << endl;
}
void doubledLinkedList:: add(node N)
{
node *newNode = new node();
newNode->Data = N.Data;
if (numberOfNode == 0)
{
first = last = newNode;
numberOfNode++;
}
else
{
last->next = newNode;
newNode->per = last;
last = last->next;
numberOfNode++;
}
}
node* doubledLinkedList::search( int d)
{
node *temp = first;
while (temp != NULL)
{
if (temp->Data == d)
{
return temp;
}
temp = temp->next;
}
return NULL;
}
void doubledLinkedList::delet(int data)
{
node *temp = search(data);
if (temp != NULL)
{
node *temppre = temp->per;
node *tempnext = temp->next;
if (temppre != NULL)
{
temppre->next = tempnext;
}
else
{
first = tempnext;
}
if (tempnext != NULL)
{
tempnext->per = temppre;
}
else
{
last = temppre;
}
delete temp;
numberOfNode--;
}
}
void doubledLinkedList:: swap(node* a, node* b)
{
if (a == first)
{
first = b;
}
else
{
if (b == first)
{
first = a;
}
}
if (a == last)
{
last = b;
}
else
{
if (b == last)
{
last = a;
}
}
node*temppre1 = a->per;
node*tempnext1 = a->next;
node*temppre2 = b->per;
node*tempnext2 = b->next;
if (a->next != b && a->per != b)
{
a->next = tempnext2;
a->per = temppre2;
if (temppre2 != NULL)
{
temppre2->next = a;
}
if (tempnext2 != NULL)
{
tempnext2->per = a;
}
b->next = tempnext1;
b->per = temppre1;
if (temppre1 != NULL)
{
temppre1->next = b;
}
if (tempnext1 != NULL)
{
tempnext1->per = b;
}
}
else
{
if (a->next == b)
{
b->next = a;
b->per = temppre1;
a->next = tempnext2;
a->per = b;
if (temppre1 != NULL)
{
temppre1->next = b;
}
if (tempnext2 != NULL)
{
tempnext2->per = a;
}
}
else
{
b->per = a;
b->next = tempnext1;
a->per = temppre2;
a->next = b;
if (tempnext1 != NULL)
{
tempnext1->per = b;
}
if (temppre2 != NULL)
{
temppre2->next = a;
}
}
}
}
void doubledLinkedList:: sort(void)
{
node* temp1 = first;
node* temp2;
node* temp3;
while (temp1->next != NULL)
{
temp2 = temp1->next;
while (temp2 != NULL)
{
if (temp2->Data < temp1->Data)
{
swap(temp1, temp2);
temp3 = temp1;
temp1 = temp2;
temp2 = temp3;
}
temp2 = temp2->next;
}
temp1 = temp1->next;
}
}
//------------------------------------------------------------------------------------------------
int main( )
{
doubledLinkedList myList;
node mynode6(60);
myList.add(mynode6);
node mynode2(20);
myList.add(mynode2);
node mynode3(30);
myList.add(mynode3);
node mynode5(50);
myList.add(mynode5);
node mynode4(40);
myList.add(mynode4);
node mynode(10);
myList.add(mynode);
myList.delet(20);
myList.sort();
myList.display();
return 0;
}
اگر کدی بهتر از این کد دارید یا این کد را با زبان دیگر نوشته اید آن را در اختیار ما قرار دهید تا به این پست اضافه اش کنیم.
