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

资源描述

数据结构串的基本操作及应用实验报告（常用版） (可以直接使用，可编辑完整版资料，欢迎下载）实验日期 2021.5.10 教师签字成绩实验报告【实验名称】第四章串的基本操作及应用【实验目的】 1、熟悉将算法转换成程序代码的过程。 2、了解串的逻辑结构特性，熟练掌握串顺序存储结构的C 语言描述方法。 3、熟练掌握串的基本操作：求长度、串的连接、插入、删除等，掌握串的存取特性。【实验原理】 1. 串可以可以有三种存储方式，分别为顺序存储、堆分配存储、链式存储，串的基本操作在这三种存储方式下操作。 2. 串的模式匹配KMP算法在每一趟匹配过程中出现字符不等时，不需回溯指针，而是利用已经得到的部分匹配结果的结果将模式向右滑动尽可能远的一段距离，继续进行比较。【实验内容】 1. 串的顺序存储表示及基本操作（插入、删除、求串长、合并连接串、求子串、串比较等） #include<stdio.h> #include<iostream.h> #include<malloc.h> #include<string.h> #define SIZE 20 struct HString {char ch[SIZE]; int length;}; void StrInsert(HString &s,int pos,HString t){ int i,j; if(pos<1||pos>s.length+1)cout<<"ERROR!"; if(t.length){ for(i=s.length-1;i>=pos-1;--i) s.ch[i+t.length]=s.ch[i]; for(j=0;j<=t.length-1;j++) s.ch[pos-1+j]=t.ch[j]; s.length+=t.length;} } void StrDelete(HString &s,int pos,int len){ int i;int v=pos-1; if(pos<1||pos>s.length||len<0||len>s.length-pos+1)cout<<"ERROR!"; for(i=pos+len-1;i<=s.length-1;i++) s.ch[v++]=s.ch[i]; 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;j<i;j++) t.ch[j]=chars[j]; t.length=i; } } int StrLen(HString &s) { return s.length; } int StrCompare(HString &s,HString t) { for(int i=0;i<s.length&&i<t.length;i++) { if(s.ch[i]!=t.ch[i]) return (int)(t.ch[i]-s.ch[i]); } return s.length-t.length; } void Concat(HString &t,HString s1,HString s2) { int i=s1.length+s2.length; for(i=0;i<s1.length;i++) t.ch[i]=s1.ch[i]; t.length=s1.length+s2.length; for(i=s1.length;i<t.length;i++) t.ch[i]=s2.ch[i-s1.length]; } int SubString(HString &sub,HString s,int pos,int len) { if(pos<1||pos>s.length||len<0||len>s.length-pos+1) { cout<<"ERROR!"<<endl; return 0; } if(!len) { sub.length=0; } else { int i=len; for(i=0;i<len;i++) sub.ch[i]=s.ch[pos+i-1]; sub.length=len; } } void Display(HString &t) { for(int i=0;i<=t.length-1;i++) cout<<t.ch[i]; cout<<endl; } void main() { int i; char s[20]; do { cout<<"选择您要进行的串的基本操作:"<<endl; cout<<"1.插入"<<endl<<"2.删除"<<endl<<"3.串连结"<<endl<<"4.取子串"<<endl<<"5.串比较"<<endl<<"6.求串长"<<endl<<"7.结束"<<endl; cin>>i; switch(i) { case 1: { HString s,t;int pos; cout<<"请输入串s:"; cin>>s.ch; StrAssign(s,s.ch); cout<<endl; cout<<"请输入要插入的串t:"; cin>>t.ch; StrAssign(t,t.ch); cout<<endl; cout<<"请输入你所要插入的位置:"; cin>>pos; StrInsert(s,pos,t); cout<<"插入之后串变为:"; Display(s); break; } case 2: { HString s;int pos,len; cout<<"请输入串s:"; cin>>s.ch; StrAssign(s,s.ch); cout<<"请输入你所要删除串的首位置为:"; cin>>pos; cout<<"请输入你需要删除的串的长度:"; cin>>len; StrDelete(s,pos,len); cout<<"删除之后串变为:"; Display(s); break; } case 3: { HString s1,s2,t; cout<<"请输入串s1:"; cin>>s1.ch; StrAssign(s1,s1.ch); cout<<"请输入串s2:"; cin>>s2.ch; StrAssign(s2,s2.ch); Concat(t,s1,s2); cout<<"s1与s2合并后的串为:"; Display(t); break; } case 4: { HString sub,s; int pos,len; cout<<"请输入主串s:"; cin>>s.ch; StrAssign(s,s.ch); cout<<"请输入所取原串的起始位置pos:"; cin>>pos; cout<<"请输入子串的长度len:"; cin>>len; SubString(sub,s,pos,len); cout<<"取出的子串为:"; Display(sub); break; } case 5: { HString s,t; int value; cout<<"请输入串s:"; cin>>s.ch; StrAssign(s,s.ch); cout<<"请输入串t:"; cin>>t.ch; StrAssign(t,t.ch); value=StrCompare(s,t); if(value>0) cout<<"串s大于串t"<<endl; else if(value==0) cout<<"串s等于串t"<<endl; else cout<<"串s小于串t"<<endl; cout<<endl; break; } case 6:HString s;char *chars;int val; cout<<"请输入串s:"; cin>>s.ch; StrAssign(s,s.ch); val=StrLen(s); cout<<"串的长度为:"<<val<<endl;break; case 7:cout<<"操作结束!"<<endl;break; default:cout<<"输入错误!请重新输入!"<<endl;break; } }while(i!=7); } 2. 串的堆分配存储表示及基本操作（插入、删除、求串长、合并连接串、求子串、串比较等） #include<stdio.h> #include<iostream.h> #include<malloc.h> #include<string.h> struct HString { char *ch; int length; }; void StrInsert(HString &s,int pos,HString t){ int i,j; if(pos<1||pos>s.length+1)cout<<"ERROR!"; if(t.length){ s.ch=(char*)realloc(s.ch,(s.length+t.length)*sizeof(char)); for(i=s.length-1;i>=pos-1;--i) s.ch[i+t.length]=s.ch[i]; for(j=0;j<=t.length-1;j++) s.ch[pos-1+j]=t.ch[j]; s.length+=t.length;} } void StrDelete(HString &s,int pos,int len){ int i;int v=pos-1; if(pos<1||pos>s.length||len<0||len>s.length-pos+1)cout<<"ERROR!"; for(i=pos+len-1;i<=s.length-1;i++) s.ch[v++]=s.ch[i]; 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=0;j<i;j++) t.ch[j]=chars[j]; t.length=i; } } int StrLen(HString &s) { return s.length; } int StrCompare(HString &s,HString t) { for(int i=0;i<s.length&&i<t.length;i++) { if(s.ch[i]!=t.ch[i]) return (int)(t.ch[i]-s.ch[i]); } 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;i<s1.length;i++) t.ch[i]=s1.ch[i]; t.length=s1.length+s2.length; for(i=s1.length;i<t.length;i++) t.ch[i]=s2.ch[i-s1.length]; } int SubString(HString &sub,HString s,int pos,int len) { if(pos<1||pos>s.length||len<0||len>s.length-pos+1) { cout<<"ERROR!"<<endl; return 0; } if(!len) { sub.ch=NULL; sub.length=0; } else { int i=len; sub.ch=(char *)malloc(i*sizeof(char)); for(i=0;i<len;i++) sub.ch[i]=s.ch[pos+i-1]; sub.length=len; } } void Display(HString &t) { for(int i=0;i<=t.length-1;i++) cout<<t.ch[i]; cout<<endl; } void main() { int i; char s[20]; cout<<"选择您要进行的串的基本操作:"<<endl; do { cout<<"1.插入"<<endl<<"2.删除"<<endl<<"3.串连结"<<endl<<"4.取子串"<<endl<<"5.串比较"<<endl<<"6.求串长"<<endl<<"7.结束"<<endl; cin>>i; switch(i) { case 1: { HString s,t;char a[20],b[20];char *sa,*sb;int pos; cout<<"请输入串s:"; cin>>a; sa=a; StrAssign(s,sa); cout<<endl; cout<<"请输入要插入的串t:"; cin>>b; sb=b; StrAssign(t,sb); cout<<endl; cout<<"请输入你所要插入的位置:"; cin>>pos; StrInsert(s,pos,t); cout<<"插入之后串变为:"; Display(s); break; } case 2: { HString s;char str[20];char *chars;int pos,len; cout<<"请输入串s:"; cin>>str; chars=str; StrAssign(s,chars); cout<<"请输入你所要删除串的首位置为:"; cin>>pos; cout<<endl; cout<<"请输入你需要删除的串的长度:"; cin>>len; cout<<endl; StrDelete(s,pos,len); cout<<"删除之后串变为:"; Display(s); break; } case 3: { HString s1,s2,t; char a[20],b[20]; char *sa,*sb; cout<<"请输入串s1:"; cin>>a; sa=a; StrAssign(s1,sa); cout<<"请输入串s2:"; cin>>b; sb=b; StrAssign(s2,sb); Concat(t,s1,s2); cout<<"s1与s2合并后:"; Display(t); break; } case 4: { HString sub,s; char a[20]; char *sa; int pos,len; cout<<"请输入主串s:"; cin>>a; sa=a; StrAssign(s,sa); cout<<"请输入所取原串的起始位置pos:"; cin>>pos; cout<<"请输入子串的长度len:"; cin>>len; SubString(sub,s,pos,len); cout<<"该子串为:"; Display(sub); break; } case 5: { HString s,t; int value; char a[20],b[20]; char *sa,*sb; cout<<"请输入串s:"; cin>>a; sa=a; StrAssign(s,sa); cout<<"请输入串t:"; cin>>b; sb=b; StrAssign(t,sb); value=StrCompare(s,t); if(value>0) cout<<"串s大于串t"<<endl; else if(value==0) cout<<"串s等于串t"<<endl; else cout<<"串s小于串t"<<endl; cout<<endl; break; } case 6:HString s;char str[20];char *chars;int val; cout<<"请输入串s:"; cin>>str; chars=str; StrAssign(s,chars); val=StrLen(s); cout<<"串的长度为:"<<val<<endl;break; case 7:cout<<"操作结束!"<<endl;break; default:cout<<"输入错误!请重新输入!"<<endl;break; } }while(i!=7); 3. KMP算法的C实现 #include<iostream.h> #include<malloc.h> #include<string.h> struct 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;j<i;j++) t.ch[j]=chars[j]; t.length=i; } } void get_next(HString s,int next[]) { int i,j; i=1;j=0; next[1]=0; while(i<s.length) { if(j==0||s.ch[i-1]==s.ch[j-1]) { i++;j++;next[i]=j; } else j=next[j]; } for(i=1;next[i]!='\0';i++) cout<<next[i]<<" "; } int Index(HString s,HString t,int pos) { int i=pos; int j=1; int next[20]; get_next(t,next); while(i<=s.length&&j<=t.length) { if(s.ch[i-1]==t.ch[j-1]||j==0) { ++i;++j;} else { j=next[j]; } } if(j>t.length) return i-t.length; else return 0; } void Display(HString t) { for(int i=0;i<t.length;i++) cout<<t.ch[i]; cout<<endl; } void main() { HString s,t; int pos,k; char a[20],b[20]; char *sa,*sb; cout<<"请输入主串s:"; cin>>a; sa=a; StrAssign(s,sa); cout<<"请输入模式串t:"; cin>>b; sb=b; StrAssign(t,sb); cout<<"请输入起始位置pos:"; cin>>pos; k=Index(s,t,pos); if(k==0) cout<<"匹配失败!"<<endl<<endl; else {cout<<"从第"<<k<<"个位置开始匹配"<<endl; Display(s); for(int i=1;i<k;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;i<A.length;i++) {C.elem[i]=A.elem[i]; } for(j=0;j<B.length;j++) {flag=LocateElem_Sq(A, B.elem[j]); if(flag==0) {C.elem[i]=B.elem[j];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;j<B.length;j++) {flag=LocateElem_Sq(A, B.elem[j]); if(flag!=0) {C.elem[i]=B.elem[j];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;i<A.length;i++) {flag=LocateElem_Sq(B,A.elem[i]); if(flag==0) {C.elem[k]=A.elem[i];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;(i<A.length)&&(j<B.length);) {if(A.elem[i]<B.elem[j]) {C.elem[k]=A.elem[i];k++;i++; } else {if(A.elem[i]==B.elem[j]) {C.elem[k]=A.elem[i];k++;i++;j++; } else {C.elem[k]=B.elem[j];k++;j++;} } } if(i<A.length) {for(;i<A.length;i++) {C.elem[k]=A.elem[i];k++;i++; } } if(j<B.length) {for(;j<B.length;j++) {C.elem[k]=B.elem[j];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;(i<A.length)&&(j<B.length);) {if(A.elem[i]<B.elem[j]) {i++;} else {if(A.elem[i]==B.elem[j]) {C.elem[k]=A.elem[i];k++;i++;j++; } else {j++;} } } 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;(i<A.length)&&(j<B.length);) {if(A.elem[i]<B.elem[j]) {C.elem[k]=A.elem[i];i++;k++; } else {if(A.elem[i]==B.elem[j]) {i++;j++;} else {j++; } } } if(i<A.length) {for(;i<A.length;i++) {C.elem[k]=A.elem[i];k++;i++;} } C.length=k; } void InserOrder_Sq(SqList &L,ElemType e) {int i,j; for(i=0;i<L.length;i++) {if(L.elem[i]>=e) break; } for(j=L.length-1;j>=i;j--) L.elem[j+1]=L.elem[j]; L.elem[i]=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;i<11;) {if(i==0) {p=new LNode; p->date=NULL; p->next=NULL; h=p;q=p;i++;} else {e=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;

展开阅读全文