实验总结报告-串和数组

实验总结报告—栈和队列学号：姓名：时间：目的做实验的目的2.撰写实验报告的目的内容说明实验次数及实验内容本次实验用一个实验课时完成。实验内容：1.编写函数StrAssign(),StrCopy(),StrLenth(),StrCompare(),StrConcat(),Substring(),Replace(),完成串赋值,串复制,求串长度,串比较,串连接,求字串,子串替代等相应功能。注:Replace()依赖Find_KMP()2.使用KMP算法,编写函数Find_KMP(char*S,char*P,intstart)实现字符串匹配。测试数据:2.1charS[]=“abcabcabcd”;charP[]=“abcabcd”;2.2charS[]=“abcdababcabcdabcabcabcd”;charP[]=“abcabcd”;2.3charS[]=“cocaocoaoc”;charP[]=“coaoc”;要求:1.打印出模式串P的next[]模式数组;2.完成Find_KMP()后在Repalce()中调用,将P替换成“AAA”。注意2.2有2个地方要替换。3.创建三元组实现以下稀疏矩阵的存储,并利用三元组实现稀疏矩阵的转置,比较“按需查找”方法与“按位就座”方法的区别。01290000000000030000140002400000180000015007000建议实现流程为1.矩阵2.三元组3.转置的三元组4.转置的矩阵,将3或4打印出来。做实验完成情况实验内容在实验课时时间内完成（提前编写了大概1/2部分的代码），选做内容也完成。本次实验内容较多，为使代码看着简洁有条理，采用了建工程的方式。串部分：自定义了头文件String.h:/*自定义头文件*/#include<stdio.h>#defineMAX_LEN255typedefunsignedcharSString[MAX_LEN+1];/*自定义函数*/voidStrAssign(SString&T,chars[]);//将字符串常量s赋给TvoidStrPrint(SStringT);//打印串voidStrCopy(SString&T,SStringS);//串复制voidtest();//检验串操作intStrLength(SStringT);//求串长intStrCompare(SStringT,SStringS);//比较串，T>S返回正值，T<S返回负值，相等返回0voidStrConcat(SString&T,SStringS1,SStringS2);//用T返回SString类型串S1、S2连接成的新串voidSubString(SString&S,SStringT,intpos,intlen);//用S返回串T中起始位置为pos，长度为len的字串voidIndex(SStringS,SStringT,intpos[]);//若S串中存在不重叠的子串T，则用pos[]返回所有T串的起始位置voidStrReplace(SString&S,SStringT,SStringV);//若串S中存在字串T，则用V替代所有不重叠的TvoidStrInsert(SString&S,intpos,SStringT);//在串S中pos位置插入子串TvoidStrDelete(SString&S,intpos,intlen);//在串S中pos位置删除长度为len的子串voidGetNext(SStringS,intnext[]);//求模式串中的next函数修正值并写入数组next[]intFindKMP(SStringS,SStringT,intstart);//在串S中从start位置开始，查找第一次出现模式T的位置返回，没找到返回-1voidStrReplace2(SString&S,SStringT,SStringV);//若串S中存在字串T，则用V替代所有不重叠的TvoidKMP();//KMP算法及其应用在头文件中对所有要用到的自定义函数进行了声明，各函数的功能可见代码注释部分。串赋值：#include"String.h"voidStrAssign(SString&T,chars[]){ if(!s){ printf("Error\n"); return; } inti=0; while(s[i]!='\0'){ T[i]=s[i]; i++; } T[i]='\0';}该操作将字符串常量s中的元素赋值给SString类型T；串复制：#include"String.h"voidStrCopy(SString&T,SStringS){ if(!S){ printf("原串为空串\n"); return; } inti=0; while(S[i]!='\0'){ T[i]=S[i]; i++; } T[i]='\0';}该操作完成将SString类型T赋给SString类型S；求串长度：#include"String.h"intStrLength(SStringT){ inti=0; while(T[i]!='\0') i++; returni;}该操作返回SString类型中元素的个数即串的长度；串比较：#include"String.h"intStrCompare(SStringT,SStringS){ inti; for(i=0;T[i]!='\0'&&S[i]!='\0';i++) if(S[i]!=T[i]) returnT[i]-S[i]; returnT[i]-S[i];}串连接：#include"String.h"voidStrConcat(SString&T,SStringS1,SStringS2){ inti; if(!S1&&!S2){ printf("Error\n"); return; }//S1、S2均为空 if(!S1&&S2){ for(i=0;S2[i]!='\0';i++) T[i]=S2[i]; T[i]='\0'; return; }//S1为空 if(!S2&&S1){ for(i=0;S1[i]!='\0';i++) T[i]=S1[i]; T[i]='\0'; return; }//S2为空 for(i=0;i<=StrLength(S1);i++) T[i]=S1[i]; for(i=0;i<=StrLength(S2);i++) T[i+StrLength(S1)]=S2[i]; T[StrLength(S1)+StrLength(S2)+1]='\0';}此操作完成将串S1和S2连接之后赋给T；求子串：#include"String.h"voidSubString(SString&S,SStringT,intpos,intlen){ intTlen,i; Tlen=StrLength(T); if(pos+len>Tlen||pos<0||pos>Tlen-1||len<0){ printf("Error"); return; } for(i=0;i<len;i++) S[i]=T[i+pos]; S[i]='\0';}该操作求出T串的一个子串S；子串代替：参考BF算法：#include"String.h"voidStrReplace(SString&S,SStringT,SStringV){ intpos[20],i,Tlen; Tlen=StrLength(T); for(i=0;i<20;i++) pos[i]=1000; Index(S,T,pos); for(i=0;pos[i]!=1000;i++){ StrDelete(S,pos[i],Tlen); StrInsert(S,pos[i],V); }}此方法要用到Index()函数，此函数参考BF算法完成：#include"String.h"voidIndex(SStringS,SStringT,intpos[]){ inti,j=0,Slen,Tlen,flag=0,count=0; Slen=StrLength(S); Tlen=StrLength(T); for(i=0;i<=Slen;){ if(S[i]==T[j]){ flag++; if(flag==Tlen){ pos[count]=i-Tlen+1; count++; flag=0; j=0; i++; } else{ i++; j++; } } else{ flag=0; i++; j=0; } } if(count==0) printf("S中没有T串\n");}参考KMP算法：#include"String.h"voidStrReplace2(SString&S,SStringT,SStringV){ intstart,Tlen; Tlen=StrLength(T); while(FindKMP(S,T,0)!=-1){ start=FindKMP(S,T,0); StrDelete(S,start,Tlen); StrInsert(S,start,V); }}此方法利用了KMP算法，需要求next[]数组；KMP算法：#include"String.h"intFindKMP(SStringS,SStringT,intstart){ inti,j=0,next[20]; GetNext(T,next); if(start<0||start>StrLength(S)-StrLength(T)){ return-1; } i=start; while(i<StrLength(S)&&j<StrLength(T)){ if(j==-1||S[i]==T[j]){ i++; j++; } else j=next[j]; } if(j==StrLength(T)) returni-j; return-1;}KMP算法需要求next[]数组进行辅助；Next：#include"String.h"voidGetNext(SStringS,intnext[]){ intj=0,k=-1; next[0]=-1; while(j<StrLength(S)){ if(k==-1||S[j]==S[k]){ j++; k++; if(S[j]!=S[k]) next[j]=k; else next[j]=next[k]; } else k=next[k]; }}此操作获得模式串改进后的next[]数组；除此之外，我还用到了子串删除和子串插入的操作：#include"String.h"voidStrDelete(SString&S,intpos,intlen){ inti; if(pos>StrLength(S)-1||pos+len>StrLength(S)||len<0||pos<0){ printf("Error"); return; } for(i=pos;i<=StrLength(S)-len;i++) S[i]=S[i+len];}#include"String.h"voidStrInsert(SString&S,intpos,SStringT){ inti,Slen,Tlen; Slen=StrLength(S); Tlen=StrLength(T); for(i=Slen;i>=pos;i--) S[i+Tlen]=S[i]; for(i=0;i<Tlen;i++) S[pos+i]=T[i]; S[Slen+Tlen+1]='\0';}主函数中分别调用test()和KMP()用来实现对串操作的检验和对KMP算法的检验主函数：/*主函数*/#include"String.h"#include<stdlib.h>intmain(){ /*检验串操作的正确性*/ test(); /*KMP算法及其应用*/ KMP(); system("pause"); return0;}Test()：#include"String.h"voidtest(){ printf("=========================================\n"); printf("TestBegain:\n"); printf("\n"); chars[]="abcdefgh"; intlen,r,pos[20],i; SStringT,S,Q,P; SStringR="abcdkhaksabcdlkjflabcd"; SStringR2="abc"; SStringR3="xyz"; StrAssign(T,s); StrPrint(T); StrCopy(S,T); StrPrint(S); len=StrLength(S); printf("len=%d\n",len); r=StrCompare(R,T); printf("r=%d\n",r); StrConcat(Q,T,R); StrPrint(Q); SubString(P,Q,5,10); StrPrint(P); for(i=0;i<20;i++) pos[i]=1000; Index(R,R2,pos); for(i=0;pos[i]!=1000;i++) printf("pos[%d]=%d",i,pos[i]); printf("\n"); StrDelete(R,5,6); StrInsert(R,4,R2); StrReplace(R,R2,R3); StrPrint(R); printf("\n"); printf("TestEnd!\n"); printf("=========================================\n");}KMP()：#include"String.h"voidKMP(){ printf("KMPBegain:\n"); printf("\n"); SStringS1="abcabcabcd",S2="abcdababcabcdabcabcabcd",S3="cocaocoaoc"; SStringP1="abcabcd",P2="abcabcd",P3="coaoc"; SStringP="AAA"; intnext1[20],next2[20],next3[20],i,r1,r2,r3; GetNext(P1,next1); for(i=0;i<StrLength(P1);i++) printf("next1[%d]=%d\n",i,next1[i]); r1=FindKMP(S1,P1,0); printf("r1=%d\n",r1); StrReplace2(S1,P1,P); StrPrint(S1); printf("\n"); GetNext(P2,next2); for(i=0;i<StrLength(P2);i++) printf("next2[%d]=%d\n",i,next2[i]); r1=FindKMP(S2,P2,0); printf("r2=%d\n",r1); StrReplace2(S2,P2,P); StrPrint(S2); printf("\n"); GetNext(P3,next3); for(i=0;i<StrLength(P3);i++) printf("next3[%d]=%d\n",i,next3[i]); r1=FindKMP(S3,P3,0); printf("r3=%d\n",r1); StrReplace2(S3,P2,P); StrPrint(S3); printf("\n"); printf("KMPEnd!\n"); printf("=========================================\n");}实验结果：从实验结果来看，串的各个操作成功实现。数组部分：自定义了头文件Array.h：/*自定义头文件（数组）*/#include<stdio.h>#defineMAX_SIZE1000/*结构体*/typedefintElemType;typedefstruct{ inti,j; ElemTypee;}Triple;typedefstruct{ Tripledata[MAX_SIZE]; intmu,nu,tu;}TSMatrix;/*自定义函数*/voidCreateTSMatrix(TSMatrix&M,ElemTypem[][7],intr,intc);//创建三元组voidPrintTSMatrix(TSMatrixM);//打印三元组voidCreateRpos(TSMatrixM,intrpos[],intnum[]);//求矩阵的rops数组voidTRansposeTS(TSMatrixM,TSMatrix&T);//将三元组顺序表压缩存储的矩阵M转置为矩阵T在头文件中对所有要用到的自定义函数进行了声明，各函数的功能可见代码注释部分。创建三元组：#include"Array.h"voidCreateTSMatrix(TSMatrix&M,ElemTypem[][7],intr,intc){ M.mu=r; M.nu=c; M.tu=0; intk,l; for(k=0;k<r;k++){ for(l=0;l<c;l++){ if(m[k][l]!=0){ M.data[M.tu].e=m[k][l]; M.data[M.tu].i=k; M.data[M.tu].j=l; M.tu++; } } }}此操作将r*c的矩阵创建成三元组表示的矩阵TSMatrixM；转置三元组矩阵：#include"Array.h"#defineMAXM100voidTRansposeTS(TSMatrixM,TSMatrix&T){ intp,q,col; intnum[MAXM],rpos[MAXM]; T.mu=M.nu; T.nu=M.mu; T.tu=M.tu; if(!M.tu) return; CreateRpos(M,rpos,num); for(p=0;p<M.tu;p++){ col=M.data[p].j; q=rpos[col]; T.data[q].i=M.data[p].j; T.data[q].j=M.data[p].i; T.data[q].e=M.da