查找
查找(Searching): 就是根据给定的某个值,在查找表中确定⼀个其关键字等于给定值的数据元素
查找表(SearchTable)是由同⼀类型的数据元素(记录)构成的集合
关键字(Key)是数据元素中某个数据项的值.⼜称为键值.⽤它可以表示⼀个数据元素,也可以标识⼀个记录的某个数据项(字段).我们称为关键码
若关键字可以唯⼀地标识⼀个记录,则称此关键字为主关键字 (PrimaryKey)
对于那些可以识别多个属于元素(记录)的关键字,我们称为次关键字(SecondaryKey)
查找表操作⽅式分类(静态/动态)
静态查找表(StaticSearchTable):只作查找操作的查找表：
- 查询某个”特定的”数据元素是否在查找表中;
- 检索某个"特定的"数据元素和各种属性;
动态查找表(DynamicSearchTable):在查找过程中同时插⼊查找表中不存在的数据元素,或者从查找表中删除已经存在的某个数据元素;显然动态查找表的操作就是2个动作 ：
- 查找时插⼊数据元素;
- .查找时删除数据元素;
顺序表查找(SequentialSearch)
顺序查找(SequentialSearch),⼜称为线性查找.是最基本的查找技术.它的查找过程:从表中的第⼀个(或最后⼀个)记录开始,逐个进⾏记录关键字和给定值⽐较;
- 若某个记录的关键字和给定值相等,则查找成功,找到所查记录;
- 如果直到最后⼀个(或第⼀个)记录,其关键字和给定值⽐较都不等时,则表中没有所查的记录,查找不成功;
代码实现：
//a为数组,n为查找的数组个数,key为要查找的关键字;
int Sequential_Search(int *a,int n,int key){
for (int i = 1; i <= n ; i++)
if (a[i] == key)
return i;
return 0;
}
//2.顺序查找_哨兵
int Sequential_Search2(int *a,int n,int key){
int i;
//设置a[0]为关键字值,称为'哨兵'
a[0] = key;
//循环从数组尾部开始
i = n;
while (a[i] != key) {
i--;
}
//返回0,则说明查找失败
return i;
}
两种方法的时间复杂度都为O(n)折半查找(BinarySearch)
折半查找(BinarySearch)技术,⼜称为⼆分查找
- 它的前提是线性表中的记录必须是关键码有序(通常是从⼩到⼤有序),线性表必须采⽤顺序存储;
- 折半查找的基本思想是:
- 在有序表中,取中间记录作为⽐较对象,若给定值与中间记录的关键字相等则查找成功;
- 若给定值⼩于中间的记录关键字,则在中间记录的左半区继续查找;
- 若给定的值⼤于中间记录的关键字,则在中间记录的右半区继续查找;
- 不断重复以上的过程,直到查找成功,或所以查找区域⽆记录,查找失败为⽌.
代码实现:
//假设数组a,已经是有序的(从小到大)
int Binary_Search(int *a,int n,int key){
int low,high,mid;
//定义最低下标为记录首位
low = 1;
//定义最高下标为记录末位
high = n;
while (low <= high) {
//折半计算
mid = (low + high) / 2;
if (key < a[mid]) {
//若key比a[mid] 小,则将最高下标调整到中位下标小一位;
high = mid-1;
}else if(key > a[mid]){
//若key比a[mid] 大,则将最低下标调整到中位下标大一位;
low = mid+1;
}else
//若相等则说明mid即为查找到的位置;
return mid;
}
return 0;
}
时间复杂度为Log(n)折半查找(BinarySearch)优化
假设,a[11]={0,1,16,24,35,47,59,62,73,88,99},low=1,hight=10;则a[low]=1,a[high]
=99;如果我们需要查找key=16;按照原有的折半查找需要进⾏4次才能找到结果;但是如果才有新的⽅程式,则
对2.377取整则mid=2,那么我们只需要进⾏2次查找就能找到结果.
插值查找(InterpolationSearch)
插值查找(InterpolationSearch):
是根据查找的关键字key与查找表中最⼤最⼩记录的关键字⽐较后的查找⽅法,其核⼼就是在于插值的计算公式: key-a[low] / a[high]-a[low]
代码实现：
int Interpolation_Search(int *a,int n,int key){
int low,high,mid;
low = 1;
high = n;
while (low <= high) {
//插值
mid = low + (high - low) * (key - a[low]) / (a[high] - a[low]);
if (key < a[mid]) {
//若key比a[mid]插值小,则将最高下标调整到插值下标小一位;
high = mid-1;
}else if(key > a[mid]){
//若key比a[mid]插值 大,则将最低下标调整到插值下标大一位;
low = mid+1;
}else
//若相等则说明mid即为查找到的位置;
return mid;
}
return 0;
}
斐波拉契查找(FibonacciSearch)
斐波那契数列
斐波那契数列假设查找,n=10,key=99
代码实现：
int F[100]; /* 斐波那契数列 */
int Fibonacci_Search(int *a,int n,int key){
int low,high,mid,i,k;
//最低下标为记录的首位;
low = 1;
//最高下标为记录的末位;
high = n;
k = 0;
//1.计算n为斐波拉契数列的位置;
while (n > F[k]-1) {
k++;
}
//2.将数组a不满的位置补全值;
for(i = n;i < F[k]-1;i++)
a[i] = a[n];
//3.
while (low <= high) {
//计算当前分隔的下标;
mid = low+F[k-1]-1;
if (key < a[mid]) {
//若查找的记录小于当前分隔记录;
//将最高下标调整到分隔下标mid-1处;
high = mid-1;
//斐波拉契数列下标减1位;
k = k-1;
}else if(key > a[mid]){
//若查找的记录大于当前的分隔记录;
//最低下标调整到分隔下标mid+1处
low = mid+1;
//斐波拉契数列下标减2位;
k = k-2;
}else{
if (mid <= n) {
//若相等则说明,mid即为查找的位置;
return mid;
}else
{
//若mid>n,说明是补全数值,返回n;
return n;
}
}
}
return 0;
}
最后main函数执行打印
int main(int argc, const char * argv[]) {
// insert code here...
printf("Hello, 静态查找!\n\n");
int a[MAXSIZE+1],i,result;
int arr[MAXSIZE] = {0,1,16,24,35,47,59,62,73,88,99};
for (i = 0; i<= MAXSIZE; i++) {
a[i] = i;
}
//1,顺序查找
result=Sequential_Search(a,MAXSIZE,MAXSIZE);
printf("顺序查找:%d\n",result);
//2,顺序查找_哨兵
result=Sequential_Search2(a,MAXSIZE,1);
printf("顺序查找_哨兵:%d \n",result);
//3.折半查找
result=Binary_Search(arr,10,62);
printf("折半查找:%d \n",result);
//4.插值查找
result=Interpolation_Search(arr,10,62);
printf("插值查找:%d \n",result);
//5.斐波拉契查找
//斐波拉契数列计算;
F[0]=0;
F[1]=1;
for(i = 2;i < 100;i++)
{
F[i] = F[i-1] + F[i-2];
}
result=Fibonacci_Search(arr,10,99);
printf("斐波拉契查找:%d \n",result);
result=Fibonacci_Search(arr,10,59);
printf("斐波拉契查找:%d \n",result);
printf("\n");
return 0;
}
打印结果：
有序总结：
二叉排序树
⼆叉排序树(BinarySortTree)定义
⼆叉排序树(BinarySortTree),⼜称为⼆叉查找树.它或者是⼀颗空树.或者是⼀颗具有下列性质的⼆叉树：
- 若它的左⼦树不空,则左⼦树上所有结点的值均⼩于它的根结构的值;
- 若它的右⼦树不空,则右⼦树上的所有结点的值均⼤于它的根结点的值;
- 它的左右⼦树也分别是⼆叉排序树;
二叉树结构定义
//结点结构
typedef struct BiTNode
{
//结点数据
int data;
//左右孩子指针
struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
⼆叉排序树(BinarySortTree)—查找操作
[算法设计]设计⼀个查找算法,在⼆叉排序树.找到关键字key=93的结点
模拟:
- 第1次:判断62是否等于key,不等于则将查找范围缩⼩到右⼦树;
- 第2次:判断88是否等于key,不等于则将查找范围缩⼩到右⼦树;
- 第3次:判断99是否等于key,不等于则将查找缩⼩到左⼦树;
- 第4次:判断93是否等于key,成功;则返回TRUE;
代码实现:向⼆叉排序树中查找关键字95;如果不存在该记录则插⼊到95到⼆叉排序树中
⼆叉排序树(BinarySortTree)—删除操作
情况1:删除的数据,例如37,51,73,93都是⼆叉排序树中是叶⼦结点.
情况2:删除的数据只有左⼦树或者只有右⼦树.也就是删除类似于58,35,99;
第⼀步:删除结点35,99;删除后如图：
情况3:删除的数据即有左⼦树⼜有右⼦树的情况怎么处理：
- 47被直接前驱37替换;
- 删除37结点;
- 将36移动到原来37的位置
- 47被直接后继48替换;
- 删除48结点;
⼆叉排序树删除结点会出现的3种情况:
- 删除叶⼦结点
- 删除仅有左或者右⼦树的结点;
- 删除左右⼦树都有的结点;
- 将temp和p都指向需要删除的结点47;
- 将s指向待删除的结点的左⼦树
- 在待删除的结点的左⼦树中,从右边找
- 使⽤temp保存好直接前驱的双亲结点
- 将要删除的结点p数据赋值成s- >data,简单说就是将37赋值到p结点的p data,替换47;
- 如果temp不等于p,则将S->lchild 赋值给temp->rchild;
- 如果temp等于p,则将S->lchild赋值给temp->lchild
- 删除s指向的结点;free(s),删除37;
主要代码实现
#include "stdio.h"
#include "stdlib.h"
#include "math.h"
#include "time.h"
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 100
typedef int Status;
//二叉树的二叉链表结点结构定义
//结点结构
typedef struct BiTNode
{
//结点数据
int data;
//左右孩子指针
struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
//1.二叉排序树--查找
/*
递归查找二叉排序树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); /* 在右子树中继续查找 */
}
//2.二叉排序树-插入
/* 当二叉排序树T中不存在关键字等于key的数据元素时， */
/* 插入key并返回TRUE，否则返回FALSE */
Status InsertBST(BiTree *T, int key) {
BiTree p,s;
//1.查找插入的值是否存在二叉树中;查找失败则->
if (!SearchBST(*T, key, NULL, &p)) {
//2.初始化结点s,并将key赋值给s,将s的左右孩子结点暂时设置为NULL
s = (BiTree)malloc(sizeof(BiTNode));
s->data = key;
s->lchild = s->rchild = NULL;
//3.
if (!p) {
//如果p为空,则将s作为二叉树新的根结点;
*T = s;
}else if(key < p->data){
//如果key<p->data,则将s插入为左孩子;
p->lchild = s;
}else
//如果key>p->data,则将s插入为右孩子;
p->rchild = s;
return TRUE;
}
return FALSE;
}
//3.从二叉排序树中删除结点p,并重接它的左或者右子树;
Status Delete(BiTree *p){
BiTree temp,s;
if((*p)->rchild == NULL){
//情况1: 如果当前删除的结点,右子树为空.那么则只需要重新连接它的左子树;
//①将结点p临时存储到temp中;
temp = *p;
//②将p指向到p的左子树上;
*p = (*p)->lchild;
//③释放需要删除的temp结点;
free(temp);
}else if((*p)->lchild == NULL){
//情况2:如果当前删除的结点,左子树为空.那么则只需要重新连接它的右子树;
//①将结点p存储到temp中;
temp = *p;
//②将p指向到p的右子树上;
*p = (*p)->rchild;
//③释放需要删除的temp结点
free(temp);
}else{
//情况③:删除的当前结点的左右子树均不为空;
//①将结点p存储到临时变量temp, 并且让结点s指向p的左子树
temp = *p;
s = (*p)->lchild;
//②将s指针,向右到尽头(目的是找到待删结点的前驱)
//-在待删除的结点的左子树中,从右边找到直接前驱
//-使用`temp`保存好直接前驱的双亲结点
while (s->rchild) {
temp = s;
s = s->rchild;
}
//③将要删除的结点p数据赋值成s->data;
(*p)->data = s->data;
//④重连子树
//-如果temp 不等于p,则将S->lchild 赋值给temp->rchild
//-如果temp 等于p,则将S->lchild 赋值给temp->lchild
if(temp != *p)
temp->rchild = s->lchild;
else
temp->lchild = s->lchild;
//⑤删除s指向的结点; free(s)
free(s);
}
return TRUE;
}
//4.查找结点,并将其在二叉排序中删除;
/* 若二叉排序树T中存在关键字等于key的数据元素时，则删除该数据元素结点, */
/* 并返回TRUE；否则返回FALSE。 */
Status DeleteBST(BiTree *T,int key)
{
//不存在关键字等于key的数据元素
if(!*T)
return FALSE;
else
{
//找到关键字等于key的数据元素
if (key==(*T)->data)
return Delete(T);
else if (key<(*T)->data)
//关键字key小于当前结点,则缩小查找范围到它的左子树;
return DeleteBST(&(*T)->lchild,key);
else
//关键字key大于当前结点,则缩小查找范围到它的右子树;
return DeleteBST(&(*T)->rchild,key);
}
}
int main(int argc, const char * argv[]) {
// insert code here...
printf("Hello, 二叉排序树(Binary Sort Tree)!\n");
int i;
int a[10]={62,88,58,47,35,73,51,99,37,93};
BiTree T=NULL;
for(i=0;i<10;i++)
{
InsertBST(&T, a[i]);
}
BiTree p;
int statusValue = SearchBST(T, 99, NULL, &p);
printf("查找%d是否成功:%d (1->YES/0->NO)\n",p->data,statusValue);
statusValue = DeleteBST(&T,93);
printf("二叉排序树删除93是否成功:%d (1->YES/0->NO)\n",statusValue);
statusValue = DeleteBST(&T,47);
printf("二叉排序树删除47是否成功:%d (1->YES/0->NO)\n",statusValue);
statusValue = DeleteBST(&T,12);
printf("二叉排序树删除12是否成功:%d (1->YES/0->NO)\n",statusValue);
statusValue = SearchBST(T, 93, NULL, &p);
printf("查找%d是否成功:%d (1->YES/0->NO)\n",93,statusValue);
statusValue = SearchBST(T, 47, NULL, &p);
printf("查找%d是否成功:%d (1->YES/0->NO)\n",47,statusValue);
statusValue = SearchBST(T, 99, NULL, &p);
printf("查找%d是否成功:%d (1->YES/0->NO)\n",99,statusValue);
printf("\n");
return 0;
}
打印结果：
