kmp数据结构课程设计报告(2)

本系统共设置6个子程序，各子程序的函数名及功能说明如下。 （1）Void get_next(SString T,int next[]) //求模式串T的next函数值并存入数组next

（2）Int Index(SString S,SString T,int pos）//KMP匹配函数

（3）Int lenth(SString str) //取串str的长度

（4）Void find(char name[],SString keys) //查找函数，对于输入的每一个要查找的关键字，从文本文件中逐行读取字符串查找。 //调用(1),(2),(3)

（5）Void main() //主函数，负责系统的输入和输出。调用(4) （6）strcmp(s,zhanghao) //账号匹配函数，负责系统的进入。

3详细设计

3.1 数据类型定义

(1)定长顺序存储串类型的定义 #define MAXSTRLEN 255 //最大串长

typedef char SString[MAXSTRLEN+1];//串的定长顺序存储表示，0号单元存放串的长度

typedef char SString[MAXSTRLEN+1]; char zhanghao[7]="888888"; //定义初始密码

（2）全局变量的定义

int next[MAXSTRLEN] //KMP算法中用到的next数组

3.2 系统主要子程序详细设计

（1）主函数模块设计，负责系统的输入输出工作，调用查找函数。void main()

{ 输入包含路径的文本文件名； 输入要查找的关键字个数； 一次性输入要查找的关键字；

对于每一个关键字，循环调用find函数进行查找统计； }

（2）查找模块设计

void find(char name[],SString keys) { SString text;

int i=1,j=0,k,q=0; //i用于存放行号，j用于存放列号,k用于输出格式的控制,q用于统计出现次数 FILE *fp;

if (!(fp=(fopen(name,"r")))) //打开小说文件 { printf("打开文件出错!\n"); exit(0); }

keys[0]=lenth(keys); //求关键字的长度 printf("\n%s\n",&keys[1]); //打印关键字

while (!feof(fp)) //如果还没到小说文件末尾，则继续循环

{ k=0; fgets(&text[1],MAXSTRLEN,fp); //从小说文件中读取一行字符串，存入text串中

text[0]=lenth(text); //求读入的串的长度

j=Index(text,keys,j+1); //调用KMP算法，统计关键字在该行出现的位置，若匹配不成功则返回0 if (j!=0)

{printf("行=%d,列=%d",i,j); k++;} //若匹配成功则打印行号和列号

while(j!=0) //若该行找到了关键字，则继续寻找看是否还能匹配成功

{ j=Index(text,keys,j+1); //调用KMP算法从刚找到的列号后一字符起匹配 if (j!=0)

{printf(",%d",j);k++;} //若匹配成功，则打印列号 }

i++; //行号加1，在下一行中寻找

q+=k; //累加k 以统计关键字出现次数 if (k) printf("\n"); //输出格式控制 }

printf("%s出现%d次。\n",&keys[1],q); //打印关键字出现次数 }

（3）求next函数值

void get_next(SString T,int next[]) { int j=1,k=0; next[1]=0; while(j<T[0])

{ if(k==0||T[k]==T[j])

{ ++j; ++k; if(T[j]!=T[k]) next[j]=k;

else next[j]=next[k]; } } }

（4）KMP匹配函数

int Index(SString S,SString T,int pos)

{ //利用模式串T的next函数球T主串S中第POS个字符之后的位置的KMP算法 int i=pos,j=1; while(i<=S[0]&&j<=T[0])

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

else j=next[j]; //模式串向右移动 } if(j>T[0])

return (i-T[0]); //匹配成功 else return 0; //匹配失败主程序模块

（5）账号匹配函数 { char s[8]; int n=3; int flag=0;

do{ printf("请输入6位数的软件账号:\n"); scanf("%s",s);

if(!strcmp(s,zhanghao)) /*账号匹配验证*/ { printf("账号输入正确，请输入密码\n\n\n"); flag=1; break; } else{ printf("账号输入不正确，验证失败，请重新输入:\n"); n--; } }

while(n>0); if(!flag)

{printf("你已输入3次均不成功!是否忘记账号，请与工作人员联系，工作人员将尽快为你解决\n"); /*已输入3次*/

exit(0); /*自动退出*/ } char c[8]; int l=3;

do{ printf("请输入6位数的软件密码:\n"); scanf("%s",c);

if(!strcmp(c, password)) /*密码匹配验证*/ { printf("信息匹配成功，正在飞速进入界面\n\n\n"); flag=1; break; } else{ printf("密码输入不正确，验证失败，请重新输入:\n"); l--; } }

while(l>0);

if(!flag)

{printf("你已输入3次均不成功!是否忘记密码，请与工作人员联系，工作人员将尽快为你解决\n"); /*已输入3次*/

exit(0); /*自动退出*/ }

（6）界面颜色设计 在main函数中添加 int a1=6;

system("color a1"); 将界面设置成绿色

4调试分析与结果

最终程序调试完成，输入相应数据，程序运行的结果如下所示。

4.1 实验数据

使用本程序代码WENJIAN.cpp作为实验数据

4.2 程序运行截图

图 3.1验证账号信息启动程序

图3.2进入程序界面

图3.3 输入文档及查询内容

图3.4 输出查询结果

图3.5 继续查询或退出程序

4.3 调试过程

在程序运行的过程中，曾经出现了输入数据发生死循环问题，最终发现是一个for循环判断的逻辑出现了错误，导致将正确的数据判断成了错误的数据，并反复在循环内判断造成了不良后果。最终在排查错误的时候，检查到了错误，并解决。一个中英文字符的不同就造成了程序报错， 经过排查，也得到了解决。所以说细心和一个良好的编写习惯很重要。

4.4 待完善部分

本程序在使用的时候仍然有很多不尽人意的地方：

1、该程序的算法不是最高效的，出现错误的概率理论上还不是较小，有更好的

2、程序没有实现读取电脑上任意磁盘中任意文件的功能，。

5课设总结

在程序编写时由于个人电脑系统兼容性，不能使用VC，只好在cfree上进行编写，过程中了解了一些编程系统间的不同，就比如cfree要求把main改成整型，而在VC中又应该是void，还有有些头文件在不同系统中编写也不一样，而且有一些头文件不能找到，只能报错或程序闪退，过程中反反复复改了不知道几次，终于成功运行了，为了改变界面单调的背景，我在网上查询了颜色函数的使用，想要深入可是又有太多没学过，因为大幅提升界面，要涉及到Windows系统，只能现学现卖，学艺不精只能改背景颜色，不过绿色界面好挺好看的，也算是有进步。

通过本次的课程设计，我对于模式匹配算法有了更深刻的认识。KMP算法是一种最基本最常用的一种数据结构。有比它好的也有比它差的算法，该程序基于模式匹配算法中的KMP …… 此处隐藏：3221字，全部文档内容请下载后查看。喜欢就下载吧 ……