基于改進KMP算法的字符文件子串查找

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