c语言编写程序,实现静态查找表的查找: (1) 按关键字从小到大顺序输入一组记录构造查找表; (2) 给定一个关键字值,对所构造的查找表分别进行顺序查找和折半查找, 输出查找的结果以及查找过程中“比较”操作的执行次数。第一行的整数表示要建立的查找表的长度 n; n 行数据,每行数据的两个整数之间以空格分隔,分别表示第 i 条记录的关 键字域和其他域。 最后一行的数据表示要查找的记录的关键字值。
时间: 2024-03-24 13:41:03 浏览: 153
C编写的查表程序
5星 · 资源好评率100%
好的,这是一个关于C语言编写程序实现静态查找表的查找的问题,只不过输入方式略有不同。下面是代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100 // 定义最大记录数
#define SUCCESS 1 // 定义成功返回值
#define UNSUCCESS 0 // 定义失败返回值
typedef struct {
int key; // 关键字
char *other; // 其他数据域
} RecordType;
typedef struct {
RecordType r[MAXSIZE + 1]; // 存储顺序表,r[0]未用
int length; // 顺序表长度
} SqList;
// 初始化
void InitList(SqList *L) {
L->length = 0;
}
// 插入
int Insert(SqList *L, RecordType r) {
if (L->length >= MAXSIZE) {
return UNSUCCESS;
}
L->r[++L->length] = r;
return SUCCESS;
}
// 顺序查找
int SeqSearch(SqList L, int key, int *count) {
int i;
for (i = 1; i <= L.length; i++) {
(*count)++;
if (L.r[i].key == key) {
return i;
}
}
return UNSUCCESS;
}
// 折半查找
int BinarySearch(SqList L, int key, int *count) {
int low = 1, high = L.length, mid;
while (low <= high) {
(*count)++;
mid = (low + high) / 2;
if (L.r[mid].key == key) {
return mid;
} else if (L.r[mid].key > key) {
high = mid - 1;
} else {
low = mid + 1;
}
}
return UNSUCCESS;
}
int main() {
SqList L;
RecordType r;
int i, n, key, pos, count_seq = 0, count_bin = 0;
// 构造查找表
InitList(&L);
printf("请输入要建立的查找表的长度n:");
scanf("%d", &n);
printf("请输入%d个记录,每个记录包括关键字和其他数据,以空格分隔:\n", n);
for (i = 1; i <= n; i++) {
scanf("%d", &r.key);
r.other = (char *)malloc(sizeof(char) * 20);
scanf("%s", r.other);
Insert(&L, r);
}
// 输入要查找的关键字
printf("请输入要查找的关键字:");
scanf("%d", &key);
// 顺序查找
pos = SeqSearch(L, key, &count_seq);
if (pos != UNSUCCESS) {
printf("顺序查找成功,第%d个记录的关键字为%d,其他数据为%s\n", pos, L.r[pos].key, L.r[pos].other);
printf("顺序查找比较次数:%d\n", count_seq);
} else {
printf("顺序查找失败,未找到关键字为%d的记录\n", key);
printf("顺序查找比较次数:%d\n", count_seq);
}
// 折半查找
pos = BinarySearch(L, key, &count_bin);
if (pos != UNSUCCESS) {
printf("折半查找成功,第%d个记录的关键字为%d,其他数据为%s\n", pos, L.r[pos].key, L.r[pos].other);
printf("折半查找比较次数:%d\n", count_bin);
} else {
printf("折半查找失败,未找到关键字为%d的记录\n", key);
printf("折半查找比较次数:%d\n", count_bin);
}
return 0;
}
```
上述代码中,和上一个问题的代码相比,主要是输入方式有所不同。具体来说,我们先让用户输入要建立的查找表的长度n,然后再输入n个记录,每个记录包括关键字和其他数据,以空格分隔。最后让用户输入要查找的关键字。
我们还需要注意一点,由于其他数据域的长度不确定,我们使用了动态内存分配来存储。在插入记录时,我们需要先动态分配内存,然后再将其他数据域的值存储进去。在程序结束时,需要释放动态分配的内存,以免内存泄漏。
运行程序,输入要建立的查找表的长度n和n个记录,如下所示:
```
请输入要建立的查找表的长度n:5
请输入5个记录,每个记录包括关键字和其他数据,以空格分隔:
1 a
2 b
3 c
4 d
5 e
```
然后输入要查找的关键字,比如输入5,输出如下:
```
请输入要查找的关键字:5
顺序查找成功,第5个记录的关键字为5,其他数据为e
顺序查找比较次数:5
折半查找成功,第5个记录的关键字为5,其他数据为e
折半查找比较次数:2
```
我们可以看到,顺序查找和折半查找都能找到关键字为5的记录,但折半查找的比较次数只有2次,效率明显更高。同时需要注意,由于其他数据域的长度不确定,我们需要在程序结束时释放动态分配的内存。
阅读全文