实现线性表的查找操作。 顺序查找。要求:顺序表的第0个元素赋值为要查找的关键字key,并从顺序表最后一个元素,依次向前查找。 折半查找。要求:对顺序表中关键字按非递减顺序排列后,使用折半查找算法进行查找。 输入说明: 第1行输入顺序表中关键字的个数n; 第2行依次输入顺序表中各关键字的值; 第3行输入要查找的关键字key。 输出说明 输出比较次数,及查找是否成功。(其中的标点符号为中文全角标点符号)
时间: 2024-03-15 18:43:58 浏览: 50
2、 掌握线性表的基本操作:初始化,插入,删除,查找,判空,求线性表长度等运算在顺序存储结构和链式存储结构上的实现
5星 · 资源好评率100%
好的,以下是针对你的问题的解答:
顺序查找的实现代码如下:
```c++
int Sequential_Search(int a[], int n, int key) //a为数组,n为数组长度,key为要查找的关键字
{
int i;
a[0] = key; //将a[0]赋值为要查找的关键字
for (i = n; a[i] != key; i--); //从数组最后一个元素开始向前查找
return i; //返回查找到的位置,若查找失败返回0
}
```
折半查找的实现代码如下:
```c++
int Binary_Search(int a[], int n, int key)
{
int low, high, mid;
low = 1; //定义查找范围的左端点
high = n; //定义查找范围的右端点
while (low <= high)
{
mid = (low + high) / 2; //取中间位置
if (key < a[mid])
high = mid - 1; //在左半边继续查找
else if (key > a[mid])
low = mid + 1; //在右半边继续查找
else
return mid; //查找成功,返回位置
}
return 0; //查找失败,返回0
}
```
输入格式如下:
```
7
1 3 5 7 9 11 13
5
```
输出格式如下:
```
3,success
```
其中,3为比较次数,success表示查找成功,若查找失败则输出“0,failed”。
阅读全文