广义表的应用

break;

case 4: cout<<\广义表取表尾：\ cout<<\ GListTail(L); cout<<\ break;

case 5: printf(\广义表的逆表：\ TraverseList(L); cout<

case 6: cout<<\广义表的深

3.创建广义表函数：CreateGList（）void CreateGList(GList **L) //创建广义表函数 { char ch; cin>>ch; //输入数据 if(ch == '#') //如果输入的是#表示为空 *L = NULL; else if(ch == '(') //如果是左括号就递归构建子表 { *L = (GList *)malloc(sizeof(GList)); (*L)->tag =1; //广义表的标志量为LIST CreateGList(&((*L)->hp)); //建立此广义表的表头指针所指的元素 } else //只有原子的情况下 { *L = (GList *)malloc(sizeof(GList)); (*L)->tag = 0; //广义表标志量为ATOM (*L)->atom = ch; //元素为所输入数值 a[i]=ch; //不能写成a[i]=(*L)->atom; 度为：\

cout<hp)<

case 0: cout<<\退出！\

exit(0); break; } }

return 0; }

i++; } cin>>ch; //此处输入的必为逗号或者右括 if(ch == ',') //如果是逗号就递归构建下一个子表 CreateGList(&((*L)->next)); else if(ch == ')') //如果是右括号就结束 (*L)->next =NULL; } 4.广义表输出函数PrintGList（） void PrintGList(GList *L) //输出广义表 { if(L->tag == 1) //广义表标志量为LIST { cout<<\//先输出左括号 if(L->hp == NULL) //表头指针为空 cout<<\ else PrintGList(L->hp); //递归打印子表 cout<<\//结束打印右括号 } else

2

//标志量为ATOM

cout<atom; //输出此元素

if(L->next !=NULL) {

cout<<\

PrintGList(L->next); //调用此函数，输出广义表下一个元素 } }

5. 广义表查找函数Locate（）

void Locate(GList *L,char ch) //广义表 查找 {

int j;

cin>>ch; //输入要查找关键字

for (j=0;j<=i;j++)//用for循环查找 {

if(a[j]==ch) //如果找到 {

cout<<\查找成功，位置为:\ break; } }

if(j>i)

cout<<\查找失败,元素不存在此广义表中!\}

6.广义表取表头函数：

void GListHead(GList *L) //广义表取表头 { GList *p; p=L->hp; //p指向广义表表头 PrintGListHead(p); //调用表头输出函数 }

7.广义表取表尾函数

void GListTail(GList *L) //广义表取表尾 { GList *p,*q; q=L->hp; //q指向广义表表头 p=q->next; //p指向广义表表尾 PrintGList(p); }

8.广义表逆置函数TraverseList()

void TraverseList(GList *L) //广义表逆置 {

cout<<\

GListTail(L); //调用取表尾函数 cout<<\

GListHead(L); //调用取表头函数 cout<<\}

9. 广义表求深度函数

int GListDepth(GList *L) //求广义表深度 {

int max, dep; if(!L) //广义表存在

2

return 1;

for(max =0; L; L=L->next) //max初值为0，元素地址不为空 {

if(L->tag == 1) //元素标志量为LIST {

dep = GListDepth(L->hp); //求以L->hp的子表深度 if(dep > max) max = dep; } }

return max + 1; 各元素的深度的最大值加一 }

//

五、程序代码

#include using namespace std; typedef enum{ATOM, LIST}ElemTag; //ATOM==0:原子,LIST==1:子表 typedef struct GLNode //广义表结构类型 { int tag; //标志域,区分原子和表结点 union //原子结点和表结点的联合部分 { char atom; //原子结点的值域 struct GLNode *hp; //表结点表头指针 }; struct GLNode *next; //下一个元素结点 }GList; int i=0; //定义变量i，用来作数组下标 int a[10]; //定义数组用来存储广义表中的关键字 void CreateGList(GList **L) //创建广义表函数 { char ch; cin>>ch; //输入数据 if(ch == '#') //如果输入的是#表示为空 *L = NULL; else if(ch == '(') //如果是左括号就递归构建子表 { *L= (GList *)malloc(sizeof(GList)); (*L)->tag=1; //广义表的标志量为LIST CreateGList(&((*L)->hp)); //建立此广义表的表头指针所指的元素 } else //只有原子的情况下 { *L = (GList *)malloc(sizeof(GList)); (*L)->tag = 0; //广义表标志量为ATOM (*L)->atom = ch; //元素为所输入数值 a[i]=ch; //不能写成a[i]=(*L)->atom; i++; }

cin>>ch; //此处输入的必为逗号或者右括 if(ch == ',') //如果是逗号就递归构建下一个子表 CreateGList(&((*L)->next)); else if(ch==')') //如果是右括号就结束 (*L)->next =NULL; } void PrintGList(GList *L) //输出广义表 { if(L->tag==1)

2

//广义表标志量为LIST } { return max + 1; cout<<\//各元素的深度的最大值加一 //先输出左括号 } if(L->hp == NULL) //表头指针为空 void PrintGListHead(GList *L) cout<<\//打印广义表表头函数 else {

PrintGList(L->hp); if(L->tag == 1 ) //递归打印子表 cout<<\//结束打印右括号 } else //标志量为ATOM cout<atom; //输出此元素 if(L->next !=NULL) { cout<<\ PrintGList(L->next); //调用此函数，输出广义表下一个元素 } } int GListDepth(GList *L) //求广义表深度 { int max, dep; if(!L) //广义表存在 return 1; for(max = 0; L; L = L->next) //max初值为0，元素地址不为空 { if(L->tag == 1) //元素标志量为LIST { dep = GListDepth(L->hp); //求以L->hp的子表深度 if(dep > max) max = dep; } //子表 { cout<<\//先输出左括号 if(L->hp == NULL) //如果表头为空 cout<<\ else PrintGListHead(L->hp); //递归打印子表 cout<<\结束打印右括号 } else //原子 cout<atom; } void GListHead(GList *L) //广义表取表头 { GList *p; p=L->hp; //p指向广义表表头 PrintGListHead(p); //调用表头输出函数 } void GListTail(GList *L) //广义表取表尾 {

GList *p,*q; q=L->hp; //q指向广义表表头 p=q->next; //p指向广义表表尾

2