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

发布时间:2024-07-28 21:21

阅读量:0

查找

顺序查找

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

实现步骤：

从数组的第一个元素开始。
逐一比较数组中的元素与目标值。
如果找到目标值，返回其索引。
如果遍历完整个数组仍未找到，返回-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; }