数据结构 | 双向链表简单实现及图示

- 日理万妓 2022-05-23 11:34 120阅读 0赞

双向链表

\- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

和单向链表相比有以下优势：

插入删除不需要移动元素外，可以原地插入删除

可以双向遍历

\- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

初始化+尾插法图示：//head始终指向头结点，p指向尾节点，方便后续算法使用

![1146465-20170429154747928-1994887382.png][]

删除单个图示：

![1146465-20170429154748350-758050755.png][]

实现代码：

![复制代码][copycode.gif]

1 #include <stdio.h>
      2 #include <stdlib.h>
      3 #include <string.h>
      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);//初始化链表并赋值,返回尾节点last
    107     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     else
    117         printf("Element does not exist, cannot be deleted\n");
    118     /***************************************************************/
    119     DeleteList(&head);//清空列表
    120     PrintList(head);
    121     return 0;
    122 }

![复制代码][copycode.gif]

[1146465-20170429154747928-1994887382.png]: /images/20220523/63d7848b2c4a4f01a5158f6752f7919f.png
[1146465-20170429154748350-758050755.png]: /images/20220523/1f348f1015bc42828b7235073f3095b3.png
[copycode.gif]: /images/20220523/c0080910136f4e3a9754d3f52459ebd6.png