数据结构复习笔记(5)-白红宇

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，如需转载请自行联系原作者，如需转载请自行联系原作者