迷宫与栈问题等-数据结构课程设计(15级).docx

1、“数据结构”课程设计-指导书 2014-4-51选题一：迷宫与栈问题【问题描述】以一个 mXn 的长方阵表示迷宫，0 和 1 分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。【实现提示】1) 首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i，j，d）的形式输出。其中：（i，j）指示迷宫中的一个坐标，d 表示走到下一坐标的方向。如，对于下列数据的迷宫，输出一条通路为：（1，1， 1） ， （1，2，2） ， （2 ，2，2 ） ， （3，2，3 ） ， （3，1，2） ，。2) 编写递归形

2、式的算法，求得迷宫中所有可能的通路。3) 以方阵形式输出迷宫及其通路。【测试数据】迷宫的测试数据如下：左上角（0，1 ）为入口，右下角（ 8，9）为出口。8765432100 1 2 3 4 5 6 7 899入口出口0087654321011111111101000000010110100012010010111301011000140000010015011001001601000011170000000018111111119 1 1111111119入口出口“数据结构”课程设计-指导书 2014-4-52选题二：算术表达式与二叉树【问题描述】一个表达式和一棵二叉树之间，存在着自然的对应

3、关系。写一个程序，实现基于二叉树表示的算术表达式的操作。【实现提示】假设算术表达式 Expression 内可以含有变量（ az） 、常量（09 ）和二元运算符（+，-，*，/， (乘幂)） 。实现以下操作：1) ReadExpre(E)以字符序列的形式输入语法正确的前缀表达式并构造表达式 E。2) WriteExpre(E)用带括弧的中缀表达式输出表达式 E。3) Assign(V,c)实现对变量 V 的赋值（V=c） ，变量的初值为 0。4) Value(E)对算术表达式 E 求值。5) CompoundExpr（P，E1， E2）-构造一个新的复合表达式（ E1）P（E2）【测试数据】1

4、) 分别输入 0；a；-91；+a*bc；+*5x2*8x；+*3x3*2x2x6 并输出。2) 每当输入一个表达式后，对其中的变量赋值，然后对表达式求值。“数据结构”课程设计-指导书 2014-4-53选题三：银行业务模拟与离散事件模拟【问题描述】假设某银行有 4 个窗口对外接待客户，从早晨银行开门（开门 9：00am ，关门5： 00pm）起不断有客户进入银行。由于每个窗口在某个时刻只能接待一个客户，因此在客户人数众多时需要在每个窗口前顺次排队，对于刚进入银行的客户（建议：客户进入时间使用随机函数产生） ，如果某个窗口的业务员正空闲，则可上前办理业务；反之，若 4 个窗口均有窗户所占，他便

5、会排在人数最少的队伍后面。【实现提示】1) 编制一个程序以模拟银行的这种业务活动并计算一天中客户在银行逗留的平均时间。2) 建议有如下设置：a) 客户到达时间随机产生，一天客户的人数设定为 100 人。b) 银行业务员处理时间随机产生，平均处理时间 10 分钟。3) 将一天的数据（包括业务员和客户）以文件方式输出。【测试数据】由随机数产生器生成“数据结构”课程设计-指导书 2014-4-54选题四：文学研究助手与模式匹配算法 KMP【问题描述】文学研究人员需要统计某篇英文小说中某些形容词的出现次数和位置。试写一个实现这一目标的文字统计系统【实现提示】1) 英文小说存于一个文本文件中。待统计的词

6、汇集合要一次输入完毕，即统计工作必须在程序的一次运行之后就全部完成。程序的输出结果是每个词的出现次数和出现位置所在的行的行号，格式自行设计。待统计的“单词”在文本串中不跨行出现，它或者从行首开始，或者前置以一个空格符。2) 模式匹配要基于 KMP 算法。3) 推广到更一般的模式集匹配问题，并设待查模式串可以跨行（提示：定义操作GetAChar） 。【测试数据】1) 文本文件为 testword.c2) 待统计的词集：if、else 、 for、while、return、void、int、char、typedef、struct“数据结构”课程设计-指导书 2014-4-55选题五：琼州学院校园导

7、游咨询与最短路径【问题描述】1) 从琼州学院的平面图中选取有代表性景点（10-15 个） ，抽象成一个无向带权图。以图中顶点表示景点，边上的权值表示两地之间距离。2) 本程序的目的是为用户提供路径咨询。根据用户指定的始点和终点输出相应路径，或者根据用户指定的景点输出景点的信息。【实现提示】1) 从琼州学院的平面图中选取有代表性景点（10-15 个） ，抽象成一个无向带权图。以图中顶点表示校内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等信息。2) 为来访客人提供图中任意景点相关信息的查询。3) 为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路

8、径。4) 区分汽车线路与步行线路。【测试数据】琼州学院导游图（距离可估计） 。“数据结构”课程设计-指导书 2014-4-56选题六：设计一个计算机管理系统完成图书管理基本业务 【实现提示】 1)每种书的登记内容包括书号、书名、著作者、现存量和库存量； 2)对书号建立索引表（线性表）以提高查找效率（索引表采用树表）； 3)系统主要功能如下： *采编入库：新购一种书，确定书号后，登记到图书帐目表中，如果表中已有，则只将库存量增加； *借阅：如果一种书的现存量大于 0，则借出一本，登记借阅者的书证号和归还期限，改变现存量； *归还：注销对借阅者的登记，改变该书的现存量。“数据结构”课程设计-指导书

9、 2014-4-57选题七：哈夫曼 (Huffman)编/译码器【问题描述】利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原） 。对于双工信道（即可以双向传输信息的信道） ，每端都需要一个完整的编/ 译码系统。试为这样的信息收发站写一个哈夫曼码的编/译码系统。【实现提示】一个完整的系统应具有以下功能：1) I：初始化（ Initialization） 。从终端读入字符集大小 n，以及 n 个字符和 n 个权值，建立哈夫曼树，并将它存于文件 hfmTree 中。2) E：编码（

10、Encoding ） 。利用以建好的哈夫曼树（如不在内存，则从文件 hfmTree中读入） ，对文件 ToBeTran 中的正文进行编码，然后将结果存入文件 CodeFile 中。3) D：译码（Decoding） 。利用已建好的哈夫曼树将文件 CodeFile 中的代码进行译码，结果存入文件 TextFile 中。4) P：印代码文件（ Print） 。将文件 CodeFile 以紧凑格式显示在终端上，每行 50 个代码。同时将此字符形式的编码文件写入文件 CodePrin 中。5) T：印哈夫曼树（ Tree Printing） 。将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在

11、终端上，同时将此字符形式的哈夫曼树写入文件 TreePrint 中。【测试数据】1) 利用教科书例 6-2（严蔚敏数据结构P148）中的数据调试程序。2) 用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码：“THIS PROGRAM IS MY FAVORITE”。字符 空格 A B C D E F G H I J K L M频度 186 64 13 22 32 103 21 15 47 57 1 5 32 20字符 N O P Q R S T U V W X Y Z 频度 57 63 15 1 48 51 80 23 8 18 1 16 1 “数据结构”课程设计

12、-指导书 2014-4-58选题八：内部排序算法比较【问题描述】在教科书中，各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。试通过随机数据比较各种算法的关键字比较次数和关键字移动次数，以取得直观感受。【实现提示】1) 对以下 7 种常用的内部排序算法进行比较：冒泡排序、直接插入排序、简单选择排序、希尔排序、堆排序、归并排序、快速排序。2) 待排序表的表长不小于 100；其中的数据要用伪随机数程序产生；至少要用 5 组不同的输入数据作比较；比较的指标为有关键字参加的比较次数和关键字的移动次数（关键字交换计为 3 次移动） 。3) 最后要对结果作出简单分析，包括对各组

13、数据得出结果波动大小的解释。【测试数据】由随机数产生器生成“数据结构”课程设计-指导书 2014-4-59选题九：简单行编辑程序【问题描述】文本编辑器程序是利用计算机进行文字加工的基本软件工具，实现对文本文件的插入、删除等修改操作。限制这些操作以行为单位进行的编辑程序称为行编辑程序。被编辑的文本文件可能很大，全部读入编辑程序的数据空间（内存）的作法既不经济，也不总能实现。一种解决办法是逐段地编辑。任何时刻只把待编辑文件的一段放在内存，利为活区。试按照这种方法实现一个简单的行编辑程序。设文件每行不超过 320 个字符，很少超过 80 个字符。【实现提示】实现以下 4 条基本编辑命令：1) 行插入

14、：格式：i 将插入活区中第行之后。2) 行删除。格式：d 删除活区中第(到第 行) 。例如“d10 ”和“d10 14”3) 活区切换。格式：n 将活区写入输出文件，并从输入文件中读入下一段，作为新的活区。4) 活区显示。模式：p 逐页地（每页 20 行）显示活区内容，每显示一页之后请用户决定是继续显示以后各页（如果存在） 。印出的每一行要前置行号和一个空格符，行号固定占4 位，增量为 1。各条命令中的行号均须在活区中各行行号范围之内，只有插入命令的行号可以等于活区第一行行号减 1，表示插入当前屏幕中第一行之前，否则命令参数非法。【测试数据】自行设定，注意测试将活区删空等特殊情况。“数据结构”课程设计-指导书 2014-4-510选题十：一元多项式计算【问题描述】1.能够按照指数降序排列建立并输出多项式；2.能够完成两个多项式的相加、相减，并将结果输入；【实现提示】1.存储结构;2.多项式相加的基本过程的算法（可以使用程序流程图）3.可以提出算法的改进方法；【测试数据】自行设定，注意边界等特殊情况。