数据结构查找

一.查找的基本概念

在计算机科学中，查找是一种在数据结构中寻找特定值的过程。在编程中，查找可以用于在数组、列表、树等数据结构中搜索特定值。不同的查找算法有不同的时间和空间复杂度，因此在选择查找算法时需要根据数据结构和查询需求来权衡时间和空间复杂度。

常见的查找算法包括线性查找、二分查找、哈希表查找、二叉搜索树查找等。其中，线性查找是最简单的查找算法，但时间复杂度较高为O(n)。二分查找适用于有序数组，时间复杂度为O(log n)。哈希表查找和二叉搜索树查找能够在O(1)或O(log n)的时间内完成查找，但需要额外的空间来存储哈希表或二叉搜索树。

在实际应用中，可以根据数据的大小、查询频率、插入和删除的操作频率等因素来选择不同的查找算法。

二. 查找方法

以下是对每种查找方法的补全和C语言示例代码，并对代码进行逐行分析。

顺序查找

顺序查找是一种简单的查找方法，它按顺序逐个比较待查找元素与数据结构中的元素，直到找到匹配的元素或遍历完整个数据结构。

C语言示例代码：

#include <stdio.h>int sequentialSearch(int arr[], int n, int key) {int i;for (i = 0; i < n; i++) {if (arr[i] == key) {return i;  // 返回元素在数组中的索引}}return -1;  // 没有找到元素，返回-1
}int main() {int arr[] = {4, 2, 7, 1, 5};int n = sizeof(arr) / sizeof(arr[0]);int key = 7;int result = sequentialSearch(arr, n, key);if (result == -1) {printf("元素 %d 未找到\n", key);} else {printf("元素 %d 的索引为 %d\n", key, result);}return 0;
}

代码分析：

sequentialSearch 函数接受一个数组 arr、数组长度 n 和待查找的关键字 key 作为参数。
通过 for 循环逐个比较数组元素和关键字，如果找到匹配的元素，返回该元素在数组中的索引。
如果遍历完整个数组都没有找到匹配的元素，函数返回 -1。
在 main 函数中，定义一个整型数组 arr 并初始化。
通过 sizeof 运算符计算数组的长度，并将其除以 sizeof(arr[0]) 得到元素个数。
定义关键字 key，调用 sequentialSearch 函数进行查找，并将结果存储在 result 变量中。
最后根据 result 的值输出查找结果。

分块查找

分块查找又称为索引顺序查找，它将数据结构分为若干块，每块中的元素可以是无序的，但块与块之间必须按照关键字的大小有序排列。

C语言示例代码：

#include <stdio.h>// 分块查找
int blockSearch(int blocks[], int indices[], int n, int m, int key) {int i, j;for (i = 0; i < n; i++) {if (key <= indices[i]) {break;  // 找到对应的块}}if (i == n) {return -1;  // 关键字超出范围，未找到}int start = (i == 0) ? 0 : blocks[i-1];  // 块的起始位置int end = blocks[i];  //块的结束位置for (j = start; j < end; j++) {if (key == blocks[j]) {return j;  // 在块中找到关键字，返回索引}}return -1;  // 在块中未找到关键字，返回-1
}int main() {int blocks[] = {2, 6, 8, 12, 15};int indices[] = {4, 9, 14, 17, 20};int n = sizeof(blocks) / sizeof(blocks[0]);int m = sizeof(indices) / sizeof(indices[0]);int key = 12;int result = blockSearch(blocks, indices, n, m, key);if (result == -1) {printf("元素 %d 未找到\n", key);} else {printf("元素 %d 的索引为 %d\n", key, result);}return 0;
}

代码分析：

blockSearch 函数接受两个数组 blocks 和 indices，分别表示块中的元素和块的索引，以及两个整数 n 和 m 分别表示块的数量和索引的数量，还有待查找的关键字 key。
通过 for 循环找到关键字所在的块，如果关键字超出范围，则返回 -1。
根据块的索引计算出块的起始位置 start 和结束位置 end。
在块中使用 for 循环逐个比较元素和关键字，如果找到匹配的元素，返回该元素在块中的索引。
如果在块中未找到匹配的元素，则返回 -1。
在 main 函数中，定义两个数组 blocks 和 indices 并初始化。
通过 sizeof 运算符计算数组的长度，并将其除以 sizeof(blocks[0]) 得到元素个数。
定义关键字 key，调用 blockSearch 函数进行查找，并将结果存储在 result 变量中。
最后根据 result 的值输出查找结果。

折半查找

折半查找也称为二分查找，它要求数据结构中的元素必须按照关键字的大小有序排列，通过将待查找范围逐渐缩小一半来快速定位目标元素。

C语言示例代码：

#include <stdio.h>// 折半查找
int binarySearch(int arr[], int low, int high, int key) {while (low <= high) {int mid = (low + high) / 2;if (arr[mid] == key) {return mid;  // 找到关键字，返回索引} else if (arr[mid] < key) {low = mid + 1;  // 关键字在右半部分} else {high = mid - 1;  // 关键字在左半部分}}return -1;  // 未找到关键字，返回-1
}int main() {int arr[] = {1, 2, 4, 5, 7};int n = sizeof(arr) / sizeof(arr[0]);int key = 4;int result = binarySearch(arr, 0, n-1, key);if (result == -1) {printf("元素 %d 未找到\n", key);} else {printf("元素 %d 的索引为 %d\n", key, result);}return 0;
}

代码分析：

binarySearch 函数接受一个有序数组 arr、查找范围的起始位置 low 和结束位置 high，以及待查找的关键字 key。
使用 while 循环进行折半查找，循环条件是起始位置小于等于结束位置。
在循环中，通过计算中间位置 mid，并将其与关键字进行比较。
如果中间位置的元素等于关键字，返回该元素的索引。
如果中间位置的元素小于关键字，则将起始位置 low 更新为 mid + 1，以缩小查找范围至右半部分。
如果中间位置的元素大于关键字，则将结束位置 high 更新为 mid - 1，以缩小查找范围至左半部分。
如果循环结束仍未找到关键字，则返回 -1。
在 main 函数中，定义一个有序数组 arr 并初始化。
通过 sizeof 运算符计算数组的长度，并将其除以 sizeof(arr[0]) 得到元素个数。
定义关键字 key，调用 binarySearch 函数进行查找，并将结果存储在 result 变量中。
最后根据 result 的值输出查找结果。

树型查找

树型查找方法基于树的结构，通过利用树的特性来提高查找效率。其中常用的树型查找方法包括二叉搜索树、平衡二叉树和红黑树。

二叉搜索树

二叉搜索树（Binary Search Tree，BST）是一种二叉树，它满足以下性质：

左子树上的所有节点的关键字都小于根节点的关键字。
右子树上的所有节点的关键字都大于根节点的关键字。
左子树和右子树也都是二叉搜索树。

C语言示例代码：

#include <stdio.h>
#include <stdlib.h>struct Node {int key;struct Node* left;struct Node* right;
};// 创建新节点
struct Node* createNode(int key) {struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));newNode->key = key;newNode->left = NULL;newNode->right = NULL;return newNode;
}// 插入节点
struct Node* insertNode(struct Node* root, int key) {if (root == NULL) {return createNode(key);}if (key < root->key) {root->left = insertNode(root->left, key);} else if (key > root->key) {root->right = insertNode(root->right, key);}return root;
}// 在二叉搜索树中查找关键字
struct Node* searchNode(struct Node* root, int key) {if (root == NULL || root->key == key) {return root;}if (key < root->key) {return searchNode(root->left, key);} else {return searchNode(root->right, key);}
}int main() {struct Node* root = NULL;root = insertNode(root, 4);insertNode(root, 2);insertNode(root, 7);insertNode(root, 1);insertNode(root, 5);int key = 7;struct Node* result = searchNode(root, key);if (result == NULL) {printf("元素 %d 未找到\n", key);} else {printf("元素 %d 已找到\n", key);}return 0;
}

代码分析：

定义一个结构体 Node 表示二叉搜索树的节点，其中包含关键字 key，左子节点 left 和右子节点 right。
创建一个新节点的函数 createNode 接受一个关键字 key，分配内存并初始化节点的值和子节点指针，然后返回该节点的指针。
插入节点的函数 insertNode 接受根节点 root 和关键字 key，如果根节点为空，则创建一个新节点并将其作为根节点返回。
如果关键字小于根节点的值，则将关键字插入左子树中。
如果关键字大于根节点的值，则将关键字插入右子树中。
查找关键字的函数 searchNode 接受根节点 root 和关键字 key，如果根节点为空或关键字等于根节点的值，则返回根节点。
如果关键字小于根节点的值，则在左子树中继续查找。
如果关键字大于根节点的值，则在右子树中继续查找。
在 main 函数中，定义根节点 root 并初始化为空。
使用 insertNode 函数插入一些关键字构建二叉搜索树。
定义待查找的关键字 key，调用 searchNode 函数进行查找，并将结果存储在 result 变量中。
最后根据 result 的值输出查找结果。

平衡二叉树

平衡二叉树（Balanced Binary Tree），也称为AVL树，是

一种特殊的二叉搜索树，它的左子树和右子树的高度差不超过1，以保持树的平衡。

C语言示例代码：

#include <stdio.h>
#include <stdlib.h>struct Node {int key;              // 键值struct Node* left;    // 左子节点指针struct Node* right;   // 右子节点指针int height;           // 节点的高度
};// 计算节点的高度
int getHeight(struct Node* node) {if (node == NULL) {return 0;}return node->height;
}// 计算节点的平衡因子
int getBalanceFactor(struct Node* node) {if (node == NULL) {return 0;}return getHeight(node->left) - getHeight(node->right);
}// 创建新节点
struct Node* createNode(int key) {struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));newNode->key = key;newNode->left = NULL;newNode->right = NULL;newNode->height = 1;return newNode;
}// 执行右旋操作
struct Node* rightRotate(struct Node* y) {struct Node* x = y->left;struct Node* T2 = x->right;// 右旋操作x->right = y;y->left = T2;// 更新节点的高度y->height = 1 + ((getHeight(y->left) > getHeight(y->right)) ? getHeight(y->left) : getHeight(y->right));x->height = 1 + ((getHeight(x->left) > getHeight(x->right)) ? getHeight(x->left) : getHeight(x->right));return x;
}// 执行左旋操作
struct Node* leftRotate(struct Node* x) {struct Node* y = x->right;struct Node* T2 = y->left;// 左旋操作y->left = x;x->right = T2;// 更新节点的高度x->height = 1 + ((getHeight(x->left) > getHeight(x->right)) ? getHeight(x->left) : getHeight(x->right));y->height = 1 + ((getHeight(y->left) > getHeight(y->right)) ? getHeight(y->left) : getHeight(y->right));return y;
}// 在平衡二叉树中插入节点
struct Node* insertNode(struct Node* root, int key) {if (root == NULL) {return createNode(key);}if (key < root->key) {root->left = insertNode(root->left, key);} else if (key > root->key) {root->right = insertNode(root->right, key);} else {return root;  // 重复的关键字，不插入}// 更新节点的高度root->height = 1 + ((getHeight(root->left) > getHeight(root->right)) ? getHeight(root->left) : getHeight(root->right));int balanceFactor = getBalanceFactor(root);// 左子树的高度大于右子树的高度，不平衡的情况下，需要进行旋转操作if (balanceFactor > 1 && key < root->left->key) {return rightRotate(root);}// 右子树的高度大于左子树的高度，不平衡的情况下，需要进行旋转操作if (balanceFactor < -1 && key > root->right->key) {return leftRotate(root);}// 左子树的高度大于右子树的高度，但插入节点的键值大于左子节点的键值，不平衡的情况下，需要进行先左旋再右旋的操作if (balanceFactor > 1 && key > root->left->key) {root->left = leftRotate(root->left);return rightRotate(root);}// 右子树的高度大于左子树的高度，但插入节点的键值小于右子节点的键值，不平衡的情况下，需要进行先右旋再左旋的操作if (balanceFactor < -1 && key < root->right->key) {root->right = rightRotate(root->right);return leftRotate(root);}return root;
}// 中序遍历打印二叉树
void inOrder(struct Node* root) {if (root == NULL) {return;}inOrder(root->left);printf("%d ", root->key);inOrder(root->right);
}int main() {struct Node* root = NULL;// 插入节点root = insertNode(root, 10);root = insertNode(root, 20);root = insertNode(root, 30);root = insertNode(root, 40);root = insertNode(root, 50);root = insertNode(root, 25);printf("Inorder traversal of the AVL tree: ");inOrder(root);return 0;
}

红黑树 (Red-Black Tree):

红黑树是一种自平衡的二叉搜索树，具有以下特性：

每个节点要么是红色，要么是黑色。
根节点是黑色。
所有叶子节点（NULL节点）都是黑色。
如果一个节点是红色，那么它的两个子节点都是黑色。
从任意节点到其每个叶子节点的所有路径都包含相同数目的黑色节点。

红黑树通过这些特性保持平衡，确保在最坏情况下，插入、删除和搜索操作的时间复杂度都为O(log n)。

B树和B+树:

B树和B+树是一种多路搜索树，用于在大量数据中进行高效的查找。

B树和B+树具有以下特性：

每个节点可以包含多个键值对，且按照键值的顺序排列。
内部节点包含的键值对数量比子节点数量少一个。
所有叶子节点都在同一层级，且通过指针连接。
B树允许在非叶子节点中存储键值对，而B+树只在叶子节点中存储键值对。
B树和B+树通过调整节点的分裂和合并来保持平衡。

B树和B+树适用于需要高效处理大量数据的场景，如数据库系统和文件系统索引。

散列表 (Hash Table):

散列表是一种数据结构，将键值对存储在数组中，并通过散列函数将键映射到数组索引上。

散列表具有以下特性：

通过散列函数将键转换为数组索引。
使用数组存储键值对，称为哈希表。
解决冲突的方法包括开放寻址法和链表法。
散列函数应该具有良好的散列性能，尽量避免冲突。

散列表提供了快速的插入、删除和查找操作，平均情况下时间复杂度为O(1)，但最坏情况下可能为O(n)。

查找算法的分析以及应用:

查找算法用于在数据集合中查找特定元素的位置或判断元素是否存在。

常见的查找算法包括线性查找、二分查找、哈希查找和树查找。

线性查找是最简单的查找算法，逐个比较元素直到找到目标元素或遍历完整个集合。时间复杂度为O(n)。

二分查找是一种在有序数组中查找目标

元素的高效算法。通过将数组分成两部分，并使用中间元素与目标元素进行比较，可以排除一半的元素，从而快速定位目标元素。时间复杂度为O(log n)。

哈希查找利用散列表来存储和查找元素，通过散列函数将键映射到数组索引上，从而实现快速的查找操作。平均情况下时间复杂度为O(1)，但最坏情况下可能为O(n)。

树查找包括二叉搜索树、平衡二叉搜索树（如红黑树和AVL树）、B树和B+树等。这些树结构通过按照特定规则组织元素，可以快速进行查找操作。时间复杂度通常为O(log n)。

这些查找算法在不同的应用场景中发挥着重要的作用。例如，在数据库系统中，使用索引结构（如B+树）来加速数据的查找操作。在字典或词典应用中，可以使用哈希表来实现快速的单词查找。在排序和搜索问题中，二分查找算法可以大大减少比较的次数，提高效率。

下面是一个使用二分查找算法在有序数组中查找目标元素的C语言代码示例：

#include <stdio.h>int binarySearch(int arr[], int low, int high, int target) {while (low <= high) {int mid = low + (high - low) / 2;if (arr[mid] == target) {return mid;}if (arr[mid] < target) {low = mid + 1;} else {high = mid - 1;}}return -1; // Target element not found
}int main() {int arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};int n = sizeof(arr) / sizeof(arr[0]);int target = 23;int index = binarySearch(arr, 0, n - 1, target);if (index != -1) {printf("Element found at index %d\n", index);} else {printf("Element not found\n");}return 0;
}

以上代码演示了如何使用二分查找算法在有序数组中查找目标元素。