見代碼
[cpp]
#define OVERFLOW -2
typedef enum{ATOM,LIST}ElemTag; //ATOM=0,原子；LIST=1,子表；
typedef char *AtomType; //原子類型
typedef struct GLNode{
ElemTag tag; //公共部分，區別原子結點和表結點
union {
AtomType atom; //原子結點的值域
struct{struct GLNode *hp,*tp;
char *listname;
}ptr; //分指表頭和表尾
};
}*GList; //廣義表類型
/********************字符串的操作***********************************/
int StrLength(char *s) //返回串長
{return strlen(s);
}
status SubString(char *&sub,char *str,int pos,int len)
//取出從pos位置起，長為len的子串
{char *p;
int k,i;
p=str;k=StrLength(str);
if(pos<1||pos>k||len<0||len>k-pos+1) return ERROR; //參數不合法
sub=new char[len+1];
for(i=pos-1;i<pos+len-1;i++)
*sub++=*(p+i);
*sub='\0';
sub=sub-len;
return OK;
}
void StrCopy(char *&t,char *s)//將子串s復制到t
{ t=new char[StrLength(s)+1];
strcpy(t,s);
}
int StrCompare(char *s,char *t) //比較串s和t
{ return strcmp(s,t);
}
status StrEmpty(char *s) //判斷串s是否為空
{
if(!s) return OK; //若空返回OK
else return ERROR; //否則返回ERROR
}
void ClearString(char *&s) //清空串s
{ if(s){
delete(s);
s=NULL;
}
}
/********************出錯信息處理***********************************/
void ERRORMESSAGE(char *s) //出錯信息處理函數
{
cout<<s<<endl;
exit(1);
}
/***********************建廣義表********************************/
void Sever(char *&sub,char *&str){//分離出表頭或原子結點的字符串
int i=1,n;char *ch;
n=StrLength(str);
SubString(ch,str,i,1);
if(*ch=='('){ //若第一個字符為(，則或為空表，或為共享部分，返回(
sub=ch;
SubString(str,str,2,n-1); //str為剩余部分
}
else{ //否則返回表頭或原子結點的字符串
while(*ch!=')'&&*ch!=','&&*ch!='('&&*ch!='\0') {
i++;
SubString(ch,str,i,1);
}
SubString(sub,str,1,i-1);
SubString(str,str,i,n-i+1);//str為剩余部分
}
}
status GetChar(char *&str,char &ch){ //從字符串頭分離一個字符
int n;
if(!str) return ERROR;
n=StrLength(str);
ch=*str; //取出第一個字符
SubString(str,str,2,n-1); //str為剩余部分
return OK;
}
status CreatGList(GList &L,char *&s){ //創建帶子表名的廣義表
char *ch1,ch2,ch; GList p;status i;
Sever(ch1,s); //取字符串
GetChar(s,ch2); //取下一個字符
if((*ch1=='('||*ch1=='#')&&ch2==')'){ //空表或共享表部分
L=NULL;
if(*ch1=='('){
GetChar(s,ch); //讀取下一字符以判斷是否仍有未建子表
if(ch==',') return 1; //仍有未建子表返回1
else return 2; //此層次上的子表建完，返回2
}
else return 2;
}
if(!(L=new GLNode)) exit(OVERFLOW);
if(ch2==','||ch2==')'||ch2=='\0'){ //原子結點
L->tag=ATOM;L->atom=ch1;
if(ch2==',') return 1; //仍有未建子表返回1
else return 2; //此層次上的子表建完，返回2
}
if(ch2=='('){ //表結點
L->tag=LIST;
L->ptr.listname=ch1; //listname存放表名
i=CreatGList(L->ptr.hp,s);
p=L;
while(i!=2){ //i!=2時遞歸建下一子表
p=p->ptr.tp=new GLNode;
p->tag=LIST;p->ptr.listname="#";
i=CreatGList(p->ptr.hp,s);
}
p->ptr.tp=NULL;
GetChar(s,ch);
if(ch==',') return 1; //仍有未建子表返回1
else return 2; //此層次上的子表建完，返回2
}
return FALSE; //字符串錯誤
}//Creat
/*********************廣義表共享*********************************/
GList Get(GList L,int I[]) //根據層次序號查找共享及被共享結點
{ int k,j; GList p;
k=0; p=L;
while(I[k]){
j=1;
while(j<I[k]) {p=p->ptr.tp;j++;}//根據層次序號的第一個數向表尾部走
k++;
if(I[k]) p=p->ptr.hp; //向表頭部走
}
return p;
}
void Share(GList &L) //建立共享結構
{ GList p,q;
int I[10];int i; char ch;
do{ i=0;
cout<<"共享子表序號:"<<endl;
cin>>I[i];
while(I[i]) cin>>I[++i];
p=Get(L,I); //p指向共享子表
i=0;
cout<<"被共享子表序號:"<<endl;
cin>>I[i];
while(I[i]) cin>>I[++i];
q=Get(L,I); //q指向被共享子表
p->ptr.hp=q->ptr.hp;p->ptr.tp=q->ptr.tp; //共享
cout<<"another?(y/n)"; //若還有其余共享，輸入y
cin>>ch;
}while(ch=='Y'||ch=='y'); //循環控制共享結點個數
}
/***********************打印廣義表*****************************/
status PrintGList(GList L,int i)//打印廣義表，i為空格數，初始為0
{ GList p,q;int k;
if(!L) {
for(k=0;k<i;k++) cout<<' ';
cout<<"#"<<endl; return OK;
} //打印空表
if(L->tag==ATOM) {
for(k=0;k<i;k++) cout<<' ';
cout<<L->atom<<endl; return OK;
} //打印原子結點
p=L;
for(k=0;k<i;k++) cout<<' ';
cout<<p->ptr.listname<<endl; //打印子表名
while(p){ //打印各個子表
q=p->ptr.hp; //q指向第一個子表
PrintGList(q,i+2); //遞歸打印第一個子表，空格數增加
p=p->ptr.tp; //指針後移
}//while
return OK;
}//PrintGList
