数据结构之双链表双链表|数据结构

本文概述

双链表的内存表示
双链表上的操作
C中的菜单驱动程序可实现双链表的所有操作

双链表是链表的一种复杂类型, 其中节点包含指向序列中上一个节点和下一个节点的指针。因此, 在双向链表中, 节点由三部分组成：节点数据, 指向顺序中下一个节点的指针（下一个指针）, 指向上一个节点的指针（上一个指针）。图中显示了双向链接列表中的示例节点。

文章图片
下图显示了一个双向链接列表, 该列表包含三个节点, 这些节点的数据部分中的数字从1到3。

文章图片
在C语言中, 双向链表中节点的结构可以表示为：

struct node { struct node *prev; int data; struct node *next; }

第一个节点的上一个部分和最后一个节点的下一个部分将始终包含null, 指示在每个方向上的结束。
在一个单链表中, 我们只能在一个方向上遍历, 因为每个节点都包含下一个节点的地址, 并且没有任何先前节点的记录。但是, 双链表克服了单链表的这一局限性。由于列表中的每个节点都包含其前一个节点的地址, 因此, 我们也可以使用存储在每个节点的前一部分中的前一个地址, 找到有关前一个节点的所有详细信息。
双链表的内存表示下图显示了双向链接列表的内存表示形式。通常, 双向链表会为每个节点占用更多空间, 因此会导致更广泛的基本操作, 例如插入和删除。但是, 由于列表在两个方向（向前和向后）都维护指针, 因此我们可以轻松地操作列表的元素。
在下图中, 列表的第一个元素（即13）存储在地址1。头指针指向起始地址1。由于这是被添加到列表的第一个元素, 因此列表的prev包含空值。列表的下一个节点位于地址4, 因此第一个节点的下一个指针包含4。
我们可以以这种方式遍历列表, 直到找到下一个包含null或-1的节点。

文章图片
双链表上的操作节点创建

struct node { struct node *prev; int data; struct node *next; }; struct node *head;

下表描述了有关双链表的所有其余操作。

序号	运作方式	描述
1	开始插入	开始时将节点添加到链表中。
2	最后插入	将节点添加到链接列表的末尾。
3	在指定节点后插入	将节点添加到指定节点之后的链接列表中。
4	开始删除	从列表的开头删除节点
5	最后删除	从列表末尾删除节点。
6	删除具有给定数据的节点	删除紧接在包含给定数据的节点之后的节点。
7	Searching	将每个节点数据与要搜索的项目进行比较, 如果找到的项目返回列表, 则返回该项目在列表中的位置。
8	Traversing	至少访问列表的每个节点一次, 以执行某些特定操作, 例如搜索, 排序, 显示等。

C中的菜单驱动程序可实现双链表的所有操作

#include< stdio.h> #include< stdlib.h> struct node { struct node *prev; struct node *next; int data; }; struct node *head; void insertion_beginning(); void insertion_last(); void insertion_specified(); void deletion_beginning(); void deletion_last(); void deletion_specified(); void display(); void search(); void main () { int choice =0; while(choice != 9) { printf("\n*********Main Menu*********\n"); printf("\nChoose one option from the following list ...\n"); printf("\n===============================================\n"); printf("\n1.Insert in begining\n2.Insert at last\n3.Insert at any random location\n4.Delete from Beginning\n 5.Delete from last\n6.Delete the node after the given data\n7.Search\n8.Show\n9.Exit\n"); printf("\nEnter your choice?\n"); scanf("\n%d", & choice); switch(choice) { case 1: insertion_beginning(); break; case 2: insertion_last(); break; case 3: insertion_specified(); break; case 4: deletion_beginning(); break; case 5: deletion_last(); break; case 6: deletion_specified(); break; case 7: search(); break; case 8: display(); break; case 9: exit(0); break; default: printf("Please enter valid choice.."); } } } void insertion_beginning() { struct node *ptr; int item; ptr = (struct node *)malloc(sizeof(struct node)); if(ptr == NULL) { printf("\nOVERFLOW"); } else { printf("\nEnter Item value"); scanf("%d", & item); if(head==NULL) { ptr-> next = NULL; ptr-> prev=NULL; ptr-> data=http://www.srcmini.com/item; head=ptr; } else { ptr-> data=item; ptr-> prev=NULL; ptr-> next = head; head-> prev=ptr; head=ptr; } printf("\nNode inserted\n"); }} void insertion_last() { struct node *ptr, *temp; int item; ptr = (struct node *) malloc(sizeof(struct node)); if(ptr == NULL) { printf("\nOVERFLOW"); } else { printf("\nEnter value"); scanf("%d", & item); ptr-> data=http://www.srcmini.com/item; if(head == NULL) { ptr-> next = NULL; ptr-> prev = NULL; head = ptr; } else { temp = head; while(temp-> next!=NULL) { temp = temp-> next; } temp-> next = ptr; ptr -> prev=temp; ptr-> next = NULL; }} printf("\nnode inserted\n"); } void insertion_specified() { struct node *ptr, *temp; int item, loc, i; ptr = (struct node *)malloc(sizeof(struct node)); if(ptr == NULL) { printf("\n OVERFLOW"); } else { temp=head; printf("Enter the location"); scanf("%d", & loc); for(i=0; i< loc; i++) { temp = temp-> next; if(temp == NULL) { printf("\n There are less than %d elements", loc); return; } } printf("Enter value"); scanf("%d", & item); ptr-> data = http://www.srcmini.com/item; ptr-> next = temp-> next; ptr -> prev = temp; temp-> next = ptr; temp-> next-> prev=ptr; printf("\nnode inserted\n"); } } void deletion_beginning() { struct node *ptr; if(head == NULL) { printf("\n UNDERFLOW"); } else if(head-> next == NULL) { head = NULL; free(head); printf("\nnode deleted\n"); } else { ptr = head; head = head -> next; head -> prev = NULL; free(ptr); printf("\nnode deleted\n"); }} void deletion_last() { struct node *ptr; if(head == NULL) { printf("\n UNDERFLOW"); } else if(head-> next == NULL) { head = NULL; free(head); printf("\nnode deleted\n"); } else { ptr = head; if(ptr-> next != NULL) { ptr = ptr -> next; } ptr -> prev -> next = NULL; free(ptr); printf("\nnode deleted\n"); } } void deletion_specified() { struct node *ptr, *temp; int val; printf("\n Enter the data after which the node is to be deleted : "); scanf("%d", & val); ptr = head; while(ptr -> data != val) ptr = ptr -> next; if(ptr -> next == NULL) { printf("\nCan't delete\n"); } else if(ptr -> next -> next == NULL) { ptr -> next = NULL; } else { temp = ptr -> next; ptr -> next = temp -> next; temp -> next -> prev = ptr; free(temp); printf("\nnode deleted\n"); } } void display() { struct node *ptr; printf("\n printing values...\n"); ptr = head; while(ptr != NULL) { printf("%d\n", ptr-> data); ptr=ptr-> next; } } void search() { struct node *ptr; int item, i=0, flag; ptr = head; if(ptr == NULL) { printf("\nEmpty List\n"); } else { printf("\nEnter item which you want to search?\n"); scanf("%d", & item); while (ptr!=NULL) { if(ptr-> data =http://www.srcmini.com/= item) { printf("\nitem found at location %d ", i+1); flag=0; break; } else { flag=1; } i++; ptr = ptr -> next; } if(flag==1) { printf("\nItem not found\n"); } } }

【数据结构之双链表】输出量

*********Main Menu*********Choose one option from the following list ...===============================================1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete the node after the given data 7.Search 8.Show 9.ExitEnter your choice? 8 printing values...*********Main Menu*********Choose one option from the following list ...===============================================1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete the node after the given data 7.Search 8.Show 9.ExitEnter your choice? 1Enter Item value12Node inserted*********Main Menu*********Choose one option from the following list ...===============================================1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete the node after the given data 7.Search 8.Show 9.ExitEnter your choice? 1Enter Item value123Node inserted*********Main Menu*********Choose one option from the following list ...===============================================1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete the node after the given data 7.Search 8.Show 9.ExitEnter your choice? 1Enter Item value1234Node inserted*********Main Menu*********Choose one option from the following list ...===============================================1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete the node after the given data 7.Search 8.Show 9.ExitEnter your choice? 8 printing values... 1234 123 12*********Main Menu*********Choose one option from the following list ...===============================================1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete the node after the given data 7.Search 8.Show 9.ExitEnter your choice? 2Enter value89node inserted*********Main Menu*********Choose one option from the following list ...===============================================1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete the node after the given data 7.Search 8.Show 9.ExitEnter your choice? 3 Enter the location1 Enter value12345node inserted*********Main Menu*********Choose one option from the following list ...===============================================1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete the node after the given data 7.Search 8.Show 9.ExitEnter your choice? 8 printing values... 1234 123 12345 12 89*********Main Menu*********Choose one option from the following list ...===============================================1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete the node after the given data 7.Search 8.Show 9.ExitEnter your choice? 4node deleted*********Main Menu*********Choose one option from the following list ...===============================================1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete the node after the given data 7.Search 8.Show 9.ExitEnter your choice? 5node deleted*********Main Menu*********Choose one option from the following list ...===============================================1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete the node after the given data 7.Search 8.Show 9.ExitEnter your choice? 8 printing values... 123 12345*********Main Menu*********Choose one option from the following list ...===============================================1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete the node after the given data 7.Search 8.Show 9.ExitEnter your choice? 6 Enter the data after which the node is to be deleted : 123*********Main Menu*********Choose one option from the following list ...===============================================1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete the node after the given data 7.Search 8.Show 9.ExitEnter your choice? 8 printing values... 123*********Main Menu*********Choose one option from the following list ...===============================================1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete the node after the given data 7.Search 8.Show 9.ExitEnter your choice? 7Enter item which you want to search? 123item found at location 1 *********Main Menu*********Choose one option from the following list ...===============================================1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete the node after the given data 7.Search 8.Show 9.ExitEnter your choice? 6 Enter the data after which the node is to be deleted : 123Can't delete*********Main Menu*********Choose one option from the following list ...===============================================1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete the node after the given data 7.Search 8.Show 9.ExitEnter your choice? 9 Exited..