數(shù)據(jù)結(jié)構(gòu)串實(shí)驗(yàn)報(bào)告

1、實(shí)驗(yàn)報(bào)告課程數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)名稱實(shí)驗(yàn)三 串學(xué)號(hào)姓名實(shí)驗(yàn)日期：實(shí)驗(yàn)三 串實(shí)驗(yàn)?zāi)康模?. 熟悉串類型的實(shí)現(xiàn)方法，了解簡(jiǎn)單文字處理的設(shè)計(jì)方法；2. 熟悉C語(yǔ)言的字符和把字符串處理的原理和方法；3. 熟悉并掌握模式匹配算法。實(shí)驗(yàn)原理：順序存儲(chǔ)結(jié)構(gòu)下的關(guān)于字符串操作的基本算法。模式匹配算法BF、KMP實(shí)驗(yàn)內(nèi)容： 4-19. 在節(jié)例4-6的基礎(chǔ)上，編寫比較Brute-Force算法和KMP算法比較次數(shù)的程序。 4-20. 設(shè)串采用靜態(tài)數(shù)組存儲(chǔ)結(jié)構(gòu)，編寫函數(shù)實(shí)現(xiàn)串的替換Replace（S，start，T，V），即要求在主串S中，從位置start開始查找是否存在字串T。若主串S中存在子串T，則用子串V替換子串T，

2、且函數(shù)返回1；若主串S中不存在子串T，則函數(shù)返回0；并要求設(shè)計(jì)主函數(shù)進(jìn)行測(cè)試。一個(gè)測(cè)試?yán)訛椋篠=“I am a student”,T=“student”,V=“teacher”。程序代碼：4-19的代碼：/*靜態(tài)存儲(chǔ)結(jié)構(gòu)*/typedef struct char strMaxSize; int length;String;/*初始化操作*/void Initiate(String *S) S->length=0;/*插入子串操作 */int Insert(String *S, int pos, String T)/*在串S的pos位置插入子串T*/ int i; if(pos<0

3、|pos>S->length) printf("The parameter pos is error!n"); return 0; else if(S->length+T.length>MaxSize) printf("The space of the array is not enough!n"); return 0; else for(i=S->length-1; i>=pos; i-) S->stri+T.length=S->stri; /*依次后移數(shù)據(jù)元素*/ for(i=0; i<T.len

4、gth; i+) S->strpos+i=T.stri; /*插入*/ S->length=S->length+T.length; /*產(chǎn)生新的串長(zhǎng)度值*/ return 1; /*刪除子串操作 */int Delete(String *S, int pos, int len)/*刪除串S的從pos位置開始長(zhǎng)度為len的子串值*/ int i; if(S->length<=0) printf("No elements deleting!n"); return 0; else if(pos<0|len<0|pos+len>S-&

5、gt;length) printf("The parameters pos and len are not correct!n"); return 0; else for(i=pos+len; i<=S->length-1; i+) S->stri-len=S->stri; /*依次前移數(shù)據(jù)元素*/ S->length=S->length-len; /*產(chǎn)生新的串長(zhǎng)度值*/ return 1; /*取子串操作 */int SubString(String S, int pos, int len, String *T)/*取串S的從pos位

6、置開始長(zhǎng)度為len的子串值賦給子串T*/ int i; if(pos<0|len<0|pos+len>S.length) printf("The parameters pos and len are not correct!n"); return 0; else for(i=0; i<=len; i+) T->stri=S.strpos+i; /*給子串T賦值*/ T->length=len; /*給子串T的長(zhǎng)度域賦值*/ return 1; /*查找子串BF(Brute-Force)操作*/int BFIndex(String S, i

7、nt start, String T)/*查找主串S從start開始的子串T，找到返回T在S中的開始字符下標(biāo)，否則返回-1*/ int i= start, j=0, v; while(i<S.length && j<T.length) if(S.stri=T.strj) i+; j+; else i=i-j+1; j=0; if(j=T.length) v=i-T.length; else v=-1; return v;/*查找子串KMP(D.E.Knuth-J.H.Morris-V.R.Pratt)操作 */int KMPIndex(String S, int s

8、tart, String T, int next)/*查找主串S從start開始的子串T，找到返回T在S中的首字符下標(biāo)，*/*否則返回-1*/*數(shù)組Next中存放有模式串T的nextj值*/ int i= start, j=0, v; while(i<S.length && j<T.length) if(S.stri=T.strj) i+; j+; else if(j=0) i+; else j=nextj; if(j=T.length) v=i-T.length; else v=-1; return v;/*求模式串nextj值的操作 */void GetNext

9、(String T, int next)/*求子串T的nextj值并存放于數(shù)組next中*/ int j=1, k=0; next0=-1; next1=0; while(j<T.length) if(T.strj=T.strk) nextj+1=k+1; j+; k+; else if(k=0) nextj+1=0; j+; else k=nextk; /*查找子串BF(Brute-Force)算法累計(jì)次數(shù) */int BFIndexC(String S, int start, String T)/*查找主串S從start開始的子串T，找到返回T在S中的開始字符下標(biāo)，否則返回-1*/

10、int i= start, j=0, t=0; while(i<S.length && j<T.length) if(S.stri=T.strj) i+; j+; else i=i-j+1; j=0; t+; return t;/*查找子串KMP(D.E.Knuth-J.H.Morris-V.R.Pratt)操作 */int KMPIndexC(String S, int start, String T, int next)/*查找主串S從start開始的子串T，找到返回T在S中的首字符下標(biāo)，*/*否則返回-1*/*數(shù)組Next中存放有模式串T的nextj值*/ i

11、nt i= start, j=0, t=0; while(i<S.length && j<T.length) if(S.stri=T.strj) i+; j+; else if(j=0) i+; else j=nextj; t+; return t;測(cè)試主函數(shù)：#include<stdio.h>#define MaxSize 100#include"SString.h"#include"BFandKMP.h"void main(void) String S="cddcdc",6, T="

12、;abcde",5; String S1="aaaaaaaa",8, T1="aaaab",5; String S2="aaaaaaaaaaaaaaaaad",18, T2="aaaab",5; int next20, count; count=BFIndexC(S,0,T); printf("從S中查找T的Brute-Force算法比較次數(shù)：%dn",count); GetNext(T, next); count=KMPIndexC(S,0,T,next); printf("

13、;從S中查找T的KMP算法比較次數(shù)：%dn",count); count=BFIndexC(S1,0,T1); printf("從S1中查找T1的Brute-Force算法比較次數(shù)：%dn",count); GetNext(T1, next); count=KMPIndexC(S1,0,T1,next); printf("從S1中查找T1的KMP算法比較次數(shù)：%dn",count); count=BFIndexC(S2,0,T2); printf("從S2中查找T2的Brute-Force算法比較次數(shù)：%dn",count)

14、; GetNext(T2, next); count=KMPIndexC(S2,0,T2,next); printf("從S2中查找T2的KMP算法比較次數(shù)：%dn",count); 4-20的部分代碼： Replace函數(shù)：/* 從主串S中查找字串T，若存在，并用串V替換串T并返回1，否則，返回0*/ int Replace(String S,int start,String T,String V) int i,v; Initiate(&S); Initiate(&T); Initiate(&V); for(i=0; i<strlen(S.s

15、tr); i+) S.length=S.length+1; for(i=0; i<strlen(T.str); i+) T.length=T.length+1; for(i=0; i<strlen(V.str); i+) V.length=V.length+1; i=BFIndex(S, 0, T); if (i!=-1) if(Delete(&S, i, T.length) Insert(&S, i, V); for(i=0; i<S.length; i+) printf("%c", S.stri); printf("n"); return v=1; else printf("主串S中不存在串Tn");return v=0; 測(cè)試主函數(shù)：#define MaxSize 80#include<stdio.h>#include<string.h>#include "SString.h"int main(void) int v; String S="I am a student.", T="student"