223 lines
5.2 KiB
Markdown
223 lines
5.2 KiB
Markdown
# 原创
|
||
： 第九章 查找
|
||
|
||
# 第九章 查找
|
||
|
||
## 一、基础知识点
|
||
|
||
### 1.基本概念
|
||
|
||
>
|
||
|
||
|
||
|
||
### 2.顺序查找法
|
||
|
||
>
|
||
思路：从表的一端开始，顺序扫描线性表，依次扫描到的关键字和给定值k比较
|
||
|
||
|
||
```
|
||
//数组a[]有n个元素，没有次序，数组从下标1开始存储，写出查找元素k的算法
|
||
int Search(int a[],int n,int k)
|
||
{
|
||
int i;
|
||
for(i=1;i<=n;++i)
|
||
{
|
||
if(a[i]==k)return i;
|
||
}
|
||
return 0;
|
||
}
|
||
//查找成功----ASL分析：ASL=(1/n)*n*(1+n)/2=(n+1)/2,时间复杂度O(n);
|
||
//查找失败----ASL分析：ASL=n,时间复杂度O(n);
|
||
```
|
||
|
||
### 3.折半查找法
|
||
|
||
>
|
||
**思路：** <br/> 1.要求线性表**有序**，设R[low, … ,high]是当前查找区间，mid = ( low / high ) / 2； <br/> 2.将待查找k与R[mid]进行比较，相等则查找成功，返回mid，失败则确定新查找区间； <br/> 3.R[mid] > k，则high = mid - 1；若R[mid]
|
||
|
||
|
||
```
|
||
//数组从下标1开始存储
|
||
int HalfSearch(int R[],int low,int high,int k)
|
||
{
|
||
int mid;
|
||
while(low<=high)
|
||
{
|
||
mid=(low+high)/2;
|
||
if(R[mid]==k)return mid;
|
||
else if(R[mid]>k)high=mid-1;
|
||
else low=mid+1;
|
||
}
|
||
return 0;
|
||
}
|
||
```
|
||
|
||
>
|
||
|
||
|
||
|
||
### 4.分块查找
|
||
|
||
>
|
||
|
||
|
||
|
||
```
|
||
//索引表定义
|
||
typedef struct
|
||
{
|
||
int key;
|
||
int low,high; //记录块内第一个和最后一个元素位置
|
||
}indexElem;
|
||
indexElem index[maxSize]; //定义索引表
|
||
```
|
||
|
||
>
|
||
**算法描述：** <br/> 首先确定待查找元素的块，采用二分法查找；块内元素较少，直接用顺序查找； <br/> 平均查找长度 = 二分法查找平均长度 + 顺序查找平均查找长度；
|
||
|
||
|
||
## 二、二叉排序树与平衡二叉树
|
||
|
||
### 1.二叉排序树
|
||
|
||
>
|
||
|
||
|
||
|
||
**基本算法：**
|
||
|
||
```
|
||
//1.查找关键字算法
|
||
//与这折半查找的二叉树类比,很简单
|
||
BTNode *BSTSearch(BTNode *bt,int key)
|
||
{
|
||
if(bt==NULL)return NULL;
|
||
else
|
||
{
|
||
if(bt->key==key)return bt;
|
||
else if(bt->key>key)return BSTSearch(bt->lchild,key);
|
||
else if(bt->key<key)return BSTSearch(bt->rchild,key);
|
||
}
|
||
}
|
||
|
||
//2.插入关键字的算法
|
||
//注意BST是一个查找表，对于一个不存在于二叉排序树中的关键字，查找不成功的位置即为需要将关键字插入的位置
|
||
int BSTInsert(BTNode *&bt,int key)//由于二叉树需要改变，所以用引用，绪论里说过
|
||
{
|
||
if(bt==NULL)//空指针即为找到关键字插入位置
|
||
{
|
||
bt=(BTNode*)malloc(sizeof(BTNode));
|
||
bt->lchild=bt->rchild=NULL;
|
||
bt->key=key;
|
||
return 1;
|
||
}
|
||
else
|
||
{
|
||
if(key==bt->key)return 0;//关键字存在二叉树中，插入1失败
|
||
else if(key<bt->key)return BSTInsert(bt->lchild,key);
|
||
else if(key>bt->key)return BSTInsert(bt->rchild,key);
|
||
}
|
||
}
|
||
|
||
//3.二叉排序树的构造算法
|
||
//建立一棵空树，直接逐个插入即可
|
||
void CreatBST(BTNode *&bt, int key[], int n)
|
||
{
|
||
int i;
|
||
bt=NULL;
|
||
for(i=0;i<n;++i)BSTInsert(bt,key[i]);
|
||
}
|
||
|
||
//4.删除关键字操作
|
||
/*
|
||
1.p结点为叶子结点
|
||
2.p结点只有右子树或者只有左子树
|
||
3.p结点有左右子树，为保证二叉排序树的成立条件（输出的中序遍历有序）
|
||
遍历p左子树的右指针，直到到达最右边的结点r（或者遍历p右子树的左指针，直到到达最左边的结点）
|
||
p的关键字用r的关键字(相当于删除p),然后处理多出来的r，删除方式就按1，2情况处理。
|
||
*/
|
||
//具体算法严版书上有P230页
|
||
|
||
//5.判断一棵二叉树是否为二叉排序树(结点值为int型)
|
||
//思路：利用二叉排序树BST的中序遍历为递增序列的性质，对该二叉树进行中序遍历即可
|
||
int predt=INF;//INF为已知常量，小于任何树中结点值，predt始终记录当前结点的前驱结点的值
|
||
int judgeBST(BTNode *bt)
|
||
{
|
||
int b1,b2;
|
||
if(bt==NULL)return1;//空BST
|
||
else
|
||
{
|
||
b1=judgeBST(bt->lhild);
|
||
if(b1==0||predt > bt->date)return 0;
|
||
predt=bt->date;
|
||
b2=judgeBST(bt->rchild);
|
||
return b2;
|
||
}
|
||
}
|
||
```
|
||
|
||
### 2.平衡二叉树
|
||
|
||
>
|
||
|
||
|
||
|
||
## 三、B-树和B+树
|
||
|
||
### 1.基本概念
|
||
|
||
>
|
||
|
||
<table><thead><th align="center">n</th><th align="center">k1</th><th align="center">k2</th><th align="center">…</th><th align="center">kn</th>
|
||
</thead><tbody><td align="center">p0</td><td align="center">p1</td><td align="center">p2</td><td align="center">…</td><td align="center">pn</td>
|
||
</tbody></table>
|
||
|
||
|
||
### 2.基本操作
|
||
|
||
### 3.B+树
|
||
|
||
>
|
||
|
||
|
||
|
||
## 四、散列表
|
||
|
||
### 1.基本概念
|
||
|
||
>
|
||
|
||
|
||
|
||
### 2.Hash表建立以及冲突解决
|
||
|
||
>
|
||
|
||
|
||
|
||
### 3.常用Hash函数构造方法
|
||
|
||
>
|
||
|
||
|
||
|
||
### 4.常用的Hash冲突处理方法
|
||
|
||
>
|
||
|
||
|
||
|
||
### 5.散列表的性能分析
|
||
|
||
>
|
||
|
||
<table><thead><th align="right">解决冲突的方法</th><th align="center">查找成功时</th><th align="left">查找不成功时</th>
|
||
</thead><tbody><td align="right">线性查找法</td><td align="center">`[1+1/(1-a)]/2`</td><td align="left">`[1+1/(1-a)^2]/2`</td>
|
||
<td align="right">平方探查法</td><td align="center">`-(1/a)ln(1-a)`</td><td align="left">`1/(1-a)`</td>
|
||
<td align="right">链地址法</td><td align="center">`1+a/2`</td><td align="left">`a+e^a≈a`</td>
|
||
</tbody></table>
|
||
**特别注意链地址法的ASL2求法**
|
||
|