‏انواع لیست پیوندی

مهدی نظری — Mon, 20 Jun 2022 20:49:48 +0430

‏ لیست ‏‏پیوندی‏‏ یک ساختار داده خطی است، که در آن عناصر در مکان های حافظه به هم مرتبط ذخیره نمی شوند بلکه عناصر در یک لیست پیوندی با استفاده از اشاره گرها به هم ‏‏مرتبط می شوند‏‏. به عبارت ساده، یک لیست پیوندی شامل گره هایی است که هر گره شامل یک فیلد داده و یک مرجع(پیوند) به گره بعدی در لیست است. ‏‏انواع لیست پیوندی‏ ‏لیست پیوندی یک طرفه:‏‏ ساده ترین نوع لیست پیوندی است که در آن هر گره حاوی برخی داده ها و یک اشاره گر به گره بعدی از همان نوع داده است. گره شامل اشاره گر به گره بعدی به این معنی است که گره آدرس گره بعدی را در دنباله ذخیره می کند. یک لیست پیوندی تنها به تراورزال داده ها به یک طریق اجازه می دهد. همانطور که در تصویر زیر مشاهده می کنید:ساختار لیست پیوندی یک طرفه در زبان c:class Node {public:int data Node* next;};ایجاد و تراورزال لیست پیوندی یک طرفه:#include using namespace std;class Node {public: int data; Node* next;};void printList(Node* n){ while (n != NULL) { cout << n->data << " " n = n->next; }} Node* head = NULL; Node* second = NULL; Node* third = NULL; head = new Node(); second = new Node(); third = new Node(); head->data = 1; head->next = second; second->data = 2; second->next = third; third->data = 3; third->next = NULL; printList(head); return 0;}‏لیست ‏‏پیوندی دو طرفه:‏‏ لیست پیوندی دو طرفه، نوع پیچیده تری از لیست پیوندی است که شامل اشاره گر به گره بعدی و همچنین گره قبلی در دنباله است، بنابراین شامل سه بخش داده، اشاره گر به گره بعدی، و اشاره گر به گره قبلی است. این ما را قادر به عبور از لیست در جهت عقب نیز می سازد. همانطور که در تصویر زیر مشاهده می کنید:‏ساختار لیست پیوندی دوطرفه در زبان c:struct Node { int data; struct Node* next; struct Node* prev;};ایجاد و تراورزال لیست پیوندی دو طرفه در زبان c: #include using namespace std;class Node {public: int data; Node* next; Node* prev;};void push(Node** head_ref, int new_data){ Node* new_node = new Node(); new_node->data = new_data; new_node->next = (*head_ref); new_node->prev = NULL; if ((*head_ref) != NULL) (*head_ref)->prev = new_node; (*head_ref) = new_node;}void printList(Node* node){ Node* last; cout << "\nTraversal in forward" << " direction \n" while (node != NULL) { cout << " " << node->data << " " last = node; node = node->next; } cout << "\nTraversal in reverse" << " direction \n" while (last != NULL) { cout << " " << last->data << " " last = last->prev; }}int main(){ Node* head = NULL; push(&head, 6); push(&head, 7); push(&head, 1); cout << "Created DLL is: " printList(head);return 0;} ‏‏لیست پیوندی حلقوی(دایره ایی):‏‏ در لیست پیوندی حلقوی، گره آخر شامل اشاره گر به گره اول لیست است، در حالی که در تراورزال یک لیست پیوندی ، ما می توانیم در هر گره ای آغاز و با عبور از لیست در هر جهتی، رو به جلو و یا رو به عقب و تا زمانی که رسیدن به همان گره شروع شده باشد. بدین ترتیب یک لیست پیوندی حلقوی هیچ آغاز و پایانی ندارد. همانطور که در تصویر زیر مشاهده می کنید:ساختار لیست پیوندی حلقوی در زبان C:class Node {public: int data; Node* next;};ایجاد و تراورزال لیست پیوندی حلقوی در زبان c:#include using namespace std;class Node {public: int data; Node* next;};void push(Node** head_ref, int data){ Node* ptr1 = new Node(); Node* temp = *head_ref; ptr1->data = data; ptr1->next = *head_ref; if (*head_ref != NULL) { while (temp->next != *head_ref) { temp = temp->next; } temp->next = ptr1; } else ptr1->next = ptr1; *head_ref = ptr1;}void printList(Node* head){ Node* temp = head; if (head != NULL) { do { cout << temp->data << " " temp = temp->next; } while (temp != head); }}// Driver Codeint main(){ Node* head = NULL; push(&head, 12); push(&head, 56); push(&head, 2); push(&head, 11); cout << "Contents of Circular" << " Linked List\n " printList(head);return 0;}گرداورندگان:علی قاسمی حسین قربانیسروش زندیمهدی نظری ابوالفضل ولی الهی یاشار مرتاضبا تشکر از استاد دکتر مریم حاجی اسمعیلی دکترای علوم کامپیوتر از دانشگاه کینگستون لندنDr. Maryam Hajiesmaeili phD of computer science from Kingstone university of London https://ir.linkedin.com/in/dr-maryam-hajiesmaeili-90930743 منابع: https://www.tutorialspoint.com/data_structures_algorithms/linked_list_program_in_c.htm

نوشته های مهدی نظری

‏انواع لیست پیوندی