daniel_developer

daniel_developer

关注
发信
关注(28)粉丝(399)

数据结构与算法之查找（静态查找与动态查找）

1. 概述

查找(Searching): 就是根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素。
查找表(Search Table)是由同⼀类型的数据元素(记录)构成的集合。
关键字(Key)是数据元素中某个数据项的值，又称为键值，用它可以表示⼀个数据元素，也可以标识一个记录的某个数据项(字段)，我们称为关键码。
若关键字可以唯⼀地标识一个记录, 则称此关键字为主关键字 (Primary Key)。
对于那些可以识别多个属于元素(记录)的关键字，我们称为次关键字(Secondary Key)。

查找表操作可分为静态查找和动态查找：

静态查找表(Static Search Table): 只作查找操作的查找表。
1.查询某个”特定的”数据元素是否在查找表中;
2.检索某个"特定的"数据元素和各种属性;

动态查找表(Dynamic Search Table): 在查找过程中同时插入查找表中不存在的数据元素, 或者从查找表中删除已经存在的某个数据元素。显然动态查找表的操作就是2个动作：
1.查找时插入数据元素;
2.查找时删除数据元素;

2. 静态查找

2.1 顺序查找

顺序查找(Sequential Search), 又称为线性查找，是最基本的查找技术。
它的查找过程: 从表中的第一个(或最后一个)记录开始，逐个进行记录关键字和给定值比较：
1.若某个记录的关键字和给定值相等，则查找成功，找到所查记录;
2.如果直到最后一个(或第⼀个)记录, 其关键字和给定值比较都不等时, 则表中没有所查的记录，查找不成功。

// a为数组,n为查找的数组个数,key为要查找的关键字。查询数组的第0位存放哨兵。
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.2 顺序查找优化

上面的顺序查找方法中，for循序每次都需要判断数组是否越界，因此去除for循环，优化代码如下：

// 顺序查找优化，使用哨兵。
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;
}

2.3 折半查找（二分查找）

折半查找(Binary Search)技术，又称为⼆分查找。

  • 它的前提是线性表中的记录必须是关键码有序(通常是从小到大有序)，线性表必须采用顺序存储;

  • 折半查找的基本思想是:

    • 在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键字相 等则查找成功;
    • 若给定值小于中间记录关键字，则在中间记录的左半区继续查找;
    • 若给定值大于中间记录关键字，则在中间记录的右半区继续查找;
    • 不断重复以上的过程，直到查找成功，或所有查找区域无记录，查找失败为⽌。
//假设数组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;
}

2.4 插值查找

插值查找是对折半查找的优化，在折半查找中，我们取中间元素与给定查找元素进行对比，而插值查找则不取中间元素，而是通过某种计算，找到待查找元素的附近的一个位置元素，然后进行对比。这样可以快速缩小查找范围。
折半查找中，计算mid的方法是：

理解为: mid 等于最低下标low加上最高下标high与最低下标low的差的一半，那么我们的前辈考虑将1/2进行改进，改进如下面的计算方案:

// 插值查找
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;
}

2.5 斐波那契查找

除了上面的查找方法，还有一种方法，斐波那契查找方法，它充分利用了黄金分割的原理，是一种特殊的折半查找方法。

首先要准备一个斐波那契数列：
F = {0, 1, 1, 2, 3, 5, 8, 13, 21, ...}
然后再准备一个供查询的数组：
a[11] = {0, 1, 16, 24, 35, 47, 59, 62, 73, 88, 99}

斐波拉契查找算法的核心在于:

  1. 当key = a[mid]时，表示查找成功;
  2. 当key < a[mid]时，将斐波那契数列分割下标k减小1（k=k-1）向左查找，新范围是第low个到第新mid-1个,此时范围个数为F[k-1]-1个;
  3. 当key > a[mid]时，将斐波那契数列分割下标k减小2（k=k-2）向右查找，新范围是第mid+1个到第high个. 此时范围个数为F[K-2]-1个;

首先需要计算出黄金分割点k，如上面a数组中除哨兵外元素个数n=10.

根据已知条件，计算k值

k = 0;
    while (n > F[k]-1) {
        k++;
    }

计算后k为7，此时根据k计算查找的范围F[k]-1 = F[7]-1 = 13 - 1 = 12.
显然12已经大于要查询的数组a的范围，所以我们需要将不足的位置用数组的最后一个元素补足。即：

//将数组a不满的位置补全值;
    for(i = n;i < F[k]-1;i++)
        a[i] = a[n];

准备工作做好之后，剩下的就是查找过程了，全部代码如下：

//斐波拉契查找
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;
}

测试代码如下：

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;
}

3. 动态查找

3.1 二叉排序树定义

二叉排序树(Binary Sort Tree)，又称为二叉查找树、二叉搜索树，它或者是一棵空树，或者是一棵具有下列性质的二叉树。

  • 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值;
  • 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值;
  • 它的左右子树也分别是二叉排序树;

二叉排序树结点定义如下：

#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;

3.2 二叉排序树查找

二叉排序树中查找某个key采用了递归查找，首先将key和根结点的数据域的值比较：

  • 如果小于，则以根结点的左孩子为新二叉排序树的根结点，然后继续进行比较；
  • 如果大于，则以根结点的右孩子为新二叉排序树的根结点，然后继续进行比较；
  • 反复执行上述操作，直到找到与key相等的结点，或者递归查找结束也没有找到。
/*
 递归查找二叉排序树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);  /*  在右子树中继续查找 */
}

3.3 二叉排序树插入

二叉排序树插入，首先需要遍历查找一遍是否存在插入的值key，如果不存在才进行插入。

  • 如果插入的二叉树不存在，则直接创建根结点，并将新插入的值存入根结点数据域。
  • 如果插入的二叉树存在，在查询过程中，已经记录了待插入位置的双亲结点，将key值与双亲结点数据域值比较，如果小于，则将key插入双亲结点的左孩子中，如果大于，则将key插入双亲结点的有孩子中。
/*  当二叉排序树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.4 二叉排序树删除

⼆叉排序树删除结点会出现以下3种情况:

  1. 删除叶子结点；
  2. 删除仅有左或者右子树的结点;
  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;
}

//查找结点,并将其在二叉排序中删除;
/* 若二叉排序树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;
}
03-05 16:05
Powered by LMLPHP ©2024 daniel_developer 0.072877