不使用数组对结构进行排序

Question

这似乎是一个简单的练习，但有些东西不适用于以下 qsort 算法。 struct abcSort 正确显示所有分配的值。不幸的是，qsort 没有对任何东西进行排序。

typedef int(*compfn)(const void*, const void*);

struct ABCSort
{
    int svSort[10];
    string itemSort[10];
};

struct ABCSort abcSort;

int compare(struct ABCSort*, struct ABCSort*);

void mainSort()
{   
    for (int i = 0; i < 10; i++)
    {
        abcSort.svSort[i] = 100 - i;
        abcSort.itemSort[i] = arrayREAD[i][2];
    }

    qsort( (void*)&abcSort, 10, sizeof(struct ABCSort), (compfn)compare );
}

int compare(struct ABCSort *elem1, struct ABCSort *elem2)
{
    if (elem1->svSort< elem2->svSort)
        return -1;
    else if (elem1->svSort > elem2->svSort)
        return 1;
    else
        return 0;
}

Answer 1

您似乎打算对整数数组进行排序（您的比较函数看起来像那样）。但是您实际上交给 qsort 进行排序的是指向一个结构的指针，该结构包含一个数组。

因此，您实际上要排序的是一个已初始化的结构 ABCSort 和其他 9 个未初始化的结构。这一定会失败。

您的 qsort 行应该如下所示：

qsort ((void*)&(abcsort.svsort), 10, sizeof (int), (compfn)compare);

此外，您应该更改比较函数，使其接受并处理两个指向整数的指针：

int compare (int * e1, int * e2) {
   return *e1 - *e2;
}

编辑：在您更好地解释了您想要的内容之后，请查看以下内容：

typedef int(compfn)(const void, const void*); 

#define MAXCARS 5

struct car { 
   int sortKey;
   double displacement; 
   char name[15];  /* Note I have decided this should be C */
}; 

/* This time we have an array of structs */
struct car cars [MAXCARS] = { 
   { 0, 1.9, "BMW" }, 
   { 0, 6.3, "Audi" }, 
   { 0, 0.5, "Fiat" },
   { 0, 25.0, "Humvee" },
   { 0, 0.05, "Minibike" }
};

int compare(struct car*, struct car*); 

void main(int argc, char *argv []) { 
   int i;

   for (i = 0; i < MAXCARS; i++)
       cars[i].sortKey = 100 - i;

   qsort((void *)&cars, MAXCARS, sizeof(struct car), (compfn)compare); 
} 

/* Note we are comparing struct car-s in here, based on their displacement */
int compare(struct car *elem1, struct car *elem2) { 
   return elem1->sortKey - elem2->sortKey;
}

Answer 2

您已经构建了两个整数和字符串数组，您希望按数字对它们进行排序，同时保持初始配对。这是第一个问题，您应该已经创建了 one 结构数组，每个结构包含一个数字和一个字符串，以及一个比较该结构的整数成员以获得排序顺序的函数。

您也将此问题标记为 C++，但您使用的是 qsort、数组和函数指针，类似于 C，因此我将提供两个完整的 C 程序来解决您的问题。

让我们看看，使用结构数组，您的代码会是什么样子：

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

#define MAX 6
#define CMAX 15

typedef int(*cmp_fn)(const void*, const void*);

typedef struct {
    int num;
    char str[CMAX];
} numABC;

int comp_struct(const numABC *lhs, const numABC *rhs ) { 
    if ( lhs->num < rhs->num ) 
        return -1; 
    if ( lhs->num > rhs->num ) 
        return 1; 
    return 0;
} 

int main(void) {

    numABC myArray[MAX] = { {6, "cat"}, {4, "dog"}, {8, "panter"},
                         {2, "red fish"}, {1, "hawk"}, {6, "snake"} };
    int i;

    // sort the array of structs by int member
    qsort(myArray, MAX, sizeof(numABC), (cmp_fn)comp_struct);

    // print out the sorted array
    printf("\nSort by numbers:\n");
    for ( i = 0; i < MAX; ++i ) {
        printf("%d %s\n",myArray[i].num,myArray[i].str);
    }

    return 0;
}

如果您想使用此代码，但您有几个数组，一种选择是转换这些数组：

int nums[MAX] = {6,4,8,2,1,3};
char str[MAX][CMAX] = {"cat","dog","panter","red fish","hawk","snake"};
int i;

// create the array of structs from the two arrays
numABC myArray[MAX];
for ( i = 0; i < MAX; ++i ) {
    myArray[i].num = nums[i];
    strcpy(myArray[i].str, str[i]);
}

对两个不同的数组进行排序的另一种选择（保持两者之间的配对或对齐）是使用一种更复杂的方法，该方法包括对索引数组进行排序。为了保持两个原始数组之间的关系，我将不得不使用可以在比较函数内部访问的全局变量。对索引进行排序后，原始数组将相应更改。

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

#define MAX 6
#define CMAX 15

const size_t I_DIM = MAX * sizeof(int);
const size_t SS_DIM = MAX * sizeof(char*);
const size_t S_DIM = MAX * CMAX;

// global variables needed to perform comparisons   
int *pg_int;
char **pg_str;

typedef int(*cmp_fn)(const void*, const void*);

int comp_num(const int *lhs, const int *rhs ) { 
    if (pg_int[*lhs] < pg_int[*rhs]) 
        return -1; 
    if (pg_int[*lhs] > pg_int[*rhs]) 
        return 1; 
    return 0;
} 

int comp_str(const int *lhs, const int *rhs ) { 
    return strcmp(pg_str[*lhs],pg_str[*rhs]);
} 

int main(void) {
    int nums[MAX] = {6,4,8,2,1,3};
    char str[MAX][CMAX] = {"cat","dog","panter","red fish","hawk","snake"};
    int i;

    // create an array of indeces 
    int index[MAX];
    for ( i = 0; i < MAX; ++i ) {
        index[i] = i;
    }

    // set global copies
    pg_int = malloc(I_DIM);
    memcpy(pg_int,nums,I_DIM);
    pg_str = malloc(SS_DIM);
    pg_str[0] = malloc(S_DIM);
    memcpy(pg_str[0],str[0],S_DIM);
    for ( i = 1; i < MAX; i++ ) {
        pg_str[i] = pg_str[0] + i * CMAX;
    }

    // sort the indeces ordering by ints
    qsort(index, MAX, sizeof(int), (cmp_fn)comp_num);

    //update the two arrays
    for ( i = 0; i < MAX; ++i ) {
        nums[i] = pg_int[index[i]];
        strcpy(str[i],pg_str[index[i]]);
    }

    // print out sorted couples
    printf("Sort by numbers:\n");
    for ( i = 0; i < MAX; ++i ) {
        printf("%d %s\n",nums[i],str[i]);
    }

    // sort the indeces ordering by strings
    qsort(index, MAX, sizeof(int), (cmp_fn)comp_str);

    //update the two arrays
    for ( i = 0; i < MAX; ++i ) {
        nums[i] = pg_int[index[i]];
        strcpy(str[i],pg_str[index[i]]);
    }

    // print out sorted couples
    printf("\nSort by strings:\n");
    for ( i = 0; i < MAX; ++i ) {
        printf("%d %s\n",nums[i],str[i]);
    }

    free(pg_int);
    free(pg_str[0]);
    free(pg_str);
    return 0;
}

输出（抱歉这个愚蠢的例子）是：

Sort by numbers:
1 hawk
2 red fish
3 snake
4 dog
6 cat
8 panter

Sort by strings:
6 cat
4 dog
1 hawk
8 panter
2 red fish
3 snake

如果您想在 C++ 中完成相同的任务，您应该利用标准库并使用 std::vector as a container and std::sort 作为算法：

#include <iostream>
#include <vector>
#include <algorithm>

using std::vector;
using std::string;
using std::cout;

struct numABC {
    double num;
    string str;

    // instead of a compare function I can overload operator <
    friend bool operator<( const numABC &lhs, const numABC &rhs ) {
        return lhs.num < rhs.num;
    }
};

// or use a lambda
auto cmp_str = []( const numABC &lhs, const numABC &rhs ) -> bool {
    return lhs.str < rhs.str;
};

int main() {

    vector<numABC> my_data = { {3.6, "cat"}, {5.7, "dog"}, {7.1, "panter"},
                         {0.2, "red fish"}, {1.8, "hawk"}, {1.1, "snake"}};

    std::sort(my_data.begin(), my_data.end());

    std::cout << "Sort by numbers:\n";
    for ( auto & s : my_data ) {
        std::cout << s.num << ' ' << s.str << '\n';
    }

    std::sort(my_data.begin(), my_data.end(), cmp_str);
    // passing a lambda to specify how to compare ^^

    std::cout << "Sort by strings:\n";
    // if you don't like c++11 range for:
    for ( int i = 0; i < my_data.size(); ++i ) {
        std::cout << my_data[i].num << ' ' << my_data[i].str << '\n';
    }

    return 0;
}

请注意，我已将 my_data 初始化为 numABC 类型的 对象向量 。如果必须从两个数组开始，可以这样创建向量：

vector<double> nums = {3.6, 5.7, 7.1, 0.2, 1.8, 1.1};
vector<string> str = {"cat", "dog", "panter", "red fish", "hawk", "snake"};
vector<numABC> my_data;

for ( int i = 0; i < nums.size(); ++i ) {
    my_data.push_back(numABC{nums[i],str[i]});
}

排序后，如果你必须再次提取这两个向量（而不是简单地循环my_data）你可以这样做：

for ( int i = 0; i < my_data.size(); ++i ) {
    nums[i] = my_data[i].num;
    str[i] = my_data[i].str;
}

或者，您可以实现一种类似于我之前使用的算法，并 使用索引的辅助向量对两个向量 nums 和 srt 进行排序:

vector<double> nums = {3.6, 5.7, 7.1, 0.2, 1.8, 1.1};
vector<string> str = {"cat", "dog", "panter", "red fish", "hawk", "snake"};

// create the vector of indeces
vector<int> idx(nums.size());
std::iota(idx.begin(),idx.end(),0); // fill the vector, require #include <numeric>

// thanks to the lambda variable capture you don't need globals
auto cmp_ind = [ &nums ]
           ( const int &lhs, const int &rhs ) -> bool {
    return nums[lhs] < nums[rhs];
};

// sort indeces 
std::sort(idx.begin(), idx.end(),cmp_ind);

// create sorted arrays. It could be done in place but it's more difficult
vector<double> sorted_nums(nums.size());
vector<string> sorted_str(str.size());
for ( int i = 0; i < nums.size(); ++i ) {
    sorted_nums[i] = nums[idx[i]];
    sorted_str[i] = str[idx[i]];
}

std::cout << "Sort by numbers:\n";
for ( int i = 0; i < nums.size(); ++i ) {
    std::cout << sorted_nums[i] << ' ' << sorted_str[i] << '\n';
}

不使用数组对结构进行排序

Not sorting of struct using arrays

c++

qsort