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

数据构造课程设计报告题目: 表达式求值广义表的运算学 院信息工程学院 专 业 计算机科学与技术年级班别_12 级四班 学号2023051419 学生姓名张海涛 指导教师米文丽 成绩_2023 年 12 月1题目：广义表的运算。本设计要求实现广义表的建立、查找、输出、取表尾、以及求深度、求逆表等。一、问题分析与任务定义：此程序需要完成以下几个任务：首先要将输入的用数组存储的广义表转化成以广义表的 存储构造存储的广义表，这个过程也就是生成广义表；查找广义表，查找广义表要返回一个 值 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，bc，d，e ，如图 310 a0 b10 c0 d1 0 e1 图 3 广义表的存储图示3、求广义表的逆表需要用堆栈存储广义表的元素，栈的数据类型如下： typedef char ElemType;typedef struct ElemType datamaxlen ; int top;SeqStack;3、程序流程图如图。main建立一个用字符数组存储的广义表，用字符指针 s 指向它输入广义表生成数组广义表构造遍历广义表建立堆栈查找待查元 素 ，flag=1，找到待查元素，反之， 没有查到。求广义表的表头，并输出。求广义表的表尾，并输出。求广义表的深度，并输出。求广义表的逆表，并输出。退出运算，并输出再见。输出结果再见 欢送使用输出4三、具体设计与编码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)输出左括号”(”；10if (g->val.hp=NULL)输出一个空格；elseelse递归调用子表；输出数据域；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、求广义表的表头：headGlist *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假设 h 为空表maxGLDepth(sh)|sh 为 h 的子表+1其他状况广义表的深度的递归定义是它等于全部子表中表的最大深度加1，假设一个表为空或仅由单个元素所组成，则深度为 1。求广义表深度的递归函数GLDepth如实现过程如下：int GLDepth(GList *g)if (g->tag=0)为原子时返回；g=g->val.hp; if (g=NULL)为空表时返回 1； while (g!=NULL)if (g->tag=1)递归调用求出子表的深度；if (dep>max)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“);elseprintf(“ 没有找到待查元素！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 王昆仑 李红 .数据构造与算法.北京：中国铁道出版社，2023 年 6 月第一版2 谭浩强.C 程序设计指导.北京：清华大学出版社,2023 年 7 月3 姚群 夏清国.数据构造.陕西：西北工业大学出版社，2023 年 6 月第一版4黄国兴 章炯民.数据构造与算法.北京：机械工业出版社，2023 年 7 月第一版九、附录#include <stdio.h> #include <malloc.h> #include<stdlib.h> #define maxlen 100 typedef char ElemType;typedef struct GLNode/广义表构造体的定义int tag; union/结点类型标识ElemType atom;/原子值struct GLNode *hp;/指向子表的指针 val;struct GLNode *tp;GList;/指向下一个元素，相当于单链表中的nexttypedef 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;/假设为“)“时，字表为空elseh->tag=0;h->val.atom=ch;/假设都不满足，则为原子结点，ch=*s;/取下一个字符s+;/指针后移if (h!=NULL)/推断是否为空if (ch=”,”)/当前字符为”,”h->tp=CreateGL(s);/递归调用后续子表elseh->tp=NULL;/否则，则后续字表为空return h;voidDispGL(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)/假设为原子结点，返回 0 return 0;g=g->val.hp; if (g=NULL)return 1; while (g!=NULL)/广义表g 被赋值为子表结点/假设广义表为空，返回值 1/假设不为空if (g->tag=1)/假设为表结点dep=GLDepth(g);/递归调用，求深度if (dep>max)max=dep;g=g->tp;return(max+1);/广义表g 被赋值为其后续子表GList *head(GList *g)/ 求广义表表头GList *p;/定义个广义表 pif (g->tag =1&&g->val.hp=NULL) /假设其为空表时，输出空表不能求表头 printf(“空表不能求表尾n“); returnNULL ;/返回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“); returnNULL ;/返回else if (g->tag=0)/假设为原子结点时，输出原子结点不能求表尾printf(“原子不能求表尾n“); return NULL;/否则，为表结点p=p->tp;/p 被赋为其后续结点t=(GList *)malloc(sizeof(GList); /申请一个结点 t t->tag=1;/t 为表结点t->tp=NULL;/t 的后续结点被赋为空t->val.hp=p;/t 的子表为p return t;void FindGListX(GList *g,char x,int &flag) / 广义表查找if(g!=NULL)if (g->tag = 0 && g->val.atom =x)/假设为原子结点，且原子结点值等于x，flag=1flag = 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 mainGList *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);printf(“你输入的广义表为：n“);while(m)DispGL(g); printf(“b n“);printf(“tt*广义表的运算*n“); printf(“ tt=n“);printf(“ tt |* 1.广义表查找 *|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,mark);if (mark)printf(“找到待查元素！n“);elseprintf(“ 没有找到待查元素！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“); elsesystem(“cls“);printf(“再见 ，欢送再次使用 ！n“);