1,KMP算法
void preKmp(char *x, int m, int kmpNext[])
{
int i, j;
i = 0;
j = kmpNext[0] = -1;
while (i < m) {
while (j > -1 && x[i] != x[j])
j = kmpNext[j];
i++;
j++;
if (x[i] == x[j])
kmpNext[i] = kmpNext[j];
else
kmpNext[i] = j;
}
}
void KMP(char *x, int m, char *y, int n)
{//x为模式串,m为其长度,y为主串，n为其长度
int i, j, kmpNext[MAXSIZE];//kmpNext数组存放next函数值
/* Preprocessing */
preKmp(x, m, kmpNext);
/* Searching */
i = j = 0;
while (j < n) {
while (i > -1 && x[i] != y[j])
i = kmpNext[i];
i++;
j++;
if (i >= m) {
OUTPUT(j - i);
i = kmpNext[i];
}
}
}
2，二叉排序树的建立及查找算法
#include <stdlib.h>
#include <stdio.h>
#define NULL 0
typedef int KeyType;
typedef struct
{
KeyType key;
}ElemType; //元素类型
typedef struct BiTNode
{
ElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
BiTree find(BiTree root,KeyType key)
{ //在二叉排序树中查找其关键字等于给定值的结点是否存在，并输出相应信息
BiTNode *p;
p=root;
if (p==NULL) return NULL;
else if (p->data.key==key) return p;
else if (key<p->data.key) return find(p->lchild,key);
else return find(p->rchild,key);
}
void Insert(BiTree *p,BiTree t){ //在二叉排序树中插入一个新结点
if (*p==NULL) *p=t;
else if(t->data.key<(*p)->data.key) Insert(&((*p)->lchild),t);
else if(t->data.key>(*p)->data.key) Insert(&((*p)->rchild),t);
}
void inorder(BiTree p){ //中序遍历所建二叉排序树，将得到一个按关键字有序的元素序列
if(p!=NULL){
inorder(p->lchild);
printf("%5d",(p->data).key);
inorder(p->rchild);
}
}
void main(){
char ch;
KeyType key;
BiTree p,s;
int i=0;
printf("Please input datas (9999:end)：\n");//建立一棵二叉排序树，元素值从键盘输入，直到输入关键字等于9999为止
scanf("%4d",&key);
p=NULL;
while(key!=9999){
s=(BiTree)malloc(sizeof(BiTNode));
(s->data).key=key;
s->lchild=s->rchild=NULL;
Insert(&p,s);
scanf("%d",&key);
}
printf("Create is completed\n");
inorder(p); //中序遍历已建立的二叉排序树
printf("\n");
do{ //二叉排序树的查找，可多次查找，并输出查找的结果
printf("Input the key you want to search:");
scanf("%4d",&key);
s=find(p,key);
if (s!=NULL) printf("success,the value is %4d ",s->data.key);
else printf("unsuccess");
printf("\ncontinue?y:n\n");getchar();
ch=getchar();
}while(ch=='y'||ch=='Y');
}
本文转自Phinecos(洞庭散人)博客园博客，原文链接：http://www.cnblogs.com/phinecos/archive/2006/09/24/513017.html，如需转载请自行联系原作者，如需转载请自行联系原作者