清华大学 严蔚敏版数据结构 实验第四章.doc

学号 专业 计算机科学与技术 姓名 实验日期 2010.5.10 教师签字 成绩 实验报告【实验名称】第四章-串的基本操作及应用【实验目的】熟练掌握串的基本操作，并能应用其解决简单的问题，加深对串存储结构的认识。【实验内容】#include #include #include /* malloc()等 */ #include /* INT_MAX等 */ #include /* EOF(=Z或F6),NULL */ #include /* atoi() */ #include /* eof() */ #include /* floor(),ceil(),abs() */ #include /* exit() */ #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1typedef int Status; typedef struct char *ch; /* 若是非空串,则按串长分配存储区,否则ch为NULL */ int length; /* 串长度 */ HString;Status StrAssign(HString *T,char *chars)int i,j;char *c;if(T-ch)free(T-ch);for(i=0,c=chars; c;+i,+c);if(!i)T-ch=NULL;T-length=0;elseif(T-ch=(char *)malloc(i*sizeof(char) exit(OVERFLOW); for(j=0;jchj=charsj; T-length=i; return OK; Status StrCopy(HString &T,HString S) /由串S复制串Tint i;if(T.ch)free(T.ch);T.ch=(char *)malloc(S.length*sizeof(char);if(!T.ch)exit(OVERFLOW);for(i=0;iS.length;i+)T.chi=S.chi;T.length=S.length;return OK;Status StrEmpty(HString S)if(S.length=0)return TRUE;else return FALSE;int StrCompare(HString S,HString T)int i;for(i=0;iS.length & iT.length;i+)if(S.chi!=T.chi) return S.chi-T.chi;return S.length-T.length;Status StrLength(HString S)return S.length;Status ClearString(HString *S) /* 将S清为空串 */ if(*S).ch) free(*S).ch); (*S).ch=NULL; (*S).length=0; return OK; Status Concat(HString *T,HString S1,HString S2) /用T返回由S1和S2连接而成的新新串int i;if(*T).ch)free(*T).ch);if(!(char *)malloc(S1.length+S2.length)*sizeof(char)exit(OVERFLOW);elsefor(i=0;ichi=S1.chi;T-length=S1.length+S2.length;for(i=0;ichi+S1.length=S2.chi;return OK;Status SubString(HString &Sub,HString S,int pos,int len)/在s中求子串Subint i;if(posS.length|lenS.length-pos+1)return ERROR;if(Sub.ch)free(Sub.ch);if(!len)Sub.ch=NULL;Sub.length=0;elseSub.ch=(char *)malloc(len*sizeof(char);if(!Sub.ch) return OVERFLOW;for(i=0;i0) n=StrLength(S); m=StrLength(T); i=pos; while(i=m-n+1) SubString(sub,S,i,m); if(StrCompare(sub,T)!=0) +i; else return i; return 0; Status StrInsert(HString &S,int pos,HString T)/在串S的第pos个字符之前插入串Tint i;if(posS.length+1)return ERROR;if(T.length)S.ch=(char*)realloc(S.ch,(S.length+T.length)*sizeof(char);if(!S.ch) exit(OVERFLOW);for(i=S.length-1;i=pos-1;i-)S.chi+T.length=S.chi;for(i=0;iT.length;i+)S.chpos+i-1=T.chi;S.length+=T.length;return OK;Status StrDelete(HString &S,int pos,int len)int i;if(iS.length-len+1) exit(ERROR); for(i=pos-1;i=S.length-len;i+) S.chi=S.chi+len; S.length-=len; S.ch=(char*)realloc(S.ch,S.length*sizeof(char); return OK; Status StrInsert(HString *S,int pos,HString T) /* 1posStrLength(S)+1。在串S的第pos个字符之前插入串T */ int i; if(pos(*S).length+1) /* pos不合法 */ return ERROR; if(T.length) /* T非空,则重新分配空间,插入T */ (*S).ch=(char*)realloc(*S).ch,(*S).length+T.length)*sizeof(char); if(!(*S).ch) exit(OVERFLOW); for(i=(*S).length-1;i=pos-1;-i) /* 为插入T而腾出位置 */ (*S).chi+T.length=(*S).chi; for(i=0;iT.length;i+) (*S).chpos-1+i=T.chi; /* 插入T */ (*S).length+=T.length; return OK; Status Replace(HString &S,HString T,HString V) /* 初始条件: 串S,T和V存在,T是非空串（此函数与串的存储结构无关） */ /* 操作结果: 用V替换主串S中出现的所有与T相等的不重叠的子串 */ int i=1; /* 从串S的第一个字符起查找串T */ if(StrEmpty(T) /* T是空串 */ return ERROR; do i=Index(S,T,i); /* 结果i为从上一个i之后找到的子串T的位置 */ if(i) /* 串S中存在串T */ StrDelete(S,i,StrLength(T); /* 删除该串T */ StrInsert(S,i,V); /* 在原串T的位置插入串V */ i+=StrLength(V); /* 在插入的串V后面继续查找串T */ while(i); return OK; void StrPrint(HString T) /* 输出T字符串。另加 */ int i; for(i=0;iT.length;i+) printf(%c,T.chi); printf(n); void main() int i; char c,*p=God bye!,*q=God luck!; HString t,s,r; InitString(&t); /* HString类型必需初始化 */ InitString(&s); InitString(&r); StrAssign(&t,p); printf(串t为: ); StrPrint(t); printf(串长为%d 串空否？%d(1:空 0:否)n,StrLength(t),StrEmpty(t); StrAssign(&s,q); printf(串s为: ); StrPrint(s); i=StrCompare(s,t); if(i0) c=; printf(串s%c串tn,c); Concat(&r,t,s); printf(串t联接串s产生的串r为: ); StrPrint(r); StrAssign(&s,oo); printf(串s为: ); StrPrint(s); StrAssign(&t,o); printf(串t为: ); StrPrint(t); Replace(&r,t,s); printf(把串r中和串t相同的子串用串s代替后，串r为:n); StrPrint(r); ClearString(&s); printf(串s清空后，串长为%d 空否？%d(1:空 0:否)n,StrLength(s),StrEmpty(s); SubString(&s,r,6,4); printf(串s为从串r的第6个字符起的4个字符，长度为%d 串s为: ,s.length); StrPrint(s); StrCopy(&t,r); printf(复制串t为串r,串t为: ); StrPrint(t); StrInsert(&t,