查找--数据结构

宁在春

发布于 2022-10-31 13:56:03

6250

发布于 2022-10-31 13:56:03

查找是在大量的信息中寻找一个特定的信息元素，在计算机应用中，查找是常用的基本运算，例如编译程序中符号表的查找。本文简单概括性的介绍了常见的七种查找算法，说是七种，其实二分查找、插值查找以及斐波那契查找都可以归为一类——插值查找。插值查找和斐波那契查找是在二分查找的基础上的优化查找算法。树表查找和哈希查找会在后续的博文中进行详细介绍。

查找定义：根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素（或记录）。

1. 顺序查找

说明：顺序查找适合于存储结构为顺序存储或链接存储的线性表。

**基本思想：**顺序查找也称为线形查找，属于无序查找算法。从数据结构线形表的一端开始，顺序扫描，依次将扫描到的结点关键字与给定值k相比较，若相等则表示查找成功；若扫描结束仍没有找到关键字等于k的结点，表示查找失败。

复杂度分析：

查找成功时的平均查找长度为：（假设每个数据元素的概率相等） ASL = 1/n(1+2+3+…+n) = (n+1)/2 ; 　　当查找不成功时，需要n+1次比较，时间复杂度为O(n);

所以， 顺序查找的时间复杂度为O(n)。

C++实现源码：

//顺序查找
int SequenceSearch(int a[], int value, int n)
{
    int i;
    for(i=0; i<n; i++)
        if(a[i]==value)
            return i;
    return -1;
}

2. 二分查找

https://www.bilibili.com/video/BV1i4411a78o/?spm_id_from=autoNext

说明：元素必须是有序的，如果是无序的则要先进行排序操作。

**基本思想：**也称为是折半查找，属于有序查找算法。**用给定值k先与中间结点的关键字比较，中间结点把线形表分成两个子表，若相等则查找成功；**若不相等，再根据k与该中间结点关键字的比较结果确定下一步查找哪个子表，这样递归进行，直到查找到或查找结束发现表中没有这样的结点。

复杂度分析：最坏情况下，关键词比较次数为log2(n+1)，且期望时间复杂度为O(log2n)；

注：折半查找的前提条件是需要有序表顺序存储，对于静态查找表，一次排序后不再变化，折半查找能得到不错的效率。但对于需要频繁执行插入或删除操作的数据集来说，维护有序的排序会带来不小的工作量，那就不建议使用。——《大话数据结构》

C++实现源码：

//二分查找（折半查找），版本1
int BinarySearch1(int a[], int value, int n)
{
    int low, high, mid;
    low = 0;
    high = n-1;
    while(low<=high)
    {
        mid = (low+high)/2;
        if(a[mid]==value)
            return mid;
        if(a[mid]>value)
            high = mid-1;
        if(a[mid]<value)
            low = mid+1;
    }
    return -1;
}
//123456789101112131415161718
//二分查找，递归版本
int BinarySearch2(int a[], int value, int low, int high)
{
    int mid = low+(high-low)/2;
    if(a[mid]==value)
        return mid;
    if(a[mid]>value)
        return BinarySearch2(a, value, low, mid-1);
    if(a[mid]<value)
        return BinarySearch2(a, value, mid+1, high);
}

总结

通过比较折半查找的平均查找长度，同前面介绍的顺序查找相对比，明显折半查找的效率要高。但是折半查找算法只适用于有序表，同时仅限于查找表用顺序存储结构表示。

3、索引查找

#include <stdio.h>
#include <stdlib.h>
#include<bits/stdc++.h>
using namespace std;
struct index {  //定义块的结构
	int key;
	int start;
} newIndex[3];   //定义结构体数组

int cmp(const void *a,const void* b) {
	return (*(struct index*)a).key>(*(struct index*)b).key?1:-1;
}
int search(int key, int a[]) {
	int i, startValue;
	i = 0;
	while (i<3 && key>newIndex[i].key) { //确定在哪个块中，遍历每个块，确定key在哪个块中
	// 99 99>newIndex[0]=21
	// 99 99>newIndex[1]=27
	// 99 99<newIndex[2]=333   i=2
		i++;
	}
	if (i>=3) {  //大于分得的块数，则返回0
		return -1;
	}
	startValue = newIndex[i].start;  //startValue等于块范围的起始值
	while (startValue <= startValue+5 && a[startValue]!=key) {
		startValue++;
	}
	if (startValue>startValue+5) {  //如果大于块范围的结束值，则说明没有要查找的数
		return -1;
	}
	return startValue;
}

int main() {
	int i, j=-1, k, key;
//    int a[] = {33,42,44,38,24,48, 22,12,13,8,9,20,  60,58,74,49,86,53};
	int a[]= {1 ,5, 4, 21, 19,
	
	          22, 25, 23, 24, 27,
	          
	          31, 99, 333, 35, 29
	         };
	//确认模块的起始值和最大值
	for (i=0; i<3; i++) {
		newIndex[i].start = j+1;  //确定每个块范围的起始值
		// newIndex[0]=0~4
		// newIndex[1]=5~9
		//new Index[2]=10~14
		j += 5;
		for (int k=newIndex[i].start; k<=j; k++) {
			if (newIndex[i].key<a[k]) {
				newIndex[i].key=a[k]; //  0  5  4  21  newIndex[0].key=21 
									//  22  25  23  24 27  newIndex[1].key=27
									//  31  99  333   newIndex[2].key=333 	
			}
		}
		cout<<"	newIndex[i].key:=="	<<newIndex[i].key<<endl; //查看块的索引
	}
	//对结构体按照 key 值进行排序
	qsort(newIndex,3, sizeof(newIndex[0]), cmp);
	// cmp 是一个给定一个排序规则  是从小到大 还是从大到小   
	//https://www.cnblogs.com/tsingke/p/5347672.html
	//四、对结构体一级排序 从小到大排序 
	/*
	struct In
	{
	  double data;
	   int other;
	}s[100]；

	int cmp( const void *a ,const void *b)
	{
	  return (*(struct In *)a)->data > (*(struct In *)b)->data ? 1 : -1;
	}
	qsort(s,100,sizeof(s[0]),cmp);
	*/
	
	//输入要查询的数，并调用函数进行查找
	printf("请输入您想要查找的数：\n");
	scanf("%d", &key);
	k = search(key, a);
	//输出查找的结果
	if (k>=0) {
		printf("查找成功！您要找的数在数组中的位置是：%d\n",k+1);
	} else {
		printf("查找失败！您要找的数不在数组中。\n");
	}
	return 0;
}

4、动态查找

观看视频：

https://www.bilibili.com/video/BV1Ca4y1i7Mj 1

https://www.bilibili.com/video/av17499415/ 2

https://www.cnblogs.com/sench/p/7783331.html 3 博客（二叉树的建立和操作）[c++类操作]

https://blog.csdn.net/yixianfeng41/article/details/52802855 4 博客（二叉树的建立和操作）[普通c++操作]

注：动态查找表中做查找操作时，若查找成功可以对其进行删除；如果查找失败，即表中无该关键字，可以将该关键字插入到表中。

4.1、什么是二叉排序树？

二叉排序树要么是空

二叉树

，要么具有如下特点：

二叉排序树中，如果其根结点有左子树，那么左子树上所有结点的值都小于根结点的值；
二叉排序树中，如果其根结点有右子树，那么右子树上所有结点的值都大于根结点的值；
二叉排序树的左右子树也要求都是二叉排序树；

例如，

图 1 就是一个二叉排序树：

图 1 二叉排序树

4.2、使用二叉排序树查找关键字二叉排序树是中序遍历

二叉排序树中查找某关键字时，查找过程类似于次优二叉树，在二叉排序树不为空树的前提下，首先将被查找值同树的根结点进行比较，会有 3 种不同的结果：

如果相等，查找成功；
如果比较结果为根结点的关键字值较大，则说明该关键字可能存在其左子树中；
如果比较结果为根结点的关键字值较小，则说明该关键字可能存在其右子树中；

实现函数为：（运用递归的方法）

BiTree SearchBST(BiTree T,KeyType key){
    //如果递归过程中 T 为空，则查找结果，返回NULL；或者查找成功，返回指向该关键字的指针
    if (!T || key==T->data) {
        return T;
    }else if(key<T->data){
        //递归遍历其左孩子
        return SearchBST(T->lchild, key);
    }else{
        //递归遍历其右孩子
        return SearchBST(T->rchild, key);
    }
}

4.3、二叉排序树中插入关键字

二叉排序树本身是动态查找表的一种表示形式，有时会在查找过程中插入或者删除表中元素，当因为查找失败而需要插入数据元素时，该数据元素的插入位置一定位于二叉排序树的叶子结点，并且一定是查找失败时访问的最后一个结点的左孩子或者右孩子。

例如，在图 1 的二叉排序树中做查找关键字 1 的操作，当查找到关键字 3 所在的叶子结点时，判断出表中没有该关键字，此时关键字 1 的插入位置为关键字 3 的左孩子。

所以，二叉排序树表示动态查找表做插入操作，只需要稍微更改一下上面的代码就可以实现，具体实现代码为：

BOOL SearchBST(BiTree T,KeyType key,BiTree f,BiTree *p){
    //如果 T 指针为空，说明查找失败，令 p 指针指向查找过程中最后一个叶子结点，并返回查找失败的信息
    if (!T){
        *p=f;
        return false;
    }
    //如果相等，令 p 指针指向该关键字，并返回查找成功信息
    else if(key==T->data){
        *p=T;
        return true;
    }
    //如果 key 值比 T 根结点的值小，则查找其左子树；反之，查找其右子树
    else if(key<T->data){
        return SearchBST(T->lchild,key,T,p);
    }else{
        return SearchBST(T->rchild,key,T,p);
    }
}
//插入函数
BOOL InsertBST(BiTree T,ElemType e){
    BiTree p=NULL;
    //如果查找不成功，需做插入操作
    if (!SearchBST(T, e,NULL,&p)) {
        //初始化插入结点
        BiTree s=(BiTree)malloc(sizeof(BiTree));
        s->data=e;
        s->lchild=s->rchild=NULL;
        //如果 p 为NULL，说明该二叉排序树为空树，此时插入的结点为整棵树的根结点
        if (!p) {
            T=s;
        }
        //如果 p 不为 NULL，则 p 指向的为查找失败的最后一个叶子结点，只需要通过比较 p 和 e 的值确定 s 到底是 p 的左孩子还是右孩子
        else if(e<p->data){
            p->lchild=s;
        }else{
            p->rchild=s;
        }
        return true;
    }
    //如果查找成功，不需要做插入操作，插入失败
    return false;
}

通过使用二叉排序树对动态查找表做查找和插入的操作，同时在中序遍历二叉排序树时，可以得到有关所有关键字的一个有序的序列。

例如，假设原二叉排序树为空树，在对动态查找表 {3，5，7，2，1} 做查找以及插入操作时，可以构建出一个含有表中所有关键字的二叉排序树，过程如图 2 所示:

图 2 二叉排序树插入过程

通过不断的查找和插入操作，最终构建的二叉排序树如图 2（5）所示。当使用中序遍历算法遍历二叉排序树时，得到的序列为：1 2 3 5 7 ，为有序序列。

一个无序序列可以通过构建一棵二叉排序树，从而变成一个有序序列。

4.4、二叉排序树中删除关键字

在查找过程中，如果在使用二叉排序树表示的动态查找表中删除某个数据元素时，需要在成功删除该结点的同时，依旧使这棵树为二叉排序树。

假设要删除的为结点 p，则对于二叉排序树来说，需要根据结点 p 所在不同的位置作不同的操作，有以下 3 种可能：

1、结点 p 为叶子结点，此时只需要删除该结点，并修改其双亲结点的指针即可； 2、结点 p 只有左子树或者只有右子树，此时只需要将其左子树或者右子树直接变为结点 p 双亲结点的左子树即可； 3、结点 p 左右子树都有，此时有两种处理方式：

1）令结点 p 的左子树为其双亲结点的左子树；结点 p 的右子树为其自身直接前驱结点的右子树，如图 3 所示；

图 3 二叉排序树中删除结点（1）

2）用结点 p 的直接前驱（或直接后继）来代替结点 p，同时在二叉排序树中对其直接前驱（或直接后继）做删除操作。如图 4 为使用直接前驱代替结点 p：

图 4 二叉排序树中删除结点（2）

图 4 中，在对左图进行中序遍历时，得到的结点 p 的直接前驱结点为结点 s，所以直接用结点 s 覆盖结点 p，由于结点 s 还有左孩子，根据第 2 条规则，直接将其变为双亲结点的右孩子。

4.5、二叉排序树的实现：

一、

#include<bits/stdc++.h>
using namespace std;

class BSTNode {
	public:
		int key;            //结点的值
		BSTNode* left;        //结点的左孩子
		BSTNode* right;        //结点的右孩子
		BSTNode* parent;    //结点的双亲

		/*构造函数*/
		BSTNode():parent(NULL) {}
		BSTNode(int key, BSTNode* left, BSTNode* right, BSTNode* parent) :key(key), left(left), right(right), parent(parent) {}
};
class BSTree {
	private:
		BSTNode* root;        //根节点
	public:
		/*构造函数*/
		BSTree() :root(NULL) {};

		/*获取根节点*/
		BSTNode* getRoot() {
			return root;
		}

		/*将键值key插入到二叉树中*/
		void insert(int key);

		/*将结点插入到二叉树中*/
		void insert(BSTNode*& root, BSTNode* node);

		/*先序遍历*/
		void preOrder(BSTNode* root);

		/*中序遍历*/
		void inOrder(BSTNode* root);

		/*后序遍历*/
		void postOrder(BSTNode* root);

		/*查找二叉树中键值为key的结点并返回*/
		BSTNode* search(BSTNode* node, int key);

		/*找出二叉树中键值最小的结点并返回*/
		BSTNode* minimum(BSTNode* node);

		/*找出二叉树中键值最大的结点并返回*/
		BSTNode* maximum(BSTNode* node);

		/*找到二叉树结点node的后继结点*/
		BSTNode* successor(BSTNode* node);

		/*找到二叉树结点node的前驱结点*/
		BSTNode* predecessor(BSTNode* node);

		/*移除键值为key的结点*/
		BSTNode* remove(BSTNode*& root, int key);

		/*销毁二叉排序树*/
		void destroy(BSTNode* root);
};
/*
* 将结点插入到二叉树中
*
* 参数说明：
*     root 二叉树的根结点
*     node 要插入的结点
*/
void BSTree::insert(BSTNode*& root, BSTNode* node)
{
    BSTNode* y = NULL;
    BSTNode* x = root;

    /*找到要插入的位置*/
    while (x != NULL)
    {
        y = x;
        if (node->key > x->key)
            x = x->right;
        else x = x->left;
    }

    /*插入结点*/
    node->parent = y;
    if (y == NULL)
        root = node;
    else if(y->key > node->key)
        y->left = node;
    else y->right = node;
}

void BSTree::insert(int key) {
    BSTNode* node = new BSTNode(key, NULL, NULL, NULL);
    insert(root, node);
}
/*先序遍历*/
void BSTree::preOrder(BSTNode* root) {
	if (root != NULL) {
		cout << root->key;
		preOrder(root->left);
		preOrder(root->right);
	}
}
/*中序遍历*/
void BSTree::inOrder(BSTNode* root) {
	if (root != NULL) {
		inOrder(root->left);
		cout << root->key;
		inOrder(root->right);
	}
}
/*后序遍历*/
void BSTree::postOrder(BSTNode* root) {
	if (root != NULL) {
		postOrder(root->left);
		postOrder(root->right);
		cout << root->key;
	}
}
BSTNode* BSTree::search(BSTNode* node, int key) {
	if (node == NULL || node->key == key)
		return node;
	if (node->key < key)
		search(node->right, key);
	else search(node->left, key);
}
BSTNode* BSTree::minimum(BSTNode* node) {
	if (node->left == NULL)
		return node;
	minimum(node->left);
}
BSTNode* BSTree::maximum(BSTNode* node) {
	if (node->right == NULL)
		return node;
	maximum(node->right);
}
/*查找结点node的前驱节点*/
BSTNode* BSTree::predecessor(BSTNode* node) {
	/*（1）左子树非空，返回左子树最大值结点*/
	if (node->left != NULL)
		return maximum(node->left);

	/*（2）*/
	BSTNode* pnode = node->parent;
	while (pnode != NULL&&node == pnode->left) {
		node = pnode;
		pnode = pnode->parent;
	}
	return pnode;
}
/*查找node的后继结点*/
BSTNode* BSTree::successor(BSTNode* node) {
	/*（1）右子树非空，返回右子树最小值结点*/
	if (node->right != NULL)
		return minimum(node->right);

	/*（2）*/
	BSTNode* pnode = node->parent;
	while (pnode != NULL&&node == pnode->right) {
		node = pnode;
		pnode = pnode->parent;
	}
	return pnode;
}
/*获取要删除的结点并返回*/
BSTNode* BSTree::remove(BSTNode*& root, int key) {
	BSTNode* node = search(root, key);
	printf("%d\n", node->key);
	if (node != NULL) {
		if (node->left == NULL && node->right == NULL) {  //node为叶子结点
			if (node->parent == NULL)    //要删除的结点为根结点
				return node;
			else if (node->parent->left == node)//判断要删除点在双亲结点的左边还是右边
				node->parent->left = NULL;
			else
				node->parent->right = NULL;
		} else if (node->left == NULL) { //node左子树为空
			if (node->parent == NULL) { //要删除的结点为根结点
				this->root = node->right;
				node->right->parent = NULL;
			} else if (node->parent->left == node) //判断要删除点在双亲结点的左边还是右边
				node->parent->left = node->right;
			else
				node->parent->right = node->right;
		} else if (node->right == NULL) { //node右子树为空
			if (node->parent == NULL) {  //要删除的结点为根结点
				this->root = node->left;
				node->left->parent = NULL;
			} else if (node->parent->left == node) //判断要删除点在双亲结点的左边还是右边
				node->parent->left = node->left;
			else
				node->parent->right = node->left;
		} else {                        //node左右子树均不为空
			BSTNode* lnode = node->left;    //lnode初始为node左子树的根节点
			while (lnode->right)            //找到node左子树的最右结点赋值为lnode
				lnode = lnode->right;
			lnode->right = node->right;        //将node的右子树变成lnode的右子树
			node->right->parent = lnode;
			if (node->parent == NULL) { //要删除的结点为根结点
				this->root = node->right;
				if (node->right->left != NULL) {
					BSTNode* leftDownNode = minimum(node->right);
					leftDownNode->left = node->left;
					node->left->parent = leftDownNode;
				} else {
					node->right->left = node->left;
					node->left->parent = node->right;
				}
			} else if (node->parent->left == node) { //将node的左子树替换node的位置
				node->parent->left = node->left;
				node->left->parent = node->parent;
			} else if (node->parent->right == node) {
				node->parent->right = node->left;
				node->left->parent = node->parent;
			}
		}
	}
	return node;
}
/*销毁二叉树*/
void BSTree::destroy(BSTNode* root) {
	if (root == NULL)
		return;
	destroy(root->left);
	destroy(root->right);
	delete root;
}
int main() {
	int a[] = { 1, 5, 4, 3, 2, 6 };

	BSTree* tree = new BSTree();
	for (int i = 0; i < 6; i++)
		tree->insert(a[i]);

	cout << "先序遍历：";
	tree->preOrder(tree->getRoot());
	cout << endl;

	cout << "中序遍历：";
	tree->inOrder(tree->getRoot());
	cout << endl;

	cout << "后序遍历：";
	tree->postOrder(tree->getRoot());
	cout << endl;

	cout << "最小值：";
	BSTNode* minNode = tree->minimum(tree->getRoot());
	if(minNode != NULL)
		cout << minNode->key << endl;

	cout << "最大值：";
	BSTNode* maxNode = tree->maximum(tree->getRoot());
	if (maxNode != NULL)
		cout << maxNode->key << endl;


	BSTNode* node = tree->search(tree->getRoot(), 6);
	BSTNode* snode = tree->successor(node);
	if (snode != NULL)
		cout << snode->key << endl;

	BSTNode* pnode = tree->predecessor(node);
	if (pnode != NULL)
		cout << pnode->key << endl;

	BSTNode* root = tree->getRoot();
	BSTNode* dnode = tree->remove(root, 5);
	cout << "删除" << dnode->key << "后先序遍历：" << endl;
	if (dnode) delete dnode;
	tree->preOrder(tree->getRoot());
	cout << endl;

	cout << "销毁二叉树" << endl;
	tree->destroy(root);
	return 0;
}

二、

#include<bits/stdc++.h>
using namespace std;

// 定义一个二叉排序树结构：
typedef int DataType;
typedef struct BST_Node {
    DataType data;
    struct BST_Node *lchild, *rchild;
}BST_T, *BST_P;

//递归版查找 
BST_P Search_BST(BST_P root, DataType key)
{
    if (root == NULL)
        return NULL;
    if (key > root->data) //查找右子树  
        return Search_BST(root->rchild, key);
    else if (key < root->data) //查找左子树  
        return Search_BST(root->lchild, key);
    else
        return root;
}
//插入代码如下：
void Insert_BST(BST_P *root, DataType data)
{
    //初始化插入节点
    BST_P p = (BST_P)malloc(sizeof(struct BST_Node));
    if (!p) return;
    p->data = data;
    p->lchild = p->rchild = NULL;

    //空树时，直接作为根节点
    if (*root == NULL)
    {
        *root = p;
        return;
    }

    //是否存在，已存在则返回，不插入
    if (Search_BST(*root, data) != NULL) return; 

    //进行插入，首先找到要插入的位置的父节点
    BST_P tnode = NULL, troot = *root;
    while (troot)
    {       
        tnode = troot;
        troot = (data < troot->data) ? troot->lchild : troot->rchild;
    }
    if (data < tnode->data)
        tnode->lchild = p;
    else
        tnode->rchild = p;
}
//建立二叉排序树，用到Insert_BST方法
void CreateBST(BST_P *T, int a[], int n)
{
    int i;
    for (i = 0; i < n; i++)
    {
        Insert_BST(T, a[i]);
    }
}

// 查找最小关键字	
BST_P SearchMin(BST_P root)
{
    if (root == NULL)
        return NULL;
    if (root->lchild == NULL)
        return root;
    else  //一直往左孩子找，直到没有左孩子的结点  
        return SearchMin(root->lchild);
}
// 查找最大关键字	
BST_P SearchMax(BST_P root)
{
    if (root == NULL)
        return NULL;
    if (root->rchild == NULL)
        return root;
    else  //一直往右孩子找，直到没有右孩子的结点  
        return SearchMax(root->rchild);
}


//删除节点代码：
void DeleteBSTNode(BST_P *root, DataType data)
{
    BST_P p = *root, parent = NULL, s = NULL;

    if (!p) return;

    if (p->data == data) //找到要删除的节点了
    {
        /* It's a leaf node */
        if (!p->rchild && !p->lchild) 
            *root = NULL;

        // 只有一个左节点
        else if (!p->rchild&&p->lchild) 
            *root = p->lchild;

        // 只有一个右节点
        else if (!p->lchild&&p->rchild) 
            *root = p->rchild;

        //左右节点都不空
        else 
        {
            s = p->rchild;
            /* the s without left child */
            if (!s->lchild)
                s->lchild = p->lchild;
            /* the s have left child */
            else 
            {
                /* find the smallest node in the left subtree of s */
                while (s->lchild) 
                {
                    /* record the parent node of s */
                    parent = s;
                    s = s->lchild;
                }
                parent->lchild = s->rchild;
                s->lchild = p->lchild;
                s->rchild = p->rchild;
            }
            *root = s;
        }
        free(p);
    }
    else if (data > p->data) //向右找
        DeleteBSTNode(&(p->rchild), data);
    else if (data < p->data) //向左找
        DeleteBSTNode(&(p->lchild), data);
}

//先序遍历
void PreOrderTraverse(BST_P T)
{
    if (T)
    {
        cout << T->data << " ";
        PreOrderTraverse(T->lchild);
        PreOrderTraverse(T->rchild);
    }
}

//中序遍历

void MidOrderTraverse(BST_P T)
{
    if (T)
    {
        MidOrderTraverse(T->lchild);
        cout << T->data << " ";
        MidOrderTraverse(T->rchild);
    }
}
//后序遍历

void PostOrderTraverse(BST_P T)
{
    if (T)
    {
        PostOrderTraverse(T->lchild);
        PostOrderTraverse(T->rchild);
        cout << T->data << " ";
    }
}
int main()
{
    int arr[] = { 17,12,19,10,15,18,25,8,11,13,16,22};  

    BST_P root = NULL;

    //创建二叉排序树
    CreateBST(&root, arr, 12);
    printf("\nCreate BST: ");
    printf("\npre order traverse: ");
    PreOrderTraverse(root);
    printf("\npost order traverse: ");
    PostOrderTraverse(root);
    cout << endl;

    //在二叉排序树中查找节点12.
    BST_P result = Search_BST(root, 12);
    printf("\nSearch Data: ");
    cout << "查找结果：\n" << "指针：" << result << endl << "指针的值：" << result->data << endl;

    //在二叉排序树中插入9
    Insert_BST(&root, 9);
    printf("\nInsert Data: ");
    printf("\npre order traverse: ");
    PreOrderTraverse(root);
    printf("\npost order traverse: ");
    PostOrderTraverse(root);
    cout << endl;

    //删除二叉排序树中的节点12
    DeleteBSTNode(&root, 12);
    printf("\nDelete Data: ");
    printf("\npre order traverse: ");
    PreOrderTraverse(root);
    printf("\npost order traverse: ");
    PostOrderTraverse(root);
    printf("\n");
    return 0;
}

三、

#include<stdio.h>
#include<stdlib.h>
#define TRUE 1
#define FALSE 0
#define ElemType int
#define  KeyType int
/* 二叉排序树的节点结构定义 */
typedef struct BiTNode
{
    int data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

//二叉排序树查找算法
int SearchBST(BiTree T,KeyType key,BiTree f,BiTree *p){
    //如果 T 指针为空，说明查找失败，令 p 指针指向查找过程中最后一个叶子结点，并返回查找失败的信息
    if (!T){
        *p=f;
        return FALSE;
    }
    //如果相等，令 p 指针指向该关键字，并返回查找成功信息
    else if(key==T->data){
        *p=T;
        return TRUE;
    }
    //如果 key 值比 T 根结点的值小，则查找其左子树；反之，查找其右子树
    else if(key<T->data){
        return SearchBST(T->lchild,key,T,p);
    }else{
        return SearchBST(T->rchild,key,T,p);
    }
}
int InsertBST(BiTree *T,ElemType e){
    BiTree p=NULL;
    //如果查找不成功，需做插入操作
    if (!SearchBST((*T), e,NULL,&p)) {
        //初始化插入结点
        BiTree s=(BiTree)malloc(sizeof(BiTree));
        s->data=e;
        s->lchild=s->rchild=NULL;
        //如果 p 为NULL，说明该二叉排序树为空树，此时插入的结点为整棵树的根结点
        if (!p) {
            *T=s;
        }
        //如果 p 不为 NULL，则 p 指向的为查找失败的最后一个叶子结点，只需要通过比较 p 和 e 的值确定 s 到底是 p 的左孩子还是右孩子
        else if(e < p->data){
            p->lchild=s;
        }else{
            p->rchild=s;
        }
        return TRUE;
    }
    //如果查找成功，不需要做插入操作，插入失败
    return FALSE;
}
//删除函数
int Delete(BiTree *p)
{
    BiTree q, s;
    //情况 1，结点 p 本身为叶子结点，直接删除即可
    if(!(*p)->lchild && !(*p)->rchild){
        *p = NULL;
    }
    else if(!(*p)->lchild){ //左子树为空，只需用结点 p 的右子树根结点代替结点 p 即可；
        q = *p;
        *p = (*p)->rchild;
        free(q);
    }
    else if(!(*p)->rchild){//右子树为空，只需用结点 p 的左子树根结点代替结点 p 即可；
        q = *p;
        *p = (*p)->lchild;//这里不是指针 *p 指向左子树，而是将左子树存储的结点的地址赋值给指针变量 p
        free(q);
    }
    else{//左右子树均不为空，采用第 2 种方式
        q = *p;
        s = (*p)->lchild;
        //遍历，找到结点 p 的直接前驱
        while(s->rchild)
        {
            q = s;
            s = s->rchild;
        }
        //直接改变结点 p 的值
        (*p)->data = s->data;
        //判断结点 p 的左子树 s 是否有右子树，分为两种情况讨论
        if( q != *p ){
            q->rchild = s->lchild;//若有，则在删除直接前驱结点的同时，令前驱的左孩子结点改为 q 指向结点的孩子结点
        }else{
            q->lchild = s->lchild;//否则，直接将左子树上移即可
        }
        free(s);
    }
    return TRUE;
}
int DeleteBST(BiTree *T, int key)
{
    if( !(*T)){//不存在关键字等于key的数据元素
        return FALSE;
    }
    else
    {
        if( key == (*T)->data ){
            Delete(T);
            return TRUE;
        }
        else if( key < (*T)->data){
            //使用递归的方式
            return DeleteBST(&(*T)->lchild, key);
        }
        else{
            return DeleteBST(&(*T)->rchild, key);
        }
    }
}
void order(BiTree t)//中序输出
{
    if(t == NULL){
        return ;
    }
    order(t->lchild);
    printf("%d ", t->data);
    order(t->rchild);
}
int main()
{
    int i;
    int a[5] = {3,4,2,5,9};
    BiTree T = NULL;
    for( i = 0; i < 5; i++ ){
        InsertBST(&T, a[i]);
    }
    printf("中序遍历二叉排序树：\n");
    order(T);
    printf("\n");
    printf("删除3后，中序遍历二叉排序树：\n");
    DeleteBST(&T,3);
    order(T);
}

5、哈希表的概念

在面前讨论的各种结构（线性表、树）中，记录在结构中的相对位置是随机的，和记录的关键字之间不存在确定的关系，因此，在结构中查找记录时需进行一系列和关键字的比较。这一类查找方法建立在“比较”额基础上。在顺序查找时，比较的结果为“=”与“≠”两种可能；在折半查找、二叉排序树查找，比较的结果为“<”、“=”和“>”三种可能。查找的效率依赖于查找过程中所进行的比较次数。

理想的情况是希望不经过任何比较，一次存取便能得到所查记录，那就必须在记录的储存位置和它的关键字之间建立一个确定的对应关系f，使每个关键字和结构中一个唯一的储存位置相对应。因而在查找时，只要根据这个对应关系f找到给定值k得像f（k）。若结构中存在关键字和k相等的记录，则必定在f（k）的储存位置上，由此，不需要进行比较便可直接取得所查记录。在此，我们称这个对应关系f为哈希（Hash）函数，按这个思想思想建立的表为哈希表。

我们可以举一个哈希表的最简单的例子。假设要建立一张全国30个地区的各民族人口统计表，每个地区为一个记录，记录的各数据项为：

编号	地区名	总人口	汉族	回族	···

显然，可以用一个一维数组c（1:30）来存放这张表其中C[i]是编号i的地区的人口情况。编号i便于记录的关键字，由他唯一确定记录的储存位置C[i]。列如：假设北京市的各民族人口，只要取出C[1]的记录即可。假如把这个数组看成是哈希表f（key）=key。然而，很多情况下的哈希函数并不如此简单。可仍以此为例，为了查看方便应以地区名作为关键字。假设地区名以汉语拼音的方式表示，则不能简单地取哈希函数f(key)=key，而是首先要将它们转化为数字，有时还要作些简单的处理。列如我们可以有这样的哈希函数：（1）取关键字中第一个字母在字母表中的序号作为哈希函数。列如：BEIJNG的哈希函数：

（1）取关键字中第一个字母在字母表中的序号作为哈希函数。列如:BEIJING的哈希函数值为字母“B”在字母表中的序号，等于02:；

（2）先求关键字的第一个和最后一个字母在字母表中的序号之和，然后判别这个和值，若比30（表长）大，则减去30.列如:TIANJIN的首尾两个字母“T”和“N”的序号之和为34，故取04为他它的哈希函数值；或

（3）先求每个汉字的第一个字母的ASCII码（和英文字母相同）之和的八进制形式，然后将这个八进制数看成是十进制再除以30取余数，若余数为零再加上30而为哈希函数值。

例如：HENAN的两个拼音字母为“H”和“N”，他们的ASCII码之和为（266），以（266）除以（30）的余数为16，则16为HENAN的哈希函数值。上述人口统计部分关键字在这三种不同的哈希函数情况下的哈希函数值如表下图所列：

从这个例子可见：

（1）哈希函数一个映像，因此哈希函数的设定很灵活，只要是的任何关键字由此所得的哈希函数值都落在表长允许范围之类即可；

对不同的关键字可能得到同一哈希地址，即key≠key2面f（key1）=f（key2）这种现象称冲突（collision）。具有相同函数值的关键词对该哈希函数来说乘坐同义词（synonym）。例如：关键词HEBEI和HENAN不等，但f1（HEBEI）=f1（HENAN）,又如：f2（SHANGHAI）:f3（HENAN）==f3（SICHUAN）.这种现象给建造成困难，如在第一种哈希函数的情况下，因为山西，上海，山东和四川这四个记录的哈希地址均为19而C[19]只能存放一个记录，那么其他三个记录存放在表中的什么位置呢？并且，从上表三个不同的哈希函数的情况下就可以看出，哈希函数选的合适可以减少这种突发情况。特别是在这个例子中。只可能有30个记录，可以仔细分析这30个关键词的特性，选择一个恰当的哈希函数来避免冲突的发生。

一、哈希函数的构造方法

构造哈希函数的方法撒很多。在介绍各种方法之前，首先需要明确什么是“好”的哈希函数。

若对于关键字集合中的任何一个关键字，经哈希函数映像到地址集合中任何一个地址的概率是相等的。则称此类哈希函数为均匀的（Uniform）哈希函数。换句话说，就是是关键字经过哈希函数得到一个“随机的地址”，以便使一组关键字的哈希地址均匀分布在整个地址区间中，从而减少冲突。

常用的构造哈希函数的方法有：

1. 直接定址法

取关键字或关键字的某个线性函数值为哈希地址。即：

H(Key)=key或（key）=a*key+b

其中a和b为常数（这种哈希函数叫做自身函数）。

例如：有一个从1岁到100岁的人口数字统计表，其中，年龄作为关键字，哈希函数取关键字自身。如表9.2所示

地址	01	02	03	.。。。	25	26	27	。。。	100
年龄	1	2	3	。。。	25	26	27	。。。	.。。。
人数	3000	2000	5000	。。。	1050	。。。	.。。。	。。。	。。。
。。。

表1直接定址哈希函数例之一

这样，若要询问25岁的人有多少，则只要查询的第25项即可。又如：有一个解放后出生的人口调查表，关键字是年份，哈希函数取关键字加一常数：

H（key）=key+（-1948），如表9.3所示。

地址	01 02 03 …. 22 …
年份	1949 1950 1951 …. 1970 ……
人数	…. …… …… …. 15000 ….
….

表2直接定址哈希函数例之二

这样，若要查1970年出生的人数，则只要查第）（1970-1948）=22项即可。由于直接定址所得地址集合关键词集合的大小相同。因此，对于不同的关键词不会发生冲突。但实际中能用这种哈希函数的情况很少。

2. 数字分析法

假设关键字是以r为基的数（如：以10为基的十进制数）。，并且哈希表中可能出现的关键字都是事先知道的，则可取关键字的若干数位组成哈希地址。例如有80个记录，其关键字为8位十进制数。假设哈希的表长为10010，则可无取两位十进制数组成哈希地址。取哪两位?原则是使得到的哈希地址尽量避免产生冲突，则需从分析这80个关键字着手。假设这80个关键字中的一部分如下所列：

对关键字全体的分析中我们发现第1,2 位都是“8，,1”，第三位3或4，第8位只可能取2，5,7，因此这四位数都不可取。由于中间的四位数可看成是近乎随机的，因此可取其中任意两位，获取其中两位与另外两位的叠加求和后舍去进位作为哈希地址。

1. 平方取中法：

取关键字平方后的中间几位为哈希地址。这是一种较常见的构造哈希函数的方法。

通常在选定哈希函数时不一定能知道关键最的全部情况，去其中哪几位也不一定合适，而一个数平方后的中间几位数的每一位都想关，由此使随机分布的关键字得到的哈希地址也是随机的。取的位数由表长决定。

例如：为BASIC源程序中的标识符建立一个哈希表。假设BASIC语言中允许的标识符为一个字母，或一个子母和一个数字，在计算机内可用两位八位进制数表示字母和数字。取标识符在计算机中的八进制数为它的关键字。假设表长为512=29.则可取关键字平方后的中间9二进制数为哈希地址。例如下图列出了一些标识符及它们的哈希地址。

A B C … Z 0 1 2 … 9

01 02 03 32 60 61 62 71

1. 除留余数法

取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址。即

H（key）=key MOD p p< m（一般取小于m的最大质数

这是一种最简单，也最常用的构造哈希函数的方法。他不仅可以对关键字直接取摸（MOD），也可以在折迭、平方取中等运算之后取摸。值得注意的是，在使用除留余数法时，对p的选择很重要。若p选的不好，容易产生同义词。

二、处理冲突的方法

在“第一小节什么是哈希表”中曾提及均匀的哈希函数可以减少冲突，但不能避免，因此，如何处理冲突是哈希表不可缺少的另一方面。

假设哈希表的地址集为0~（n-1），冲突是指由关键字得到的哈希地址为j（0≤j≤n-1）的位置上已存有记录，则“处理冲突”就是为该关键字的记录找到另一个“空”的哈希地址。

在处理冲突的过程中可能得到一个地址序列Hi i=1，2，…，k，（Hi∈[0，n-1]。

即在处理哈希地地址的冲突时，

若得到的另一个哈希地址Hi仍然发生冲突，则再求下一个地址H2 若H2仍然冲突，再求得H3. 以此类推，直至Ha不发生冲突为止，则Ha为记录在表中的地址。

通常用的处理冲突的方法有下列几种：

1. 开放定址法

Hi=（H（key）+di）MODm i=1,2，…， k（k≤M-1）其中：h（key）为哈希函数；m为哈希表表长；di为增量序列，可有下列三种取法:

di=1,2,3，…，m-1，呈线性探测在散列；

例如，在长度为11的哈希表中一填中有关键字分别为17,60,29的记录（哈希函数H（key）=key MOD11），现有第四个记录，其关键字为38 由哈希函数得到哈希地址为5，产生冲突。若用线性探测在散列的方法处理时

，得到下一个地址6，扔冲突：再求下一个地址7仍冲突

；直到哈希地址为8的位置为“空”时止处理冲突的过程结束，

记录填入哈希表中序列为8的位置。若用二次探测在散列，则应该填入序号为4的位置类似地可得到伪散列，则应该填入序号为4的位置。类似地可得到伪序列再散列的位置。

2. 再哈希法

i=1,2,…,k

RHi均是不同的哈希函数，即在同义词产生地址冲突时计算另一个哈希函数的地址，直到冲突不再发生。这种方法不易产生“聚集”，但增加了计算的时间。

注：会产生空隙

三、哈希表的查找及分析

在哈希表上进行查找的过程跟哈希造表过程基本一致，给定K值，根据造表时设计的哈希函数计算出哈希地址，若此位置上没有记录，则查找不成功；否则比较关键字若与给定的关键字相同，则查找成功。否则根据造表时处理冲突的方法找“下一地址”，直至哈希表中某个位置为空，或者表中所填记录的关键字与给定的关键字相等为止。

已知如图所示一组关键字按哈希函数H（key）=key MOD 13和线性探测处理冲突，构造所得的哈希表。

例如查找关键字84，H(84)=6,去6查看发现该单元格不空，但是不等于84，采用线性探测处理冲突则去下一位位置7查找，发现不空也不等于84，则再线性探测去8单元格找，不空恰好等于84，则查找成功，查找次数为3。

其他元素依次类推，可得到平均的查找长度（ASL）：

综上所述，一般情况，查找的平均长度与三个因素相关：

1、哈希函数

2、处理冲突的方法

3、装填因子

哈希表的装填因子定义为：

的值越小，发生冲突的概率越小，反正越大，表中填入的记录越多，在填入的时候发生冲突的可能性就越大，在进行查找时候，查找的次数也就越多。

四、代码哈希表的实现

#include <stdio.h>
#include <memory.h>
#include <string.h>
#include <stdlib.h>

#define HARSH_TABLE_MAX_SIZE   (1000) // 哈希数组的最大元素个数

typedef struct HarshNode_struct HarshNode;

// 定义一个哈希表的节点
struct HarshNode_struct {
	char * sKey;   // [sKey,nvalue]是一对键值对
	int nValue;
	HarshNode *pNext;
};

HarshNode * harshTable[HARSH_TABLE_MAX_SIZE]; // 哈希表数组
unsigned int g_harsh_table_size = 0x0;



//初始化哈希表
void harsh_table_init(void) {
	int i = 0x0;
	memset(harshTable,0,sizeof(HarshNode *)*HARSH_TABLE_MAX_SIZE);
	g_harsh_table_size = 0x0;

}


// 将字符给变成hashcode
unsigned int harsh_table_harsh_string(const char * sKey) {
	const unsigned  char* p =  (const unsigned  char*) sKey;
	unsigned int value = *p;

	if(value) {
		for( p += 1; *p != '\0'; p++) {
			value = (value << 5) - value + *p;
		}
	}

	return value;

}


//根据键值对向哈希表中添加节点，如果skey已经存在则直接更新键值nValue
//添加成功返回0，添加失败返回-1
int harsh_table_insert_node(const char * sKey, int nValue) {
	HarshNode * pHarshNodeHead   = NULL;
	HarshNode * pNewNode = NULL;
	unsigned int pos = 0x0;

	if((g_harsh_table_size >= HARSH_TABLE_MAX_SIZE )||(NULL  == sKey))
		return -1;

	pos =  harsh_table_harsh_string(sKey) % HARSH_TABLE_MAX_SIZE; //用这种方法计算sKey在哈希数组中对应的位置

	printf("skey在哈希表中的位置 : pos = %d\n",pos);

	pHarshNodeHead = harshTable[pos];

	if(NULL == pHarshNodeHead)
		printf("最后空指向头指针:NULL == pHarshNodeHead\n");

	while(NULL != pHarshNodeHead ) { // 如果这个位置对应的不是这一串中最后一个节点的话，那就要向后移动了
		if(strcmp(pHarshNodeHead->sKey,sKey) == 0) { //如果这个键值对已经存在，只更新键值即可
			pHarshNodeHead ->nValue = nValue;

			return 0;
		}

		pHarshNodeHead = pHarshNodeHead->pNext;  //向后移动,肯定会有NULL的时候

	}

	pNewNode = (HarshNode *)malloc(sizeof(HarshNode)); //申请一块HarshNode 大小的内存
	if(NULL == pNewNode) {
		return -1;
	}
	memset(pNewNode,0,sizeof(HarshNode));

	pNewNode ->sKey = (char *)malloc(strlen(sKey) + 1); //申请一块sKey大小的内存
	if(NULL == pNewNode ->sKey ) {
		return -1;
	}
	memset(pNewNode ->sKey,0,strlen(sKey) + 1);

	strcpy(pNewNode ->sKey,sKey); //将sKey的内容赋给 pNewNode -> sKey
	pNewNode ->nValue = nValue; //键值也复制过来

	pNewNode ->pNext = NULL; //由于是新节点，也是尾节点，所以pNext指向NULL

	pHarshNodeHead  = pNewNode;
	harshTable[pos] = pHarshNodeHead; //最后一定要让数组中的这个位置指向这个头指针

	g_harsh_table_size ++;

	return 0;


}


//打印数组中对应的某个位置的那一串哈希值
void print_harsh_node(int pos) {
	HarshNode * pHarshNodeHead   = NULL;

	if(pos >= HARSH_TABLE_MAX_SIZE)
		return;

	pHarshNodeHead = harshTable[pos];

	if(NULL == pHarshNodeHead)
		printf("NULL == pHarshNodeHead\n");
	while(NULL != pHarshNodeHead) {
		printf("位置:%d, sKey:%s, nValue:%d \n",pos,pHarshNodeHead->sKey,pHarshNodeHead->nValue);
		pHarshNodeHead = pHarshNodeHead->pNext;

	}


}

// 根据键值sKey来查找对应的哈希节点
HarshNode * harsh_table_lookup(const char *sKey) {
	unsigned int pos = 0x0;
	HarshNode * pHarshHead = NULL;

	if(NULL == sKey) {
		return NULL;
	}

	pos = harsh_table_harsh_string(sKey) % HARSH_TABLE_MAX_SIZE; //计算出在哈希数组中的位置

	pHarshHead = harshTable[pos];

	while(NULL != pHarshHead) {
		if(strcmp(sKey,pHarshHead->sKey) == 0)//找到了
			return pHarshHead;

		pHarshHead = pHarshHead->pNext; // 没有找到的话来到下一个节点
	}

	return NULL;

}


int main() {
	char * pSkey = "abcd";
	int nValue = 1234;
	int ret = -1;
	int pos = 0xffffffff;
	HarshNode * pHarshNode = NULL;

	harsh_table_init();
	ret = harsh_table_insert_node(pSkey,nValue);

	printf("ret = %d\n",ret);


	if(!ret) {
		pos = harsh_table_harsh_string(pSkey) % HARSH_TABLE_MAX_SIZE;
		printf("main:  pos = %d\n",pos);
		print_harsh_node(pos);
	}

	pHarshNode = harsh_table_lookup(pSkey);

	if(NULL != pHarshNode) {
		printf("最终值: sKey:%s, nValue: %d\n",pHarshNode->sKey,pHarshNode->nValue);
	}
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2021-01-30，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

二叉树

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

二叉树