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

《数据结构与算法问题分析及源代码之广义表》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

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，则先打印‘)’，再调用该函数输出下一个结点数据；每次输出数据值以后测试该结点是否为子广义表的最后一个结点，不

3、是则输出‘，’，否则返回。5程序结构图主程序Main求广义表的长度GLLength(GLNode*g)求广义表的深度GLDepth(GLNode*g)输出广义表DiapGL(GLNode*g)由串s建立一个广义表CreatGL(char*&s)6源程序#include#include#includetypedefstructlnode{inttag;union{charatom;structlnode*p;}ptr;structlnode*q;}Lnode;Lnode*CreatGL(){//创建一个广义表，表中元素为字

4、符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)

5、{//求广义表的长度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(dep>max)max=dep;}g=g->q;}return(max+1);}voidDispGL(Lnode*g){//输出广义表if(g){if(g->tag==1){cout<<"(";if(g-

6、>ptr.p==NULL)cout<<"";elseDispGL(g->ptr.p);}elsecout<ptr.atom;if(g->tag==1)cout<<")";if(g->q){cout<<",";DispGL(g->q);}}elsecout<<"广义表不存在"<#include#include#include"glist.h"intmain(){charchoice;Lnode*glist;cout<<"键入广义表："<

7、tem("cls");printf("请选择(输入0退出)1输出广义表内容2输出广义表长度3输出广义表深度");cout<>choice;while(choice!='0'){system("cls");printf("请选择(输入0退出)1输出广义表内容2输出广义表长度3输出广义表深度");switch(choice){case'1':DispGL(glist);cout<