数据结构——串实践报告.doc

_成绩：实 验 报 告课程名称：数据结构实践课实验项目：定长串存储方法姓 名：专 业：班 级：学 号：计算机科学与技术学院实验教学中心2017 年 9 月 23 日精品资料_实验项目名称： 串的定长存储表示方法 一、实践目的：1. 熟练掌握串的定长顺序存储表示方法。2. 利用串的基本操作实现相关算法。二、实践内容：1. 实现串的定长顺序存储表示的基本操作。并用主程序进行多次验证。2. 设s=abcdefghijk、t=cde为两个字符串，利用定长顺序存储结构的串操作，判断t是否为s的子串。如果是，输出子串所在位置（第一个字符）。编程实现。3. 已知三个字符串分别为s=ababababcaabcbcaaaaaa，s1=caab,s2=bcb。利用所学字符串基本运算的函数得到结果串为：s3=caabcbcaaaaaacaaaaaa。编程实现。三、实验用设备仪器及材料计算机四、实验原理及接线五、实验操作步骤/ main4-1.cpp 检验bo4-1.cpp的主程序/ c1.h (程序名)#include#include#include / malloc()等#include / INT_MAX等#include / EOF(=Z或F6),NULL#include / atoi()#include / eof()#include / floor(),ceil(),abs()#include / exit()/ #include / cout,cin/ 函数结果状态代码#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1/ #define OVERFLOW -2 因为在math.h中已定义OVERFLOW的值为3,故去掉此行typedef int Status; / Status是函数的类型,其值是函数结果状态代码，如OK等typedef int Boolean; / Boolean是布尔类型,其值是TRUE或FALSE/ c4-1.h 串的定长顺序存储表示#define MAXSTRLEN 30 / 用户可在255以内定义最大串长（1个字节）typedef char SStringMAXSTRLEN+1; / 0号单元存放串的长度/ bo4-1.cpp 串采用定长顺序存储结构(由c4-1.h定义)的基本操作(14个)/ SString是数组，故不需引用类型。此基本操作包括算法4.2,4.3,4.5Status StrAssign(SString &T,char *chars) / 生成一个其值等于chars的串T int i; if(strlen(chars)MAXSTRLEN) return ERROR; else T0=strlen(chars); for(i=1; i=T0; i+) Ti=*(chars+i-1); return OK; Status StrCopy(SString T,SString S) / 由串S复制得串T int i; for(i=0; iT,则返回值0;若S=T,则返回值=0;若ST,则返回值0 int i; for(i=1; i=S0&i=T0; +i) if(Si!=Ti) return Si-Ti; return S0-T0;int StrLength(SString S) / 返回串的元素个数 return S0;Status ClearString(SString S) / 初始条件:串S存在。操作结果:将S清为空串 S0=0;/ 令串长为零 return OK;Status Concat(SString &T,SString S1,SString S2) / 算法4.2改 / 用T返回S1和S2联接而成的新串。若未截断，则返回TRUE，否则FALSE int i; if(S10+S20=MAXSTRLEN) / 未截断 for(i=1; i=S10; i+) Ti=S1i; for(i=1; i=S20; i+) TS10+i=S2i; T0=S10+S20; return TRUE; else / 截断S2 for(i=1; i=S10; i+) Ti=S1i; for(i=1; i=MAXSTRLEN-S10; i+) TS10+i=S2i; T0=MAXSTRLEN; return FALSE; Status SubString(SString &Sub,SString S,int pos,int len) / 用Sub返回串S的第pos个字符起长度为len的子串。算法4.3 int i; if(posS0|lenS0-pos+1) return ERROR; for(i=1; i=len; i+) Subi=Spos+i-1; Sub0=len; return OK;int Index(SString S,SString T,int pos) / 返回子串T在主串S中第pos个字符之后的位置。若不存在,则函数值为0。 / 其中,T非空,1posStrLength(S)。算法4.5 int i,j; if(1=pos&pos=S0) i=pos; j=1; while(i=S0&jT0) return i-T0; else return 0; else return 0;Status StrInsert(SString S,int pos,SString T) / 初始条件: 串S和T存在,1posStrLength(S)+1 / 操作结果: 在串S的第pos个字符之前插入串T。完全插入返回TRUE,部分插入返回FALSE int i; if(posS0+1) return ERROR; if(S0+T0=pos; i-) Si+T0=Si; for(i=pos; ipos+T0; i+) Si=Ti-pos+1; S0=S0+T0; return TRUE; else /部分插入 for(i=MAXSTRLEN; i=pos; i-) Si=Si-T0; for(i=pos; ipos+T0; i+) Si=Ti-pos+1; S0=MAXSTRLEN; return FALSE; Status StrDelete(SString S,int pos,int len) / 初始条件: 串S存在,1posStrLength(S)-len+1 / 操作结果: 从串S中删除第pos个字符起长度为len的子串 int i; if(posS0-len+1|len0) return ERROR; for(i=pos+len; i=S0; i+) Si-len=Si; S0-=len; return OK;Status Replace(SString S,SString T,SString 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 DestroyString() / 由于SString是定长类型,无法销毁void StrPrint(SString T) / 输出字符串T。另加 int i; for(i=1; i=T0; i+) printf(%c,Ti); printf(n);/ printf(n);int main() char g=1; int i,j; Status k; char s,cMAXSTRLEN+1; SString t,s1,s2; printf(请输入串s1: ); gets(c); k=StrAssign(s1,c); if(!k) printf(串长超过MAXSTRLEN(=%d)n,MAXSTRLEN); exit(0); printf(串长为%d 串空否？%d(1:是 0:否)n,StrLength(s1),StrEmpty(s1); StrCopy(s2,s1); printf(拷贝s1生成的串为: ); StrPrint(s2); printf(请输入串s2: ); gets(c); k=StrAssign(s2,c); if(!k) printf(串长超过MAXSTRLEN(%d)n,MAXSTRLEN); exit(0); i=StrCompare(s1,s2); if(i0) s=; printf(串s1%c串s2n,s); k=Concat(t,s1,s2); printf(串s1联接串s2得到的串t为: ); StrPrint(t); if(k=FALSE) printf(串t有截断n); ClearString(s1); printf(清为空串后,串s1为: ); StrPrint(s1); printf(串长为%d 串空否？%d(1:是 0:否)n,StrLength(s1),StrEmpty(s1); printf(求串t的子串,请输入子串的起始位置,子串长度: ); scanf(%d,%d,&i,&j); k=SubString(s2,t,i,j); if(k) printf(子串s2为: ); StrPrint(s2); printf(从串t的第pos个字符起,删除len个字符，请输入pos,len: ); scanf(%d,%d,&i,&j); StrDelete(t,i,j); printf(删除后的串t为: ); StrPrint(t); i=StrLength(s2)/2; StrInsert(s2,i,t); printf(在串s2的第%d个字符之前插入串t后,串s2为:n,i); StrPrint(s2); i=Index(s2,t,1); printf(s2的第%d个字母起和t第一次匹配n,i); SubString(t,s2,1,1); printf(串t为：); StrPrint(t); Concat(s1,t,t); printf(串s1为：); StrPrint(s1); Replace(s2,t,s1); printf(用串s1取代串s2中和串t相同的不重叠的串后,串s2为: ); StrPrint(s2); while(g!=0)scanf(%c,&g);/ main4-1.cpp 检验bo4-1.cpp的主程序/ c1.h (程序名)#include#include#include / malloc()等#include / INT_MAX等#include / EOF(=Z或F6),NULL#include / atoi()#include / eof()#include / floor(),ceil(),abs()#include / exit()/ #include / cout,cin/ 函数结果状态代码#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1/ #define OVERFLOW -2 因为在math.h中已定义OVERFLOW的值为3,故去掉此行typedef int Status; / Status是函数的类型,其值是函数结果状态代码，如OK等typedef int Boolean; / Boolean是布尔类型,其值是TRUE或FALSE/ c4-1.h 串的定长顺序存储表示#define MAXSTRLEN 30 / 用户可在255以内定义最大串长（1个字节）typedef char SStringMAXSTRLEN+1; / 0号单元存放串的长度/ bo4-1.cpp 串采用定长顺序存储结构(由c4-1.h定义)的基本操作(14个)/ SString是数组，故不需引用类型。此基本操作包括算法4.2,4.3,4.5Status StrAssign(SString &T,char *chars) / 生成一个其值等于chars的串T int i; if(strlen(chars)MAXSTRLEN) return ERROR; else T0=strlen(chars); for(i=1; i=T0; i+) Ti=*(chars+i-1); return OK; Status StrCopy(SString T,SString S) / 由串S复制得串T int i; for(i=0; iT,则返回值0;若S=T,则返回值=0;若ST,则返回值0 int i; for(i=1; i=S0&i=T0; +i) if(Si!=Ti) return Si-Ti; return S0-T0;int StrLength(SString S) / 返回串的元素个数 return S0;Status ClearString(SString S) / 初始条件:串S存在。操作结果:将S清为空串 S0=0;/ 令串长为零 return OK;Status Concat(SString &T,SString S1,SString S2) / 算法4.2改 / 用T返回S1和S2联接而成的新串。若未截断，则返回TRUE，否则FALSE int i; if(S10+S20=MAXSTRLEN) / 未截断 for(i=1; i=S10; i+) Ti=S1i; for(i=1; i=S20; i+) TS10+i=S2i; T0=S10+S20; return TRUE; else / 截断S2 for(i=1; i=S10; i+) Ti=S1i; for(i=1; i=MAXSTRLEN-S10; i+) TS10+i=S2i; T0=MAXSTRLEN; return FALSE; Status SubString(SString &Sub,SString S,int pos,int len) / 用Sub返回串S的第pos个字符起长度为len的子串。算法4.3 int i; if(posS0|lenS0-pos+1) return ERROR; for(i=1; i=len; i+) Subi=Spos+i-1; Sub0=len; return OK;int Index(SString S,SString T,int pos) / 返回子串T在主串S中第pos个字符之后的位置。若不存在,则函数值为0。 / 其中,T非空,1posStrLength(S)。算法4.5 int i,j; if(1=pos&pos=S0) i=pos; j=1; while(i=S0&jT0) return i-T0; else return 0; else return 0;Status StrInsert(SString S,int pos,SString T) / 初始条件: 串S和T存在,1posStrLength(S)+1 / 操作结果: 在串S的第pos个字符之前插入串T。完全插入返回TRUE,部分插入返回FALSE int i; if(posS0+1) return ERROR; if(S0+T0=pos; i-) Si+T0=Si; for(i=pos; ipos+T0; i+) Si=Ti-pos+1; S0=S0+T0; return TRUE; else /部分插入 for(i=MAXSTRLEN; i=pos; i-) Si=Si-T0; for(i=pos; ipos+T0; i+) Si=Ti-pos+1; S0=MAXSTRLEN; return FALSE; Status StrDelete(SString S,int pos,int len) / 初始条件: 串S存在,1posStrLength(S)-len+1 / 操作结果: 从串S中删除第pos个字符起长度为len的子串 int i; if(posS0-len+1|len0) return ERROR; for(i=pos+len; i=S0; i+) Si-len=Si; S0-=len; return OK;Status Replace(SString S,SString T,SString V) / 初始条件: 串S,T和V存在,T是非空串（此函数与串的存储结构无关） / 操作结果