数据结构(00002

1、 数据结构串的应用 南京信息工程大学数据结构实验（实习）报告 串的应用 实验（实习）日期 2015-11-2 得分 顾韵华指导教师 实验（实习）名称 2 班次年级计软院 专业 计科 2014级系 实验目的一、 1、掌握串的用法。 实验内容二、 。以堆分配法表示串个字符()1、设计一个算法，删去串s中从第i个字符开始的连续j 中出现的字符。x中第一个不在y2、若x和y是两个以堆分配法表示的串，请设计一个算法，找出 一个文本串可用事先给定的字母映射表进行加密。例如，设字母映射表为：abcdefghijungzbqtcomtkqlmrnospfhealxkwpduvwzxyijvrsy 则字符串en

2、crypt被加密为tkzwsdf。 (1) 写一算法将输入的文本串进行加密后输出； (2) 写一算法，将输入的已加密文本串进行解密后输出。 4、实现朴素的模式匹配算法。 三、 /设计一个算法，删去串s中从第i个字符开始的连续j个字符(以堆分配法表示串)。 #include #include #include #define OK 1 #define ERROR 0 typedef int Status; typedef struct /堆分配法表示串的类型定义 char *ch; /存储区基址 int length; /串长 HString; Status strAssign(HString

3、&S,char *chars) /生成一个其值等于串常量chars的串S int i,j; char *c; if (S.ch) free(S.ch); for (i=0,c=chars;*c!=0;i+,c+); /求串chars的长度,存于i if (!i) /chars为空串 S.ch=NULL; S.length=0; else if (!(S.ch=(char *) malloc(i*sizeof(char) return ERROR; for(j=0;jS.length | i1) return ERROR; for (k=i+j-1,m=i-1;kS.length;k+,m+)

4、S.chm=S.chk; S.chm+1=0; S.length=S.length-j; return OK; void printString(HString S) int i; for (i=0;iS.length;i+) printf(%c,S.chi); printf(); /* run this program using the console pauser or add your own getch, system(pause) or input loop */ int main() HString S; char str=This is a test string!; ?牰湩晴

5、尨创建字符串S!n); if (strAssign(S,str)=ERROR) ?牰湩晴尨创建的字符串S失败！n); return 1; 牰湩晴尨创建的字符串S为：); printString(S); ?牰湩晴尨删除字符串S从3开始的4个字符：n); strDelete(S,3,4); ?牰湩晴尨删除字符后的字符串S为：n); printString(S); return 0; 2、/若x和y是两个以堆分配法表示的串，请设计一个算法，找出x中第一个不在y中出现的字符 #include #include #include #include #define OK 1 #define ERROR 0

6、 #define OVERFLOW -1 typedef int Status; typedef struct /堆分配法表示串的类型定义 char *ch; /存储区基址 int length; /串长 HString; Status strAssign(HString &S,char *chars) T 的串chars生成一个其值等于串常量 / int i,j; char *c; if (S.ch) free(S.ch); for (i=0,c=chars;*c;i+,c+); /求串chars的长度,存于i if (!i) /ars为空串 S.ch=NULL; S.length=0; e

7、lse if (!(S.ch=(char *) malloc(i*sizeof(char) exit(OVERFLOW); for(j=0;ji;j+) S.chj=charsj; S.length=i; return OK; void strSearch(HString &S1,HString &S2) int i,j; for(i=0;iS1.length;i+) int m=0; for(j=0;jS2.length;j+) if(S1.chi=S2.chj) break; else m+; if(m=S2.length) goto l; l: printf(%cn,S1.chi); i

8、nt main() HString S1,S2; char str1100,str2100; 牰湩晴尨输入串X:); gets(str1); 牰湩晴尨输入串Y:); gets(str2); S1.ch=NULL;S2.ch=NULL; strAssign(S1,str1);strAssign(S2,str2); strSearch(S1,S2); return 0; 3、/一个文本串可用事先给定的字母映射表进行加密 #include #include #include #define OK 1/定义常量 #define ERROR 0 typedef int Status; typedef s

9、truct /堆分配法表示串的类型定义 char *ch; /存储区基址 int length; /串长 HString; Status StrLength(HString s)/求串长 return s.length; Status strAssign(HString &S,char *chars) S 的串chars生成一个其值等于串常量/ int i,j; char *c; /if (S.ch) free(S.ch); for (i=0,c=chars;*c!=0;i+,c+); /求串chars的长度,存于i 为空串 if (!i) /chars S.ch=NULL; S.length

10、=0; else if (!(S.ch=(char *) malloc(i*sizeof(char) return ERROR; for(j=0;ji;j+) S.chj=charsj; S.length=i; return OK; 将输入的字符串加密后输出void strencrypt(HString &s)/ int i=0; int n; n=StrLength(s); while(i=n) switch(s.chi) case a:s.chi=n;break; case b:s.chi=g;break; case c:s.chi=z;break; case d:s.chi=q;brea

11、k; case e:s.chi=t;break; case f:s.chi=c;break; case g:s.chi=o;break; case h:s.chi=b;break; case i:s.chi=m;break; case j:s.chi=u;break; case k:s.chi=h;break; case l:s.chi=e;break; case m:s.chi=l;break; case n:s.chi=k;break; case o:s.chi=p;break; case p:s.chi=d;break; case q:s.chi=a;break; case r:s.ch

12、i=w;break; case s:s.chi=x;break; case t:s.chi=f;break; case u:s.chi=y;break; case v:s.chi=i;break; case w:s.chi=v;break; case x:s.chi=r;break; case y:s.chi=s;break; case z:s.chi=j;break; i+; for(i=0;i=n;i+) printf(%c,s.chi); printf(); void instrencrypt(HString &s)/将输入的字符串解密后输出 int i=0; int n; n=StrL

13、ength(s); while(i=n) switch(s.chi) case n:s.chi=a;break; case g:s.chi=b;break; case z:s.chi=c;break; case q:s.chi=d;break; case t:s.chi=e;break; case c:s.chi=f;break; case o:s.chi=g;break; case b:s.chi=h;break; case m:s.chi=i;break; case u:s.chi=j;break; case h:s.chi=k;break; case e:s.chi=l;break; c

14、ase l:s.chi=m;break; case k:s.chi=n;break; case p:s.chi=o;break; case d:s.chi=p;break; case a:s.chi=q;break; case w:s.chi=r;break; case x:s.chi=s;break; case f:s.chi=t;break; case y:s.chi=u;break; case i:s.chi=v;break; case v:s.chi=w;break; case r:s.chi=x;break; case s:s.chi=y;break; case j:s.chi=z;

15、break; i+; for(i=0;i=n;i+) printf(%c,s.chi); printf(); int main() HString s,t; char str1100; char str2100; 牰湩晴尨请输入未加密的字符串：); gets(str1); strAssign(s,str1); 牰湩晴尨加密后的字符串为:); strencrypt(s); 牰湩晴尨请输入加密的字符串:); gets(str2); strAssign(t,str2); 牰湩晴尨解密后的字符串为:); instrencrypt(t); return 0; 4、朴素模式的匹配 #include /朴素

16、的模式匹配 #include #include #include #define OK 1 #define ERROR 0 typedef int Status; typedef unsigned char HString100; Status strAssign(HString &S,char *chars) /生成一个其值等于串常量chars的串S int i,j; char *c; for (i=0,c=chars;*c!=0;+i,+c); /求串chars的长度,存于i 为空串 if (!i) /charsS0=0; else for(j=0;ji;j+) Sj+1=charsj;

17、S0=i; return OK; Status Index(HString S,HString T,int pos)/返回子串T在主串S中第Pos个字符之后的位置 int i=pos,j=1; while(i=S0&jT0) return i-T0; else return 0; int main() HString s,t; char str1100,str2100; int n,k; 牰湩晴尨请输入主串：); gets(str1); 牰湩晴尨请输入子串：); gets(str2); 牰湩晴尨请输入位置：); scanf(%d,&n); strAssign(s,str1); strAssign(t,str2); k=Index(s,t,n); printf(%dn,k); return 0; 四、程序调试 、操作结果：1 是两个以堆