用结构体类型描述查找表的存储结构,编写具体函数实现查找表的顺序查找与折半查找等基本操作,编写完整代码程序,并给出一个具体实例输入和输出结果。
时间: 2023-12-03 13:45:28 浏览: 91
数据结构实验 折半查找的有关操作
以下是一个使用结构体类型描述查找表的存储结构,并实现顺序查找和折半查找的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100
typedef struct {
int key;
char value[10];
} RecordType;
typedef struct {
RecordType r[MAXSIZE];
int length;
} TableType;
int SeqSearch(TableType *T, int key) {
int i;
for (i = 0; i < T->length; i++) {
if (T->r[i].key == key) {
return i;
}
}
return -1;
}
int BinSearch(TableType *T, int key) {
int low = 0, high = T->length - 1, mid;
while (low <= high) {
mid = (low + high) / 2;
if (T->r[mid].key == key) {
return mid;
} else if (T->r[mid].key < key) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1;
}
int main() {
TableType T = {
{{1, "red"}, {3, "blue"}, {5, "green"}, {7, "yellow"}, {9, "white"}},
5
};
int key = 5;
int index = SeqSearch(&T, key);
if (index >= 0) {
printf("Sequential search: key %d found at index %d\n", key, index);
} else {
printf("Sequential search: key %d not found\n", key);
}
key = 7;
index = BinSearch(&T, key);
if (index >= 0) {
printf("Binary search: key %d found at index %d\n", key, index);
} else {
printf("Binary search: key %d not found\n", key);
}
return 0;
}
```
在上面代码中,使用 `RecordType` 结构体类型表示表中的一条记录,包含一个整型的 `key` 和一个字符串类型的 `value`。而使用 `TableType` 结构体类型表示整个查找表,包含一个 `RecordType` 类型的数组 `r` 和一个整型的 `length` 表示表的长度。
在 `SeqSearch` 函数中实现了顺序查找算法,遍历整个表查找关键字,如果找到返回其下标,否则返回 `-1`。
在 `BinSearch` 函数中实现了折半查找算法,通过不断将查找区间折半来逼近要查找的关键字,最终找到或者判定不存在。
在主函数中,定义了一个 `TableType` 类型的变量 `T` 作为查找表,并初始化为含有 5 条记录的表。接着,分别调用 `SeqSearch` 和 `BinSearch` 函数进行顺序查找和折半查找,并输出结果。
以下是一个具体实例输入和输出结果:
```c
Sequential search: key 5 found at index 2
Binary search: key 7 found at index 3
```
这说明在所给的表中,关键字分别为 5 和 7 的记录被正确找到了。
阅读全文