[C语言] 单向链表的构建以及翻转算法_图文详解（附双向链表构建代码）

　　[C语言]单向链表的构建以及翻转算法

一、基本概念

　　单向链表的链接方向是单向的，其中每个结点都有指针成员变量指向链表中的下一个结点，访问链表时要从头节点（带头节点的链表）或存储首个数据的节点（不带头节点的链表）开始顺序查询。本文将以带头结点的非循环单向链表为例，其链表模型如下：

　　其中head为头结点（不存储数据）、data节点存储数据、pNext存储下一节点的地址。

　　当单项链表不包含头结点时，链表首个节点便是所存储的第一个数据的节点；当单项链表是循环链表时，链表中存储最后一个数据的节点中pNext指向的不是NULL而是链表首部。

二、构建算法

1、单项链表节点结构体的定义

　　链表节点包含两个部分：①节点所存储的数据。②节点所存储的下一节点地址。

　　其单个节点模型如下：

1 typedef int T;
2 
3 typedef struct SLNode
4 {
5     //节点保存的数据
6     T data;
7     //下一个节点的位置
8     struct SLNode* next;
9 }SLNode,SLLink;

 1 typedef int T;
 2 
 3 typedef struct DLNode
 4 {
 5     //节点保存的数据
 6     T data;
 7     struct DLNode* prev;
 8     struct DLNode* next;
 9 }DLNode;
10 
11 typedef struct DLLink
12 {
13     struct DLNode* head;
14     struct DLNode* tail;
15 }DLLink;

View Code（双向链表）

　　tips：①用 typedef 定义数据类型能有效提高代码的实用性，②一般用 NODE* 定义节点， LINK* 定义链表，便以区分。

2、单项链表的始终

2.1 单项链表的创建

　　单项链表的创建主要包含三个部分：①为申请头结点内存，②使pNext指向下一节点（NULL）。③返回头地址。

　　其头节点模型如下：

 1 //创建一个链表
 2 SLLink* creat_SLLink()
 3 {
 4     //创建一个节点，表示头节点，该节点并不保存数据
 5     SLLink* head = (SLLink*)malloc(sizeof(SLNode));
 6     //让头节点的next置NULL，表示链表为空
 7     head->next = NULL;
 8     //返回头的地址
 9     return head;
10 }

 1 //创建一个节点
 2 DLNode* creat_DLNode()
 3 {
 4     //创建一个节点，该节点并不保存数据且前后置空
 5     DLNode* node = (DLNode*)malloc(sizeof(DLNode));
 6     node->prev = NULL;
 7     node->next = NULL;
 8     //返回节点的地址
 9     return node;
10 }
11 
12 //创建一个链表
13 DLLink* creat_DLLink()
14 {
15     //创建链表与头尾节点，头尾节点并不保存数据
16     DLLink* link = (DLLink*)malloc(sizeof(DLLink));
17     link->head = creat_DLNode();
18     link->tail = creat_DLNode();
19     //让头尾节点的互指
20     link->head->next = link->tail;
21     link->head->prev = NULL;
22     link->tail->next = NULL;
23     link->tail->prev = link->head;
24     //返回链表地址
25     return link;
26 }

View Code（双向链表）

2.2 单项链表的清空与销毁

　　单项链表的清空与销毁主要包含两个步骤：①依次释放存储数据的节点内存。②释放头结点的内存，变量置空。

 1 //清空链表
 2 void clear_SLLink(SLLink* link)
 3 {
 4     SLNode* node = link->next;
 5     while(node != NULL)
 6     {
 7         SLNode* tmp = node;
 8         node = node->next;
 9         free(tmp);
10     }
11     link->next = NULL;
12 }
13 
14 //销毁链表
15 void destroy_SLLink(SLLink* link)
16 {
17     clear_SLLink(link);
18     free(link);
19     link = NULL;
20 }

 1 //清空链表
 2 void clear_DLLink(DLLink* link)
 3 {
 4     DLNode* node = link->head->next;
 5     while(node != link->tail)
 6     {
 7         node = node->next;
 8         free(node->prev);
 9     }
10     //让头尾节点的互指
11     link->head->next = link->tail;
12     link->tail->prev = link->head;
13 }
14 
15 //销毁链表
16 void destroy_DLLink(DLLink* link)
17 {
18     clear_DLLink(link);
19     free(link);
20     link = NULL;
21 }

View Code（双向链表）

3、单项链表的判定

3.1 单项判定链表是否为空

1 //判断链表是否为空
2 bool emtpy_SLLink(SLLink* link)
3 {
4     return !link->next;
5 }

1 //判断链表是否为空
2 bool emtpy_DLLink(DLLink* link)
3 {
4     return link->tail->next == link->tail;
5 }

View Code（双向链表）

4、单向链表的查询

4.1 获取单向链表中数据的个数

　　获取单向链表中数据的个数主要包含三个步骤：①创建变量存储数据个数、创建node记录头节点的下一节位置点用于遍历链表。②循环遍历，当当前节点的pNext指向NULL时代表已达链表末尾，结束循环。③返回数据个数。

 1 //获得链表里数据的个数
 2 size_t size_SLLink(SLLink* link)
 3 {    
 4     size_t i = 0;
 5     //用node记录头节点的下一个位置
 6     SLNode* node = link->next;
 7     //只要node不为NULL,表示该节点存在
 8     while(node != NULL)
 9     {
10         //让node继续指向下一个节点
11         node = node->next;
12         i++;
13     }
14     return i;
15 }

 1 //获得链表里元素的个数
 2 size_t size_DLLink(DLLink* link)
 3 {    
 4     size_t i = 0;
 5     //用node记录头节点的下一个位置
 6     DLNode* node = link->head->next;
 7     //只要node不为NULL,表示该节点存在
 8     while(node != link->tail)
 9     {
10         //让node继续指向下一个节点
11         node = node->next;
12         i++;
13     }
14     return i;
15 }

View Code（双向链表）

4.2 获取指定下标节点的前一个节点

　　获取指定下标节点的前一个节点主要包含三个步骤：①创建node记录头节点位置用于遍历链表。②循环遍历，当当前节点的pNext指向NULL时代表已达链表末尾，结束循环。③返回指定下标的前一个节点。

 1 //返回下标为index的前一个节点
 2 SLNode* getNode_SLLink(SLLink* link, int index)
 3 {
 4     SLNode* node = link;
 5     //如果index=0 其前一个节点就为link ,并不会进入下面循环
 6     for(int i=0; node != NULL && i<index; i++)
 7     {
 8         node = node->next;
 9     }
10     return node;
11 }

 1 //返回下标为index的个节点
 2 DLNode* getNode_DLLink(DLLink* link, int index)
 3 {
 4     DLNode* node = link->head->next;
 5     //如果index=0 其前一个节点就为DLLink ,并不会进入下面循环
 6     for(int i=0; node != link->tail && i<index; i++)
 7     {
 8         node = node->next;
 9     }
10     return node;
11 }

View Code（双向链表）

4.3 查找指定数据的下标（第一个）

　　查找指定数据的下标主要包含主要包含三个步骤：①创建node记录头节点的下一节位置点用于遍历链表。②循环遍历，当当前节点的pNext指向NULL时代表已达链表末尾，结束循环。③成功返回数据下标，失败则返回 -1 。

 1 //查找数据value的下标
 2 int indexOf_SLLink(SLLink* link, T value)
 3 {
 4     SLNode* node = link->next;
 5     for(int i = 0; node != NULL; i++)
 6     {
 7         if(node->data == value)
 8             return i;
 9         node = node->next;
10     }
11     return -1;
12 }

 1 //查找元素value的下标
 2 int indexOf_DLLink(DLLink* link, T value)
 3 {
 4     DLNode* node = link->head->next;
 5     for(int i = 0; node != link->tail; i++)
 6     {
 7         if(node->data == value)
 8         {
 9             return i;
10         }
11         node = node->next;
12     }
13     return -1;
14 }

View Code（双向链表）

4.4 遍历显示链表

　　遍历显示链表主要包含主要包含三个步骤：①创建node记录头节点的下一节位置点用于遍历链表。②循环遍历，顺序输出每一个节点中储存的数据，当当前节点的pNext指向NULL时代表已达链表末尾，结束循环。

 1 //遍历链表
 2 void travel_SLLink(SLLink* link)
 3 {
 4     SLNode* node = link->next;
 5     while(node != NULL)
 6     {
 7         printf("%d ",node->data);
 8         node = node->next;
 9     }
10     puts("");
11 }

 1 //顺序遍历链表
 2 void sequenceTravel_DLLink(DLLink* link)
 3 {
 4     DLNode* node = link->head->next;
 5     while(node != link->tail)
 6     {
 7         printf("%d ",node->data);
 8         node = node->next;
 9     }
10     puts("");
11 }

View Code（双向链表）

5、单项链表的节点插入

5.1 将一个节点插入指定下标

　　将一个节点插入指定下标（index）主要包含三个步骤：①获取指定下标节点的上一个节点位置。②创建node节点存储需要插入的数据。③让插入节点的下一个节点指向index前一个节点的后节点，让index的前节点的下一个节点指向当前插入的节点。

　　其演示模型如下：

 1 //插入一个元素到指定位置 index取值范围[0,size_SLLink(SLLink* link)]
 2 bool insert_SLLink(SLLink* link, int index, T value)
 3 {
 4     if(index < 0 || index > size_SLLink(link)) 
 5         return false;
 6     //得到下标为index位置的前一个节点
 7     SLNode* prevSLNode = getNode_SLLink(link, index);
 8     //申请内存，用于保存需要插入的数据
 9     SLNode* node = (SLNode*)malloc(sizeof(SLNode));
10     node->data = value;
11     //插入节点的下一个节点指向index前一个节点的后节点
12     node->next = prevSLNode->next;
13     //让index的前节点的下一个节点指向当前插入的节点
14     prevSLNode->next = node;
15     return true;
16 }
17 //插入一个元素到链表末尾
18 bool insertBack_SLLink(SLLink* link, T value)
19 {
20     return insert_SLLink(link, size_SLLink(link), value);
21 }
22 //插入一个元素到链表首部
23 bool insertFront_SLLink(SLLink* link, T value)
24 {
25     return insert_SLLink(link, 0, value);
26 }

 1 //插入一个元素到指定位置 index取值范围[0,size_DLLink(DLLink* link)
 2 bool insert_DLLink(DLLink* link, int index, T value)
 3 {
 4     if(index < 0 || index > size_DLLink(link)) 
 5     {
 6         return false;
 7     }
 8     //得到下标为index节点
 9     DLNode* currNode = getNode_DLLink(link, index);
10     //申请内存，用于保存需要插入的数据
11     DLNode* insertNode = (DLNode*)malloc(sizeof(DLNode));
12     insertNode->data = value;
13     //插入节点的下一个节点指向index当前节点
14     insertNode->next = currNode;
15     //插入节点的前一个节点指向index节点的前一个节点
16     insertNode->prev = currNode->prev;
17     //让index当前的前节点的下一个节点指向插入的节点
18     currNode->prev->next = insertNode;
19     //让index当前节点的上一个节点指向插入的节点
20     currNode->prev = insertNode;
21     return true;
22 }
23 //插入一个元素到链表末尾
24 bool insertBack_DLLink(DLLink* link, T value)
25 {
26     return insert_DLLink(link, size_DLLink(link)-1, value);
27 }
28 //插入一个元素到链表首部
29 bool insertFront_DLLink(DLLink* link, T value)
30 {
31     return insert_DLLink(link, 0, value);
32 }

View Code（双向链表）

5.2 将一个节点替换指定下标节点

　　将一个节点替换指定下标（index）节点只包含一个步骤：创建node节点获取指定下标节点的位置并存储需要插入的数据。

1 //更新链表下标为index的节点的值
2 bool update_SLink(SLLink* link, int index, T value)
3 {
4     if(index < 0 || index > size_link(link)-1)
5         return false;
6     SLNode* node = getNode_SLLink(link, index+1);
7     node->data = value;
8     return true;
9 }

 1 //更新链表下标为index的节点的值
 2 bool update_DLLink(DLLink* link, int index, T value)
 3 {
 4     if(index < 0 || index > size_DLLink(link)-1)
 5     {
 6         return false;
 7     }
 8     DLNode* node = getNode_DLLink(link, index);
 9     node->data = value;
10     return true;
11 }

View Code（双向链表）

6、单项链表的数据删除

6.1 将一个指定下标的节点删除

　　将一个指定下标的节点（index）删除主要包含四个步骤：①获取指定下标节点的上一个节点位置。②保存要删除的节点，用于释放内存。③让要删除节点的前一个节点指向要删除节点的后一个节点。④释放内存。

　　其演示模型如下：

 1 //删除指定下标的元素
 2 bool delete_SLLink(SLLink* link, int index)
 3 {
 4     if(index < 0 || index > size_SLLink(link)-1) 
 5         return false;
 6     //获得需要删除节点的前一个节点
 7     SLNode* prevSLNode = getNode_SLLink(link, index);
 8     //保存要删除的节点，用于释放内存
 9     SLNode* node  = prevSLNode->next;
10     //让要删除节点的前一个节点指向要删除节点的后一个节点
11     prevSLNode->next = prevSLNode->next->next;
12     free(node);
13     return true;
14 }

 1 //删除指定下标的元素
 2 bool delete_DLLink(DLLink* link, int index)
 3 {
 4     if(index < 0 || index > size_DLLink(link)-1) 
 5     {
 6         return false;
 7     }
 8     //获得需要删除节点
 9     DLNode* currNode = getNode_DLLink(link, index+1);
10     //保存要删除的节点，用于释放内存
11     DLNode* tmp = currNode;
12     currNode->prev->next = currNode->next;
13     currNode->next->prev = currNode->prev;
14     free(tmp);
15     return true;
16 }

View Code（双向链表）

6.2 删除链表中所有包含指定数据的节点

　　删除链表中所有包含指定数据（value）的节点主要包含三个步骤：①设置标志变量（flag）表示该链表的数据是否发生变化。②循环遍历，顺序删除每一个包含指定数据的节点并将标志变量置位置为1，当当前节点的pNext指向NULL时代表已达链表末尾，结束循环。③返回标志变量。

 1 //删除元素为value的所有节点，返回值表示该链表的数据是否发生变化
 2 bool deleteDatas_SLLink(SLLink* link, T value)
 3 {
 4     //作为是否删除成功的一个标志
 5     bool flag = false;
 6     SLNode* prevNode = link;
 7     SLNode* currNode = link->next;
 8     while(currNode != NULL)
 9     {
10         if(currNode->data == value)
11         {
12             SLNode* tmp = currNode;
13             prevNode->next = currNode->next;
14             currNode = currNode->next;
15             free(tmp);
16             flag = true;
17         }
18         else
19         {
20             prevNode = prevNode->next;
21             currNode = currNode->next;
22         }
23     }
24     return flag;
25 }
26 
27 //删除元素为value的第一个元素
28 bool deleteData_SLLink(SLLink* link, T value)
29 {
30     SLNode* prevNode = link;
31     SLNode* currNode = link->next;
32     while(currNode != NULL)
33     {
34         if(currNode->data == value)
35         {
36             SLNode* tmp = currNode;
37             prevNode->next = currNode->next;
38             currNode = currNode->next;
39             free(tmp);
40             return true;
41         }
42         else
43         {
44             prevNode = prevNode->next;
45             currNode = currNode->next;
46         }
47     }
48     return false;
49 }

 1 //删除元素为value的所有节点，返回值表示该链表的数据是否发生变化
 2 bool deleteDatas_DLLink(DLLink* link, T value)
 3 {
 4     //作为是否删除成功的一个标志
 5     bool flag = false;
 6     DLNode* node = link->head->next;
 7     while(node != link->tail)
 8     {
 9         if(node->data == value)
10         {
11             DLNode* tmp = node;
12             node->prev->next = node->next;
13             node->next->prev = node->prev;
14             node = node->next;
15             free(tmp);
16             flag = true;
17         }
18         else
19         {
20             node = node->next;
21         }
22     }
23     return flag;
24 }
25 
26 //删除元素为value的第一个元素
27 bool deleteData_DLLink(DLLink* link, T value)
28 {
29     DLNode* node = link->head->next;
30     while(node != link->tail)
31     {
32         if(node->data == value)
33         {
34             DLNode* tmp = node;
35             node->prev->next = node->next;
36             node->next->prev = node->prev;
37             free(tmp);
38             return true;
39         }
40         else
41         {
42             node = node->next;
43         }
44     }
45     return false;
46 }

View Code（双向链表）

三、拓展应用

1、单项链表的整体翻转

　　单向链表的整体翻转具体步骤见“代码注释”，其演示模型如下（建议先了解代码）：

　　0：记录前一个节点与当前节点

　　1.1：先记录当前节点的后一个节点

　　2.1：让当前节点(node)的下一个节点(node->next)指向前一个节点(prev)

　　3.1：让前一个节点指向当前节点、当前节点指向原先记录的下一个节点

　　1.2：先记录当前节点的后一个节点

　　2.2：让当前节点(node)的下一个节点(node->next)指向前一个节点(prev)

　　3.2 : 让前一个节点指向当前节点、当前节点指向原先记录的下一个节点

　　4 : 让原来的第一个元素变为尾元素，尾元素的下一个置NULL

　　5 : 让链表的头节点指向原来的尾元素

 1 //链表逆序
 2 void reverse(Link link)
 3 {
 4     if(link == NULL || link->next == NULL)
 5         return;
 6     //0、记录前一个节点与当前节点
 7     Node* prevNode = link->next;
 8     Node* node = prevNode->next;//NULL
 9     //只要当前节点存在
10     while(node != NULL)
11     {
12         //1、先记录当前节点的后一个节点
13         Node* nextNode = node->next;
14         //2、让当前节点(node)的下一个节点(node->next)指向(=)前一个节点(prev)
15         node->next = prevNode;
16         //3、让前一个节点指向当前节点、当前节点指向原先记录的下一个节点
17         prevNode = node;
18         node = nextNode;
19     }
20     //4、让原来的第一个元素变为尾元素，尾元素的下一个置NULL
21     link->next->next = NULL;
22     //5、让链表的头节点指向原来的尾元素
23     link->next = prevNode;
24 }

2、链表中每k个节点进行翻转，若最后一组节点数量不足k个，则按实际个数翻转。

　　具体流程参考“单项链表的整体翻转”。

 1 //链表中每k个节点进行翻转，若最后一组节点数量不足k个，则按实际个数翻转。
 2 void reverseByNum(Node* prev,Node* node,int num)
 3 {
 4     if(node == NULL)
 5         return;
 6     Node* prevNode = node;
 7     Node* curNode = node->next;
 8     int count = 1;
 9     while(curNode != NULL)
10     {
11         Node* nextNode = curNode->next;
12         curNode->next = prevNode;
13         prevNode = curNode;
14         curNode = nextNode;
15         count++;
16         if(count == num)
17         {
18             Node* tmp = prev->next;
19             prev->next->next = curNode;
20             prev->next = prevNode;
21             reverseByNum(tmp,curNode,num);
22             return;
23         }
24     }
25     prev->next->next = curNode;
26     prev->next = prevNode;
27 }

　　以上是个人对链表的一些认识及理解，若有错误欢迎各位指出。