囧~~
#include <stdio.h>
#include <stdlib.h>
#define NULL 0
typedef enum{ATOM, LIST}ElemTag; /*ATOM==0:原子,LIST==1:子表*/
typedef struct GLNode
{
int tag; /*公共部分,區(qū)分原子和表結(jié)點(diǎn)*/
union /*原子結(jié)點(diǎn)和表結(jié)點(diǎn)的聯(lián)合部分*/
{
char atom; /*原子結(jié)點(diǎn)的值域*/
struct GLNode *sublist; /*表結(jié)點(diǎn)表頭指針*/
};
struct GLNode *next; /*下一個(gè)元素結(jié)點(diǎn)*/
}GList;
void CreateGList(GList **gl);
void PrintGList(GList *gl);
int GListDepth(GList *gl);
int main(void)
{
GList *gl;
printf("建立一個(gè)廣義表,以右括號(hào)結(jié)束\n");
CreateGList(&gl);
printf("輸出廣義表：");
PrintGList(gl);
printf("\n");
printf("廣義表的深度：");
printf("%d\n", GListDepth(gl->sublist));
return 0;
}
/*************************************************
函數(shù)名稱:CreateGList
函數(shù)功能:創(chuàng)建一個(gè)廣義表(遞歸構(gòu)件子表)
輸入的時(shí)候是換一行輸入,最后要多輸右括號(hào),是遞歸的原因
被本函數(shù)調(diào)用的函數(shù)清單:無
調(diào)用本函數(shù)的函數(shù)清單:無
輸入?yún)?shù):gl,取用指針的指針的形式,可以對(duì)其直接修改
輸出參數(shù):無
函數(shù)返回值:(void)
**************************************************/
void CreateGList(GList **gl)
{
char ch;
scanf("%c", &ch);
getchar(); /*吞食scanf留下的換行*/
if(ch == '#') /*如果輸入的是#表示為空*/
{
*gl = NULL;
}
else if(ch == '(') /*如果是左括號(hào)就遞歸構(gòu)件子表*/
{
*gl = (GList *)malloc(sizeof(GList));
(*gl)->tag = LIST;
CreateGList(&((*gl)->sublist));
}
else /*就是只有原子的情況下*/
{
*gl = (GList *)malloc(sizeof(GList));
(*gl)->tag = ATOM;
(*gl)->atom = ch;
}
scanf("%c", &ch); /*此處輸入的必為逗號(hào)或者右括號(hào)*/
getchar();
if((*gl) == NULL)
{
;
}
else if(ch == ',') /*如果是逗號(hào)就遞歸構(gòu)件下一個(gè)子表*/
{
CreateGList(&((*gl)->next));
}
else if(ch == ')') /*如果是右括號(hào)就結(jié)束*/
{
(*gl)->next = NULL;
}
}
/*************************************************
函數(shù)名稱:GListDepth
函數(shù)功能:求廣義表的深度(遞歸子表->到子表..(最長(zhǎng)+1))
被本函數(shù)調(diào)用的函數(shù)清單:無
調(diào)用本函數(shù)的函數(shù)清單:無
輸入?yún)?shù):gl
輸出參數(shù):無
函數(shù)返回值:(void)
**************************************************/
int GListDepth(GList *gl)
{
int max, dep;
if(!gl)
return 1;
for(max = 0; gl; gl = gl->next)
{
if(gl->tag == LIST)
{
dep = GListDepth(gl->sublist); /*求以gl->sunlist的子表深度*/
if(dep > max)
{
max = dep;
}//if
}//if
}//for
return max + 1; /*各元素的深度的最大值加一*/
}
/*************************************************
函數(shù)名稱:PrintGList
函數(shù)功能:打印廣義表(遞歸打印子表)
被本函數(shù)調(diào)用的函數(shù)清單:無
調(diào)用本函數(shù)的函數(shù)清單:無
輸入?yún)?shù):gl
輸出參數(shù):無
函數(shù)返回值:(void)
**************************************************/
void PrintGList(GList *gl)
{
if(gl->tag == LIST)
{
printf("("); /*先輸出左括號(hào)*/
if(gl->sublist == NULL)
{
printf("#");
}
else
{
PrintGList(gl->sublist); /*遞歸打印子表*/
}
printf(")"); /*結(jié)束打印右括號(hào)*/
}
else
{
printf("%c", gl->atom);
}
if(gl->next != NULL) /*如果沒結(jié)束就繼續(xù)遞歸打印子表*/
{
printf(", ");
PrintGList(gl->next);
}
}
