- 1树莓派nmap扫描
- 2Fooocus-开源AI绘画工具 无需繁琐配置 一键下载安装_fooocus 需要关防火墙吗
- 3ionic5+angular8混合移动开发（一）——环境搭建_ionic新建项目指定angular的版本
- 4GIT07_Fetch、rebase命令详解、日常开发步骤_fetch rebase
- 52020年非上海生源应届普通高校毕业生落户材料办理流程及注意事项_英语六级 证书 复印件
- 6测试工程师转android开发,「(android/ios)移动端测试工程师工作经验分享」-看准网...
- 7新冠知识图谱学习记录
- 8Shiro反序列化漏洞利用详解（Shiro-550+Shiro-721）_shiro 550与721加密方式
- 9linux shell 统计行数的8种方法_shell中计算行数
- 10Kafka#ELK+Kafka高并发日志分析收集系统_中间件kafka审计记录
链表【+逆序链表】、循环队列、堆栈讲解（头插法和尾插法）_逆序构造链表
赞
踩
堆栈的知识点可以参考这篇文章：详解堆栈的几种实现方法——C语言版
循环队列的实现可以参考这篇文章：队列的实现（1）：循环队列的实现
一、链表
（1）链表简单介绍
链表是一种常用的数据结构。相较于数组，链表的好处在于可以动态地分配内存空间，因此可以适应更为灵活的内存需求。
链表由若干个节点组成，每个节点包含两个部分：数据域和指针域。数据域存储节点的数据，指针域指向下一个节点。将所有的节点连接起来，就形成了一个链表。
优点：
- 可以动态地分配内存空间，不受固定大小的限制；
- 插入和删除操作效率高，时间复杂度为O(1)；
- 可以轻松地实现栈、队列等数据结构。
缺点：
- 随机访问不方便，需要遍历整个链表；
- 内存空间占用较大，因为每个节点都需要额外的指针域；
- 不支持快速排序等高级算法。
带头结点和不带头结点的区别：
（2）链表的创建
链表创建的基本步骤如下：
- 定义一个结构体，用于表示链表的节点。结构体中至少包含两个成员：一个是存放数据的变量，另一个是指向下一个节点的指针。
- 定义一个头指针变量，并初始化为空指针（NULL）。
- 创建节点，为每个节点分配内存空间，使用 malloc() 函数可以在堆上动态地分配足够大小的内存空间。
- 将新节点添加到链表中，需要修改前面节点的指针域和新节点的指针域。
- 重复步骤 3 和 4 直到链表的末尾（尾插法）。
- 最后返回头指针即可，就完成了整个链表的创建操作。
typedef struct node_s { int data; struct node_s *next; }node_t;//定义一个结构体 int main(int argc, char argv[]) { node_t *head = NULL;//创建头节点 node_t *new_node;//创建新的节点 new_node = malloc(sizeof(node_t));//申请结构体大小的空间 memset(new_node,0,sizeof(*new_node));//初始化，清零 new_node->next = NULL; new_node->data = xxx;//将数据放进去 ...... }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
（3）数据的插入
链表实现数据的头插法和尾插法是两种常见的链表操作方法，它们的区别在于新节点插入链表的位置不同。所以在写代码的时候，实现的代码方式也是不一样的。
【1】头插法
将新节点插入到链表的头部。首先新建一个节点，赋值并将其 next 指针指向链表头指针，然后更新链表头指针为这个新节点的地址。如果链表为空，则新节点就是唯一的节点。如果链表不为空，那么新节点将成为头节点，原来的头节点成为它的下一个节点，这样就完成了节点的插入。
new_node->next = head;
head = new_node;
- 1
- 2
头插法直接将我们的next域指向head指向的节点，然后将head指向我们的新节点就可。一定注意需要先将新节点的next指向head指向的节点，不然如果有数据的话就会丢失了。
【2】尾插法
将新节点插入到链表的尾部。需要先判断链表是否为空。如果链表为空，直接将链表头指针指向新节点。如果链表不为空，则需要从链表头开始遍历到链表尾部，找到最后一个节点，然后将最后一个节点的 next 指针指向新节点。尾插法的优点是保证节点的顺序是正序的。
node_t *tail;
if(head == NULL)
{
head = new_node;
}
else
{
tail->next = new_node;
}
tail = new_node;
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
尾插法的代码中我们有创建了一个名为tail的节点指针，这个指针只是指向前面一个node的。我们不能直接将最前面的head指向new_node，不然中间的数据就断开了，但是我们可以创建一个新的节点指针保存前面一个node，然后将next域指向new_node，在将我们的tail保存我们的new_node就可以了。
总之：
头插法【栈】：先进后出（可以理解为先进入链表，但是排在后面）。尾插法【队列】：先进先出（可以理解为进进去链表，排在前面）。所以实现栈和队列的时候也就是用到了不同的插入方法。
（4）链表的删除
删除节点步骤：
- 从链表的头节点开始遍历到要删除节点的前一个节点，同时记录当前节点和前一个节点的地址。在遍历过程中，可以通过比较当前节点的 next 指针是否指向要删除的节点来找到要删除节点的前驱节点。
- 找到要删除节点的前驱节点后，将前驱节点的 next 指针指向要删除节点的下一个节点。如果要删除的是头节点，那么需要更新链表头指针为第二个节点的地址；如果要删除的是尾节点，则需要将前驱节点的 next 指针设置为 NULL。
- 删除要删除节点的内存空间，释放其占用的内存资源。
// 删除链表中指定数据值的节点 node_t *list_delete(node_t *head, int data) { if (head == NULL) // 特判：链表为空 { return NULL; } if (head->data == data) // 特判：头节点的值等于data { node_t *new_head = head->next;//删除节点1的数据，然后head替换节点1的next free(head); return new_head; } node_t *p = head; while (p->next != NULL && p->next->data != data) { p = p->next; } if (p->next != NULL) // 找到了待删除的节点 { node_t *q = p->next; // q指向待删除的节点 p->next = q->next; // 将p的指针指向q的后继节点 free(q); // 释放待删除的节点 } return head; // 返回头节点的指针 }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
首先，程序会对链表为空的情况进行特判，如果链表为空则直接返回 NULL。
接着，程序会对头节点的值与待删除值相等的情况进行特判。如果头节点的值等于待删除值，则将头指针更新为下一个节点的地址，并释放原来的头节点占用的内存空间，然后返回新的头指针。
如果头节点的值不等于待删除值，则从头节点开始遍历链表，直到找到待删除的节点或者遍历到链表末尾。循环中的条件语句 p->next != NULL && p->next->data != data 表示只要当前节点 p 的下一个节点不为空且下一个节点的值不等于待查找的值 data，就继续遍历链表。当遍历到一个节点的值等于待查找的值 data 或者遍历到链表的末尾时，循环结束。
如果找到了待查找的节点，程序会在循环结束后返回指向该节点的指针 p；如果没有找到，则返回 NULL。需要注意的是，在判断节点的值是否等于待查找的值时，代码使用的是 p->next->data != data 而不是 p->data != data，这是因为在进入循环之前就已经将 p 指向了链表的第一个有效节点，而不是头节点，因此在循环中需要访问 p 的下一个节点。
最后，函数返回头指针。
（5）源代码实现
实现的功能：
- 宏定义LIST_HEAD_INSERT和LIST_TAIL_INSERT决定实现的是尾插法还是头插法
- 创建链表
- 插入数据（1-10）
- 实现删除指定节点函数
- 遍历链表打印数据
#include<stdio.h> #include<stdlib.h> #include<string.h> #define LIST_HEAD_INSERT //#define LIST_TAIL_INSERT typedef struct node_s { int data; struct node_s *next; }node_t;//定义一个结构体，相当于一节小火车 // 删除链表中指定数据值的节点 node_t *list_delete(node_t *head, int data) { if (head == NULL) // 特判：链表为空 { return NULL; } if (head->data == data) // 特判：头节点的值等于data { node_t *new_head = head->next; free(head); return new_head; } node_t *p = head; while (p->next != NULL && p->next->data != data) { p = p->next; } if (p->next != NULL) // 找到了待删除的节点 { node_t *q = p->next; // q指向待删除的节点 p->next = q->next; // 将p的指针指向q的后继节点 free(q); // 释放待删除的节点 } return head; // 返回头节点的指针 } //打印链表内容 void list_print(node_t *head) { node_t *node = NULL;//遍历链表打印 for(node = head; node != NULL; node = node->next) { printf("%d ",node->data); } printf("\n"); } int main(int argc, char *argv[]) { node_t *head = NULL;//头节点 node_t *new_node;//新的小火车 node_t *tail;//小火车的尾巴 int i; for(i = 0; i < 10; i++ ) { new_node = malloc(sizeof(node_t));//申请结构体大小的空间，类似于申请一节小车厢 //memset(new_node,0,sizeof(node_t))//几万行代码之后可能就不知道new_node是node_t类型的 memset(new_node,0,sizeof(*new_node));//这样写比较好，因为如果代码太多的话，就不知道这个new_node是一个指针 new_node->next = NULL; new_node->data = i+1;//将数据放进去 #ifdef LIST_TAIL_INSERT if(head == NULL) { head = new_node; } else { tail->next = new_node; } tail = new_node;//节点插完之后，引用第三个指针，tail指向第这个节点（tail指向的这段空间有一个叫next的域），就不用head了 #elif (defined LIST_HEAD_INSERT) new_node->next = head; head = new_node; #endif } list_print(head); list_delete(head, 5); list_print(head); return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
结果：
上述代码定义 node_t 结构体时，包含了两个域：data 表示节点存储的数据值，next 表示指向下一个节点的指针。
在创建链表时，通过 for 循环创建多个节点，并通过宏定义来选择是使用头插法还是尾插法进行节点的插入。采用头插法时，每次新插入的节点都成为链表的新头节点；采用尾插法时，则将新节点插入到链表尾部。
对于删除操作，先判断链表是否为空，如果是则直接返回 NULL。如果头节点的值等于待删除的值 data，需要特殊处理，即将头节点指向新的链表头并释放原头节点。否则，从头节点开始遍历链表，直到找到待删除的节点或者遍历到链表末尾位置。如果找到了要删除的节点，只需将该节点的前驱节点指向该节点的后继节点，并释放该节点即可。
最后，通过 list_print 函数遍历链表并输出每个节点的值。
值得注意的是，在创建节点时需要使用 malloc 函数来分配结构体大小的空间，同时需要使用 memset 函数将该空间清零。在使用完节点之后，需要调用 free 函数释放空间，避免内存泄漏问题。
二、队列（循环队列）
（1）队列详细介绍
队列是一种特殊的线性表结构，它只允许在队尾tail 插入元素，在队头 front 读元素。队列的数据结构通常称之为 FIFO（First In First Out），即“先进先出”。
队列的实现方式有两种，分别是顺序队列和链式队列（链式队列就是前面插入数据的尾插法，这里不过多介绍了）。
这是大小为5的队列（即数组的大小为5）：
当我们需要将数据写入的时候，tail++，装满的时候，tail指向最后一个元素，tail=5，不能再进了：
出去数据的时候，front++，直到最后指向最后一个元素，front=5，队列已经空了，不能再出去数据了。
现在队列已经空了，按照常理来说我们可以继续写数据的，但是front和tail都是5，但是现在我们如何再去写或者读数据呢？所以为了解决这个问题，就推出了循环队列，也可以称为循环buffer。
（2）循环队列讲解
循环缓冲区（Circular Buffer），也称为环形缓冲区或循环队列，是基于数组的一种高效的队列实现方式。它可以避免队列为满时浪费大量空间的问题，并且支持对元素的快速访问。
循环缓冲区采用了头尾相连的方式，即队列的头部和尾部在数组中是相邻的。当队列满时，插入操作不再进行，而是从队头开始覆盖之前的数据，实现队列的循环利用。
循环缓冲区的操作需要维护两个指针变量，即头指针 front 和尾指针 rear。其中，front 表示队列的头部，rear 表示队列的尾部。初始时，两个指针都指向第一个位置，然后随着队列的插入和删除操作，移动指针的位置。
（3）循环队列代码实例
下面代码主要实现的功能是循环队列的基本操作，包括创建一个长度为k的循环队列、判断队列是否为空或已满、将元素插入到队尾、输出循环队列中每个元素的值等。同时，这段代码也提供了一个示例，通过调用上述函数实现将元素1到5插入循环队列中，并输出每个元素的值，最终释放循环队列空间。
#include <stdio.h> #include <stdlib.h> #include <stdbool.h> // 引入 bool 类型及相关操作 // 定义 CircularQueue 结构体，其中包含循环队列的基本参数和存储元素的数组 typedef struct { int front; // 队首指针 int tail; // 队尾指针 int size; // 队列中元素的数量 int capacity; // 队列的容量，即可存储的元素个数 int *array; // 存储队列元素的数组 } CircularQueue; /** * @brief 初始化循环队列，创建一个新的循环队列 * * @param k 队列的容量 * @return CircularQueue* 返回指向新循环队列的指针 */ CircularQueue* queueCreate(int k) { // 创建 CircularQueue 结构体指针 CircularQueue *queue = (CircularQueue*) malloc(sizeof(CircularQueue)); if(queue == NULL) // 内存分配失败则返回 NULL 指针 return NULL; queue->front = -1; // 初始情况下队首和队尾指针均指向 -1，表示队列为空 queue->tail = -1; queue->size = 0; // 初始状态下队列中元素数量为 0 queue->capacity = k; // 初始化队列容量 queue->array = (int*) malloc(k * sizeof(int)); // 创建一个 k 大小的数组存储队列元素 if(queue->array == NULL) { // 内存分配失败则释放已分配内存，返回 NULL 指针 free(queue); return NULL; } return queue; // 返回指向新循环队列的指针 } /** * @brief 判断循环队列是否为空 * * @param queue 指向 CircularQueue 结构体的指针 * @return true 队列为空 * @return false 队列不为空 */ bool queueIsEmpty(CircularQueue *queue) { return queue->size == 0; // 根据 size 的值判断队列是否为空 } /** * @brief 判断循环队列是否已满 * * @param queue 指向 CircularQueue 结构体的指针 * @return true 队列已满 * @return false 队列未满 */ bool queueIsFull(CircularQueue *queue) { return queue->size == queue->capacity; // 根据 size 和 capacity 的值判断队列是否已满 } /** * @brief 将元素入队 * * @param queue 指向 CircularQueue 结构体的指针 * @param value 待插入的元素 * @return true 插入成功，元素已成功插入到队尾 * @return false 插入失败，队列已满或出现了异常情况 */ bool queueEnqueue(CircularQueue *queue, int value) { // 先判断队列是否已满，如果已满则插入失败，直接返回 false if(queueIsFull(queue)) return false; // 如果队列为空，则插入元素后队首指针应该指向第一个元素 if(queueIsEmpty(queue)) queue->front = 0; // 计算出下一个尾指针的位置，由于队列是循环队列，因此对 capacity 取模操作 queue->tail = (queue->tail+1) % queue->capacity; // 将元素存储到队尾指针所在的位置 queue->array[queue->tail] = value; queue->size++; // 队列中元素数量加 1 return true; // 插入成功，返回 true } /** * @brief 输出循环队列中每个元素的值 * * @param queue 待输出的循环队列 */ void queuePrint(CircularQueue *queue) { printf("Circular Queue: [ "); for(int i=0; i<queue->size; i++) { // 从队首开始遍历整个队列 // 根据当前元素在数组中的位置计算出元素在循环队列中的真实位置 int index = (queue->front + i) % queue->capacity; printf("%d ", queue->array[index]); // 输出元素值 } printf("]\n"); } /** * @brief 主函数，程序入口 * * @return int 返回整型 0，表示程序正常结束 */ int main() { CircularQueue *queue = queueCreate(5); // 创建长度为 5 的循环队列 if(queue == NULL) { // 如果 CircularQueue 结构体指针为空，则说明创建循环队列失败，退出程序 printf("Failed to create circular queue!\n"); return -1; } // 将元素 1-5 依次插入到循环队列中 queueEnqueue(queue, 1); queueEnqueue(queue, 2); queueEnqueue(queue, 3); queueEnqueue(queue, 4); queueEnqueue(queue, 5); queuePrint(queue); // 输出循环队列中每个元素的值 // 释放循环队列空间 free(queue->array); free(queue); return 0; // 程序执行完毕，返回整型 0 }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
结果：
（4）代码细节讲解
上述代码在判断队列中数据是否已满的情况下，我们是直接比较size（数据的个数）和capacity（5）容量的大小。相等说明满了。空的时候直接看size的大小，如果为0就说明是空的。
上述代码中，我们主要看插入数据和读取数据中获取tail和front的位置的代码即可。
插入数据是我们利用的取模公式，也就是上述图片上所提示的rear = (rear+1)%rb_size：
queue->tail = (queue->tail+1) % queue->capacity;
- 1
读取数据的时候，我们获取下标也是按照取模的方法：
int index = (queue->front + i) % queue->capacity;
- 1
判断空或者满，也可以用front和tail的取模计算方法来判断实现，当然上述代码中没有用到：
空条件：rear==front
满条件：(rear+1)% rb_size==front
- 1
- 2
在没有利用到size的时候，我们判断空或者满的时候确实需要利用到上面的两个条件，但是我们插入一条数据，我们的size就+1，可以直接判断我们的队列中有多少数据，我们的队列容量也是知道的，判断size和容量的大小即可判断是否满，size是否为0判断是否空。当然也可以用上述的判断条件。
三、栈
栈（Stack）是一种常见的数据结构，它的特点是先进后出（Last In First Out，LIFO），即最先放入栈中的元素最后弹出。栈通常有两个基本操作：入栈（Push）和出栈（Pop）。入栈操作将元素加入到栈顶，而出栈操作则将栈顶元素移除并返回该元素的值。
栈也就是上面我们将链表的时候所讲到的头插法。
堆栈的详情知识点看这篇文章吧，写的够详细了：详解堆栈的几种实现方法——C语言版
四、逆序链表
逆序链表是将原链表中的每个节点从后至前依次排列得到的新链表。具体而言，对于原链表中的第一个节点，它将成为逆序链表中的最后一个节点；对于原链表中的第二个节点，它将成为逆序链表中的倒数第二个节点；以此类推，直到最后一个节点成为逆序链表的第一个节点。与原链表不同，逆序链表的头指针指向的是原链表中的最后一个节点。
逆序链表是链表操作中的常见问题，可以使用迭代法或递归法实现。
（1）迭代法实现逆序链表
迭代法使用三个指针，分别指向当前结点、前驱结点和后继结点，依次改变它们的指向即可完成链表的逆序。具体实现代码如下：
node_t *reverseList(node_t *head){
node_t *prev = NULL, *cur = head, *nextNode = NULL;// 设置三个指针：prev、cur和nextNode。初始时，prev为NULL，cur为head。
// 进入while循环，只要当前节点cur不为空就一直循环
while (cur != NULL) {
nextNode = cur->next; // 先用nextNode保存cur的下一个节点，以免在逆序过程中丢失后续节点信息
cur->next = prev;// 将cur节点的next指针指向前一个节点prev，实现逆序操作
prev = cur;//将prev指向目前已经逆序的链表的头节点，也就是cur节点
cur = nextNode; // 将cur指向原链表中它的下一个节点，进入下一次循环
}
return prev;// 返回新的头节点prev，即原链表的尾节点
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
具体实现方法如下：
- 定义三个指针prev、cur和nextNode（图片中为Node），并初始化prev为NULL，cur为head。
- 进入while循环，循环条件是cur不为NULL。这个条件的意思是，只有当cur指向一个非空节点时，才需要执行逆序操作。
- 在循环体内，首先将nextNode指向cur的下一个节点，以备后续使用。
- 然后将cur的next指针指向prev，这样就完成了cur节点的逆序操作。
- 接着将prev指向cur，使得prev指向已经遍历过的节点的最后一个节点，也就是逆序链表的尾节点。
- 最后将cur指向nextNode，也就是指向原链表中cur的下一个节点，进入下一次循环。
- 当cur指向NULL时，循环结束。此时prev指向逆序链表的头节点，因为它是原链表中的最后一个节点，所以函数返回prev。
迭代法是通过循环来进行重复操作的方法。它适用于能够使用循环语句来描述的问题，其基本思想是通过循环不断地执行某个操作来达到目的。由于迭代法中的循环需要占用一定的内存空间，因此在处理大规模数据时，应尽量考虑减少循环次数和内存消耗。
（2）递归法实现逆序链表
递归法先递归到链表末尾，然后对每个结点执行交换操作。由于需要返回新的头结点，因此在递归过程中需要记录前驱结点。具体实现代码如下：
node_t *reverseList(node_t *head) {
// 如果链表为空或者只有一个节点，直接返回头节点
if (head == NULL || head->next == NULL) {
return head;
}
node_t *newHead = reverseList(head->next);// 递归调用reverseList函数，传入head->next节点，并将返回值保存在newHead变量中
head->next->next = head;// 反转当前节点和后续节点之间的指针关系
head->next = NULL;
return newHead;// 返回新的头部节点newHead
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
具体实现方法如下：
- 首先判断输入的head是否为空或者只有一个节点。如果是，则直接返回head本身。
- 如果输入的head节点不为空且后续还有其他节点，则调用reverseList函数，传入head->next节点，并将返回的新头部节点保存在newHead变量中。
- 在返回之后，交换当前节点(head)和后续节点(head->next)之间的关系。具体来说，将head->next->next指针指向head，这样head就成了新链表的尾部节点，head->next指针指向NULL，意味着head节点成为新链表的最后一个节点。
- 最后，返回newHead变量，它指向链表逆序后的新头部节点。
递归法则是通过函数调用自身来进行重复操作的方法。它适用于具有递归结构的问题，例如树、图等数据结构。递归法的基本思想是将一个大问题分解为若干个小问题，然后递归地解决每个小问题，最终合并结果得到完整的问题解决方案。由于递归法需要不断调用函数本身，因此会消耗较多的栈空间，同时也可能导致函数调用次数过多而降低效率。
（3）完整代码实现
#include<stdio.h> #include<stdlib.h> #include<string.h> #define LIST_HEAD_INSERT //#define LIST_TAIL_INSERT typedef struct node_s { int data; struct node_s *next; }node_t;//定义一个结构体，相当于一节小火车 //递归法实现逆序链表 node_t *a_reverseList(node_t *head) { if (head == NULL || head->next == NULL) { return head; } node_t *newHead = a_reverseList(head->next); head->next->next = head; head->next = NULL; return newHead; } //迭代法实现逆序链表 node_t *b_reverseList(node_t *head) { node_t *prev = NULL, *cur = head, *nextNode = NULL; while (cur != NULL) { nextNode = cur->next; cur->next = prev; prev = cur; cur = nextNode; } return prev; } // 删除链表中指定数据值的节点 node_t *list_delete(node_t *head, int data) { if (head == NULL) // 特判：链表为空 { return NULL; } if (head->data == data) // 特判：头节点的值等于data { node_t *new_head = head->next; free(head); return new_head; } node_t *p = head; while (p->next != NULL && p->next->data != data) { p = p->next; } if (p->next != NULL) // 找到了待删除的节点 { node_t *q = p->next; // q指向待删除的节点 p->next = q->next; // 将p的指针指向q的后继节点 free(q); // 释放待删除的节点 } return head; // 返回头节点的指针 } //打印链表内容 void list_print(node_t *head) { node_t *node = NULL;//遍历链表打印 for(node = head; node != NULL; node = node->next) { printf("%d ",node->data); } printf("\n"); } int main(int argc, char *argv[]) { node_t *head = NULL;//头节点 node_t *new_node;//新的小火车 node_t *tail;//小火车的尾巴 int i; for(i = 0; i < 10; i++ ) { new_node = malloc(sizeof(node_t));//申请结构体大小的空间，类似于申请一节小车厢 //memset(new_node,0,sizeof(node_t))//几万行代码之后可能就不知道new_node是node_t类型的 memset(new_node,0,sizeof(*new_node));//这样写比较好，因为如果代码太多的话，就不知道这个new_node是一个指针 new_node->next = NULL; new_node->data = i+1;//将数据放进去 #ifdef LIST_TAIL_INSERT if(head == NULL) { head = new_node; } else { tail->next = new_node; } tail = new_node;//节点插完之后，引用第三个指针，tail指向第这个节点（tail指向的这段空间有一个叫next的域），就不用head了 #elif (defined LIST_HEAD_INSERT) new_node->next = head; head = new_node; #endif } list_print(head); list_print(a_reverseList(head)); return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
结果：
