数据结构与算法问题分析及源代码之广义表

广义表1题目编写一个程序，实现广义表的各种运算，并在此基础上设计一个程序完成如下功能：建立广义表g＝“（b,(b,a),((a,b),c)）”的链式存储结构。输出广义表g的长度。输出广义表g的深度。2目标熟悉广义表的定义及其基本操作的实现3设计思想链式存储的广义表，结点包含数据区，指针，以及一个标记头结点的整型数。广义表的表示结构为：（a,b）,其中a、b可以是字符或广义表。因此，可以用递归算法来实现对它的定义与操作。4算法描述（1）创建广义表：逐个输入表示广义表的字符串，以‘（’为起始标志建立结点并标记为头结点，递归调用此操作建立广义表；若读入‘）’则将最后结点的指针置空；读入非结束字符，赋值到结点数据区，并赋值指针形链式结构，两个结点之间打印‘，’。（2）求广义表长度：广义表基本组成元素（a,b）若a、b不是广义表则(a,b)深度为一。广义表的深度等于表头结点的数量，从表头结点遍历广义表，对每一个广义表结点应用该函数，若tag==1（结点是表头）则返回计数器加一，否则返回0。（3）输出广义表：从表头开始，测试结点指针，若指针指向结点的标记位为1，则先打印‘（’再输出其数据值，并调用该操作输出下一个结点；函数返回时，测试指针指向结点的标记位，若为1，则先打印‘)’，再调用该函数输出下一个结点数据；每次输出数据值以后测试该结点是否为子广义表的最后一个结点，不是则输出‘，’，否则返回。5程序结构图6源程序#includeiostream.h#includemalloc.h#includestdio.htypedefstructlnode{inttag;union{主程序Main求广义表的长度GLLength(GLNode*g)求广义表的深度GLDepth(GLNode*g)输出广义表DiapGL(GLNode*g)由串s建立一个广义表CreatGL(char*&s)charatom;structlnode*p;}ptr;structlnode*q;}Lnode;Lnode*CreatGL(){//创建一个广义表，表中元素为字符Lnode*h;charch;ch=getchar();if(ch){h=(Lnode*)malloc(sizeof(Lnode));//为表分配内存空间if(ch=='('){h-tag=1;h-ptr.p=CreatGL();//用递归的方法实现创建广义表的操作}elseif(ch==')')h=NULL;else{h-tag=0;h-ptr.atom=ch;}}elseh=NULL;ch=getchar();if(h!=NULL)if(ch==',')h-q=CreatGL();elseh-q=NULL;returnh;}intGLLength(Lnode*g){//求广义表的长度intn=0;g=g-ptr.p;while(g){n++;g=g-q;}returnn;}intGLDepth(Lnode*g){//求广义表的深度intmax=0,dep;if(g-tag==0)return0;g=g-ptr.p;if(g==NULL)return1;while(g){if(g-tag==1){dep=GLDepth(g);if(depmax)max=dep;}g=g-q;}return(max+1);}voidDispGL(Lnode*g){//输出广义表if(g){if(g-tag==1){cout(;if(g-ptr.p==NULL)cout;elseDispGL(g-ptr.p);}elsecoutg-ptr.atom;if(g-tag==1)cout);if(g-q){cout,;DispGL(g-q);}}elsecout广义表不存在endl;}#includestdio.h#includestdlib.h#includeiostream.h#includeglist.hintmain(){charchoice;Lnode*glist;cout键入广义表：endl;glist=CreatGL();system(cls);printf(请选择(输入0退出)\n1输出广义表内容\n2输出广义表长度\n3输出广义表深度\n);coutendl选择：;cinchoice;while(choice!='0'){system(cls);printf(请选择(输入0退出)\n1输出广义表内容\n2输出广义表长度\n3输出广义表深度\n);switch(choice){case'1':DispGL(glist);coutendl;break;case'2':cout广义表的长度为:GLLength(glist)endl;break;case'3':cout广义表深度为：GLDepth(glist)endl;break;case'0':return0;}coutendl选择：;cinchoice;}