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

《广义表的运算-数据结构与算法课程设计报告.pdf》由会员分享，可在线阅读，更多相关《广义表的运算-数据结构与算法课程设计报告.pdf（13页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

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

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

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

5、个标志位，用来区分当前结点是原子结点还是子表。当 tag 为 1 时，该结点是子表，第二个域为 hp，用以存放子表的地址；当 tag 为 0 时，该结点是原子结点，第二个域为 atom，用以存放元素值。tp 域是用来存放与本元素同一层的下一个元素对应结点的地址，当该元素是所在层的最后一个元素时，tp 的值为 NULL。广义表及结点类型描述如下：typedef char ElemType;typedef struct GLode 广义表的深度 GLDepth(GList*g)。tag=0 atom*tp tag=1*hp*tp main()建立一个用字符数组存储的广义输入广义表 生成数组广义表结

6、构 遍历广义表 建立堆栈 广义表的深度的递归定义是它等于所有子表中表的最大深度加 1，若一个表为空或仅由单个元素所组成，则深度为 1。求广义表深度的递归函数 GLDepth（）如 实现过程如下：int GLDepth(GList*g)if(g-tag=0)为原子时返回；g=g-;if (g=NULL)为空表时返回 1；while(g!=NULL)if(g-tag=1)递归调用求出子表的深度；if(depmax)max 为同一层所求过的子表中深度的最大值；使 g 指向下一个元素；返回表的深度(max+1)。7、求广义表的逆表 NIGList(GList*g,SeqStack*s)求广义表的逆表的

7、算法思想是：利用广义表的遍历将广义表的元素存入一个堆栈中，然后在将栈中所有的元素出栈打印，函数的实现如下：将广义表中的元素存入堆栈中：void NIGList(GList*g,SeqStack*s)if(g!=NULL)输出 结果 1 若 h 为空表 maxGLDepth(sh)|sh 为 h 的子表+1 其他情况 if(g-tag=1)将广义表中的“(”以“)”存入栈中；else 递归调用，将子表中的元素存入栈中；else 将广义表中的元素存入栈中；if(g-tag=1)将广义表中的)以(存入栈中；if(g-tp!=NULL)将广义表中的,存入栈中；递归将后续表的内容存入栈中。将栈中所有元素

8、输出：void Pop(SeqStack*s)打印栈中元素。四、上机调试 1、调试函数 FindGListX(GList*g,char x,int flag)时，函数起不了作用，对于 flag 的值不能做改变，在 mian 函数中使用两个 scanf（）函数，后面一个函数得不到运行。解决办法：在 scanf()函数前加 getchar（），如下面的程序所示：flag=0;getchar();scanf(%c,&x);FindGListX(g,x,flag);if(flag)printf(找到待查元素！n);else printf(没有找到待查元素！n);break;2.程序运行后出现图 5 的

9、错误：图 5 错误 2 解决办法：在 while 循环中加入以下程序：printf(是否继续：1.继续；0.停止n);printf(请选择：);scanf(%d,&xz);if(xz=1)system(cls);else system(cls);printf(再 见 ！n);3.求表尾函数错误，当输入空表时，不能输出空表不能求表尾这句提示语。如图 6 所示：图 6 错误 3 解决方法:把语句 if(g=NULL)改成 if(g-tag=1&g-=NULL),因为空表为表结点，且空表没子表，所以这话就可以判断出广义表是否为空表了。五、测试结果及其分析 1、查找广义表中的元素：（1）待查元素在广义

10、表中的运行结果如图 9：图 9 找到待查元素 （2）待查元素不在广义表中的运行结果如图 10 所示：图 10 没有找到待查元素 2、求表头运行结果如图 11 所示：图 11 求广义表的表头 3、求广义表的表尾运行结果如图 12 所示：图 12 求广义表的表头 4、求广义表的深度的运行结果如图 13 所示：图 13 求广义表的深度 5、求广义表的逆表的运行结果如图 14 所示；图 14 求广义表的逆表、退出广义表的运行结果如图 15 所示 图 15 求广义表的逆表 六、用户使用说明 本程序运行过程时带有提示性语句，用户可以根据需要和提示进行操作：1、运行程序，程序提示输入广义表，出现运行界面；2

11、、查找广义表中的元素。选择 1，程序提示，输入要查找的元素，若该元素在广义表中，程序显示：找到待查元素。否则显示:找不到待查元素；3、求广义表的表头。选择 2，程序输出所求广义表的表头；4、求广义表的表尾。选择 3，程序输出所求广义表的表尾 5、求广义表的深度。选择 4，程序输出广义表的深度；6、求广义表的逆表。选择 5，程序输出广义表的逆表；7、选择 0，退出广义表的运算，程序终止；8、每次操作结束以后，会有提示语句：是否继续执行其他操作(选择 1、继续；0、停止)。七、总结 1、广义表的运算包括广义表的建立、查找、求表头、求表尾、求深度、广义表删除、求逆表，依据原子结点和结点的存储结构不同

12、，进行相应的操作。2、程序中多次使用递归调用。3、使用联合体建立广义表的数据类型。4、根据栈的特点将广义表逆置输出。5、程序中使用 switch 函数，将每个操作分开进行。八、参考书目 1王昆仑 李红.数据结构与算法.北京：中国铁道出版社，2007 年 6 月第一版 2 谭浩强.C 程序设计指导.北京：清华大学出版社,2005 年 7 月 3姚群 夏清国.数据结构.陕西：西北工业大学出版社，2004 年 6 月第一版 4黄国兴 章炯民.数据结构与算法.北京：机械工业出版社，2004 年 7 月第一版 九、附录#include#include#include#define maxlen 100

13、typedef char ElemType;typedef struct GLNode 义表查找 *|n);printf(tt|*2.求广义表头 *|n);printf(tt|*3.求广义表尾 *|n);printf(tt|*4.求广义表深度*|n);printf(tt|*5.求广义表逆表*|n);printf(tt|*0.退出表的运算*|n);printf(tt=n);printf(请 选 择:(05)n);scanf(%d,&y);switch(y)case 1:printf(请输入要查找的元素：n);mark=0;getchar();scanf(%c,&x);FindGListX(g,x

14、,mark);if(mark)printf(找到待查元素！n);else printf(没有找到待查元素！n);break;case 2:gt=head(g);printf(表头:);DispGL(gt);printf(b n);break;case 3:gt=tail(g);printf(表尾:);DispGL(gt);printf(b n);break;case 4:printf(广义表的深度:%dn,GLDepth(g);break;case 5:printf(所求广义表的逆表为：n);NIGList(g,k);Pop(k);printf(n);break;default:system(cls);printf(再 见，欢迎再次使用！n);return;printf(是否继续：1.继续；0.停止n);printf(请选择：n);scanf(%d,&m);if(m=1)system(cls);else system(cls);printf(再 见，欢迎再次使用！n);