广义表的运算-数据结构与算法课程设计报告.doc

《广义表的运算-数据结构与算法课程设计报告.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、合肥学院计算机科学与技术系课程设计报告2009～2010学年第二学期课程数据结构与算法课程设计名称广义表的运算学生姓名陈发银学号0804012028专业班级08计本（2）班指导教师王昆仑2010年6月20题目：广义表的运算。本设计要求实现广义表的建立、查找、输出、取表尾、以及求深度、求逆表等。一、问题分析与任务定义：此程序需要完成以下几个任务：首先要将输入的用数组存储的广义表转化成以广义表的存储结构存储的广义表，这个过程也就是生成广义表；查找广义表，查找广义表要返回一个值flag，当flag=1时，程序查找到待查的元素，当flag=0时，程序没有找到待查元素；输出广义表，

2、遍历广义表，输出广义表的遍历结果；取表头，返回表头结点；取表尾，将广义表从第二个元素开始复制到另一个广义表中；求广义表的深度，遍历每一层广义表，将广义表内每层广义表深度最大的广义表相加为同一层所求过的子表中深度的最大值，最后返回值加一即为广义表的深度；求逆表，将广义表逆向输出。实现本程序需要解决以下问题：1、如何根据广义表的特点建立广义表。2、用什么方法才能查找到广义表中每一个元素，如何标志是否找到待查元素。3、建立广义表，如何根据广义表的存储结构的特点建立广义表。4、求广义表的深度的依据是什么。5、运用什么方法才能将广义表逆序。6、如何实现广义表的遍历。二、概要设计和数

3、据结构选择：1、设计思想：广义表是线性表的一种推广，但它并不是线性表。课本上在介绍广义表的计本概念的基础上，介绍了广义表的存储及应用。广义表浓缩了线性表、数组等常见的数据结构的特点，在有效利用存储空间方面更胜一筹，目前在文本处理、人工智能、代数操作和计算机图形方面等各个领域都具有应用价值。所以在我当时拿到这个题目的时候，虽然它只有短短的几行字，但是我深深的感觉到了它的难度，在后来课程设计中，也证实了我的感觉，每个功能都实在是太难实现了，所以只有各个击破了。设计程序时，先起草了流程图，通过流程图来看，就使得程序鲜明易懂，接下来先写好了主函数，通过主函数的调用，实现题目要求的

4、各个功能，使得程序模块化，便于编写，即使不会写的子函数，也可以先空着，等待以后想到好的方法后再对其进行操作，同时在程序界面上也做了美化，使人感觉舒畅，另外通过一个循环，能让用户进行循环操作，不至于每次只能进行一项操作,这个循环用的和线性表里的循环有点类似，但其实现的操作不同，当然有了以前实验的基础，这次编写起来，也感觉轻松了不少。2、广义表的存储结构：由于广义表中的元素本身又可以具有结构，是一种带有层次的非线性结构，因此难以用顺序存储的结构表示。通常采用链式存储结构，每个元素可用一个结点表示，结点结构如图1、图2所示：tag=0atom*tp图1原子结点的存储结构20ta

5、g=1*hp*tp图2结点的存储结构每个结点由三个域构成。其中tag是一个标志位，用来区分当前结点是原子结点还是子表。当tag为1时，该结点是子表，第二个域为hp，用以存放子表的地址；当tag为0时，该结点是原子结点，第二个域为atom，用以存放元素值。tp域是用来存放与本元素同一层的下一个元素对应结点的地址，当该元素是所在层的最后一个元素时，tp的值为NULL。广义表及结点类型描述如下：typedefcharElemType;typedefstructGLode//广义表结构体的定义{inttag;/*结点类型标识*/union{ElemTypeatom;/*原子值*/

6、structGLode*hp;/*指向子表的指针*/}val;structGLode*tp;/*指向下一个元素*/}GList;例如：建立广义表：（a，b（c，d），e），如图31^0a0b1^0c0d1^0e1^^图3广义表的存储图示3、求广义表的逆表需要用堆栈存储广义表的元素，栈的数据类型如下：typedefcharElemType;typedefstruct{ElemTypedata[maxlen];inttop;}SeqStack;203、程序流程图如图。main()建立一个用字符数组存储的广义表，用字符指针s指向它输入广义表生成数组广义表结构遍历广义表建立堆栈查

7、找待查元素，flag=1，找到待查元素，反之，没有查到。求广义表的深度，并输出。求广义表的表尾，并输出。求广义表的表头，并输出。·输出结果再见欢迎使用输出退出运算，并输出再见。求广义表的逆表，并输出。20三、详细设计与编码1、建立广义表CreateGL(char*&s)。在生成广义表之前，用一个数组存储广义表，并用指针s指向数组，通过数组中的元素生成广义表。基本思想是：在广义表表达式中，遇到左括号”(”时递归构造子表，否则构造原子结点；遇到逗号时递归构造后续广义表，直到字符串数组结束，以""作为结束标志。实现过程如下：GL