1、 数据结构课程设计报告数据结构课程设计报告 题目题目: : 表达式求值表达式求值广义表的运算广义表的运算 学学 院院 信息工程学院信息工程学院 _ 专专 业业 _ _ 计算机科学与技术计算机科学与技术 年级班别年级班别 _12_12 级四班级四班_ 学学 号号 _ 学生姓名学生姓名 _ 指导教师指导教师 _ 成成 绩绩 _ _ 2013 年 12 月 1 题目：题目： 广义表的运算。本设计要求实现广义表的建立、查找、输出、取表尾、以及求深度、求 逆表等。 一、一、问题分析与任务定义：问题分析与任务定义： 此程序需要完成以下几个任务： 首先要将输入的用数组存储的广义表转化成以广义表的 存储结构存
2、储的广义表，这个过程也就是生成广义表；查找广义表，查找广义表要返回一个 值 flag，当 flag=1 时，程序查找到待查的元素，当 flag=0 时，程序没有找到待查元素； 输出广义表，遍历广义表，输出广义表的遍历结果；取表头，返回表头结点；取表尾，将广 义表从第二个元素开始复制到另一个广义表中；求广义表的深度，遍历每一层广义表，将广 义表内每层广义表深度最大的广义表相加为同一层所求过的子表中深度的最大值， 最后返回 值加一即为广义表的深度；求逆表，将广义表逆向输出。 实现本程序需要解决以下问题： 1、 如何根据广义表的特点建立广义表。 2、 用什么方法才能查找到广义表中每一个元素，如何标志
3、是否找到待查元素。 3、 建立广义表，如何根据广义表的存储结构的特点建立广义表。 4、 求广义表的深度的依据是什么。 5、 运用什么方法才能将广义表逆序。 6、 如何实现广义表的遍历。 二、概要设计和数据结构选择：二、概要设计和数据结构选择： 1、设计思想：广义表是线性表的一种推广，但它并不是线性表。课本上在介绍广义表的计 本概念的基础上，介绍了广义表的存储及应用。广义表浓缩了线性表、数组等常见的数据结 构的特点，在有效利用存储空间方面更胜一筹，目前在文本处理、人工智能、代数操作和计 算机图形方面等各个领域都具有应用价值。 所以在我当时拿到这个题目的时候， 虽然它只有短短的几行字， 但是我深深
4、的感觉到了 它的难度，在后来课程设计中，也证实了我的感觉，每个功能都实在是太难实现了，所以只 有各个击破了。设计程序时，先起草了流程图，通过流程图来看，就使得程序鲜明易懂，接 下来先写好了主函数，通过主函数的调用，实现题目要求的各个功能，使得程序模块化，便 于编写，即使不会写的子函数，也可以先空着，等待以后想到好的方法后再对其进行操作， 同时在程序界面上也做了美化， 使人感觉舒畅， 另外通过一个循环， 能让用户进行循环操作， 不至于每次只能进行一项操作,这个循环用的和线性表里的循环有点类似，但其实现的操作 不同，当然有了以前实验的基础，这次编写起来，也感觉轻松了不少。 2、广义表的存储结构：
5、由于广义表中的元素本身又可以具有结构，是一种带有层次的非线性结构，因此难以用 顺序存储的结构表示。 通常采用链式存储结构， 每个元素可用一个结点表示， 结点结构如图 1、 图 2 所示： tag=0 atom *tp 2 图 1 原子结点的存储结构 图 2 结点的存储结构 每个结点由三个域构成。其中 tag 是一个标志位，用来区分当前结点是原子结点还是子 表。当 tag 为 1 时，该结点是子表，第二个域为 hp，用以存放子表的地址；当 tag 为 0 时， 该结点是原子结点，第二个域为 atom，用以存放元素值。tp 域是用来存放与本元素同一层的 下一个元素对应结点的地址，当该元素是所在层的
6、最后一个元素时，tp 的值为 NULL。广义表 及结点类型描述如下： typedef char ElemType; typedef struct GLode/广义表结构体的定义 int tag; /*结点类型标识*/ union ElemType atom; /*原子值*/ struct GLode *hp; /*指向子表的指针*/ val; struct GLode *tp; /*指向下一个元素*/ GList; 例如：建立广义表： （a，b（c，d） ，e） ，如图 3 图 3 广义表的存储图示 3、求广义表的逆表需要用堆栈存储广义表的元素，栈的数据类型如下： typedef char ElemType; typedef struct tag=1 *
