算法 - 查找算法（顺序、折半、红黑树、AVL树、B+树、散列）

🕗 发布于 2024-07-22 06:59 算法 b树 数据结构

查找

顺序查找

查找算法原理：
顺序查找是一种简单的查找方法，从数组的第一个元素开始，依次比较每个元素，直到找到目标元素或者数组结束为止。

实现步骤：

从数组的第一个元素开始。
逐一比较数组中的元素与目标值。
如果找到目标值，返回其索引。
如果遍历完整个数组仍未找到，返回-1。

C语言代码：

#include <stdio.h>

int sequential_search(int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == target) {
            return i;
        }
    }
    return -1;
}

int main() {
    int arr[] = {2, 4, 6, 8, 10};
    int target = 6;
    int n = sizeof(arr) / sizeof(arr[0]);
    int result = sequential_search(arr, n, target);
    if (result != -1) {
        printf("Element found at index %d\n", result);
    } else {
        printf("Element not found\n");
    }
    return 0;
}

代码解释：

int sequential_search(int arr[], int n, int target): 定义顺序查找函数，参数为数组、数组长度和目标值。
for (int i = 0; i < n; i++): 遍历数组。
if (arr[i] == target): 如果找到目标值。
return i: 返回目标值的索引。
return -1: 如果未找到目标值，返回-1。

折半查找（也称二分查找）

查找算法原理：
折半查找是一种在有序数组中查找目标值的高效方法。它通过不断将查找范围减半，直到找到目标值或范围为空为止。

实现步骤：

确定查找范围的起始和结束索引。
计算中间索引。
比较中间元素与目标值。
如果中间元素等于目标值，返回其索引。
如果中间元素小于目标值，缩小查找范围至右半部分。
如果中间元素大于目标值，缩小查找范围至左半部分。
重复上述步骤直到找到目标值或范围为空。

C语言代码：

#include <stdio.h>

int binary_search(int arr[], int n, int target) {
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            return mid;
        }
        if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

int main() {
    int arr[] = {2, 4, 6, 8, 10};
    int target = 6;
    int n = sizeof(arr) / sizeof(arr[0]);
    int result = binary_search(arr, n, target);
    if (result != -1) {
        printf("Element found at index %d\n", result);
    } else {
        printf("Element not found\n");
    }
    return 0;
}

代码解释：

int binary_search(int arr[], int n, int target): 定义二分查找函数，参数为数组、数组长度和目标值。
int left = 0, right = n - 1: 初始化左右索引。
while (left <= right): 当查找范围有效时。
int mid = left + (right - left) / 2: 计算中间索引。
if (arr[mid] == target): 如果找到目标值。
return mid: 返回目标值的索引。
if (arr[mid] < target): 如果中间元素小于目标值。
left = mid + 1: 调整左索引。
else: 如果中间元素大于目标值。
right = mid - 1: 调整右索引。
return -1: 如果未找到目标值，返回-1。

分块查找

查找算法原理：
分块查找将数据分成若干块，并在每块中进行线性查找。首先找到目标值可能所在的块，然后在该块中进行顺序查找。

实现步骤：

将数据分成若干块。
在块索引中找到目标值可能所在的块。
在该块中进行顺序查找。

C语言代码：

#include <stdio.h>

int block_search(int arr[], int n, int target, int block_size) {
    int block_count = (n + block_size - 1) / block_size;

    for (int i = 0; i < block_count; i++) {
        int start = i * block_size;
        int end = start + block_size;
        if (end > n) end = n;

        if (arr[end - 1] >= target) {
            for (int j = start; j < end; j++) {
                if (arr[j] == target) {
                    return j;
                }
            }
            return -1;
        }
    }
    return -1;
}

int main() {
    int arr[] = {2, 4, 6, 8, 10, 12, 14, 16, 18};
    int target = 10;
    int n = sizeof(arr) / sizeof(arr[0]);
    int block_size = 3;
    int result = block_search(arr, n, target, block_size);
    if (result != -1) {
        printf("Element found at index %d\n", result);
    } else {
        printf("Element not found\n");
    }
    return 0;
}

代码解释：

int block_search(int arr[], int n, int target, int block_size): 定义分块查找函数，参数为数组、数组长度、目标值和块大小。
int block_count = (n + block_size - 1) / block_size: 计算块的数量。
for (int i = 0; i < block_count; i++): 遍历每个块。
int start = i * block_size: 计算当前块的起始索引。
int end = start + block_size: 计算当前块的结束索引。
if (end > n) end = n: 如果结束索引超过数组长度，调整结束索引。
if (arr[end - 1] >= target): 如果目标值在当前块中。
for (int j = start; j < end; j++): 在块中进行顺序查找。
if (arr[j] == target): 如果找到目标值。
return j: 返回目标值的索引。
return -1: 如果未找到目标值，返回-1。

二叉排序树查找

查找算法原理：
二叉排序树（BST）是一种二叉树，每个节点的左子树所有值都小于该节点的值，右子树所有值都大于该节点的值。在BST中查找目标值时，通过比较当前节点值与目标值，决定在左子树或右子树中继续查找。

实现步骤：

从根节点开始。
比较当前节点值与目标值。
如果相等，返回该节点。
如果目标值小于当前节点值，在左子树中递归查找。
如果目标值大于当前节点值，在右子树中递归查找。
如果节点为空，返回未找到。

C语言代码：

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

struct TreeNode {
    int val;
    struct TreeNode *left, *right;
};

struct TreeNode* create_node(int key) {
    struct TreeNode* new_node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    new_node->val = key;
    new_node->left = new_node->right = NULL;
    return new_node;
}

struct TreeNode* insert(struct TreeNode* node, int key) {
    if (node == NULL) return create_node(key);
    if (key < node->val)
        node->left = insert(node->left, key);
    else if (key > node->val)
        node->right = insert(node->right, key);
    return node;
}

struct TreeNode* search(struct TreeNode* root, int target) {
    if (root == NULL || root->val == target)
        return root;
    if (target < root->val)
        return search(root->left, target);
    return search(root->right, target);
}

int main() {
    struct TreeNode* root = NULL;
    int keys[] = {20, 8, 22

, 4, 12, 10, 14};
    int n = sizeof(keys) / sizeof(keys[0]);

    for (int i = 0; i < n; i++) {
        root = insert(root, keys[i]);
    }

    int target = 10;
    struct TreeNode* result = search(root, target);
    if (result != NULL) {
        printf("Element found: %d\n", result->val);
    } else {
        printf("Element not found\n");
    }

    return 0;
}

代码解释：

struct TreeNode: 定义二叉排序树节点结构。
struct TreeNode* create_node(int key): 创建新节点。
struct TreeNode* insert(struct TreeNode* node, int key): 插入节点。
struct TreeNode* search(struct TreeNode* root, int target): 查找节点。
int main(): 主函数，演示插入和查找操作。

平衡二叉树（AVL树）

查找算法原理：
平衡二叉树是一种自平衡的二叉排序树，其左右子树的高度差最多为1，确保查找、插入、删除的时间复杂度为O(log n)。

实现步骤：

插入节点后，通过旋转操作保持树的平衡。
左旋和右旋操作用于重新平衡树。
计算每个节点的高度以保持平衡。

C语言代码：

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

struct TreeNode {
    int val;
    struct TreeNode *left, *right;
    int height;
};

int max(int a, int b) {
    return (a > b) ? a : b;
}

int height(struct TreeNode *N) {
    return (N == NULL) ? 0 : N->height;
}

struct TreeNode* create_node(int key) {
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node->val = key;
    node->left = node->right = NULL;
    node->height = 1;
    return node;
}

struct TreeNode* right_rotate(struct TreeNode *y) {
    struct TreeNode *x = y->left;
    struct TreeNode *T2 = x->right;

    x->right = y;
    y->left = T2;

    y->height = max(height(y->left), height(y->right)) + 1;
    x->height = max(height(x->left), height(x->right)) + 1;

    return x;
}

struct TreeNode* left_rotate(struct TreeNode *x) {
    struct TreeNode *y = x->right;
    struct TreeNode *T2 = y->left;

    y->left = x;
    x->right = T2;

    x->height = max(height(x->left), height(x->right)) + 1;
    y->height = max(height(y->left), height(y->right)) + 1;

    return y;
}

int get_balance(struct TreeNode *N) {
    return (N == NULL) ? 0 : height(N->left) - height(N->right);
}

struct TreeNode* insert(struct TreeNode* node, int key) {
    if (node == NULL)
        return create_node(key);

    if (key < node->val)
        node->left = insert(node->left, key);
    else if (key > node->val)
        node->right = insert(node->right, key);
    else
        return node;

    node->height = 1 + max(height(node->left), height(node->right));

    int balance = get_balance(node);

    if (balance > 1 && key < node->left->val)
        return right_rotate(node);

    if (balance < -1 && key > node->right->val)
        return left_rotate(node);

    if (balance > 1 && key > node->left->val) {
        node->left = left_rotate(node->left);
        return right_rotate(node);
    }

    if (balance < -1 && key < node->right->val) {
        node->right = right_rotate(node->right);
        return left_rotate(node);
    }

    return node;
}

struct TreeNode* search(struct TreeNode* root, int target) {
    if (root == NULL || root->val == target)
        return root;

    if (target < root->val)
        return search(root->left, target);
    return search(root->right, target);
}

int main() {
    struct TreeNode* root = NULL;
    int keys[] = {20, 8, 22, 4, 12, 10, 14};
    int n = sizeof(keys) / sizeof(keys[0]);

    for (int i = 0; i < n; i++) {
        root = insert(root, keys[i]);
    }

    int target = 10;
    struct TreeNode* result = search(root, target);
    if (result != NULL) {
        printf("Element found: %d\n", result->val);
    } else {
        printf("Element not found\n");
    }

    return 0;
}

代码解释：

定义AVL树节点结构，包含节点值、左子树、右子树和节点高度。
create_node 函数用于创建新节点。
right_rotate 和 left_rotate 函数用于保持树的平衡。
get_balance 函数用于计算节点的平衡因子。
insert 函数用于插入节点并保持树的平衡。
search 函数用于查找节点。

红黑树

查找算法原理：
红黑树是一种自平衡的二叉查找树，每个节点包含一个颜色（红色或黑色）。通过节点颜色和旋转操作保持树的平衡，确保查找、插入、删除操作的时间复杂度为O(log n)。

实现步骤：

插入节点后通过颜色调整和旋转操作保持树的平衡。
左旋和右旋操作用于重新平衡树。
确保树的性质：根节点是黑色，红色节点的子节点是黑色，从任一节点到叶子节点的路径上黑色节点数相同。

C语言代码：

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

enum Color { RED, BLACK };

struct TreeNode {
    int val;
    enum Color color;
    struct TreeNode *left, *right, *parent;
};

struct TreeNode* create_node(int key) {
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node->val = key;
    node->color = RED;
    node->left = node->right = node->parent = NULL;
    return node;
}

void left_rotate(struct TreeNode** root, struct TreeNode* x) {
    struct TreeNode* y = x->right;
    x->right = y->left;
    if (y->left != NULL) y->left->parent = x;
    y->parent = x->parent;
    if (x->parent == NULL)
        *root = y;
    else if (x == x->parent->left)
        x->parent->left = y;
    else
        x->parent->right = y;
    y->left = x;
    x->parent = y;
}

void right_rotate(struct TreeNode** root, struct TreeNode* y) {
    struct TreeNode* x = y->left;
    y->left = x->right;
    if (x->right != NULL) x->right->parent = y;
    x->parent = y->parent;
    if (y->parent == NULL)
        *root = x;
    else if (y == y->parent->left)
        y->parent->left = x;
    else
        y->parent->right = x;
    x->right = y;
    y->parent = x;
}

void insert_fixup(struct TreeNode** root, struct TreeNode* z) {
    while (z->parent != NULL && z->parent->color == RED) {
        if (z->parent == z->parent->parent->left) {
            struct TreeNode* y = z->parent->parent->right;
            if (y != NULL && y->color == RED) {
                z->parent->color = BLACK;
                y->color = BLACK;
                z->parent->parent->color = RED;
                z = z->parent->parent;
            } else {
                if (z == z->parent->right) {
                    z = z->parent;
                    left_rotate(root, z);
                }
                z->parent->color = BLACK;
                z->parent->parent->color = RED;
                right_rotate(root, z->parent->parent);
            }
        } else {
            struct TreeNode* y = z->parent->parent->left;
            if (y != NULL && y->color == RED) {
                z->parent->color = BLACK;
                y->color = BLACK;
                z->parent->parent->color = RED;
                z = z->parent->parent;
            } else {
                if (z == z->parent->left) {
                    z = z->parent;
                    right_rotate(root, z);
                }
                z->parent->color = BLACK;
                z->parent->parent->color = RED;
                left_rotate(root, z->parent->parent);
            }
        }
    }
    (*root)->color = BLACK;
}

void insert(struct TreeNode** root, int key) {
    struct TreeNode* z = create_node(key);
    struct TreeNode* y = NULL;
    struct TreeNode* x = *root;

    while (x != NULL) {
        y = x;
        if (z->val < x->val)
            x = x->left;
        else
            x = x->right;
    }

    z->parent = y;
    if (y == NULL)
        *root = z;
    else if (z->val < y->val)
        y->left = z;
    else
        y->right = z;

    insert_fixup(root, z);
}

struct TreeNode* search(struct TreeNode* root, int target) {
    while (root != NULL && root->val != target) {
        if (target < root->val)
            root

 = root->left;
        else
            root = root->right;
    }
    return root;
}

int main() {
    struct TreeNode* root = NULL;
    int keys[] = {20, 8, 22, 4, 12, 10, 14};
    int n = sizeof(keys) / sizeof(keys[0]);

    for (int i = 0; i < n; i++) {
        insert(&root, keys[i]);
    }

    int target = 10;
    struct TreeNode* result = search(root, target);
    if (result != NULL) {
        printf("Element found: %d\n", result->val);
    } else {
        printf("Element not found\n");
    }

    return 0;
}

代码解释：

定义红黑树节点结构，包含节点值、颜色、左子树、右子树和父节点。
create_node 函数用于创建新节点。
left_rotate 和 right_rotate 函数用于保持树的平衡。
insert_fixup 函数用于插入节点后的颜色调整和旋转操作。
insert 函数用于插入节点并保持树的平衡。
search 函数用于查找节点。

B树

查找算法原理：
B树是一种自平衡的树数据结构，广泛应用于数据库和文件系统中。B树节点可以有多个子节点和关键字，确保查找、插入、删除操作的时间复杂度为O(log n)。

实现步骤：

B树的每个节点可以包含多个关键字和子节点。
关键字和子节点根据值进行分布。
插入和删除操作需要保持树的平衡，通过节点分裂和合并操作实现。

C语言代码：

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

#define T 3

struct BTreeNode {
    int *keys;
    int t;
    struct BTreeNode **C;
    int n;
    int leaf;
};

struct BTreeNode* create_node(int t, int leaf) {
    struct BTreeNode* node = (struct BTreeNode*)malloc(sizeof(struct BTreeNode));
    node->t = t;
    node->leaf = leaf;
    node->keys = (int*)malloc((2*t-1) * sizeof(int));
    node->C = (struct BTreeNode**)malloc((2*t) * sizeof(struct BTreeNode*));
    node->n = 0;
    return node;
}

void traverse(struct BTreeNode* root) {
    int i;
    for (i = 0; i < root->n; i++) {
        if (!root->leaf)
            traverse(root->C[i]);
        printf(" %d", root->keys[i]);
    }
    if (!root->leaf)
        traverse(root->C[i]);
}

struct BTreeNode* search(struct BTreeNode* root, int k) {
    int i = 0;
    while (i < root->n && k > root->keys[i])
        i++;
    if (root->keys[i] == k)
        return root;
    if (root->leaf)
        return NULL;
    return search(root->C[i], k);
}

void insert_non_full(struct BTreeNode* x, int k);
void split_child(struct BTreeNode* x, int i, struct BTreeNode* y);

void insert(struct BTreeNode** root, int k) {
    struct BTreeNode* r = *root;
    if (r->n == 2*T-1) {
        struct BTreeNode* s = create_node(r->t, 0);
        s->C[0] = r;
        split_child(s, 0, r);
        int i = 0;
        if (s->keys[0] < k)
            i++;
        insert_non_full(s->C[i], k);
        *root = s;
    } else {
        insert_non_full(r, k);
    }
}

void split_child(struct BTreeNode* x, int i, struct BTreeNode* y) {
    struct BTreeNode* z = create_node(y->t, y->leaf);
    z->n = T - 1;
    for (int j = 0; j < T-1; j++)
        z->keys[j] = y->keys[j+T];
    if (!y->leaf) {
        for (int j = 0; j < T; j++)
            z->C[j] = y->C[j+T];
    }
    y->n = T - 1;
    for (int j = x->n; j >= i+1; j--)
        x->C[j+1] = x->C[j];
    x->C[i+1] = z;
    for (int j = x->n-1; j >= i; j--)
        x->keys[j+1] = x->keys[j];
    x->keys[i] = y->keys[T-1];
    x->n = x->n + 1;
}

void insert_non_full(struct BTreeNode* x, int k) {
    int i = x->n - 1;
    if (x->leaf) {
        while (i >= 0 && x->keys[i] > k) {
            x->keys[i+1] = x->keys[i];
            i--;
        }
        x->keys[i+1] = k;
        x->n = x->n + 1;
    } else {
        while (i >= 0 && x->keys[i] > k)
            i--;
        if (x->C[i+1]->n == 2*T-1) {
            split_child(x, i+1, x->C[i+1]);
            if (x->keys[i+1] < k)
                i++;
        }
        insert_non_full(x->C[i+1], k);
    }
}

int main() {
    struct BTreeNode* root = create_node(T, 1);
    int keys[] = {10, 20, 5, 6, 12, 30, 7, 17};
    int n = sizeof(keys) / sizeof(keys[0]);

    for (int i = 0; i < n; i++) {
        insert(&root, keys[i]);
    }

    printf("Traversal of the constructed tree is ");
    traverse(root);

    int target = 6;
    struct BTreeNode* result = search(root, target);
    if (result != NULL) {
        printf("\nElement found");
    } else {
        printf("\nElement not found");
    }

    return 0;
}

代码解释：

定义B树节点结构，包含关键字、子节点、关键字数量和是否为叶子节点。
create_node 函数用于创建新节点。
traverse 函数用于遍历B树。
search 函数用于查找节点。
insert 函数用于插入节点。
split_child 函数用于分裂节点。
insert_non_full 函数用于在非满节点中插入关键字。

B+树

查找算法原理：
B+树是B树的一种变种，所有数据都存储在叶子节点中，并且叶子节点通过链表相连。B+树的非叶子节点只存储索引，便于范围查找。

实现步骤：

B+树的每个节点可以包含多个关键字和子节点。
关键字和子节点根据值进行分布。
插入和删除操作需要保持树的平衡，通过节点分裂和合并操作实现。

C语言代码：

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

#define T 3

struct BPlusTreeNode {
    int *keys;
    struct BPlusTreeNode **C;
    struct BPlusTreeNode *next;
    int n;
    int leaf;
};

struct BPlusTreeNode* create_node(int leaf) {
    struct BPlusTreeNode* node = (struct BPlusTreeNode*)malloc(sizeof(struct BPlusTreeNode));
    node->keys = (int*)malloc((2*T-1) * sizeof(int));
    node->C = (struct BPlusTreeNode**)malloc((2*T) * sizeof(struct BPlusTreeNode*));
    node->next = NULL;
    node->n = 0;
    node->leaf = leaf;
    return node;
}

void traverse(struct BPlusTreeNode* root) {
    struct BPlusTreeNode* current = root;
    while (!current->leaf)
        current = current->C[0];

    while (current) {
        for (int i = 0; i < current->n; i++)
            printf(" %d", current->keys[i]);
        current = current->next;
    }
}

struct BPlusTreeNode* search(struct BPlusTreeNode* root, int k) {
    int i = 0;
    while (i < root->n && k > root->keys[i])
        i++;
    if (i < root->n && root->keys[i] == k)
        return root;
    if (root->leaf)
        return NULL;
    return search(root->C[i], k);
}

void insert_non_full(struct BPlusTreeNode* x, int k);
void split_child

(struct BPlusTreeNode* x, int i, struct BPlusTreeNode* y);

void insert(struct BPlusTreeNode** root, int k) {
    struct BPlusTreeNode* r = *root;
    if (r->n == 2*T-1) {
        struct BPlusTreeNode* s = create_node(0);
        s->C[0] = r;
        split_child(s, 0, r);
        int i = 0;
        if (s->keys[0] < k)
            i++;
        insert_non_full(s->C[i], k);
        *root = s;
    } else {
        insert_non_full(r, k);
    }
}

void split_child(struct BPlusTreeNode* x, int i, struct BPlusTreeNode* y) {
    struct BPlusTreeNode* z = create_node(y->leaf);
    z->n = T - 1;
    for (int j = 0; j < T-1; j++)
        z->keys[j] = y->keys[j+T];
    if (!y->leaf) {
        for (int j = 0; j < T; j++)
            z->C[j] = y->C[j+T];
    } else {
        z->next = y->next;
        y->next = z;
    }
    y->n = T - 1;
    for (int j = x->n; j >= i+1; j--)
        x->C[j+1] = x->C[j];
    x->C[i+1] = z;
    for (int j = x->n-1; j >= i; j--)
        x->keys[j+1] = x->keys[j];
    x->keys[i] = y->keys[T-1];
    x->n = x->n + 1;
}

void insert_non_full(struct BPlusTreeNode* x, int k) {
    int i = x->n - 1;
    if (x->leaf) {
        while (i >= 0 && x->keys[i] > k) {
            x->keys[i+1] = x->keys[i];
            i--;
        }
        x->keys[i+1] = k;
        x->n = x->n + 1;
    } else {
        while (i >= 0 && x->keys[i] > k)
            i--;
        if (x->C[i+1]->n == 2*T-1) {
            split_child(x, i+1, x->C[i+1]);
            if (x->keys[i+1] < k)
                i++;
        }
        insert_non_full(x->C[i+1], k);
    }
}

int main() {
    struct BPlusTreeNode* root = create_node(1);
    int keys[] = {10, 20, 5, 6, 12, 30, 7, 17};
    int n = sizeof(keys) / sizeof(keys[0]);

    for (int i = 0; i < n; i++) {
        insert(&root, keys[i]);
    }

    printf("Traversal of the constructed B+ tree is ");
    traverse(root);

    int target = 6;
    struct BPlusTreeNode* result = search(root, target);
    if (result != NULL) {
        printf("\nElement found");
    } else {
        printf("\nElement not found");
    }

    return 0;
}

代码解释：

定义B+树节点结构，包含关键字、子节点、下一个节点、关键字数量和是否为叶子节点。
create_node 函数用于创建新节点。
traverse 函数用于遍历B+树。
search 函数用于查找节点。
insert 函数用于插入节点。
split_child 函数用于分裂节点。
insert_non_full 函数用于在非满节点中插入关键字。

散列查找

查找算法原理：
散列查找通过散列函数将关键字映射到数组中的位置。使用链地址法处理散列冲突，每个数组位置存储一个链表，链表中的每个节点包含具有相同散列值的关键字。

实现步骤：

使用散列函数计算关键字的散列值。
根据散列值将关键字插入对应位置的链表中。
查找时，计算关键字的散列值，然后在链表中查找目标值。

C语言代码：

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

#define TABLE_SIZE 10

struct Node {
    int key;
    struct Node* next;
};

struct Node* hash_table[TABLE_SIZE];

unsigned int hash(int key) {
    return key % TABLE_SIZE;
}

void insert(int key) {
    unsigned int index = hash(key);
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
    new_node->key = key;
    new_node->next = hash_table[index];
    hash_table[index] = new_node;
}

struct Node* search(int key) {
    unsigned int index = hash(key);
    struct Node* current = hash_table[index];
    while (current != NULL) {
        if (current->key == key)
            return current;
        current = current->next;
    }
    return NULL;
}

void display() {
    for (int i = 0; i < TABLE_SIZE; i++) {
        struct Node* current = hash_table[i];
        printf("hash_table[%d]: ", i);
        while (current != NULL) {
            printf("%d -> ", current->key);
            current = current->next;
        }
        printf("NULL\n");
    }
}

int main() {
    insert(10);
    insert(20);
    insert(15);
    insert(7);
    insert(32);

    display();

    int target = 15;
    struct Node* result = search(target);
    if (result != NULL) {
        printf("Element found: %d\n", result->key);
    } else {
        printf("Element not found\n");
    }

    return 0;
}

代码解释：

定义链表节点结构，包含关键字和下一个节点指针。
定义哈希表为链表节点指针数组。
hash 函数用于计算关键字的散列值。
insert 函数用于插入关键字到哈希表。
search 函数用于查找关键字。
display 函数用于显示哈希表的内容。

原文地址：https://blog.csdn.net/L6666688888/article/details/140589548

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：Robot Operating System——消息的序列化和反序列化
下一篇：MongoDB教程（十六）：MongoDB高级索引

第七章：TDengine SHOW 命令大全
SHOW命令用于获取TDengine数据库中的系统信息、元数据、状态等。通过SHOW命令，用户可以方便地查看数据库的各种信息，如数据库列表、表结构、索引、连接信息等。
阅读更多2024-11-18
【Linux内核剖析】深入分析inet_init的处理机制
inet_init是 Linux 内核中用于初始化 TCP/IP 协议栈的函数。它在内核启动时被调用，完成各种协议和数据结构的注册和初始化。
阅读更多2024-11-18
【C++进阶篇】——string类的使用
是 C++ 标准库的一部分，但它不是 STL 容器的一部分。STL 容器是指那些基于模板的容器，如std::list等。提供了类似于 STL 容器的功能，比如动态内存管理、迭代器支持等，但它的设计和实
阅读更多2024-11-18
Javaweb开发核心之应用上下文知识（笔记）
⽐比如：PageContext，ServletRequest，HttpSession，ServletContext；简介:讲解Javaweb作⽤用域对象介绍和ServletContext讲解。就是对象
阅读更多2024-11-18
Web Service 学习笔记
Web Service 即 web 服务，它是一种跨编程语言和跨操作系统平台的远程调用技术。Java 中共有三种 Web Service 规范：- JAX-WS(JAX-RPC): 基于 xml 数据
阅读更多2024-11-18
使用函数的选择法排序
其中a是待排序的数组，n是数组a中元素的个数。该函数用选择法将数组a中的元素按升序排列，结果仍然在数组a中。
阅读更多2024-11-18
Leetcode 3356. Zero Array Transformation II
Leetcode 3356. Zero Array Transformation II
阅读更多2024-11-18
图形最高分
游戏一开始，玩家在每一轮可以合并两个图形，当只有一个图形的时候游戏结束，每个图形都有一个大小，合并完成后的图形的大小为x+y,x和y分别为合并之前的两个图形，与此同时，玩家会获得x*y的分数。现在屏幕
阅读更多2024-11-18
nodejs入门（1）：nodejs的前后端分离
浏览器和前端web服务器交互，前端web服务器和后端web服务器进行交互，前端web服务器向后端的web服务器请求数据，对后端服务器得到请求后将数据传递给前端web服务器，格式化后由浏览器展示。好的，
阅读更多2024-11-18
wife_wife
在下面的信息中加上"__proto__":{"isAdmin":true}上网查了一下，用到了Javascript原型链污染攻击。用这个漏洞的前提是后端使用的语
阅读更多2024-11-18

算法 - 查找算法（顺序、折半、红黑树、AVL树、B+树、散列）

查找

顺序查找

折半查找（也称二分查找）

分块查找

二叉排序树查找

平衡二叉树（AVL树）

红黑树

B树

B+树

散列查找

相关文章