用C语言,编程实现有序顺序表的折半查找(升序和降序),键盘上输入的形式实现
时间: 2024-02-09 11:11:32 浏览: 42
以下是使用 C 语言,实现有序顺序表的折半查找的示例代码,可以根据用户输入的顺序自动判断升序或降序:
```c
#include <stdio.h>
#define MAXSIZE 100 // 定义顺序表的最大长度
// 定义顺序表结构体
typedef struct {
int data[MAXSIZE]; // 存储数据的数组
int length; // 当前顺序表的长度
} SqList;
// 初始化顺序表
void InitList(SqList *L) {
L->length = 0;
}
// 插入元素
int Insert(SqList *L, int x) {
if (L->length >= MAXSIZE) {
return 0; // 表满,插入失败
}
L->data[L->length++] = x; // 插入元素到表尾
return 1; // 插入成功
}
// 打印顺序表
void PrintList(SqList L) {
printf("当前顺序表:");
for (int i = 0; i < L.length; i++) {
printf("%d ", L.data[i]);
}
printf("\n");
}
// 折半查找(升序)
int BinarySearchAsc(SqList L, int x) {
int low = 0, high = L.length - 1, mid;
while (low <= high) {
mid = (low + high) / 2;
if (L.data[mid] == x) {
return mid; // 查找成功,返回元素下标
} else if (L.data[mid] < x) {
low = mid + 1; // 去右边查找
} else {
high = mid - 1; // 去左边查找
}
}
return -1; // 查找失败,返回-1
}
// 折半查找(降序)
int BinarySearchDesc(SqList L, int x) {
int low = 0, high = L.length - 1, mid;
while (low <= high) {
mid = (low + high) / 2;
if (L.data[mid] == x) {
return mid; // 查找成功,返回元素下标
} else if (L.data[mid] > x) {
low = mid + 1; // 去右边查找
} else {
high = mid - 1; // 去左边查找
}
}
return -1; // 查找失败,返回-1
}
int main() {
SqList L;
InitList(&L);
// 获取用户输入的顺序表元素
int n;
printf("请输入顺序表的长度:");
scanf("%d", &n);
printf("请输入%d个有序的整数:", n);
for (int i = 0; i < n; i++) {
int x;
scanf("%d", &x);
Insert(&L, x);
}
PrintList(L);
// 获取用户输入的查找元素
int x, index;
printf("请输入要查找的元素:");
scanf("%d", &x);
// 根据顺序表是否升序来决定使用哪种折半查找算法
if (L.data[0] <= L.data[L.length - 1]) {
index = BinarySearchAsc(L, x);
} else {
index = BinarySearchDesc(L, x);
}
if (index == -1) {
printf("查找失败,元素%d不存在\n", x);
} else {
printf("查找成功,元素%d的下标为%d\n", x, index);
}
return 0;
}
```
以上代码中,我们使用了 `InitList` 函数来初始化顺序表,使用 `Insert` 函数来插入元素,使用 `PrintList` 函数来打印顺序表,使用 `BinarySearchAsc` 函数来实现升序顺序表的折半查找,使用 `BinarySearchDesc` 函数来实现降序顺序表的折半查找。然后,根据用户输入的顺序表元素的顺序来决定使用哪种折半查找算法,在查找成功或失败后,输出相应的提示信息。