データ構造--広義表
13752 ワード
コード:
#include<string.h>
#include<ctype.h>
#include<malloc.h>
#include<limits.h>
#include<stdio.h>
#include<stdlib.h>
#include<io.h>
#include<math.h>
#include<process.h> //exit()
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
typedef char AtomType; //
typedef int Status; //Status ， ， OK
/* */
typedef struct
{
char *ch; // , , ch NULL
int length; //
}HString;
/* */
typedef enum{ATOM,LIST}ElemTag; //ATOM==0: ,LIST==1:
typedef struct GLNode
{
ElemTag tag; // ，
union //
{
AtomType atom; // ，AtomType
struct GLNode *hp; //
}a;
struct GLNode *tp; // next，
}*GList,GLNode; // GList
//1.
Status StrAssign(HString *T,char *chars)
{
int i,j;
if((*T).ch)
free((*T).ch);
i=strlen(chars);
if(!i)
{
(*T).ch=NULL;
(*T).length=0;
}
else
{ //chars 0
(*T).ch=(char*)malloc(i*sizeof(char));
if(!(*T).ch) //
exit(OVERFLOW);
for(j=0;j<i;j++) //
(*T).ch[j]=chars[j];
(*T).length=i;
}
return OK;
}
//2. ： S T
Status StrCopy(HString *T,HString S)
{
int i;
if((*T).ch)
free((*T).ch);
(*T).ch=(char*)malloc(S.length*sizeof(char));
if(!(*T).ch)
exit(OVERFLOW);
for(i=0;i<S.length;i++)
(*T).ch[i]=S.ch[i];
(*T).length=S.length;
return OK;
}
//3. ： S , TRUE, FALSE
Status StrEmpty(HString S)
{
if(S.length==0&&S.ch==NULL)
return TRUE;
else
return FALSE;
}
//4. ： S>T, >0; S=T, =0; S<T, <0
int StrCompare(HString S,HString T)
{
int i;
for(i=0;i<S.length&&i<T.length;++i)
if(S.ch[i]!=T.ch[i])
return S.ch[i]-T.ch[i];
return S.length-T.length;
}
//5. ： S ,
int StrLength(HString S)
{
return S.length;
}
//6. ： S
Status ClearString(HString *S)
{
if((*S).ch)
{
free((*S).ch);
(*S).ch=NULL;
}
(*S).length=0;
return OK;
}
//7. ： Sub S pos len
Status SubString(HString *Sub, HString S,int pos,int len)
{ // ,1≤pos≤StrLength(S) 0≤len≤StrLength(S)-pos+1
int i;
if(pos<1||pos>S.length||len<0||len>S.length-pos+1)
return ERROR;
if((*Sub).ch)
free((*Sub).ch); //
if(!len) //
{
(*Sub).ch=NULL;
(*Sub).length=0;
}
else
{ //
(*Sub).ch=(char*)malloc(len*sizeof(char));
if(!(*Sub).ch)
exit(OVERFLOW);
for(i=0;i<=len-1;i++)
(*Sub).ch[i]=S.ch[pos-1+i];
(*Sub).length=len;
}
return OK;
}
//8. ： ( ) T
void InitString(HString *T)
{
(*T).length=0;
(*T).ch=NULL;
}
//9. ： str :hstr ',' ,str
Status sever(HString *str,HString *hstr)
{
int n,i=1,k=0; //k
HString ch,c1,c2,c3;
InitString(&ch); // HString
InitString(&c1);
InitString(&c2);
InitString(&c3);
StrAssign(&c1,","); //
StrAssign(&c2,"(");
StrAssign(&c3,")");
n=StrLength(*str); //
do
{
SubString(&ch,*str,i,1); //
if(!StrCompare(ch,c2)) //
++k;
else if(!StrCompare(ch,c3)) //
--k;
++i;
}while(i<=n&&StrCompare(ch,c1)||k!=0); //
if(i<=n)
{
StrCopy(&ch,*str); //
SubString(hstr,ch,1,i-2); //
SubString(str,ch,i,n-i+1); //
}
else
{
StrCopy(hstr,*str); //
ClearString(str); // str
}
return OK;
}
//10. L
Status InitGList(GList *L)
{
*L=NULL;
return OK;
}
//11. S L： S
Status CreateGList(GList *L,HString S)
{
HString emp,sub,hsub;
GList p;
InitString(&emp); // HString
InitString(&sub);
InitString(&hsub);
StrAssign(&emp,"()"); // ， emp="()"
*L=(GList)malloc(sizeof(GLNode));
if(!*L) //
exit(OVERFLOW);
if(!StrCompare(S,emp)) // S emp ,
{
(*L)->tag=LIST;
(*L)->a.hp=NULL;
(*L)->tp=NULL;
}
else if(StrLength(S)==1) // S 1，
{
(*L)->tag=ATOM;
(*L)->a.atom=S.ch[0];
(*L)->tp=NULL;
}
else //
{
(*L)->tag=LIST;
(*L)->tp=NULL;
SubString(&sub,S,2,StrLength(S)-2); //
sever(&sub,&hsub); // sub hsub
CreateGList(&(*L)->a.hp,hsub); // L
p=(*L)->a.hp;
while(!StrEmpty(sub)) // StrEmpty 。 ， n
{
sever(&sub,&hsub); // sub hsub
CreateGList(&p->tp,hsub);
p=p->tp;
}
}
return OK;
}
//12. L
void DestroyGList(GList *L)
{
GList ph,pt;
if(*L) //L
{ // ph pt L
if((*L)->tag) //
ph=(*L)->a.hp;
else //
ph=NULL;
pt=(*L)->tp;
free(*L); // L
*L=NULL; // L
DestroyGList(&ph); // ph
DestroyGList(&pt); // pt
}
}
//13. ： L T
Status CopyGList(GList *T,GList L)
{
if(!L) //L
{
*T=NULL;
return OK;
}
*T=(GList)malloc(sizeof(GLNode));
if(!*T)
exit(OVERFLOW);
(*T)->tag=L->tag; //
if(L->tag==ATOM) //
(*T)->a.atom=L->a.atom; //
else
CopyGList(&(*T)->a.hp,L->a.hp); // ，
if(L->tp==NULL) //
(*T)->tp=L->tp;
else
CopyGList(&(*T)->tp,L->tp); //
return OK;
}
//14. L ,
int GListLength(GList L)
{
int len=0;
GList p;
if(L->tag==LIST&&!L->a.hp) //
return 0; // 0
else if(L->tag==ATOM) //
return 1;
else //
{
p=L->a.hp;
do
{
len++;
p=p->tp;
}while(p);
return len;
}
}
//15. L
int GListDepth(GList L)
{
int max,dep;
GList pp;
if(L==NULL||L->tag==LIST&&!L->a.hp)
return 1; // 1
else if(L->tag==ATOM)
return 0; // 0
else //
for(max=0,pp=L->a.hp;pp;pp=pp->tp)
{
dep=GListDepth(pp); // pp
if(dep>max)
max=dep;
}
return max+1; // 1
}
//16. L
GList GetHead(GList L)
{
GList h;
InitGList(&h); // h
if ( !L || L->tag==LIST && !L->a.hp) // L
{
printf ( "
!"); //
exit ( 0); // ,
}
h=(GList)malloc(sizeof(GLNode)); // h
if ( !h) // ,
exit ( OVERFLOW);
h->tag=L->a.hp->tag; //
h->tp=NULL;
if ( h->tag==ATOM) //
h->a.atom=L->a.hp->a.atom;
else //
CopyGList(&h->a.hp,L->a.hp->a.hp);
return h; //
}
//17. L
GList GetTail(GList L)
{
GList T; // T
if ( !L) // L
{
printf ( "
!"); //
exit ( 0); //
}
T=(GList)malloc(sizeof(GLNode)); // T
if ( !T) // ,
exit ( OVERFLOW);
T->tag=LIST; // ,
T->tp=NULL;
CopyGList(&T->a.hp,L->a.hp->tp); // T
return T; //
}
//18. L
void Traverse_GL(GList L,void(*v)(AtomType))
{
GList hp;
if(L) //L
{
if(L->tag==ATOM) //L
{
v(L->a.atom);
hp=NULL;
}
else //L
hp=L->a.hp;
Traverse_GL(hp,v); //
Traverse_GL(L->tp,v);
}
}
//19. ， Traverse_GL
void visit(AtomType e)
{
printf("%c ", e);
}
//20.
void main( )
{
char p[80];
int i;
GList l,m;
HString t;
InitString(&t); // HString
InitGList(&l); //
InitGList(&m);
do
{
printf ( "
***************************************
");
printf ( "\t :
");
printf ( "\t1、 L
");
printf ( "\t2、 L
");
printf ( "\t3、 L
");
printf ( "\t4、 L
");
printf ( "\t5、 L M
");
printf ( "\t6、 M
");
printf ( "\t7、 M
");
printf ( "\t8、 M
");
printf ( "\t9、 L ，
");
printf ( "\t10、 L ，
");
printf ( "\t0、
");
printf ( "***************************************
");
do
{
printf ( " (0-10)：");
scanf ( "%d",&i); getchar ( );
}while ( i<0||i>10);
switch(i){
case 1:
printf(" L【 (a,(b),b))】：");
gets(p);
StrAssign(&t,p);
printf(" L ：%s
",t);
CreateGList(&l,t); // t l
break;
case 2:
printf ( " L =%d
",GListLength(l)); //
break;
case 3:
printf ( " L =%d
",GListDepth(l)); //
break;
case 4:
printf ( " L：
");
Traverse_GL(l,visit); // ， l
printf ( "
");
break;
case 5:
CopyGList(&m,l);
printf ( " L M， M ：%s
",t);
break;
case 6:
printf ( " M =%d
",GListLength(m)); //
break;
case 7:
printf ( " M =%d
",GListDepth(m)); //
break;
case 8:
printf ( " M：
");
Traverse_GL(m,visit); // ， m
printf ( "
");
break;
case 9:
DestroyGList(&m); // m
m=GetHead(l); // l
printf ( " L ， ：
");
Traverse_GL(m,visit); // m
printf ( "
");
break;
case 10:
DestroyGList(&m); // m
m=GetTail(l); // l
printf ( "m L ， ：
");
Traverse_GL(m,visit); // m
printf ( "
");
}
}while ( i);
printf ( "
");
DestroyGList(&m); // m
system("PAUSE"); //
}