m0_62375273 2022-07-10 14:37 采纳率: 81.3%
浏览 129
已结题

数据结构的算法复杂度

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

img

img

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

C语言

运行结果及报错内容

如图所示

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

已有大概思路

我想要达到的结果

完成程序正常运行

  • 写回答

3条回答 默认 最新

  • 关注

    用类似快排的分治法来找,因为中位数需要分偶数和奇数两种情况,数组长度为奇数情况下比较简单,找中间的数输出就可以了;数组长度为偶数的情况下稍微复杂一些,需要找出(n-1)/2和(n-1)/2+1两个数据的平均值。找到中间数(n-1)/2后,找到后面n/2个数的最小值进行计算。

    img

    代码:

    #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 swap(Student a[],int m,int n)
    {
        Student t=a[m];
        a[m] = a[n];
        a[n] = t;
    }
    
    void partition(Student A[],int left,int right,int *pos)
    {
        Student data=A[left];
        int i;
        for(*pos=left,i=left+1;i<=right;i++)
        {
            if(A[i].score < data.score)
            {
                (*pos)++;
                swap(A,*pos,i);
            }
        }
        swap(A,left,*pos);
    }
    
    double Getmid(Student A[],int n)
    {
        int left=0;
        int right=n-1;
        int mid=(left+right)/2;
        int pos,count=1;
        while(1)
        {
            partition(A,left,right,&pos);
            
            if(pos==mid)
                break;
            else if(pos>mid)
                right=pos-1;
            else
                left=pos+1; 
        }
    
        if(n%2==1)
            return A[mid].score;
        else
        {
            //求后面几个数的最小值
            int mx = mid+1;
            for(int t=mid+2;t<n;t++)
            {
                if(A[t].score < A[mx].score)
                    mx = t;
            }
            return (A[mid].score + A[mx].score)/2;
        }
    
        
    }
    
    
    
    
    //录入数据
    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);
        }
    }
    
    
    
    int main()
    {
        LinkList ls;
        input(&ls);
    
        //double A[10]={2.2,2.3,1.2,7.8,4.4,3.2};
    
    
        double dd = Getmid(ls.stu,ls.nmb);
    
        printf("中位数:%.2f\n",dd);
    
    
        return 0;
    }
    
    
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(2条)

报告相同问题?

问题事件

  • 系统已结题 7月18日
  • 已采纳回答 7月10日
  • 创建了问题 7月10日

悬赏问题

  • ¥15 seatunnel-web使用SQL组件时候后台报错,无法找到表格
  • ¥15 fpga自动售货机数码管(相关搜索:数字时钟)
  • ¥15 用前端向数据库插入数据,通过debug发现数据能走到后端,但是放行之后就会提示错误
  • ¥30 3天&7天&&15天&销量如何统计同一行
  • ¥30 帮我写一段可以读取LD2450数据并计算距离的Arduino代码
  • ¥15 飞机曲面部件如机翼,壁板等具体的孔位模型
  • ¥15 vs2019中数据导出问题
  • ¥20 云服务Linux系统TCP-MSS值修改?
  • ¥20 关于#单片机#的问题:项目:使用模拟iic与ov2640通讯环境:F407问题:读取的ID号总是0xff,自己调了调发现在读从机数据时,SDA线上并未有信号变化(语言-c语言)
  • ¥20 怎么在stm32门禁成品上增加查询记录功能