/*
我們提供的服務(wù)有：成都網(wǎng)站制作、做網(wǎng)站、外貿(mào)營(yíng)銷網(wǎng)站建設(shè)、微信公眾號(hào)開(kāi)發(fā)、網(wǎng)站優(yōu)化、網(wǎng)站認(rèn)證、定結(jié)ssl等。為數(shù)千家企事業(yè)單位解決了網(wǎng)站和推廣的問(wèn)題。提供周到的售前咨詢和貼心的售后服務(wù)，是有科學(xué)管理、有技術(shù)的定結(jié)網(wǎng)站制作公司
廣義表的實(shí)現(xiàn)
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;
/* 遞歸創(chuàng)建廣義表，注意參數(shù)比較復(fù)雜，指針的指針 */
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);
}
}
}
/* 遞歸復(fù)制廣義表 */
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);
}
/* 求表的深度函數(shù)（有錯(cuò)誤？） */
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);
}
}
/* 求原子結(jié)點(diǎn)的個(gè)數(shù)函數(shù) */
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;
/************************************************************************/
/* 以下是關(guān)于廣義表操作的4個(gè)簡(jiǎn)單算法 */
/************************************************************************/
struct GNode{
int tag; /* 標(biāo)志域：取0表示單元素結(jié)點(diǎn)；取1時(shí)表示子表結(jié)點(diǎn) */
union{
elemType data;
struct GNode *subList;
};
struct GNode *next; /* 指向后繼結(jié)點(diǎn)的指針域 */
};
/* 1.求廣義表的長(zhǎng)度 */
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;
/* 遍歷每個(gè)結(jié)點(diǎn)，求出所以子表的最大深度 */
while(gl != NULL){
if(gl-tag == 1){
/* 遞歸求出一個(gè)子表的深度 */
int dep = depthGList(gl-subList);
/* 讓max始終為同一個(gè)所求子表中深度的最大值 */
if(dep max){
max = dep;
}
}
gl = gl-next; /* 讓gl指向下一個(gè)結(jié)點(diǎn) */
}
return max + 1; /* 返回表的深度 */
}
/* 3.建立廣義表的存儲(chǔ)結(jié)構(gòu) */
void creatGList(struct GNode* *gl)
{
char ch;/* 讀入一個(gè)字符，此處可能讀入'＃'，'（'，'）'，','或者英文字母 */
scanf("%c", ch);
/* 若輸入為＃，則置表頭指針為空 */
if(ch == '#'){
*gl = NULL;
}
/* 若輸入左括號(hào)則建立由*gl所指向的子表結(jié)點(diǎn)并遞歸構(gòu)造子表 */
else if(ch == '('){
*gl = malloc(sizeof(struct GNode));
(*gl)-tag = 1;
creatGList(((*gl)-subList));
}
/* 若輸入為字符則建立由*gl所指向的單元素結(jié)點(diǎn) */
else{
*gl = malloc(sizeof(struct GNode));
(*gl)-tag = 0;
(*gl)-data = ch;
}
/* 此處讀入的字符必為逗號(hào)或右括號(hào)或分號(hào) */
scanf("%c", ch);
/* 若*gl為空，則什么都不做 */
if(*gl == NULL){
;
}
/* 若輸入為逗號(hào)則遞歸構(gòu)造后繼表 */
else if(ch == ','){
creatGList(((*gl)-next));
}
/* 若輸入為右括號(hào)或分號(hào)則置*gl的后繼指針域?yàn)榭?*/
else if((ch == ')') || (ch == ';')){
(*gl)-next = NULL;
}
return;
}
/* 4.打印廣義表 */
void printGList(struct GNode *gl)
{
/* 對(duì)于表結(jié)點(diǎn)的處理 */
if(gl-tag == 1){
/* 存在子表，先輸出左括號(hào) */
printf("(");
/* 若子表為空，則輸出'#'字符 */
if(gl-subList == NULL){
printf("#");
}
/* 若子表非表，則遞歸輸出子表 */
else{
printGList(gl-subList);
}
/* 當(dāng)一個(gè)子表輸出結(jié)束后，再輸出右括號(hào) */
printf(")");
}
/* 對(duì)單元素結(jié)點(diǎn)，則輸出該結(jié)點(diǎn)的值 */
else{
printf("%c", gl-data);
}
/* 輸出該結(jié)點(diǎn)的后繼表 */
if(gl-next != NULL){
/* 先輸出逗號(hào)分隔 */
printf(", ");
/* 再遞歸輸出后繼表 */
printGList(gl-next);
}
return;
}
int main()
{
struct GNode *gl;
printf("輸入一個(gè)廣義表， 以右括號(hào)結(jié)束 ");
creatGList(gl);
printf("輸出廣義表：");
printGList(gl);
printf(" ");
printf("廣義表的長(zhǎng)度：");
printf("%d ", lenthGList(gl-subList));
printf("廣義表的深度：");
printf("%d ", depthGList(gl-subList));
system("pause");
return 0;
}
網(wǎng)上搜了個(gè)類似程序，希望滿足你要求：
#includestdafx.h
#includestdio.h
#includestring.h
#includestdlib.h
typedef
char
ElemType;
//自定義結(jié)構(gòu)體存放廣義表中單元素節(jié)點(diǎn)和字表節(jié)點(diǎn)
typedef
struct
lnode
{
int
tag;
union
{
ElemType
data;
struct
lnode
*sublist;
}val;
struct
lnode
*next;
}GLNode;
//自定義函數(shù)來(lái)實(shí)現(xiàn)廣義表創(chuàng)建
void
creatGList(struct
lnode
**gl)
{
char
ch;
ch=getchar();
if(ch=='#')
*gl=NULL;
else
if(ch=='(')
//輸入左括號(hào)則遞歸構(gòu)造字表
{
*gl=(lnode*)malloc(sizeof(struct
lnode));
(*gl)-tag=1;
creatGList(((*gl)-val.sublist));
}
else
//輸入為字符則建立單元素節(jié)點(diǎn)
{
*gl=(lnode*)malloc(sizeof(struct
lnode));
(*gl)-tag=0;
(*gl)-val.data=ch;
}
ch=getchar();
if(*gl==NULL)
;
else
if(ch==',')
//若輸入為逗號(hào)則遞歸構(gòu)建后繼表
creatGList(((*gl)-next));
else
(*gl)-next=NULL;
return;
}
//自定義函數(shù)實(shí)現(xiàn)廣義表輸出
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);//單個(gè)元素則直接輸出
if(gl-next!=NULL)
//輸出節(jié)點(diǎn)的后繼表
{
printf(",");
printGList(gl-next);
}
return;
}
//求廣義表長(zhǎng)度
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();
}
重慶分公司
重慶分公司
