三、实验内容 编写一个名为chazhao.cpp.的程序代码。 实现以下功能： （1）创建一个含有10个元素的有序序列。在键盘输入数据 (2）顺序查找（有哨兵位）。 (3）递归折半查找。 (4）非递归播半查找。 要求以上功能写成函数段，只写一个主函数调用以上功能来验证函数。

在C++中，你可以按照以下步骤编写一个名为`chazhao.cpp`的程序，实现顺序查找、递归折半查找和非递归二分查找的功能：

#include <iostream>
using namespace std;

// 1. 创建有序序列 (含哨兵位)
const int SIZE = 11; // 带头哨兵，实际元素数为SIZE - 1
int arr[SIZE] = {0}; // 初始化为0，后续填充用户输入
void inputArray() {
    for(int i = 1; i <= SIZE; ++i) {
        cout << "请输入第" << i << "个元素: ";
        cin >> arr[i];
        // 确保数组有序，如果输入大于已存在的元素，则交换位置
        if (arr[i] > arr[i - 1]) {
            swap(arr[i], arr[i - 1]);
        }
    }
}

// 2. 顺序查找 (有哨兵位)
bool linearSearch(int target, int& index) {
    for (index = 1; index <= SIZE; ++index) {
        if (arr[index] == target) {
            return true;
        }
    }
    return false;
}

// 3. 递归折半查找
int recursiveBinarySearch(int target, int left, int right) {
    if (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target)
            return mid;
        else if (arr[mid] < target)
            return recursiveBinarySearch(target, mid + 1, right);
        else
            return recursiveBinarySearch(target, left, mid - 1);
    }
    return -1; // 如果未找到目标，返回 -1
}

// 4. 非递归二分查找
int nonRecursiveBinarySearch(int target) {
    int left = 1, right = SIZE;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target)
            return mid;
        else if (arr[mid] < target)
            left = mid + 1;
        else
            right = mid - 1;
    }
    return -1;
}

int main() {
    inputArray();
    
    int target;
    cout << "请输入你要查找的目标值: ";
    cin >> target;

    bool foundByLinearSearch = linearSearch(target, SIZE); // 使用索引来检查是否找到
    int resultByRecursiveSearch = recursiveBinarySearch(target, 1, SIZE);
    int resultByNonRecursiveSearch = nonRecursiveBinarySearch(target);

    if (foundByLinearSearch) {
        cout << "在顺序查找中找到了目标值 (" << target << ")，其位置在第" << SIZE << "个元素处.\n";
    } else {
        cout << "顺序查找中未找到目标值.\n";
    }

    if (resultByRecursiveSearch != -1) {
        cout << "递归折半查找在数组第" << resultByRecursiveSearch+1 << "位置找到了目标值 (" << target << ").\n";
    } else {
        cout << "递归折半查找未找到目标值.\n";
    }

    if (resultByNonRecursiveSearch != -1) {
        cout << "非递归二分查找在数组第" << resultByNonRecursiveSearch+1 << "位置找到了目标值 (" << target << ").\n";
    } else {
        cout << "非递归二分查找未找到目标值.\n";
    }

    return 0;
}

在这个程序中，我们首先通过`inputArray`函数获取用户的输入并保持数组有序。然后分别使用顺序查找、递归折半查找和非递归二分查找来搜索目标值，并输出结果。