数据结构上机实习PPT课件

1 数据结构上机实习 2 上机实习安排 实习时间 第6 8 10 12周的周四下午2 00 5 00实习地点 191161 2班 综合楼313191163 4班 综合楼315 3 实习步骤 1 按照每次实习的要求选定题目 2 分析题目要求 明确要实现的功能 设计数据结构 根据面向对象编程方法 确定算法的基本思想 主要模块 各模块功能及调用关系 再用C 语言对主要算法进行细化 3 编写好上机源程序 并进行静态检查 使程序中的逻辑错误和语法错误减少到最低程度 4 准备好测试数据 考虑好调试手段 上机调试程序 程序通过后 打印一份源程序清单及对测试数据的运行结果 5 最后写好调试分析报告及使用说明 完成一份完整的实习报告 4 实习报告的内容 一 实习题目与要求包括题目与功能要求二 需求分析包括问题描述 系统环境 运行要求等三 概要设计包括数据结构和存储结构的设计 算法设计 模块设计等四 详细设计包括类的函数成员和数据成员设计 界面设计及其它模块设计与实现 5 五 调试分析调试过程中遇到的主要问题是如何解决的 对设计和编码的回顾讨论和分析 算法的时间和空间复杂度的分析 算法的进一步改进等 六 使用说明使用说明主要描述如何使用你的程序及使用时的注意事项 七 测试结果如果题目规定了测试数据 则结果要包含这些测试数据和运行输出 当然还可以含其他测试数据及其运行输出 需要多组测试数据 八 源程序清单源程序中要添加必要的注释 6 实习一线性表 栈和队列及应用 任选一题 7 1 一元稀疏多项式运算器 问题描述 设计一个一元稀疏多项式简单计算器 基本要求 1 输入并建立两个多项式 2 多项式a与b相加 建立和多项式c 3 多项式a与b相减 建立差多项式d 4 输出多项式a b c d 输出格式 比如多项式a为 A x c1xe1 c2xe2 cmxem 其中 ci和ei分别为第i项的系数和指数 且各项按指数的升幂排列 即0 e1 e2 em 8 测试数据 1 1 x x2 x3 x4 x5 x3 x4 1 x x2 x5 2 x x100 x100 x200 x 2x100 x200 3 2x 5x8 3x11 7 5x8 11x9 7 2x 11x9 3x11 4 6x 3 x 4 4x2 1 2x9 6x 3 4 4x2 7 8x15 12x 3 x 1 2x9 7 8x15 实现提示 1 用带头结点的单链表存储多项式 2 每个多项式链表中都只存储非零系数项 若多项式a与b中指数相等的两项相加 减后 系数为零 则在和 差多项式中不存储该指数项 拓展内容 计算器的仿真界面 9 2 n n 20 的阶乘 问题描述 大数运算 计算n的阶乘 n 20 基本要求 1 数据的表示和存储 累积运算的中间结果和最终的计算结果的数据类型要求是整型 这是问题本身的要求 试设计合适的存储结构 要求每个元素或结点最多存储数据的3位数值 2 数据的操作及其实现 基于设计的存储结构实现乘法操作 要求从键盘上输入n值 在屏幕上显示最终计算结果 10 测试数据 1 n 20 n 2432902008176640000 2 n 30 n 265252859812191058636308480000000 实现提示 1 设计数据的存储结构 介于阶乘运算的精确性以及实型数据表示的不精确性 本题不能采用实型表示累积运算的中间结果和最终的计算结果 而只能用整型 然而由于普通整型和长整型所能表述数的范围受其字长的限制 不能表示大数阶乘的累积结果 故必须设计一个合适的数据结构实现对数据的存储 例如可以让每个元素或结点存储数据的若干位数值 从问题描述不难看出n值为任意值 故为使程序尽量不受限制 应采用动态存储结构 11 2 实现两个数的乘法运算需考虑 乘数的各位数都要与被乘数进行乘法运算 乘法过程中的进位问题及其实现 因每个元素或结点最多存储数据的3位数值 故当元素或结点中的数值大于999 需向前一个元素或结点进位 12 3 表达式的后缀表示 问题描述 表达式中包含运算对象 运算符和圆括号等 习惯上使用中缀表示 指运算符夹在两运算符对象中间 形式 计算表达式的值 涉及到运算符的优先级别 如先乘除后加减 括在一对圆括号中的子表达式必须先计算 因此 圆括号可视为特殊的运算符 具有最高优先级别 圆括号可以任意嵌套 这意味着左圆括号后面又是表达式 形成表达式的递归定义 为了直接指明表达式中各运算对象的先后计算顺序 可将表达式的中缀形式转换成后缀 指运算符放在二运算对象的后面 形式 例如 表达式a b c d e 这是通常的中缀形式 其后缀表示是ab cd e 其中圆括号在后缀形式中已不见了 设计一转换程序 将输入的任一表达式转换成相应的后缀形式后输出 13 基本要求 为简单起见 假定运算对象只含变量 且每个变量名以单字母表示 运算符仅含 和圆括号 表达式以分号 结尾 在转换过程中 要求作必要的语法检查 例如圆括号是否配对 单词是否合法等 要求分别编写转换程序的非递归与递归算法 测试数据 1 A B C 2 a b c d e f 3 A B D E F A D C 14 实习二树和二叉树及应用 任选一题 15 1 实现Windows资源管理器 问题描述 Windows资源管理器是用来管理计算机资源的窗口 电脑里所有的文件都可以在资源管理器里找到 可以在资源管理器里查看文件夹的分层结构 可以利用资源管理器快速进行文件和文件夹的操作 例如 磁盘 根 目录 不同类型的文件 其中 文件信息包括文件名 类型 创建时间 文件大小等 磁盘信息包括磁盘名称 总大小 可用空间等 目录信息包括目录名称 修改日期 大小 对象数等 16 基本要求 1 构造一个空的资源管理器 2 新建 删除磁盘 3 在当前选择目录下新建 删除目录 4 在当前选择目录下新建 删除文件 5 以目录树的形式输出当前目录下的文件以及文件夹信息 并统计目录数和文件数 6 回上一级 当前目录为当前目录的上一级目录 并以目录树的形式输出当前目录下的文件以及文件夹信息 并统计目录数和文件数 7 模糊查找目录 文件信息 并显示查找结果 8 撤销一个资源管理器 17 2 树的遍历 问题描述 1 一棵有n个结点的有根树 结点从1到n标号 不同的点标号不同 对于每一个结点 求在它的子孙结点中 有多少个结点的标号比它的标号小 2 已知一棵树上的边的长度 那么有多少对结点的距离小于等于K 可自定义K值 及构建自己的树 扩展内容 一棵有n个结点的树 以及定义在边上的权值w 选出一个最多有p个结点的集合S 定义d i min dis i j j是S中的结点 要求这样的S 使得给定d 1 d 2 d n 最小 18 3 唯一的确定一棵二叉树 问题描述 如果给出了遍历二叉树的前序序列和中序序列 则可以构造出唯一的一棵二叉树 试编写实现上述功能的程序 基本要求 已知一棵二叉树的前序和中序遍历序列 试设计完成下列任务的一个算法 1 构造一棵二叉树 2 证明构造正确 即分别以前序和中序遍历该树 将得到的结果与给出的序列进行比较 3 对该二叉树进行后序遍历 输出后序遍历序列 4 用凹入法输出该二叉树 19 测试数据 1 前序序列为ABDEGCFHIJ中序序列为DBGEAHFIJC 2 前序序列为 abc de中序序列为a b c d e 拓展内容 已知后序和中序遍历序列构造二叉树 20 实习三搜索及应用 任选一题 21 1 实现对字典的查找 问题描述 采用分块查找 二叉搜索树查找 哈希表查找等不同的查找方法实现对字典的查找 并分析不同查找方法的效率 统计查找花费的时间 22 2 电话号码查询系统 问题描述 设计散列表实现电话号码查询系统 基本要求 1 设每个记录有下列数据项 电话号码 用户名 地址 2 从键盘输入各记录 分别以电话号码和用户名为关键字建立散列表 3 采用合适的方法解决冲突 4 查找并显示给定电话号码的记录 5 查找并显示给定用户名的记录 23 实现提示 构造哈希函数时 要注意使其分布均匀 用户名的长度均不超过20个字符 可先对过长的用户名作折叠处理 选作内容 1 从几种哈希函数构造方法中选出适用者并设计几个不同的哈希函数 比较它们的地址冲突率 2 在哈希函数确定的前提下 尝试各种不同的处理冲突的方法 并比较平均查找长度的变化 24 实习四图及其应用 任选一题 25 1 求无向连通图的生成树 问题描述 若要在n个城市之间建设通信网络 只需要架设n 1条路线即可 如何以最低的经济代价建设这个通信网 是一个网的最小生成树问题 基本要求 1 利用克鲁斯卡尔算法求网的最小生成树 其中 以课本中的等价类表示构造生成树过程中的连通分量 2 利用普里姆算法求网的最小生成树 3 以文本文件形式输出生成树中各条边及它们的权值 26 2 图的遍历 问题描述 有一个长方形的房间 房间里的地面上布满了正方形的瓷砖 瓷砖要么是红色的 要么是黑色的 一个人站在其中一块黑色的瓷砖上 他可以向四周的瓷砖上移动 但是不能移动到红色的瓷砖上 只能在黑色的瓷砖上