资源描述：
《数据结构课程设计题目及说明》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、目录1一元稀疏多项式计算器22迷宫问题23哈夫曼编/译码器34教学计划编制问题45成绩分析问题56二叉排序树与平衡二叉树的实现67图的基本操作与实现68全国交通咨询模拟69内部排序算法的性能分析710背包问题的求解711简单个人书管理系统的设计与实现812简易电子表格的设计813停车厂模拟管理程序的设计与实现914农夫过河问题的求解915电话号码查询系统1016航班订票系统1117哈夫曼编码的实现1118最小生成树问题1119算术表达式求值1120综合排序算法的比较1221散列法的试验研究12题目难易程度及选题说明：–第一类(最简单类)
2、：5、11、13、15、19、21共6题，限选0~1题–第二类(较简单类):2、10、14、16、18、20共6题。限选1题–第三类(较难类):1、3、4、7、17共5题。限选1题及以上–第四类(最难类):6、8、9、12共4题。不限121一元稀疏多项式计算器[问题描述]设计一个一元稀疏多项式简单计算器。[基本要求]一元稀疏多项式简单计算器的基本功能是：（1）输入并建立多项式；（2）输出多项式，输出形式为整数序列：n,c1,e1,c2,e2,,,,,,,cn,en,其中n是多项式的项数，ci,ei,分别是第i项的系数和指数，序列按指数降
3、序排序；（3）多项式a和b相加，建立多项式a+b；（4）多项式a和b相减，建立多项式a-b；（5）计算多项式在x处的值。（6）计算器的仿真界面。（选做）[测试数据](1)(2x+5x8-3.1x11)+(7-5x8+11x9)=(-3.1x11+11x9+2x+7)(2)(6x-3-x+4.4x2-1.2x9)-(-6x-3+5.4x2-x2+7.8x15)=(-7.8x15-1.2x9-x+12x-3)(3)(1+x+x2+x3+x4+x5)+(-x3-x4)=(x5+x2+x+1)(4)(x+x3)+(-x-x3)=0(5)(x+x
4、2+x3)+0=(x3+x2+x)[实现提示]用带表头结点的单链表存储多项式，多项式的项数存放在头结点中。2迷宫问题[问题描述]以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。[基本要求]（1）实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i,j,d）的形式输出，其中：（i,j）指示迷宫中的一个坐标，d表示走到下一坐标的方向。（2）编写递归形式的算法，求得迷宫中所有可能的通路；（3）以方阵形式输出迷
5、宫及其通路。（选做）[测试数据]迷宫的测试数据如下：左上角（1，1）为入口，右下角（9，8）为出口。1234567800100010001000100000110101110010000100000100010112011110011100010111000000[实现提示]计算机解迷宫通常用的是“穷举求解”方法，即从入口出发，顺着某一个方向进行探索，若能走通，则继续往前进；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，则所设定的迷宫没有通路。可以二维数组存储迷宫数据，通常设
6、定入口点的下标为（1，1），出口点的下标为（m,n）。为处理方便起见，可在迷宫的四周加一圈障碍。对于迷宫中任一位置，均可约定有东、南、西、北四个方向可通。3哈夫曼编/译码器[问题描述]利用哈夫曼编码进行信息通讯可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码；在接收端将传来的数据进行译码(复原)。对于双工信道(即可以双向传输信息的信道)，每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼码的编译码系统。[基本要求]一个完整的系统应具有以下功能：(l)I:初始化
7、(Initialization)。从终端读入字符集大小n，及n个字符和m个权值，建立哈夫曼树，并将它存于文件hfmtree中。(2)C:编码(Coding)。利用已建好的哈夫曼树(如不在内存，则从文件hfmtree中读入)，对文件tobetrans中的正文进行编码，然后将结果存入文件codefile中。(3)D:解码(Decoding)。利用已建好的哈夫曼树将文件codefile中的代码进行译码，结果存入文件textfile中。(4)P:打印代码文件(Print)。将文件codefile以紧凑格式显示在终端上，每行50个代码。同时将此字
8、符形式的编码文件写入文件codeprint中。(5)T:打印哈夫曼树(Treeprinting)。将已在内存中的哈夫曼树以直观的方式(树或凹入表形式)显示在终端上，同时将此字符形式的哈夫曼树写入文件tree
