用c语言编写程序,实现静态查找表的查找:(1) 按关键字从小到大顺序输入一组记录构造查找表;(2) 给定一个关键字值,对所构造的查找表分别进行顺序查找和折半查找,输出查找的结果以及查找过程中“比较”操作的执行次数。输入格式:第一行的整数表示要建立的查找表的长度n;n 行数据,每行数据的两个整数之间以空格分隔,分别表示第i条记录的关键字域和其他域。最后一行的数据表示要查找的记录的关键字值。输出格式:查找结果,两行数据,第一行表示用顺序查找的查找结果,两个数据分别表示是否找到和比较次数;第二行表示用折半查找的查找结果,两个数据分别表示是否找到和比较次数。
时间: 2024-03-25 13:38:43 浏览: 110
C语言实现顺序表的顺序查找和折半查找
好的,下面是用 C 语言实现的代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义记录类型
typedef struct {
int key, value;
} Record;
// 顺序查找
int sequential_search(int key, Record *table, int n) {
int count = 0;
for (int i = 0; i < n; i++) {
count++;
if (key == table[i].key) {
return count;
}
}
return count;
}
// 折半查找
int binary_search(int key, Record *table, int n) {
int count = 0;
int low = 0, high = n - 1;
while (low <= high) {
int mid = (low + high) / 2;
count++;
if (key == table[mid].key) {
return count;
} else if (key < table[mid].key) {
high = mid - 1;
} else {
low = mid + 1;
}
}
return count;
}
int main() {
int n;
printf("请输入查找表的长度n:");
scanf("%d", &n);
Record *table = (Record *)malloc(sizeof(Record) * n);
// 输入记录
for (int i = 0; i < n; i++) {
scanf("%d%d", &table[i].key, &table[i].value);
}
// 按照关键字从小到大排序
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
if (table[i].key > table[j].key) {
Record tmp = table[i];
table[i] = table[j];
table[j] = tmp;
}
}
}
int key;
printf("请输入要查找的关键字值:");
scanf("%d", &key);
// 顺序查找
int seq_count = sequential_search(key, table, n);
if (seq_count <= n) {
printf("用顺序查找的查找结果:找到,比较次数:%d\n", seq_count);
} else {
printf("用顺序查找的查找结果:未找到,比较次数:%d\n", seq_count);
}
// 折半查找
int bin_count = binary_search(key, table, n);
if (bin_count <= n) {
printf("用折半查找的查找结果:找到,比较次数:%d\n", bin_count);
} else {
printf("用折半查找的查找结果:未找到,比较次数:%d\n", bin_count);
}
free(table);
return 0;
}
```
注意,在 C 语言中,需要手动申请和释放内存空间,所以需要使用 `malloc` 和 `free` 函数。另外,这里假设输入的数据没有错误,例如输入的长度n与实际输入的记录数一致,输入的记录按照关键字从小到大排序等。如果要增加容错处理,需要在代码中添加相应的判断。
阅读全文