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

数据结构串的基本操作及应用实验报告（常用版）(可以直接使用，可编辑 完整版资料，欢迎下载）实验日期 2021.5.10 教师签字 成绩 实 验 报 告【实验名称】 第四章串的基本操作及应用 【实验目的】1、熟悉将算法转换成程序代码的过程。2、了解串的逻辑结构特性，熟练掌握串顺序存储结构的C 语言描述方法。3、熟练掌握串的基本操作：求长度、串的连接、插入、删除等，掌握串的存取特性。【实验原理】1. 串可以可以有三种存储方式，分别为顺序存储、堆分配存储、链式存储，串的基本操作在这三种存储方式下操作。2. 串的模式匹配KMP算法在每一趟匹配过程中出现字符不等时，不需回溯指针，而是利用已经得到的部分匹配结果的结果将模式向右滑动尽可能远的一段距离，继续进行比较。【实验内容】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.length;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;elsefor(int j=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;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.length=0;elseint i=len;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;docout选择您要进行的串的基本操作: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.ch);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);Concat(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=StrCompare(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. 串的堆分配存储表示及基本操作（插入、删除、求串长、合并连接串、求子串、串比较等）#include#include#include#includestruct HStringchar *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 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.ch=NULL;t.length=0;elset.ch=(char *)malloc(i*sizeof(char);for(int j=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 *)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;elseint 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;docout1.插入endl2.删除endl3.串连结endl4.取子串endl5.串比较endl6.求串长endl7.结束i;switch(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);coutpos;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;int 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=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#includestruct HStringchar *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;elset.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.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.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语言函数的陌生导致问题变的繁琐，自己的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个人坐成一圈玩杀人游戏，按顺时针编号 1 2 3 N。从1号开始顺时针开始数到第m号就杀掉第一个人，被杀掉的人要退出游戏。 如果数到了编号的末尾，接着数开头的编号。 重复，直至杀掉一半人时，游戏结束，聪明的你能告诉我活到最后的幸存者最初的编号是多少吗？ 输入数据：N、M ；输出数据：幸存者的编号 分析该程序，如果N=20，M=2，10。聪明的你应选择的编号是多少，（提示，计算出M分别等于1到10的情况下，那些编号生存概率较大）。给出实验结果6、作业抽查问题：有35个学生的班级，由于某种原因不能够做到全部检查作业，现在希望每次抽查10名学生，希望能够随机抽查，并能够有记忆，即希望抽查过的学生，下次抽查的概率有所减小，但避免不被抽查。设计一个算法实现该功能，给出你的解释。1. void BingSet(SqList A, SqList B,SqList &C)/求并集int i,j;int flag=0;C.length=0;for(i=0;iA.length;i+)C.elemi=A.elemi;for(j=0;jB.length;j+)flag=LocateElem_Sq(A, B.elemj);if(flag=0)C.elemi=B.elemj;i+;C.length=i;void JiaoSet(SqList A, SqList B,SqList &C)/求交集int i,j;int flag=0;C.length=0;i=0;for(j=0;jB.length;j+)flag=LocateElem_Sq(A, B.elemj);if(flag!=0)C.elemi=B.elemj;i+;C.length=i;void ChaSet(SqList A, SqList B,SqList &C)/求差集int i,j,k;int flag=0;C.length=0;k=0;for(i=0;iA.length;i+)flag=LocateElem_Sq(B,A.elemi);if(flag=0)C.elemk=A.elemi;k+;C.length=k;运行结果：2. void BingSet(SqList A, SqList B,SqList &C)/求并集int i,j,k;k=0;C.length=0;for(i=0,j=0;(iA.length)&(jB.length);)if(A.elemiB.elemj)C.elemk=A.elemi;k+;i+;elseif(A.elemi=B.elemj)C.elemk=A.elemi;k+;i+;j+;elseC.elemk=B.elemj;k+;j+;if(iA.length)for(;iA.length;i+)C.elemk=A.elemi;k+;i+;if(jB.length)for(;jB.length;j+)C.elemk=B.elemj;k+;j+;C.length=k;void JiaoSet(SqList A, SqList B,SqList &C)/求交集int i,j,k;k=0;C.length=0;for(i=0,j=0;(iA.length)&(jB.length);)if(A.elemiB.elemj)i+;elseif(A.elemi=B.elemj)C.elemk=A.elemi;k+;i+;j+;elsej+;C.length=k;void ChaSet(SqList A, SqList B,SqList &C)/求差集 int i,j,k;int flag=0;k=0;C.length=0;for(i=0,j=0;(iA.length)&(jB.length);)if(A.elemiB.elemj)C.elemk=A.elemi;i+;k+;elseif(A.elemi=B.elemj)i+;j+;elsej+;if(iA.length)for(;iA.length;i+)C.elemk=A.elemi;k+;i+;C.length=k;void InserOrder_Sq(SqList &L,ElemType e)int i,j;for(i=0;i=e)break;for(j=L.length-1;j=i;j-)L.elemj+1=L.elemj;L.elemi=e;L.length+;运行结果：3. void bing(link &p,link &h,link &q) /求并集link l,s,m;int j=0,i=0;q=new LNode;q-date=NULL;q-next=NULL;s=p-next;m=q;while(s)l=new LNode;l-date=s-date;l-next=NULL;s=s-next;m-next=l;m=l; s=h-next;while (s)i=s-date;j=Locate(p,i);if(j=0)l=new LNode;l-date=s-date;l-next=NULL;m-next=l;m=l;s=s-next;void jiao(link &p,link &h,link &q) /求交集link l,s,t,m;int j=0;Elem i=0;q=new LNode;q-date=NULL;q-next=NULL;m=q;s=h-next;while (s)i=s-date;j=Locate(p,i);if(j=1)l=new LNode;l-date=s-date;l-next=NULL;m-next=l;m=l;s=s-next;void cha(link &p,link &h,link &q) /求差集link l,s,t,m;int j=0;Elem i=0;q=new LNode;q-date=NULL;q-next=NULL;m=q;s=p-next;while (s)i=s-date;j=Locate(h,i);if(j=0)l=new LNode;l-date=s-date;l-next=NULL;m-next=l; m=l;s=s-next;void shengcheng(link &p,link &h,link &q) int i,j=0;Elem e;for(i=0;idate=NULL;p-next=NULL;h=p;q=p;i+;elsee=rand()%50+1;j=Locate(p,e);if(j=0)LInsert(p,e);i+;运行结果：4. void bing(link &p,link &h,link &q) /并集link l,s,m;int j=0,i=0;q=new LNode;q-date=NULL;q-next=NULL;s=p-next;m=q;while(s)l=new LNode;l-date=s-date;l-next=NULL;s=s-next;m-next=l;m=l;s=h-next;while (s)i=s-date;j=Locate(p,i);if(j=0)LInsert(q,i);s=s-next;void jiao(link &p,link &h,link &q) /交集link l,s,t,m;int j=0;Elem i=0;q=new LNode;q-date=NULL;q-next=NULL;m=q;s=h-next;while (s)i=s-date;j=Locate(p,i);if(j=1)l=new LNode;l-date=s-date;l-next=NULL;m-next=l;m=l;s=s-next;void cha(link &p,link &h,link &q) /差集link l,s,t,m;int j=0;Elem i=0;q=new LNode;q-date=NULL;q-next=NULL;m=q;s=p-next;while (s)i=s-date;j=Locate(h,i);if(j=0)l=new LNode;l-date=s-date;l-next=NULL;m-next=l;