求助，望指教。用头尾链表存储表示建立一个广义表 碰到的问题
求助，望指教。用头尾链表存储表示建立一个广义表#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#define OK 0
#define FALSE -1
#define OVERFLOW -2
#define Status int
#define MAXSTRLEN 255
#define SElemType unsigned char
#define AtomType char
typedef struct{
SElemType *base;
int Ssize;
}Sstring;
Sstring S,sub,hsub;
//定义广义表的头尾链式 存储
typedef enum{ATOM,LIST} ElemTag;
typedef struct GLNode{
ElemTag tag;
union {
AtomType atom;
struct {
struct GLNode *hp,*tp;
}ptr;
};
}*GList;
GList L;
Status CreateGList(GList &L,Sstring &S);
Status sever(Sstring &str,Sstring &hstr);
Status StrLength(Sstring &S);
Status SubString(Sstring &Sub,Sstring &S,int pos,int i);
char SubString1(Sstring &str,int i, int long);
Status Strcopy(Sstring &S1,Sstring &S2);
Status ClearString(Sstring &S);
Status StrEmpty(Sstring &S);
Status InitString(Sstring &S);
Status Create_String(Sstring &S,char a[255]);
Status InitGList(GList L);
Status StrCompare(Sstring &S1);
void output_String(Sstring &S);
void output_GLNode(GList L);
Status Traverse_GList(GList L);
int GListDepth(GList L);
//由广义表的书写形式串 S 创建广义表 L
Status CreateGList(GList &L,Sstring &S){
GList p,q;
if(StrCompare(S)) {
L=NULL;
} // 相同，返回 1
else{
if(!(L=(GList)malloc(sizeof(GLNode)))) exit(OVERFLOW);
if(StrLength(S)==1){//直接取得是S.base[0]的值
L->tag=ATOM;
L->atom=S.base[1];
// printf("%c\n",L->atom);
}
else{
L->tag=LIST; p=L;
SubString(sub,S,2,StrLength(S)-2);
// output_String(sub);
do{
sever(sub,hsub);
output_String(hsub);
output_String(sub);
CreateGList(p->ptr.hp,hsub);q=p;
if(!StrEmpty(sub)){
if(!(p=(GLNode *)malloc(sizeof(GLNode))))
exit(OVERFLOW);
p->tag=LIST;q->ptr.tp=p;
}
}while(!StrEmpty(sub));
q->ptr.tp=NULL;
}
}
return OK;
}
Status sever(Sstring &str,Sstring &hstr){
//将非空串str分割为两个部分，hstr为第一个，之前的字串，str为之后的字串
int i,k,n;
char ch;
n=StrLength(str);
i=1;
k=0;
ch=SubString1(str,i,1); //k记录尚未配对的左括号数
for( ;i<=n&&(ch!=','||k!=0);i++){
ch=SubString1(str,i,1);
if(ch=='(') ++k;
else if(ch==')') --k;
}
if((i-1)<n){
SubString(hstr,str,1,i-2);
SubString(str,str,i,n-i+1);
}
else{
Strcopy(hstr,str);
ClearString(str);
}
return OK;
}
/*Status sever(Sstring &str,Sstring &hstr){
int n,i=0,k=0;
char ch;
n=StrLength(str);
do{
++i;
ch=SubString1(str,i,1);
if(ch=='(') ++k;
else if(ch==')') --k;
}while(i<n&&(ch!=','||k!=0));
if(i<n){
SubString(hstr,str,1,i-1);
SubString(str,str,i+1,n-i);
}
else{
Strcopy(hstr,str);
ClearString(str);
}
return OK;
}*/
Status StrLength(Sstring &S){
return S.base[0];
}
Status SubString(Sstring &Sub,Sstring &S,int pos,int i){
int temp;
if((pos+i-1)>S.base[0])
return FALSE;
else{
Sub.base[0]=i;
for(temp=1;temp<=i;temp++){
Sub.base[temp]=S.base[pos];
pos++;
}
}
return OK;
}
//取字符串 str的第 i+1的位置值
char SubString1(Sstring &str,int i, int long){
char ch;
ch=str.base[i];
return ch;
}
//将 S2复制给 S1
Status Strcopy(Sstring &S1,Sstring &S2){
int i;
for(i=0;i<=S2.base[0];i++){
S1.base[i]=S2.base[i];
}
return OK;
}
Status StrCompare(Sstring &S){
if(S.base[0]!=2) return 0;
else{
if((S.base[1]=='(')&&(S.base[2]==')'))
return 1;
else return 0;
}
}
Status ClearString(Sstring &S){
S.base[0]=0;
return OK;
}
Status StrEmpty(Sstring &S){
if(S.base[0]==0) return 1;
return 0;
}
Status InitGList(GList L){
L=NULL;
return OK;
}
Status InitString(Sstring &S){
S.base=(SElemType *)malloc((MAXSTRLEN+1)*sizeof(SElemType));
if(!S.base) exit(OVERFLOW);
S.Ssize=MAXSTRLEN+1;
S.base[0]=0;//0表示的是实数0，'0'表示的是字符
return OK;
}
/*int Create_String(Sstring &S){
int ch;
int i=0;
ch=getchar();
while(i<S.Ssize){
if(ch!=EOF){
i++;
S.base[0]=S.base[0]+1;
S.base[i]=ch;
ch=getchar();
}
else return OK;
}
}*/
int Create_String(Sstring &S,char a[255]){
int i,n; char *c;
for(i=0,c=a;*c!='\0';){
i++;
c++;
}
printf("%d\n",i);
if(!i){
S.base[0]=0;
}
else{
S.base[0]=i;
for(n=0;n<i;n++){
S.base[n+1]=a[n];
}
}
return OK;
}
Status Traverse_GList(GList L){
if(!L) ;
else{
if(L->tag==ATOM)
output_GLNode(L);
else{
Traverse_GList(L->ptr.hp);
Traverse_GList(L->ptr.tp);
}
}
return OK;
}
void output_String(Sstring &S){
int i;
printf("%d\n",S.base[0]);
for(i=1;i<=S.base[0];i++){
printf("%c",S.base[i]);
}
printf("\n");
}
void output_GLNode(GList L){
printf("%c",L->atom);
}
int GListDepth(GList L){
int max,dep;
GList pp;
if(!L) return 1;
if(L->tag==ATOM) return 0;
for(max=0,pp=L;pp;pp=pp->ptr.tp){
dep=GListDepth(pp->ptr.hp);
printf("%d ",dep);
if(dep>max) max=dep;
}
return max+1;
}
int main(){
int Depth;
//为什么碰到（e），（a）这样的情况就不行；
//char a[255]="((),a,(e),(a,(b,c,d)))";
//(2)char a[255]="((),a,(e),((d)))";
//(1) char a[255]="(((a)),b,(d))";
// 也是正确的//
char a[255]="(a,c,x,e,(s))";
//几种特殊的情况 都是正确的
//char a[255]="(a)";
//char a[255]="a";
// char a[255]="()";
InitGList(L);
InitString(S);InitString(sub);InitString(hsub);
Create_String(S,a);
output_String(S);
CreateGList(L,S);
printf("%d\n",L);
printf("output the equal members:\n");
Traverse_GList(L);
printf("\n");
Depth=GListDepth(L);
printf("\n");
printf("The Depth of the GList is:%d\n",Depth);
system("pause");
return 0;
}
//运行时，像（a,b,c,(e)）这样的情况就可以。只要碰到像（（e），（x））的就不行，不会把（x）链接到链表中
