服务器之家

服务器之家 > 正文

【数据结构之链表】详细图文教你花样玩链表

时间:2021-04-13 00:14     来源/作者:二十二画程序员

【数据结构之链表】详细图文教你花样玩链表

0. 提要钩玄

 

前面在文章【数据结构链表】看完这篇文章我终于搞懂链表了中已经介绍了链式存储结构,介绍了链式存储结构的最基本(简单)实现——单向链表。

单向链表,顾名思义,它是单向的。

因为单链表的每个结点只有一个数据域和一个指针域,而该指针域只存储了下一个结点的地址,所以我们只能通过某结点找到其直接后继结点,却不能通过某节点找到其直接前驱结点。

此外,由于单链表到尾结点(链表的最后一个结点)结束,所以尾结点的指针域是 NULL,以此来表示链表的终止,这就导致我们遍历到尾结点的时候,如果想再次遍历,只能手动回到头结点再开始遍历。

为了弥补单链表的上面两个缺点,下面介绍两种链表,它们都是单链表的变形,如果你理解了单链表,那么会很容易理解这两种变形。

【数据结构之链表】详细图文教你花样玩链表

目录

1. 单向循环链表

 

1.1. 结构

单链表的尾结点的指针域是 NULL,所以单链表到此终止。如果我们使用单链表的尾结点的指针域存储头结点的地址,即尾结点的直接后继结点为头结点,如此一来,单链表就构成了一个环(循环),称之为单项循环链表。

【数据结构之链表】详细图文教你花样玩链表

1.2. 实现思路

单向循环链表是由单链表进化而来的,算是单链表的“儿子”,所以单链表的那一套结构对于单向循环链表来说完全适用,从上图你也可以看出,结构并无较大改变,二者所不同只在尾结点,所以我们只需要在尾结点和与尾结点相关的操作上下功夫就行了。

因此,单向循环链表的结构体和单链表的结构体相同。

  1. /*单向循环链表的结点的结构体*/ 
  2. typedef struct _Node { 
  3.     int data; //数据域:存储数据 
  4.     struct _Node *next; //指针域:存储直接后继结点的地址 
  5. } Node; 

为了统一对空链表和非空链表的操作,我们使用带头结点的链表来实现它。

1.3. 空链表及初始化

一个空链表如图所示,只有一个头指针和头结点:

【数据结构之链表】详细图文教你花样玩链表

空链表

头结点的指针域指向其本身构成一个循环,我们可以借此来判断链表是否为空。

  1. if (head->next == head) { 
  2.     printf("空链表。\n"); 

想要初始化一个空链表很简单,创造头结点,使头结点的 next 指针指向其自身即可:

  1. Node *create_node(int elem) 
  2.     Node *new = (Node *) malloc(sizeof(Node)); 
  3.     new->data = elem; 
  4.     new->next = NULL
  5.     return new; 
  6.  
  7. /** 
  8.  * 初始化链表 
  9.  * p_head: 指向头指针的指针 
  10.  */ 
  11. void init(Node **p_head) 
  12.     //创建头结点 
  13.     Node *head_node = create_node(0); 
  14.     //头指针指向头结点 
  15.     *p_head = head_node; 
  16.     //头结点的next指针指向其本身,构成环 
  17.     head_node->next = head_node; 

1.4. 插入操作

这里只演示头插法和尾插法

【头插法】

因为带头结点,所以不需要考虑是否为空链表。下图是向空链表中头插两个元素的过程:

【数据结构之链表】详细图文教你花样玩链表

单向循环链表头插法过程

  1. /** 
  2.  * 头插法,新结点为头结点的直接后继 
  3.  * p_head: 指向头指针的指针 
  4.  * elem: 新结点的数据 
  5.  */ 
  6. void insert_at_head(Node **p_head, int elem) 
  7.     Node *new = create_node(elem); 
  8.     Node *head_node = *p_head; //头结点 
  9.     //新结点插入头结点之后 
  10.     new->next = head_node->next
  11.     head_node->next = new; 

【尾插法】

因为为了尽量简单,所以我们并没有设置指向尾结点的尾指针,所以在尾插之前,需要先借助某个指针,遍历至尾结点,然后再插入。

  1. /** 
  2.  * 尾插法:新插入的结点始终在链表尾 
  3.  * p_head: 指向头指针的指针 
  4.  * elem: 新结点的数据 
  5.  */ 
  6. void insert_at_tail(Node **p_head, int elem) 
  7.     Node *new = create_node(elem); 
  8.     Node *head_node = *p_head; //头结点 
  9.     Node *tail = head_node; //tail指针指向头结点 
  10.     while (tail->next != head_node) { //tail遍历至链表尾 
  11.         tail = tail->next
  12.     } 
  13.     //尾插 
  14.     new->next = tail->next
  15.     tail->next = new; 

1.5. 删除操作

删除的本质是“跳过”待删除的结点,所以我们要找到待删除结点的直接前驱结点,然后让其直接前驱结点的 next 指针指向其直接后继结点,以此来“跳过”待删除结点,最后保存其数据域,释放结点,即完成删除。

这里只演示头删法。

因为删除的是头结点的直接后继结点,所以我们不必再费力寻找待删除结点的直接前驱结点了。

【数据结构之链表】详细图文教你花样玩链表

单向循环链表头删法过程

  1. /** 
  2.  * 头删法:删除头结点之后的结点 
  3.  * p_head: 指向头指针的指针 
  4.  * elem: 指向保存数据变量的指针 
  5.  */ 
  6. void delete_from_head(Node **p_head, int *elem) 
  7.     Node *head_node = *p_head; //头结点 
  8.     if (head_node->next == head_node) { 
  9.         printf("空链表,无元素可删。\n"); 
  10.         return
  11.     } 
  12.     Node *first_node = head_node->next; //首结点:头结点的下一个结点 
  13.     *elem = first_node->data; //保存被删除结点的数据 
  14.     head_node->next = first_node->next; //删除结点 
  15.     free(first_node); //释放 

1.6. 遍历操作

我们可以一圈又一圈地循环遍历链表,下面是循环打印 20 次结点地代码:

  1. /** 
  2.  * 循环打印20次结点 
  3.  */ 
  4. void output_20(Node *head) 
  5.     if (head->next == head) { 
  6.         printf("空链表。\n"); 
  7.         return
  8.     } 
  9.     Node *p = head->next
  10.     for (int i = 0; i <= 20; i++) { 
  11.         if (p != head) { //不打印头结点 
  12.             printf("%d ", p->data); 
  13.         } 
  14.         p = p->next
  15.     } 
  16.     printf("\n"); 

2. 双向链表

 

2.1. 结构

顾名思义,双向链表,就是有两个方向,一个指向前,一个指向后。这样我们就弥补了单链表的某个结点只能找到其直接后继的缺陷。如图所示:

【数据结构之链表】详细图文教你花样玩链表

双向链表

2.2. 实现思路

为了实现能指前和指后的效果,只靠 next 指针肯定是不够的,所以我们需要再添加一个指针 —— prev,该指针指向某结点的直接前驱结点。

  1. /*双向链表的结点结构体*/ 
  2. typedef struct _Node { 
  3.     int data; //数据域 
  4.     struct _Node *prev; //指向直接前驱结点的指针 
  5.     struct _Node *next; //指向直接后继结点的指针 
  6. } Node; 

2.3. 空链表及初始化

双向链表的空链表如图所示:

【数据结构之链表】详细图文教你花样玩链表

双向空链表

要初始化一个这样的空链表,需要创造出头结点,然后将两个指针域置空即可:

  1. Node *create_node(int elem) 
  2.     Node *new = (Node *)malloc(sizeof(Node)); 
  3.     new->data = elem; 
  4.     new->prev = NULL
  5.     new->next = NULL
  6.     return new; 
  7.  
  8. void init(Node **p_head) 
  9.     //创建头结点 
  10.     Node *head_node = create_node(0); 
  11.     //头指针指向头结点 
  12.     *p_head = head_node; 

2.4. 插入操作

这里只演示头插法,过程如下:

【数据结构之链表】详细图文教你花样玩链表

【数据结构之链表】详细图文教你花样玩链表

双向链表头插法过程

代码如下:

  1. /** 
  2.  * 头插法,新结点为头结点的直接后继 
  3.  * p_head: 指向头指针的指针 
  4.  * elem: 新结点的数据 
  5.  */ 
  6. void insert_at_head(Node **p_head, int elem) 
  7.     Node *new = create_node(elem); 
  8.     Node *head_node = *p_head; //头结点 
  9.     if (head_node->next != NULL) { //不为空链表 
  10.         Node *first_node = head_node->next; //首结点:头结点的下一个结点 
  11.         //首结点的prev指针指向new结点 
  12.         first_node->prev = new; 
  13.         //new结点的next指针指向首结点 
  14.         new->next = first_node; 
  15.     } 
  16.     //new结点的prev指针指向头结点 
  17.     new->prev = head_node; 
  18.     //头结点的next指针指向new结点 
  19.     head_node->next = new; 

2.5. 删除操作

这里只演示头删法。下图是将一个有两个元素结点的双向链表头删为空链表的过程:

【数据结构之链表】详细图文教你花样玩链表

双向链表头删法过程

代码如下:

  1. /** 
  2.  * 头删法 
  3.  * p_head: 指向头指针的指针 
  4.  * elem: 指向保存变量的指针 
  5.  */ 
  6. void delete_from_head(Node **p_head, int *elem) 
  7.     Node *head_node = *p_head; //头结点 
  8.     Node *first_node = head_node->next; //待删除的首结点:头结点的下一个结点 
  9.     if (head_node->next == NULL) { //判空 
  10.         printf("空链表,无元素可删。\n"); 
  11.         return
  12.     } 
  13.     *elem = first_node->data; //保存数据 
  14.      
  15.     if (first_node->next != NULL) { 
  16.         first_node->next->prev = first_node->prev; 
  17.     } 
  18.     first_node->prev->next = first_node->next
  19.     free(first_node); 

2.6. 遍历操作

有了 next 指针域,我们可以一路向后遍历;有了 prev 指针域,我们可以一路向前遍历。

这里不再展示代码了。

3. 总结

 

了解了单向循环链表和双向链表,就像拿搭积木一样,我们还可以创造出来双向循环链表。这里就不再演示了,读者可以自行尝试。只要你搞懂上面三种链表,这绝非难事。

以上就是链表的花样玩法部分内容,以后还会继续更新。

参考资料

[1]GitHub: https://github.com/xingrenguanxue/Simple-DS-and-Easy-Algo

[2]Gitee: https://gitee.com/xingrenguanxue/Simple-DS-and-Easy-Algo

原文地址:https://mp.weixin.qq.com/s/ngBXuv99oqE9l12eQ6BItA

标签:

相关文章

热门资讯

2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全 2019-12-26
yue是什么意思 网络流行语yue了是什么梗
yue是什么意思 网络流行语yue了是什么梗 2020-10-11
背刺什么意思 网络词语背刺是什么梗
背刺什么意思 网络词语背刺是什么梗 2020-05-22
Intellij idea2020永久破解,亲测可用!!!
Intellij idea2020永久破解,亲测可用!!! 2020-07-29
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总 2020-11-13
返回顶部