C程序设计基础LAB14

内容纲要

1061. Sort Students

/*                                                             */
/*  DON'T MODIFY main function ANYWAY!                         */
/*                                                             */
/***************************************************************/

// ********** Specification of STUDENT **********
// No.:  long long  
// Name: char[15]
// Scores: 3 integers (0-100)
//

typedef struct {
    long long num;
    char name[15];
    int score[3];
} STUDENT;

/********** Specification of Input **********/
STUDENT* Input(int n)
/* PreCondition:
     the length of student namelist
   PostCondition:
     an pointer pointed to the array that store information of n students
*/
{ //TODO: your function definition

}

/********** Specification of Sort **********/
void Sort(STUDENT *ps, int n)
/* PreCondition:
       ps points to a Student array with n positive integers
   PostCondition:
       Array pointed by ps is sorted based on their mean scores in descending order.
       If two students have identical mean scores, the order is based on student 
       numbers in ascending order.
*/
{ //TODO: your function definition

}

#include <stdio.h>
#define N 100000

int main() {
    STUDENT* a = NULL;
    int i, n;
    scanf("%d\n", &n);

    a = Input(n);
    Sort(a, n);

    for (i = 0; i < n; i++)
        printf("%lld %s %d %d %d\n", a[i].num, a[i].name,
               a[i].score[0], a[i].score[1], a[i].score[2]);
    return 0;
}

样例

input
5
5 you 59 59 59
4 will 58 59 59
3 fail 58 58 59
2 the 58 58 58
1 exam 59 59 59
output
1 exam 59 59 59
5 you 59 59 59
4 will 58 59 59
3 fail 58 58 59
2 the 58 58 58

题解

没啥难度,写个cmp完事。

代码

typedef struct {
    long long num;
    char name[15];
    int score[3];
} STUDENT;

/********** Specification of Input **********/
STUDENT *Input(int n)
/* PreCondition:
     the length of student namelist
   PostCondition:
     an pointer pointed to the array that store information of n students
*/
{ //TODO: your function definition
    STUDENT *stu = (STUDENT *)malloc(sizeof(STUDENT) * n);
    for (int i = 0; i < n; i++)
        scanf("%lld %s %d %d %d", &stu[i].num, &stu[i].name,
            &stu[i].score[0], &stu[i].score[1], &stu[i].score[2]);
    return stu;    
}

double getMean(STUDENT stu){
    return ((double)stu.score[0]+(double)stu.score[1]+(double)stu.score[2])/3.0;
}

int cmp(const void* a, const void* b){
    STUDENT A = *(STUDENT*)a;
    STUDENT B = *(STUDENT*)b;
    if(fabs(getMean(A) - getMean(B))>0.000001){
        if(getMean(A) > getMean(B))
            return -1;
        else
            return 1;
    }
    else{
        if(A.num<B.num)
            return -1;
        else
            return 1;
    }
}

/********** Specification of Sort **********/
void Sort(STUDENT *ps, int n)
/* PreCondition:
       ps points to a Student array with n positive integers
   PostCondition:
       Array pointed by ps is sorted based on their mean scores in descending order.
       If two students have identical mean scores, the order is based on student 
       numbers in ascending order.
*/
{ //TODO: your function definition
    qsort(ps, n, sizeof(STUDENT), cmp);
}

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define N 100000

int main()
{
    STUDENT *a = NULL;
    int i, n;
    scanf("%d\n", &n);

    a = Input(n);
    Sort(a, n);

    for (i = 0; i < n; i++)
        printf("%lld %s %d %d %d\n", a[i].num, a[i].name,
               a[i].score[0], a[i].score[1], a[i].score[2]);
    return 0;
}

1062. Count Word Occurrences

Count the occurrences of different words in several lines, and output in alphabetical order.

Words can be separated with at least one of the \n, \t, (space).

Lowercase ascii letters only. Sum length of all words will not exceed $500~000$.

题解

本题包含排序+查重两步。
如果先排序,查重就可以使用线性查重,大大提高效率。
如果先查重,则查重的时间复杂度能达到O(n^2),排序也不见得快了多少。
因此如果先查重再排序,这道题目几乎没法AC,除非有巨佬会写红黑树,反正我不会。
存储方式很简单,开一个超长数组,将所有的字符串全部存在这个数组里面,用'\0'分割开,举个例子:
比如一个char str[20];
里面存放'h''e''l''l''o''\0''w''o''r''l''d''\0''a'.......'\0'
令指针char *p = str; char *p1 = p+6;
那么printf("%s %s",p,p1);的输出就是hello world。
我们开另外一个指针数组,令此数组中的每个元素指向长数组中每个字符串的起始位置,就能代表一个字符串了。然后对指针数组排序即可。
线性查重比较容易想到,一次遍历,入口为第一个元素,将入口加入结构体数组,如果碰到和这个入口一样的,那么就将入口的次数+1,如果碰到和入口不一样的,那么将入口换为新的字符串,将其加入结构体数组,循环到末尾即可。

代码

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

typedef struct myType{
    char *s;
    int time;
}Mt;

int cmp(const void* a, const void* b){
    Mt A = *(Mt*)a;
    Mt B = *(Mt*)b;
    return strcmp(A.s, B.s);
}

char arr[1000000] = {'\0'};

void myPrint(Mt *m, int length){
    for(int i = 0; i < length; i++)
        printf("%s %d\n", m[i].s, m[i].time);
}

int main(){
    int count = 0;
    Mt* m = (Mt*)malloc(sizeof(Mt)*500001);
    Mt* n = (Mt*)malloc(sizeof(Mt)*500001);
    int nlen = 0;
    int slen = 0;
    while(scanf("%s",arr+nlen+1)!=EOF){
        slen = strlen(arr+nlen+1);
        m[count].s = arr+nlen+1;
        m[count].time = 1;
        count++;
        nlen += slen+1;
    }

    qsort(m, count, sizeof(Mt), cmp);

    int cnt = 0;

    for(int i = 0; i < count; ){
        char *tmps = m[i++].s;
        n[cnt].s = tmps;
        n[cnt].time = 1;
        int flag = 0;
        if(i >= count) break;
        while(strcmp(tmps,m[i++].s)==0){
            n[cnt].time++;
            if(i >= count) {flag = 1;break;}
        }
        if(flag) break;
        cnt++;
        i--;
    }

    myPrint(n, cnt+1);

    free(m);
    free(n);
    return 0;
}

《C程序设计基础LAB14》有1条留言

肖春芸进行回复 取消回复