m0_62375273 2022-06-23 18:26 采纳率: 81.3%
浏览 161
已结题

数据结构的算法复杂度

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

img

img

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

C或C++

运行结果及报错内容

按要求复杂度出结果

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

我已经用python完成了一遍

我想要达到的结果

C或C++顺利运行并达到问题所求

  • 写回答

2条回答 默认 最新

  • 关注

    二分查找的时间复杂度是O(logn),假设学生信息按照学号升序拍好录入,
    运行结果:

    img

    代码如下:

    #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;
    
    //数组以升序排列时,二分法查找x,返回在顺序表中stu数组中的下标
    int binSearch(LinkList *list,int x)
    {
        int low, high, mid;
        int n = list->nmb;
        low = 0;
        high = n - 1;
        while (low <= high)
        {
            mid = (low + high) / 2;
            if (x < list->stu[mid].id)
                high = mid - 1;
            else if (x > list->stu[mid].id)
                low = mid + 1;
            else
                return mid;
        }
        return -1;
    }
    
    //录入数据
    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 id;
        LinkList list;
        input(&list); //录入数据,按照学号升序排序录入
        printf("请输入要查找的学号:");
        scanf("%d", &id);
        n = binSearch(&list,id );
        if (n == -1)
            printf("查无此人!\n");
        else
            showStu(list.stu[n]);
        return 0;
    }
    
    
    
    
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论 编辑记录
查看更多回答(1条)

报告相同问题?

问题事件

  • 系统已结题 7月3日
  • 已采纳回答 6月25日
  • 创建了问题 6月23日

悬赏问题

  • ¥15 wannier复现图像时berry曲率极值点与高对称点严重偏移
  • ¥15 利用决策森林为什么会出现这样·的问题(关键词-情感分析)
  • ¥15 DispatcherServlet.noHandlerFound No mapping found for HTTP request with URI[/untitled30_war_e
  • ¥15 使用deepspeed训练,发现想要训练的参数没有梯度
  • ¥15 寻找一块做为智能割草机的驱动板(标签-stm32|关键词-m3)
  • ¥15 信息管理系统的查找和排序
  • ¥15 基于STM32,电机驱动模块为L298N,四路运放电磁传感器,三轮智能小车电磁组电磁循迹(两个电机,一个万向轮),怎么用读取的电磁传感器信号表示小车所在的位置
  • ¥15 如何解决y_true和y_predict数据类型不匹配的问题(相关搜索:机器学习)
  • ¥15 PB中矩阵文本型数据的总计问题。
  • ¥15 MATLAB卫星二体模型仿真