王道数据结构|王道数据结构 第二章 线性表（3） 编程题下半部分
- 假设有两个元素值按递增次序排列的线性表，均以单链表形式存储，编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。
（考虑到使用递减排列，故使用头插法）
void unionDesc(linkList L1, linkList L2) {
linkList p1 = L1->pNext, p2 = L2->pNext;
linkList temp = nullptr;
L1->pNext = nullptr;
//任选其中一个链表的头部作为头指针
while (p1 && p2) {
if (p1->data <= p2->data) {
temp = p1->pNext;
p1->pNext = L1->pNext;
L1->pNext = p1;
p1 = temp;
//上述为头插的基本操作，需要熟练掌握
}
else {
temp = p2->pNext;
p2->pNext = L1->pNext;
L1->pNext = p2;
p2 = temp;
}
}
if (p1) {
p2 = p1;
}
while (p2) {
temp = p2->pNext;
p2->pNext = L1->pNext;
L1->pNext = p2;
p2 = temp;
}
free(L2);
}
- 设A和B是两个单链表（带头结点），其中元素递增有序，设计一个算法从A和B公共元素中产生单链表C，要求不破坏A,B的结点。
注意要设置变量temp，始终指向新链表的尾部。貌似没啥难度吧。
linkList commonNodeList(linkList L1, linkList L2) {
linkList p1 = L1->pNext, p2 = L2->pNext;
linkList c = (linkList)malloc(sizeof(Node));
linkList temp = c, t;
while (p1 && p2) {
if ( p1->data < p2->data ) {
p1 = p1->pNext;
}
else if (p2->data < p1->data) {
p2 = p2->pNext;
}
else {
t = (linkList)malloc(sizeof(Node));
t->data = https://www.it610.com/article/p1->data;
temp->pNext = t;
temp = temp->pNext;
p1 = p1->pNext;
p2 = p2->pNext;
}
}
temp->pNext = nullptr;
return c;
}
- 已知两个链表A和B分别表示两个集合，元素递增排列，编制函数，求A和B的交集，并存放于A链表中。（这一题和上一题的主要区别是，本题结果保留在原来的链表上，链表的其余部分需要进行释放。）
void intersection(linkList &L1, linkList &L2) {
linkList p1 = L1->pNext, p2 = L2->pNext, temp = L1;
while (p1 && p2) {
if (p1->data =https://www.it610.com/article/= p2->data) {
temp->pNext = p1;
temp = temp->pNext;
linkList tNode = p2;
p1 = p1->pNext;
p2 = p2->pNext;
free(tNode);
//将不用的L2上的结点释放
}
else if (p1->data < p2->data) {
linkList tNode = p1;
p1 = p1->pNext;
free(tNode);
}
else {
linkList tNode = p2;
p2 = p2->pNext;
free(tNode);
}
}
while (p1) {
linkList tNode = p1;
p1 = p1->pNext;
free(tNode);
}
while (p2) {
linkList tNode = p2;
p2 = p2->pNext;
free(tNode);
}
temp->pNext = nullptr;
free(L2);
}
- 两个整数序列，A和B，已经存入两个单链表中，设计算法判断B是否是A的连续子序列。
bool isSubsquence(linkList l1, linkList l2) {
linkList p1 = l1->pNext, p2 = l2->pNext;
while (p1 && p2) {
if (p1->data =https://www.it610.com/article/= p2->data) {
p1 = p1->pNext;
p2 = p2->pNext;
}
else {
p1 = p1->pNext;
p2 = l2->pNext;
}
}
if (p2 == nullptr) return 1;
else return 0;
}
【王道数据结构|王道数据结构 第二章 线性表（3） 编程题下半部分】后面琐碎待补。
推荐阅读
- 《数据结构与算法之美》——队列
- 怪谈清道夫(第二章）
- 空船鱼场（二）
- 笔记|C语言数据结构——二叉树的顺序存储和二叉树的遍历
- Java深入了解数据结构之栈与队列的详解
- Java集合框架|Java集合框架 数据结构
- 数据结构与算法|【算法】力扣第 266场周赛
- 数据结构和算法|LeetCode 的正确使用方式
- 拆书0102+龙小猫+记笔记很难吗（坚持就是王道）
- 第二章|第二章 断了的绳索