经典：数据结构课程设计

1、软件工程专业数据结构课程设计软件工程专业数据结构课程设计成都理工大学 信息科学与技术学院12021/8/61. 从指定的题目中任选一题，独立完成，不得自行设计指定题目外的其它题目，不得抄袭。2. 成绩构成： 平时成绩30%，点名6次，每次5分。 课程设计答辩，包括演示程序，回答老师提问30%，（如果回答问题中发现程序不是本人开发，直接判定不及格）。 课程设计报告，按照指定格式和模板编写，不得随意更改结构。（报告必须与答辩程序相符，如果不符合或发现抄袭，直接判定不及格）22021/8/61.报告内容必须包括以下部分 选题的意义与目的（1-2页）所选题目的任务要求选题的意义课程设计的目标 算法分析

2、，分析所选题目需要用到的数据结构算法，给出算法的基本思路或原理，绘制相关图件（2-3页） 程序设计与实现（10-15页）设计程序的整体结构，分析程序中存在的类，以及它们之间的关系，绘制UML类图。对核心数据结构类给出详细函数接口说明。对关键数据结构算法绘制流程图，给出函数实现代码。32021/8/6 程序运行结果，选择合适的测试数据，对程序进行测试，给出测试用例以及对应的程序运行截图（2-3页） 结论，总结针对所选题目采用的数据结构、算法和程序设计思路，说明取得的成果，论证所述方法的正确性，提一点进一步研究的方向。（1页） 参考文献（不少于5篇）2. 报告正文采用宋体小四号，1.5倍行距书写，

3、各个大部分之间要分页。调整好版式，每页不能有太多空白。图要有标号。总页数不少于20页42021/8/61. 独立设计程序，不得抄袭，不得从网上下载2. 开发平台为Windows系列操作系统3. 编程语言推荐C+，也可以使用Java、C#等主流开发语言4. 开发工具对于C+/C#请采用VC6或VS2008/2010等微软系列开发工具，对于Java请采用Eclipse5. 无论使用何种开发语言和工具，程序数据结构和算法部分不得使用已有类库或第三方类库，必须自己编码实现6. 代码风格统一，书写规范，关键算法加入注释7. 程序必须能正确编译及运行，答辩时程序不能正确编译或主体功能不正确判定为不及格52

4、021/8/662021/8/6 允许用户输入带变量x的函数表达式f(x)，并且可以设定变量范围 根据教材3.1.4节介绍的表达式求值算法原理，利用栈实现带变量的表达式求值 根据表达式求值结果和自变量范围，离散均匀采样绘制函数图像 利用简单的二分法求方程的根要求程序具有UI界面能够绘制函数图像如果用户输入表达式有误，可以提示错误72021/8/682021/8/6 利用Windows控制台API函数开发一个类似于vi的文本编辑器 能够新建或打开已有的文本文件 在控制模式下按下键i，进入编辑模型，在编辑模式下可以用方向键或PgUp、PgDn翻动浏览文件，可以插入或删除字符 在编辑模式下按Esc键

5、可以回到控制模式 在控制模式下输入:q可以退出程序 在控制模式下输入:w可以保存文件92021/8/6 在控制模式下输入:f 查找字符串，可以在文件中查找并定位字符串 在控制模式下输入:r 查找字符串 替换字符串，可以替换从当前光标位置开始的第一个匹配字符串 在控制模式下输入:ra查找字符串 替换字符串，可以替换文件中所有匹配字符串 所有文件编辑功能实现必须是在文本模式下，不得简单调用窗口控件实现文本编辑功能 控制台文本操作的基本功能已被封装，可以直接使用 字符串、列表等数据结构必须自行设计实现，不得使用现有类库 字符串匹配必须使用KMP算法102021/8/6 利用哈夫曼树对文件按字节进行变

6、长编码，降低平均编码长度，达到压缩文件的目的 首先打开并扫描整个文件，按字节统计数0255出现的概率 根据教材7.7节关于哈夫曼树的介绍，对0255进行变长编码，使得最常出现的数具有最短的编码，而最不常出现的数具有最常编码112021/8/6 建立哈夫曼树后，先将哈夫曼树存储到目标文件中，然后再次扫描源文件，对每个字节进行编码并写入到目标文件中，实现文件压缩 解压缩时先从压缩源文件中读取哈夫曼树，然后扫描压缩文件，利用哈夫曼树将变长编码恢复为原来的定长编码，并写入到目标解压文件中哈夫曼编码后的变长编码不是8bit的整数倍，请使用位运算实现变长编码的连续输出程序要有UI界面，压缩和解压缩过程中应

7、显示正确的处理进度压缩后的文件应比源文件小，解压恢复的文件应和源文件完全一致122021/8/6132021/8/6 从文本文件中读取多个无向图的邻接矩阵，按要求绘图 图文件格式如下： 24 文件中存储的邻接矩阵数目 10 图顶点数 0 0 0 0 0 0 1 1 0 0 图的邻接矩阵：0表示无边，1表示有边 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0

8、0 1 1 0 0 0 0 0 0 1 0 1 0 1 0 0 0 0 142021/8/6 图的绘制要求： 用教材8.6.2节的弗洛伊德算法计算顶点间距离，找出最大距离的顶点，设为vi和vj 用教材8.6.1节介绍的迪杰斯特拉算法计算vi到vj的路径，用该路径作为图的主轴方向 遍历路径上其它顶点，如果顶点的度2，则说明存在分支，如果分支数为1则向上绘制分支，如果分支数为2则向上、向下绘制分支，如果分支数2则以横轴为中心，分成上下两部分，每部分均匀绘制分支152021/8/6 输入文件中存在多个邻接矩阵，请按照读入顺序按先列后行的顺序进行绘制，直至所有矩阵绘制完毕。程序要求有UI界面，通过菜单打开图文件成功打开文件后对文件