لیست پیوندی دو طرفه با ++C
در این مطلب از اوپن مایند، پیاده سازی لیست پیوندی دو طرفه با ++C را به شما آموزش می دهیم.
فهرست مطالب
پیشگفتار
مدت ها پیش پستی در مورد لیست پیوندی یک طرفه گذاشتم که در آن نحوه ی ایجاد لینک لیست یک طرفه را همراه با اضافه کردن گره ، حذف گره و همین طور جست و جوی یک گره را بررسی کردیم . در این پست ما به لیست پیوندی دوطرفه همان لیست دو پیوندی می پردازیم که ارتقاع یافته لیست پیوندی یک طرفه است.
اگر با لینک لیست یک طرفه ( لیست یک پیوندی) آشنا نیستید ابتدا این پست را مطالعه نمایید : آموزش لیست پیوندی linked list در برنامه نویسی .
نکته : این کد برای اینکه جنبه آموزشی دارد به ساده ترین شکل نوشته شده است – خودتان می توانید آن را با استفاده از template باز نویسی کنید و یک کلاس کلی برای خود بسازید.
لیست پیوندی دو طرفه یا Doubly Linked List
لینک لیست دوطرفه دارای دو لینک است . یک لینک به گره بعدی خود و لینک دیگر به گره ی قبلی اشاره دارد . مانند شکل زیر :
همین طور که در شکل بالا می بینید هر گره دارای دو اشارگر است . ساختار کلی یک گره را در شکل زیر می بینید:
خوب این سوال پیش اومده باشه که این چه مزیتی نسبت به لیست پیوندی یک طرفه دارد؟ در لینک لیست یک طرفه ما فقط می توانستیم در لیست رو به جلو حرکت کنیم چون فقط یک اشاره گر به گره ی بعدی داشتیم و نمی توانستیم به عقب برگردیم و اگر می خواستیم به عقب برگردیم باید از اول لیست را پیمایش می کردیم. به پست لینک لیست یک طرفه که لینکش را در بالا گذاشتم مراجعه کنید و به بخش حذف گره از لیست توجه کنید . در کل کار با لینک لیست دو طرفه آسان تر است و پیاده سازی آسان تری دارد.
پیاده سازی
لیست پیوندی که من پیاده سازی کرده ام از دو کلاس تشکیل شده است , یکی کلاس node و دیگری کلاس doubled Linked List .اولی کلاسی برای گره ها در لیست است و دومی کلاسی است برای خود لیست پیوندی .
کلاس node
این کلاس دارای سه ویژگی زیر است :
int Data : این ویژگی همان مقدار درون گره است. که می توان بر حسب نیاز تغییرش داد و گره هایی با مقادیر مورد نیاز خود بسازید.
node *next: اشاره گری به گره ی بعدی است و اگر گره ی بعدی وجود نداشت به NULL اشاره می کند.
node *pre : اشاره گری به گره ی قبلی است و اگر گره ی قبلی وجود نداشت به NULL اشاره می کند.
توابع کلاس node :
تابع زیر سازنده ی کلاس node است که مقدار Data را برابر با صفر می کند و اشارگرها را NULL میکند.
1 2 3 4 5 6 | node::node() { Data = 0; next = NULL; per = NULL; } |
تابع زیر سازنده ی دیگر کلاس node است که یک عدد به عنوان آرگومان می گیرد و آن را در Data می گذارد و بعد اشاره گر ها را NULL می کند.
1 2 3 4 5 6 | node::node(int D) { Data = D; next = NULL; per = NULL; } |
تابع زیر یک گره را را در ترمینال چاپ می کند.
1 2 3 4 | void node::print() { cout << Data << endl; } |
کلاس doubled Linked List
این کلاس دارای سه ویژگی زیر است.
int numberOfNode : تعداد گره ها در لیست پیوندی دو طرفه را نشان می دهد.
node * first : اشاره گری است که به گره ی اول لیست پیوندی اشاره می کند.
node * last : اشاره گری است که به گره ی آخر لیست پیوندی اشاره می کند.
توابع کلاس لیست دو پیوندی :
تابع زیر سازنده این کلاس است که اعداد گره ها موجود در لیست پیوندی را برابر صفر قرار می دهد و اشاره گر به اول و آخر لیست را برابر NULL می کند.
1 2 3 4 5 6 | doubledLinkedList::doubledLinkedList() { numberOfNode = 0; first = NULL; last = NULL; } |
تابع زیر تمام گره های یک لیست پیوندی را از اول تا آخر در ترمینال چاپ می کند.
1 2 3 4 5 6 7 8 9 10 11 12 | void doubledLinkedList:: display() { node * temp; temp = first; cout << "----------Display-----------"<< endl; while (temp != NULL) { cout << temp->Data << endl; temp = temp->next; } cout << "----------End-Display-------" << endl; } |
تابع زیر یه عدد می گیرد و یک گره جدید با اون عد ایجاد می کندو گره ی جدید را به ته لیست اضافه می کند.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | 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 بر می گرداند.
1 2 3 4 5 6 7 8 9 10 11 12 13 | 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 می کنیم و همین طور اشاره گره هایی که سایر گره ها به گره ی مورد نظر دارند را اصلاح می کنیم و بعد آن گره را از حافظه پاک می کنیم. و همین طور یکی از تعداد گره ها کم می کنیم . و در آخر اگر نودی که حذف کردیم اولین یا آخرین نود بود اشاره گر به اول یا آخر لیست را اصلاح می کنیم.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 | 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--; } } |
تابع زیر دو اشاره گر به گره ها را می گیرد و با اصلاح اشاره گر هایی که به دو گره وارد یا خارج می شود جای آن دو را در لیست پیوندی دو طرفه عوض می کند.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 | 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; } } } } |
مرتب سازی لیست پیوندی ( sort linked list ): تابع زیر با استفاده از تابع swap بالا لینک لیست را بر اساس Data سورت می کند.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | 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 یک لینک لیست ساخته ام و توابع مختلف را روی آن تست کرده ام .
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 | // 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; } |
نکته : البته خود سی پلاس پلاس یک کتابخانه برای لیست دو پیوندی دارد که با اضافه کردن آن به برنامه تان می توانید از آن استفاده کنید:
1 | #include <list> |
اگر کدی بهتر از این کد دارید یا این کد را با زبان دیگری نوشته اید آن را در اختیار ما قرار دهید تا به این پست اضافه اش کنیم.
مطلب خیلی آموزنده و مفید بود.
خیلی به دردم خورد ممنون.
ممنون کارتون عالی بود خسته نباشید.
سایت خوبیه ممنون
عااااااالی بود.خیلی خوب و واضج توضیح دادید.ممنون
عالی بود. واقعا به دردم خورد.خیلی خیلی ممنونم
خیلی ممنوووووون
ببخشید میشه کد ساختن درخت heapرو هم لطفا بذارید؟ ممنون
سلام ، حتما ولی تا حدود دو سه هفته دیگه
سلام
دکت گرم
eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeyyyyyyyyyyyyyyyyyyyyyyyyvvvvvvvvvvvvvvvvvvvaaaaaaaaaaaaaaaaaaaaaaaallllllllllllllllllllll