数据结构串的基本操作及应用实验报告常用版.docx

1、数据结构串的基本操作及应用实验报告常用版实验日期 2021.5.10 教师签字 成绩 实 验 报 告【实验名称】 第四章串的基本操作及应用 【实验目的】1、熟悉将算法转换成程序代码的过程。2、了解串的逻辑结构特性，熟练掌握串顺序存储结构的C 语言描述方法。3、熟练掌握串的基本操作：求长度、串的连接、插入、删除等，掌握串的存取特性。【实验原理】1.串可以可以有三种存储方式，分别为顺序存储、堆分配存储、链式存储，串的基本操作在这三种存储方式下操作。2.串的模式匹配KMP算法在每一趟匹配过程中出现字符不等时，不需回溯指针，而是利用已经得到的部分匹配结果的结果将模式向右滑动尽可能远的一段距离，继续进行

2、比较。【实验内容】1.串的顺序存储表示及基本操作（插入、删除、求串长、合并连接串、求子串、串比较等）#include#include#include#include#define SIZE 20struct HStringchar chSIZE; int length;void StrInsert(HString &s,int pos,HString t) int i,j; if(poss.length+1)cout=pos-1;-i) s.chi+t.length=s.chi; for(j=0;j=t.length-1;j+) s.chpos-1+j=t.chj; s.length+=t.l

3、ength;void StrDelete(HString &s,int pos,int len) int i;int v=pos-1; if(poss.length|lens.length-pos+1)coutERROR!; for(i=pos+len-1;i=s.length-1;i+) s.chv+=s.chi; s.length-=len;void StrAssign(HString &t,char chars) int i; char *c; for(i=0,c=chars;*c;+i,+c); if(!i) t.length=0; else for(int j=0;ji;j+) t.

4、chj=charsj; t.length=i; int StrLen(HString &s) return s.length;int StrCompare(HString &s,HString t) for(int i=0;is.length&it.length;i+) if(s.chi!=t.chi) return (int)(t.chi-s.chi); return s.length-t.length;void Concat(HString &t,HString s1,HString s2) int i=s1.length+s2.length; for(i=0;is1.length;i+)

5、 t.chi=s1.chi; t.length=s1.length+s2.length; for(i=s1.length;it.length;i+) t.chi=s2.chi-s1.length;int SubString(HString &sub,HString s,int pos,int len) if(poss.length|lens.length-pos+1) coutERROR!endl; return 0; if(!len) sub.length=0; else int i=len; for(i=0;ilen;i+) sub.chi=s.chpos+i-1; sub.length=

6、len; void Display(HString &t) for(int i=0;i=t.length-1;i+) coutt.chi; coutendl;void main() int i; char s20;do cout选择您要进行的串的基本操作:endl; cout1.插入endl2.删除endl3.串连结endl4.取子串endl5.串比较endl6.求串长endl7.结束i; switch(i) case 1: HString s,t;int pos; couts.ch; StrAssign(s,s.ch); coutendl; coutt.ch; StrAssign(t,t.c

7、h); coutendl; coutpos; StrInsert(s,pos,t); cout插入之后串变为:; Display(s); break; case 2: HString s;int pos,len; couts.ch; StrAssign(s,s.ch); coutpos; coutlen; StrDelete(s,pos,len); cout删除之后串变为:; Display(s); break; case 3: HString s1,s2,t; couts1.ch; StrAssign(s1,s1.ch); couts2.ch; StrAssign(s2,s2.ch); Co

8、ncat(t,s1,s2); couts1与s2合并后的串为:; Display(t); break; case 4: HString sub,s; int pos,len; couts.ch; StrAssign(s,s.ch); coutpos; coutlen; SubString(sub,s,pos,len); cout取出的子串为:; Display(sub); break; case 5: HString s,t; int value; couts.ch; StrAssign(s,s.ch); coutt.ch; StrAssign(t,t.ch); value=StrCompar

9、e(s,t); if(value0) cout串s大于串tendl; else if(value=0) cout串s等于串tendl; else cout串s小于串tendl; coutendl; break; case 6:HString s;char *chars;int val; couts.ch; StrAssign(s,s.ch); val=StrLen(s); cout串的长度为:valendl;break; case 7:cout操作结束!endl;break; default:cout输入错误!请重新输入!endl;break; while(i!=7);2.串的堆分配存储表示及

10、基本操作（插入、删除、求串长、合并连接串、求子串、串比较等）#include#include#include#includestruct HString char *ch; int length;void StrInsert(HString &s,int pos,HString t) int i,j; if(poss.length+1)cout=pos-1;-i) s.chi+t.length=s.chi; for(j=0;j=t.length-1;j+) s.chpos-1+j=t.chj; s.length+=t.length;void StrDelete(HString &s,int p

11、os,int len) int i;int v=pos-1; if(poss.length|lens.length-pos+1)coutERROR!; for(i=pos+len-1;i=s.length-1;i+) s.chv+=s.chi; s.length-=len;void StrAssign(HString &t,char *chars) int i; char *c; for(i=0,c=chars;*c;+i,+c); if(!i) t.ch=NULL; t.length=0; else t.ch=(char *)malloc(i*sizeof(char); for(int j=

12、0;ji;j+) t.chj=charsj; t.length=i; int StrLen(HString &s) return s.length;int StrCompare(HString &s,HString t) for(int i=0;is.length&it.length;i+) if(s.chi!=t.chi) return (int)(t.chi-s.chi); return s.length-t.length;void Concat(HString &t,HString s1,HString s2) int i=s1.length+s2.length; t.ch=(char

13、*)malloc(i*sizeof(char); for(i=0;is1.length;i+) t.chi=s1.chi; t.length=s1.length+s2.length; for(i=s1.length;it.length;i+) t.chi=s2.chi-s1.length;int SubString(HString &sub,HString s,int pos,int len) if(poss.length|lens.length-pos+1) coutERROR!endl; return 0; if(!len) sub.ch=NULL; sub.length=0; else

14、int i=len; sub.ch=(char *)malloc(i*sizeof(char); for(i=0;ilen;i+) sub.chi=s.chpos+i-1; sub.length=len; void Display(HString &t) for(int i=0;i=t.length-1;i+) coutt.chi; coutendl;void main() int i; char s20; cout选择您要进行的串的基本操作:endl;do cout1.插入endl2.删除endl3.串连结endl4.取子串endl5.串比较endl6.求串长endl7.结束i; switc

15、h(i) case 1: HString s,t;char a20,b20;char *sa,*sb;int pos; couta; sa=a; StrAssign(s,sa); coutendl; coutb; sb=b; StrAssign(t,sb); coutendl; coutpos; StrInsert(s,pos,t); cout插入之后串变为:; Display(s); break; case 2: HString s;char str20;char *chars;int pos,len; coutstr; chars=str; StrAssign(s,chars); cout

16、pos; coutendl; coutlen; coutendl; StrDelete(s,pos,len); cout删除之后串变为:; Display(s); break; case 3: HString s1,s2,t; char a20,b20; char *sa,*sb; couta; sa=a; StrAssign(s1,sa); coutb; sb=b; StrAssign(s2,sb); Concat(t,s1,s2); couts1与s2合并后:; Display(t); break; case 4: HString sub,s; char a20; char *sa; in

17、t pos,len; couta; sa=a; StrAssign(s,sa); coutpos; coutlen; SubString(sub,s,pos,len); cout该子串为:; Display(sub); break; case 5: HString s,t; int value; char a20,b20; char *sa,*sb; couta; sa=a; StrAssign(s,sa); coutb; sb=b; StrAssign(t,sb); value=StrCompare(s,t); if(value0) cout串s大于串tendl; else if(value

18、=0) cout串s等于串tendl; else cout串s小于串tendl; coutendl; break; case 6:HString s;char str20;char *chars;int val; coutstr; chars=str; StrAssign(s,chars); val=StrLen(s); cout串的长度为:valendl;break; case 7:cout操作结束!endl;break; default:cout输入错误!请重新输入!endl;break; while(i!=7);3.KMP算法的C实现#include#include#includestr

19、uct HString char *ch; int length;void StrAssign(HString &t,char *chars) int i; char *c; for(i=0,c=chars;*c;+i,+c); if(!i) t.ch=NULL; t.length=0; else t.ch=(char *)malloc(i*sizeof(char); for(int j=0;ji;j+) t.chj=charsj; t.length=i; void get_next(HString s,int next) int i,j; i=1;j=0; next1=0; while(is

20、.length) if(j=0|s.chi-1=s.chj-1) i+;j+;nexti=j; else j=nextj; for(i=1;nexti!=0;i+) coutnexti ;int Index(HString s,HString t,int pos) int i=pos; int j=1; int next20; get_next(t,next); while(i=s.length&jt.length) return i-t.length; else return 0;void Display(HString t) for(int i=0;it.length;i+) coutt.

21、chi; coutendl;void main() HString s,t; int pos,k; char a20,b20; char *sa,*sb; couta; sa=a; StrAssign(s,sa); coutb; sb=b; StrAssign(t,sb); coutpos; k=Index(s,t,pos); if(k=0) cout匹配失败!endlendl; else cout从第k个位置开始匹配endl; Display(s); for(int i=1;ik;i+) cout ; Display(t);【小结讨论】1. 此程序关键在于位置查询，由于对C语言函数的陌生导致

22、问题变的繁琐，自己的C语言水平有待提高。2.对于串不能想当然的用gets()输入puts()输出，这是不对的，对输入我们可以利用串赋值初始化串，输出则就利用一个普通的循环输出。3在定义函数时.一些需要加“&”使用引用的一定要加否则会导致程序运行错误。北京联合大学实训报告课程（项目）名称： 数据结构 学 院： 专 业：班 级： 学 号： 姓 名： 成 绩： 2012年6月21日数据结构实训任务一一、任务与目的： 1、用顺序表表示两个无序集合A、B，实现集合的如下操作，求两个集合的并集、交集、差集。2、 用顺序表表示两个集合A、B（集合A、B都是有序递增的情况）实现集合的如下操作，求两个集合的并集、交集、差集。3、用带头单链表存储结构表示两个无序集合A、B，实现集合的如下操作，求两个集合的并集、交集、差集。4、用带头单链表存储结构表示两个集合A、B（集合A、B都是有序递增的情况），实现集合的如下操作，求两个集合的并集、交集、差集。5、杀人游戏 N个人坐成一圈玩杀人游