查找:就是根据给定的某个值,在查找表中确定一个其关键字等于给定值的数据元素(或记录)
查找表按照操作方式分为两大种:静态查找表和动态查找表.
静态查找表:只做查找操作的查找表.它的主要操作有:
1.查询某个'特定的'数据元素是否在查找表中
2.检索某个'特定的'数据元素和各种属性
动态查找表:在查找过程中同时插入查找表中不存在的数据元素,或者从查找表中删除已经存在的某个数据元素.注意操作:
1.查找时插入数据元素
2.查找时删除数据元素
2.顺序表查找
顺序查找又叫线性查找,是最基本的查找技术,它的查找过程是:从表中第一个(或最后一个)记录开始,逐个进行记录的关键字和给定值比较,若某个记录的关键字和给定值相等,则查找成功,找到所查的记录;如果直到最后一个(或第一个)记录,其关键字和给定值比较都不等时,则表中没有所查的记录,查找不成功
查找表算法:
//顺序查找,a为数组,n为要查找的数组个数,key为要查找的关键字
int Sequential_Search(int *a,int n,int key){
int i;
for (i = i; i <= n; i++){
if (a[i] == key)
return i;
}
return 0;
}
顺序表查找优化
设置哨兵,可以解决每次让i与n作比较
int Sequetial_Search2 (int *a,int n,int key){
int i;
a[0] = key;//设置a[0]为关键字,我们称为"哨兵"
i = n;//循环从数组尾部开始
while(a[i] != key){{
i--;
}
return i ;//返回0则说明查找失败
}
顺序查找技术有很大的缺点,n很大事,查找效率极为低下,优点是,算法简单,对静态查找表的记录没有任何要求,在一些小型数据的查找,也是可以适用的
3.有序表查找
1.折半查找
折半查找技术,又称为二分查找,他的前提是线性表中的记录必须是关键码有序(通常从小到达有序),线性表必须采用顺序存储.折半查找的基本思想是:在有序表中,取中间记录作比较对象,若给定值与中间记录的关键字相等,则查找成功;若给定值小于中间记录的关键字,则在中间记录的关键字,则在中间记录的左半区继续查找;若给定值大于中间记录的关键字,则在中间记录的右半区继续查找.不断重复上述过程,直到查找成功,或所有查找区域无记录,查找失败为止.
有序表数组{0,1,16,24,35,47,59,62,73,88,99},除0下标外共10个数字对它进行查找是否存在62这个树
//折半查找
int Binary_Search (int *a, int n ,int key){
int low,high,mid;
low = 0;//定义最低下标为记录首位
high = n;//定义最高下标为记录末位
while(low <=hight){
mid = (low + high) / 2;//折半
if (key < a[mid])//若查找值比中指小
high = mid - 1;//最高下标调整到中位下标小一位
else if (key > a[mid])//若查找值比中值大
low = mid + 1;//最低下标调整到中位下标大衣位
else
return mid;//若相等则说明mid即为查找到的位置
}
return 0;
}
1.程序开始运行,参数a={0,1,16,24,35,47,59,62,73,88,99},n=10,key= 62,第3~5行,此时low-1,high = 10
2.mid = (0+ 10) / 2 = 5,a[5] =47 < key,所以执行第12行 low = 5+1 = 6
3.mid = (6+ 10)/2 = 8,a[8] = 73> key,所以执行第10行,high= 8 - 1= 7
4.mid =(6 + 7)/ 2 = 6 ,a[6] = 59< key,执行第12行.low = 6+1=7
2.插值查找
你一定会想,为什么非得折半,为什么不可以四分之一或者更多那.这一点算法数学家已经考虑了,而且还改进了折半查找的算法
折半查找代码的第八句,我们使用等式变换后得到:
mid = (low + high) / 2 = low + 1 * (hight - low)/ 2,算法数学家将1/2进行改进,得到
........啥,,你问我怎么改的,来,过来~,靠近点,看我不打死你,这样就没人知道我也不会了
那现在不问了吧,咱们接着往下扯,呸~咱们接着往下学
//插值查找
int Interpolation_Search (int *a, int n ,int key){
int low,high,mid; low = 0;//定义最低下标为记录首位
high = n;//定义最高下标为记录末位
while(low <=hight){
**mid = low +( key - a[low]) * (high - low) /a[high] - a[low];**//插值查找
if (key < a[mid])//若查找值比中指小
high = mid - 1;//最高下标调整到中位下标小一位
else if (key > a[mid])//若查找值比中值大
low = mid + 1;//最低下标调整到中位下标大衣位
else
return mid;//若相等则说明mid即为查找到的位置
}
return 0;
}
3.斐波那契查找
斐波那契查找,利用黄金分割的原来来实现的,黄金分割哦~
提起斐波那契数列,一定会想到那个经典的兔子生兔子的命题,就不详细介绍了
//斐波那契查找
int Fibonacci_Search(int * a, int n , int key){
int low, high, mid, i, k;
low = 0;//定义最低下标为记录首位
high = n;//定义最高下标为记录首位
k = 0;
while (n > F[k] - 1) //计算n位于斐波那契数列的位置
k++;
for (i= n;i : F[k] - 1; i++)//将不满的数值补全
a[i] = a[n];
while (low <= high){
mid = low + F[k - 1] - 1;计算当前分隔的下标
if (key < a[mid]){ //若查找记录小于当前分隔记录
high = mid - 1; //最高下标调整到分隔下标mid - 1处
k =k - 1;//斐波那契数列下标-1
}
else if(key > a[mid]){ //若查找记录大于当前分隔记录
low = mid + 1;//最低下标调整到分隔下标+ 1处
k = k + 2;
}else{
if (mid < = n) {
return mid; //若相等则说明mid即为查找到的位置
}else{
return n;//若mid > n,说明是补全数组,返回n
}
}
}
return 0;
}
4.二叉排序树
对集合{21,28,14,32,25,18,11,30,19,15}做查找,我们打算创建此集合时就考虑二叉树结构,而且是排序好的二叉树,集合的第一个元素21,做根结点,比他小的为左子树,大的为右子数
我们对他进行中序遍历,即可得到一个有序的序列{11,14,15,19,18,21,25,28,30,32},所有我们通常称他为二叉排序树
二叉排序树,又称为二叉查找树.它或者是一棵空树,或者是具有下列性质的二叉树
- 1.若它的左子树不空,则左子树上所有结点的值均小于它的根结构的值
- 2.若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值
- 3.它的左,右子树也分别为二叉排序树
左子树结点一定比其双亲结点小,右子树结点一定比其双亲结点大
5.二叉排序树查找操作
//二叉树定义
typedef struct BitNode //结点结构
{
int data; //结点数据
struct BitNode *lchild,*rchild;//左右孩子指针
}BitNode , *BiTree;
//二叉排序树的查找实现
//递归查找二叉排序树T中是否存在key
//指针f指向T的双亲,其初始调用值为NULL
//若查找成功,则指针p指向该数据元素结点,并返回TRUE
//否则指针p指向查找路径上访问的最后一个结点并返回FALSE
Status SearchBST(BiTree T, int key , BiTree f,BiTree * p){
if (!T) { //查找不成功
*p = f;
return FALSE;
}
else if (key == T -> data) {//查找成功
*p = T;
return TRUE;
}else if (key < T -> data)
return SearchBST (T -> lchild, key , T, p); //在左子树继续查找
else
return SearchBST(T -> rchild, key, T, p);//在右子树继续查找
}
由图可以看成,使用二叉树查找只需要三步即可,而使用有序的数组需要10步
6.二叉排序树的删除操作
我们对删除结点三种情况的分析
1.叶子结点
2.仅有左或右子树的结点
-
3.左右子树都有的结点
//若二叉排序树中存在关键字等于key的数据元素,则删除该数据元素结点 //并返回TRUE ,否则返回FALSE Status DeleteBST (BiTree *T, int key){ if (!T) //不存在关键字等于key的数据元素 return FALSE; else{ if (key == (*T )->data) //找到关键字等于key的数据元素 return Delete(T); else if (key < (*T) -> data) return DeleteBST(&(*T) -> lchild, key); else return DeleteBST(@&(*T) -> rchild ,key); } } //重点来了 ...... Status Delete(BiTree *p ) { BiTree q,s; if ((*p) -> rchild == NULL) //右子树空则只需要重接它的左子树 q = *p; *p = (*p) -> rchild; free(q); else{ //左右子树均不空 q = *p; s = (*p) -> lchild; while (s -> rchild) { //转左,然后向右到尽头(找待删结点的前驱) q = s; s = s -> rchild; } (*p) -> data = s -> data; //s指向被删除结点的直接前驱 if (q != *p) q -> rchild = s -> lchild; //重接q的右子树 else q -> lchild = s -> lchild;//重接q的左子树 free(s); } return TRUE; }
如果前面的代码,看不下去的话,这里是重点!!!!!
思路:被删除结点A的左子树的最右结点或A的右子树的最左结点作为替代A的结点,并修改相应的最左或最右结点的父节点的指针
7.平衡二叉树
平衡二叉树是一种**二叉排序树**,其中每一个节点的左子树和右子树的高度差至多等于1,那么平衡二叉树的平衡因子只可能是-1,0和1
我们将二叉树上结点的左子树深度减去右子数深度的值称为平衡因子
距离插入节点最近的,且平衡因子的绝对值大于1的结点为根的子树,我们称为最小不平衡子树
当新插入结点37时,距离它最近的平衡因子绝对值超过1的结点是58(即它的左子树高度2减去右子数高度0),所有从58开始以下的子树为最小不平衡子树
8.平衡二叉树实现原理
数组a[10] = {3,2,1,4,5,6,7,10,9,8}需要构建平衡二叉树
