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;
    }
    
    
    
    
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论 编辑记录
  • 有问必答小助手 2022-06-25 23:09
    关注
    您好,我是有问必答小助手,您的问题已经有小伙伴帮您解答,感谢您对有问必答的支持与关注!
    PS:问答VIP年卡 【限时加赠:IT技术图书免费领】,了解详情>>> https://vip.csdn.net/askvip?utm_source=1146287632
    评论
查看更多回答(1条)

报告相同问题?

问题事件

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

悬赏问题

  • ¥15 div editable中的光标问题
  • ¥15 mysql报错1415Not allowed to return a result set from a trigger 不知如何修改
  • ¥60 Python输出Excel数据整理,算法较为复杂
  • ¥15 回答几个问题 关于数据库
  • ¥15 51单片机串口通信问题,未完成且要修改
  • ¥15 百鸡问题 c++编程问题(相关搜索:输出数据)
  • ¥30 如何在CMD中设置代理
  • ¥15 我有一块薛定谔的硬盘
  • ¥15 微信小游戏开发2D碰撞检测问题
  • ¥30 MapReduce案例实践(实验过程需要截图加文字)