C語(yǔ)言算法查找字符串在文中出現(xiàn)的次數(shù)

1、目錄一. 問(wèn)題描述1二基本要求 1三數(shù)據(jù)結(jié)構(gòu) 1三數(shù)據(jù)結(jié)構(gòu)四.1算 法c 設(shè) 計(jì)思 想及流程1圖五源程序六-5測(cè)試情況參8考文獻(xiàn)8/求next值算法查找函數(shù)II 最大串長(zhǎng) 串的定長(zhǎng)順序存儲(chǔ)表示一.問(wèn)題描述建立一個(gè)文本文件，每個(gè)單詞不包含空格且不跨行，單詞由字符序列構(gòu)成且 區(qū)分大小寫。統(tǒng)計(jì)給定單詞在文本文件中出現(xiàn)的總次數(shù)； 檢索輸出某個(gè)單詞出現(xiàn) 在文本中的行號(hào)、在該行中出現(xiàn)的位置。二. 基本要求1. 建立一個(gè)文本文件2. 輸入一個(gè)不含空格的單詞，統(tǒng)計(jì)輸出在文本中出現(xiàn)的次數(shù)3. 輸入一個(gè)，檢索并輸出在文本中出現(xiàn)的行號(hào)和該行中的相應(yīng)位置三. 數(shù)據(jù)結(jié)構(gòu)1 .子函數(shù)設(shè)計(jì)：(1) . void get_n

2、ext(SStri ng T,i nt n ext)(2) . i nt In dex(SStri ng S,SStri ng T,i nt pos) KMP(3) . void fin d(char name,SStri ng keys) /2. 主函數(shù)調(diào)用設(shè)計(jì)：int mai n() / 主函數(shù)3. 結(jié)構(gòu)設(shè)計(jì):#define MAXSTRLEN 255typedef char SStri ngMAXSTRLEN+1;IIint n extMAXSTRLEN四.算法設(shè)計(jì)思想及流程圖/KMP算法中用到的next主函數(shù)設(shè)計(jì):int main()char name50; /存儲(chǔ)輸入的小說(shuō)路徑字符串

3、SStri ng words10; /定義字符串?dāng)?shù)組，用于存儲(chǔ)輸入的關(guān)鍵字int n,i;prin tf(Please in put the n ame of the no vel:n);sca nf(%s, name);B-WWWWaVa.VWVV.B-WWMWWVVWWWfaWW.-nWWWWprin tf(How many words do you want to fin d?( n10)n);sca nf(%d,&n);prin tf(Please in put the words you want to fin d:n);for (i=0;i n ;i+)scanf(%s，&word

4、si1);/用戶一次性輸入要查找的關(guān)鍵字，wordsi0用于存放字符串的長(zhǎng)度f(wàn)or (i=0;i n ;i+)find(name,wordsi); /對(duì)于每一個(gè)關(guān)鍵字，調(diào)用查找函數(shù)進(jìn)行查找統(tǒng)計(jì)子函數(shù)設(shè)計(jì):/求next值void get_next(SStri ng T,i nt next) / int j=1,k=0;next1=0;while(jT0)if(k=0|Tk=Tj)+j;+k;if(Tj!=Tk) n extj=k;else n extj=n extk;else k=n extk;求next值/KMP算法int In dex(SStri ng S,SStri ng T,i nt p

5、os) /KMP算法int i=pos,j=1;while(iT0) return (i-T0); elsereturn 0;/求串長(zhǎng)int len th(SStri ng str) /求串長(zhǎng)int i=1;while(stri) i+;return(i-1);/查找函數(shù)void find(char name,SString keys) / 對(duì)于輸入的每一個(gè)/要查找的關(guān) 鍵字，從小說(shuō)文件中逐行讀取字符串查找SStri ng text; /存放從小說(shuō)文件讀取的一行字符串int i=1,j=0,k; /i用于存放行號(hào)，j用于存放列號(hào),k用于輸出格式的控制FILE *fp;if (!(fp=(fop

6、e n(n ame,r) /打開(kāi)小說(shuō)文件prin tf(Ope n file error!n);exit(0);keys0=le nth(keys); get_ next(keys ,n ext); 的n ext值 prin tf(%sn,&keys1); while (!feof(fp) / /求關(guān)鍵字的長(zhǎng)度/求模式串(關(guān)鍵字)每一個(gè)字符對(duì)應(yīng)/打印關(guān)鍵字如果還沒(méi)到小說(shuō)文件末尾k=0;fgets(&text1,MAXSTRLEN,fp);/從小說(shuō)文件中讀取一行字符串，存入text串中textO=le nth(text);/求讀入的串的長(zhǎng)度j=ln dex(text,keys,j+1); /的位

7、置，若匹配不成功則返回調(diào)用KMP算法，統(tǒng)計(jì)關(guān)鍵字在該行出現(xiàn)0if (j!=0) num+ ；/次數(shù)加 1printf(第4次出現(xiàn)在第 %d行第%d列n,num,i,j); k+; /若匹配成功則打印次數(shù)、行號(hào)和列號(hào)while(j!=0) /若該行找到了關(guān)鍵字，則繼續(xù)尋找看是否還能匹配成功j=ln dex(text,keys,j+1);/調(diào)用KMP算法從剛找到的列號(hào)后一字符起匹配if (j!=0) num+;/次數(shù)加 1printf(第(:次出現(xiàn)在第d行第4列n,num,i,j); /若匹配成功,則打印次數(shù)、行號(hào)、列號(hào)i+; / 行號(hào)加1，在下一行中尋找if (k) pri ntf(n); /輸

8、出格式控制 算法流程圖：KMF串匹配示意圖:第一趟嚴(yán)期！ = b囚L不變j滑動(dòng)到勺第二趟第三趟a =F1o ab cat) uac b胡b =1.迪 af fj=o J=4 嚴(yán)岐= b何L不爽J滑動(dòng)到EHr10a = ababcabcacbabR,SrI B I a I J s. . J . 1 J 1Tto十藐加11j=LJr5/*j犬于b壬串的怪度匹配應(yīng)劭.函數(shù)返回嚴(yán)圖4.5無(wú)回溯宦法匹配過(guò)程五.源程序#i nclude #i nclude #defi ne MAXSTRLEN 255/最大串長(zhǎng)串的定長(zhǎng)順序存儲(chǔ)表示 算法中用到的next求next值typedef char SStri ng

9、MAXSTRLEN+1; / int n extMAXSTRLEN;KMPvoid get_next(SStri ng T,i nt next) / _int j=1,k=O;next1=0;while(jT0)if(k=0|Tk=Tj)+j;+k;if(Tj!=Tk) n extj=k;else n extj=n extk;else k=n extk;int In dex(SStri ng S,SStri ng T,i nt pos) KMP算法int i=pos,j=1;while(iT0) return (i-T0);elsereturn 0;int len th(SStri ng st

10、r) /求串長(zhǎng)int i=1;while(stri) i+;return(i-1);查找函數(shù)，該函數(shù)是整個(gè)程序的重要void fin d(char n ame,SStri ng keys) /部分，對(duì)于輸入的每一個(gè)/要查找的關(guān)鍵字，從小說(shuō)文件中逐行讀取字符串查找SStri ng text; /存放從小說(shuō)文件讀取的一行字符串int i=1,j=O,k,num=0; /i用于存放行號(hào)，j用于存放列號(hào),k用于輸出格式的控制FILE *fp;if (!(fp=(fope n(n ame,r) /打開(kāi)小說(shuō)文件prin tf(Ope n file error!n);exit(0);keys0=le nth

11、(keys); / get_ next(keys ,n ext);/值_prin tf(%sn,&keys1);/求關(guān)鍵字的長(zhǎng)度求模式串(關(guān)鍵字)每一個(gè)字符對(duì)應(yīng)的打印關(guān)鍵字如果還沒(méi)到小說(shuō)文件末尾nextk=0;fgets(&text1,MAXSTRLEN,fp);/入text串中text0=le nth(text);/j=I ndex(text,keys,j+1); / 的位置，若匹配不成功則返回 0從小說(shuō)文件中讀取一行字符串，存求讀入的串的長(zhǎng)度調(diào)用KMP算法，統(tǒng)計(jì)關(guān)鍵字在該行出現(xiàn)while (!feof(fp) /if (j!=0)nu m+;printf(第d次出現(xiàn)在第 d行第%dn,nu

12、m,i,j);k+; /若匹配成功則打印行號(hào)和列號(hào)while(j!=0) /若該行找到了關(guān)鍵字，則繼續(xù)尋找看是否還能匹配成功j=Index(text,keys,j+1);/調(diào)用KMP算法從剛找到的列號(hào)后一字符起匹配if (j!=0)nu m+;printf(第4次出現(xiàn)在第d行第%dn,num,i,j); / 若匹配成功，則打印列號(hào)i+; / 行號(hào)加1，在下一行中尋找if (k) pri ntf(n); /輸出格式控制int main()char name50; /存儲(chǔ)輸入的小說(shuō)路徑字符串SStri ng words10; /定義字符串?dāng)?shù)組，用于存儲(chǔ)輸入的關(guān)鍵字int n,i;prin tf(P

13、lease in put the n ame of the no vel:n);sca nf(%s, name);prin tf(How many words do you want to find?(n 10 )n ”)；sca nf(%d,&n);prin tf(Please in put the words you want to fin d:n);for (i=0;i n ;i+)scanf(%s，&wordsi1);/用戶一次性輸入要查找的關(guān)鍵字，wordsi0用于存放字符串的長(zhǎng)度f(wàn)or (i=0;i n ;i+)find(n ame,wordsi); /對(duì)于每一個(gè)關(guān)鍵字，調(diào)用查找函數(shù)進(jìn)行查找統(tǒng)計(jì)六.測(cè)試情況Please input the name of the nciuel：123.txtHow naiiy words dowant to f i