数据结构与C语言综合训练实习
94 长整数的加减计算 95 迷宫的生成与路由 1. 低于100Km收费20.00元 2. 100Km以外的路程枚Km收费0.15元 ④ 汽车根据行驶的路程定期进行维护。 ⑤ 还需实现辅助操作：汽车查询，打印全部信息，计算并打印收入、成本及收益。 ⑥ 管理系统应有完整地界面（最好是图形化界面）。 (4) 实现提示 主要集中在链表的基本操作上。 (1) 问题描述 设计数据结构完成长整数的表示和存储，并编写算法来实现两长整数的加、减等基本代数运算。 (2) 课程设计目的 能够应用线性数据结构解决实际问题。 (3) 基本要求 ① 长整数长度在一百位以上。 ② 实现两长整数在同余代数下的加、减操作。 即实现算法来求解a+b mod n, a-b mod n。 ③ 输入输出均在文件中。 ④ 分析算法的时空复杂性。 (4) 实现提示 需将长整数的加法转化为多个一般整数加法的组合。 (1) 问题描述 设计算法生成一个N×M(N行M列)的迷宫，并完成迷宫的组织和存储。实现两种不同的迷宫路由算法：广度优先，深度优先算法。并比较(包括理论和实验)三种方法的时空复杂性。 (2) 课程设计目的 理解栈的应用，理解深(广)度优先思想，理解问题的理论和实验分析。 (3) 基本要求 ① N和M是用户可配置的，缺省值为50和50。 26
数据结构与C语言综合训练实习
96 应用堆实现一个优先队列 97 教学计划编制问题 ② 迷宫的入口和出口分别在第0行和第N-1行上，随机选择。 ③ 生成的迷宫要求是连通的。 ④ 实现图形化界面(可用VC++，也可用C语言的图形库)。 ⑤ 三种方法的试验比较应该在多个迷宫实例上(尤其可以选一些特定的迷宫)。 (4) 实现提示 多考虑栈上的运算。 (1) 问题描述 优先队列priority queue是一种可以用于很多场合的数据结构，该结构支持如下几本操作： ?Insert (S, x) – 将元素x插入集合S ?Minimum (S) – 返回S中最小的关键字 ?Extract –Min (S) –删除S中的最小关键字 可设计要求以堆作为辅助结构实现一个优先队列。要将堆结构嵌入到队列结构中，以作为其数据组织的一部分。此处由于要用堆实现队列，所以堆结构的存储表示要求用数组。 (2) 课程设计目的 堆结构的应用，优先队列的构造。 (3) 基本要求 ① 给出优先队列的ADT描述，包括队列的逻辑结构及其上基本操作。 ② 以堆结构为辅助结构实现优先队列的存储表示并实现其上的基本操作。 ③ 应用优先队列的ADT实现根据学生成绩对学生信息进行排序输出。 ④ 学生信息存放在文本文件中（格式自定，内容自行输入）。 (4) 实现提示 出队、入队需考虑优先性。 (1) 问题描述 针对西北农林科技大学信息学院本科课程，依据其相互依赖关系制定课程安排计划， 并要求各学期课程数目大致相同且搭配适当。 (2) 课程设计目的 27
数据结构与C语言综合训练实习
98 99 100 掌握图上的基本算法，以及集合的划分。 (3) 基本要求 ① 求解上图的拓扑排序结果。 ② 上述课程在4学期上完，要求每学期上课的门数大致一样。 ③ 每学期的课程应尽量搭配适当，即在每学期内同一系列的课程不要太多。 (4) 实现提示 在拓扑排序基础上作适当修改。 (1) 问题描述 构造集合结构的抽象数据型，并在此基础上进行集合的等价划分。 (2) 课程设计目的 掌握集合的表示方法，并设计等价划分算法。 (3) 基本要求 ① 选择合理的结构完成集合的表示(要求以ADT的形式给出)。 集合的等价划分 ② 在进行等价划分前，等价关系需用户输入(从文件输入，格式自定)。 ③ 需要验证用户输入的关系是否为等价关系。 ④ 对集合进行等价划分，且要分析该划分的时空复杂性。 (4) 实现提示 可用树结构来表示集合，如果能进行适当的优化并给出理由和实验分析结果将更好。 问题描述：利用哈夫曼编码，实现符号文本的压缩和解压缩。基本要求：对于给定的符号文本，可以根据其频度进行哈夫曼编码，并能输出对应的哈夫曼树和哈夫曼编码；实现哈夫曼符号文本压缩 解码。提高要求：(1)能够分析文件，统计文件中出现的字符，统计字符出现的概率，再对文件进行编码，实现文件的压缩和解压缩。(2)能够对于文件的压缩比例进行统计。 (1) 问题描述 设计并建立一个链式存储分配系统来表示和操作多项式。为了避免对零和非零多项式进多项式链式存储结构及其行不同的处理，使用带头结点的循环链表。为了充分利用多项式中不再使用的结点，维护一 个可用空间表avail,把不再使用的多项式的结点链入其中。当需要一个新结点时，就查看这代数运算 个单链表avail。如果表非空，那么可以使用它的一个结点。只有当该表为空时，才使用动态存储分配来创建新结点。 28
数据结构与C语言综合训练实习
101 （2）设计目的 掌握循环链表的存储结构及其操作；能够运用循环链表的存储结构表示多项式，并进行代数运算。 (3) 基本要求 设计多项式的存储结构，编写并测试下列函数： a) get_node和ret_node，从/向可用空间表申请和插入一个多项式结点。 b) pread，读取一个多项式，并将其转换成循环存储表示。返回指向该多项式的头结点的指针。 c) pwrite，输出多项式，采用能够清楚显示的形式。 d) padd，计算d = a+b。不改变a和b。 e) psub，计算d = a-b。不改变a和b。 f) pmult，计算d = a*b。不改变a和b。 g) eval，计算多项式在某点a的值，其中a是一个浮点型常量。返回结果为浮点数。 h) perase，把存储表示为循环链表的多项式返还给可用空间表。 （4）实现提示 为了进一步简化加法算法，把多项式的头结点的指数域设为-1 (1) 问题描述 稀疏矩阵的每个结点包含down，right，row，col和value五个域。用单独一个结点表示一个非零项，并将所有结点连接在一起，形成两个循环链表。使得第一个表即行表，把所有结点按照行序（同一行内按列序）用right域链接起来。使得第二个表即列表，把所有结点按照列序（同一列内按行序）用down链接起来。这两个表共用一个头结点。另外，增加一个包含矩阵维数的结点。稀疏矩阵的这种存储表示称为完全链表表式。 稀疏矩阵的完全链表表示实现一个完全链表系统进行稀疏矩阵运算，并分析下列操作函数的计算时间和额外存储 及其运算 空间的开销。 （2）设计目的 认识和掌握稀疏矩阵的完全链表表示；能够建立并运用这种存储结构 (3) 基本要求 建立一个用户友好、菜单式系统进行下列操作，并使用合当的测试数据测试该系统。 （a） 读取一个稀疏矩阵建立其完全链表表示 29
数据结构与C语言综合训练实习
102 “随机漫步”问题 （b） 输出一个稀疏矩阵的内容 （c） 删除一个稀疏矩阵 （d） 两个稀疏矩阵相加 （e） 两个稀疏矩阵相减 （f） 两个稀疏矩阵相乘 （g） 稀疏矩阵的转置 （4）实现提示 链表上的操作。 (1) 问题描述 有一类问题总称为“随机漫步”（random walk）问题，这类问题长久以来吸引着数学界的兴趣。所有这些问题即使是最简单的解决起来也是极其困难的。而且它们在很大程度上还远没有得到解决。一个这样的问题可以描述为： 在矩形的房间里，铺有n×m块瓷砖，现将一只（醉酒的）蟑螂放在地板中间一个指定方格里。蟑螂随机地从一块瓷砖“漫步”到另一块瓷砖（可能是在找一片阿司匹林）。假设它可能从其所在的瓷砖移动到其周围八块瓷砖中的任何一个（除非碰到墙壁），那么它把每一块瓷砖都至少接触一次将花费多长时间？ 虽然这个问题可能很难用纯粹的概率技术来解决，但是使用计算机的话却十分容易。使用计算机解决此问题的技术称为“模拟”。这种技术广泛应用于工业中，用来预测运输流量，存货控制等等。该问题可采用如下方法进行模拟： 用一个n×m数组作为计数器来表示蟑螂到达每一块瓷砖的次数，每个数组单元的初始值均置为零。蟑螂在地板上的位置用坐标（ibug，jbug）表示。蟑螂的八种可能移动用在位置(ibug + imove[k]，jbug + jmove[k])的瓷砖表示，其中0≤k≤7，并且 imove[0] = -1 jmove[0] = 1 imove[1] = 0 jmove[1] = 1 imove[2] = 1 jmove[2] = 1 imove[3] = 1 jmove[3] = 0 imove[4] = 1 jmove[4] = -1 imove[5] = 0 jmove[5] = -1 imove[6] = -1 jmove[6] = -1 30