数据结构的算法设计和复杂度

Question

问题遇到的现象和发生背景

问题相关代码，请勿粘贴截图

c或者c++

运行结果及报错内容

设计算法

我的解答思路和尝试过的方法

我已用python解决了一遍

我想要达到的结果

用C或者C++完成算法设计并分析复杂度

Answer 1

只是学号按顺序排好了，那么只能遍历链表，所以时间复杂度是O(n)，遍历过程中，只用到1个临时变量，所以空间复杂度是O(1);
代码如下：

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#define N 1000
typedef struct _stu
{
    int id; //学号
    char name[20];//姓名
    char sex;//性别
    char pro[20]; //专业
    int grade; //班级
    float score; //绩点
}Student;

typedef struct _node
{
    Student stu[N];
    int nmb; //实际学生数量
}LinkList;



//录入数据
void input(LinkList* list)
{
    int i, n;
    printf("请输入学生数量：");
    scanf("%d", &n);
    list->nmb = n;
    for (i = 0; i < n; i++)
    {
        printf("请输入学生%d的学号：", i + 1);
        scanf("%d", &list->stu[i].id);
        printf("请输入学生%d的姓名：", i + 1);
        scanf("%s", list->stu[i].name);
        getchar(); //吸收回车符
        printf("请输入学生%d的性别：", i + 1);
        scanf("%c", &list->stu[i].sex);
        printf("请输入学生%d的专业：", i + 1);
        scanf("%s", list->stu[i].pro);
        printf("请输入学生%d的班级：", i + 1);
        scanf("%d", &list->stu[i].grade);
        printf("请输入学生%d的绩点：", i + 1);
        scanf("%f", &list->stu[i].score);
    }
}

//显示学生信息
void showStu(Student stu)
{
    printf("学号：%d\n", stu.id);
    printf("姓名：%s\n", stu.name);
    printf("性别：%c\n", stu.sex);
    printf("专业：%s\n", stu.pro);
    printf("班级：%d\n", stu.grade);
    printf("绩点：%.2f\n", stu.score);
}

int main()
{
    int i, n;
    int score;
    LinkList list;
    input(&list); //录入数据，按照学号升序排序录入
    printf("请输入要查找的绩点：");
    scanf("%f", &score);
    
    for (i = 0; i < list.nmb; i++)
    {
        if (list.stu[i].score == score)
            showStu(list.stu[i]);
    }

    
    return 0;
}