pta7-2 数据结构实验三 图的广度优先搜索

本题要求实现图的广度优先搜索算法，基本思想是从某个顶点开始，先访问其所有的邻接点，然后按照访问顺序继续访问它们的邻接点，直到所有顶点都被访问为止。

广度优先搜索通常使用队列来实现，从起始顶点开始，首先将它入队，然后将它的所有邻接点入队。接着，队首元素出队并访问，然后将它的所有未被访问过的邻接点入队。重复上述过程，直到队列为空为止。

具体实现时，可以使用邻接表来表示图，使用一个数组来记录每个顶点是否被访问过，使用一个队列来存储待访问的顶点。

下面是一个C++的实现示例：

相关问题

pta6-2 数据结构实验 根据带虚结点的先序序列创建二叉树

好的，我可以为你解答这个问题。

根据带虚结点的先序序列创建二叉树的步骤如下：

1. 读入先序序列，包括虚结点和实结点。如果当前读入的结点是虚结点，则不需要创建对应的结点，直接跳过。
2. 如果当前读入的结点是实结点，则创建一个新的二叉树结点，将其值设置为当前读入的值。
3. 判断当前结点的父节点是否存在，如果存在，则将当前结点作为父节点的左子节点或右子节点，具体是左子节点还是右子节点取决于先序序列中下一个结点的类型。
4. 将当前结点加入到一个栈中保存，以便后续处理。
5. 如果下一个结点是虚结点，则直接跳过；如果是实结点，则重复步骤2-4，直到先序序列结束。
6. 返回根节点。

下面是一个示例代码，用于根据带虚结点的先序序列创建二叉树：

#include <iostream>
#include <stack>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

TreeNode* createTree(vector<int>& preorder) {
    stack<TreeNode*> st;
    TreeNode* root = new TreeNode(preorder[0]);
    st.push(root);
    for (int i = 1; i < preorder.size(); i++) {
        if (preorder[i] == -1) {
            continue;
        }
        TreeNode* curr = new TreeNode(preorder[i]);
        if (i % 2 == 1) {
            st.top()->left = curr;
        } else {
            st.top()->right = curr;
        }
        st.push(curr);
        while (!st.empty() && st.top()->right != NULL) {
            st.pop();
        }
    }
    return root;
}

int main() {
    vector<int> preorder = {1, 2, -1, 3, 4, 5, -1, -1, -1, -1, -1};
    TreeNode* root = createTree(preorder);
    return 0;
}

在这个示例代码中，我们使用了一个栈来保存当前处理到的结点，以及其祖先结点。对于每个读入的结点，我们先判断其类型（虚结点还是实结点），然后根据其在先序序列中的位置，将其作为左子节点或右子节点加入到其父节点中。如果当前结点的右子节点已经存在，说明其已经处理完毕，我们可以将其从栈中弹出。最后，我们返回根节点即可。

pta7-2 二分搜索

### PTA 实验 7-2 二分搜索

#### 题目描述
在一个有序数组中，给定目标值进行查找。如果存在该目标值，则返回其索引；否则返回 `-1` 表明未找到。

输入格式如下：
- 第一行包含两个整数 `n` 和 `target`，分别表示数组长度和待查的目标值。
- 接下来的一行包含 `n` 个升序排列的整数，代表数组中的元素。

输出格式为单个整数，即目标值的位置索引（假设第一个位置索引为 `0`），如果没有找到则输出 `-1`[^3]。

#### 解题思路
为了高效地解决这个问题，可以采用经典的二分查找算法来降低时间复杂度到 O(log n)，而不是线性扫描整个列表。以下是具体的实现方法：

定义左右边界指针分别为 `left=0` 和 `right=n-1`；
当左界不超过右界时循环执行以下操作：
- 计算中间位置 `mid=(left+right)//2`
- 如果位于 mid 的数值正好等于 target 则直接返回 mid 值作为结果
- 若当前区间内不存在此数，则依据比较情况调整新的搜索范围直到收敛或确认无解为止
- 当最终未能定位至确切匹配项时应报告失败并退出程序运行

def binary_search(nums, target):
    left, right = 0, len(nums) - 1
    
    while left <= right:
        mid = (left + right) // 2
        
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
            
    return -1

对于特殊情况处理，比如空数组或者只有一个元素的情况，在正式进入主逻辑前应当先行检测以简化后续流程控制。