数据结构课程设计ppt课件

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