基于改進(jìn)KMP算法的字符文件子串查找

./數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告評(píng)分評(píng)分滿分——5分學(xué)號(hào)：2015111898姓名：許明華專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)知識(shí)范疇：字符串完成日期：2017年4月14日實(shí)驗(yàn)題目：基于改進(jìn)KMP算法的字符文件子串查找實(shí)驗(yàn)內(nèi)容及要求：從鍵盤輸入字符文件名以及子串,用改進(jìn)KMP算法在字符文件中實(shí)現(xiàn)子串查找。要求程序輸出子串的改進(jìn)nextval數(shù)組元素值以及子串在文件中成功匹配的次數(shù)〔查找失敗輸出成功匹配次數(shù)為0。實(shí)驗(yàn)?zāi)康模赫莆兆哟檎业腒MP算法。數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)簡(jiǎn)要描述：序言：這是本學(xué)期第四個(gè)實(shí)驗(yàn),本實(shí)驗(yàn)是要求我們將一個(gè)文件中的字符串讀取出來,并自己從鍵盤上輸入一個(gè)字符串來進(jìn)行匹配,并用kmp算法來進(jìn)行字符串的匹配查找；數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)單設(shè)計(jì)：本實(shí)驗(yàn)主要可分為三大模塊,第一,從文件中讀取出主串,并將其保存在一個(gè)字符數(shù)組中；第二,通過我們從鍵盤上輸入的字符串來獲得改進(jìn)的nextval數(shù)組,而在改進(jìn)的nextval數(shù)組求值算法中,變量還是跟蹤的是next數(shù)組的值；第三,利用kmp算法來進(jìn)行主串〔char*s和模式子串〔char*t的匹配,并求出成功匹配的次數(shù)；算法設(shè)計(jì)簡(jiǎn)要描述：1,求nextval數(shù)組的值,我們將不需要用到next數(shù)組就可以直接求出nextval數(shù)組的值,使nextval得出示值為-1,即nextval[0]=k=-1;將子串下標(biāo)j初始化為1,然后通過t[j]和t[k]的值變化來獲得nextval數(shù)組的值,其中的要點(diǎn)是,k值跟蹤的仍然是未改進(jìn)的next[j]的值；2,利用kmp算法來進(jìn)行主串和模式子串的匹配,定義一個(gè)記錄匹配的變量c=0,主串下標(biāo)為i=0,子串下標(biāo)j=0,當(dāng)主串和子串第一個(gè)元素匹配成功后,進(jìn)行i++和j++操作,都遍歷到下一個(gè)元素；當(dāng)進(jìn)行一次成功匹配時(shí),將子串的下標(biāo)回溯到初始位置,記錄變量c++,此時(shí)主串下標(biāo)已經(jīng)到達(dá)匹配成功的下一個(gè)元素,再繼續(xù)進(jìn)行匹配,知道主串到達(dá)末尾,結(jié)束匹配。輸入/輸出設(shè)計(jì)簡(jiǎn)要描述：1,輸入：輸入存儲(chǔ)主串的文件名,輸入子串；2,輸出：當(dāng)輸入文件名后,會(huì)打印輸出主串；當(dāng)輸入子串后,會(huì)打印輸出nextval數(shù)組的值以及匹配成功的次數(shù)值c。編程語言說明：編程軟件,CodeBlocks16.0；代碼均用C語言實(shí)現(xiàn)；輸入輸出采用C語言的printf和scanf函數(shù)；程序注釋采用C/C++規(guī)范；主要函數(shù)說明：voidwrite<char>;//讀取主串函數(shù)voidget_nextval<char,int>;//獲得nextval數(shù)組函數(shù)intindex_kmp<char,char,int>;//kmp算法函數(shù)voidprint_nextval<int,int>;//輸出nextval數(shù)組函數(shù)程序測(cè)試簡(jiǎn)要報(bào)告：見截圖：1,2,源程序代碼：#include<stdio.h>#include<stdlib.h>#include<string.h>intnextval[32]={-999};//定義一個(gè)nextval數(shù)組,并進(jìn)行初始化//函數(shù)聲明voidwrite<chars[]>;//讀取主串函數(shù)voidget_nextval<char,int>;//獲得nextval數(shù)組函數(shù)intindex_kmp<char,char,int>;//kmp算法函數(shù)voidprint_nextval<int,int>;//輸出nextval數(shù)組函數(shù)//從文件中將主串讀出來并保存在s[]數(shù)組中voidwrite<chars[256]>{charfilename[10];FILE*fp;printf<"請(qǐng)輸入文件名：\n">;scanf<"%s",filename>;if<<fp=fopen<filename,"r">>==NULL>{printf<"cannotopenthefile!\n">;exit<0>;}while<!feof<fp>>{fscanf<fp,"%s",s>;//將讀取的主串保存在s數(shù)組中}printf<"主串為：\n%s",s>;//將主串輸出到屏幕上fclose<fp>;}//求得nextval數(shù)組的值voidget_nextval<char*t,intnextval[]>{intj=1;intk=-1;nextval[0]=k;while<t[j]>if<<k==-1>||<t[j-1]==t[k]>>if<t[++k]==t[j]>nextval[j++]=nextval[k];elsenextval[j++]=k;elsek=nextval[k];}intindex_kmp<chars[],chart[],intnext[]>{intc=0;inti=0,j=0;while<1>{while<s[i]&&<j==-1||t[j]>>//當(dāng)主串s[i]不為空并且子串t[j]不為空if<<j==-1>||<s[i]==t[j]>>//如果主串的第一個(gè)元素和子串的第一個(gè)元素匹配上之后,主串和子串下標(biāo)均向后移一位{i++;//主串循環(huán)到下一個(gè)j++;//子串循環(huán)到下一個(gè)}elsej=nextval[j];if<!t[j]>//如果子串完成一次成功的匹配,{i=i-j+1;//每一次主串的下標(biāo)i回溯到初始位置的下一個(gè),這樣就能避免匹配漏掉；j=0;//就將子串下標(biāo)回溯到初始位置c++;//將記錄成功匹配的次數(shù)的值加1,還有,此時(shí)主串下標(biāo)已經(jīng)向前移動(dòng)一位,所以這里不需要再進(jìn)行i++}if<!s[i]>//如果主串到達(dá)末尾,說明遍歷完成,則退出循環(huán)break;}returnc;//返回成功匹配的次數(shù)}//輸出next或者nextval數(shù)組的值voidprint_nextval<intnextval[],intn>{for<inti=0;i<n;i++>{printf<"%d",nextval[i]>;}}//主函數(shù)調(diào)用intmain<>{intindex;//定義一個(gè)成功匹配的次數(shù)的值chars[256],t[256];//定義兩個(gè)字符串?dāng)?shù)組,來保存主串和子串write<s>;//將主串中的數(shù)據(jù)讀取到s數(shù)組中printf<"\n子串為：\n">;scanf<"%s",t>;//輸出主串get_nextval<t,nextval>;//得到nextval數(shù)組的值printf<"改進(jìn)nextval數(shù)組元素值為：\n">;print_nextval<next