[项目006] 链表的综合应用 显示答案 | 返回首页

作者：欧新宇（Xinyu OU）
当前版本：Release v1.0
开发平台：gcc 13.1.0, g++ 13.1.0, gdb 13.2
运行环境：Intel Core i7-13700KF CPU 3.4GHz, 32GB RAM
本教案所涉及的数据及代码仅用于教学和交流使用，请勿用作商用。

最后更新：2023年9月15日

---

作业要求：将【课后作业】的题目及程序代码整理成实验报告，并以PDF格式，或直接拍照上传到【雨课堂】（不要使用word文档进行上传）。

【课后作业】

‍1. 在带头结点的单链表L中，删除所有值为x的结点，并释放其空间，假设值为x的结点不唯一，试编写算法以实现上述操作。

算法提示：
1.定义两个指针p和pre，分别指向工作结点和该节点直接前驱；
2.逐元素扫描链表，当p所指结点的值等于x时，删除该节点，并让p向后移至下一结点；
3.若未找到值为x的结点，则将p和pre同时向后移动一个结点。

void DeleteX(LinkList &L, ElemType x){
    // 在此处填入代码
}

2.有两个循环单链表，链表头指针分别为 h1 和 h2，编写一个函数将链表 h2 连接到链表 h1 之后，要求链接后的链表仍保持循环链表形式。

算法提示：

1. 找到这两个循环链表的尾指针r1和r2；
2. 将第一个链表的尾指针与第二个链表的首元结点相连；同时，将第二个链表的尾指针也与第一个链表的头结点相连。

LinkList Link_TwoLinkList(LinkList &h1, LinkList &h2){
    // 在此处填入代码
}

3. 【2009年统考真题】已知一个带有表头结点的单链表，结点结构为[data|link]。假设该链表只给出了头指针list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点（k为正整数）。若查找成果，算法输出该节点的data域的值，并返回1；否则，只返回0。要求：
1). 描述算法的基本设计思想
2). 描述算法的详细实现步骤
3). 根据设计思想和实现步骤，采用程序设计语言C/C++描述算法，关键之处请给出简要注释。

算法提示：
1.本题的关键是设计一个尽可能高效的算法，因此需要尽量保证算法的复杂度为O(n)，也即只需要进行依次链表扫描；若扫描次数为两次O(2n)，甚至更多 $O(n^2)$，则会被扣分。
2.考虑定义两个指针p和q，p指针先向前走k-1步；之后p和q同时向前走，当p走到链表尾时，q指向的结点即为倒数第k个结点。（注意该算法仅需要扫描一次链表）

int FindLastK(LinkList list, int k){
    // 在此处填入代码
}

4. (选做)[奖励分:0~1] 已知两个非递减序列S1与S2，要求设计一个基于链表的合并算法输出一个新的递减序列S3，该序列不能有重复数据。要求：
1). 描述算法的基本设计思想
2). 描述算法的详细实现步骤
3). 根据设计思想和实现步骤，使用C/C++语言完成该算法的编写，关键之处给出注释。

【扩展练习】

1. 设计一个算法用于判断带头结点的循环双链表是否对称。

算法提示：
1.定义两个方向指针l和r，并让l从左向右扫描，让r从右向左扫描；
2.若l和r所指结点值相等，则继续扫描，否则返回0；若l和r均扫描到表尾，则返回1；
3.若双链表中结点个数为奇数，则l和r均最终将指向中间结点；若为偶数，则l和r最终将相遇但不重合。

int Symmetry(DLinkList L){
    // 在此处填入代码
}

2. 设头指针为L的带有表头结点的非循环双向链表，其每个结点中除有前驱指针pre、数据data和后继指针next外，还有一个访问频度域freq。在链表被启用前，其值均初始化为零。每当在链表中进行一次Locate(L, x)运算时，令元素值为x的结点中freq域的值增1，并使此链表中结点保持按访问频度非增（递减）的顺序排列，同时最近访问的结点排在频度相同的结点前面，以便使频繁访问的结点总是靠近表头。试编写符合上述要求的Locate(L,x)运算的算法，该运算为函数过程，返回找到结点的地址，类型为指针型。

算法提示：
1.本题涉及三个过程，分别是查找、删除和插入；
2.查找：在双向链表中查找值为x的结点；
3.删除：将查找到的值从链表上摘下；
4.插入：从摘除点开始往前进行查找，查找第一个freq比其大的结点，并插入到该结点之后。注意双链表的插入需要执行四件套，被插入结点的前驱和后继都有两个指针需要修改。

DLinkList Locate(DLinkList &L, ElemType &x){
    // 在此处填入代码
}

3. 试编写在带头结点的单链表L中删除一个最小值结点的高效算法，假设最小值结点时唯一的。

算法提示：
1.定义一组指针p和pre用来扫描链表，其中pre为p的直接前驱；
2.定义另一组指针minp和minpre，用于保存值最小的结点和其直接前驱；
3.从左往右扫描链表，并比较当前扫描结点p和minp的值，若minp<p，则将minp指向p所在的位置，minpre指向p的直接前驱；
4.待整个链表扫描完成后，将minp指向的结点删除即可。

LinkList DeleteMin(LinkList &L){
    // 在此处填入代码
}

4. 将一个带头结点的单链表A分解为两个带头结点的单链表A和B，使得A表中含有原表中序号为奇数的元素，而B表中含有原表中序号为偶数的元素，且保持其相对顺序不变。

算法提示：

1. 定义一个flag变量来计算被访问过的结点数
2. 当flag为奇数时，将结点插入A表，否则插入B表

LinkList SeparateList(LinkList &L){
    // 在此处填入代码
}