建立一个任意类型数据构成的顺序表,根据用户输入的查找值,使用不同的方法实现顺序表的查找。请用c语言写出这道题的完整代码
时间: 2024-03-27 15:39:57 浏览: 24
好的,这是完整的代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct {
int *data; // 指向存储数据的数组
int length; // 当前顺序表的长度
int maxsize; // 顺序表的最大容量
} SqList;
// 初始化顺序表
void init(SqList *L, int maxsize) {
L->data = (int *) malloc(maxsize * sizeof(int));
L->length = 0;
L->maxsize = maxsize;
}
// 插入元素
void insert(SqList *L, int value) {
if(L->length == L->maxsize) {
printf("顺序表已满,无法插入!\n");
return;
}
L->data[L->length] = value;
L->length++;
}
// 线性查找
int search(SqList L, int key) {
int i;
for(i = 0; i < L.length; i++) {
if(L.data[i] == key) {
return i;
}
}
return -1; // 如果没找到,返回-1
}
// 二分查找
int binary_search(SqList L, int key) {
int low = 0;
int high = L.length - 1;
while(low <= high) {
int mid = (low + high) / 2;
if(L.data[mid] == key) {
return mid;
} else if(L.data[mid] < key) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1; // 如果没找到,返回-1
}
int main() {
int i, n, value, key, pos;
SqList L;
printf("请输入顺序表的最大容量:");
scanf("%d", &n);
init(&L, n);
printf("请输入%d个元素:\n", n);
for(i = 0; i < n; i++) {
scanf("%d", &value);
insert(&L, value);
}
printf("请输入要查找的值:");
scanf("%d", &key);
pos = search(L, key);
if(pos != -1) {
printf("线性查找:元素%d在顺序表中的位置是%d\n", key, pos + 1);
} else {
printf("线性查找:元素%d不在顺序表中\n", key);
}
pos = binary_search(L, key);
if(pos != -1) {
printf("二分查找:元素%d在顺序表中的位置是%d\n", key, pos + 1);
} else {
printf("二分查找:元素%d不在顺序表中\n", key);
}
return 0;
}
```
代码中,我们先定义了 `SqList` 结构体来表示顺序表,然后实现了初始化、插入、线性查找和二分查找等函数。在 `main()` 函数中,我们通过输入顺序表的元素来初始化顺序表,并输入要查找的值,然后分别使用线性查找和二分查找来查找该值,并输出查找结果。
注意:由于本题要求建立任意类型数据构成的顺序表,因此可以将 `SqList` 结构体中的 `int` 类型改为其他数据类型。另外,二分查找的前提是顺序表必须是有序的。