/*
我们提供的服务有：成都网站制作、做网站、外贸营销网站建设、微信公众号开发、网站优化、网站认证、定结ssl等。为数千家企事业单位解决了网站和推广的问题。提供周到的售前咨询和贴心的售后服务，是有科学管理、有技术的定结网站制作公司
广义表的实现
author: kk.h
date: 2006.10
*/
#include "stdio.h"
typedef struct node
{
int tag;
union{struct node *sublist;
char data;
}dd;
struct node *link;
}NODE;
/* 递归创建广义表，注意参数比较复杂，指针的指针 */
NODE *creat_GL(char **s)
{
NODE *h;
char ch;
ch=*(*s);
(*s)++;
if(ch!='\0')
{
h=(NODE*)malloc(sizeof(NODE));
if(ch=='(')
{
h-tag=1;
h-dd.sublist=creat_GL(s);
}
else
{
h-tag=0;
h-dd.data=ch;
}
}
else
h=NULL;
ch=*(*s);
(*s)++;
if(h!=NULL)
if(ch==',')
h-link =creat_GL(s);
else
h-link=NULL;
return(h);
}
/* 递归打印广义表 */
vOId prn_GL(NODE *p)
{
if(p!=NULL)
{
if(p-tag==1)
{
printf("(");
if(p-dd.sublist ==NULL)
printf(" ");
else
prn_GL(p-dd.sublist );
}
else
printf("%c",p-dd.data);
if(p-tag==1)
printf(")");
if(p-link!=NULL)
{
printf(",");
prn_GL(p-link);
}
}
}
/* 递归复制广义表 */
NODE *copy_GL(NODE *p)
{
NODE *q;
if(p==NULL) return(NULL);
q=(NODE *)malloc(sizeof(NODE));
q-tag=p-tag;
if(p-tag)
q-dd.sublist =copy_GL(p-dd.sublist );
else
q-dd.data =p-dd.data;
q-link=copy_GL(p-link);
return(q);
}
/* 求表的深度函数（有错误？） */
int depth(NODE *p)
{
int h,maxdh;
NODE *q;
if(p-tag==0) return(0);
else
if(p-tag==1p-dd.sublist==NULL) return 1;
else
{
maxdh=0;
while(p!=NULL)
{
if(p-tag==0) h=0;
else
{q=p-dd.sublist;
h=depth(q);
}
if(hmaxdh)
maxdh=h;
p=p-link;
}
return(maxdh+1);
}
}
/* 求原子结点的个数函数 */
int count(NODE *p)
{
int m,n;
if(p==NULL) return(0);
else
{
if(p-tag==0) n=1;
else
n=count(p-dd.sublist);
if(p-link!=NULL)
m=count(p-link);
else m=0;
return(n+m);
}
}
main()
{
NODE *hd,*hc;
char s[100]="(a,(b,(c,d)))",*p;
/*p=gets(s);*/
p=s;
hd=creat_GL(p);
hc=copy_GL(hd);
printf("\ncopy after:");
prn_GL(hc);
printf("\ndepth=%d (wrong?)",depth(hc));
printf("\ncount=%d",count(hc));
getch();
}
#include stdio.h
#include stdlib.h
typedef char elemType;
/************************************************************************/
/* 以下是关于广义表操作的4个简单算法 */
/************************************************************************/
struct GNode{
int tag; /* 标志域：取0表示单元素结点；取1时表示子表结点 */
union{
elemType data;
struct GNode *subList;
};
struct GNode *next; /* 指向后继结点的指针域 */
};
/* 1.求广义表的长度 */
int lenthGList(struct GNode *gl)
{
if(gl != NULL){
return 1 + lenthGList(gl-next);
}else{
return 0;
}
}
/* 2.求广义表的深度 */
int depthGList(struct GNode *gl)
{
int max = 0;
/* 遍历每个结点，求出所以子表的最大深度 */
while(gl != NULL){
if(gl-tag == 1){
/* 递归求出一个子表的深度 */
int dep = depthGList(gl-subList);
/* 让max始终为同一个所求子表中深度的最大值 */
if(dep max){
max = dep;
}
}
gl = gl-next; /* 让gl指向下一个结点 */
}
return max + 1; /* 返回表的深度 */
}
/* 3.建立广义表的存储结构 */
void creatGList(struct GNode* *gl)
{
char ch;/* 读入一个字符，此处可能读入'＃'，'（'，'）'，','或者英文字母 */
scanf("%c", ch);
/* 若输入为＃，则置表头指针为空 */
if(ch == '#'){
*gl = NULL;
}
/* 若输入左括号则建立由*gl所指向的子表结点并递归构造子表 */
else if(ch == '('){
*gl = malloc(sizeof(struct GNode));
(*gl)-tag = 1;
creatGList(((*gl)-subList));
}
/* 若输入为字符则建立由*gl所指向的单元素结点 */
else{
*gl = malloc(sizeof(struct GNode));
(*gl)-tag = 0;
(*gl)-data = ch;
}
/* 此处读入的字符必为逗号或右括号或分号 */
scanf("%c", ch);
/* 若*gl为空，则什么都不做 */
if(*gl == NULL){
;
}
/* 若输入为逗号则递归构造后继表 */
else if(ch == ','){
creatGList(((*gl)-next));
}
/* 若输入为右括号或分号则置*gl的后继指针域为空 */
else if((ch == ')') || (ch == ';')){
(*gl)-next = NULL;
}
return;
}
/* 4.打印广义表 */
void printGList(struct GNode *gl)
{
/* 对于表结点的处理 */
if(gl-tag == 1){
/* 存在子表，先输出左括号 */
printf("(");
/* 若子表为空，则输出'#'字符 */
if(gl-subList == NULL){
printf("#");
}
/* 若子表非表，则递归输出子表 */
else{
printGList(gl-subList);
}
/* 当一个子表输出结束后，再输出右括号 */
printf(")");
}
/* 对单元素结点，则输出该结点的值 */
else{
printf("%c", gl-data);
}
/* 输出该结点的后继表 */
if(gl-next != NULL){
/* 先输出逗号分隔 */
printf(", ");
/* 再递归输出后继表 */
printGList(gl-next);
}
return;
}
int main()
{
struct GNode *gl;
printf("输入一个广义表， 以右括号结束 ");
creatGList(gl);
printf("输出广义表：");
printGList(gl);
printf(" ");
printf("广义表的长度：");
printf("%d ", lenthGList(gl-subList));
printf("广义表的深度：");
printf("%d ", depthGList(gl-subList));
system("pause");
return 0;
}
网上搜了个类似程序，希望满足你要求：
#includestdafx.h
#includestdio.h
#includestring.h
#includestdlib.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(depmax)
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();
}
