首页 > 代码库 > 广义表的创建与打印
广义表的创建与打印
广义表的创建与打印
本文取自《数据结构与算法》(C语言版)(第三版),出版社是清华大学出版社。
源码是VC++ 6.0上可运行程序,我挪到了VS2010中运行。
在VS2010中新建C++ Win32 控制台应用程序项目,创建结果截图:
1.广义表的创建:
广义表的存储结构示意图:演示样例:C(x, y, (a, b))
广义表能够通过以下的递归方式进行定义。
基本项:(1)广义表为空表,当s为空时;(2)广义表为原子结点。当s为单字符串时。
归纳项:如果Subs为S去掉最外层括号对的串,记作“S1。S2。...,Sn”。当中Si(i=1,...,n)为非空字符串。对每一个Si建立表结点,并令其hp域的指针为由Si建立的子表的头指针,除最后建立的表结点的尾指针为NULL外,其余表结点的尾指针均指向在它之后建立的表结点。也就是说,由于Si是一个字符串,首先要为这个字符串建立一个表结点,表结点的指针域指向Si中的元素。它的tp域指向下一次建立的Si+1,而Sn的tp域为空。
由于在广义表的定义中要用到subs串,因此须要一个函数来求这个串。这里採用函数Getsubs(str,hstr)来实现。
当中,hstr存放的是str中第1个","之前的子串,而且函数将str改动为删除子串hstr和","之后的剩余串。
若串str中没有",",则hstr即为str。而str改动为空串NULL。
2.广义表的打印:
打印广义表的算法思想是:先打印一个左括号"(",若遇到tag=ATOM,则打印该结点的值。假设此结点后面有后继结点,则再打印一个",";假设tag=LIST,说明是一个子表,则递归调用函数,打印这个子表。打印全然部结点以后,最后打印一个“)”。
源程序例如以下:GeneralList.cpp
// GeneralList.cpp : 定义控制台应用程序的入口点。 #include "stdafx.h" #include <stdio.h> #include <stdlib.h> #include <string.h> typedef enum {ATOM, LIST}ElemTag; //ATOM==0 原子, LIST==1 子表 struct GLNode { ElemTag tag; //标识域 union { char atom; struct GLNode *hp; }; struct GLNode *tp; }; typedef struct GLNode GList; //求取广义表的子串Subs void Getsubs(char str[], char hstr[]) { int i=0; int j=0; int k=0; //用来记录没有匹配的左括号数 int r=0; char s[100]; while(str[i]&&(str[i]!=','||k)) { if(str[i]=='(') k++; else if(str[i]==')') k--; if(str[i]!=','||str[i]==','&&k) { hstr[j]=str[i]; i++; j++; } } hstr[j]='\0'; if(str[i]==',') i++; while(str[i]) { s[r]=str[i]; r++; i++; } s[r]='\0'; strcpy(str,s); } //创建广义表 GList *GListCreate(char str[]) { GList *G; char subs[100]; char hstr[100]; GList *q; int len=strlen(str); if(len==0||!strcmp(str,"()")) G=NULL; else if(len==1) //原子结点的情况 { G=(GList *)malloc(sizeof(GList)); if(!G) { printf("申请空间失败!"); exit(0); } G->tag = ATOM; G->atom = *str; G->tp = NULL; } else { GList *p; G=(GList *)malloc(sizeof(GList)); if(!G) { printf("申请空间失败!Ctrl+F5执行GeneralList.cpp的执行结果:例如以下截图:"); exit(0); } G->tag = LIST; p=G; str++; strncpy(subs,str,len-2); //去掉最外面的() subs[len-2]='\0'; while(len>0) { GList *r; Getsubs(subs,hstr); //将subs分开为表头hstr和表尾subs r=GListCreate(hstr); //生成表头的广义表 p->hp=r; q=p; len=strlen(subs); if(len>0) { p=(GList *)malloc(sizeof(GList)); if(!G) { printf("申请空间失败!"); exit(0); } p->tag = LIST; q->tp=p; } } q->tp=NULL; } return G; } //打印广义表 void GListPrint(GList *G) { GList *q,*p; printf("("); while(G) { p=G->hp; q=G->tp; if(p&&q&&!p->tag) //p为原子结点,而且有兴许结点 { printf("%c,",p->atom); p=q->hp; q=q->tp; } if(p&&!p->tag) //p为原子结点,而且没有兴许结点 { printf("%c",p->atom); break; } else { if(!p) printf("()"); //p为空表 else GListPrint(p); if(q) printf(","); //还存在着兴许的结点 G=q; } } printf(")"); } int main() { int n; char *s; GList *G; printf("请输入广义表的字符数:\n"); scanf("%d",&n); printf("请输入广义表:\n"); s=(char *)malloc(n*sizeof(char)); scanf("%s",s); G=GListCreate(s); printf("所输入的广义表为:\n"); GListPrint(G); printf("\n"); return 0; }
广义表的创建与打印