识别广义表头尾演示数据结构课程设计报告.doc

沈阳航空航天大学 课课 程程 设设 计计 报报 告告 课程设计名称 数据结构课程设计数据结构课程设计 课程设计题目 识别广义表头尾演示识别广义表头尾演示 院 系 计算机学院 专 业 软件工程 班 级 34010301 学 号 2013040103030 姓 名 张为 指导教师 丁一军 说明 结论 优秀 良好 中等 及格 不及格 作为相关教环节考核必要依据 说明 结论 优秀 良好 中等 及格 不及格 作为相关教环节考核必要依据 格式不符合要求 数据不实 不予通过 报告和电子数据必须作为实验现象重复的格式不符合要求 数据不实 不予通过 报告和电子数据必须作为实验现象重复的 关键依据 关键依据 沈阳航空航天大学课程设计报告 学术诚信声明 本人声明本人声明 所呈交的报告 含电子版及数据文件 是我个人在导师指 导下独立进行设计工作及取得的研究结果 尽我所知 除了文中特别 加以标注或致谢中所罗列的内容以外 报告中不包含其他人己经发表 或撰写过的研究结果 也不包含其它教育机构使用过的材料 与我一 同工作的同学对本研究所做的任何贡献均己在报告中做了明确的说明 并表示了谢意 报告资料及实验数据若有不实之处 本人愿意接受本 教学环节 不及格 和 重修或重做 的评分结论并承担相关一切后 果 本人签名 日期 年 月 日 沈阳航空航天大学课程设计报告 I 沈阳航空航天大学沈阳航空航天大学 课课程程设设计计任任务务书书 课程设计名称 数数据据结结构构课课程程设设计计专业 软软件件工工程程 学生姓名张为张为班级 34010301 学号 2013040103030 题目名称 识别广义表头尾演示识别广义表头尾演示 起止日期2014年9月1日起至2015年1月14日止 课设内容和要求 1 写一个程序 建立广义表的存储结构 演示在此存储结构上实现的广义表 求头 求尾操作序列的结果 2 广义表允许多行输入 其中可以任意输入空格符 3 广义表存储结构自定 4 对广义表的操作为一个由 t 和 h 组成的字符串 参考资料 算法与数据结构 C 语言程序设计 教教研研室室审审核核意意见见 教教研研室室主主任任签签字字 指导教师 签名 指导教师 签名 年月日 沈阳航空航天大学课程设计报告 II 学学 生 签名 生 签名 年月日 沈阳航空航天大学课程设计报告 III 目目 录录 沈阳航空航天大学沈阳航空航天大学 I 学术诚信声明学术诚信声明 I 1 题目介绍与功能描述题目介绍与功能描述 1 1 1 题目介绍 1 1 2 具体要求 1 1 3 题目分析 1 2 系统功能模块结构图系统功能模块结构图 2 2 1 系统功能结构图 2 2 2 主要模块功能说明 3 2 2 1 建立广义表 3 2 2 2 对表进行求头尾操作 3 3 数据结构设计及用法说明数据结构设计及用法说明 4 3 1 存储结构 4 3 2 用法说明 4 4 主要函数主要函数 5 4 1 VOID CREATLIST GLIST 表结点类型 tag 0 表示原子结点 tag 1 表示表结点 union char data struct struct GLNode hr tr GList 3 2 用法说明用法说明 对广义表的结构采用链表的形式进行定义 由于广义表可以是原子也可以是 表 所以在结构体中还采用了共用体的数据结构 让原子和节点可以共享存储单 元 tag 代表节点的类型 0 为原子 1 为表 hr 代表表的头指针 tr 代表表的尾指 针 data 为表的内容 沈阳航空航天大学课程设计报告 4 4 主要函数 程序主体由几个关键函数组成 creatlist GList c getchar if c return 1 广义表第一个字符必须是 否则终止函数 GList Ls creatlist Ls 在整个程序中采用 getchar 函数从键盘缓冲区读取输入的广义表数据 creatlist 函数的完全代码如下 void creatlist GList c getchar 拾取一个合法字符 if c 空表的情况 Ls NULL c getchar if c return 空表的下一个合法字符应该是 else 沈阳航空航天大学课程设计报告 5 当前输入的广义表非空 GList p Ls GList malloc sizeof GLNode Ls tag 1 表结点 if c 表头为单原子 Ls hr GList malloc sizeof GLNode p Ls hr p tag 0 p data c 建立原子结点 else 表头为广义表 creatlist Ls hr 对此广义表递归建立存储结构 c getchar if c creatlist Ls tr 当前广义表未结束 等待输入下一个子表 else if c Ls tr NULL 当前广义表输入结束 广义表是采用递归的方式定义的 因此 creatlist 中广义表也是采用递归的方式建 立的 由于广义表的第一个字符 在 main 函数中已被读取 因此 creatlist 中从键 盘数据缓冲区读取的第一个字符是所输入的广义表的第二个字符 若当层广义表 非空 则应建立表结点 在建立原子结点时所用的判断方法为 if c 是因 为 之后的字符要么是 要么是原子 在经过代码 if c 沈阳航空航天大学课程设计报告 6 creatlist Ls tr 递归建立的广义表的读取的第一个字符只能是原子或者 而不可能是 因此建立原子结点的判断方法为 if c 当 getchar 读取的字符为 时 表示要进入下一层广义表 故使用语句 creatlist Ls hr 递归建立下一层广义表 当 getchar 读取的字符为 时 表示当层广义表未结束 还有子表需要建立 故用 creatlist Ls tr 递归建立剩余的子表 当 getchar 读取的字符为 时 表示当层广义表已结束 则表结点的表尾指针 应为空 即 Ls tr NULL 缺点 缺点 函数 creatlist 的纠错能力较差 要求输入的广义表应为广义表的标准正确 形式 如 a b a 1 d 3 4 如果输入的形式错误 如 s d o 就会造成整个程 序无法运行下去 4 2 void GL Elem GList p GL Elem 十分简单 只是一个将存储的原子输出的函数 代码如下 void GL Elem GList p 输出原子 printf c p data 4 3 void printf GL GList Ls int Ls 指向空表 else cout hr if p 空表 printf else if p tag 1 p 指向表结点 printf i printf GL p i else if p tag 0 GL Elem p 若 p 指向原子结点则输出原子 GList k Ls tr 表结点的尾指针 if k printf 尾指针存在表示此表中还有元素 printf GL k i 遍历下一结点 else if k i 主要思想 主要思想 解决这两个问题需要分辨出当前指针指向的是第几层子表 对于 沈阳航空航天大学课程设计报告 8 问题一 假设 Ls 指向的是当层子表的一个表结点 p Ls hr 显然 p tag 0 表 示 p 指针所指结点与 Ls 所指结点在同一层 则只需输出原子即可 p tag 1 表 示 p 指针所指结点为 Ls 所指结点所在层次的广义表的子层 则输出 并递 归遍历 p 所指层次的广义表 即 printf GL p i 对于问题二 则需要分辨出表结点的尾指针的指向 k Ls tr 若 k 存在 则说明此层子表中仍有元素 故输出 若 k 不存在 说明此层子表完结 输 出 4 4 void GetHead GList GList p Ls 保存头指针 p tr NULL 隔离出 Ls 所指广义表的第一个元素 int i 0 printf GL p i 主要思想主要思想 输出广义表的表头 可以利用 printf GL 函数遍历广义表的第一个元 素 具体做法只需将第一个结点的尾指针设为空 则将这一结点从原广义表中独 立开来 单独作为一个 广义表 进行遍历 输出的结果即为原广义表的表头 由于广义表的表头为广义表的第一个元素 可以不是一个子表 如广义表 a 1 2 的表头为 a 因此将传递的参数 i 初始值置为 0 这样在最上层的 广义表表结点尾指针为空 k 时 由于 i 0 故不需要输出 4 5 void GetTail GList Ls Ls tr if Ls 沈阳航空航天大学课程设计报告 9 printf Ls 指向空表 else printf 表尾第一个字符为 int i 1 已有左括号 故 i 1 printf GL Ls i 主要思想主要思想 输出广义表的表尾 可将指向广义表的指针 Ls 指向第一个结点 的下一个结点 Ls Ls tr 这样就能得到原广义表中除第一个元素外其他元素所 组成的新表 即原广义表的表尾 然后再利用遍历广义表的方法对该表尾进行遍 历即可 4 6 void Get HT GList Ls 这是直接求表头 表尾的函数 由它接收输入 此函数实现对广义表求头尾 操作的函数 解释输入的操作序列命令 由 t h 组成的字符串 并执行 代码如下 void Get HT GList Ls 执行求广义表表头 尾 的操作函数 char ch getchar while ch GList p Ls 保存表头指针 if p printf n 当前表为空表 不能执行求头尾操作 n break else switch ch case t GetTail Ls break case h GetHead Ls break 沈阳航空航天大学课程设计报告 10 case 空串时输出整个广义表 printf n 上表为 if Ls printf Ls 指向空表 else printf 广义表第一个字符为 int i 1 已有左括号 故 i 1 printf GL Ls i break default return ch getchar 主要思想主要思想 Get HT 函数中同样是利用 getchar 函数读取输入的操作命令 根据读取到的不同字符 完成不同的操作 沈阳航空航天大学课程设计报告 11 5 主要函数流程图 5 1 main 函数函数 否 是 是 否 图图 5 15 1 mainmain 函数流程图函数流程图 主函数较简洁 操作都放在具体函数之上 退出 进入建表函数 求头尾函数 C 是否为 表为空 开始 结束 输入头尾操作序列 输出 输出广义表 沈阳航空航天大学课程设计报告 12 5 2 creatlist 函数函数 是 否 是 是 否 输入为 图图 5 25 2 createlistcreatelist 函数流程图函数流程图 建表函数主要运用递归的思想对广义表进行建立 循环的建立表头 表尾 直到输入的为反括号为止结束 在建表的时候需要对表进行判断 判断输入的是 否为空或字符 表为空 建立空表 退出 建立原子节点 输入为 输入为 结束 开始 c 是否为空 C 为 C 为 沈阳航空航天大学课程设计报告 13 5 3 printf GL 函数函数 是 否 是 否 否 是 否 是 图图 5 35 3 printf GLprintf GL 函数流程图函数流程图 输出函数是整个程序很重要的函数 取表头 取表尾的操作都依靠输出函数 表头 表尾函数与输出函数结合构成整个程序的核心 开始 K 为尾指针 输出原子 输出 i tag 1 输出 P 为空 P 为头指针 结束 输出 i i 0 输出 K 为空 沈阳航空航天大学课程设计报告 14 6 调试报告 6 1 测试用例设计测试用例设计 1 输入 a b c d 操作 thth 2 输入 e a b c d 操作 tth 3 输入 b c d e 操作 htht 4 输入 3 4 5 2 d 操作 h tth 注意 注意 和 是不同的 前者括号内无空格符 后者有 本程只能识别后 一种 代表空表 测试用例 3 中 操作序列 h tth 是由 5 个字符 h 空格符 t t h 组 成 其中空格符表示空串 6 2 调试过程调试过程 遇到问题 遇到问题 1 当求表头时 输出时 在结果末尾会多出现一个右括号 例 如 对于广义表 1 2 3 进行求表头操作 得到的结果为 1 正确的结果应为 1 2 第一次输入广义表的数据后 无法再输入求头尾的操作序列 使 得 程序不能完成应有的求头尾的功能 原因及解决方法 原因及解决方法 1 问题原因 问题原因 问题出在遍历函数 printf GL 中 在求头尾的操作中 由 于将第一个表结点的尾指针置为空 将其从原广义表中独立出来 使得在 printf GL 中 执行了一次 printf 解决方法 解决方法 设置一个括号计数器 i 当输出一个 时 i 输 出一个 时 i 并利用 i 的值判断是否应当输出 即判断条 件为 if k语句 2 问题原因问题原因 程序中使用了两次不同需求的 getchar 函数 但是当 用户 沈阳航空航天大学课程设计报告 15 键入回车之后 getchar 才开始从 stdin 流中每次读入一个字符 在第一次输入过 程中 由于输入了广义表之后 键入了回车 导致接下来的 getchar 函数均是从 键盘缓冲区中读入数据 使得用户无法输入新数据 解决方法 解决方法 通过 fflush stdin 来清空输入缓冲区 以确保不影响后面的数 据读取 将此语句放在 main 函数第一部分的末尾 即在建立好广义表后清空缓 冲区 6 3 运行结果运行结果 1 输入 a b c d 操作 thth 2 输入 e a b c d 操作 tth 沈阳航空航天大学课程设计报告 16 3 输入 b c d e 操作 htht 4 输入 3 4 5 2 d 操作 h tth 沈阳航空航天大学课程设计报告 17 沈阳航空航天大学课程设计报告 18 课程设计总结 课程设计总结 在此次的课程设计之前 我对广义表的内容了解的比较模糊 经过此次课 程设计 对于广义表的存储结构以及求头尾操作 我有了较深的理解 广义表 的用途十分广泛 因此要求了广义表的灵活性 广义表的存储结构是链式的 且类似于二叉树 广义表与二叉树的表头结点均有两个指针 但是二叉树的指 针是自上而下的联系 而广义表中的尾指针是指向同层结点 因此有横向的联 系 这点上与二叉树不同 对广义表的求头尾操作中要注意 广义表的表头是广义表中的第一个元素 而广义表的表尾是除第一个元素外其他元素组成的表 即广义表的表尾一定是 广义表 而表头是否为广义表 取决于第一个元素的类型 由于时间问题 很多地方我都没有精雕细琢 导致本程序的容错能力不是 很好 即健壮性较差 需要改进的地方有很多 本程序尤其对输入的广义表要 求很高 若输入的广义表出错 而用户没有发现 将会照成程序无法运行 软 件设计的健壮与否直接反应了分析设计和编码人员的水平 即所谓高手写的程 序不容易死 因此我还有很多值得学习的内容 有很多地方需要提高 沈阳航空航天大学课程设计报告 19 参考文献 1 谭浩强 C 程序设计 北京 清华大学出版社 2002 2 严蔚敏 吴伟民 数据结构 C 语言版 北京 清华大学出版社 2002 沈阳航空航天大学课程设计报告 20 附录 源程序清单 include include typedef struct GLNode 广义表结点定义 int tag 表结点类型 tag 0 表示原子结点 tag 1 表示表结点 union char data struct struct GLNode hr tr h 为表头指针 t 为表尾指针 GList void creatlist GList c getchar 拾取一个合法字符 if c 空表的情况 Ls NULL c getchar if c return 空表的下一个合法字符应该是 else 当前输入的广义表非空 GList p 沈阳航空航天大学课程设计报告 21 Ls GList malloc sizeof GLNode Ls tag 1 表结点 if c 表头为单原子 Ls hr GList malloc sizeof GLNode p Ls hr p tag 0 p data c 建立原子结点 else 表头为广义表 creatlist Ls hr 对此广义表递归建立存储结构 c getchar if c creatlist Ls tr 当前广义表未结束 等待输入下一个子表 else if c Ls tr NULL 当前广义表输入结束 void GL Elem GList p 输出原子 printf c p data 沈阳航空航天大学课程设计报告 22 void printf GL GList Ls int if p 空表 printf else if p tag 1 p 指向表结点 printf i printf GL p i else if p tag 0 GL Elem p 若 p 指向原子结点则输出原子 GList k Ls tr 表结点的尾指针 if k printf 尾指针存在表示此表中还有元素 printf GL k i 遍历下一结点 else if k i void GetHead GList 沈阳航空航天大学课程设计报告 23 GList p Ls 保存头