//glist.h
//----------------------- 广义表 ---------------------------------------
typedef enum...{ATOM, LIST} ElemTag; //ATOM==0:原子，LIST==1：子表
typedef int AtomType; //原子的数据类型
typedef struct GLNode...{
ElemTag tag; //公共部分，区分原子节点和表节点
union...{ //原子节点和表节点的联合部分
AtomType atom; //原子节点的值
struct GLNode *hp; //表节点的表头指针
};
struct GLNode *tp; //相当于线形链表的next，指向下一个元素
}*GList;
//----------------- 基本操作的算法实现 -------------------------------
Status Sever(HString &str, HString &hstr)...{
//将非空串str分割成两部分：hstr为第一个','之前的自串，str为之后的子串
int n = StrLength(str), i=1, k=0; //k记尚未配对的左括号个数
HString ch;StrInit(ch);StrAssign(ch,"a");
for(i=1, k=0; i<=n&&ch.ch[0]!=','||k!=0;i++)...{ //搜索最外层的第一个','
SubString(ch,str,i,1);
if(ch.ch[0]=='(') ++k;
else if(ch.ch[0]==')')--k;
}
if(i<=n)...{ SubString(hstr,str,1,i-2); SubString(str,str,i,n-i+1); }
else...{StrCopy(hstr,str); ClearString(str);}
return OK;
}
Status CreateGList(GList &L, HString S)...{
//采用头尾链接存储结构,由广义表的书写形式串S创建广义表L
HString emp; StrInit(emp); StrAssign(emp,"()");
GList p,q;
if( !StrCompare(S,emp) ) L=NULL; //创建空表
else...{
if(!(L=(GList)malloc(sizeof(GLNode)))) exit(OVERFLOW); //创建节点
if(StrLength(S)==1) ...{L->tag = ATOM; L->atom = *(S.ch);} //创建原子节点
else...{
L->tag = LIST; p=L;
HString sub,hsub; StrInit(sub); StrInit(hsub);
SubString(sub,S,2,StrLength(S)-2); //脱外层扩号
do...{
Sever(sub,hsub);
CreateGList(p->hp,hsub); q=p;
if(!StrEmpty(sub))...{
if(!(p=(GLNode *) malloc(sizeof(GLNode))))
exit(OVERFLOW);
p->tag = LIST; q->tp = p;
}
}while(!StrEmpty(sub));
q->tp = NULL;
}
}
return OK;
}
Status CopyGList(GList &T, GList L)...{
//L复制给T
if(!L) T=NULL;
else...{
if(!(T=(GList)malloc(sizeof(GLNode)))) exit(OVERFLOW);
T->tag = L->tag;
if(L->tag ==ATOM ) T->atom = L->atom;
else...{
CopyGList(T->hp, L->hp);
CopyGList(T->tp, L->tp);
}
}
return OK;
}
int GListDepth(GList L)...{
//求广义表的深度
if(!L) return 1;
if(L->tag==ATOM) return 0;
int max;
GList pp;
for(max=0,pp=L;pp;pp=pp->tp)...{
int dep = GListDepth(pp->hp);
if(dep>max) max= dep;
}
return max+1;
}
Status PrintGList(GList L)...{
//显示广义表
GList p = L;
if(!L) ...{printf("()"); return OK; }
if(L->tag== ATOM) printf("%c",L->atom);
else...{
printf("(");
while(p!=NULL)...{
PrintGList(p->hp);
p=p->tp;
if(p) ...{ printf(","); }
}
printf(")");
}
return OK;
}
2.
//hstring.h
//----------------- 串的堆分配存储表示 ---------------------------
typedef struct{
char *ch; //若是非空串，则按串长分配存储区，否则ch为NULL
int length; //串长度
}HString;
//----------------- 栈的基本操作的算法实现 --------------------------------
Status StrInit(HString &T){
//初始化串
T.ch=NULL; T.length=0;
return OK;
}
Status StrAssign(HString &T, char *chars){
//生成一个其值等于串常量chars的串T
//if(T.ch) free(T.ch); //释放原有的串空间
int len; char *c;
for(len=0, c=chars;*c;++len,++c); //求chars的长度i;
if(!len) {T.ch=NULL; T.length=0;}
else{
if( !(T.ch = (char *) malloc(len*sizeof(char) ) ))
exit(OVERFLOW);
for(int i=0;i<len;i++) T.ch[i] = chars[i];
T.ch[i]='\0'; //结尾加上\0
T.length = len;
}
return OK;
}
int StrLength(HString s){
//返回串长度
return s.length;
}
void StrPrint(HString s){
//打印串
for(int i=0;i<s.length;i++)
printf("%c",s.ch[i]);
printf("\n");
}
int Index(HString s,HString t, int pos){
//返回子串t在主串s中第pos个字符之后的位置。如不存在，则返回0
int i=pos,j=1;
while(i<=s.length && j<=t.length){
if(s.ch[i-1]==t.ch[j-1]) i++,j++;
else i=i-j+2,j=1;
}
if(j>t.length) return i-t.length;
else return 0;
}
int Next(HString s,int j){
//KMP模式匹配的next函数
if(j==1) return 0;
for(int k=j-1;k>1;k--){
for(int i=1;i<k;i++){
if(s.ch[i-1] != s.ch[j-k+i-1])
break;
}
if(i==k) break;
}
return k;
}
int Index_KMP(HString s,HString t, int pos){
//KMP算法
int i=pos,j=1;
while(i<=s.length && j<=t.length){
if(j==0 || s.ch[i-1]==t.ch[j-1]) i++,j++;
else j=Next(t,j);
}
if(j>t.length) return i-t.length;
else return 0;
}
Status SubString(HString &sub, HString s, int pos, int len){
//用sub返回串S的第pos个字符起长度为len的子串
if(pos<1 || pos>s.length || len<0 )
return ERROR;
if( len>s.length-pos+1 ) len=s.length-pos+1; //如果所取长度超过实际长度，输出实际长度
// if(sub.ch) free(sub.ch);
if(!len){ sub.ch=NULL; sub.length=0; }
else{
if( !(sub.ch = (char *) malloc(len*sizeof(char) ) ))
exit(OVERFLOW);
for(int i=0;i<len;i++) sub.ch[i] = s.ch[pos+i-1];
sub.ch[i]='\0'; //结尾加上\0
sub.length = len;
}
return OK;
}
Status ClearString(HString &s){
//清空s
if(s.ch) {
// realloc(s.ch,0);
s.ch=NULL;
}
s.length =0;
return OK;
}
int StrCompare(HString s,HString t){
//比较s,t
for(int 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;
}
Status Concat(HString &t, HString s1, HString s2){
//用t返回由s1和s2联接而成的新串
//if(t.ch) free(t.ch);
if(!(t.ch=(char *)malloc((s1.length+s2.length)*sizeof(char))))
exit(OVERFLOW);
for(int i=0;i<s1.length;i++) t.ch[i]=s1.ch[i];
for(i=0;i<s2.length;i++) t.ch[i+s1.length]=s2.ch[i];
t.ch[s1.length+s2.length]='\0';
t.length = s1.length+s2.length;
return OK;
}
Status StrCopy(HString &t,HString s){
if(!(t.ch=(char *)malloc( (s.length)*sizeof(char))))
exit(OVERFLOW);
for(int i=0;i<s.length;i++) t.ch[i]=s.ch[i];
t.ch[s.length] = '\0';
t.length = s.length;
return OK;
}
Status StrEmpty(HString s){
return s.length==0;
return OK;
}
