admin管理员组文章数量:1794759
2024重生之回溯数据结构与算法系列学习（8）【无论是王道考研人还是IKUN都能包会的；不然别给我家鸽鸽丢脸好嘛？】
上节回顾
前节回顾
王道第2.3章节之线性表精题汇总四
（6）题目：试编写算法将带头节点的单链表Q就地逆置，所谓“就地”是指辅助空间复杂度为0(1)。
解题思路：
代码语言：javascript代码运行次数：0运行复制链表节点结构体 (LNode):
data 用于存储节点的数据。
next 是一个指针，用于指向下一个节点。
头插法 (HeadInsert):
通过不断读取输入，将新节点插入到链表的头部。
使用 L->next 来维护链表的结构。
尾插法 (TailInsert):
持续读取输入，将新节点追加到链表末尾。
r 用于跟踪当前尾部节点，更新尾部指针。
打印函数 (Print):
遍历链表，从头节点开始输出每个节点的数据。
反转链表 (fn):
将链表中的节点顺序反转。
使用三个指针：p 用于当前节点，r 用于暂存下一个节点，L->next 用于构建反转后的链表。
主函数 (main):
创建链表头节点，调用 TailInsert 进行数据插入，然后调用 fn 反转链表，最后输出反转后的链表。实现代码：
代码语言：javascript代码运行次数：0运行复制#include <iostream>
using namespace std;
// 定义链表节点结构体
typedef struct LNode
{
int data; // 节点数据
struct LNode *next; // 指向下一个节点的指针
} LNode, *LinkList;
// 头插法
void HeadInsert(LinkList &L)
{
int val = 0; // 存储输入的值
while (cin >> val) // 持续接受输入
{
LNode *s = new LNode; // 创建新的节点
s->data = val; // 将输入值赋给节点数据
s->next = L->next; // 新节点指向当前链表的第一个节点
L->next = s; // 更新头指针，指向新节点
// 判断是否为输入结束
if (cin.get() == '\n')
{
break; // 如果遇到换行，结束输入
}
}
}
// 尾插法
void TailInsert(LinkList &L)
{
int val = 0; // 存储输入的值
LNode *r = L; // r指向尾部节点
while (cin >> val) // 持续接受输入
{
LNode *s = new LNode; // 创建新的节点
s->data = val; // 将输入值赋给节点数据
r->next = s; // 尾节点的next指向新节点
r = s; // r更新为新节点
r->next = NULL; // 新节点的next指向NULL
// 判断是否为输入结束
if (cin.get() == '\n')
{
break; // 如果遇到换行，结束输入
}
}
}
// 遍历输出链表元素
void Print(LinkList L)
{
LNode *p = L->next; // 从头节点的下一个节点开始遍历
while (p)
{
cout << p->data << '\t'; // 输出节点数据
p = p->next; // 移动到下一个节点
}
cout << endl; // 输出换行
}
// 反转链表
void fn(LinkList &L)
{
LNode *p, *r;
p = L->next; // 从链表的第一个节点开始
L->next = NULL; // 清空链表
// 反转链表
while (p)
{
r = p->next; // 暂存当前节点的下一个节点
p->next = L->next; // 当前节点的next指向新的头节点
L->next = p; // 更新链表头，指向当前节点
p = r; // 移动到下一个节点
}
}
int main()
{
LinkList L = new LNode; // 创建链表头节点
TailInsert(L); // 调用尾插法插入数据
fn(L); // 反转链表
Print(L); // 打印链表
}
（7）题目：设在一个带表头节点的 单链表Q中所有元素节点的数据值无序，试编写一个函数，删除表中所有介于给定的两个值(作为函数参数给出)之间的元素的元素(若存在) 。
解题思路：
代码语言：javascript代码运行次数：0运行复制>定义工作指针p、前驱指针q
>遍历链表删除节点
链表节点结构体 (LNode):
data：用于存储节点的数据。
next：指向下一个节点的指针。
头插法 (HeadInsert):
通过不断读取输入，将新节点插入到链表的头部。
使用 L->next 来维护链表的结构。
尾插法 (TailInsert):
持续读取输入，将新节点追加到链表末尾。
r 用于跟踪当前尾部节点，更新尾部指针。
打印函数 (Print):
遍历链表，从头节点开始输出每个节点的数据。
删除指定范围内的节点 (DelValue):
该函数用于删除链表中数据值在 left 和 right 之间的所有节点。
使用两个指针 p 和 pre 来维护当前节点和前驱节点，判断并删除符合条件的节点。
主函数 (main):实现代码：
代码语言：javascript代码运行次数：0运行复制#include <iostream>
using namespace std;
// 定义链表节点结构体
typedef struct LNode
{
int data; // 节点数据
struct LNode *next; // 指向下一个节点的指针
} LNode, *LinkList;
// 头插法函数
void HeadInsert(LinkList &L)
{
int val = 0; // 存储输入的值
while (cin >> val) // 持续接受输入
{
LNode *s = new LNode; // 创建新的节点
s->data = val; // 将输入值赋给节点数据
s->next = L->next; // 新节点指向当前链表的第一个节点
L->next = s; // 更新头指针，指向新节点
// 判断是否为输入结束
if (cin.get() == '\n')
{
break; // 如果遇到换行，结束输入
}
}
}
// 尾插法函数
void TailInsert(LinkList &L)
{
int val = 0; // 存储输入的值
LNode *r = L; // r指向尾部节点
while (cin >> val) // 持续接受输入
{
LNode *s = new LNode; // 创建新的节点
s->data = val; // 将输入值赋给节点数据
r->next = s; // 尾节点的next指向新节点
r = s; // r更新为新节点
r->next = NULL; // 新节点的next指向NULL
// 判断是否为输入结束
if (cin.get() == '\n')
{
break; // 如果遇到换行，结束输入
}
}
}
// 遍历输出链表元素
void Print(LinkList L)
{
LNode *p = L->next; // 从头节点的下一个节点开始遍历
while (p)
{
cout << p->data << '\t'; // 输出节点数据
p = p->next; // 移动到下一个节点
}
cout << endl; // 输出换行
}
// 删除指定范围内的节点
void DelValue(LinkList &L, int left, int right)
{
LNode *p, *pre; // p用于当前节点，pre用于前驱节点
p = L->next; // 从链表的第一个节点开始
pre = L; // pre初始化为头节点
while (p) // 当当前节点不为空时循环
{
// 检查节点数据是否在指定范围内
if (p->data > left && p->data < right)
{
LNode *q = p; // 暂存待删除节点
p = p->next; // 移动到下一个节点
pre->next = p; // 前驱节点的next指向当前节点的下一个节点
delete q; // 删除旧节点，释放内存
}
else // 若不在指定范围内
{
pre = p; // 更新前驱节点
p = p->next; // 移动到下一个节点
}
}
}
int main()
{
LinkList L = new LNode; // 创建链表头节点
TailInsert(L); // 调用尾插法插入数据
DelValue(L, 3, 5); // 删除数据在3和5之间的节点
Print(L); // 打印链表
}
（8）题目：给定两个单链表Q，编写算法找出两个链表的公共结点。
解题思路：
代码语言：javascript代码运行次数：0运行复制>公共结点之后的所有结点地址均一致
>所以只需要比较结点即可
>但是需要二者从同一倒数长度开始
>所以长的链表需要先向后偏移链表长度之差
链表结构: 使用 LNode 结构体定义链表节点，包括数据和指向下一个节点的指针。
链表操作:
HeadInsert: 使用头插法插入数据。
TailInsert: 使用尾插法插入数据。
Print: 输出链表中所有节点的数据。
PublicNode: 查找两个链表的公共节点，并输出该节点的数据。
主函数: 创建两个链表，构建公共节点，并调用 PublicNode 函数查找和打印公共节点的数据。实现代码：
代码语言：javascript代码运行次数：0运行复制#include <iostream>
using namespace std;
// 定义链表节点结构体
typedef struct LNode
{
int data; // 节点数据
struct LNode *next; // 指向下一个节点的指针
} LNode, *LinkList;
// 头插法创建链表
void HeadInsert(LinkList &L)
{
int val = 0;
// 从输入中读取值，直到遇到换行符
while (cin >> val)
{
LNode *s = new LNode; // 创建新节点
s->data = val; // 设置节点数据
s->next = L->next; // 新节点指向当前链表的第一个节点
L->next = s; // 更新头节点的指针指向新节点
// 检测是否为换行符
if (cin.get() == '\n')
{
break;
}
}
}
// 尾插法创建链表
void TailInsert(LinkList &L)
{
int val = 0;
LNode *r = L; // r指向当前链表的最后一个节点
while (cin >> val)
{
LNode *s = new LNode; // 创建新节点
s->data = val; // 设置节点数据
r->next = s; // 将当前节点的next指向新节点
r = s; // 更新r指向新节点
r->next = NULL; // 新节点的next为NULL
// 检测是否为换行符
if (cin.get() == '\n')
{
break;
}
}
}
// 遍历输出链表元素
void Print(LinkList L)
{
LNode *p = L->next; // p指向链表的第一个节点
while (p)
{
cout << p->data << '\t'; // 输出节点数据
p = p->next; // 移动到下一个节点
}
cout << endl;
}
// 查找两个链表的公共节点
void PublicNode(LinkList &LA, LinkList &LB)
{
int lena = 0, lenb = 0;
LNode *p = LA->next;
// 计算链表A的长度
while (p)
{
lena++;
p = p->next;
}
p = LB->next;
// 计算链表B的长度
while (p)
{
lenb++;
p = p->next;
}
LNode *longList, *shortList;
int dist = 0;
// 确定较长和较短的链表
if (lena > lenb)
{
longList = LA->next; // 链表A较长
shortList = LB->next; // 链表B较短
dist = lena - lenb; // 计算长度差
}
else
{
longList = LB->next; // 链表B较长
shortList = LA->next; // 链表A较短
dist = lenb - lena; // 计算长度差
}
// 移动较长链表的指针，使其与较短链表对齐
while (dist--)
{
longList = longList->next;
}
// 同时遍历两个链表，寻找公共节点
while (longList != NULL)
{
if (longList == shortList) // 找到公共节点
{
cout << longList->data; // 输出公共节点数据
return;
}
else
{
longList = longList->next; // 移动到下一个节点
shortList = shortList->next;
}
}
}
int main()
{
LNode *p1 = new LNode; // 创建链表A的头结点
LNode *q1 = new LNode; // 创建链表B的头结点
LNode *q2 = new LNode; // 链表B的节点
LNode *q3 = new LNode; // 链表B的节点
// 公共结点
LNode *m1 = new LNode;
m1->data = 99999; // 公共节点的数据
LNode *m2 = new LNode; // 公共节点的下一个节点
m1->next = m2; // 设置公共节点的下一个节点
m2->next = NULL; // 公共节点的下一节点指向NULL
p1->next = m1; // 链表A连接公共节点
// 构建链表B
q1->next = q2; // q1指向q2
q2->next = q3; // q2指向q3
q3->next = m1; // q3指向公共节点m1
// 查找并输出公共节点
PublicNode(p1, q1);
}（9）题目：给定一个带表头结点的单链表，设head为头指针，结点结构为（data，next），data为整型元素，next为指针，试写出算法：按递增次序输出单链表中各节点的数据元素，并释放结点所占的存储空间(要求:不允许使用数组作为辅助空间)。
解题思路：
代码语言：javascript代码运行次数：0运行复制>遍历链表找到最小值将其输入
>然后将其删除，重复该过程
>直到表为空
链表结构: 使用 LNode 结构体定义链表节点，包括数据和指向下一个节点的指针。
链表操作:
HeadInsert: 头插法创建链表（未在 main 中调用）。
TailInsert: 尾插法创建链表，从标准输入读取整数，直到遇到换行符。
Print: 遍历链表，输出所有节点的数据（未在 main 中调用）。
PrintValue: 遍历链表，找到并输出每次遍历中的最小值，并删除该节点。
主函数: 创建一个链表，调用 TailInsert 函数添加数据，然后调用 PrintValue 函数输出并删除链表中的最小值。实现代码：
代码语言：javascript代码运行次数：0运行复制#include <iostream>
using namespace std;
// 定义链表节点结构体
typedef struct LNode
{
int data; // 节点数据
struct LNode *next; // 指向下一个节点的指针
} LNode, *LinkList;
// 头插法创建链表
void HeadInsert(LinkList &L)
{
int val = 0;
// 从输入中读取值，直到遇到换行符
while (cin >> val)
{
LNode *s = new LNode; // 创建新节点
s->data = val; // 设置节点数据
s->next = L->next; // 新节点指向当前链表的第一个节点
L->next = s; // 更新头节点的指针指向新节点
// 检测是否为换行符
if (cin.get() == '\n')
{
break;
}
}
}
// 尾插法创建链表
void TailInsert(LinkList &L)
{
int val = 0;
LNode *r = L; // r指向当前链表的最后一个节点
while (cin >> val)
{
LNode *s = new LNode; // 创建新节点
s->data = val; // 设置节点数据
r->next = s; // 将当前节点的next指向新节点
r = s; // 更新r指向新节点
r->next = NULL; // 新节点的next为NULL
// 检测是否为换行符
if (cin.get() == '\n')
{
break;
}
}
}
// 遍历输出链表元素
void Print(LinkList L)
{
LNode *p = L->next; // p指向链表的第一个节点
while (p)
{
cout << p->data << '\t'; // 输出节点数据
p = p->next; // 移动到下一个节点
}
cout << endl;
}
// 输出链表中的最小值并删除
void PrintValue(LinkList &L)
{
LNode *p, *pre;
LNode *minP, *minPre;
// 当链表还有节点时循环
while (L->next)
{
p = L->next; // 从第一个节点开始
pre = L; // pre指向当前节点的前驱
minP = L->next; // 初始最小节点为第一个节点
minPre = L; // 最小节点的前驱为头节点
// 遍历链表查找最小值节点
while (p)
{
if (p->data < minP->data) // 找到更小的值
{
minP = p; // 更新最小节点
minPre = pre; // 更新最小节点前驱
}
pre = p; // 移动前驱指针
p = p->next; // 移动当前指针
}
// 输出最小值
cout << minP->data << '\t';
// 删除最小值节点
LNode *q = minP; // 临时保存最小节点
minPre->next = minP->next; // 更新前驱节点的next指针
delete q; // 删除最小节点
}
}
int main()
{
LinkList L = new LNode; // 创建链表的头结点
TailInsert(L); // 调用尾插法插入数据
PrintValue(L); // 打印链表中的最小值并删除
}
（10）题目：将一个带头节点的单链表QA分解为两个带头节点的单链表A和B,使得A表中含有原表中序号为奇数的元素，而B表中含有原表中序号为偶数的元素，且保持其相对顺序不变。
解题思路：
代码语言：javascript代码运行次数：0运行复制>定义位置变量，用于指示节点序号
>然后定义两个尾指针，分别判断节点序号奇偶
>使用尾插法进行插入
链表结构: 使用 LNode 结构体定义链表节点，包括数据和指向下一个节点的指针。
链表操作:
HeadInsert: 头插法创建链表（未在 main 中调用）。
TailInsert: 尾插法创建链表，从标准输入读取整数，直到遇到换行符。
Print: 遍历链表，输出所有节点的数据。
BreakList: 将原链表中的节点分成两个链表，奇数位置的节点放入链表 LA，偶数位置的节点放入链表 LB。
主函数:
创建两个链表 LA 和 LB 的头节点。
调用 TailInsert 函数添加数据到链表 LA。
调用 BreakList 函数将链表 LA 分割成两个链表 LA 和 LB。
打印两个链表的内容。实现代码：
代码语言：javascript代码运行次数：0运行复制#include <iostream>
using namespace std;
// 定义链表节点结构体
typedef struct LNode
{
int data; // 节点数据
struct LNode *next; // 指向下一个节点的指针
} LNode, *LinkList;
// 头插法创建链表
void HeadInsert(LinkList &L)
{
int val = 0;
while (cin >> val) // 从标准输入读取值
{
LNode *s = new LNode; // 创建新节点
s->data = val; // 设置节点数据
s->next = L->next; // 新节点指向当前链表的第一个节点
L->next = s; // 更新头节点的指针指向新节点
// 检测是否为换行符
if (cin.get() == '\n')
{
break; // 遇到换行符结束输入
}
}
}
// 尾插法创建链表
void TailInsert(LinkList &L)
{
int val = 0;
LNode *r = L; // r指向链表的最后一个节点
while (cin >> val) // 从标准输入读取值
{
LNode *s = new LNode; // 创建新节点
s->data = val; // 设置节点数据
r->next = s; // 将当前节点的next指向新节点
r = s; // 更新r指向新节点
r->next = NULL; // 新节点的next指向NULL
// 检测是否为换行符
if (cin.get() == '\n')
{
break; // 遇到换行符结束输入
}
}
}
// 遍历输出链表元素
void Print(LinkList L)
{
LNode *p = L->next; // p指向链表的第一个节点
while (p) // 当p不为空时
{
cout << p->data << '\t'; // 输出节点数据
p = p->next; // 移动到下一个节点
}
cout << endl; // 输出换行
}
// 将链表分成两个链表，奇数节点进入LA，偶数节点进入LB
void BreakList(LinkList &LA, LinkList &LB)
{
int i = 1; // 节点计数器
LNode *p, *ra, *rb;
p = LA->next; // 从LA的第一个节点开始
ra = LA; // ra指向LA链表的当前末尾
rb = LB; // rb指向LB链表的当前末尾
ra->next = NULL; // 初始化LA的next为空
rb->next = NULL; // 初始化LB的next为空
// 遍历原链表
while (p)
{
if (i % 2 == 1) // 如果是奇数位置的节点
{
ra->next = p; // 将当前节点链接到LA
ra = p; // 更新ra指向当前节点
}
else // 如果是偶数位置的节点
{
rb->next = p; // 将当前节点链接到LB
rb = p; // 更新rb指向当前节点
}
p = p->next; // 移动到下一个节点
i++; // 计数器加一
}
ra->next = NULL; // 结束LA链表
rb->next = NULL; // 结束LB链表
}
int main()
{
LinkList LA = new LNode; // 创建链表LA的头节点
LinkList LB = new LNode; // 创建链表LB的头节点
TailInsert(LA); // 使用尾插法创建链表LA
BreakList(LA, LB); // 将链表LA分成两个链表LA和LB
Print(LA); // 打印链表LA
Print(LB); // 打印链表LB
}本文标签： 2024重生之回溯数据结构与算法系列学习（8）无论是王道考研人还是IKUN都能包会的不然别给我家鸽鸽丢脸好嘛
版权声明：本文标题：2024重生之回溯数据结构与算法系列学习（8）【无论是王道考研人还是IKUN都能包会的；不然别给我家鸽鸽丢脸好嘛？】 内容由林淑君副主任自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.xiehuijuan.com/baike/1754674638a1705053.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论