實(shí)驗(yàn)總結(jié)報告-串和數(shù)組

實(shí)驗(yàn)總結(jié)報告—棧和隊(duì)列學(xué)號：姓名：時間：目的做實(shí)驗(yàn)的目的2.撰寫實(shí)驗(yàn)報告的目的內(nèi)容說明實(shí)驗(yàn)次數(shù)及實(shí)驗(yàn)內(nèi)容本次實(shí)驗(yàn)用一個實(shí)驗(yàn)課時完成。實(shí)驗(yàn)內(nèi)容：1.編寫函數(shù)StrAssign(),StrCopy(),StrLenth(),StrCompare(),StrConcat(),Substring(),Replace(),完成串賦值,串復(fù)制,求串長度,串比較,串連接,求字串,子串替代等相應(yīng)功能。注:Replace()依賴Find_KMP()2.使用KMP算法,編寫函數(shù)Find_KMP(char*S,char*P,intstart)實(shí)現(xiàn)字符串匹配。測試數(shù)據(jù):2.1charS[]=“abcabcabcd”;charP[]=“abcabcd”;2.2charS[]=“abcdababcabcdabcabcabcd”;charP[]=“abcabcd”;2.3charS[]=“cocaocoaoc”;charP[]=“coaoc”;要求:1.打印出模式串P的next[]模式數(shù)組;2.完成Find_KMP()后在Repalce()中調(diào)用,將P替換成“AAA”。注意2.2有2個地方要替換。3.創(chuàng)建三元組實(shí)現(xiàn)以下稀疏矩陣的存儲,并利用三元組實(shí)現(xiàn)稀疏矩陣的轉(zhuǎn)置,比較“按需查找”方法與“按位就座”方法的區(qū)別。01290000000000030000140002400000180000015007000建議實(shí)現(xiàn)流程為1.矩陣2.三元組3.轉(zhuǎn)置的三元組4.轉(zhuǎn)置的矩陣,將3或4打印出來。做實(shí)驗(yàn)完成情況實(shí)驗(yàn)內(nèi)容在實(shí)驗(yàn)課時時間內(nèi)完成（提前編寫了大概1/2部分的代碼），選做內(nèi)容也完成。本次實(shí)驗(yàn)內(nèi)容較多，為使代碼看著簡潔有條理，采用了建工程的方式。串部分：自定義了頭文件String.h:/*自定義頭文件*/#include<stdio.h>#defineMAX_LEN255typedefunsignedcharSString[MAX_LEN+1];/*自定義函數(shù)*/voidStrAssign(SString&T,chars[]);//將字符串常量s賦給TvoidStrPrint(SStringT);//打印串voidStrCopy(SString&T,SStringS);//串復(fù)制voidtest();//檢驗(yàn)串操作intStrLength(SStringT);//求串長intStrCompare(SStringT,SStringS);//比較串，T>S返回正值，T<S返回負(fù)值，相等返回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函數(shù)修正值并寫入數(shù)組next[]intFindKMP(SStringS,SStringT,intstart);//在串S中從start位置開始，查找第一次出現(xiàn)模式T的位置返回，沒找到返回-1voidStrReplace2(SString&S,SStringT,SStringV);//若串S中存在字串T，則用V替代所有不重疊的TvoidKMP();//KMP算法及其應(yīng)用在頭文件中對所有要用到的自定義函數(shù)進(jìn)行了聲明，各函數(shù)的功能可見代碼注釋部分。串賦值：#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；串復(fù)制：#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類型中元素的個數(shù)即串的長度；串比較：#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()函數(shù)，此函數(shù)參考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[]數(shù)組；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[]數(shù)組進(jìn)行輔助；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]; }}此操作獲得模式串改進(jìn)后的next[]數(shù)組；除此之外，我還用到了子串刪除和子串插入的操作：#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';}主函數(shù)中分別調(diào)用test()和KMP()用來實(shí)現(xiàn)對串操作的檢驗(yàn)和對KMP算法的檢驗(yàn)主函數(shù)：/*主函數(shù)*/#include"String.h"#include<stdlib.h>intmain(){ /*檢驗(yàn)串操作的正確性*/ test(); /*KMP算法及其應(yīng)用*/ 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");}實(shí)驗(yàn)結(jié)果：從實(shí)驗(yàn)結(jié)果來看，串的各個操作成功實(shí)現(xiàn)。數(shù)組部分：自定義了頭文件Array.h：/*自定義頭文件（數(shù)組）*/#include<stdio.h>#defineMAX_SIZE1000/*結(jié)構(gòu)體*/typedefintElemType;typedefstruct{ inti,j; ElemTypee;}Triple;typedefstruct{ Tripledata[MAX_SIZE]; intmu,nu,tu;}TSMatrix;/*自定義函數(shù)*/voidCreateTSMatrix(TSMatrix&M,ElemTypem[][7],intr,intc);//創(chuàng)建三元組voidPrintTSMatrix(TSMatrixM);//打印三元組voidCreateRpos(TSMatrixM,intrpos[],intnum[]);//求矩陣的rops數(shù)組voidTRansposeTS(TSMatrixM,TSMatrix&T);//將三元組順序表壓縮存儲的矩陣M轉(zhuǎn)置為矩陣T在頭文件中對所有要用到的自定義函數(shù)進(jìn)行了聲明，各函數(shù)的功能可見代碼注釋部分。創(chuàng)建三元組：#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的矩陣創(chuàng)建成三元組表示的矩陣TSMatrixM；轉(zhuǎn)置三元組矩陣：#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