编写C++程序,实现以下功能: (1) 建立一个整数构成的顺序表。 (2) 根据用户输入的查找值,实现顺序表的顺序查找。 (3) 建立一个有序的整数构成的顺序表(可直接利用前面排序实验的结果)。 (4) 根据用户输入的查找值,实现二分查找,并输出比较的元素、元素的比较次数等。要求实现递归和非递归算法。 (5) *模拟统计查找长度, 随机产生100,200,500,1000,2000等若干个随机整数,在(3)中定义的有序表中查找这些值,统计查找成功和查找不成功的平均查找长度。
时间: 2023-06-04 08:08:35 浏览: 100
好的,这是一个关于编写C程序实现顺序表查找的问题。以下是回答:
(1) 建立一个整数构成的顺序表。
可以使用数组来表示一个顺序表,例如:
int arr[MAXSIZE]; // MAXSIZE 为顺序表的最大长度
(2) 根据用户输入的查找值,实现顺序表的顺序查找。
顺序查找可以遍历整个顺序表,找到对应的元素,例如:
int search(int arr[], int key, int n) { // key 为查找的值,n 为顺序表的当前长度
int i;
for (i = 0; i < n; i++) {
if (arr[i] == key) {
return i; // 返回元素在顺序表中的下标
}
}
return -1; // 如果找不到,返回 -1
}
(3) 建立一个有序的整数构成的顺序表(可直接利用前面排序实验的结果)。
可以使用冒泡排序、插入排序、选择排序等方法将一个无序的顺序表转化为有序的顺序表,这里不再赘述。
(4) 根据用户输入的查找值,实现二分查找,并输出比较的元素、元素的比较次数等。要求实现递归和非递归算法。
非递归算法可以使用循环来实现,例如:
int binary_search(int arr[], int key, int n) { // key 为查找的值,n 为顺序表的当前长度
int low = 0, high = n - 1, mid, count = 0;
while (low <= high) {
count++;
mid = (low + high) / 2;
if (arr[mid] == key) {
printf("元素比较次数: %d\n", count);
return mid; // 返回元素在顺序表中的下标
} else if (arr[mid] < key) {
low = mid + 1;
} else if (arr[mid] > key) {
high = mid - 1;
}
}
printf("元素比较次数: %d\n", count);
return -1; // 如果找不到,返回 -1
}
递归算法可以用函数递归来实现,例如:
int binary_search_recursive(int arr[], int key, int low, int high, int* count) {
(*count)++;
if (low > high) {
printf("元素比较次数: %d\n", *count);
return -1;
}
int mid = (low + high) / 2;
if (arr[mid] == key) {
printf("元素比较次数: %d\n", *count);
return mid;
} else if (arr[mid] < key) {
return binary_search_recursive(arr, key, mid + 1, high, count);
} else if (arr[mid] > key) {
return binary_search_recursive(arr, key, low, mid - 1, count);
}
}
(5) *模拟统计查找长度, 随机产生100,200,500,1000,2000等若干个随机整数,在(3)中定义的有序表中查找这些值,统计查找成功和查找不成功的平均查找长度。
可以使用随机函数来生成随机整数,然后对每个随机整数进行查找,计算查找成功和查找不成功的平均查找长度,例如:
void test_search(int arr[], int n) { // n 为顺序表的当前长度
int random[MAXSIZE] = {0}; // 用来存储随机数
int i, key, pos, sum_found = 0, sum_not_found = 0;
float avg_found, avg_not_found;
srand((unsigned int) time(NULL)); // 初始化随机种子
for (i = 0; i < MAXSIZE; i++) { // 生成随机数
random[i] = rand() % n;
}
for (i = 0; i < MAXSIZE; i++) { // 查找随机数
key = random[i];
pos = binary_search(arr, key, n);
if (pos != -1) { // 查找成功
sum_found += pos + 1; // 累加查找长度
} else { // 查找不成功
sum_not_found += n;
}
}
avg_found = (float) sum_found / MAXSIZE; // 计算平均查找长度
avg_not_found = (float) sum_not_found / MAXSIZE;
printf("查找成功的平均查找长度: %.1f\n", avg_found);
printf("查找不成功的平均查找长度: %.1f\n", avg_not_found);
}
注意,这个问题中涉及的内容较为复杂,需要仔细地阅读和理解,为了保证程序的正确性和稳定性,请根据具体的开发需求和实际情况进行修改和完善。
相关推荐
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![txt](https://img-home.csdnimg.cn/images/20210720083642.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![ppt](https://img-home.csdnimg.cn/images/20210720083527.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)