数据结构——串实践报告

.成绩：实 验 报 告课程名称： 数据结构实践课实验项目： 定长串存储方法姓 名 ：专 业 ：班 级 ：学 号 ：计算机科学与技术学院实验教学中心;.2017年9月 23日实验项目名称：串的定长存储表示方法一、实践目的：1. 熟练掌握串的定长顺序存储表示方法。2. 利用串的基本操作实现相关算法。二、实践内容：1. 实现串的定长顺序存储表示的基本操作。并用主程序进行多次验证。2. 设 s=abcdefghijk、t=cde为两个字符串，利用定长顺序存储结构的串操作，判断 t 是否为 s 的子串。如果是，输出子串所在位置（第一个字符）。编程实现。3. 已知三个字符串分别为s= ababababcaabcbcaaaaa，a s1=caab, s2=bcb 。 利 用 所 学 字 符 串 基 本 运 算 的 函 数 得 到 结 果 串 为 ： s3= caabcbcaaaaaacaaaaa。a 编程实现。三、实验用设备仪器及材料计算机四、实验原理及接线五、实验操作步骤/ 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.5 status strassign(sstring &t,char *chars)/生成一个其值等于chars的串 t int i;if(strlen(chars)maxstrlen) return error;elset0=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则, int i;返回值 0;若 s=t则,返回值 =0;若 st则,返回值 0for(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)else/未截断for(i=1; i=s10; i+) ti=s1i;for(i=1; i=s20; i+)ts10+i=s2i;t0=s10+s20;return true;/截断 s2for(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非空,1 pos strlengt。h(s算) 法 4.5 int i,j;if(1=pos&pos=s0)i=pos; j=1;while(i=s0&jt0)i=i-j+2; j=1;elsereturn i-t0; return 0;elsereturn 0;status strinsert(sstring s,int pos,sstring t)/初始条件 : 串 s和 t 存在,1 pos strlength(s)+1/操作结果 : 在串 s的第 pos 个字符之前插入串t。完全插入返回 true部, falseint 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;/ 部分插入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存在,1 pos strlengt-hle(sn)+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的第一个字符起查找串tif(strempty(t) / t 是空串return error;doi=index(s,t,i); / 结果 i 为从上一个 i 之后找到的子串 t 的位置if(i) /串 s中存在串 tstrdelete(s,i,strlength(t); / 删 除 该 串 t strinsert(s,i,v); / 在 原 串 t 的 位 置 插 入 串 v i+=strlength(v); /在插入的串 v 后面继续查找串twhile(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.5 status strassign(sstring &t,char *chars)/生成一个其值等于chars的串 t int i;if(strlen(chars)maxstrlen) return error;elset0=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则, int i;返回值 0;若 s=t则,返回值 =0;若 st则,返回值 0for(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)else/未截断for(i=1; i=s10; i+) ti=s1i;for(i=1; i=s20; i+) ts10+i=s2i;t0=s10+s20;return true;/截断 s2for(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。) int i,j;if(1=pos&pos=s0)算法 4.5i=pos; j=1;while(i=s0&jt0)i=i-j+2; j=1;elseelsereturn i-t0; return 0;return 0;status strinsert(sstring s,int pos,sstring t)/初始条件 : 串 s和 t 存在,1posstrlength(s)+1/操作结果 : 在串 s的第 pos 个字符之前插入串t。完全插入返回 true部, falseint 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;/ 部分插入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存在,1 posstrlength(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)/初