共享结构的库存模型实现 (一)

见代码

[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 *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< 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);