1.3 链表C（20段代码）
<h2>链表的构建</h2>
<pre><code class="language-c">#include &lt;stdio.h&gt; // 包含标准输入输出库，用于输入输出操作
#include &lt;stdlib.h&gt; // 包含标准库，用于动态内存分配等操作
// 定义元素类型，这里使用int类型
typedef int EType;
// 定义链表节点结构体
typedef struct LinkNode {
EType data; // 节点存储的数据，类型为EType（即int）
struct LinkNode* next; // 指向下一个节点的指针
} Link; // 为结构体定义一个别名Link，方便后续使用</code></pre>
<p> </p>
<h1>辅助操作</h1>
<h2>【初始化/创建】</h2>
<pre><code class="language-c">/**
* 初始化链表
*
* @return 返回链表的头指针，如果内存分配失败则返回NULL
*/
Link* init() {
// 动态分配一个链表节点的内存
Link* head = (Link*)malloc(sizeof(Link));
// 检查内存分配是否成功
if (head == NULL) {
// 如果内存分配失败，返回NULL
return NULL;
}
// 初始化头节点的next指针为NULL，表示链表为空
head-&gt;next = NULL;
// 返回头节点指针
return head;
}</code></pre>
<p> </p>
<h2>【销毁】</h2>
<pre><code class="language-c">/**
* 释放链表占用的内存
*
* @param link 链表的头指针
*/
void destroy(Link* link) {
// 当链表不为空时，进入循环
while (link-&gt;next) {
// 保存当前节点的下一个节点的地址
Link* n = link-&gt;next;
// 释放当前节点的内存
free(link);
// 将当前节点指针移动到下一个节点
link = n;
}
// 释放最后一个节点的内存
free(link);
}</code></pre>
<p> </p>
<h2>【格式化输出】</h2>
<pre><code class="language-c">/**
* 显示链表中的所有元素
*
* @param s 链表的头指针
*/
void show(Link* s) {
// 如果传入的头指针为空，输出提示信息并返回
if (s == NULL) {
printf(&quot;s is null\n&quot;);
return;
}
// 如果链表为空（即头指针的next为NULL），输出提示信息并返回
if (s-&gt;next == NULL) {
printf(&quot;s is empty\n&quot;);
return;
}
// 遍历链表，打印每个节点的数据
while (s-&gt;next) {
printf(&quot;%d &quot;, s-&gt;next-&gt;data); // 打印当前节点的下一个节点的数据
s = s-&gt;next; // 将当前节点指针移动到下一个节点
}
// 打印换行符，使输出更整洁
printf(&quot;\n&quot;);
}</code></pre>
<p> </p>
<h2>【判断是不是空】</h2>
<pre><code class="language-c">int isempty(Link* link) {
// 检查链表的头指针的next是否为NULL
// 如果为NULL，表示链表为空，返回1
// 否则，返回0
return link-&gt;next == NULL;
}</code></pre>
<h1>增加元素</h1>
<h2>【头部添加】</h2>
<pre><code class="language-c">/**
* 在链表头部插入一个新节点
*
* @param link 链表的头指针
* @param data 要插入的新节点的数据
*/
void append_head(Link* link, EType data) {
// 动态分配一个新节点的内存
Link* node = (Link*)malloc(sizeof(Link));
// 检查内存分配是否成功
if (node == NULL) {
// 如果内存分配失败，直接返回
return;
}
// 设置新节点的数据
node-&gt;data = data;
// 将新节点的next指针指向当前头指针的next节点
node-&gt;next = link-&gt;next;
// 将头指针的next指针指向新节点
link-&gt;next = node;
}</code></pre>
<p> </p>
<h2>【尾部添加】</h2>
<pre><code class="language-c">/**
* 在链表尾部插入一个新节点
*
* @param link 链表的头指针
* @param data 要插入的新节点的数据
*/
void append_tail(Link* link, EType data) {
// 动态分配一个新节点的内存
Link* node = (Link*)malloc(sizeof(Link));
// 检查内存分配是否成功
if (node == NULL) {
// 如果内存分配失败，直接返回
return;
}
// 设置新节点的数据
node-&gt;data = data;
// 设置新节点的next指针为NULL，表示它是链表的最后一个节点
node-&gt;next = NULL;
// 遍历链表，找到最后一个节点
while (link-&gt;next) {
// 将当前节点指针移动到下一个节点
link = link-&gt;next;
}
// 将新节点链接到链表的末尾
link-&gt;next = node;
}</code></pre>
<p> </p>
<h2>【插入】</h2>
<pre><code class="language-c">/**
* 在链表的指定位置插入一个新节点
*
* @param link 链表的头指针
* @param i 插入位置的索引
* @param data 要插入的新节点的数据
* @return 如果插入成功返回0，否则返回1
*/
int insert(Link* link, int i, int data) {
// 如果插入位置索引小于0，返回1表示插入失败
if (i &lt; 0) {
return 1;
}
// 用于计数的变量
int j;
// 遍历链表，找到插入位置的前一个节点
for (j = 0; j &lt; i; j++) {
// 如果在到达指定位置之前链表已经结束，返回1表示插入失败
if (link-&gt;next == NULL) {
return 1;
}
// 将当前节点指针移动到下一个节点
link = link-&gt;next;
}
// 动态分配一个新节点的内存
Link* node = (Link*)malloc(sizeof(Link));
// 检查内存分配是否成功
if (node == NULL) {
return 1; // 如果内存分配失败，返回1表示插入失败
}
// 设置新节点的数据
node-&gt;data = data;
// 将新节点的next指针指向当前节点的下一个节点
node-&gt;next = link-&gt;next;
// 将当前节点的next指针指向新节点
link-&gt;next = node;
// 插入成功，返回0
return 0;
}</code></pre>
<p> </p>
<h2>【拼接】</h2>
<pre><code class="language-c">/**
* 将链表link2的所有节点追加到链表link1的末尾
*
* @param link1 第一个链表的头指针
* @param link2 第二个链表的头指针
*/
void extend(Link* link1, Link* link2) {
// 遍历链表link1，找到其最后一个节点
while (link1-&gt;next) {
// 将当前节点指针移动到下一个节点
link1 = link1-&gt;next;
}
// 将链表link2的第一个实际节点（即link2-&gt;next）链接到链表link1的末尾
link1-&gt;next = link2-&gt;next;
// 释放链表link2的头节点，因为它不再需要
free(link2);
}</code></pre>
<p> </p>
<h1>删除元素</h1>
<h2>【弹出一个元素】</h2>
<pre><code class="language-c">/**
* 从链表的末尾移除一个节点
*
* @param link 链表的头指针
* @return 如果移除成功返回0，如果链表为空返回1
*/
int pop(Link* link) {
// 检查链表是否为空
if (isempty(link)) {
// 如果链表为空，返回1表示移除失败
return 1;
}
// 遍历链表，找到倒数第二个节点
while (link-&gt;next-&gt;next != NULL) {
// 将当前节点指针移动到下一个节点
link = link-&gt;next;
}
// 释放链表的最后一个节点
free(link-&gt;next);
// 将倒数第二个节点的next指针设为NULL，表示链表的末尾
link-&gt;next = NULL;
// 移除成功，返回0
return 0;
}</code></pre>
<p> </p>
<h2>【删除第i个】</h2>
<pre><code class="language-c">/**
* 从链表的指定位置移除一个节点
*
* @param link 链表的头指针
* @param i 要移除的节点的位置索引
* @return 如果移除成功返回0，如果索引无效或链表为空返回1
*/
int popi(Link* link, int i) {
// 检查索引是否有效
if (i &lt; 0) {
// 如果索引小于0，返回1表示移除失败
return 1;
}
// 用于计数的变量
int j;
// 遍历链表，找到要移除节点的前一个节点
for (j = 0; j &lt; i; j++) {
// 如果在到达指定位置之前链表已经结束，返回1表示移除失败
if (link-&gt;next == NULL) {
return 1;
}
// 将当前节点指针移动到下一个节点
link = link-&gt;next;
}
// 检查要移除的节点是否存在
if (link-&gt;next) {
// 保存要移除的节点
Link* n = link-&gt;next;
// 将当前节点的next指针指向要移除节点的下一个节点
link-&gt;next = link-&gt;next-&gt;next;
// 释放要移除的节点的内存
free(n);
// 移除成功，返回0
return 0;
} else {
// 如果要移除的节点不存在，返回1表示移除失败
return 1;
}
}</code></pre>
<p> </p>
<h2>【删除n这个值】</h2>
<pre><code class="language-c">/**
* 从链表中移除所有值为指定数据的节点
*
* @param link 链表的头指针
* @param data 要移除的节点的数据值
*/
void remove_(Link* link, EType data) {
// 用于临时保存要移除的节点
Link* t;
// 遍历链表
while (link-&gt;next) {
// 检查当前节点的下一个节点的数据是否等于要移除的数据
if (link-&gt;next-&gt;data == data) {
// 保存要移除的节点
t = link-&gt;next;
// 将当前节点的next指针指向要移除节点的下一个节点
link-&gt;next = link-&gt;next-&gt;next;
// 释放要移除的节点的内存
free(t);
} else {
// 如果当前节点的下一个节点的数据不等于要移除的数据，继续遍历
link = link-&gt;next;
}
}
}</code></pre>
<p> </p>
<h2>【清空】</h2>
<pre><code class="language-c">/**
* 递归清空链表中的所有节点
*
* @param link 链表的头指针
*/
void clear(Link* link) {
// 如果当前节点的下一个节点为空，表示已经到达链表末尾，直接返回
if (link-&gt;next == NULL) {
return;
}
// 递归调用clear函数，处理下一个节点
clear(link-&gt;next);
// 释放下一个节点的内存
free(link-&gt;next);
// 将当前节点的next指针设为NULL，表示该节点的下一个节点已被清除
link-&gt;next = NULL;
}</code></pre>
<p> </p>
<h1>修改</h1>
<h2>【修改第i个值】</h2>
<pre><code class="language-c">/**
* 在链表的指定位置设置节点的数据
*
* @param link 链表的头指针
* @param i 要设置数据的节点的位置索引
* @param data 要设置的新数据值
* @return 如果设置成功返回0，如果索引无效或链表为空返回1
*/
int set(Link* link, int i, EType data) {
// 检查索引是否有效
if (i &lt; 0) {
// 如果索引小于0，返回1表示设置失败
return 1;
}
// 用于计数的变量
int j;
// 遍历链表，找到要设置数据的节点的前一个节点
for (j = 0; j &lt; i; j++) {
// 如果在到达指定位置之前链表已经结束，返回1表示设置失败
if (link-&gt;next == NULL) {
return 1;
}
// 将当前节点指针移动到下一个节点
link = link-&gt;next;
}
// 检查要设置数据的节点是否存在
if (link-&gt;next) {
// 设置节点的数据
link-&gt;next-&gt;data = data;
// 设置成功，返回0
return 0;
} else {
// 如果要设置数据的节点不存在，返回1表示设置失败
return 1;
}
}</code></pre>
<p> </p>
<h2>【替换x为y】</h2>
<pre><code class="language-c">/**
* 在链表中将所有值为x的节点的数据替换为y
*
* @param link 链表的头指针
* @param x 要被替换的旧数据值
* @param y 新的数据值
*/
void replace(Link* link, EType x, EType y) {
// 遍历链表
while (link-&gt;next) {
// 检查当前节点的下一个节点的数据是否等于x
if (link-&gt;next-&gt;data == x) {
// 如果等于x，将其数据替换为y
link-&gt;next-&gt;data = y;
}
// 将当前节点指针移动到下一个节点
link = link-&gt;next;
}
}</code></pre>
<p> </p>
<h2>【翻转】</h2>
<p>略，一般不对单链表进行翻转，思考：为什么？</p>
<p> </p>
<h1>查询</h1>
<h2>【获取长度】</h2>
<pre><code class="language-c">/**
* 计算链表的长度
*
* @param link 链表的头指针
* @return 链表的长度
*/
int length(Link* link) {
// 初始化计数器，用于记录链表的节点数
int count = 0;
// 遍历链表
while (link-&gt;next) {
// 每遍历一个节点，计数器加1
count++;
// 将当前节点指针移动到下一个节点
link = link-&gt;next;
}
// 返回链表的长度
return count;
}</code></pre>
<p> </p>
<h2>【获取最大值/最小值】</h2>
<pre><code class="language-c">/**
* 获取链表中的最大值
*
* @param link 链表的头指针
* @param data 用于存储最大值的指针
* @return 如果获取成功返回0，如果链表为空返回1
*/
int getmax(Link* link, EType* data) {
// 检查链表是否为空
if (isempty(link)) {
// 如果链表为空，返回1表示获取失败
return 1;
}
// 初始化最大值为链表第一个实际节点的数据
int max = link-&gt;next-&gt;data;
// 遍历链表
while (link-&gt;next) {
// 检查当前节点的数据是否大于当前最大值
if (max &lt; link-&gt;next-&gt;data) {
// 如果当前节点的数据更大，更新最大值
max = link-&gt;next-&gt;data;
}
// 将当前节点指针移动到下一个节点
link = link-&gt;next;
}
// 将最大值赋值给传入的指针
*data = max;
// 获取成功，返回0
return 0;
}</code></pre>
<p> </p>
<h2>【判断某个值在不在里面】</h2>
<pre><code class="language-c">/**
* 检查链表中是否包含指定的数据
*
* @param link 链表的头指针
* @param data 要查找的数据
* @return 如果链表中包含指定的数据返回1，否则返回0
*/
int has(Link* link, EType data) {
// 检查链表是否为空
if (isempty(link)) {
// 如果链表为空，返回0表示未找到
return 0;
}
// 遍历链表
while (link-&gt;next) {
// 检查当前节点的数据是否等于要查找的数据
if (link-&gt;next-&gt;data == data) {
// 如果找到，返回1表示已找到
return 1;
}
// 将当前节点指针移动到下一个节点
link = link-&gt;next;
}
// 如果遍历完链表仍未找到，返回0表示未找到
return 0;
}</code></pre>
<p> </p>
<h2>【获取某个位置的值】</h2>
<pre><code class="language-c">/**
* 获取链表中指定位置的节点数据
*
* @param link 链表的头指针
* @param i 要获取的节点的位置索引
* @param data 用于存储获取到的数据的指针
* @return 如果获取成功返回0，如果索引无效或链表为空返回1
*/
int get(Link* link, int i, EType* data) {
// 检查索引是否有效
if (i &lt; 0) {
// 如果索引小于0，返回1表示获取失败
return 1;
}
// 用于计数的变量
int j;
// 遍历链表，找到指定位置的节点
for (j = 0; j &lt; i; j++) {
// 如果在到达指定位置之前链表已经结束，返回1表示获取失败
if (link-&gt;next == NULL) {
return 1;
}
// 将当前节点指针移动到下一个节点
link = link-&gt;next;
}
// 检查指定位置的节点是否存在
if (link-&gt;next) {
// 将指定位置的节点数据赋值给传入的指针
*data = link-&gt;next-&gt;data;
// 获取成功，返回0
return 0;
} else {
// 如果指定位置的节点不存在，返回1表示获取失败
return 1;
}
}</code></pre>
<p> </p>
<h2>【获取某个值的位置】</h2>
<pre><code class="language-c">/**
* 查找链表中指定数据的索引
*
* @param link 链表的头指针
* @param data 要查找的数据
* @return 如果找到数据，返回其索引；如果未找到，返回-1
*/
int index_(Link* link, EType data) {
// 初始化索引变量，初始值为-1
int i = -1;
// 遍历链表
while (link-&gt;next) {
// 索引递增
i++;
// 检查当前节点的数据是否等于要查找的数据
if (link-&gt;next-&gt;data == data) {
// 如果找到，返回当前索引
return i;
}
// 将当前节点指针移动到下一个节点
link = link-&gt;next;
}
// 如果遍历完链表仍未找到，返回-1表示未找到
return -1;
}</code></pre>