KMP模式匹配算法.docx
- 文档编号:18526639
- 上传时间:2023-08-19
- 格式:DOCX
- 页数:28
- 大小:104.83KB
KMP模式匹配算法.docx
《KMP模式匹配算法.docx》由会员分享,可在线阅读,更多相关《KMP模式匹配算法.docx(28页珍藏版)》请在冰点文库上搜索。
KMP模式匹配算法
KMP模式匹配算法
1、需求分析
输入:
模式串,主串
输出:
一串值和匹配结果
功能要求:
模式串的next值表与匹配结果
2、设计概要
3、详细设计
#include
#include
#include
#include
#include
voidgetNext(constchar*t,int*Next)//Next数组
{
intk=-1;
intj=0;
intsize=strlen(t);
Next[0]=1;
while(j { if(k==-1||t[j]==t[k]) { k++; j++; Next[j]=k; } else k=Next[k]; } for(j=0;j { printf("Next表: %d",Next[j]); printf("\n"); } } intmyStrstr(constchar*Dest,constchar*subStr) { intdestSize=strlen(Dest); intsubSize=strlen(subStr); inti,j; int*Next=(int*)(malloc(sizeof(int)*subSize)); i=j=0; assert((Dest! =NULL)&&(subStr! =NULL)); getNext(subStr,Next); while(i { if(j==-1||Dest[i]==subStr[j]) { i++; j++; } else j=Next[j]; } if(j==subSize)returni-j; return-1; } intmain() { char*temp,*sub,*Dest; intch; unsignedinttemplen,length=20*sizeof(char); unsignedintmlength=20*sizeof(char); sub=(char*)malloc(length); Dest=(char*)malloc(length); if(sub==NULL||Dest==NULL) { printf("输入非法! \n"); exit(0); } temp=sub; printf("输入模式串: \n"); while((ch=getchar())! =10) { if((temp-sub)/sizeof(char)==length) { templen=length; sub=realloc(sub,length+=20*sizeof(char)); if(sub==NULL) { printf("输入非法! \n"); exit(0); } temp=sub+templen*sizeof(char); } *temp++=ch; } *temp='\0'; temp=Dest; printf("输入主串: \n"); while((ch=getchar())! =10) { if((temp-Dest)/sizeof(char)==mlength) { templen=mlength; Dest=realloc(Dest,mlength+=20*sizeof(char));//越界 if(Dest==NULL) { printf("输入非法! \n"); exit(0); } temp=Dest+templen*sizeof(char); } *temp++=ch; } *temp='\0'; printf("匹配起始位置为: %d\n",myStrstr(Dest,sub)); free(Dest); free(sub); return0; getchar(); } 四、调试过程 在调试过程中经常会有报错的情况,检查显示错误时发现大都是些丢掉分号或括号等由于粗心马虎等造成的小错误,因为这个程序比较简单,因此调试过程还算顺利。 五、用户使用说明 (1)首先输入模式串 (2)输入主串 (3)敲回车即输出next值 六、运行结果 Kruskal算法 一、需求分析 输入: 无向图(顶点序列,边序列) 输出: 一串字符和数值 功能要求: 输出最小生成树的各组成边及最小生成树的权值 二、概要设计 三、详细设计 #include #include #defineM20 #defineMAX20 typedefstruct { intbegin; intend; intweight; }EdgeType; typedefstruct { intadj; intweight; }AdjMatrix[MAX][MAX]; typedefstruct { AdjMatrixarc; intvexnum,arcnum; }MGraph; voidCreatGraph(MGraph*); voidsort(EdgeType*,MGraph*); voidMiniSpanTree(MGraph*); intFind(int*,int); voidCreatGraph(MGraph*G) { inti,j,n,m; printf("bianshuhedingdianshu: "); scanf("%d%d",&G->arcnum,&G->vexnum); for(i=1;i<=G->vexnum;i++) { for(j=1;j<=G->vexnum;j++) { G->arc[i][j].adj=G->arc[j][i].adj=0; } } for(i=1;i<=G->arcnum;i++) { printf("\nshuruyoubiandedingdian: "); scanf("%d%d",&n,&m); while(n<0||n>G->vexnum||m<0||n>G->vexnum) { printf("输入的数字不符合要求请重新输入: "); scanf("%d%d",&n,&m); } G->arc[n][m].adj=G->arc[m][n].adj=1; getchar(); printf("\n%dhe%djianquanzhi: ",n,m); scanf("%d",&G->arc[n][m].weight); } printf("linjiejuzheng: \n"); for(i=1;i<=G->vexnum;i++) { for(j=1;j<=G->vexnum;j++) { printf("%d",G->arc[i][j].adj); } printf("\n"); } } voidsort(EdgeTypeEdgeTypes[],MGraph*G) { inti,j,t; for(i=1;i { for(j=i+1;j<=G->arcnum;j++) { if(EdgeTypes[i].weight>EdgeTypes[j].weight) { t=EdgeTypes[i].begin; EdgeTypes[i].begin=EdgeTypes[j].begin; EdgeTypes[j].begin=t; t=EdgeTypes[i].end; EdgeTypes[i].end=EdgeTypes[j].end; EdgeTypes[j].end=t; t=EdgeTypes[i].weight; EdgeTypes[i].weight=EdgeTypes[j].weight; EdgeTypes[j].weight=t; } } } printf("paixuzihou: \n"); for(i=1;i<=G->arcnum;i++) { printf("<<%d,%d>>%d\n",EdgeTypes[i].begin,EdgeTypes[i].end,EdgeTypes[i].weight); } } voidMiniSpanTree(MGraph*G) { inti,j,n,m; intk=1; intfather[M]; EdgeTypeEdgeTypes[M]; for(i=1;i { for(j=i+1;j<=G->vexnum;j++) { if(G->arc[i][j].adj==1) { EdgeTypes[k].begin=i; EdgeTypes[k].end=j; EdgeTypes[k].weight=G->arc[i][j].weight; k++; } } } sort(EdgeTypes,G); for(i=1;i<=G->arcnum;i++) { father[i]=0; } printf("zuixiaoshengchengshu: \n"); for(i=1;i<=G->arcnum;i++) { n=Find(father,EdgeTypes[i].begin); m=Find(father,EdgeTypes[i].end); if(n! =m) { father[n]=m; printf("<<%d,%d>>%d\n",EdgeTypes[i].begin,EdgeTypes[i].end,EdgeTypes[i].weight); } } } intFind(int*father,intf) { while(father[f]>0) { f=father[f]; } returnf; } intmain(void) { MGraph*G; intq; G=(MGraph*)malloc(sizeof(MGraph)); if(G==NULL) { printf("memoryallcationfailed,goodbye"); exit (1); } do{ CreatGraph(G); MiniSpanTree(G); printf("Doyouwantagain? (1or0): "); scanf("%d",&q);}while(q); system("pause"); return0; getch(); } 四、调试分析 刚开始没弄懂程序的包含关系,走了弯路,弄了一大堆之后发现不能运行,有数多个错误,当时很苦恼,后来找了班级数据结构比较好的同学问了一下,把程序做了个大改变,才得以实现。 五、用户使用说明 (1)输入边数和顶点数 (2)依次输入有边的顶点和其间的权值 (3)按回车输出结果 六、输出结果 二叉排序树生成算法(含平衡化) 一、需求分析 输入: 遍历序列(先序序列和中序序列或中序序列和后序序列),最大字符数为20. 输出: 恢复后的二叉树的三序字符串。 功能要求: 输出二叉树形态或输出二叉树的三种遍历序列 二、概要设计 三、详细设计 #include #definemaxsize26 typedefchardatatype;//结点属性值类型 typedefstructbitreenode//二叉树结点类型 { datatypeinfo; structbitreenode*leftchild,*rightchild; }bitreenode; typedefstructstack//栈的定义 { bitreenode*data[maxsize]; inttag[maxsize]; inttop; }seqstack; voidinitstack(seqstack*t)//栈的初始化 { t->top=-1; } intemptystack(seqstack*t)//判断栈是否为空 { return(t->top==-1? 1: 0); } voidpushstack(seqstack*t,bitreenode*e)//入栈 { t->data[++t->top]=e; } bitreenode*popstack(seqstack*t)//出栈 { return(t->data[t->top--]); } bitreenode*getstack_top(seqstack*t)//取栈顶元素 { return(t->data[t->top]); } bitreenode*creatbitree()//按深度输入完全二叉树来建立二叉树 {//从上到下,从左到右,输入完全二叉树 inti; struct { datatypex; bitreenode*p; }y[maxsize+1]; charc[maxsize]; gets(c); for(i=0;i { y[i+1].x=c[i]; if(y[i+1].x! ='$') { y[i+1].p=(bitreenode*)malloc(sizeof(bitreenode)); y[i+1].p->info=c[i]; y[i+1].p->leftchild=y[i+1].p->rightchild=NULL; } else y[i+1].p=NULL; } for(i=1;i<=strlen(c)/2;i++) { y[i].p->leftchild=y[2*i].p; if((2*i+1)>strlen(c)) break; y[i].p->rightchild=y[2*i+1].p; } return(y[1].p); } voidpreorder_by_digui(bitreenode*t)//前序遍历(递归) { if(t) { printf("%c",t->info); preorder_by_digui(t->leftchild); preorder_by_digui(t->rightchild); } } voidinorder_by_digui(bitreenode*t)//中序遍历(递归) { if(t) { inorder_by_digui(t->leftchild); printf("%c",t->info); inorder_by_digui(t->rightchild); } } voidpostorder_by_digui(bitreenode*t)//后序遍历(递归) { if(t) { postorder_by_digui(t->leftchild); postorder_by_digui(t->rightchild); printf("%c",t->info); } } main() { bitreenode*root;//指向二叉树根结点的指针 root=creatbitree(); printf("前序遍历\n"); preorder_by_digui(root); printf("\n"); printf("\n中序遍历\n"); inorder_by_digui(root); printf("\n"); printf("\n后序遍历\n"); postorder_by_digui(root); printf("\n"); getch(); } 四、调试分析 在老师讲二叉树的遍历时学的好算比较好,因此这次程序设计做的也还算顺利,仅是遇到一些犹豫粗心引起的小问题,经过调试之后便可运行出结果。 五、用户使用说明 (1)按顺序输入一个完全二叉树 (2)敲回车即可输出二叉树的前序、中序、后序遍历结果 六、输出结果 堆排序 一、需求分析 输入: 待排序数据序列 输出: 数个排序情况,直至最终正确结果 功能要求: 输出每步骤排序情况;希望能进行排序方向的选择(从大到小或从小到大) 二、概要设计 三、详细设计 #include #defineN6 intk,j; voidbuild(int*a,inti,intn){ inttmp; k=i; j=2*k+1; while(j<=n){ if(j j++; if(a[k]>=a[j])break; tmp=a[k]; a[k]=a[j]; a[j]=tmp; k=j; j=2*j+1; } } voidprnt(int*a,intn){ inti; printf("\n"); for(i=0;i printf("%3d",a[i]); } printf("\n"); } voidprnthp(int*a,intb1,intb2){ intsize; inth=0,sum=0,item=1; inti,j,cnt,start,tmp; size=b2-b1+1; while(sum<=size){ sum+=item; h++; item*=2; } item=1; cnt=0; start=b1; tmp=1; printf("\n--------------------------------------------\n"); printf("堆: \n"); while (1){ for(i=0;i for(j=0;j printf(""); for(j=0;j for(j=0;j if(cnt>size-1)gotoend; printf("%4d",a[cnt++]); } printf("\n"); tmp*=2; } } end: printf("\n"); return; } voidprntar(int*a,intb2,intlen){ inti; printf("已排序: \n"); for(i=0;i printf(""); } for(i=b2;i<=len;i++){ printf("%3d",a[i]); } printf("\n"); } main(){ inta[50]; inti; inttmp; intsum; intnum; intlen; printf("堆排序\n"); printf("\n============================================\n"); printf("\n请输入待排序数组个数,以回车结束: \n"); scanf("%3d",&len); printf("\n请输入待排序数组,以回车结束: \n"); for(i=0;i scanf("%3d",&a[i]); tmp=1;sum=0; while(sum+tmp<=len){ sum+=tmp; tmp*=2; } printf("\n============================================\n"); printf("\n初始数组: \n"); prnt(a,len); for(i=sum-1;i>=0;i--) build(a,i,len-1); prnthp(a,0,len-1); for(i=0;i tmp=a[0]; a[0]=a[len-1-i]; a[len-1-i]=tmp; build(a,0,len-2-i); prnthp(a,0,len-2-i); prntar(a,len-1-i,len-1); } printf("\n--------------------------------------------\n"); printf("\n排序结果: \n"); prnt(a,len); printf("\n============================================\n\n"); getchar(); } 四、调试分析 堆排序相比较而言不是很难,但由于自己还是知识掌握的还凑合,而一用于实际就不太行了,所以中途也很惆怅过,后经同学间相互讨论学习都将其顺利解决了。 五、用户使用说明 (1)输入待排序数组个数,以回车结束 (2)请输入待排序数组,各数组中间加空格 (3)敲回车即输出结果 六、输出结果
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- KMP 模式 匹配 算法