数据结构-查找

顺序查找和折半查找

顺序查找

可分为一般线性表的顺序查找和按关键字的有序线性表的查找
适用于顺序表与链表。遍历方式为下标与next指针。

一般线性表的顺序查找

typedef struct {
    ElemType *data;
    int length;
}SeqList;

int Search_Seq(SeqList L,ElemType key){
    L.data[0] = key;        //sentry
    while(int i = L.length;L.data[i] != key;--i);
    return i;
}

/*
定义length为5，数组下标1-5为存储data单元，0作为哨兵（本题中）
*/

上面代码引入了“哨兵”，用于避免不必要的判断语句。就其而言，不用些越界判断条件i>=0了

那么能不能在链式存储结构中使用哨兵呢？看看下面这个代码

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

// 定义元素类型和链表节点
typedef int ElemType; // 假设元素类型为 int
typedef struct LNode {
    ElemType data;          // 数据域
    struct LNode *next;     // 指针域
} LNode, *LinkList;

// 顺序查找函数（带哨兵）
LNode* seq_search_with_sentinel(LinkList L, ElemType key) {
    if (L->next == NULL) {
        return NULL; // 链表为空，直接返回 NULL
    }

    // 创建哨兵节点，并将其值设置为 key
    LNode sentinel;
    sentinel.data = key;
    sentinel.next = NULL;

    // 将哨兵节点添加到链表的末尾
    LNode *p = L->next; // 指向首元节点
    while (p->next != NULL) {
        p = p->next;
    }
    p->next = &sentinel; // 将哨兵节点链接到链表末尾

    // 查找过程
    LNode *p_find = L->next; // 从头节点的下一个节点开始查找
    while (p_find->data != key) {
        p_find = p_find->next;
    }

    // 恢复链表结构，移除哨兵节点
    p->next = NULL;

    // 判断是否找到目标节点
    if (p_find != &sentinel) {
        return p_find; // 找到目标节点
    } else {
        return NULL; // 未找到目标节点
    }
}

// 创建链表（头插法）
void create_list(LinkList L, ElemType arr[], int n) {
    L->next = NULL; // 初始化头节点
    for (int i = 0; i < n; i++) {
        LNode *new_node = (LNode *)malloc(sizeof(LNode));
        new_node->data = arr[i];
        new_node->next = L->next;
        L->next = new_node;
    }
}

// 打印链表
void print_list(LinkList L) {
    LNode *p = L->next;
    while (p != NULL) {
        printf("%d -> ", p->data);
        p = p->next;
    }
    printf("NULL\n");
}

int main() {
    // 初始化链表
    LinkList L = (LinkList)malloc(sizeof(LNode)); // 创建头节点
    ElemType arr[] = {3, 1, 4, 1, 5, 9, 2, 6};
    int n = sizeof(arr) / sizeof(arr[0]);
    create_list(L, arr, n);

    // 打印链表
    printf("链表内容: ");
    print_list(L);

    // 查找测试
    ElemType key = 5;
    LNode *result = seq_search_with_sentinel(L, key);
    if (result != NULL) {
        printf("找到元素: %d\n", result->data);
    } else {
        printf("未找到元素: %d\n", key);
    }

    // 释放链表内存
    LNode *p = L->next;
    while (p != NULL) {
        LNode *temp = p;
        p = p->next;
        free(temp);
    }
    free(L);

    return 0;
}

结合“将哨兵节点添加到链表的末尾”，说明需要遍历两次链表，虽然时间复杂度仍是O(n)，但意义并不大。

总结：

ASL_S=(n+1)/2 ASL_F=n+1:(比较次数)
缺点，n较大时效率低

有序线性表的顺序查找

折半查找（二分查找）

int Binary_Search(SeqList L,ElemType key){
    int low = 0, high = L->length-1;mid = 0;
    while(low <= high){
        //注意这里为什么是等于，因为low与high始终在闭区间内运算，当low=high时，仍有一个值没有运算。
        mid = low +(high-low)/2;
        if(L.data[mid] > L.data[key]){
            high = mid -1;
        }else if(L.data[mid] < L.data[key]){
            low = mid +1;
        }else{
            return mid;
        }
    }
    return -1;
}

需求有序排列
仅适用于有序线性表（可以随机定位），不适合链式存储。

分块查找

先将整个表分块（称为索引表），每个块中的元素不大于下一个块中的最小元素；再将索引表中的元素分为查找表。即这个过程有两个表。
ASL = ASL(索引表) + ASL(查找表)

若它们均采用顺序查找（总表长度为n,索引表被分为b块，查找表被分为s块）。ASL = (b+1)/2 + (s+1)/2，这里有n=sb。

树形查找

二叉排序树（BST）

说明与定义

构造二叉排序树不是为了排序，而是为了加快插入与删除
二叉排序树为递归定义：左子树结点值 < 根节点值 < 右子树结点值。因此中序遍历会得到递增的序列

查找

// 非递归
BSTNode *BST_Search(BiTree T , ElemType key){
    while(T != NULL && T->data != key){
        if(T->data < key){
            T = T->rchild;
        }else{
            T = T->lchild;
        }
    }
    return T;       //查找不到会返回NULL
}

//递归
BSTNode* BST_Search(BiTree T, ElemType key) {
    // 递归基（终止条件）：如果当前节点为空或节点的值等于key，返回当前节点
    if (T == NULL || T->data == key) {
        return T;
    }

    // 递归调用：根据key的大小决定向左子树还是右子树查找
    if (T->data < key) {
        return BST_Search(T->rchild, key);  // 查找右子树
    } else {
        return BST_Search(T->lchild, key);  // 查找左子树
    }
}

插入

int BST_Insert(BiTree T,ElemType k){
    if(T == NULL){
        T = (BiTree)malloc(sizeof(BiTree));
        T->data = k;
        T->lchild = NULL;
        T->rchild = NULL;
        return 1;
    }
    if(T->data == k){
        return 0 ;      //faild
    }
    if(T->data > k){
        //BST_Insert(T->lchild,k);          注意加上return，逐层返回
        return BST_Insert(T->lchild,k);
    }
    if(T->data < k){
        return BST_Insert(T->rchild,k);
    }
}

构造

void BST_Create(BiTree* T,ElemType str[],int n){
    int i = 0;
    while(i<n){
        BST_Init(T,str[i]);
        i++;
    }
}