Tasks.Data_Structure

数据结构 第二次课堂作业

题目

第二章练习题 16

设有一个双向链表 h ，每个结点中除了有 prior 、 data 和 next 几个域以外，还有一个访问频度数 freq ， 在链表被启用之前，其值均初始化为零。每当进行 LocateNode(h,x) 运算时，令元素值为 x 的结点中 freq 域的值加1， 并调整表中结点的次序，使其按访问频度的递减次序排序，以便使频繁访问的结点总是靠近表头。试写一个符合上述要求的 LocateNode 运算的算法。

第二章练习题 19

用带头结点的单向链表表示整数集合，完成以下运算并分析时间复杂度：

1. 设计一个算法求两个集合 A 和 B 的并集运算，既 C=A∪B ，要求不破坏原有的单向链表 A 和 B 。
2. 假设集合中的元素按递增排序，设计一个高效算法求两个集合 A 和 B 的并集运算，既 C=A∪B ，要求不破坏原有的单向链表 A 和 B 。

第二章练习题 20

用带头结点的单向链表表示整数集合，完成以下运算并分析时间复杂度：

1. 设计一个算法求两个集合 A 和 B 的差集运算，既 C=A-B ，要求算法的空间复杂度为 O(1) ，并释放链表 A 和 B 中不需要的结点。
2. 假设集合中的元素按递增排序，设计一个高效算法求两个集合 A 和 B 的差集运算，既 C=A-B ，要求算法的空间复杂度为 O(1) ，并释放链表 A 和 B 中不需要的结点。

用栈求解迷宫问题

给定一个 M*N 的迷宫图，入口与出口、行走规则。求一条从指定入口到出口的路径。

所求路径必须是简单路径，既路径不重复。

一些测试数据：

1. 11*11 唯一解
2. 21*21 唯一解
3. 21*21 多解
4. 601*601 多解

四则运算计算器

输入一个四则运算中缀表达式，求其后缀表达式与值。

提交

1. 将作业打包为压缩文件，如 zip 格式。
2. 压缩文件命名为你的学号， 如 2018302114514.zip 。
3. 将压缩文件以附件形式发送到邮箱 DS_Task2 # superexercisebook.com
4. 如果一切顺利，你将会收到一个投递成功回执。