数据结构的算法复杂度

Question

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

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

C语言

运行结果及报错内容

如图所示

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

已有大概思路

我想要达到的结果

完成程序正常运行

Answer 1

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

代码：

#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;
}