用结构体类型描述查找表的存储结构,编写具体函数实现查找表的顺序查找与折半查找等基本操作,编写完整代码程序,在程序运行后的输入框中输入一个包含数据元素的有序表(关键字即数据元素的值),接着输入要查找的数据元素,若找到,则输出结果为查找的数据元素在有序表中的位置,否则输出结果为0,并给出一个具体实例。
时间: 2023-12-03 07:45:53 浏览: 71
顺序查找,折半查找,二叉排序树,哈希表
以下是结构体类型描述查找表的存储结构的代码示例:
```c
#define MAXSIZE 100
typedef struct {
int key;
// 其他数据元素
} ElementType;
typedef struct {
ElementType data[MAXSIZE];
int length;
} SeqList;
```
其中,`SeqList` 表示顺序表,包含一个数组 `data` 和长度 `length`。
接下来,我们可以编写具体函数实现查找表的顺序查找与折半查找等基本操作。具体代码如下:
```c
#include <stdio.h>
// 顺序查找
int SeqSearch(SeqList L, int key) {
int i;
for (i = 0; i < L.length; i++) {
if (L.data[i].key == key) {
return i + 1;
}
}
return 0;
}
// 折半查找
int BinarySearch(SeqList L, int key) {
int low = 0, high = L.length - 1, mid;
while (low <= high) {
mid = (low + high) / 2;
if (L.data[mid].key == key) {
return mid + 1;
} else if (L.data[mid].key > key) {
high = mid - 1;
} else {
low = mid + 1;
}
}
return 0;
}
```
以上代码中,`SeqSearch` 函数实现了顺序查找,返回查找到的数据元素在有序表中的位置,若未找到则返回 0;`BinarySearch` 函数实现了折半查找,返回查找到的数据元素在有序表中的位置,若未找到则返回 0。
最后,我们可以编写完整的程序代码,实现输入一个包含数据元素的有序表和要查找的数据元素,输出结果为查找的数据元素在有序表中的位置,否则输出结果为 0。具体代码如下:
```c
#include <stdio.h>
#define MAXSIZE 100
typedef struct {
int key;
// 其他数据元素
} ElementType;
typedef struct {
ElementType data[MAXSIZE];
int length;
} SeqList;
// 顺序查找
int SeqSearch(SeqList L, int key) {
int i;
for (i = 0; i < L.length; i++) {
if (L.data[i].key == key) {
return i + 1;
}
}
return 0;
}
// 折半查找
int BinarySearch(SeqList L, int key) {
int low = 0, high = L.length - 1, mid;
while (low <= high) {
mid = (low + high) / 2;
if (L.data[mid].key == key) {
return mid + 1;
} else if (L.data[mid].key > key) {
high = mid - 1;
} else {
low = mid + 1;
}
}
return 0;
}
int main() {
SeqList L;
int i, key, res;
printf("请输入有序表的长度:");
scanf("%d", &L.length);
printf("请输入有序表的数据元素:");
for (i = 0; i < L.length; i++) {
scanf("%d", &L.data[i].key);
}
printf("请输入要查找的数据元素:");
scanf("%d", &key);
res = BinarySearch(L, key);
if (res == 0) {
printf("未找到 %d\n", key);
} else {
printf("%d 在有序表中的位置是 %d\n", key, res);
}
return 0;
}
```
输入一个包含数据元素的有序表(关键字即数据元素的值),接着输入要查找的数据元素,程序输出查找结果。例如,输入以下数据:
```
请输入有序表的长度:6
请输入有序表的数据元素:1 3 5 7 9 11
请输入要查找的数据元素:5
```
则程序输出:
```
5 在有序表中的位置是 3
```
阅读全文