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

1、广义表1 题目 编写一个程序，实现广义表的各种运算，并在此基础上设计一个程序完成如下功能：建立广义表g“（b,(b,a),(a,b),c)）”的链式存储结构。输出广义表g的长度。输出广义表g的深度。2 目标熟悉广义表的定义及其基本操作的实现3 设计思想链式存储的广义表，结点包含数据区，指针，以及一个标记头结点的整型数。广义表的表示结构为：（a,b）,其中a、b可以是字符或广义表。因此，可以用递归算法来实现对它的定义与操作。4 算法描述（1）创建广义表：逐个输入表示广义表的字符串，以（为起始标志建立结点并标记为头结点，递归调用此操作建立广义表；若读入）则将最后结点的指针置空；读入非结束字符，赋值

2、到结点数据区，并赋值指针形链式结构，两个结点之间打印，。（2）求广义表长度：广义表基本组成元素（a,b）若a、b不是广义表则(a,b)深度为一。广义表的深度等于表头结点的数量，从表头结点遍历广义表，对每一个广义表结点应用该函数，若tag=1（结点是表头）则返回计数器加一，否则返回0。（3）输出广义表：从表头开始，测试结点指针，若指针指向结点的标记位为1，则先打印（再输出其数据值，并调用该操作输出下一个结点；函数返回时，测试指针指向结点的标记位，若为1，则先打印)，再调用该函数输出下一个结点数据；每次输出数据值以后测试该结点是否为子广义表的最后一个结点，不是则输出，否则返回。5 程序结构图主程序

3、Main求广义表的长度GLLength(GLNode *g)求广义表的深度GLDepth(GLNode *g)输出广义表DiapGL(GLNode *g)由串s建立一个广义表CreatGL(char *&s)6 源程序#include#include#include typedef struct lnodeint tag;unionchar atom; struct lnode *p;ptr; struct lnode *q;Lnode;Lnode *CreatGL() / 创建一个广义表，表中元素为字符Lnode *h;char ch;ch=getchar();if(ch)h=(Lnode*

4、)malloc(sizeof(Lnode); /为表分配内存空间if(ch=()h-tag=1;h-ptr.p=CreatGL(); /用递归的方法实现创建广义表的操作else if(ch=)h=NULL;elseh-tag=0;h-ptr.atom=ch;else h=NULL;ch=getchar();if(h!=NULL)if(ch=,)h-q=CreatGL();elseh-q=NULL;return h;int GLLength(Lnode *g) / 求广义表的长度int n=0;g=g-ptr.p;while(g)n+;g=g-q;return n;int GLDepth(Lno

5、de *g) / 求广义表的深度int max=0,dep;if(g-tag=0)return 0;g=g-ptr.p;if(g=NULL)return 1;while(g)if(g-tag=1)dep=GLDepth(g);if(depmax)max=dep;g=g-q;return (max+1);void DispGL(Lnode *g) / 输出广义表if(g)if(g-tag=1)coutptr.p=NULL)coutptr.p);elsecoutptr.atom;if(g-tag=1)coutq)coutq);else cout广义表不存在endl;#include #includ

6、e #include#includeglist.hint main()char choice; Lnode *glist;cout键入广义表：endl;glist=CreatGL(); system(cls);printf(请选择(输入0退出)n1 输出广义表内容n2 输出广义表长度n3 输出广义表深度n);coutendlchoice; while(choice!=0) system(cls); printf(请选择(输入0退出)n1 输出广义表内容n2 输出广义表长度n3 输出广义表深度n);switch (choice)case 1:DispGL(glist);coutendl;break;case 2:cout广义表的长度为: GLLength