数据结构 实验报告-6

第一题 寻找大富翁：

一、实验内容：

胡润研究院的调查显示，截至2017年底，中国个人资产超过1亿元的高净值人群达15万人。假设给出N个人的个人资产值，请快速找出资产排前M位的大富翁。

二、实验目的：

握选择、插入、冒泡三种排序方法，根据实际问题选择合适的排序算法；

三、程序清单：

▶

Code

#include<stdio.h>
#include<malloc.h>

int main(int argc, char **argv)
{
    int N, M;
    int num = 0;
    scanf("%d %d", &N, &M);
    int i = 0, j = 0;
    long long *Max;
    Max = (long long*)malloc(sizeof(long long) * N);

    for (i = 0; i < N; i++){
        scanf("%lld", Max + i);
    }

    for (i = 0; i < M; i++){
        for ( j = 0; j < N; j++){
            if (*(Max + num) < *(Max + j)){
                num = j;
            }
        }
        if (i && *(Max + num))
            printf(" ");
        if(*(Max + num))
            printf("%lld", *(Max + num));
        *(Max + num) = 0;
        num = 0;
    }
  
    return 0;
}

四、调试步骤：

1. 输入题中的测试数据；
2. 检查程序输出与预期输出的差距，分析错误在程序的哪个部分；
3. 更改程序，再次测试，直到程序输出符合预期；

第二题 奥运排行榜：

一、实验内容：

每年奥运会各大媒体都会公布一个排行榜，但是细心的读者发现，不同国家的排行榜略有不同。比如中国金牌总数列第一的时候，中国媒体就公布“金牌榜”；而美国的奖牌总数第一，于是美国媒体就公布“奖牌榜”。如果人口少的国家公布一个“国民人均奖牌榜”，说不定非洲的国家会成为榜魁…… 现在就请你写一个程序，对每个前来咨询的国家按照对其最有利的方式计算它的排名。

二、实验目的：

掌握结构体排序，熟悉基本排序算法；

三、程序清单：

▶

Code

#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#include<string.h>

struct jp{
    double jin;
    double jiang;
    double people;
    double aver_jin;
    double aver_jiang;
} a[300];

int main()
{
    int N,M,i,j;
    int b[500];
    int p0,p1,p2,p3;
    scanf("%d%d",&N,&M);

    for(i=0;i<N;i++){
        scanf("%lf%lf%lf",&a[i].jin,&a[i].jiang,&a[i].people);
        a[i].aver_jin=a[i].jin/a[i].people;
        a[i].aver_jiang=a[i].jiang/a[i].people;
    }

    for(i=0;i<M;i++)
        scanf("%d",&b[i]);
    
    for(i=0;i<M;i++){
        p0=0;p1=0;p2=0;p3=0;
        for(j=0;j<N;j++){
            if(a[b[i]].jin>=a[j].jin)  p0++;
            if(a[b[i]].jiang>=a[j].jiang)  p1++;
            if(a[b[i]].aver_jin>=a[j].aver_jin) p2++;
            if(a[b[i]].aver_jiang>=a[j].aver_jiang) p3++;
        }
        int max=p0,t=1;
        if(max<p1){max=p1;t=2;}
        if(max<p2){max=p2;t=3;}
        if(max<p3){max=p3;t=4;}
        if(i==0)
            printf("%d:%d",N-max+1,t);
        else 
            printf(" %d:%d",N-max+1,t);
    }
}

四、调试步骤：

1. 输入题中的测试数据；
2. 检查程序输出与预期输出的差距，分析错误在程序的哪个部分；
3. 更改程序，再次测试，直到程序输出符合预期；

第三题 PTA排名汇总：

一、实验内容：

计算机程序设计能力考试（Programming Ability Test，简称PAT）旨在通过统一组织的在线考试及自动评测方法客观地评判考生的算法设计与程序设计实现能力，科学的评价计算机程序设计人才，为企业选拔人才提供参考标准（网址）。 每次考试会在若干个不同的考点同时举行，每个考点用局域网，产生本考点的成绩。考试结束后，各个考点的成绩将即刻汇总成一张总的排名表。 现在就请你写一个程序自动归并各个考点的成绩并生成总排名表。

二、实验目的：

掌握结构体排序，熟悉基本排序算法；

三、程序清单：

▶

Code

#include <stdio.h>
#include <string.h>

typedef struct {
    char ID[14];//考号
    int score;//成绩
    int rank;//总排名
    int Num;//考场号
    int rank1;//场内排名
} Stu_Info;
Stu_Info stu[30000];

int cmp(Stu_Info a,Stu_Info b) {
    if(a.score==b.score)
        return strcmp(b.ID,a.ID);
    return a.score-b.score;
}

int Partition(Stu_Info stu[],int start,int end) {
    Stu_Info pivot=stu[start];
    int i=start,j=end;
    while(i<j) {
        while(i<j) {
            if(cmp(stu[j],pivot)>0) {
                stu[i]=stu[j];
                break;
            }
            j--;
        }
        while(i<j) {
            if(cmp(stu[i],pivot)<0) {
                stu[j]=stu[i];
                break;
            }
            i++;
        }
    }
    stu[i]=pivot;
    return i;
}

void sort(Stu_Info stu[],int start,int end) {
    if(start<end) {
        int t=Partition(stu,start,end);
        sort(stu,start,t-1);
        sort(stu,t+1,end);
    }
}

void rank(Stu_Info stu[],int start,int end,int type) {
    int i=start,cnt=1,pos=cnt;
    if(type==1) {
        stu[i].rank1=cnt;
        for(i=start+1; i<=end; i++) {
            pos++;
            if(stu[i].score!=stu[i-1].score)
                cnt=pos;
            stu[i].rank1=cnt;
        }
    } else {
        stu[i].rank=cnt;
        for(i=start+1; i<=end; i++) {
            pos++;
            if(stu[i].score!=stu[i-1].score)
                cnt=pos;
            stu[i].rank=cnt;
        }
    }
 
}

int main() {
    int n,j,pos,i,k=0,m;
    scanf("%d",&n);
    for(i=0; i<n; i++) {
        pos=k;
        scanf("%d",&m);
        for(j=0; j<m; j++) {
            scanf("%s %d",stu[k].ID,&stu[k].score);
            stu[k].Num=i+1;
            k++;
        }
        sort(stu,pos,k-1);
        rank(stu,pos,k-1,1);
    }
    sort(stu,0,k-1);
    rank(stu,0,k-1,0);
    printf("%d\n",k);
    for(i=0; i<k; i++) {
        printf("%s %d %d %d\n",stu[i].ID,stu[i].rank,stu[i].Num,stu[i].rank1);
    }
}

四、调试步骤：

1. 输入题中的测试数据；
2. 检查程序输出与预期输出的差距，分析错误在程序的哪个部分；
3. 更改程序，再次测试，直到程序输出符合预期；