数学系12级课程设计PPT课件.ppt

数据结构 课程设计 布置4个题目 任选两个 设计报告内容 标题 题目 问题描述程序结构 程序中的函数调用关系图 程序中函数的功能描述5 主要算法及数据结构描述 算法可用伪代码或流程图 测试方法描述 如何输入测试数据 会出现的结果 本实验总结 特色 扩展的功能 在两个题目的报告完成后 最后给出本次设计的总结 感想等 附录 源代码 要求程序风格清晰易理解 有充分的注释 有意义的注释行不少于代码的30 1 一 一元多项式的计算问题描述将多个多项式输入并存储在内存中 然后对多项式进行加 减 数乘等运算 要求 1 可设计菜单 2 2 选I 输入一个或多个多项式 如输入 f 3 0 7 46 50 13 7x 4 6x 5g 4 16 4 570 14x 1 6x 4 5x 73 选C 输入计算表达式 然后计算结果并显示如输入 h f g显示结果 h 3 4x 1 1x 4 6x 5 5x 7如输入 k f g显示结果 k 3 4x 1 13x 4 6x 5 5x 74 选L 显示内存中现有的多项式 如 显示出 f 3 7x 4 6x 5g 4x 1 6x 4 5x 7h 3 4x 1 1x 4 6x 5 5x 7 3 5 每个多项式必须用单链表来存储 typedefstructnode floatcoef 系数intexp 指数structnode next 指向下个结点的指针 nodetype 3 功能扩展 自己定制 可增加两个多项式的相乘 如f g可增加1个多项式的求导数 如f 4 二 求复杂表达式的值 课本343页综合实验题2 问题描述输入一个含有运算符和运算函数的表达式 计算其结果 要求1 以字符串方式输入一个复杂的表达式 表达式中包括 数值 整数 实数 一般运算符 正号 负号 加 减 乘 除 求模 乘方 括号 如输入 123 45 7 25 20 3 12 4 123 4 2 利用栈 根据各运算符的优先度进行数值计算 显示结果3 循环回1 继续下个表达式的输入 5 功能扩展 自己定制 1 表达式中可含有运算函数 abs 绝对值 sqrt 开方exp 指数函数 ln 对数 sin cos tan如输入 123 45 sin abs 23 3 14 exp 3 上述函数在C 中有对应的函数调用 fabs sqrt exp log sin cos tan 2 增加自定义的运算 如阶乘 30 等3 自己进一步扩充 如显示计算过程等 6 三 用二叉树实现家谱的相关运算 课本综合实验题2 1 问题描述 设计一个程序采用一颗二叉树表示一个家谱关系 2 要求 1 文件操作功能 记录输入 记录输出 清除全部文件记录 和将家谱记录存盘 2 家谱操作功能 用括号表示法和凹入表示法输出家谱二叉树 查找某人所有的儿子 查找某人所有祖先 3 由于家谱是一棵树形 而不是二叉树 存储时要转换成形式如下的二叉树 一个父亲结点的左孩子结点表示母亲结点 父亲结点无右孩子结点 母亲结点的右子树表示他们的儿子 结构示意图如下 7 家谱采用二叉树表示时的基本结构 8 4 可设计菜单如下 1 文件操作2 家谱操作0 退出请选择 1选择1 显示子菜单如下 1 输入2 输出3 全清0 存盘返回请选择 1选择1 提示输入 请输入父亲 母亲和儿子姓名 f1m1f11返回菜单显示 1 输入2 输出3 全清0 存盘返回请选择 1请输入父亲 母亲和儿子姓名 f1m1f12返回菜单显示 1 输入2 输出3 全清0 存盘返回请选择 1请输入父亲 母亲和儿子姓名 f11m11f111返回菜单显示 1 输入2 输出3 全清0 存盘返回请选择 0 9 选择0 返回上级菜单 1 文件操作2 家谱操作0 退出请选择 2选择2 显示子菜单如下 1 括号表示法2 凹入表示法3 找某人的儿子姓名4 找某人的所有祖先0 返回请选择 1选择1 输出如下 f1 m1 f11 m11 f111 f12 返回菜单显示 1 括号表示法2 凹入表示法3 找某人的儿子姓名4 找某人的所有祖先0 返回请选择 3 10 选择3 提示输入输入父亲姓名 f1输出如下 f1的儿子 f11f12返回菜单显示 1 括号表示法2 凹入表示法3 找某人的儿子姓名4 找某人的所有祖先0 返回请选择 4 11 选择4 提示输入输入姓名 f111输出如下 所有祖先 f1m1f11m111 括号表示法2 凹入表示法3 找某人的儿子姓名4 找某人的所有祖先0 返回请选择 0选择0 返回上级菜单 1 文件操作2 家谱操作0 退出请选择 0结束5 星号部分作为功能扩展可任选 12 四 基于哈夫曼编码的数据压缩 解压程序1 问题描述 将任意一个指定的文本文件中的字符进行哈夫曼编码 生成一个编码文件 压缩文件 和哈夫曼树文件 反过来 可将一个压缩文件解码还原为一个文本文件 2 要求 1 可设计一个菜单 13 2 选择C时 输入一个待压缩的文本文件名称 可带路径 如 D lu lu txt统计文本文件中各字符的个数作为权值 生成哈夫曼树 将哈夫曼树存入磁盘文件中 将文本文件利用哈夫曼树进行编码 生成压缩文件 压缩文件名称 文本文件名 COD如 D lu lu COD哈夫曼树文件名称 文本文件名 hfm如 D lu lu hfm3 选择D时 输入一个待解压的压缩文件名称 可带路径 如 D lu lu COD从对应的哈夫曼文件中读出哈夫曼树 14 利用哈夫曼树将编码文件中的编码序列解码 生成 还原 文本文件 文本文件名称 压缩文件名 new txt 如 D lu lu new txt4 选择L时 输入一个待压缩的文本文件名称 可带路径 如 D lu lu new txt显示出该文本文件的内容 3 功能扩展 自己定制 编码使用二进制位 利用位运算进行真正的数据压缩 可对任何文件进行压缩 显示出各种重要信息 如压缩率 各字符的哈夫曼编码表 15 说明 评分方法 程序60 其中注释占30 文档40 其中测试部分占20 其余20 是否按要求完成各部分文档的撰写 测试方法和测试数据的设计总结