c - 数组的长度比需要的长

Question

在下面的程序中，

    int * accepted_ids = (int *) malloc(sizeof(int)*N);
    double * accepted_scores = (double *)malloc(sizeof(double)*N);

    int * unaccepted_ids = (int *) malloc(sizeof(int)*N);
    double * unaccepted_scores = (double *) malloc(sizeof(double)*N);

这些内存分配正在为每个创建大小为 N 的数组，即使所需元素的数量远低于 N。

由于程序使用随机数生成器，我们无法事先知道每个生成器需要多少内存。

我该如何解决这个难题？

(max. 5 points)
A single dimension array SCORES stores scores of N university candidates they gained at high school. Indexes of elements of the array are the IDs of these candidates. The university accepts applications from candidates with the average score greater or equal to 4.0.

Write a short program that will display:

• The list of accepted candidates with their ID number and their average score. • The list of unaccepted candidates with their ID numbers and their average score • The number of accepted and unaccepted candidates. • Results sorted in ascending order

The average scores should be calculated from a range <2,6> using random numbers generator. The total number of candidates should be passed to the program as command line parameter. Make your program sensible to the input of wrong parameters.

Using struct is not allowed.

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <errno.h>

// This function tests whether it is possible 
// to convert a string into integer or not.
//
// This function is needed to check the 
// input argument otherwise if you type 
//      C:\>myapp.exe abc
// your program will crash.
int is_integer(const char * s)
{
    char * endptr;
    int radix = 10;//decimal number system

    // try to convert s to integer
    strtol(s, &endptr, radix);

    errno = 0;
    // if this conditions are fullfilled,
    // that means, s can't be converted 
    // to an integer.
    if (endptr == s || *endptr != '\0')
    {
        // argument must be an integer value        
        return 0; // failure
    }
    if (errno == ERANGE)
    {
        // int argument out of range        
        return 0; // failure
    }

    return 1; //success
}

// This function is needed to convert
// a string to an integer value.
int string_to_integer(const char * s)
{
    char * endptr;
    int radix = 10;//decimal number system

    // convert s to integer
    return strtol(s, &endptr, radix);
}

// Generte a random number between M and N.
//
// This function is needed coz rand() can 
// generate only integer values.
double round_between_m_to_n(double M, double N)
{
    return M + (rand() / (RAND_MAX / (N - M)));
}

// This is Bubble sort algorithm
// This is implemented as a user-defined function, 
// coz, you have to use this twice.
// First for accepted scores, 
// then for unaccepted scores.
void sort(int * ids, double * scores, int count)
{
    for (int i = 0; i < count; i++)
    {
        for (int j = 0; j < i; j++)
        {
            if (scores[i] < scores[j])
            {
                // Swap scores
                double temp = scores[i];
                scores[i] = scores[j];
                scores[j] = temp;

                // Swap ids
                int temp2 = ids[i];
                ids[i] = ids[j];
                ids[j] = temp2;
            }
        }
    }
}

// This function is to print ids and scores
// as a table.
// This is implemented as a user-defined function, 
// coz, you have to use this twice.
// First for accepted scores, 
// then for unaccepted scores.
void print(int * ids, double * scores, int count)
{

    printf("id\tavg_score\n");
    printf("-------------------\n");
    for (int i = 0; i < count; i++)
    {
        printf("%i\t%.1f\n", ids[i], scores[i]);
    }
}

int main(int argc, char ** argv)
{
    // Program can proceed only if 
    // the # of arguments is exactly 2. 
    // The 1st arg is always app-name.
    if (argc != 2)
    {
        printf("insufficient argument\n");
        return EXIT_FAILURE;
    }

    int N = 0;
    int accepted_scores_count = 0;
    int unaccepted_scores_count = 0;
    double acceptance_threshhold = 4.0;

    if (!is_integer(argv[1]))
    {
        printf("incorrect argument type\n");
        return EXIT_FAILURE;
    }
    else
    {
        N = string_to_integer(argv[1]);
        printf("Total %d students\n", N);
    }

    // Pair of variables are needed to
    // keep track of student-ids.
    // Otherwise, you can't tell what id a 
    // student has when data are sorted.
    int * accepted_ids = (int *)malloc(sizeof(int)*N);
    double * accepted_scores = (double *)malloc(sizeof(double)*N);

    int * unaccepted_ids = (int *)malloc(sizeof(int)*N);
    double * unaccepted_scores = (double *)malloc(sizeof(double)*N);

    //Initialize random seed.
    //If you don't use this, rand() will generate
    //same values each time you run the program.
    srand(time(NULL));

    // Simultaneously generate scores, ids, and
    // store them is sepaerate arrays.
    for (int i = 0; i < N; i++)
    {
        int id = i;
        double score = round_between_m_to_n(2, 6);

        // if the score is greater than or
        // equal to 4.0...
        if (score >= acceptance_threshhold)
        {
            accepted_ids[accepted_scores_count] = i;
            accepted_scores[accepted_scores_count] = score;

            accepted_scores_count++;
        }
        // ... otherwise they are unaccepted.
        else
        {
            unaccepted_ids[unaccepted_scores_count] = i;
            unaccepted_scores[unaccepted_scores_count] = score;

            unaccepted_scores_count++;
        }
    }

    // sort accepted students
    sort(accepted_ids, accepted_scores, accepted_scores_count);
    // sort unaccpeted students
    sort(unaccepted_ids, unaccepted_scores, unaccepted_scores_count);

    // print accepted students
    printf("\naccepted  students\n");
    print(accepted_ids, accepted_scores, accepted_scores_count);

    // print unaccepted students
    printf("\nunaccepted  students\n");
    print(unaccepted_ids, unaccepted_scores, unaccepted_scores_count);

    printf("\nEnd of program.\n");

    free(accepted_ids);
    free(accepted_scores);
    free(unaccepted_ids);
    free(unaccepted_scores);


    return EXIT_SUCCESS;
}

Answer 1

因为您知道要为其生成数据的学生人数，所以您可以为所有 学生使用数据数组:

    int * all_ids = (int *)malloc(sizeof(int)*N);
    double * all_scores = (double *)malloc(sizeof(int)*N);

然后正常生成数据，保持计数，但将数据分配到 all_* 数组中:

    for (int i = 0; i < N; i++)
    {
        int id = i;
        double score = round_between_m_to_n(2, 6);

        all_ids[i] = id;
        all_scores[i] = score;

        // if the score is greater than or
        // equal to 4.0...
        if (score >= acceptance_threshhold)
        {
            accepted_scores_count++;
        }
        // ... otherwise they are unaccepted.
        else
        {
            unaccepted_scores_count++;
        }
    }

因为您知道区分录取学生的阈值，所以您可以稍后拆分这些。

现在您拥有所有数据，以及被录取和未被录取的学生人数。使用此信息，您可以为已录取和未录取的学生分配数组:

    int * accepted_ids = (int *)malloc(sizeof(int) * accepted_scores_count);
    double * accepted_scores = (double *)malloc(sizeof(double) * accepted_scores_count);

    int * unaccepted_ids = (int *)malloc(sizeof(int) * unaccepted_scores_count);
    double * unaccepted_scores = (double *)malloc(sizeof(double) * unaccepted_scores_count);

使用 for 循环(减去数据生成，因为已经完成)，像您最初所做的那样，将数据分类为接受和未接受的数组:

    for (int i = 0, j = 0; (i+j) < N;)
    {
        int id = all_ids[i+j];
        double score = all_scores[i+j];

        // if the score is greater than or
        // equal to 4.0...
        if (score >= acceptance_threshhold)
        {
            accepted_ids[i] = id;
            accepted_scores[i] = score;

            i++;
        }
        // ... otherwise they are unaccepted.
        else
        {
            unaccepted_ids[j] = id;
            unaccepted_scores[j] = score;

            j++;
        }
    }

之后，您继续正常排序和打印数据。您还必须记住释放 all_* 数组。