数据结构-KMP算法的实现

5 总结

通过此次模式匹配中的KMP算法的实现的课设，我认识到自己在以前的课程学习中还有很多的不足。在课设中，我了解到各种算法对软件设计的重要性，它能帮助程序设计者设计出更好的程序为人们的日常生活提供了更大的帮助。本次课设在平时的字符的查找中发挥了重要作用。这次课设让我对C语言又复习了一遍。

6 附录：源程序清单

#include #include #include typedef struct LString { //串的链式存储表示。 char data; struct LString *next; }LString;

LString *Input(){

//通过标准输入设备输入串以链式存储存储数据并返回链的头指针。 LString *head, *tail, *p; int curlen=0; char ch;

head=(LString*)malloc(sizeof(LString));//建立头指针。 if(!head) { printf(\存储分配失败\ exit(0);

}//存储分配失败。 scanf(\ while(ch!='\\n') {

p=(LString*)malloc(sizeof(LString)); if(!p){

printf(\存储分配失败\ exit(0); }//存储分配失败。

p->data=ch; p->next=NULL;

if(curlen==0) head->next=p; else{

tail->next=p; }

9

tail=p;

++curlen;

head->data=curlen;//用头指针存储串的长度 scanf(\}

return head; }//Inpute

void Output(LString *T){

//在标准输出设备上输出串T。 LString *p; p=T->next;

while(p!= NULL) {

printf(\ p=p->next; }

printf(\ }//Output

int Length(LString *T){

//求串T的长度并返回其值。 int n=0; LString *head; head=T; if(head)

n=head->data; return n; }//Length

void Get_next(LString *T,int next[]){ //求模式串T的next函数并存入数组next。 int i=1; int j=0; int k;

char t[100];

LString *p; p=T;

for(k=0;k<=Length(T);k++) //将串T的链式存储转换为顺序存储并存入数组t。 {

t[k]=p->data; p=p->next; }

next[1]=0; while (i

10

{

++i; ++j; next[i] = j; }

else j= next[j]; }

next[i+1]='\\n'; }//Get_next

int Index_KMP(LString *S, LString *T,int pos,int next[]) {

// 利用模式串T的next函数求T在主串S中第pos个字符之后的位置的 // KMP算法。其中，T非空。,1≤pos≤StrLength(S)。 int i = pos; int j = 1; int k;

LString *p,*q; char s[255],t[255]; p=S; q=T;

for(k=0;k<=Length(S);k++) //将串S的链式存储转换为顺序存储 {

s[k]=p->data; p=p->next; }

for(k=0;k<=Length(T);k++) //将串T的链式存储转换为顺序存储 {

t[k]=q->data; q=q->next; }

while (i <= Length(S) && j <= Length(T)) {

if (j == 0 || s[i] == t[j]) { // 继续比较后继字符 ++i; ++j;

} else j = next[j]; // 模式串向右移动 }

if (j > t[0]) return i-t[0]; // 匹配成功 else return 0; } // Index_KMP

void main() {

system(\

system(\

system(\

11

printf(\ ┏━━━━━━━━━━━━━━━━━━━━━━━━━━━┓\\n\ printf(\ ┃㊣必做题4：KMP算法㊣┃\\n\ printf(\ ┃姓名：xxxx┃\\n\

printf(\ ┃学号：xxxxxxxxxx┃\\n\

printf(\ ┗━━━━━━━━━━━━━━━━━━━━━━━━━━━┛\\n\ int Loc, Next[255], pos=0,i=1,j=1; LString *A,*B;

printf(\输入执行KMP算法的模式串A并以ENTER键结束:\\n模式串:\ A=Input();//从标准输入设备接收模式串。

printf(\输入执行KMP算法主串B并以ENTER键结束:\\n主串:\ B=Input();//从标准输入设备接收主串。 printf(\

printf(\输入执行KMP算法从主串开始的位置并以ENTER键结束:\\npos=\ scanf(\从标准输入设备接收在主串执行KMP算法的开始位置。 while(pos<1)//判断输入是否正确。 {

printf(\输入错误请重新输入执行KMP算法的位置:\\npos=\ scanf(\ }

printf(\匹配结果如下:\\n\将结果输出到标准输出设备上。

printf(\匹配结果-------------------------------------------\\n\\n\ Get_next(A,Next);//调用Get_next函数。

Loc=Index_KMP(B,A,pos,Next);//调用Index_KMP函数并用Loc接收其函数值。 printf(\对A执行Next函数的值:\\n\\t\\t\\t\将next输出到标准输出设备上。 for(i=1;Next[i]!='\\n';i++) printf(\ \ if(Loc!=0){

printf(\模式串在主串的第%d位置:\\n\\n\ printf(\ Output(B); printf(\ while(j

Output(A);}

else printf(\匹配失败\\n\\n\ if(Loc==0)

printf(\匹配失败-------------------------------------\\n\ else printf(\匹配成功--------------------------------------\\n\}//main

12