查找相关数据结构和算法-白红宇

查找相关数据结构和算法

阅读量：7108 次

发布时间：2019-06-28

本文共 4736 字，大约阅读时间需要 15 分钟。

#include <stdio.h>

#include "stdlib.h"

#define MAXL 50

typedef int KeyType ;

typedef char * InfoType ;

typedef struct

{

KeyType key;

InfoType data;

}NodeType;

typedef NodeType SeqList[MAXL];

typedef struct

{

KeyType key;

int link;

}IdxType;

typedef IdxType IDX[MAXL];

typedef struct node

{

KeyType key;

InfoType data;

struct node *lchild, *rchild;

}BSTNode;

//二分查找法

int BinSearch(SeqList R, int n, KeyType k)

{

int low = 0, high = n-1, mid=0;

while(low <= high)

{

mid = (low + high) / 2;

if(R[mid].key == k) return mid;

else if(R[mid].key > k ) high = mid-1;

else low = mid + 1;

}

return -1;

}

//一下是递归算法

int BinSearch2(SeqList R, int low, int high, KeyType k)

{

int mid;

if(low <= high)

{

mid = (high + low )/ 2;

if(R[mid].key < k)

return BinSearch2(R,mid + 1,high, k);

else if(R[mid].key > k )

return BinSearch2(R,low, high -1,k);

else return mid;

}

else return -1;

}

//分块查找

int IdxSearch(IDX I, int m,SeqList R, int n,KeyType k)

{

int low=0, high = m-1, mid,i;

int b = n/m;

while(low <= high)

{

mid = (low + high) / 2;

if(I[mid].key >= k) high = mid -1;

else low = mid +1;

}

if(low < m)

{

i = I[low].link;

while(i<=I[low].link + b -1 && R[i].key != k) i++;

if(i <= I[low].link+b-1) return i;

else return -1;

}

return -1;

}

//树的查找节点的算法

BSTNode *BSTSearch(BSTNode *bt, KeyType k) //查找树中的节点当为空的时候返回空，当等于的时候返回其本身，否则的递归调用左或者右子树

{

if(bt == NULL) return NULL;

else if(bt->key == k) return bt;

else if (bt->key > k) return BSTSearch (bt->lchild, k);

else return BSTSearch (bt->rchild,k);

}

//递归插入节点

int BSTInsert(BSTNode *p, KeyType k)

{

if(p == NULL)

{

p = (BSTNode *)malloc(sizeof(BSTNode));

p->key = k;

p->lchild = p->rchild = NULL;

return 1;

}

else if(k == p->key ) return 0;

else if(k > p->key) return BSTInsert(p->rchild,k);

else return BSTInsert (p->lchild,k);

}

//构造排序树

void CreateBST(BSTNode *bt, KeyType str[],int n)

{

int i=0;

bt = NULL;

while(i<n)

{

BSTInsert(bt,str[i]);

i++;

}

}

//删除节点

int BSTDelete(BSTNode *bt, KeyType k)

{

BSTNode *p = bt, *f,*r,*f1;

f = NULL;

while(p != NULL && p->key != k) //此循环是为了能够找到，所在的节点

{

f = p; //f表示父节点

if(p->key > k) p = p->lchild;

else p = p->rchild;

}

if(p == NULL) return 0; //为找到所需节点

else if(p->lchild == NULL) //左子树为空的情况

{

if(f == NULL) bt = p->rchild; //如果父节点是根节点，则用右子树代替他

else if(f->lchild == p)

{

f->lchild = p->rchild;

free(p);

}else if(f->rchild == p)

{

f->rchild = p->rchild;

free(p);

}

}

else if(p->rchild == NULL)

{

if(f == NULL) bt = p->lchild;

else if(f->lchild == p)

{

f->lchild = p->lchild;

free(p);

}

else if(p->rchild == p)

{

f->lchild = p->lchild;

free(p);

}

}

else

{

f1=p; r = p->lchild;

while(r->rchild != NULL)

{

f1 = r;

r = r->rchild;

}

if(f1->lchild == r) f1->lchild = r->lchild;

else if(f1->rchild == r) f1->rchild = r->lchild;

r->lchild = p->lchild; //用r代替p

r->rchild = p->rchild;

if(f == NULL) bt =r;

else if (f->lchild ==p)

f->lchild = r;

else f->rchild = r;

free(p);

}

return 1;

}

//设计在二叉排序树中插入指定关键字的非递归算法

int BSTInsert1(BSTNode *bt, KeyType k)

{

BSTNode *f, *p = bt;

while(p != NULL)

{

if(p->key == k) return 0;

f = p;

if(p->key > k) p = p->lchild;

else p = p->rchild;

} //在树中找到需要插入节点的位置

p = (BSTNode *)malloc(sizeof(BSTNode ));

p->key = k;

p->lchild = p->rchild = NULL;

if(bt == NULL) //判断是否头结点是否为空 f保存的是p的父节点

bt = p;

else if(f->key > k)

f->lchild = p;

else f->rchild = p;

return 1;

}

//递归插入节点与非递归插入的不同之处在于递归在刚开始的时候就进行判断是否为要插入的位置，然后根据条件确定是否递归

//非递归则是先利用循环找到要插入的位置，然后再进行判断是插入到左节点还是右节点

//递增的输出一个二叉树的节点，由题知应该使用中序遍历

void order(BSTNode *bt)

{

if(bt != NULL)

{

order(bt->lchild);

printf("%d ",bt->key);

order(bt->rchild);

}

}

//设计一个算法从大到小输出其值不小k的关键字因为是从大到小所以先遍历右子树

void Output(BSTNode *bt, KeyType k)

{

if(bt == NULL) return ;

if(bt->rchild != NULL) Output(bt->rchild,k);

if(bt->key >= k)printf("%d ", bt->key );

if(bt->lchild != NULL) Output(bt->lchild,k);

}

//设计一个算法求出指定节点在二叉树中的层次

int level(BSTNode *bt, KeyType k)

{

int n=1;

BSTNode *p = bt;

while(p != NULL && p->key != k)

{

if(p->key > k) p = p->lchild;

else p = p->rchild;

n++; //n在此处是记录层数，因为查找是一层一层向下找的

}

if(p != NULL) return n;

else return 0;

}

#define MAXWORD 20

typedef struct tnode1

{

char ch;

int count;

struct tnode1 *lchild, *rchild;

}TNode;

TNode * CreateTree(TNode *&p, char c)

{

if(p == NULL)

{

p = (TNode *)malloc(sizeof(TNode ));

p->ch = c; p->count = 1;

p->lchild = p->rchild = NULL;

return p;

}

else if(p->ch == c) p->count++;

else if(p->ch > c) CreateTree(p->lchild,c);

else CreateTree(p->rchild,c);

}

void DispTree(TNode *p)

{

if(p != NULL)

{

DispTree(p->lchild);

printf("%c %d\n",p->ch,p->count);

DispTree(p->rchild);

}

}

void main()

{

TNode *root = NULL;

int i=0;

char str[MAXWORD];

printf("Input a string :\n");

gets(str);

while(str[i] != '\0')

{

CreateTree(root,str[i]);

i++;

}

printf("The string and times they appears :\n");

DispTree(root);

}

转载于:https://blog.51cto.com/saibro/1183652

你可能感兴趣的文章

动态开辟二维数组

查看>>

Kendo UI开发教程：使用Kendo UI库实现对象的继承

查看>>

《Linux学习并不难》使用RPM软件包（3）：安装RPM软件包

常见的nginx,apache反代用户请求至tomcat主机的实现方法

查看>>

Android 常见 View 控件滑动和拖动的几种方式

查看>>

分页查询

查看>>

MyBatis读书笔记----使用JDBC方式返回主键自增的值的两种方式

jsp通过include指令引入html乱码的解决方法

查看>>

解决mysql：The server quit without updating PID file

做一次面向对象的体操：将 JSON 字符串转换为嵌套对象的一种方法