用c语言创建表,实现折半查找。
时间: 2024-05-04 20:18:20 浏览: 11
以下是使用 C 语言创建表并实现折半查找的示例代码:
```c
#include <stdio.h>
// 定义结构体,表示表中的一个元素
struct Element {
int key;
char value[50];
};
// 定义结构体,表示整个表
struct Table {
struct Element elements[100]; // 表中最多可以存放 100 个元素
int size; // 当前表中元素的个数
};
// 初始化表
void initTable(struct Table *table) {
table->size = 0;
}
// 向表中插入元素
void insertElement(struct Table *table, int key, char *value) {
if (table->size >= 100) { // 如果表已满,插入失败
printf("Table is full!\n");
return;
}
// 创建新元素
struct Element newElement = {key};
strcpy(newElement.value, value);
// 将新元素插入到表中
int i;
for (i = 0; i < table->size; i++) {
if (table->elements[i].key > key) { // 找到插入位置
break;
}
}
// 将 i 以后的元素都往后移动一位
int j;
for (j = table->size; j > i; j--) {
table->elements[j] = table->elements[j - 1];
}
// 将新元素插入到 i 位置
table->elements[i] = newElement;
table->size++; // 表中元素个数加 1
}
// 折半查找
int binarySearch(struct Table *table, int key) {
int left = 0; // 查找范围的左端点
int right = table->size - 1; // 查找范围的右端点
while (left <= right) {
int mid = (left + right) / 2; // 中间位置
if (table->elements[mid].key == key) { // 找到了
return mid;
} else if (table->elements[mid].key < key) { // 在右半部分继续查找
left = mid + 1;
} else { // 在左半部分继续查找
right = mid - 1;
}
}
// 没有找到
return -1;
}
int main() {
struct Table table;
initTable(&table);
// 向表中插入元素
insertElement(&table, 1, "value1");
insertElement(&table, 3, "value3");
insertElement(&table, 2, "value2");
insertElement(&table, 5, "value5");
insertElement(&table, 4, "value4");
// 折半查找元素
int index = binarySearch(&table, 3);
if (index != -1) {
printf("The value of element with key = 3 is %s.\n", table.elements[index].value);
} else {
printf("Element with key = 3 not found.\n");
}
return 0;
}
```
以上代码中,我们使用了结构体来表示表和元素,通过 `initTable()` 函数初始化表,通过 `insertElement()` 函数向表中插入元素,通过 `binarySearch()` 函数实现折半查找。在 `main()` 函数中,我们向表中插入了 5 个元素,并使用折半查找查找 key 值为 3 的元素,输出其对应的 value。