【趣学C语言和数据结构100例】
问题描述
在带头结点的单链表中，删除所有值为 x 的结点，并释放其空间，假设值为 x 的结点不唯一，试编写算法以实现上述操作。
试编写在带头结点的单链表中寻找一个最小值结点的高效算法（假设该结点唯一）
设在一个带表头结点的单链表中，所有结点的元素值无序，试编写一个函数，删除表中所有介于给定的两个值（作为函数参数给出）之间的元素（若存在）。
给定两个单链表，试分析找出两个链表的公共结点。（暴力破解，最优解）
设 C={a1, b1, a2, b2, ..., an, bn} 为线性表，采用带头结点的单链表存放，设计一个就地算法将其拆分为两个线性表，使得 A={a1, a2, ..., an}, B={bn, bn-1, ..., b1}。
代码分析
==46.带头结点的单链表删指定值==
//如果带头结点,则已经定义好L的头结点，可以直接使用L，L->next
Lnode *pre=L,*p=L->next
//如果不带头结点,则需要先定义L的结点
L=(Node *) malloc(sizeof (LNode));
L->next=NULL;
分析：无返回值+对链表操作+传入删除值，故函数命名为void 函数命(LiukList &L,int x)，使用while循环，条件为p ！=NULL（不到最后一直遍历），如果p的值为指定的x，则使pre的next和当前的p的next连接，即跳过p，并且释放p，使用free(p)，使p=pre->next;继续，如果p的值不为指定的x，则pre和p都向后移动一位，使用p=p->next
//如果遍历，则while循环，条件为p != NULL
while(p){
}
==47.带头结点的单链表找一个最小值结点==
分析：设置工作指针和存储的最小指针。工作指针：通常为Lnode pre=L,p=L->next，使用while(p)循环遍历，如果当前的工作指针的值<最小指针的值，则继续替换存储，然后继续都向后移动一位。到结束输出最小的值。
==48.带表头结点的单链表删除指定范围的值==
分析：可以参考41，只需要把p的值为指定的x改为范围，其余一样。
==49.两个单链表找公共结点（暴力破解，最优解）==
有两个链表：abcde和fgde,如下图
a->b->c
↘
d->e
↗
f->g
解法1（暴力破解）：
分析返回值为Lnode 类型，则函数名为Lnode 函数名(LiiukList L1,LiiukList L2),分析进入函数后需要访问两个链表的工作指针p和q,初始化为Lnode * p=L1->next;使用while（p）循环遍历，使用while（q）循环继续内部遍历，如果p==q则返回p为公共结点，否则使q->向后移动，内部遍历后，没有找到结果，则外部循环移动，并且内部遍历从头遍历。到最后如果没有找到，则返回为NULL
解法2（最优解）：
//链表的长度
int length=0;
while(p){
lenth++;
p=p->next;
}
分析：计算两个的长度，从他们的相差的位置开始。注意：计算链表的长度后使p和q指向L->next。使长度大的先移动差位。然后使用while遍历访问，此时可以同时移动到他们相等时，即可找到公共结点。到最后如果没有找到，则返回为NULL
解法1（暴力破解）的时间复杂度为O(m*n) //平方级
解法2（最优解）的时间复杂度为O(m+n+min(m,n)) //常量级
==50.链表的拆分==
// 创建链表
LiukList L = (LiukList)malloc(sizeof(LNode));
L->next=NULL;
// 分配链表头结点
LiukList L = new Lnode;
L->next = nullptr;
分析：对A 进行正序，对B进行逆序，即对A 进行尾插，对B进行头插。初始化: 创建一个新的链表 B，并将其头结点 B->next 初始化为 NULL。创建节点ra，p，q(ra指针负责A的，p 指针用于工作，q 指针保存下一个，防断链，B就用B即可)
使用while（p）循环遍历，将第一个赋值给A即ra的下一个（A 的尾部），并更新ra,使p向后移动，如果不为空，则使用q记录p的下一个，防止断链。使p的下一个指向B 的下一个，并且令B 指向p当前的p(B 的头部)，使p=q,即A继续，并且已经移动一位。最后在A的末尾加入NULL。返回B。
代码实现
#include <stdio.h>
#include <cstring>
#include <ctype.h>
#include <math.h>
int main() {
// 46.在带头结点的单链表工中，别除所有值为x的结点，并释放其空间，假设值为x的结点不唯一，试编写算法以实现上述操作。
void Del_x(LiukList &L,int x){
Lnode *pre=L,*p=L->next;
while(p){
if(p->data=x){
pre->next=p->next;
free(p);
p=pre->next;
}
else{
pre=p;
p=p->next;
}
}
}
// 47.试编写在带头结点的单链表工中徐一个最小值结点的高效算法(假设该结点唯一)
void Del_min(LiukList &L){
Lnode *pre=L,*p=L->next; //工作
Lnode *minpre=L,*min=L->next; //最小
while(p){
if(p->data<min->data){
min=p;
minpre=pre;
}
pre=p;
p=p->next;
}
minpre->next=min->next;
free(min);
}
// 48.设在一个带表头结点的单链表中，所有结点的元素值无序，试编写一个函数，删除表中所有介于给定的两个值(作为函数参数给出)之间的元素(若存在)。
void Del_x(LiukList &L,int min,int max){
Lnode *pre=L,*p=L->next;
while(p){
if(p->data<max && p->data<max>min){
pre->next=p->next;
free(p);
p=pre->next;
}
else{
pre=p;
p=p->next;
}
}
}
// 49.给定两个单链表，试分析找出两个链表的公共结点。
// 暴力破解
void * publis_node(LiukList L1,LiukList L2){
Lnode *p=L1->next;
Lnode *q=L2->next;
while(p){
while(q){
if(p==q){
return p;
}
q=p->next;
}
p=p->next;
q=L2->next;
}
return 0;
}
// 最优解
Lnode *func(LiukList L1,LiukList L2){
Lnode *p=L1->next;
Lnode *q=L2->next;
int lenth1=0,lenth2=0;
while(p){
lenth1++;
p=p->next;
}
while(q){
lenth2++;
q=q->next;
}
p=L1->next;
q=L2->next;
int lenth=lenth1-lenth2
if(lenth>0){
while(leath--){
p=p->next
}
}
else{
while(leath--){
q=q->next
}
}
while(p){
if(p==q){
return p;
}
p=p->next;
q=q->next;
}
return 0;
}
// 50.设 C={a1,bi,a2,b...,an,b,}为线性表，采用带头结点的单链表存放，设计一个就地算法将其拆分为两个线性表，使得 A-{a1,a2,….,an}，B={b.,...,b2, bi}。
LiukList splitList(LiukList& A) {
LiukList B = new Lnode; // 分配 B 链表的头结点
B->next = nullptr;
Lnode* p = A;
Lnode* a = A; // A 链表的尾指针
Lnode* b = B; // B 链表的尾指针
while (p->next != NULL) {
// 处理 a 元素
a->next = p->next;
a = a->next;
p = a->next; // 移动到下一个节点
if (p != NULL) {
// 处理 b 元素
b->next = p;
b = b->next;
p = p->next; // 移动到下一个节点
}
}
a->next = NULL; // A 链表结尾置空
b->next = NULL; // B 链表结尾置空
return B;
}
return 0;
}
总结
本文介绍了五个链表操作的问题及其C语言实现，这些问题涉及删除特定值的节点、查找最小值节点、删除指定范围内的节点、查找两个链表的公共节点以及拆分链表。这些算法问题覆盖了链表操作的多个方面，展示了数据结构在解决实际问题中的应用。
删除特定值的节点问题要求我们在带头结点的单链表中删除所有值为x的节点。这个问题的解决关键在于使用两个指针遍历链表，当发现目标节点时，跳过这些节点并释放内存。
查找最小值节点问题要求我们在带头结点的单链表中寻找一个最小值节点。这个问题的解决需要我们使用两个指针分别记录当前节点和最小值节点，遍历链表直到找到最小值。
删除指定范围内的节点问题要求我们在带表头结点的单链表中删除所有介于给定的两个值之间的元素。这个问题的解决可以参考删除特定值的节点问题，只需将条件从单一值变为值的范围。
查找两个链表的公共节点问题要求我们分析找出两个链表的公共节点。这个问题可以通过暴力破解和最优解两种方法解决。暴力破解方法的时间复杂度为O(m*n)，而最优解的时间复杂度为O(m+n+min(m,n))。
拆分链表问题要求我们将一个带头结点的单链表拆分为两个线性表。这个问题的解决需要我们对链表进行遍历，将元素分配到两个新链表中，一个进行正序排列，另一个进行逆序排列。
这些算法的实现不仅展示了C语言在处理链表时的能力，也体现了算法设计的基本思想，如指针操作、条件判断和循环控制。通过这些算法的学习，我们可以更好地理解数据结构和算法的基本概念，提高解决实际问题的能力。
总的来说，这些算法问题不仅锻炼了编程能力，也加深了对数据结构和算法的理解。通过这些问题的解决，我们可以逐步提高自己的编程技能，为将来的学习和工作做好准备。这些算法的掌握对于计算机专业的学生和软件开发人员来说都是非常重要的。通过这些练习，我们可以逐步提高自己的编程技能，为将来的学习和工作做好准备。同时，这些问题的解决也体现了算法在处理链表时的灵活性和效率，为我们在实际开发中遇到类似问题提供了解决思路。
