Question

c语言广义表

麻烦哪位大虾写一个广义表的创建，输出及求深度，广度的程序，拜托了！

Answer 1

网上搜了个类似程序，希望满足你要求：

#include<stdafx.h>
#include<stdio.h>
#include<string.h>
#include<stdlib.h>

typedef char ElemType;

//自定义结构体存放广义表中单元素节点和字表节点
typedef struct lnode
{
int tag;
union
{
ElemType data;
struct lnode *sublist;
}val;
struct lnode *next;
}GLNode;

//自定义函数来实现广义表创建

void creatGList(struct lnode **gl)
{
char ch;
ch=getchar();
if(ch=='#')
*gl=NULL;
else if(ch=='(') //输入左括号则递归构造字表
{
*gl=(lnode*)malloc(sizeof(struct lnode));
(*gl)->tag=1;
creatGList(&((*gl)->val.sublist));
}
else //输入为字符则建立单元素节点
{
*gl=(lnode*)malloc(sizeof(struct lnode));
(*gl)->tag=0;
(*gl)->val.data=ch;
}
ch=getchar();
if(*gl==NULL) ;
else if(ch==',') //若输入为逗号则递归构建后继表
creatGList(&((*gl)->next));
else
(*gl)->next=NULL;

return;
}

//自定义函数实现广义表输出
void printGList(struct lnode *gl)
{
if(gl->tag==1)//判断是否存在字表
{
printf("(");
if(gl->val.sublist==NULL)
printf("#");

else printGList(gl->val.sublist);//递归输出字表
printf(")");
}
else
printf("%c",gl->val.data);//单个元素则直接输出

if(gl->next!=NULL) //输出节点的后继表
{
printf(",");
printGList(gl->next);
}
return;
}

//求广义表长度
int GLLength(GLNode *gl)
{
int n=0;
gl=gl->val.sublist;
while(gl != NULL)
{
n++;
gl=gl->next;
}
return n;
}

//求广义表深度
int GLDepth(GLNode *gl)
{
int max=0,dep;
if(gl->tag==0)
return 0;
gl=gl->val.sublist;
if(gl == NULL)
return 1;
while(gl != NULL)
{
if(gl->tag==1)
{
dep=GLDepth(gl);
if(dep>max)
max=dep;
}
gl=gl->next;
}
return max+1;
}

void main()
{
int len=0;
int dep=0;
struct lnode *h;
printf("input the list:\n");
creatGList(&h);
len=GLLength(h);
dep=GLDepth(h);
printf("\n");
printf("the length is:");
printf("%d\n",len);
printf("the depth is:");
printf("%d\n",dep);
if(h != NULL)
{
printf("GList is:");
printGList(h);
printf("\n");
}
else
printf("GList is NULL\n");
_getch();
}