C 语言中的查找输出372

C语言提供了几种查找或搜索列表、数组和字符串中特定元素的功能。这些功能对于处理大数据集或检索特定信息至关重要。

1. 顺序搜索

顺序搜索，也称为线性搜索，是最简单的查找算法。它依次遍历列表中的每个元素，直到找到要查找的元素或到达列表的结尾。顺序搜索的时间复杂度为 O(n)，其中 n 是列表中的元素数量。```c
int sequential_search(int arr[], int n, int element) {
for (int i = 0; i < n; i++) {
if (arr[i] == element) {
return i;
}
}
return -1;
}
```

2. 二分搜索

二分搜索是一种更有效的搜索算法，适用于已排序的列表。它将列表分成两半，比较要查找的元素与中间元素。如果匹配，则停止搜索。否则，根据元素是否小于或大于中间元素，继续在较小或较大的子列表中进行搜索。二分搜索的时间复杂度为 O(log n)。```c
int binary_search(int arr[], int n, int element) {
int low = 0;
int high = n - 1;
while (low data == element) {
return root;
} else if (element < root->data) {
return search_bst(root->left, element);
} else {
return search_bst(root->right, element);
}
}
```

4. 散列表

散列表是一种快速且有效的搜索算法，适用于大数据集。它将键映射到存储在数组中的值。查找操作通过计算键的哈希值并使用该值检索适当的数组槽来进行。散列表的平均时间复杂度通常接近 O(1)。```c
#include
struct entry {
int key;
int value;
};
struct hash_table {
struct entry *table[];
int size;
};
struct hash_table *create_hash_table(int size) {
struct hash_table *table = malloc(sizeof(struct hash_table));
table->size = size;
table->table = calloc(size, sizeof(struct entry));
return table;
}
int hash(int key, int size) {
return key % size;
}
void insert_hash(struct hash_table *table, int key, int value) {
int index = hash(key, table->size);
struct entry *entry = malloc(sizeof(struct entry));
entry->key = key;
entry->value = value;
table->table[index] = entry;
}
int search_hash(struct hash_table *table, int key) {
int index = hash(key, table->size);
struct entry *entry = table->table[index];
while (entry != NULL) {
if (entry->key == key) {
return entry->value;
}
entry = entry->next;
}
return -1;
}
```