数据结构课程设计市公开课一等奖省赛课微课金奖课件

软件工程专业数据结构课程设计成都理工大学信息科学与技术学院第1页课程设计基本要求从指定题目中任选一题，独立完成，不得自行设计指定题目外其它题目，不得剽窃。成绩组成：平时成绩30%，点名6次，每次5分。课程设计答辩，包含演示程序，回答老师提问30%，（假如回答下列问题中发觉程序不是本人开发，直接判定不及格）。课程设计汇报，按照指定格式和模板编写，不得随意更改结构。（汇报必须与答辩程序相符，假如不符合或发觉剽窃，直接判定不及格）第2页课程设计汇报撰写要求汇报内容必须包含以下部分选题意义与目标（1-2页）所选题目标任务要求选题意义课程设计目标算法分析，分析所选题目需要用到数据结构算法，给出算法基本思绪或原理，绘制相关图件（2-3页）程序设计与实现（10-15页）设计程序整体结构，分析程序中存在类，以及它们之间关系，绘制UML类图。对关键数据结构类给出详细函数接口说明。对关键数据结构算法绘制流程图，给出函数实当代码。第3页课程设计汇报撰写要求程序运行结果，选择适当测试数据，对程序进行测试，给出测试用例以及对应程序运行截图（2-3页）结论，总结针对所选题目采取数据结构、算法和程序设计思绪，说明取得结果，论证所述方法正确性，提一点深入研究方向。（1页）参考文件（不少于5篇）汇报正文采取宋体小四号，1.5倍行距书写，各个大部分之间要分页。调整好版式，每页不能有太多空白。图要有标号。总页数不少于20页第4页程序设计基本要求独立设计程序，不得剽窃，不得从网上下载开发平台为Windows系列操作系统编程语言推荐C++，也能够使用Java、C#等主流开发语言开发工具对于C++/C#请采取VC6或VS/等微软系列开发工具，对于Java请采取Eclipse不论使用何种开发语言和工具，程序数据结构和算法部分不得使用已经有类库或第三方类库，必须自己编码实现代码格调统一，书写规范，关键算法加入注释程序必须能正确编译及运行，答辩时程序不能正确编译或主体功效不正确判定为不及格第5页题目一：简单函数计算器第6页题目一：简单函数计算器允许用户输入带变量x函数表示式f(x)，而且能够设定变量范围依据教材3.1.4节介绍表示式求值算法原理，利用栈实现带变量表示式求值依据表示式求值结果和自变量范围，离散均匀采样绘制函数图像利用简单二分法求方程根要求程序含有UI界面能够绘制函数图像假如用户输入表示式有误，能够提醒错误第7页题目二：简单文本编辑器第8页题目二：简单文本编辑器利用Windows控制台API函数开发一个类似于vi文本编辑器能够新建或打开已经有文本文件在控制模式下按下键i，进入编辑模型，在编辑模式下能够用方向键或PgUp、PgDn翻动浏览文件，能够插入或删除字符在编辑模式下按Esc键能够回到控制模式在控制模式下输入:q能够退出程序在控制模式下输入:w能够保留文件第9页题目二：简单文本编辑器在控制模式下输入:f查找字符串，能够在文件中查找并定位字符串在控制模式下输入:r查找字符串替换字符串，能够替换从当前光标位置开始第一个匹配字符串在控制模式下输入:ra查找字符串替换字符串，能够替换文件中全部匹配字符串全部文件编辑功效实现必须是在文本模式下，不得简单调用窗口控件实现文本编辑功效控制台文本操作基本功效已被封装，能够直接使用字符串、列表等数据结构必须自行设计实现，不得使用现有类库字符串匹配必须使用KMP算法第10页题目三：哈夫曼编码压缩利用哈夫曼树对文件按字节进行变长编码，降低平均编码长度，到达压缩文件目标首先打开并扫描整个文件，按字节统计数0—255出现概率依据教材7.7节关于哈夫曼树介绍，对0—255进行变长编码，使得最常出现数含有最短编码，而最不常出现数含有最常编码第11页题目三：哈夫曼编码压缩建立哈夫曼树后，先将哈夫曼树存放到目标文件中，然后再次扫描源文件，对每个字节进行编码并写入到目标文件中，实现文件压缩解压缩时先从压缩源文件中读取哈夫曼树，然后扫描压缩文件，利用哈夫曼树将变长编码恢复为原来定长编码，并写入到目标解压文件中哈夫曼编码后变长编码不是8bit整数倍，请使用位运算实现变长编码连续输出程序要有UI界面，压缩和解压缩过程中应显示正确处理进度压缩后文件应比源文件小，解压恢复文件应和源文件完全一致第12页题目四：图文件绘制第13页题目四：图文件绘制从文本文件中读取多个无向图邻接矩阵，按要求绘图图文件格式以下：24文件中存放邻接矩阵数目10图顶点数0000001100

图邻接矩阵：0表示无边，1表示有边000000100100000001000000000011000000001000000000011100000000101000000000011000000101010000…第14页题目四：图文件绘制图绘制要求：用教材8.6.2节弗洛伊德算法计算顶点间距离，找出最大距离顶点，设为vi和vj用教材8.6.1节介绍迪杰斯特拉算法计算vi到vj路径，用该路径作为图主轴方向遍历路径上其它顶点，假如顶点度>2，则说明存在分支，假如分支数为1则向上绘制分支，假如分支数为2则向上、向下绘制分支，假如分支数>2则以横轴为中心，分成上下两部分，每部分均匀绘制分支第15页题目四：图文件绘制输入文件中存在多个邻接矩阵，请按照读入次序按先列后行次序进行绘制，直至全部矩阵绘制完成。程序要求有UI界面，经过菜单打开图文件成功打