建立一个c语言程序可以在VS2022运行,建立一个有序的顺序表,利用折半查找方法查找元素。要求能进行多次查找,并对每次查找输出结果,成功则输出在有序表中的位置,失败则输出“无此元素”
时间: 2024-03-21 10:40:37 浏览: 70
好的,下面是建立有序顺序表并进行折半查找的 C 语言代码:
```c
#include <stdio.h>
#define MAXSIZE 100 // 定义最大容量
typedef struct {
int data[MAXSIZE];
int length;
} SeqList;
// 初始化有序顺序表
void init(SeqList *L) {
L->length = 0;
}
// 插入元素
int insert(SeqList *L, int x) {
int i, j;
if (L->length >= MAXSIZE) {
return 0; // 表满,插入失败
}
// 找到插入位置
for (i = 0; i < L->length && L->data[i] < x; i++);
// 将插入位置后的元素后移
for (j = L->length - 1; j >= i; j--) {
L->data[j + 1] = L->data[j];
}
L->data[i] = x;
L->length++;
return 1; // 插入成功
}
// 折半查找
int binarySearch(SeqList L, int x) {
int left = 0, right = L.length - 1, mid;
while (left <= right) {
mid = (left + right) / 2;
if (L.data[mid] == x) {
return mid; // 找到元素,返回下标
} else if (L.data[mid] < x) {
left = mid + 1; // 在右半部分查找
} else {
right = mid - 1; // 在左半部分查找
}
}
return -1; // 未找到元素
}
int main() {
SeqList L;
init(&L); // 初始化有序顺序表
int i, x;
printf("请输入要插入的 %d 个元素:\n", MAXSIZE);
for (i = 0; i < MAXSIZE; i++) {
scanf("%d", &x);
if (!insert(&L, x)) {
printf("表已满,插入失败!\n");
break;
}
}
printf("插入后的有序顺序表为:\n");
for (i = 0; i < L.length; i++) {
printf("%d ", L.data[i]);
}
printf("\n请输入要查找的元素:\n");
while (scanf("%d", &x) != EOF) {
int pos = binarySearch(L, x);
if (pos >= 0) {
printf("%d 在有序表中的位置是 %d\n", x, pos + 1);
} else {
printf("无此元素!\n");
}
printf("请输入要查找的元素:\n");
}
return 0;
}
```
该程序通过 `init` 函数初始化一个有序顺序表,再通过 `insert` 函数插入元素。插入元素时,先找到插入位置,再将插入位置后的元素后移,最后将元素插入到指定位置。折半查找通过 `binarySearch` 函数实现,该函数采用循环方式,每次将查找区间缩小一半,直到找到目标元素或查找区间为空为止。
在 `main` 函数中,先输入 MAXSIZE 个元素插入有序顺序表,再通过循环输入要查找的元素,调用 `binarySearch` 函数查找元素,并输出结果。
希望这个代码能够帮助你解决问题!
阅读全文