线性表的查找

适用于静态查找表

数据类型

typedef struct {
    KeyType key; // 关键字域
    InfoType otherinfo; // 其他域
}ElemType;

typedef struct {
    ElemType *R; // 存储空间基地址
    int length;  // 当前长度
}SSTable;

顺序查找

从表的一端开始，依次将记录的关键字和给定值进行比价，若某个记录的关键字和给定值相等，则查找成功；反之，若扫描整个表后，仍为找到关键字和给定值相等的记录，则查找失败。时间复杂度O(n)

// 此假设元素从st.R[1]开始顺序向后存放，st.R[0]闲置不用，查找时从表的最后开始比较
int Search_Seq(SSTable st, KeyType key)
{
    for (int i = st.length; i >= 1; i--)
    {
        if (st.R[i].key == key)
        {
            return i;
        }
    }
    return 0;
}

// 对st.R[0]的关键字赋值key，在此，st.R[0]起到了监视哨的作用
int Search_Seq2(SSTable st, KeyType key)
{
    st.R[0].key = key;
    int i = st.length;
    for (; st.R[i].key != key; i--);
    return i;
}

折半查找

折半查找也称为二分查找，拆半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。时间复杂度 $O(log_2n)$

// 在有序表st中折半查找其关键字等于key的数据元素。若找到，则函数值为该元素在表中的位置，否则为0
// 有序表st默认递增排序
int Search_Bin(SSTable st, KeyType key)
{
    int low = 1;
    int higt = st.length;
    while (low < higt)
    {
        int mid = (low + higt) / 2;
        if (key == st.R[mid].key)
        {
            return mid;
        } else if (key < st.R[mid].key)
        {
            higt = mid - 1;
        } else
        {
            low = mid + 1;
        }
    }
    return 0;
}

分块查找

分块查找又称索引顺序查找。在该查找方法中，除表本身以外，尚需建立一个“索引表”。时间复杂度 $O(\sqrt n)$

步骤

1. 分块：将数组分成若干个大小相同的块（最后一个块可能较小）
2. 查找块：通过比较目标值与每个块的起始元素，确定目标值可能所在的块
3. 顺序查找：在确定的块内进行顺序查找，找到目标值

#include <math.h>

#define BLOCK_SIZE 3 // 定义块的大小

// 分块查找函数
int blockSearch(int arr[], int size, int target) {
    int blockCount = (int)ceil((double)size / BLOCK_SIZE); // 计算块的数量

    // 查找目标值所在的块
    for (int i = 0; i < blockCount; i++) {
        // 计算当前块的起始和结束索引
        int start = i * BLOCK_SIZE;
        int end = (i + 1) * BLOCK_SIZE < size ? (i + 1) * BLOCK_SIZE : size;

        // 如果目标值在当前块的范围内
        if (target >= arr[start] && target < arr[end - 1]) {
            // 在当前块内进行顺序查找
            for (int j = start; j < end; j++) {
                if (arr[j] == target) {
                    return j; // 找到目标值，返回索引
                }
            }
            break; // 如果在块内找到了，退出循环
        }
    }
    return -1; // 未找到目标值，返回-1
}

	顺序查找	折半查找	分块查找
时间复杂度	$O(n)$	$O(log_2n)$	与确定所在块的查找方法有关
特点	算法简单，对表结构物任何要求，但查找效率低	对表结构要求高，查找效率高	对表结构有一定要求，查找效率介于折半查找和顺序查找之间
使用情况	任何结构的线性表，不经常做插入和删除	有序的顺序表，不经常做插入和删除	块间有序、块内无序的顺序表，经常做插入和删除

树表的查找

适用于动态查找表

二叉排序树(二叉查找树)

时间复杂度

• 创建树: $O(nlog_2n)$
• 插入结点: $O(log_2n)$
• 查找结点: $O(log_2n)$
• 删除结点: $O(log_2n)$

二叉排序树或者是一棵空树，或者是具有下列性质的二叉树: - 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值 - 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值 - 它的左右子树也分别为二叉排序树

故: 中序遍历一颗二叉排序树可以得到一个结点值递增的有序序列

结构定义

typedef int KeyType;

typedef struct {
    KeyType key; // 关键字域
}ElemType;

typedef struct BSTNode {
    ElemType data; // 每个结点的数据域包括关键字项和其他数据项
    struct BSTNode *lchild, *rchild; // 左右孩子指针
}BSTNode, *BSTree;

二叉排序树的递归查找

算法步骤

• 若二叉排序树为空，则查找失败，返回空指针
• 若二叉排序树非空，将给定值与根结点的关键字t->data.key进行比较:
• 若key等于t->data.key，则查找成功，返回该结点地址
• 若key小于t->data.key，则递归查找左子树
• 若key大于t->data.key，则递归查找右子树

BSTree SearchBST(BSTree t, KeyType key)
{
    if (!t || key == t->data.key)
    {
        return t;
    }
    if (key < t->data.key)
    {
        return SearchBST(t->lchild, key);
    }
    return SearchBST(t->rchild, key);
}

二叉排序树的插入

算法步骤

• 若二叉排序树为空，则将插入结点*s作为根结点插入到空树中
• 若二叉排序树非空，则将key与根结点的关键字t->data.key比较
• 若key小于t->data.key，则将*s插入左子树
• 若key大于t->data.key，则将*s插入右子树

#include<stdlib.h>
BSTree InsertBST(BSTree t, KeyType key)
{
    if (!t)
    {
        BSTree s= (BSTree)malloc(sizeof(BSTNode));
        ElemType data = {key: key};
        s->data = data;
        s->lchild = s->rchild = NULL;
        return s;
    }
    if (key < t->data.key)
    {
        t->lchild = InsertBST(t->lchild, key);
    }
    if (key > t->data.key)
    {
        t->rchild = InsertBST(t->rchild, key);
    }
    return t;
}

二叉排序树的创建

算法步骤

• 将二叉排序树t初始化为空树
• 读取一个关键字key的结点
• 如果读取的关键字不是输入结束标志，则循环执行一下操作:
• 将此结点插入到二叉排序树t中
• 读入下一个关键字

#include<stdio.h>
#include<stdlib.h>

BSTree CreateBST()
{
    BSTree t = NULL;
    KeyType e;
    scanf("%d", e);
    while(e != 65535)
    {
        t = InsertBST(t, e);
        scanf("%d", e);
    }
    return t;
}

二叉排序树的删除

首先从二叉排序树的根结点开始查找关键字为key的待删除结点，如果树中不存在此结点，则不做任何操作；否则，假设被删结点为*p，其双亲结点为*f，$p_l$ 和 $p_r$ 分别表示其左子树和右子树。假设*p是*f的左孩子，可分下列情况讨论：

• 若*p为叶子结点，则 $p_l$ 和 $p_r$ 均为空树。由于删除叶子结点不破坏整棵树的结构，则只需修改其双亲结点的指针即可。

f->lchild=NULL;

• 若*p结点只有左子树 $p_l$ 或只有右子树 $p_r$ ，此时只要令 $p_l$ 或 $p_r$ 成为其双亲结点*f的左子树即可。

  f->lchild = p->lchild; 或 f->lchild = p->rchild;

• 若*p的左右子树均不为空。在删除*p之后，为保持其他元素之间的相对位置不变，有以下两种处理方法：

• 令*p的左子树为*f的左子树，而*p的右子树为*s的右子树 [ 可能增加树的深度 ]

  f->lchild = p->lchild; s->rchild = p->rchild

• 令*p的直接前驱（或直接后继）替代*p，然后再从二叉排序树中删除它的直接前驱（或直接后继）。当以直接前驱*s替代*p时，由于*s只有左子树 $s_l$ ，则在删去*s之后，只要令 $s_l$ 为*s的双亲*q的右子树即可 [ 以被删结点左子树中关键字最大的结点替代被删结点，然后从左子树中删除这个结点。此结点一定没有右子树（否则它就不是左子树中关键字最大的结点），这样不会增加树的高度 ]

  p->data=s->data; q->rchild=s->lchild;

#include<stdlib.h>

BSTree DeleteBST(BSTree t, KeyType key)
{
    // 初始化
    BSTree p = t;
    BSTree q = NULL;
    BSTree f = NULL;
    // 从根结点查找关键字等于key的结点p
    while (p)
    {
        if (p->data.key == key)
        {
            break;
        }
        f = p;
        if (p->data.key > key)
        {
            p = p->lchild;
        } else
        {
            p = p->rchild;
        }
    };
    // 树中不存在关键字为key的结点
    if (!p)
    {
        return t;
    }

    if (p->lchild && p->rchild)
    {
        q = p;
        BSTree s = p->lchild;
        // 在*p的左子树中继续查找其前驱结点，即最右下结点
        while (s->rchild)
        {
            q = s;
            s = s->rchild;
        }
        // s指向被删结点的"前驱"
        p->data = s->data;
        // 重接*q的右子树
        if (q != p)
        {
            q->rchild = s->lchild;
        }else
        {
            // 重接*q的左子树
            q->lchild = s->lchild;
        }
        free(s);
    }
    else if (!p->rchild)
    {
        q = p;
        p = p->lchild;
    } else
    {
        q = p;
        p = p->rchild;
    }
    // 被删除结点为根结点
    if (!f)
    {
        t = p;
    } else if (q == f->lchild) {
        // 连接到*f的左子树位置
        f->lchild = p;
    } else
    {
        // 连接到*f的右子树位置
        f->rchild = p;
    }
    free(p);
    return t;
}

平衡二叉树

查找时间复杂度 $O(log_2n)$

平衡二叉树或者是空树，或者是具有如下性质的二叉排序树

• 左子树和右子树的深度之差的绝对值小于1
• 左子树和右子树也是平衡二叉树

平衡树

折半查找和二叉排序树查找的比较

	折半查找	二叉树查找
时间复杂度	$O(log_2n)$	$O(log_2n)$
特点	数据结构采用有序的顺序表，插入和删除操作需移动大量元素	数据结构采用树的二叉链表表示，插入和删除操作无需移动元素，只需修改指针
使用情况	不经常做插入和删除的静态查找表	经常做插入和删除的动态查找表

B树

B树

散列表

散列表