数据结构课程设计.ppt

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

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

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

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

5、浏览文件，可以插入或删除字符 在编辑模式下按Esc键可以回到控制模式 在控制模式下输入:q可以退出程序 在控制模式下输入:w可以保存文件,A,10,题目二：简单文本编辑器,在控制模式下输入:f 查找字符串，可以在文件中查找并定位字符串 在控制模式下输入:r 查找字符串 替换字符串，可以替换从当前光标位置开始的第一个匹配字符串 在控制模式下输入:ra查找字符串 替换字符串，可以替换文件中所有匹配字符串 所有文件编辑功能实现必须是在文本模式下，不得简单调用窗口控件实现文本编辑功能 控制台文本操作的基本功能已被封装，可以直接使用 字符串、列表等数据结构必须自行设计实现，不得使用现有类库 字符串匹配必

6、须使用KMP算法,A,11,题目三：哈夫曼编码压缩,利用哈夫曼树对文件按字节进行变长编码，降低平均编码长度，达到压缩文件的目的 首先打开并扫描整个文件，按字节统计数0255出现的概率 根据教材7.7节关于哈夫曼树的介绍，对0255进行变长编码，使得最常出现的数具有最短的编码，而最不常出现的数具有最常编码,A,12,题目三：哈夫曼编码压缩,建立哈夫曼树后，先将哈夫曼树存储到目标文件中，然后再次扫描源文件，对每个字节进行编码并写入到目标文件中，实现文件压缩 解压缩时先从压缩源文件中读取哈夫曼树，然后扫描压缩文件，利用哈夫曼树将变长编码恢复为原来的定长编码，并写入到目标解压文件中 哈夫曼编码后的变长

7、编码不是8bit的整数倍，请使用位运算实现变长编码的连续输出 程序要有UI界面，压缩和解压缩过程中应显示正确的处理进度 压缩后的文件应比源文件小，解压恢复的文件应和源文件完全一致,A,13,题目四：图文件绘制,A,14,题目四：图文件绘制,从文本文件中读取多个无向图的邻接矩阵，按要求绘图 图文件格式如下： 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

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