表达式求值广义表的运算课程设计报告.doc

数据结构课程设计报告题目: 表达式求值广义表的运算学 院 信息工程学院 _专 业 _ 计算机科学与技术年级班别 _12级四班_学 号 2012051419_学生姓名 张海涛_指导教师 米文丽_成 绩 _2013年12月 题目：广义表的运算。本设计要求实现广义表的建立、查找、输出、取表尾、以及求深度、求逆表等。一、问题分析与任务定义：此程序需要完成以下几个任务：首先要将输入的用数组存储的广义表转化成以广义表的存储结构存储的广义表，这个过程也就是生成广义表；查找广义表，查找广义表要返回一个值flag，当flag=1时，程序查找到待查的元素，当flag=0时，程序没有找到待查元素；输出广义表，遍历广义表，输出广义表的遍历结果；取表头，返回表头结点；取表尾，将广义表从第二个元素开始复制到另一个广义表中；求广义表的深度，遍历每一层广义表，将广义表内每层广义表深度最大的广义表相加为同一层所求过的子表中深度的最大值，最后返回值加一即为广义表的深度；求逆表，将广义表逆向输出。实现本程序需要解决以下问题：1、 如何根据广义表的特点建立广义表。2、 用什么方法才能查找到广义表中每一个元素，如何标志是否找到待查元素。3、 建立广义表，如何根据广义表的存储结构的特点建立广义表。4、 求广义表的深度的依据是什么。5、 运用什么方法才能将广义表逆序。6、 如何实现广义表的遍历。二、概要设计和数据结构选择：1、设计思想：广义表是线性表的一种推广，但它并不是线性表。课本上在介绍广义表的计本概念的基础上，介绍了广义表的存储及应用。广义表浓缩了线性表、数组等常见的数据结构的特点，在有效利用存储空间方面更胜一筹，目前在文本处理、人工智能、代数操作和计算机图形方面等各个领域都具有应用价值。所以在我当时拿到这个题目的时候，虽然它只有短短的几行字，但是我深深的感觉到了它的难度，在后来课程设计中，也证实了我的感觉，每个功能都实在是太难实现了，所以只有各个击破了。设计程序时，先起草了流程图，通过流程图来看，就使得程序鲜明易懂，接下来先写好了主函数，通过主函数的调用，实现题目要求的各个功能，使得程序模块化，便于编写，即使不会写的子函数，也可以先空着，等待以后想到好的方法后再对其进行操作，同时在程序界面上也做了美化，使人感觉舒畅，另外通过一个循环，能让用户进行循环操作，不至于每次只能进行一项操作,这个循环用的和线性表里的循环有点类似，但其实现的操作不同，当然有了以前实验的基础，这次编写起来，也感觉轻松了不少。2、广义表的存储结构：由于广义表中的元素本身又可以具有结构，是一种带有层次的非线性结构，因此难以用顺序存储的结构表示。通常采用链式存储结构，每个元素可用一个结点表示，结点结构如图1、图2所示：tag=0atom*tp 图1原子结点的存储结构tag=1*hp*tp 图2结点的存储结构每个结点由三个域构成。其中tag是一个标志位，用来区分当前结点是原子结点还是子表。当tag为1时，该结点是子表，第二个域为hp，用以存放子表的地址；当tag为0时，该结点是原子结点，第二个域为atom，用以存放元素值。tp域是用来存放与本元素同一层的下一个元素对应结点的地址，当该元素是所在层的最后一个元素时，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 1 0a0b1 0c0d10e1 图3 广义表的存储图示3、求广义表的逆表需要用堆栈存储广义表的元素，栈的数据类型如下：typedef char ElemType;typedef struct ElemType datamaxlen ; int top;SeqStack;3、程序流程图如图。main()建立一个用字符数组存储的广义表，用字符指针s指向它输入广义表生成数组广义表结构遍历广义表建立堆栈查找待查元素，flag=1，找到待查元素，反之，没有查到。求广义表的深度，并输出。求广义表的表尾，并输出。求广义表的表头，并输出。输出结果再见 欢迎使用输出退出运算，并输出再见。求广义表的逆表，并输出。 三、详细设计与编码1、建立广义表CreateGL(char *&s)。在生成广义表之前，用一个数组存储广义表，并用指针s指向数组，通过数组中的元素生成广义表。基本思想是：在广义表表达式中，遇到左括号”(”时递归构造子表，否则构造原子结点；遇到逗号时递归构造后续广义表，直到字符串数组结束，以0作为结束标志。实现过程如下：GList *CreateGL(char *&s) 读入广义表的一个字符给ch； if (ch!=空格) if (ch=() 递归构造子表；else if (ch=) 遇到)字符,子表为空else 构造原子结点；else 串结束,子表为空读入广义表的一个字符给ch；if (ch=,) 递归构造后续子表；else 处理表的最后一个元素 返回广义表指针2、遍历广义表DispGL(GList *g)。输出广义表采用的算法思想是：若遇到tag=1的结点，这是一个子表的开始，先打印输出一个左括号”(”。如果该子表为空，则输出一个空格符；否则递归调用输出该子表。子表打印输出完后，再打印一个右括号”)”。若遇到tag=0的结点，则直接输出其数据域的值。若还有后续元素，则递归调用打印后续每个元素，直到遇到tp=NULL。其实现过程如下：void DispGL(GList *g)if (g!=NULL) if (g-tag=1) 输出左括号(；if (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,char x,int &mark)if(g!=NULL)if (g-tag = 0 & g-val.atom =x) 查找成功mark = 1;else if(g-tag = 1) 递归调用查找后续元素；递归查找调用后续元素；4、求广义表的表头：head（Glist *g）GList *head(GList *g) GList *p; if (g-tag =1&g-val.hp=NULL) 空表不能求表头；else 返回表头结点 5、求广义表的表尾：tail(GList *g)一个广义表的表尾指的是除去该广义表的第一个元素剩下的部分。求表尾实现过程如下：GList *tail(GList *g)if (g=NULL) 空表不能求表尾；else if (g-tag=0) 原子不能求表尾；将广义表除去第一个元素，其余的元素复制的广义表q中，既为该广义表的表尾。return q;6.求广义表的深度GLDepth(GList *g)。广义表的深度的递归定义是它等于所有子表中表的最大深度加1，若一个表为空或仅由单个元素所组成，则深度为1。求广义表深度的递归函数GLDepth（）如 输出结果1 若h为空表maxGLDepth(sh)|sh为h的子表+1 其他情况实现过程如下：int GLDepth(GList *g) if (g-tag=0)为原子时返回；g=g-val.hp;if (g=NULL)为空表时返回1；while (g!=NULL) if (g-tag=1) 递归调用求出子表的深度；if (depmax) max为同一层所求过的子表中深度的最大值； 使g指向下一个元素；返回表的深度(max+1) 。 7、求广义表的逆表NIGList(GList *g,SeqStack *s)求广义表的逆表的算法思想是：利用广义表的遍历将广义表的元素存入一个堆栈中，然后在将栈中所有的元素出栈打印，函数的实现如下：将广义表中的元素存入堆栈中：void NIGList(GList *g,SeqStack *s)if(g!=NULL) if (g-tag=1) 将广义表中的“(”以“)”存入栈中；else递归调用，将子表中的元素存入栈中；else将广义表中的元素存入栈中；if (g-tag=1) 将广义表中的)以(存入栈中；if (g-tp!=NULL) 将广义表中的,存入栈中；递归将后续表的内容存入栈中。将栈中所有元素输出：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的错误：图5 错误2解决办法：在while循环中加入以下程序：printf(是否继续：1.继续；0.停止n); printf(请选择：); scanf(%d,&xz); if(xz=1) system(cls); elsesystem(cls);printf(再 见 ！n);3.求表尾函数错误，当输入空表时，不能输出空表不能求表尾这句提示语。如图6所示：图6 错误3解决方法: 把语句if(g=NULL)改成if (g-tag =1&g-val.hp=NULL),因为空表为表结点，且空表没子表，所以这话就可以判断出广义表是否为空表了。五、测试结果及其分析1、查找广义表中的元素：（1）待查元素在广义表中的运行结果如图9：图9 找到待查元素（2）待查元素不在广义表中的运行结果如图10所示：图10 没有找到待查元素2、求表头运行结果如图11所示：图11求广义表的表头3、求广义表的表尾运行结果如图12所示：图12求广义表的表头4、求广义表的深度的运行结果如图13所示：图13求广义表的深度5、求广义表的逆表的运行结果如图14所示；图14求广义表的逆表、退出广义表的运行结果如图15所示 图15求广义表的逆表六、用户使用说明本程序运行过程时带有提示性语句，用户可以根据需要和提示进行操作：1、运行程序，程序提示输入广义表，出现运行界面；2、查找广义表中的元素。选择1，程序提示，输入要查找的元素，若该元素在广义表中，程序显示：找到待查元素。否则显示:找不到待查元素；3、求广义表的表头。选择2，程序输出所求广义表的表头；4、求广义表的表尾。选择3，程序输出所求广义表的表尾5、求广义表的深度。选择4，程序输出广义表的深度；6、求广义表的逆表。选择5，程序输出广义表的逆表；7、选择0，退出广义表的运算，程序终止；8、每次操作结束以后，会有提示语句：是否继续执行其他操作(选择1、继续 ；0、停止)。七、总结1、广义表的运算包括广义表的建立、查找、求表头、求表尾、求深度、广义表删除、求逆表，依据原子结点和结点的存储结构不同，进行相应的操作。2、程序中多次使用递归调用。3、使用联合体建立广义表的数据类型。4、根据栈的特点将广义表逆置输出。5、程序中使用switch函数，将每个操作分开进行。八、参考书目1王昆仑 李红 .数据结构与算法.北京：中国铁道出版社，2007年6月第一版2 谭浩强.C程序设计指导.北京：清华大学出版社,2005年7月3姚群 夏清国.数据结构.陕西：西北工业大学出版社，2004年6月第一版4黄国兴 章炯民.数据结构与算法.北京：机械工业出版社，2004年7月第一版九、附录#include #include #include#define maxlen 100typedef char ElemType;typedef struct GLNode /广义表结构体的定义int tag; /结点类型标识unionElemType atom; /原子值struct GLNode *hp; /指向子表的指针 val;struct GLNode *tp; /指向下一个元素，相当于单链表中的nextGList;typedef struct /栈结构的定义ElemType datamaxlen ;int top;SeqStack;GList *CreateGL(char *&s) /建立广义表 ,生成广义表的链式存储结构GList *h; /定义个新广义表char ch; ch=*s; /取一个扫描字符 s+; /往后扫描字符 if(ch!=0) /判断是否为回车，若不是，则执行下面操作 h=(GList *)malloc(sizeof(GList); /动态申请个新广义表 if (ch=() /若当前字符为(时，执行下列操作h-tag=1; /新节点做为表头节点h-val.hp=CreateGL(s); /递归调用字表，链接到表头结点上else if (ch=)h=NULL; /若为)时，字表为空else h-tag=0; h-val.atom=ch; /若都不满足，则为原子结点， ch=*s; /取下一个字符 s+; /指针后移 if (h!=NULL) /判断是否为空 if (ch=,) /当前字符为, h-tp=CreateGL(s); /递归调用后续子表 else h-tp=NULL; /否则，则后续字表为空return h; void DispGL(GList *g) /遍历广义表 if(g=NULL) return ; /若广义表为空，则返回if(g-tag=0)printf( %c ,g-val.atom); /若广义表g为原子结点，则直接输出其值else /否则为表结点，则输出(printf( );for(g=g-val.hp;g;g=g-tp) /从字表表头开始，依次遍历其后续子表 DispGL(g); printf(b),); int GLDepth(GList *g) /求广义表的深度 int max=0,dep; /定义变量if (g-tag=0) /若为原子结点，返回0return 0; g=g-val.hp; /广义表g被赋值为子表结点if (g=NULL) /若广义表为空，返回值1return 1;while (g!=NULL) /若不为空if (g-tag=1) /若为表结点dep=GLDepth(g); /递归调用，求深度if (depmax) max=dep; g=g-tp; /广义表g被赋值为其后续子表 return(max+1); GList *head(GList *g) / 求广义表表头GList *p; /定义个新广义表pif (g-tag =1&g-val.hp=NULL) /若其为空表时，输出空表不能求表头 printf(空表不能求表尾n);return NULL ; /返回 else p=g-val.hp; /不为空表时，返回广义表g的子表表头结点 return p; GList *tail(GList *g) / 求广义表表尾GList *p; /定义个新广义表pp=g-val.hp; /P被赋值为广义表g的表头结点 GList *t;if (g-tag =1&g-val.hp=NULL) /若其为空表时，输出空表不能求表尾 printf(空表不能求表尾n);return NULL ; /返回 else if (g-tag=0) /若为原子结点时，输出原子结点不能求表尾 printf(原子不能求表尾n);return NULL; /否则，为表结点p=p-tp; /p被赋为其后续结点t=(GList *)malloc(sizeof(GList); /申请一个新结点tt-tag=1; /t为表结点t-tp=NULL; /t的后续结点被赋为空t-val.hp=p; /t的子表为preturn t;void FindGListX(GList *g,char x,int &flag) / 广义表查找if(g!=NULL)if (g-tag = 0 & g-val.atom =x) /若为原子结点，且原子结点值等于x，flag=1 flag = 1; else if(g-tag = 1) /若为表结点FindGListX(g-val.hp,x,flag); /递归调用其子表的表头结点FindGListX(g-tp,x,flag); /递归调用其后续结点void NIGList(GList *g,SeqStack *s) /求广义表的逆表if(g!=NULL) if (g-tag=1) /若为表结点时s-top+;s-datas-top=); /将广义表中的(以“)”存入栈中if (g-val.hp=NULL) printf();elseNIGList(g-val.hp,s); /递归调用将子表存入栈中else /若为原子结点时 s-top+; s-datas-top=g-val.atom; /直接将原子结点值如栈if (g-tag=1)s-top+; s-datas-top=(; /将广义表中的)以(存入栈中 if (g-tp!=NULL)s-top+;s-datas-top=,; /将广义表中的,存入栈中 NIGList(g-tp,s); /递归调用将后续表的内容存入栈中void Pop(SeqStack *s) /广义表的输出 while(s-top=0) printf(%c,s-datas-top);s-top-;void main()GList *g,*gt; system(color 1B );printf(请输入一个广义表：如(a,(b),c)n);char str30; char x; int y=0,mark,m=1; SeqStack *k;k=(SeqStack *)malloc(sizeof(SeqStack);k-top=-1; char *s=gets(str); g=CreateGL(s