串的操作实验报告.doc

数据结构实验报告报告名称 串的操作 专 业 网络工程 班 级 1001 学 号 201003120129 姓 名 张剑 指导教师 陈淑红 李珍辉 黄哲 2012年 5月8日 一、实验目的：熟悉串类型的实现方法，了解简单文字处理的设计方法。二、实验内容与基本要求：1. 设计可以在主串s中第i个位置之前插入一个子串t的程序。2. 设计可以在主串s中从第i个位置开始共取m个字符，求子串的程序。3. 设计一个程序求子串t在主串s中的起始位置 三、概要设计：1.数据结构：#include #define MaxSize 100 /*最多的字符个数*/typedef struct char dataMaxSize; /*定义可容纳MaxSize个字符的空间*/ int len; /*标记当前实际串长*/ SqString;2.抽象数据类型：ADT String 数据对象：D ai |aiCharacterSet, i=1,2,.,n, n0 数据关系：R1 | ai-1, ai D, i=2,.,n StrAssign (&T, chars) 初始条件：chars 是字符串常量。 操作结果：把 chars 赋为 T 的值。 StrCopy (&T, S) 初始条件：串 S 存在。 操作结果：由串 S 复制得串 T。DestroyString (&S) 初始条件：串 S 存在。 操作结果：串 S 被销毁。StrEmpty(S)初始条件：串S存在。 操作结果：若 S 为空串，则返回 TRUE， 否则返回 FALSE。StrCompare (S, T)初始条件：串 S 和 T 存在。操作结果：若S T，则返回值 0； 若S = T，则返回值 = 0； 若S T，则返回值 0。 StrLength (S) 初始条件：串 S 存在。 操作结果：返回 S 的元素个数， 称为串的长度。Concat (&T, S1, S2) 初始条件：串 S1 和 S2 存在。 操作结果：用 T 返回由 S1 和 S2联接而成的新串SubString (&Sub, S, pos, len)初始条件：串 S 存在，1posStrLength(S) 且0lenStrLength(S)-pos+1。操作结果：用 Sub 返回串 S 的第 pos 个字符起 长度为 len 的子串。Index (S, T, pos)初始条件：串S和T存在，T是非空串，1posStrLength(S)。操作结果： 若主串 S 中存在和串 T 值相同 的子串, 则返回它在主串 S 中第pos个 字符之后第一次出现的位置； 否则函数值为0。 Replace (&S, T, V) 初始条件：串S, T和 V 均已存在且 T 是非空串。 操作结果：用V替换主串S中出现的所有与（模式串）T 相等的不重叠的子串。StrInsert (&S, pos, T)初始条件：串S和T存在， 1posStrLength(S)1。操作结果：在串S的第pos个字符之前 插入串T。StrDelete (&S, pos, len)初始条件：串S存在 1posStrLength(S)-len+1。操作结果：从串S中删除第pos个字符 起长度为len的子串。 ClearString (&S) 初始条件：串S存在。 操作结果：将S清为空串四、详细设计：#include #define MaxSize 100 /*最多的字符个数*/typedef struct char dataMaxSize; /*定义可容纳MaxSize个字符的空间*/ int len; /*标记当前实际串长*/ SqString;void StrAssign(SqString &str,char cstr)/*str为引用型参数*/ int i;char aMaxSize;gets(a);cstr=a; for (i=0;cstri!=0;i+) str.datai=cstri; str.len=i;SqString InsStr(SqString s1,int i,SqString s2) int j; SqString str; str.len=0; if (is1.len+1) /*参数不正确时返回空串*/printf(参数不正确n); return s1; for (j=0;ji-1;j+) /*将s1.ch0s1.chi-2复制到str*/ str.dataj=s1.dataj; for (j=0;js2.len;j+) /*将s2.ch0s2.chs2.len-1复制到str*/ str.datai+j-1=s2.dataj; for (j=i-1;js1.len;j+) /*将s1.chi-1s.chs1.len-1复制到str*/ str.datas2.len+j=s1.dataj; str.len=s1.len+s2.len; return str;SqString SubStr(SqString s,int i,int j) SqString str; int k; str.len=0; if (is.len | js.len)printf(参数不正确n); return str; /*参数不正确时返回空串*/ for (k=i-1;ki+j-1;k+) /*将s.chis.chi+j复制到str*/ str.datak-i+1=s.datak; str.len=j; return str; int Index(SqString s,SqString t)int i=0,j=0;while(is.len&j=t.len)return(i-t.len+1);elsereturn(-1);void DispStr(SqString str) int i; if (str.len0) for (i=0;istr.len;i+) printf(%c,str.datai);printf(n); main() SqString s,s0,s1,s2,s3,s4,s5; char *p,*q,*r,*l,*m; int c,x,y,z,w; printf(/*本程序可实现如下功能*/n); printf(t1.在主串s中第i个位置之前插入一个子串tnt2.在主串s中从第i个位置开始共取m个字符，求子串tnt3.求子串t在主串s中的起始位置tnt4.退出程序n); while(c) printf(请选择您要进入的功能: );scanf(%d,&x); switch(x) case 1: getchar(); printf(请输入主串S：); StrAssign(s1,p); printf(请输入子串T：); StrAssign(s2,q); printf(请输入插入位置i：); scanf(%d,&y); InsStr(s1,y,s2); s=InsStr(s1,y,s2); printf(输出新串为: ); DispStr(s); break; case 2: getchar(); printf(请输入主串S：); StrAssign(s3,r); printf(从位置 y 开始取长度为 z 的子串：n); scanf(%d%d,&y,&z); SubStr(s3,y,z); s0=SubStr(s3,y,z); printf(输出子串为: ); DispStr(s0); break; case 3: getchar(); printf(请输入主串S：); StrAssign(s4,l); printf(请输入子串T：); StrAssign(s5,m); Index(s4,s5); w=Index(s4,s5); if(w) printf(主串和子串在第%d个字符处首次匹配n,w); else printf(主串和子串匹配不成功n); break; case 4: getchar();c=0;break; default:printf(输入错误，请重试！n); break; 五、调试分析及测试结果：测试数据：1. 在主串s(abcdefg)中第3个位置之前插入一个子串t(apple),输出新串。2. 在主串s(thisisacprogram)中从第5个位置开始共取3个字符，求子串的程序。3. 主串s(thekingisababyandstrong),子串t(isababy),输出子串t在主串s中的起始位置。 测试结果及分析： 图一1.程序通过编译后，运行程序。进入选择界面，该程序主要实现三个功能，如图一所示。“1.在主串s中第i个位置之前插入一个子串；2.在主串s中从第i个位置开始共取m个字符，求子串；3.求子串t在主串s中的起始位置。”此界面通过switch分支语句实现。按相应的数字键进入相应的功能。 图二2.按数字键1键实现串的插入功能。输入主串“abcdefg”，依照提示输入子串“apple”，选择插入的位置为i=3；按回车键结束，输入新串为“abapplecdefg”,程序运行正确，输出结果无误。在程序运行过程中，调用串的创建StrAssign（）函数，插入字符InsStr（）函数，以及字符串的输出DispStr（）函数。 图三 3.输入数字2，进入从主串中的第i个位置开始共取m个字符，求子串的操作。该操作主要是SubStr（）函数的实现。输入主字符串“thisisacprogram”,从位置5开始取长度为3的字符串，输出结果为“isa”，程序运行完毕，进入功能选择。 图四4. 进入功能4，求子串在主串s中的起始位置t;该过程主要实现Index（）的用法。这里采用的是BrutForce算法，虽然浪费了不少内存空间，但也能实现其功能，输入主串