排序算法练习及应用..

Question

（1）一组学生信息包括：学号（int型），姓名（字符串），成绩（float型），这组学生信息输入时按学号从小到大排序，请在这组学生信息中查找指定学号的学生的信息（输出该学号学生的姓名和成绩）。
要求：1.分别使用带监视哨的顺序查找和折半查找完成题目要求。
2.两个算法分别给出

Answer 1

以下内容由CHATGPT及阿里嘎多学长共同生成、有用望采纳：

---

基于您提供的信息，以下是解决这个问题的具体步骤：

1. 定义学生信息结构体：首先，您需要定义一个结构体Student来存储学生的学号、姓名和成绩。

2. 输入学生信息：由于学号已经按从小到大排序，您可以直接从用户那里获取学生信息，并存储到一个Student类型的数组中。

3. 实现带监视哨的顺序查找：

   • 将数组的最后一个元素之后添加一个哨兵元素，该元素的学号设置为一个不可能的值（例如：-1）。
   • 从数组的第二个元素开始（因为第一个元素后是哨兵），逐个与目标学号进行比较，直到找到匹配的学号或遍历到哨兵元素。

4. 实现折半查找：

   • 由于学号已经排序，您可以使用折半查找算法。
   • 初始化左右指针，左边界为0，右边界为数组长度减1。
   • 计算中间索引，并检查中间元素的学号是否等于目标学号。
   • 如果等于，返回中间索引；如果目标学号小于中间元素的学号，更新右边界为中间索引减1；如果大于，更新左边界为中间索引加1。
   • 重复这个过程直到找到目标学号或左右指针相遇。

5. 编写查找函数：为两种查找方法分别编写函数，接受学生数组、数组长度和目标学号作为参数，并返回找到的学生的索引。

6. 输出学生信息：在主函数中，根据用户输入的学号调用相应的查找函数。如果找到了学生，使用返回的索引打印学生的姓名和成绩；如果没有找到，输出相应的提示信息。

7. 测试代码：编写测试用例，确保您的代码能够正确地找到学生信息，并且在学号不存在的情况下能够给出正确的提示。

8. 优化和调试：根据测试结果对代码进行必要的优化和调试。

9. 编写注释：在代码中添加必要的注释，说明每个函数和重要代码段的功能。

10. 代码示例：以下是根据上述步骤编写的代码示例：

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef struct {
    int id;
    char name[50];
    float score;
} Student;

// 带监视哨的顺序查找函数
int sequentialSearchWithSentinel(Student students[], int n, int targetId) {
    Student sentinel = {-1, "", -1.0};
    students[n] = sentinel; // 添加监视哨
    for (int i = 0; i < n; i++) {
        if (students[i].id == targetId) {
            return i;
        }
    }
    return -1; // 未找到
}

// 折半查找函数
int binarySearch(Student students[], int n, int targetId) {
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (students[mid].id == targetId) {
            return mid;
        } else if (students[mid].id < targetId) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1; // 未找到
}

int main() {
    int n, searchId;
    printf("Enter the number of students: ");
    scanf("%d", &n);

    Student students[n];
    printf("Enter student information (ID, Name, Score):\n");
    for (int i = 0; i < n; i++) {
        scanf("%d %s %f", &students[i].id, students[i].name, &students[i].score);
    }

    printf("Enter the student ID to search: ");
    scanf("%d", &searchId);

    int indexWithSentinel = sequentialSearchWithSentinel(students, n - 1, searchId);
    if (indexWithSentinel != -1) {
        printf("Student found with sentinel: ID = %d, Name = %s, Score = %.2f\n",
               students[indexWithSentinel].id, students[indexWithSentinel].name, students[indexWithSentinel].score);
    }

    int indexBinarySearch = binarySearch(students, n - 1, searchId);
    if (indexBinarySearch != -1) {
        printf("Student found with binary search: ID = %d, Name = %s, Score = %.2f\n",
               students[indexBinarySearch].id, students[indexBinarySearch].name, students[indexBinarySearch].score);
    }

    return 0;
}

请注意，这段代码需要在实际环境中编译和运行，以确保其正确性。同时，您可能需要根据实际情况调整输入和输出的格式。