目录

基本概念

静态查找：

动态查找：

线性结构

顺序查找

折半查找

分块查找

树形结构

二叉排序树

平衡二叉树

红黑树

B树

散列表

散列函数的构造方法

处理冲突的方法 

---

基本概念

静态查找：

在静态查找表上进行的查找操作，查找满足条件的数据元素的储存位置或者各种属性。

静态查找有三种查找方式：顺序查找、折半查找和散列查找。

动态查找：

需动态的插入或删除的查找表。

查找方式有：二叉排序树查找和散列查找，二叉排序树和B树都是二叉排序树的改进。

线性结构

顺序查找

顺序查找又称线性查找，顾名思义，就是按顺序依次查找元素。对顺序表和链表都适用。

typedef int ElemType;
typedef struct{
	ElemType *elem;//整形指针
	int TableLen; //存储动态数组元素个数 
}SSTable;
 
int Search_Seq(SSTable ST,ElemType key){
	ST.elem[0]=key;//作为哨兵 
	int i;
	for(i=ST.TableLen-1;ST.elem[i]!=key;--i);
	return i;
}

折半查找

又称二分查找，仅适用于有序顺序表。顾名思义，每次查找都拿中间元素比较。

int Binary_Search(SSTable L,ElemType key){
	int low=0,high=L.TableLen-1,mid;
	while(low<=high){
		mid=(low+high)/2;
		if(L.elem[mid]==key){
			return mid;
		}
		else if(L.elem[mid]>key){
			high=mid-1;
		}else{
			low=mid+1;
		}
	}
	return -1;
}

分块查找

又称索引顺序查找，吸收了顺序查找和折半查找的优点，既有动态结构，又适用于快速查找。

主要思想：将查找表分为若干块，块内元素可以无序，但块之间是有序的，即第一块最大的关键字（元素）小于第二个块中所有关键字。在建立一个索引表，索引表中包括各块最大关键字和各块第一个元素地址，索引表按关键字有序排列。

查找过程：第一步查找所在块，可以顺序或折半查找索引表。第二步在块内顺序查找。

树形结构

二叉排序树

又称二叉查找树，核心思想：左子树值<根节点值<右子树值，所以对其进行中序遍历，可以得到递增有序序列。1 2 3 4 6 8

//结构定义 
typedef int KeyType;
typedef struct BSTNode{
	KeyType key;
	struct BSTNode *lchild,*rchild;
}BSTNode,*BiTree;
 
//插入 
int BST_Insert(BiTree &T,KeyType k){
	if(T==NULL){
		T=(BiTree)malloc(sizeof(BSTNode));
		T->key=k;
		T->lchild=T->rchild=NULL;
		return 1;//插入成功 
	}
	else if(k==T->key){
		return 0;//发现相同元素，不插入 
	}
	else if(kkey){
		return BST_Insert(T->lchild,k);
	}
	else{
		return BST_Insert(T->rchild,k);
	}
	
}
//建表 
void Create_BST(BiTree &T,KeyType str[],int n){
	T=NULL;
	int i=0;
	while(i
		BST_Insert(T,str[i]);
		i++;
	}
}
//中序 
void InOrder(BiTree T){
	if(T!=NULL){
		InOrder(T->lchild);
		printf("%3d",T->key);
		InOrder(T->rchild);
	}
}
//查找 
BSTNode *BST_Search(BiTree T,KeyType key,BiTree &p){
	p=NULL;
	while(T!=NULL&&key!=T->key){
		p=T;
		if(keykey)
			T=T->lchild;//比当前结点小，往左找
		else
			T=T->rchild;//反之往右 
	}
	return T; 
}
//删除 
void DeleteNode(BiTree &root,KeyType x){
	if(root==NULL){
		return;
	}
	if(root->key>x){
		DeleteNode(root->lchild,x);
	}else if(root->key
		DeleteNode(root->rchild,x);
	}else{//找到了 
		if(root->lchild==NULL){//左子树为空 
			BiTree tempNode=root;
			root=root->rchild;
			free(tempNode);
		}else if(root->rchild==NULL){//右子树为空 
			BiTree tempNode=root;
			root=root->lchild;
			free(tempNode);
		}else{//左右子树非空 
			BiTree tempNode=root->lchild;
			if(tempNode->rchild!=NULL){
				tempNode=tempNode->rchild;
			}
			root->key=tempNode->key;
			DeleteNode(root->lchild,tempNode->key);
		}
	}
} 

平衡二叉树

简称平衡树。特点：左右子树高度差绝对值不超过1。因此平衡因子可能为-1,0,1。

平衡二叉树详解 通俗易懂_邓嘉文Jarvan的博客-CSDN博客_平衡二叉树

红黑树

漫画：什么是红黑树？（整合版）_程序员小灰的博客-CSDN博客

B树

又称多路平衡查找树

B树和B+树_ZJE_ANDY的博客-CSDN博客_b树的阶数

什么是B-树？（详细图解）_初念初恋的博客-CSDN博客_b-树

B-树的详解_Ouyang_Lianjun的博客-CSDN博客_b-树

散列表

散列函数：一个把查找表中的关键字映射成该关键字对应的地址函数，记为Hash(key)=Addr,这里地址可以是数组下标，索引或内存地址。

冲突：把两种或两种以上不同关键字映射到同一地址。

同义词：发生碰撞的不同关键字。

散列表：根据关键字而直接访问的数据结构。（散列表建立了关键字和存储地址之间的直接映射关系）

散列函数的构造方法

1.直接定址法

H（key）=key或H（key）=a*key+b,a和b为常数

2.除数留余法

H（key）=key%p，p为不大于表长但最接近表长的质数

3.数字分析法

4.平方取中法

处理冲突的方法 

1.开放定址法

 其中增量取法有四种，分别为线性探测法，平方探测法，双散列法和伪随机序列法。

详细增量取法请看下面的链接，写的比较详细。

散列表（开放定址法）_时代&信念的博客-CSDN博客_开放定址法

2.拉链法

 下面是一个示例代码，仅供参考。

int hash(const char* key)
{
	int h = 0, g;
	while (*key)
	{
		h = (h << 4) + *key++;
		g = h & 0xf0000000;
		if (g)
		{
			h ^= g >> 24;
		}
		h &= ~g;
	}
	return h % MaxKey;//算出下标要取余
}
 
int main()
{
	const char* pStr[5] = { "xiongda","lele","hanmeimei","wangdao","fenghua" };
	int i;
	const char* pHash_table[MaxKey] = {NULL};//哈希表，散列表
	for (i = 0; i < 5; i++)
	{
		printf("%s is key=%d\n", pStr[i], hash(pStr[i]));//算哈希值并打印
		pHash_table[hash(pStr[i])] = pStr[i];//存入哈希表
	}
	return 0;
}