c - 对结构体指针数组进行排序

Question

我有一个函数可以按字母顺序对结构指针数组进行排序，如下所示:

 void insertionSortAlpha(candidate* person[], int lo, int hi) { 
        candidate* insertItem;
        insertItem = malloc(sizeof(candidate));
        insertItem->name = malloc(25*sizeof(char));
        insertItem->numVotes=malloc(sizeof(int));   

        int i;
        for(i=lo+1; i<=hi; i++) { 
            insertItem = person[i];
            int k = i - 1;
            while (k > 0 && strcmp(insertItem->name, person[k]->name) < 0) { 
                person[k + 1] = person[k];
                --k;
            }
            person[k + 1] = insertItem;
        }
    free(insertItem->numVotes);
    free(insertItem->name);
    free(insertItem);}

然后我调用该函数并像这样释放内存。名称是从文件中填充的。打印时，它总是跳过数组中第三个元素的名称和编号。它还给了我一个无效的指针错误。为什么会发生这种情况？

insertionSortAlpha(Person, 0, 9);
  printf("\n\n");
  printf("Sorted Alphabetically\n");
  for (i=0; i<10;i++) {
    printf("%s =  %d votes \n", Person[i]->name, *Person[i]->numVotes);
  }
 for (i =0; i<10; i++) { 
    free(Person[i]->numVotes);
    free(Person[i]->name);
    free(Person[i]);
  }

Answer 1

创建 MCVE ( Minimal, Complete, Verifiable Example ) 的工作量比应有的要多一些，但此代码基本上验证了我的 comment 。 :

Your assignment to insertItem in the loop leaks the memory allocated before the loop. I don't think you need the memory allocation or release at all in the sort function. In fact, I'm sure you don't; you free the last item that was stored in insertItem after the loop, which then gives you problems later when you access (and free) already freed memory.

分配单个整数的数据结构是浪费的(尤其是在 64 位机器上)；它应该是结构的普通 int 成员。如果您要处理固定大小的名称，您也可以将名称放入固定大小的数组中。然而，这是一个小的改进(并且没有实现)。整数指针使得使用候选结构来存储内部数据变得不方便。我本可以使用 C99“复合文字”，例如 &(int){ 8000 }，但这需要更多解释(并且数组不能再是 static，并且对 new_candidate() 的调用必须修改)。

您还需要将 while 循环中的限制从 k > 0 更改为 k >= 0；除此之外，Henrietta 仍位于列表的前面。

这是一个或多或少的最小 MCVE，其中已修复:

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

typedef struct candidate
{
    char *name;
    int  *numVotes;
} candidate;

static
void insertionSortAlpha(candidate *person[], int lo, int hi)
{
    candidate *insertItem;
    //insertItem = malloc(sizeof(candidate));
    //insertItem->name = malloc(25 * sizeof(char));
    //insertItem->numVotes = malloc(sizeof(int));

    int i;
    for (i = lo + 1; i <= hi; i++)
    {
        insertItem = person[i];
        int k = i - 1;
        // k > 0 --> k >= 0
        while (k >= 0 && strcmp(insertItem->name, person[k]->name) < 0)
        {
            person[k + 1] = person[k];
            --k;
        }
        person[k + 1] = insertItem;
    }
    //free(insertItem->numVotes);
    //free(insertItem->name);
    //free(insertItem);
}

typedef struct BaseData
{
    char *name;
    int   numVotes;
} BaseData;

static void *emalloc(size_t size, const char *func)
{
    void *vp = malloc(size);
    if (vp == 0)
    {
        fprintf(stderr, "Failed to allocate %zu bytes of memory in %s()\n", size, func);
        exit(EXIT_FAILURE);
    }
    return vp;
}

static candidate *new_candidate(const char *name, int votes)
{
    candidate *person = emalloc(sizeof(*person), __func__);
    person->name = emalloc(25, __func__);
    assert(strlen(name) < 25);
    strcpy(person->name, name);
    person->numVotes = emalloc(sizeof(int), __func__);
    *person->numVotes = votes;
    return person;
}

int main(void)
{
    candidate *Person[10];
    static const BaseData people[] =
    {
        { "Henrietta",  8000 },
        { "Eric",       5000 },
        { "Beatrice",   2000 },
        { "Diana",      4000 },
        { "Francesca",  6000 },
        { "George",     7000 },
        { "Ian",        9000 },
        { "Janice",    10000 },
        { "Adrian",     1000 },
        { "Charles",    3000 },
    };

    for (int i = 0; i < 10; i++)
        Person[i] = new_candidate(people[i].name, people[i].numVotes);

    insertionSortAlpha(Person, 0, 9);
    printf("\n\n");
    printf("Sorted Alphabetically\n");
    for (int i = 0; i < 10; i++)
    {
        printf("%-15s = %6d votes\n", Person[i]->name, *Person[i]->numVotes);
    }

    for (int i = 0; i < 10; i++)
    {
        free(Person[i]->numVotes);
        free(Person[i]->name);
        free(Person[i]);
    }

    return 0;
}

示例输出:

Sorted Alphabetically
Adrian          =   1000 votes
Beatrice        =   2000 votes
Charles         =   3000 votes
Diana           =   4000 votes
Eric            =   5000 votes
Francesca       =   6000 votes
George          =   7000 votes
Henrietta       =   8000 votes
Ian             =   9000 votes
Janice          =  10000 votes

祝贺珍妮丝赢得选举。