《第四章 串——数据结构基本实验算法.docx》由会员分享，可在线阅读，更多相关《第四章 串——数据结构基本实验算法.docx（18页珍藏版）》请在三一文库上搜索。
1、实验 1 实现顺序串各种基本运算的算法#include#define MaxSize 100 /最多的字符个数typedef struct char dataMaxSize;/定义可以容纳MaxSize个字符的空间int length; /标记当前实际串长SqString;void StrAssign(SqString &str,char cstr)/由串常量cstr创建strint i;for(i=0;cstri!=0;i+)str.datai=cstri;str.length=i;void StrCopy(SqString &s,SqString t)/将串t复制到串sint i;for(
2、i=0;it.length;i+)s.datai=t.datai;s.length=t.length;int StrEqual(SqString s,SqString t)/判断两个串s和t是否相同int same=1,i;if(s.length!=t.length) /长度不相等时返回same=0;elsefor(i=0;is.length;i+)if(s.datai!=t.datai)/有一个对应字符不相同时返回same=0;return same;int StrLength(SqString s) /求串s的长度return s.length;SqString Concat(SqStri
3、ng s,SqString t)/将串t连接到串s之后产生新串SqString str;int i;str.length=s.length+t.length;for(i=0;is.length;i+) /将s.data0.s.length-1复制到strstr.datai=s.datai;for(i=0;it.length;i+) /将t.data0.t.length-1复制到strstr.datas.length+i=t.datai;return str;SqString SubStr(SqString s,int i,int j)/由串s的第i个字符开始的的j个字符产生新串SqString
4、 str;int k;str.length=0;if(is.length|js.length)printf(参数不正确n);return str; /参数不正确，返回空串for(k=i-1;ki+j-1;k+) /将s.datai.i+j复制到strstr.datak-i+1=s.datak;str.length=j;return str;SqString InsStr(SqString s1,int i,SqString s2)/将串s2插入到串s1的第i个位置处int j;SqString str;str.length=0;if(is1.length+1)/参数不正确时返回空串printf
5、(参数不正确n);return s1;for(j=0;ji-1;j+) /将s1.data0.i-2复制到strstr.dataj=s1.dataj;for(j=0;js2.length;j+)/将s2.data0.s2.length-1复制到strstr.datai+j-1=s2.dataj;for(j=i-1;js1.length;j+)/将s1.datai-1.s1.length-1复制到strstr.datas2.length+j=s1.dataj;str.length=s1.length+s2.length;return str;SqString DelStr(SqString s,
6、int i,int j)/删除串s的第i个字符开始的j个字符产生新串int k;SqString str;str.length=0;if(is.length|i+js.length+1)/参数不正确时返回空串printf(参数不正确n);return str;for(k=0;ki-1;k+) /将s.data0.i-2复制到strstr.datak=s.datak;for(k=i+j-1;ks.length;k+)/将s.datai+j-1.s.length-1str.datak-j=s.datak;str.length=s.length-j;return str;SqString RepSt
7、r(SqString s,int i,int j, SqString t)/将串s的第i个字符开始的j个字符替换成串t产生新串int k;SqString str;str.length=0;if(is.length|i+j-1s.length)/参数不正确时返回空串printf(参数不正确n);return str;for(k=0;ki-1;k+) /将s.data0.i-2复制到strstr.datak=s.datak;for(k=0;kt.length;k+)str.datai+k-1=t.datak;for(k=i+j-1;k0)for(i=0;is.length;i+)printf(%
8、c,s.datai);printf(n);/主程序void main()SqString s,s1,s2,s3,s4;printf(1)建立串s和串s1n);StrAssign(s,abcdefghijklmn);StrAssign(s1,xyz);printf(2)输出串s:);DispStr(s);printf(3)串s的长度:%dn,StrLength(s);printf(4)在串的第九个字符位置插入串s1而产生串s2n);s2=InsStr(s,9,s1);printf(5)输出串s2:);DispStr(s2);printf(6)删除串s第二个字符开始的个字符而产生串s2n);s2=
9、DelStr(s,2,3);printf(7)输出串s2：);DispStr(s2);printf(8)将串s第二个字符开始的个字符替换成串s1而产生串s2n);s2=RepStr(s,2,5,s1);printf(9)输出串s2：);DispStr(s2);printf(10)提取串s的第二个字符开始的个字符而产生串s3n);s3=SubStr(s,2,10);printf(11)输出串s3：);DispStr(s3);printf(12)将串s1和串s2连接起来而产生串s4n);s4=Concat(s1,s2);printf(13)输出串s4:);DispStr(s4);/ 实验 2 实现
10、链串各种基本运算的算法#include#includetypedef struct snodechar data;struct snode *next;LiString;void StrAssign(LiString *&s,char t)int i;LiString *r,*p;s=(LiString *)malloc(sizeof(LiString);s-next=NULL;r=s;for(i=0;ti!=0;i+)p=(LiString *)malloc(sizeof(LiString);p-data=ti;p-next=NULL;r-next=p;r=p;void StrCopy(Li
11、String *&s,LiString *t)LiString *p=t-next,*q,*r;s=(LiString *)malloc(sizeof(LiString);s-next=NULL;r=s;while(p!=NULL) /将t的所有节点复制到sq=(LiString *)malloc(sizeof(LiString);q-data=p-data;q-next=NULL;r-next=q;r=q;p=p-next;int StrEqual(LiString *s,LiString *t)LiString *p=s-next,*q=t-next;while(p!=NULL&q!=NU
12、LL&p-data=q-data)p=p-next;q=q-next;if(p=NULL&q=NULL)return 1;elsereturn 0;int StrLength(LiString *s)int i=0;LiString *p=s-next;while(p!=NULL)i+;p=p-next;return i;LiString *Concat(LiString *s,LiString *t)LiString *str,*p=s-next,*q ,*r;str=(LiString *)malloc(sizeof(LiString);str-next=NULL;r=str;while(
13、p!=NULL)/将s的所有节点复制到strq=(LiString *)malloc(sizeof(LiString);q-data=p-data;q-next=NULL;r-next=q;r=q;p=p-next;p=t-next;while(p!=NULL)/将t的所有节点复制到strq=(LiString *)malloc(sizeof(LiString);q-data=p-data;q-next=NULL;r-next=q;r=q;p=p-next;return str;LiString *SubStr(LiString *s,int i,int j)int k;LiString *s
14、tr,*p=s-next,*q,*r;str=(LiString *)malloc(sizeof(LiString);str-next=NULL;r=str;if(iStrLength(s)|jStrLength(s)printf(参数不正确n);return str; /参数不正确是返回空串for(k=0;knext;for(k=1;kdata=p-data;q-next=NULL;r-next=q;r=q;p=p-next;return str;LiString *InsStr(LiString *s,int i,LiString *t)int k;LiString *str,*p=s-n
15、ext,*p1=t-next,*q,*r;str=(LiString *)malloc(sizeof(LiString);str-next=NULL;r=str;if(iStrLength(s)+1)printf(参数不正确n);return str;for(k=1;kdata=p-data;q-next=NULL;r-next=q;r=q;p=p-next;while(p1!=NULL) /将t的所有节点复制到strq=(LiString *)malloc(sizeof (LiString);q-data=p1-data;q-next=NULL;r-next=q;r=q;p1=p1-next
16、;while(p!=NULL)/将*p及其后的节点复制到strq=(LiString *)malloc(sizeof(LiString);q-data=p-data;q-next=NULL;r-next=q;r=q;p=p-next;return str;LiString *DelStr(LiString *s,int i,int j)int k;LiString *str,*p=s-next,*q,*r;str=(LiString *)malloc(sizeof(LiString);str-next=NULL;r=str;if(iStrLength(s)|jStrLength(s)print
17、f(参数不正确n);return str;for(k=0;kdata=p-data;q-next=NULL;r-next=q;r=q;p=p-next;for(k=0;knext;while(p!=NULL)/将*p及其后的节点复制到strq=(LiString *)malloc(sizeof(LiString);q-data=p-data;q-next=NULL;r-next=q;r=q;p=p-next;return str;LiString *RepStr(LiString *s,int i,int j,LiString *t)int k;LiString *str,*p=s-next,
18、*p1=t-next,*q,*r;str=(LiString *)malloc(sizeof(LiString);str-next=NULL;r=str;if(iStrLength(s)|jStrLength(s)printf(参数不正确n);return str;for(k=0;kdata=p-data;q-next=NULL;r-next=q;r=q;p=p-next;for(k=0;knext;while(p1!=NULL)/将t的所有节点复制到strq=(LiString *)malloc(sizeof(LiString);q-data=p1-data;q-next=NULL;r-ne
19、xt=q;r=q;p1=p1-next;while(p!=NULL)/将*p及其后的节点复制到strq=(LiString *)malloc(sizeof(LiString);q-data=p-data;q-next=NULL;r-next=q;r=q;p=p-next;return str;void DispStr(LiString *s)LiString *p=s-next;while(p!=NULL)printf(%c,p-data);p=p-next;printf(n);/主程序void main()LiString *s,*s1,*s2,*s3,*s4;printf(1)建立串s和串
20、s1n);StrAssign(s,abcdefghijklmn);StrAssign(s1,xyz);printf(2)输出串s：);DispStr(s);printf(3)串s的长度:%dn,StrLength(s);printf(4)在串s的第九个字符位置插入串s1而产生串s2n);s2=InsStr(s,9,s1);printf(5)输出串s2：);DispStr(s2);printf(6)删除串s第二个字符开始的五个字符而产生串s2n);s2=DelStr(s,2,3);printf(7)输出串s2:);DispStr(s2);printf(8)将串s第二个字符开始的五个字符替换成串s
21、1而产生串s2n);s2=RepStr(s,2,5,s1);printf(9)输出串s2:);DispStr(s2);printf(10)提取串s的第二个字符开始的十个字符而产生串s3n);s3=SubStr(s,2,10);printf(11)输出串s3:);DispStr(s3);printf(12)将串s1和串s2连接起来而产生串s4n);s4=Concat(s1,s2);printf(13)输出串s4:);DispStr(s4);/实验 3 顺序串的各种模式匹配运算编写一个程序，实现顺序串的各种模式匹配运算，并在此基础上完成如下功能：（1） 建立“abcabcdabcdeabcdefa
22、bcdefg”目标串s和“abcdeabcdefab”模式串t。（2） 采用简单匹配算法求t在s中的位置。（3） 由模式串t求出next值和nextval值。（4） 采用KMP算法求出t在s中的位置。（5） 采用改进的KMP算法求出t在s中的位置。#include#include#define MaxSize 100typedef struct char dataMaxSize;/定义可容纳MaxSize个字符空间int length; /标记当前实际串长SqString;void StrAssign(SqString &str,char cstr)int i;for(i=0;cstri!=0
23、;i+)str.datai=cstri;str.length=i;void DispStr(SqString s)int i;if(s.length0)for(i=0;is.length;i+)printf(%c,s.datai);printf(n);int Index(SqString s,SqString t)/简单匹配算法int i=0,j=0,k;while(is.length&j=t.length)k=i-t.length; /返回匹配的第一个字符的下标elsek=-1; /模式匹配不成功return k;void GetNext(SqString t,int next)/由模式串t
24、求出next值int j,k;j=0;k=-1;next0=-1;while(jt.length-1)if(k=-1|t.dataj=t.datak)j+;k+;nextj=k;elsek=nextk;void GetNextval(SqString t,int nextval)/由模式串t求出nextval值int j=0,k=-1;nextval0=-1;while(jt.length)if(k=-1|t.dataj=t.datak)j+;k+;if(t.dataj!=t.datak)nextvalj=k;elsenextvalj=nextvalk;elsek=nextvalk;int K
25、MPIndex(SqString s,SqString t)/KMP算法int nextMaxSize,i=0,j=0,v;GetNext(t,next);while(is.length&j=t.length)v=i-t.length; /返回匹配模式串的首字符下标elsev=-1; /返回不匹配标志return v;int KMPIndex1(SqString s,SqString t) /改进的KMP算法int nextvalMaxSize,nextMaxSize,i=0,j=0,v;GetNextval(t,next);GetNextval(t,nextval);while(is.len
26、gth&j=t.length)v=i-t.length;/返回匹配模式串的首字符下标elsev=-1;return v;/主程序void main()int j;int nextMaxSize,nextvalMaxSize;SqString s,t;StrAssign(s,abcabcdabcdeabcdefabcdefg);StrAssign(t,abcdeabcdefab);printf(串s:);DispStr(s);printf(串t:);DispStr(t);printf(简单匹配P算法:n);printf( t 在s中的位置=%dn,Index(s,t);GetNext(t,nex
27、t);GetNextval(t,nextval);printf( j );for(j=0;jt.length;j+)printf(%4d,j);printf(n);printf( tj );for(j=0;jt.length;j+)printf(%4c,t.dataj);printf(n);printf( next );for(j=0;jt.length;j+)printf(%4d,nextj);printf(n);printf(nextval);for(j=0;jt.length;j+)printf(%4d,nextvalj);printf(n);printf(KMP算法:n);printf
28、( t在s中的位置=%dn,KMPIndex(s,t);printf( 改进的KMP算法:n);printf( t在s中的位置=%dn,KMPIndex1(s,t);/实验 4 文本串加密和解密程序 一个文本串可用事先给定的字母映射表进行加密。例如，设字母映射表为：abcdefghijklmnopqrstuvwxyzngzqtcobmuhelkpdawxfyivrsj则字符串“encrypt”被加密为“tkzwsdf”。试写一个算法将输入的文本串进行加密后输出；另写一个算法将输入的已加密的文本串进行解密后输出。#include#include#define MaxSize 100typedef
29、 struct char dataMaxSize;int length; /串长SqString;void StrAssign(SqString &str,char cstr)int i;for(i=0;cstri!=0;i+)str.datai=cstri;str.length=i;void DispStr(SqString s)int i;if(s.length0)for(i=0;is.length;i+)printf(%c,s.datai);printf(n);SqString A,B;/全局串SqString EnCrypt(SqString p)/加密过程int i=0,j;SqSt
30、ring q;while(i=p.length) /在A串中未找到p.datai字母q.datai=p.datai;elseq.datai=B.dataj;/在A串中找到p.datai字母i+;q.length=p.length;return q;SqString UnEncrypt(SqString q) /解密过程int i=0,j;SqString p;while(i=q.length) /在B串中未找到q.datai字母p.datai=q.datai;elsep.datai=A.dataj;/在B串中找到q.datai字母i+;p.length=q.length;return p;vo
31、id main()SqString p,q;int ok=1;StrAssign(A,abcdefghijklmnopqrstuvwxyz);/建立A串StrAssign(B,ngzqtcobmuhelkpdawxfyivrsj);/建立B串char strMaxSize;printf(n);printf(输入原文串:);gets(str); /获取用户输入的原文串StrAssign(p,str);/建立p串printf(加密解密如下:n);printf( 原文串:);DispStr(p);q=EnCrypt(p); /p串加密产生q串printf( 加密串:);DispStr(q);p=Un
32、Encrypt(q);/q串解密产生p串printf( 解密串:);DispStr(p);printf(n);/实验 5 求一个串中出现的第一个最长重复子串 采用顺序结构存储串，编写一个程序，求串s中出现的第一个最长重复子串的下标和长度。#include#include#include#define MaxSize 100typedef struct char dataMaxSize;int length;/串长SqString;void StrAssign(SqString &str,char cstr)int i;for(i=0;cstri!=0;i+)str.datai=cstri;st
33、r.length=i;void DispStr(SqString s)int i;if(s.length0)for(i=0;is.length;i+)printf(%c,s.datai);printf(n);SqString *MaxSubstr(SqString s)SqString *sp;int index=0,length=0,length1,i=0,j,k;while(is.length)j=i+1;while(jlength) /较大长度者赋给index与lengthindex=i;length=length1;j+=length1;elsej+;i+; /继续扫描第i个字符之后的字符sp=(SqString *)malloc(sizeof(SqString);sp-length=length;for(i=0;idatai=s.dataindex+i;return sp;void main()char strMaxSize;SqString s,*sp;printf(输入串:);gets(str);StrAssign(s,str); /创建串ssp=MaxSubstr(s);printf(求最长重复子串:n);printf( 原串: ); DispStr(s