C++代码 学生宿舍管理系统 ~顺序查找~ ~折半查找~ ~分块查找~ 完成按序号查询

以下是一个简单的学生宿舍管理系统的 C++ 代码，使用了顺序查找、折半查找和分块查找三种不同的查找方式，并且可以按照学生的序号进行查询。

#include <iostream>
#include <algorithm>

using namespace std;

const int MAXN = 1000; // 最大学生数
const int BLOCK_SIZE = 10; // 块大小

// 学生信息结构体
struct Student {
    int id; // 学号
    string name; // 姓名
    int dormitory; // 宿舍号
};

// 学生信息数组
Student students[MAXN];
int n; // 学生数

// 按学号从小到大排序
bool cmp(const Student& s1, const Student& s2) {
    return s1.id < s2.id;
}

// 顺序查找
int sequential_search(int id) {
    for (int i = 0; i < n; i++) {
        if (students[i].id == id) {
            return i;
        }
    }
    return -1; // 没有找到
}

// 折半查找
int binary_search(int id) {
    int l = 0, r = n - 1;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (students[mid].id == id) {
            return mid;
        }
        else if (students[mid].id < id) {
            l = mid + 1;
        }
        else {
            r = mid - 1;
        }
    }
    return -1; // 没有找到
}

// 分块查找
int block_search(int id) {
    // 先按学号从小到大排序
    sort(students, students + n, cmp);
    // 计算块数
    int num_blocks = (n + BLOCK_SIZE - 1) / BLOCK_SIZE;
    // 构建块信息数组
    int block_data[num_blocks][2];
    for (int i = 0; i < num_blocks; i++) {
        int l = i * BLOCK_SIZE;
        int r = min((i + 1) * BLOCK_SIZE, n) - 1;
        block_data[i][0] = students[l].id;
        block_data[i][1] = students[r].id;
    }
    // 在块信息数组中查找
    int block_index = -1;
    for (int i = 0; i < num_blocks; i++) {
        if (block_data[i][0] <= id && id <= block_data[i][1]) {
            block_index = i;
            break;
        }
    }
    if (block_index == -1) {
        return -1; // 没有找到
    }
    // 在块内顺序查找
    int l = block_index * BLOCK_SIZE;
    int r = min((block_index + 1) * BLOCK_SIZE, n) - 1;
    for (int i = l; i <= r; i++) {
        if (students[i].id == id) {
            return i;
        }
    }
    return -1; // 没有找到
}

int main() {
    // 读入学生信息
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> students[i].id >> students[i].name >> students[i].dormitory;
    }
    // 查询
    int id_to_find;
    cin >> id_to_find;
    int result = block_search(id_to_find);
    if (result == -1) {
        cout << "Not found" << endl;
    }
    else {
        cout << students[result].name << " " << students[result].dormitory << endl;
    }
    return 0;
}

在以上代码中，我们定义了一个 `Student` 结构体来存储学生的信息，包括学号、姓名和宿舍号。我们还定义了三个查找函数 `sequential_search`、`binary_search` 和 `block_search`，分别使用了顺序查找、折半查找和分块查找三种不同的查找方式。在 `main` 函数中，我们读入学生信息，然后输入一个要查询的学号，最后调用 `block_search` 函数进行查询，如果找到了对应的学生，则输出其姓名和宿舍号，否则输出 "Not found"。

注意，在 `block_search` 函数中，我们先按学号从小到大排序，然后将学生信息分成若干个块，每个块的大小为 `BLOCK_SIZE`，然后在块信息数组中查找，最后在块内进行顺序查找。这种方法可以降低查找的时间复杂度，尤其是当数据量较大时。