【数据结构--树于哨兵查找-1】

查找

从前到后- 线性查找 -就是顺序查找.

哨兵法查找–节省每次都要判断是否越界的这一步骤利于节省开销，从而提升效率。

参考我的程序

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

#define SIZE 100000000

// 普通遍历查找
bool normal_search(int arr[], int key, int size) {
    for (int i = 0; i < size; i++) {
        if (arr[i] == key) {
            return true;
        }
    }
    return false;
}

// 哨兵优化查找
int sentinel_search(int arr[], int key, int size) {
    int last = arr[size - 1];
    arr[size - 1] = key; // 设置哨兵
    
    int i = 0;
    while (arr[i] != key) {
        i++;
    }
    
    arr[size - 1] = last; // 恢复原数据
    
    if (i < size - 1 || key == last) {
        return i;
    } else {
        return -1;
    }
}

int main() {
    int *arr = (int *)malloc(SIZE * sizeof(int));
    if (arr == NULL) {
        fprintf(stderr, "内存分配失败\n");
        return 1;
    }
    
    // 初始化数组为升序排列
    for (int i = 0; i < SIZE; i++) {
        arr[i] = i;
    }
    
    clock_t start, end;
    double normal_time, sentinel_time;
    
    // 测试普通查找
    start = clock();
    normal_search(arr, SIZE - 1, SIZE);
    end = clock();
    normal_time = (double)(end - start) / CLOCKS_PER_SEC;
    
    // 测试哨兵查找
    start = clock();
    sentinel_search(arr, SIZE - 1, SIZE);
    end = clock();
    sentinel_time = (double)(end - start) / CLOCKS_PER_SEC;
    
    printf("数组大小: %d\n", SIZE);
    printf("普通查找耗时: %f 秒\n", normal_time);
    printf("哨兵查找耗时: %f 秒\n", sentinel_time);
    printf("性能提升: %.2f%%\n", (normal_time - sentinel_time) / normal_time * 100);
    
    free(arr);
    return 0;
}

二叉排序树

更便于查找的数据结构，他的查找效率，要比顺序表高太多了。
极大利于数据操作中的【查找】

左孩子节点 < 父节点B < 右孩子节点

查找嘎嘎快。

普通

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

#define SIZE 10000000

// 普通顺序查找
bool normal_search(int arr[], int size, int val) {
    for (int i = 0; i < size; i++) {
        if (arr[i] == val) return true;
    }
    return false;
}

int main() {
    int *arr = (int*)malloc(SIZE * sizeof(int));
    if (arr == NULL) {
        fprintf(stderr, "内存分配失败\n");
        return 1;
    }
    
    // 初始化数组为升序排列
    for (int i = 0; i < SIZE; i++) {
        arr[i] = i;
    }
    
    int target = SIZE - 1; // 查找目标值
    bool found = normal_search(arr, SIZE, target);
    printf("数据量= %d  \n",SIZE);
    
    
    printf("普通查找结果: %s\n", found ? "找到" : "未找到");
    
    free(arr);
    return 0;
}

bst

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

#define SIZE 1000000

// 二叉排序树节点结构
typedef struct Node {
    int data;
    struct Node *left;
    struct Node *right;
} Node;

// 插入节点（迭代实现）
Node* insert(Node* root, int val) {
    Node *newNode = (Node*)malloc(sizeof(Node));
    newNode->data = val;
    newNode->left = newNode->right = NULL;
    
    if (root == NULL) return newNode;
    
    Node *curr = root;
    while (1) {
        if (val < curr->data) {
            if (curr->left == NULL) {
                curr->left = newNode;
                break;
            } else {
                curr = curr->left;
            }
        } else {
            if (curr->right == NULL) {
                curr->right = newNode;
                break;
            } else {
                curr = curr->right;
            }
        }
    }
    return root;
}

// BST查找（迭代实现）
bool bst_search(Node* root, int val) {
    while (root != NULL) {
        if (root->data == val) return true;
        else if (val < root->data) root = root->left;
        else root = root->right;
    }
    return false;
}

// 释放BST内存
void free_bst(Node* root) {
    if (root == NULL) return;
    free_bst(root->left);
    free_bst(root->right);
    free(root);
}

int main() {
    srand(time(NULL));
    Node *root = NULL;
    
    // 初始化BST（随机数据）
    for (int i = 0; i < SIZE; i++) {
        root = insert(root, rand() % (SIZE * 10));
    }
    
    int target = SIZE - 2; // 查找目标值
    bool found = bst_search(root, target);
        printf("BST数据量= %d  \n",SIZE);
    printf("BST查找结果: %s\n", found ? "找到" : "未找到");
    
    free_bst(root);
    return 0;
}