数据结构复习笔记(5)

  1. 云栖社区>
  2. 博客>
  3. 正文

数据结构复习笔记(5)

嗯哼9925 2017-12-28 15:11:00 浏览417 评论0

摘要: 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...

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

【云栖快讯】阿里巴巴小程序繁星计划,20亿补贴第一弹云应用免费申请,限量从速!  详情请点击

网友评论