编程实现如下功能: (1)根据输入的查找表的表长n和n个关键字值,建立顺序查找表,并在此查找表中用顺序查找方法查找给定关键值的记录,最后输出查找结果。 (2)根据输入的查找表的表长n和n个按升排列的关键字值,建立有序顺序查找表,并在此查找表中用二分查找方法查找给定关键值的记录,最后输出查找结果。 (3)主程序中要求设计一个菜单,允许用户通过菜单来多次选择执行哪一种查找操作。
时间: 2024-03-21 16:43:48 浏览: 57
好的,这个功能可以使用 C 语言来实现。下面是基本的代码框架:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义记录类型
typedef struct {
int key; // 关键字
// 其他数据项
} Record;
// 顺序查找函数
int seqSearch(Record* table, int n, int key) {
for (int i = 0; i < n; i++) {
if (table[i].key == key) {
return i; // 返回找到的记录的下标
}
}
return -1; // 表示未找到
}
// 二分查找函数
int binSearch(Record* table, int n, int key) {
int left = 0, right = n - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (table[mid].key == key) {
return mid; // 返回找到的记录的下标
} else if (table[mid].key < key) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1; // 表示未找到
}
// 建立顺序查找表
void createSeqTable(Record** table, int* n) {
// 从标准输入读入表长和关键字值
scanf("%d", n);
*table = (Record*) malloc(sizeof(Record) * (*n));
for (int i = 0; i < *n; i++) {
scanf("%d", &((*table)[i].key));
// 读入其他数据项
}
}
// 建立有序顺序查找表
void createOrderedSeqTable(Record** table, int* n) {
// 从标准输入读入表长和按升序排列的关键字值
scanf("%d", n);
*table = (Record*) malloc(sizeof(Record) * (*n));
for (int i = 0; i < *n; i++) {
scanf("%d", &((*table)[i].key));
// 读入其他数据项
}
}
// 主程序
int main() {
int choice, n, key;
Record* table = NULL;
do {
// 显示菜单
printf("1. 建立顺序查找表并查找\n");
printf("2. 建立有序顺序查找表并查找\n");
printf("0. 退出程序\n");
printf("请输入您的选择:");
scanf("%d", &choice);
switch (choice) {
case 1:
// 建立顺序查找表
createSeqTable(&table, &n);
// 输入要查找的关键字
printf("请输入要查找的关键字:");
scanf("%d", &key);
// 执行顺序查找
int index = seqSearch(table, n, key);
if (index == -1) {
printf("未找到该记录!\n");
} else {
// 输出找到的记录
printf("找到关键字为%d的记录,其它数据项为:...\n", key);
}
// 释放内存
free(table);
break;
case 2:
// 建立有序顺序查找表
createOrderedSeqTable(&table, &n);
// 输入要查找的关键字
printf("请输入要查找的关键字:");
scanf("%d", &key);
// 执行二分查找
int index = binSearch(table, n, key);
if (index == -1) {
printf("未找到该记录!\n");
} else {
// 输出找到的记录
printf("找到关键字为%d的记录,其它数据项为:...\n", key);
}
// 释放内存
free(table);
break;
case 0:
printf("程序已退出!\n");
break;
default:
printf("无效的选择!\n");
break;
}
} while (choice != 0);
return 0;
}
```
这个程序中,我们定义了 `Record` 结构体来表示一个记录,其中 `key` 是关键字,可以根据实际情况添加其他数据项。我们还定义了顺序查找和二分查找两个函数,用于在查找表中查找给定关键字的记录。在主程序中,我们使用一个 do-while 循环来显示菜单,并根据用户的选择来执行相应的操作。在每个操作中,我们先调用对应的函数来建立查找表,然后输入要查找的关键字,最后调用查找函数来查找记录,如果找到则输出记录,否则输出未找到的提示。注意,在每次操作结束后,我们需要释放内存。
你可以根据实际需要对代码进行修改和完善,比如添加错误处理、输入数据验证等。
阅读全文