Сортировка массива структур в C

Question

Нам было присвоено задание в классе для сортировки массива структур. После сдачи задания мы обсудили вопрос о сортировке с помощью указателей массивов, чтобы отсортировать его, поскольку это было более эффективным, чем то, как это делали большинство людей.

Я решил попробовать и сделать это так же, но я столкнулся с некоторыми проблемами, которые я не смог решить.

http://pastebin.com/Cs3y39yu

#include <stdint.h> 
#include <stdio.h> 
#include <stdlib.h> 
#include <sys/stat.h> 

typedef struct stage2{//standard dec of the struct field 
    char need; 
     double ring; 
     char fight[8]; 
     int32_t uncle; 
     char game; 
     double war; 
     int8_t train; 
     uint32_t beds; 
     float crook; 
     int32_t feast; 
     int32_t rabbits; 
     int32_t chin; 
     int8_t ground; 
     char veil; 
     uint32_t flowers; 
     int8_t adjustment; 
     int16_t pets; 
} stage2; 

void usage(){//usage method to handle areas 
     fprintf(stderr,"File not found\n");//prints to stderr 
     exit(1);//exits the program 
} 

int needS(const void *v1, const void *v2) 
{ 
    const stage2 *p1 = v1; 
    const stage2 *p2 = v2; 
     printf("%c %c \n",p1->need,p2->need); 
    return 0; 
} 


int main(int argc, char** argv){ 
     if(argc != 3){//checks for a input files, only 1 
      usage();//if not runs usage 
    } 
    int structSize = 60;//size of structs in bytes, sizeof() doesnt return correct val 
    char* fileName = argv[1]; //pull input filename 
    FILE *file = fopen(fileName, "r");//opens in read mode 
    fseek(file, 0, SEEK_END); //goes to end of file 
    long fileSize = ftell(file); //saves filesize 
    char *vals = malloc(fileSize); //allocates the correct size for array based on its filesize 
    fseek(file, 0, SEEK_SET); //returns to start of file 
    fread(vals, 1, fileSize, file); //reads the file into char array vals 
    fclose(file); //closes file 
    int structAmount = fileSize/structSize; //determines amount of structs we need 
    stage2 mainArray[structAmount]; //makes array of structs correct size 


    int j;//loop variables 
    int i; 


    printf("need, ring, fight, uncle, game, war, train, beds, crook, feast, rabbits, chin, ground, veil, flowers, adjustment, pets\n");//prints our struct names 

    for(i = 0; i < structAmount; i ++){//initialises the array vals 
     mainArray[i].need = *(&vals[0+(i*60)]); 
     mainArray[i].ring = *((double *)&vals[1+(i*60)]); 
     for(j = 0;j<9;j++){ 
      mainArray[i].fight[j] = *(&vals[j+9+(i*60)]); 
     } 
     mainArray[i].uncle = *((int32_t *)&vals[17+(i*60)]); 
     mainArray[i].game = *(&vals[21+(i*60)]); 
     mainArray[i].war = *((double *)&vals[22+(i*60)]); 
     mainArray[i].train = *((int8_t *)&vals[30+(i*60)]); 
     mainArray[i].beds = *((uint32_t *)&vals[31+(i*60)]); 
     mainArray[i].crook = *((float *)&vals[35+(i*60)]); 
     mainArray[i].feast = *((int32_t *)&vals[39+(i*60)]); 
     mainArray[i].rabbits = *((int32_t *)&vals[43+(i*60)]); 
     mainArray[i].chin = *((int32_t *)&vals[47+(i*60)]); 
     mainArray[i].ground = *((int8_t *)&vals[51+(i*60)]); 
     mainArray[i].veil = *(&vals[52+(i*60)]); 
     mainArray[i].flowers = *((uint32_t *)&vals[53+(i*60)]); 
     mainArray[i].adjustment = *((int8_t *)&vals[57+(i*60)]); 
     mainArray[i].pets = *((int16_t *)&vals[58+(i*60)]);  
    } 

    for(i = 0; i < structAmount; i ++){//prints 
     printf("%c, %f, %s, %d, %c, %f, %d, %u, %f, %d, %d, %d, %d, %c, %u, %d, %d \n", 
     mainArray[i].need,mainArray[i].ring,mainArray[i].fight,mainArray[i].uncle,mainArray[i].game,mainArray[i].war,mainArray[i].train, 
     mainArray[i].beds,mainArray[i].crook,mainArray[i].feast,mainArray[i].rabbits,mainArray[i].chin,mainArray[i].ground,mainArray[i].veil, 
     mainArray[i].flowers,mainArray[i].adjustment,mainArray[i].pets);//prints 

    } 
    free(vals);//frees the memory we allocated to vals 

    stage2 *array = malloc(structAmount * structSize); 

    for(i = 0; i < structAmount; i ++){ 
     array[i] = mainArray[i]; 
    } 
    printf("Before Sort\n\n"); 
    for(i = 0; i < structAmount; i ++){ 
      printf("%c, %f, %s, %d, %c, %f, %d, %u, %f, %d, %d, %d, %d, %c, %u, %d, %d \n", 
    array[i].need,array[i].ring,array[i].fight,array[i].uncle,array[i].game,array[i].war,array[i].train, 
    array[i].beds,array[i].crook,array[i].feast,array[i].rabbits,array[i].chin,array[i].ground,array[i].veil, 
    array[i].flowers,array[i].adjustment,array[i].pets);//prints 
    } 
    qsort(array, structAmount,structSize,needS); 


    printf("After Sort\n\n"); 
    for(i = 0; i < structAmount; i ++){ 
      printf("%c, %f, %s, %d, %c, %f, %d, %u, %f, %d, %d, %d, %d, %c, %u, %d, %d \n", 
    array[i].need,array[i].ring,array[i].fight,array[i].uncle,array[i].game,array[i].war,array[i].train, 
    array[i].beds,array[i].crook,array[i].feast,array[i].rabbits,array[i].chin,array[i].ground,array[i].veil, 
    array[i].flowers,array[i].adjustment,array[i].pets);//prints 
    } 

    FILE *my_file = fopen(argv[2], "wb"); 
    for(i = 0; i < structAmount; i ++){ 
      fwrite(&mainArray[i].need, sizeof(char), 1, my_file); 
      fwrite(&mainArray[i].ring, sizeof(double), 1, my_file); 
      fwrite(&mainArray[i].fight, sizeof(char[8]), 1, my_file); 
      fwrite(&mainArray[i].uncle, sizeof(int32_t), 1, my_file); 
      fwrite(&mainArray[i].game, sizeof(char), 1, my_file); 
      fwrite(&mainArray[i].war, sizeof(double), 1, my_file); 
      fwrite(&mainArray[i].train, sizeof(int8_t), 1, my_file); 
      fwrite(&mainArray[i].beds, sizeof(uint32_t), 1, my_file); 
      fwrite(&mainArray[i].crook, sizeof(float), 1, my_file); 
      fwrite(&mainArray[i].feast, sizeof(int32_t), 1, my_file); 
      fwrite(&mainArray[i].rabbits, sizeof(int32_t), 1, my_file); 
      fwrite(&mainArray[i].chin, sizeof(int32_t), 1, my_file); 
      fwrite(&mainArray[i].ground, sizeof(int8_t), 1, my_file); 
      fwrite(&mainArray[i].veil, sizeof(char), 1, my_file); 
      fwrite(&mainArray[i].flowers, sizeof(uint32_t), 1, my_file); 
      fwrite(&mainArray[i].adjustment, sizeof(int8_t), 1, my_file); 
      fwrite(&mainArray[i].pets, sizeof(int16_t), 1, my_file); 
    } 

    fclose(my_file); 

    return 0;//return statement 
} 

Существует ссылка на код, который я работал. Моя основная проблема заключается в том, что из того, что я собираю, при использовании метода сравнения сортировки needS (строка 31) для первого выполнения сортировки он должен вернуть первое поле для первых двух структур в массиве и напечатать их (я знаю, что это не действительный метод сортировки, но хотелось бы убедиться, что переменные были тем, что я ожидал). Однако это не то, что происходит; переменная p1 распечатает то, что я ожидаю, однако переменная p2 не будет. С этого момента каждое использование этого будет возвращать ненужные (я думаю) значения.

Есть ли что-нибудь, что мне не хватает или что-то не так?

Answer 1

Ваша проблема в этой строке:

int structSize = 60; //size of structs in bytes, sizeof() doesn't return correct val 

Вы ошибаетесь; sizeof() действительно возвращает правильный размер. Что бы вы ни делали, это фиктивный. Вам нужно вернуться к основам сериализации. Вам нужно будет правильно записать данные. Вы должны быть в состоянии прочитать все данные в массиве в одной операции чтения. Если на входе у вас действительно есть 60 байт на запись, у вас есть серьезные проблемы. Обратите внимание, что структура структуры в памяти тратит 7 байтов на большинство систем (3 на некоторых) между элементами char need; и .

Answer 2

Функция needS должна вернуть значение, подходящее для сортировки элементов в массиве.

int needS(const void *v1, const void *v2) 
{ 
    const stage2 *p1 = v1; 
    const stage2 *p2 = v2; 
    printf("%c %c \n",p1->need,p2->need); 

    // Something like: 
    return (p1->need < p2->need); 
} 

Answer 3

Вы путаете «упакованный» размер структуры в вашем файле данных с массивом структуры памяти, который вы выделяете (по умолчанию struct stage2 будет иметь дополнительное дополнение для эффективного выравнивания типов данных). Эта линия здесь проблема:

stage2 *array = malloc(structAmount * structSize); 

Оно должно быть:

stage2 *array = malloc(structAmount * sizeof(stage2)); 

Ваш призыв к qsort должен быть обновлен соответственно тоже:

qsort(array, structAmount, sizeof(stage2), needS); 

Answer 4

В дополнение к другим плакаты хорошо ответы о функциях сравнения и размере структуры, вы также не сортируете указатели, что было вашим первоначальным намерением.

В вашем коде вы сортируете копию всего массива больших структур. При сортировке по указателю вы создаете вспомогательный массив указателей на исходные элементы массива, а затем сортируете эти указатели с помощью данных, на которые они указывают. Это оставит исходный массив неповрежденным.

Ваша функция сравнения должна обрабатывать указатели void * как указатели на указатели на вашу структуру. Пример (с сильно сокращенными структурами) ниже.

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

typedef struct stage2 { 
    int need; 
} stage2; 

int needS(const void *v1, const void *v2) 
{ 
    stage2 *const *p1 = v1; 
    stage2 *const *p2 = v2; 

    return ((*p1)->need - (*p2)->need) - ((*p2)->need - (*p1)->need); 
} 

int main(int argc, char **argv) 
{ 
    stage2 mainArray[] = { 
     {8}, {3}, {5}, {1}, {19}, {-2}, {8}, {0},{0}, {4}, {5}, {1}, {8} 
    }; 
    int structAmount = sizeof(mainArray)/sizeof(*mainArray); 

    int i; 

    stage2 **array = malloc(structAmount * sizeof(*array)); 

    // Assign pointers 
    for (i = 0; i < structAmount; i++) { 
     array[i] = &mainArray[i]; 
    } 

    qsort(array, structAmount, sizeof(*array), needS); 

    puts("Original"); 
    for (i = 0; i < structAmount; i++) { 
     printf("%d\n", mainArray[i].need); 
    } 

    puts(""); 
    puts("Sorted"); 
    for (i = 0; i < structAmount; i++) { 
     printf("%d\n", array[i]->need); 
    } 

    free(array); 

    return 0; 
}