數(shù)據(jù)結(jié)構(gòu)實驗報告-串

1、實驗四串【實驗?zāi)康摹?、掌握串的存儲表示及基本操作；2、掌握串的兩種模式匹配算法：BF和KMP。3、了解串的應(yīng)用?！緦嶒瀸W(xué)時】2學(xué)時【實驗預(yù)習(xí)】回答以下問題：1、串和子串的定義串的定義：串是由零個或多個任意字符組成的有限序列。子串的定義：串中任意連續(xù)字符組成的子序列稱為該串的子串。2、串的模式匹配串的模式匹配即子串定位是一種重要的串運算。設(shè)s和I是給定 的兩個串，從主串s的第start個字符開始查找等于子串t的過程稱 為模式匹配，如果在S中找到等于t的子串，則稱匹配成功，函數(shù)返 回t在s中首次出現(xiàn)的存儲位置（或序號）；否則，匹配失敗，返回 Oo【實驗內(nèi)容和要求】1、按照要求完成程序exp4.c

2、,實現(xiàn)串的相關(guān)操作。調(diào)試并運行如下測試數(shù)據(jù)給出運行結(jié)果： 求"This is a boy"的串長； 比較“ abc 3”和“abcde“； 表示空格 比較"english"和"student ”； 比較“ abc”和“abc ”； 截取串" white” ,起始2,長度2； 截取串" white”，起始1,長度7； 截取串" white” ,起始6,長度2； 連接串" asddffgh” 和 “ 12344” ；#include<stdio. h>#include<string. h&g

3、t;define MAXSIZE 100 define ERROR 0 define OK 1/*串的定長順序存儲表示*/typedef structchar dataMAXSIZE；int length； SqString；intstrlnit(SqString*s)；/*初始化串*/intstrCreate(SqString*s)；/*生成一個串*/intstrLength(SqString*s)；/*求串的長度*/int strCompare (SqString *sl,SqString *s2)；/*兩個串的比較*/int subString(SqString *sub, SqStri

4、ng *s, int pos, int len)；/*求子串*/int strConcat(SqString *t,SqString *sl,SqString *s2)；/*兩個串的連接*/*初始化串*/int strlnit (SqString *s)s->length=0；s->data0=，0'；return OK；/*strInit*/*生成一個串*/int strCreate (SqString *s)printf("input string ：")；gets(s->data)；s->length=strlen(s->data

5、)；return OK；/*strCreate*/* (1)-求串的長度*/int strLength(SqString *s)return s->length；/*strLength*/* (2)-兩個串的比較，S1S2返回>0, sl<s2返回<0, sl=s2返回0*/int strCompare(SqS tri ng *sl,SqString *s2)int i；for (i=0；i<sl->length&&i<s2->length；i+)(if (sl->datai>s2->datai)(return

6、1；1/1文檔可自由編輯if (sl->datai<s2->datai)return -1；return 0；/*strCompare*/* (3)求子串，sub為返回的子串，pos為子串的起始位置,len為子串的長度*/int subString(SqString *sub,SqString *s,int pos,int len) int i；if(pos<l |pos>s->length| len<0 |len>s->length-pos+l)(return ERROR；sub->length=0；for(i=0；i<len

7、；i+)(sub->datai=s->datai+pos-l；sub->length+；sub->datai=>Of；return OK；/"subString*/* (4)-兩個串連接，s2連接在si后，連接后的結(jié)果串放在t中*/int strConcat (SqString *t,SqString *sl,SqString *s2)int i=0,j=0；while(i<sl->length)(t->datai=sl->datai；i+;while(j<s2->length)(t->datai+=s2->

8、;dataj+；t->datai=，0'；t->length=sl->length+s2->length；return OK；/*strConcat*/int main()int n,k,pos,len；SqString s,t,x；do(printf ('AnStringn")；printf(n 1. strLentghn")；printf ('> 2. strComparenH)；printf (,F 3. subStringn")；printf (,F 4. strConcatn")；print

9、f(H 0. EXITn'r)；printf(vn Stringn")；printf(nninput choice：H)；scanf (,r%d" ,&n)；getchar ()；switch(n)case 1：printf (Mn*show strLength*n,F)；strCreate (&s)；printf(HstrLength is %dnn,strLength(&s)；i/i文檔可自由編輯break；case 2：printf(nn*show strCompare*nn)；strCreate (&s)；strCreate

10、(&t)；k=strCompare(&sf&t) ； /* (5)調(diào)用串比較函數(shù)比較s, I*/if(k=O)printf(ntwo string equal!nH)；else if(k<0)printf (nfirst string<second string! nn)；elseprintf (nfirst string>second string! nn)；break；case 3：printf(nn*show subString*nH)；strCreate (&s)；printf (Hinput substring pos, len：，r

11、)；scanf (H%d, %d,r, &pos, &1 en)；if(subStringpos,len)printf(substring is %snH,t. data)；elseprintf(Mpos or len ERROR!nn)；break；case 4：printf (f，n*show subConcat*nH)；strCreate (&s)；strCreate (&t)；if (strConcat(&x,&s,&t) /* (6)調(diào)用串連接 函數(shù)連接s&t*/printf (HConcat string is %sx

12、. data)； elseprintf ("Concat ERROR!n'*)；break；case 0：exit (0)；default：break；while (n)；return 0；2、按照要求完成程序exp4_2.c,實現(xiàn)BF&KMP串的模式匹配算 法。調(diào)試及測試數(shù)據(jù)并給出結(jié)果：應(yīng)用BF算法求子串“ JING”在主串“ BEIJING”中的位置，測 試起始位置分別為1和5的情況；應(yīng)用 KMP 算法求子串” abaabcac” 在主 串" acabaabaabcacaabc”中的位置，測試起始位置分別為1, 10的情況，并寫出子串的next值；exp

13、4_2. c部分代碼如下：#include<stdio. h>#include<string. h># define MAXSIZE 100# define ERROR 0# define OK 1/*串的定長順序存儲表示*/typedef structchar dataMAXSIZE；int length； SqString；int strCreate(SqString *s)；int indexBf (SqString *s,SqString *t, int pos) ；/*串的模式匹配BF*/void getNext(SqString *t,int next)；/

14、*KMP求next值*/int indexKmp(SqString *s,SqString *t,int start,int next)； /*串的模式匹配KMP*/*生成一個串*/int strCreate (SqString *s)(printf(Hinput string :")；gets (s->data)；slength=strlen(s->data)；return OK；/*strCreate*/* (1)一串的模式匹配BF*/int indexBf(SqString *stSqString *t,int pos) int i=pos-l,j=0；while

15、(i<s->length&&j<t->length)(if(s->datai=t->dataj)(i+;j+；1/1文檔可自由編輯 else (i=i-j+l；j=0；if(j>=t->length)(return i-t->length+l；else(return 0；/*index_bf*/* (2) - KMP 求 next 值*/void getNext(SqString *t,int next) (int i=0 J=-l；next 0=-l；while(i<t->length)if(j=T) I (t

16、->datai =t->dataj)j+；i+;nexti=j； else (j=nextj；/*getNext*/* (3) - KMP模式匹配*/int indexKmp(SqString *s,SqString *t,int start,int next )int i=start-l,j=0；while(i<s->length&&j<t->length) (if(j=-l |s->datai=t->dataj)i+;j+；else(產(chǎn)next j；)if(j>=t->length)(return i-t->

17、length+l；else(return 0；/*index_kmp*/int main()(int n,i,pos,nextMAXSIZE；SqString s,t； do1/1文檔可自由編輯printf(nn String n")；printf ('> 1. Index_BFn'r)；printfC1 2. INdex_KMPnu)；printfd 0. EXITn'r);printf ('rnStringn")；printf(Uninput choice：")；scanf ("%d",&n)；

18、getchar ()；switch(n)case 1：printf("n*show Index_BF*n")；printf(" s：")；strCreate (&s)；printf(" t：")；strCreate (&t)；printf(Hinput start position：H)；scanf Cr%d'* ,&pos)；printf C*BF：indexis %dnn,indexBf(&s,&t,pos)；break；case 2：printf("n*show Index_KMP*nn)；printf(" s：")；strCreate(&s)；printf(" t：")；strCreate(&t)；printf("input start position：")；scanf (，f%d'* ,