C 结构快速排序字符串

Question

我对快速排序有疑问。它应该用作者姓名对书籍进行排序。这是代码

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

struct book {
    char title[80];
    char autor[80];
    int pages;
};

int comparator (const void * a, const void *b)
{
    struct book * ia=(struct book*)a;
    struct book * ib=(struct book*)b;
    return (strcmp(ia->autor,ib->autor));
}

int main(int argc, char ** argv)
{
    int c = 2;
    int i;

    //Pointer to array of struct pointers, malloc for 2 structs
    struct book **ptr = (struct book*)malloc(c*sizeof(struct book));
    for(i=0;i<c;i++) {
            //malloc for every struct
            //also, if I'm doing it right?
            ptr[i] = (struct book*)malloc(sizeof(struct book));
            printf("Title: ");
            scanf("%s",ptr[i]->title);
            printf("Autor: ");
            scanf("%s",ptr[i]->autor);
    }
    for(i=0;i<c;i++) {
            printf("Before Quick sort Autor: %s, Title: %s \n",ptr[i]->autor,ptr[i]->title);
      }
    qsort(ptr,2, sizeof(struct book), comparator);
          printf("QSORT DONe...\n\n");
      for(i=0;i<c;i++) {
            printf("TEST");
            printf("After quick sort: Autor: %s, Title: %s \n",ptr[i]->autor,ptr[i]->title);
      }

    return 0;
}

所以程序可以编译，但它只到达 printf("TEST");（TEST 打印在屏幕上）然后崩溃。我用那种快速排序破坏了我的数组吗？或者会发生什么？

另外你可以检查我的代码是否正常？特别是 mallocs（真的）在我的代码中做了什么，因为我不确定我是否正确使用了它们。

谢谢！

Answer 1

显示为要更改的点（对于指向结构指针数组的指针（但不需要双指针））如下

#include <string.h>
struct book * ia=*(struct book**)a; struct book * ib=*(struct book**)b;
struct book **ptr = malloc(c*sizeof(struct book*));
qsort(ptr,2, sizeof(struct book*), comparator);

也许是你想要的版本

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

struct book {
    char title[80];
    char autor[80];
    int pages;
};
int comparator (const void * a, const void *b)
{
    struct book * ia=(struct book*)a;
    struct book * ib=(struct book*)b;
    return (strcmp(ia->autor,ib->autor));
}

int main(int argc, char ** argv)
{
    int c = 2;
    int i;

    struct book *ptr = malloc(c*sizeof(struct book));
    for(i=0;i<c;i++) {
            printf("Title: ");
            scanf("%s",ptr[i].title);
            printf("Autor: ");
            scanf("%s",ptr[i].autor);
    }
    for(i=0;i<c;i++) {
            printf("Before Quick sort Autor: %s, Title: %s \n",ptr[i].autor,ptr[i].title);
    }
    qsort(ptr,2, sizeof(struct book), comparator);
          printf("QSORT DONe...\n\n");
    for(i=0;i<c;i++) {
            printf("TEST");
            printf("After quick sort: Autor: %s, Title: %s \n",ptr[i].autor,ptr[i].title);
    }

    return 0;
}

Answer 2

有一些小问题和困惑：

1) 您错过了 #include <string.h> strcmp

2) 你正在分配一个指针数组，这可能不是你想要做的。 C 中的数组是指向数组第一个元素的指针，因此如果您使用 (struct book*) malloc(n * sizeof(struct book)) 进行分配，您已经在分配 n 本书的完整数组。您还可以分配指向书籍的指针数组，在这种情况下，您需要将每个指针分配给新分配的书籍。

所以您可以执行以下任一操作（并且您的代码混合了两者）：

struct book** ptr = (struct book**) malloc(c * sizeof(struct book*));

struct book* ptr = (struct book*) malloc(c * sizeof(struct book));

在第一种情况下，您需要分配新书（因此循环内的 malloc 才有意义）

第二种情况，你直接使用数组就可以了，我改了下面的代码就是这样做的：

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

struct book {
  char title[80];
  char autor[80];
  int pages;
};

int comparator(const void * a, const void *b)
{
  struct book * ia = (struct book*)a;
  struct book * ib = (struct book*)b;
  return (strcmp(ia->autor, ib->autor));
}

int main(int argc, char ** argv)
{
  int c = 3;
  int i;

  //Pointer to array of struct pointers, malloc for 2 structs
  struct book* ptr = (struct book*) malloc(c*sizeof(struct book));

  if (ptr == NULL) {
    printf("Could not allocate data\n");
    return 1;
  }

  for (i = 0;i<c;i++) {
    printf("Title: ");
    scanf("%s", ptr[i].title);
    printf("Autor: ");
    scanf("%s", ptr[i].autor);
  }
  for (i = 0;i < c;i++) {
    printf("Before Quick sort Autor: %s, Title : %s \n", ptr[i].autor, ptr[i].title);
  }
  qsort(ptr, c, sizeof(struct book), comparator);
  printf("QSORT Done...\n\n");
  for (i = 0;i<c;i++) {
    printf("TEST");
    printf("After quick sort: Autor: %s, Title: %s \n", ptr[i].autor, ptr[i].title);
  }

  free(ptr);

  return 0;
}

3) 最后，测试 malloc 的结果并在不再需要时调用 free 是一个好习惯。

Answer 3

我将给你一个答案，它会保留 ptr 的定义，它是指向 struct book 的指针的指针，并且还会更改你的代码的最少量。这意味着我们将分配一个指向 struct book 的指针数组，然后为该数组中的每个指针分配一个实际对象 struct book.

第一个 malloc 将分配 c 指向 struct book 的指针数组：

struct book **ptr = (struct book**)malloc(c*sizeof(struct book*));

使用 malloc 分配对象 struct book 的 for 循环是正确的。

第二个更正是在 qsort() 调用处。我们正在排序指向 struct book 的指针，而不是实际对象 struct book.

qsort(ptr,4, sizeof(struct book*), comparator);

然后比较功能需要修复。由于我们正在对指针进行排序，因此比较函数将 return 指向指向 struct book 的指针。所以我们需要取消引用指向 struct book:

的指针

int comparator (const void * a, const void *b)
{
    struct book* ia=*(struct book**)a;
    struct book* ib=*(struct book**)b;
    return (strcmp(ia->autor,ib->autor));
}

C 结构快速排序字符串

C struct quick sort for strings

c

malloc

struct

quicksort