写一个c语言的代码 要求(1) 编写顺序表(为整型数组)的顺序查找法,以及有序顺序表的二分查找的实现函数。 (2) 编写主函数main,创建具有n (n≥10)个随机元素(0-999之间)的顺序表R1,用顺序查找法查找某个值(由用户输入)出现的位置,统计查找成功(或不成功)的比较次数。将R1存储为具有n个随机元素(0-999之间)的有序顺序表(要求元素不重复,可正序或逆序),用二分查找法查找某个值(由用户输入)出现的位置,统计查找成功(或不成功)的比较次数。
时间: 2024-01-02 08:01:43 浏览: 105
好的,以下是您所需求的C语言代码:
```c
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX_NUM 1000
typedef struct {
int *data;
int length;
} SeqList;
void initSeqList(SeqList *list, int n) {
list->data = (int *)malloc(n * sizeof(int));
list->length = n;
srand((unsigned)time(NULL));
for (int i = 0; i < n; i++) {
list->data[i] = rand() % MAX_NUM;
}
}
int sequentialSearch(SeqList list, int key, int *count) {
for (int i = 0; i < list.length; i++) {
(*count)++;
if (list.data[i] == key) {
return i;
}
}
return -1;
}
int binarySearch(SeqList list, int key, int *count) {
int low = 0, high = list.length - 1, mid;
while (low <= high) {
(*count)++;
mid = (low + high) / 2;
if (list.data[mid] == key) {
return mid;
} else if (list.data[mid] < key) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1;
}
void sortSeqList(SeqList *list) {
for (int i = 0; i < list->length - 1; i++) {
for (int j = i + 1; j < list->length; j++) {
if (list->data[i] > list->data[j]) {
int temp = list->data[i];
list->data[i] = list->data[j];
list->data[j] = temp;
}
}
}
}
int main() {
SeqList R1;
int n, key, count = 0;
printf("Enter the number of elements in R1 (n >= 10): ");
scanf("%d", &n);
initSeqList(&R1, n);
printf("R1: [");
for (int i = 0; i < R1.length; i++) {
printf("%d", R1.data[i]);
if (i != R1.length - 1) {
printf(", ");
}
}
printf("]\n");
printf("Enter the key to search: ");
scanf("%d", &key);
int index = sequentialSearch(R1, key, &count);
if (index == -1) {
printf("Sequential search failed. Total comparisons: %d\n", count);
} else {
printf("Sequential search succeeded. Index: %d, comparisons: %d\n", index, count);
}
sortSeqList(&R1);
printf("Sorted R1: [");
for (int i = 0; i < R1.length; i++) {
printf("%d", R1.data[i]);
if (i != R1.length - 1) {
printf(", ");
}
}
printf("]\n");
printf("Enter the key to search: ");
scanf("%d", &key);
count = 0;
index = binarySearch(R1, key, &count);
if (index == -1) {
printf("Binary search failed. Total comparisons: %d\n", count);
} else {
printf("Binary search succeeded. Index: %d, comparisons: %d\n", index, count);
}
free(R1.data);
return 0;
}
```
该程序定义了一个顺序表的结构体`SeqList`,并实现了以下函数:
- `initSeqList`:用于初始化一个随机生成的顺序表。
- `sequentialSearch`:用于实现顺序查找。
- `binarySearch`:用于实现二分查找。
- `sortSeqList`:用于将顺序表排序。
在`main`函数中,程序首先让用户输入顺序表的长度`n`,然后用`initSeqList`函数初始化一个随机生成的顺序表,并输出该顺序表。接着,程序让用户输入要查找的关键字`key`,并用`sequentialSearch`函数进行顺序查找,统计比较次数并输出结果。然后,程序对顺序表进行排序,再次输出排序后的顺序表。最后,程序让用户输入要查找的关键字`key`,并用`binarySearch`函数进行二分查找,统计比较次数并输出结果。
注意:以上代码中的`count`参数用于统计比较次数。在实际应用中,统计比较次数是一个非常重要的指标,可以用来评估算法的效率。
阅读全文