————————————————————————————————————————————
双向链表
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
和单向链表相比有以下优势：
插入删除不需要移动元素外，可以原地插入删除
可以双向遍历
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
初始化+尾插法图示：//head始终指向头结点，p指向尾节点，方便后续算法使用
删除单个图示：
实现代码：
1 #include2 #include 3 #include 4 typedef struct Node pNode; 5 struct Node 6 { 7 int data; 8 pNode *prev, *next; 9 }; 10 /* 初始化链表，尾插法 */ 11 pNode *InitList(pNode **head, int n) 12 { 13 pNode *p, *s; 14 (*head) = (pNode *)malloc(sizeof(pNode)); 15 if ((*head) == NULL) 16 exit(0); 17 (*head)->next = NULL;//head的prev和next均指向NULL 18 (*head)->prev = NULL; 19 p = (*head);//p指向head 20 int i; 21 for (i = 0; i < n; ++i) 22 { 23 s = (pNode *)malloc(sizeof(pNode)); 24 if (s == NULL) 25 exit(0); 26 printf("Input the value of the %dth node:", i + 1); 27 scanf("%d", &s->data); 28 s->next = NULL; 29 p->next = s; 30 s->prev = p; 31 p = s;//p指向尾节点 32 } 33 return p; 34 } 35 /* 遍历打印 */ 36 void PrintList(pNode *head) 37 { 38 pNode *p; 39 p = head->next; 40 if (head->next == NULL) 41 printf("the list is empty\n"); 42 while(p != NULL) 43 { 44 printf("%d ", p->data); 45 p = p->next; 46 } 47 printf("\n"); 48 } 49 /* 清空链表 */ 50 void DeleteList(pNode **head) 51 { 52 pNode *p; 53 while((*head)->next != NULL) 54 { 55 p = (*head); 56 p->next->prev = NULL; 57 (*head) = p->next; 58 free(p); 59 } 60 } 61 /* 查找链表内的某个值 */ 62 int SearchList(pNode *head) 63 { 64 int number; 65 printf("Values are about to be deleted:"); 66 scanf("%d", &number); 67 pNode *p; 68 p = head->next; 69 while(p != NULL) 70 { 71 if (p->data == number) 72 { 73 return number; 74 } 75 p = p->next; 76 } 77 return 0; 78 } 79 /* 删除链表中某个元素，令p的前驱节点和后驱节点相互指向即可，如果p是尾节点则直接将前驱节点指向NULL*/ 80 void DelNumqList(pNode **head, int n) 81 { 82 int i; 83 pNode *p; 84 p = (*head)->next; 85 for (i = 1; i < n; ++i) 86 p = p->next; 87 if(p->next == NULL) 88 { 89 p->prev->next = NULL; 90 free(p); 91 } 92 else 93 { 94 p->next->prev = p->prev; 95 p->prev->next = p->next; 96 free(p); 97 } 98 } 99 int main(int argc, char const *argv[])100 {101 int n, element, flag;102 pNode *head, *last;103 /***************************************************************/104 printf("Please input the size of the list:");105 scanf("%d", &n);106 last = InitList(&head, n);//初始化链表并赋值,返回尾节点last107 printf("%d %d \n", head->next->data, last->data); //打印为第一个元素和最后一个元素108 PrintList(head);109 /***************************************************************/110 flag = SearchList(head); //搜索某个值并删除节点111 if (flag > 0 && flag <= n)112 {113 DelNumqList(&head, flag);114 PrintList(head);115 }116 else117 printf("Element does not exist, cannot be deleted\n");118 /***************************************************************/119 DeleteList(&head);//清空列表120 PrintList(head);121 return 0;122 }