2. 链表的操作（12题）
<h1>1. 链表的构建及初始化</h1>
<pre><code class="language-c">#include &lt;stdio.h&gt; // 包含标准输入输出库，用于输入输出操作
#include &lt;stdlib.h&gt; // 包含标准库，用于动态内存分配等操作
// 定义链表节点结构体
typedef struct LinkNode {
int data; // 节点存储的数据，类型为EType（即int）
struct LinkNode* next; // 指向下一个节点的指针
} Link; // 为结构体定义一个别名Link，方便后续使用
/**
* 初始化链表
*
* @return 返回链表的头指针，如果内存分配失败则返回NULL
*/
Link* init() {
// 动态分配一个链表节点的内存
Link* head = (Link*)malloc(sizeof(Link));
// 初始化头节点的next指针为NULL，表示链表为空
head-&gt;next = NULL;
// 返回头节点指针
return head;
}</code></pre>
<pre><code class="language-python">class LNode:
def __init__(self, data=None):
self.data = data
self.next = None
class Link:
def __init__(self):
self.head = LNode()</code></pre>
<h1>2. 判断链表是不是空</h1>
<pre><code class="language-c">int isempty(Link* link) {
// 检查链表的头指针的next是否为NULL
// 如果为NULL，表示链表为空，返回1
// 否则，返回0
return link-&gt;next == NULL;
}</code></pre>
<pre><code class="language-python">class Link:
def isempty(self):
return self.head.next is None</code></pre>
<h1>3. 头部添加一个元素</h1>
<pre><code class="language-c">/**
* 在链表头部插入一个新节点
*
* @param link 链表的头指针
* @param data 要插入的新节点的数据
*/
void append_head(Link* link, EType data) {
// 动态分配一个新节点的内存
Link* node = (Link*)malloc(sizeof(Link));
// 设置新节点的数据
node-&gt;data = data;
// 将新节点的next指针指向当前头指针的next节点
node-&gt;next = link-&gt;next;
// 将头指针的next指针指向新节点
link-&gt;next = node;
}</code></pre>
<pre><code class="language-python">class Link:
def append_head(self, m):
node = LNode(m)
node.next = self.head.next
self.head.next = node
</code></pre>
<h1>4. 尾部添加一个元素</h1>
<pre><code class="language-c">/**
* 在链表尾部插入一个新节点
*
* @param link 链表的头指针
* @param data 要插入的新节点的数据
*/
void append_tail(Link* link, EType data) {
// 动态分配一个新节点的内存
Link* node = (Link*)malloc(sizeof(Link));
// 设置新节点的数据
node-&gt;data = data;
// 设置新节点的next指针为NULL，表示它是链表的最后一个节点
node-&gt;next = NULL;
// 遍历链表，找到最后一个节点
while (link-&gt;next) {
// 将当前节点指针移动到下一个节点
link = link-&gt;next;
}
// 将新节点链接到链表的末尾
link-&gt;next = node;
}</code></pre>
<pre><code class="language-python">class Link:
def append_tail(self, m):
node = LNode(m)
h = self.head
while h.next:
h = h.next
h.next = node</code></pre>
<h1>5. 在链表的第i个位置插入一个数</h1>
<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));
// 设置新节点的数据
node-&gt;data = data;
// 将新节点的next指针指向当前节点的下一个节点
node-&gt;next = link-&gt;next;
// 将当前节点的next指针指向新节点
link-&gt;next = node;
// 插入成功，返回0
return 0;
}</code></pre>
<pre><code class="language-python">class Link:
def insert(self, i, k):
if i &lt; 0:
return 1
h = self.head
for j in range(i):
if h:
h = h.next
else:
return 1
if h:
node = LNode(k)
node.next = h.next
h.next = node
else:
return 1</code></pre>
<h1>6. 链表末尾删除一个元素</h1>
<pre><code class="language-c">/**
* 从链表的末尾移除一个节点
*
* @param link 链表的头指针
* @return 如果移除成功返回0，如果链表为空返回1
*/
int pop(Link* link) {
// 检查链表是否为空
if (link-&gt;next == NULL) {
// 如果链表为空，返回1表示移除失败
return 1;
}
// 遍历链表，找到倒数第二个节点
while (link-&gt;next-&gt;next != NULL) {
// 将当前节点指针移动到下一个节点
link = link-&gt;next;
}
// 将倒数第二个节点的next指针设为NULL，表示链表的末尾
link-&gt;next = NULL;
// 移除成功，返回0
return 0;
}</code></pre>
<pre><code class="language-python">class Link:
def pop(self):
if self.isempty():
return None
h = self.head
while h.next.next:
h = h.next
k = h.next.data
h.next = None
return k
</code></pre>
<h1>7. 删除第i个元素</h1>
<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>
<pre><code class="language-python">class Link:
def popi(self, i):
if self.isempty():
return None
if i&lt;0:
return None
h = self.head
for j in range(i):
if h.next is None:
return None
h = h.next
if h.next:
k = h.next.data
h.next = h.next.next
return k
else:
return None
</code></pre>
<h1>8. 修改第i个值的数据</h1>
<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>
<pre><code class="language-python">class Link:
def set(self, i, x):
if self.isempty():
return None
if i&lt;0:
return None
h = self.head
for j in range(i):
if h.next is None:
return None
h = h.next
if h.next:
h.next.data = x
else:
return None
</code></pre>
<h1>9. 计算链表的长度</h1>
<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>
<pre><code class="language-python">class Link:
def length(self):
h = self.head
count = 0
while h.next:
count += 1
h = h.next
return count
</code></pre>
<h1>10. 获取链表最大值</h1>
<pre><code class="language-c">/**
* 获取链表中的最大值
*
* @param link 链表的头指针
* @param data 用于存储最大值的指针
* @return 如果获取成功返回0，如果链表为空返回1
*/
int getmax(Link* link, EType* data) {
// 检查链表是否为空
if (link-&gt;next == NULL) {
// 如果链表为空，返回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>
<pre><code class="language-python">class Link:
def max(self):
if self.isempty():
return None
h = self.head
res = h.next.data
while h.next:
res = h.next.data if h.next.data&gt;res else res
h = h.next
return res</code></pre>
<h1>11. 判断某个值在不在链表里</h1>
<pre><code class="language-c">/**
* 检查链表中是否包含指定的数据
*
* @param link 链表的头指针
* @param data 要查找的数据
* @return 如果链表中包含指定的数据返回1，否则返回0
*/
int has(Link* link, EType data) {
// 检查链表是否为空
if (link-&gt;next == NULL) {
// 如果链表为空，返回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>
<pre><code class="language-python">class Link:
def has(self, x):
if self.isempty():
return False
h = self.head
while h.next:
if h.next.data == x:
return True
h = h.next
return False</code></pre>
<h1>12. 获取某个位置的值</h1>
<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>
<pre><code class="language-python">class Link:
def get(self, i):
if self.isempty():
return None
if i&lt;0:
return None
h = self.head
for j in range(i):
if h.next is None:
return None
h = h.next
if h.next:
return h.next.data
else:
return None
</code></pre>