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

合肥学院计算机科学与技术系课程设计报告2009～2010学年第二学期课程数据结构与算法课程设计名称广义表的运算学生姓名陈发银学号0804012028专业班级08计本（2）班指导教师王昆仑2010年6月1题目：广义表的运算。本设计要求实现广义表的建立、查找、输出、取表尾、以及求深度、求逆表等。一、问题分析与任务定义：此程序需要完成以下几个任务：首先要将输入的用数组存储的广义表转化成以广义表的存储结构存储的广义表，这个过程也就是生成广义表；查找广义表，查找广义表要返回一个值flag，当flag=1时，程序查找到待查的元素，当flag=0时，程序没有找到待查元素；输出广义表，遍历广义表，输出广义表的遍历结果；取表头，返回表头结点；取表尾，将广义表从第二个元素开始复制到另一个广义表中；求广义表的深度，遍历每一层广义表，将广义表内每层广义表深度最大的广义表相加为同一层所求过的子表中深度的最大值，最后返回值加一即为广义表的深度；求逆表，将广义表逆向输出。实现本程序需要解决以下问题：1、如何根据广义表的特点建立广义表。2、用什么方法才能查找到广义表中每一个元素，如何标志是否找到待查元素。3、建立广义表，如何根据广义表的存储结构的特点建立广义表。4、求广义表的深度的依据是什么。5、运用什么方法才能将广义表逆序。6、如何实现广义表的遍历。二、概要设计和数据结构选择：1、设计思想：广义表是线性表的一种推广，但它并不是线性表。课本上在介绍广义表的计本概念的基础上，介绍了广义表的存储及应用。广义表浓缩了线性表、数组等常见的数据结构的特点，在有效利用存储空间方面更胜一筹，目前在文本处理、人工智能、代数操作和计算机图形方面等各个领域都具有应用价值。所以在我当时拿到这个题目的时候，虽然它只有短短的几行字，但是我深深的感觉到了它的难度，在后来课程设计中，也证实了我的感觉，每个功能都实在是太难实现了，所以只有各个击破了。设计程序时，先起草了流程图，通过流程图来看，就使得程序鲜明易懂，接下来先写好了主函数，通过主函数的调用，实现题目要求的各个功能，使得程序模块化，便于编写，即使不会写的子函数，也可以先空着，等待以后想到好的方法后再对其进行操作，同时在程序界面上也做了美化，使人感觉舒畅，另外通过一个循环，能让用户进行循环操作，不至于每次只能进行一项操作,这个循环用的和线性表里的循环有点类似，但其实现的操作不同，当然有了以前实验的基础，这次编写起来，也感觉轻松了不少。2、广义表的存储结构：由于广义表中的元素本身又可以具有结构，是一种带有层次的非线性结构，因此难以用顺序存储的结构表示。通常采用链式存储结构，每个元素可用一个结点表示，结点结构如图1、图2所示：图1原子结点的存储结构tag=0atom*tp2图2结点的存储结构每个结点由三个域构成。其中tag是一个标志位，用来区分当前结点是原子结点还是子表。当tag为1时，该结点是子表，第二个域为hp，用以存放子表的地址；当tag为0时，该结点是原子结点，第二个域为atom，用以存放元素值。tp域是用来存放与本元素同一层的下一个元素对应结点的地址，当该元素是所在层的最后一个元素时，tp的值为NULL。广义表及结点类型描述如下：typedefcharElemType;typedefstructGLode//广义表结构体的定义{inttag;/*结点类型标识*/union{ElemTypeatom;/*原子值*/structGLode*hp;/*指向子表的指针*/}val;structGLode*tp;/*指向下一个元素*/}GList;例如：建立广义表：（a，b（c，d），e），如图3图3广义表的存储图示3、求广义表的逆表需要用堆栈存储广义表的元素，栈的数据类型如下：typedefcharElemType;typedefstruct{ElemTypedata[maxlen];inttop;}SeqStack;tag=1*hp*tp1^0a0b1^0c0d1^0e1^^33、程序流程图如图。main()建立一个用字符数组存储的广义表，用字符指针s指向它输入广义表生成数组广义表结构遍历广义表建立堆栈查找待查元素，flag=1，找到待查元素，反之，没有查到。求广义表的深度，并输出。求广义表的表尾，并输出。求广义表的表头，并输出。44输出结果再见欢迎使用输出退出运算，并输出再见。求广义表的逆表，并输出。4三、详细设计与编码1、建立广义表CreateGL(char*&s)。在生成广义表之前，用一个数组存储广义表，并用指针s指向数组，通过数组中的元素生成广义表。基本思想是：在广义表表达式中，遇到左括号”(”时递归构造子表，否则构造原子结点；遇到逗号时递归构造后续广义表，直到字符串数组结束，以\0作为结束标志。实现过程如下：GList*CreateGL(char*&s){读入广义表的一个字符给ch；if(ch!=空格'){if(ch=='('){递归构造子表；}elseif(ch==')')遇到')'字符,子表为空else{构造原子结点；}}else串结束,子表为空读入广义表的一个字符给ch；if(ch==',')递归构造后续子表；else处理表的最后一个元素返回广义表指针}2、遍历广义表DispGL(GList*g)。输出广义表采用的算法思想是：若遇到tag=1的结点，这是一个子表的开始，先打印输出一个左括号”(”。如果该子表为空，则输出一个空格符；否则递归调用输出该子表。子表打印输出完后，再打印一个右括号”)”。若遇到tag=0的结点，则直接输出其数据域的值。若还有后续元素，则递归调用打印后续每个元素，直到遇到tp=NULL。其实现过程如下：voidDispGL(GList*g){if(g!=NULL){if(g-tag==1){输出左括号'('；5if(g-val.hp==NULL)输出一个空格；else递归调用子表；}else输出数据域；if(g-tag==1)打印有括号“）”；if(g-tp!=NULL)输出逗号“，”，递归调用输出下一个结点。}}3、广义表的查找：FindGListX()在给定的广义表种查找数据域为x的结点，采用的算法思想是：若遇到tag=0的原子结点，如果是要查找的结点，则查找成功1；否则，若还有后续元素，则递归调用本过程在孩子表中查找，若还有后续元素，则递归调用本过程查找后续每个元素，直到遇到hp域为NULL的元素。设置flag标志查找结果；flag=1；表示查找成功，否则查找失败。本函数实现过程如下：FindGListX(GList*g,charx,int&mark){if(g!=NULL){if(g-tag==0&&g-val.atom==x){查找成功mark=1;}elseif(g-tag==1)递归调用查找后续元素；递归查找调用后续元素；}}4、求广义表的表头：head（Glist*g）GList*head(GList*g){GList*p;if(g-tag==1&&g-val.hp==NULL){空表不能求表头；}else{返回表头结点}}65、求广义表的表尾：tail(GList*g)一个广义表的表尾指的是除去该广义表的第一个元素剩下的部分。求表尾实现过程如下：GList*tail(GList*g){if(g==NULL){空表不能求表尾；}elseif(g-tag==0){原子不能求表尾；}将广义表除去第一个元素，其余的元素复制的广义表q中，既为该广义表的表尾。returnq;}6.求广义表的深度GLDepth(GList*g)。广义表的深度的递归定义是它等于所有子表中表的最大深度加1，若一个表为空或仅由单个元素所组成，则深度为1。求广义表深度的递归函数GLDepth（）如实现过程如下：intGLDepth(GList*g){if(g-tag==0)为原子时返回；g=g-val.hp;if(g==NULL)为空表时返回1；while(g!=NULL){if(g-tag==1){递归调用求出子表的深度；if(depmax)max为同一层所求过的子表中深度的最大值；}输出结果1若h为空表max{GLDepth(sh)|sh为h的子表}+1其他情况7使g指向下一个元素；}返回表的深度(max+1)。}7、求广义表的逆表NIGList(GList*g,SeqStack*s)求广义表的逆表的算法思想是：利用广义表的遍历将广义表的元素存入一个堆栈中，然后在将栈中所有的元素出栈打印，函数的实现如下：将广义表中的元素存入堆栈中：voidNIGList(GList*g,SeqStack*s){if(g!=NULL){if(g-tag==1){将广义表中的“(”以“)”存入栈中；else递归调用，将子表中的元素存入栈中；}else将广义表中的元素存入栈中；if(g-tag==1)将广义表中的)以(存入栈中；if(g-tp!=NULL)将广义表中的,存入栈中；递归将后续表的内容存入栈中。}}将栈中所有元素输出：voidPop(SeqStack*s){打印栈中元素。}8四、上机调试1、调试函数FindGListX(GList*g,charx,intflag)时，函数起不了作用，对于flag的值不能做改变，在mian函数中使用两个scanf（）函数，后面一个函数得不到运行。解决办法：在scanf()函数前加getchar（），如下面的程序所示：flag=0;getchar();scanf(%c,&x);FindGListX(g,x,flag);if(flag)printf(找到待查元素！\n);elseprintf(没有找到待查元素！\n);break;2.程序运行后出现图5的错误：图5错误2解决办法：在while循环中加入以下程序：printf(是否继续：1.继续；0.停止\n);printf(请选择：);scanf(%d,&xz);if(xz==1)system(cls);else9{system(cls);printf(再见！\n);}3.求表尾函数错误，当输入空表时，不能输出空表不能求表尾这句提示语。如图6所示：图6错误3解决方法:把语句if(g=NULL)改成if(g-tag==1&&g-val.hp==NULL),因为空表为表结点，且空表没子表，所以这话就可以判断出广义表是否为空表了。五、测试结果及其分析1、查找广义表中的元素：（1）待查元素在广义表中的运行结果如图9：10图9找到待查元素（2）待查元素不在广义表中的运行结果如图10所示：图10没有找到待查元素112、求表头运行结果如图11所示：图11求广义表的表头3、求广义表的表尾运行结果如图12所示：图12求广义表的表头124、求广义表的深度的运行结果如图13所示：图13求广义表的深度5、求广义表的逆表的运行结果如图14所示；图14求广义表的逆表６、退出广义表的运行结果如图15所示图15求广义表的逆表13六、用户使用说明本程序运行过程时带有提示性语句，用户可以根据需要和提示进行操作：1、运行程序，程序提示输入广义表，出现运行界面；2、查找广义表中的元素。选择1，程序提示，输入要查找的元素，若该元素在广义表中，程序显示：找到待查元素。否则显示:找不到待查元素；3、求广义表的表头。选择2，程序输出所求广义表的表头；4、求广义表的表尾。选择3，程序输出所求广义表的表尾5、求广义表的深度。选择4，程序输出广义表的深度；6、求广义表的逆表。选择5，程序输出广义表的逆表；7、选择0，退出广义表的运算，程序终止；8、每次操作结束以后，会有提示语句：是否继续执行其他操作(选择1、继续；0、停止)。七、总结1、广义表的运算包括广义表的建立、查找、求表头、求表尾、求深度、广义表删除、求逆表，依据原子结点和结点的存储结构不同，进行相应的操作。2、程序中多次使用递归调用。3、使用联合体建立广义表的数据类型。4、根据栈的特点将广义表逆置输出。5、程序中使用switch函数，将每个操作分开进行。八、参考书目[1]王昆仑李红.