c++ - 对包含指针的结构进行 Qsort

Question

我想编写一个程序，通过 qsort 函数按字典顺序对矩阵的行进行排序。由于比较函数需要知道每一行的大小，并且无法传递第三个参数，所以我将每一行设为包含行大小的 ROW 结构。然后将问题简化为按字典顺序对结构进行排序。

我编写默认构造函数、复制 cnostructor 和析构函数。我重载了赋值运算符。

我在VS2010上运行程序时，偶尔会报如下错误。当我在 Linux 中使用 g++ 运行它时，它可能会将某些元素修改为意外状态或在核心转储中运行。

谁能告诉我应该在哪里修改代码？谢谢

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

using namespace std;

struct ROW
{
    int *ptr;
    int L;
    ROW();
    ROW(ROW &obj);
    ~ROW();
    ROW& operator = (const ROW& obj);
};

ROW::ROW()
{
    ptr = 0;
    L = 0;
}

ROW::ROW(ROW &obj)
{
    L = obj.L;
    ptr = new int [L];
    memcpy(ptr,obj.ptr,L*sizeof(int));
}

ROW::~ROW()
{
    if (ptr)
        delete [] ptr;
    ptr = NULL;
}

ROW& ROW::operator = (const ROW& obj)
{
    if (this != &obj)
    {
        //this->ptr = obj.ptr;
        if (ptr)
            delete [] ptr;
        ptr = new int [L];
        memcpy(ptr,obj.ptr,L*sizeof(int));
    }
    return *this;
}

int MyCMP(const void *a, const void *b)
{
    ROW *L = (ROW*)a;
    ROW *R = (ROW*)b;
    for (int i=0; i < (L->L); i++)
        if ((L->ptr[i]) < (R->ptr[i]))
            return -1;
        else if ((L->ptr[i]) > (R->ptr[i]))
            return 1;
    return 0;
}

int main()
{
    srand(time(0));
    int R_size = 23;
    int R = 7;
    ROW* A = new ROW[R];
    //scanf("%d %d",&R, &R_size);
    R = rand()%20+1;
    R_size = rand()%30+1;
    printf("Row: %d, Column: %d.\n",R,R_size);

    for (int i=0; i<R; i++)
    {
        A[i].ptr = new int [R_size];
        A[i].L = R_size;
        for (int j=0; j<R_size; j++)
        {
            A[i].ptr[j] = rand()%100;
            printf("%d ",A[i].ptr[j]);
        }
        printf("\n");
    }
    printf("After sorting\n");
    qsort(A,R,sizeof(ROW),MyCMP);

    for (int i=0; i<R; i++)
    {
        for (int j=0; j<R_size; j++)
            printf("%d ",A[i].ptr[j]);
        printf("\n");
    }

    /*
    for (int i=0; i<R; i++)
    {
        if (A[i].ptr)
        {
            delete [] (A[i].ptr);
            A[i].ptr = NULL;
        }
    }
    delete [] A; 
    */
    return 0;
}

---

WINDOWS error
    TestArraySort.exe has stopped working 
        windows can check online for a solution to the problem.

      Problem Event Name:   APPCRASH
      Application Name: TestArraySort.exe
      Application Version:  0.0.0.0
      Application Timestamp:    53dd642c
      Fault Module Name:    TestArraySort.exe
      Fault Module Version: 0.0.0.0
      Fault Module Timestamp:   53dd642c
      Exception Code:   c0000005
      Exception Offset: 00011727
      OS Version:   6.1.7601.2.1.0.256.4
      Locale ID:    1033
      Additional Information 1: 0a9e
      Additional Information 2: 0a9e372d3b4ad19135b953a78882e789
      Additional Information 3: 0a9e
      Additional Information 4: 0a9e372d3b4ad19135b953a78882e789

Answer 1

分配后，您将完全改变数组的行维度。

int R_size = 23;
int R = 7;            // SET HERE
ROW* A = new ROW[R];  // USED AS ALLOC SIZE HERE

R = rand()%20+1;      // CHANGED HERE
R_size = rand()%30+1;

除非R最终小于或等于 7(几率为 7/20)，您将调用未定义的行为。如果它确实最终<= 7，您将报告部分排序的数据。总之，恶心。

---

使用现代 C++ 实现这一点

您可以通过多种方式使用现代 C++ 实现此目的。这是其中之一，它通过在插入矩阵之前对行进行排序而更进一步，从而使我们能够利用标准库比较器来获取可排序实体的容器。 这只是执行此操作的几种方法之一，它不是，也没有声称是什么 Elixir 。相反，选择它只是为了演示现代 C++ 语言和标准库必须提供的大量功能。其中:

• <random>用于随机管理。 真的是猫的 mustache 。
• std::vector<int>用于动态行存储。
• std::vector<>用于动态行存储。
• std::sort用于对单个行和行对行进行排序。
• ranged-for-loop 用法(看看能不能找到)

标准库在完成许多许多任务方面令人惊叹，但在演示一些它的能力。在学习 C++ 时，每天花时间学习更多该库。你不会后悔的。

所以，一些代码:

#include <iostream>
#include <vector>
#include <random>

int main()
{
    std::mt19937 prng{ std::random_device{}() };
    std::size_t R = std::uniform_int_distribution<std::size_t>(1,20)(prng);
    std::size_t R_size = std::uniform_int_distribution<std::size_t>(1,30)(prng);
    std::uniform_int_distribution<> dist(1,100);
    std::cout << "Row: " << R << ", Column: " << R_size << '\n';

    std::vector< std::vector<int> > rows;
    rows.reserve(R);
    for (size_t i=0; i<R; ++i)
    {
        std::vector<int> row;
        row.reserve(R_size);
        for (size_t j=0;j<R_size;++j)
        {
            row.emplace_back(dist(prng));
            std::cout << row.back() << ' ';
        }
        std::cout << '\n';
        std::sort(row.begin(), row.end());
        rows.emplace_back(std::move(row));
    }

    std::sort(rows.begin(), rows.end());
    std::cout << "After sorting\n";
    for (auto const& row : rows)
    {
        for (auto x : row)
            std::cout << x << ' ';
        std::cout << '\n';
    }
    return 0;
}

下面显示了一些示例输出运行，这显然会因运行而异。

示例输出 #1

Row: 9, Column: 19
90 16 9 66 78 38 28 52 27 61 24 42 10 52 83 27 74 52 20 
37 68 5 12 10 72 42 55 44 91 43 88 34 77 11 39 40 89 72 
47 67 86 74 13 88 88 65 64 60 81 10 42 26 58 5 6 88 83 
11 49 56 63 97 41 48 67 60 85 7 84 47 20 97 76 58 3 89 
83 15 87 63 88 10 54 20 16 82 5 33 69 21 23 16 36 47 3 
17 95 13 13 11 33 89 25 29 80 52 38 92 21 90 98 7 51 100 
12 4 74 64 11 73 9 1 24 28 49 92 57 69 20 50 53 80 20 
10 70 54 79 27 72 15 43 67 99 56 5 18 21 69 96 35 21 65 
90 75 26 86 45 92 47 70 27 81 18 23 64 71 51 31 10 81 94 
After sorting
1 4 9 11 12 20 20 24 28 49 50 53 57 64 69 73 74 80 92 
3 5 10 15 16 16 20 21 23 33 36 47 54 63 69 82 83 87 88 
3 7 11 20 41 47 48 49 56 58 60 63 67 76 84 85 89 97 97 
5 6 10 13 26 42 47 58 60 64 65 67 74 81 83 86 88 88 88 
5 10 11 12 34 37 39 40 42 43 44 55 68 72 72 77 88 89 91 
5 10 15 18 21 21 27 35 43 54 56 65 67 69 70 72 79 96 99 
7 11 13 13 17 21 25 29 33 38 51 52 80 89 90 92 95 98 100 
9 10 16 20 24 27 27 28 38 42 52 52 52 61 66 74 78 83 90 
10 18 23 26 27 31 45 47 51 64 70 71 75 81 81 86 90 92 94 

示例输出 #2

Row: 10, Column: 15
13 33 61 44 2 69 89 95 84 29 24 87 16 96 74 
44 60 72 37 78 17 94 6 88 5 61 41 37 33 13 
56 53 26 4 67 32 50 41 21 79 41 21 17 97 85 
88 84 7 93 41 13 46 10 50 70 38 71 3 55 77 
82 53 53 71 77 33 48 36 25 82 73 58 67 63 56 
27 83 5 42 81 4 86 6 51 4 29 16 6 38 78 
94 5 87 13 4 76 66 47 97 72 55 63 96 78 43 
96 2 36 55 64 25 34 27 70 44 21 2 46 54 46 
83 85 23 48 42 14 19 89 37 73 3 15 38 41 41 
98 64 49 9 61 46 49 24 94 76 51 46 98 3 26 
After sorting
2 2 21 25 27 34 36 44 46 46 54 55 64 70 96 
2 13 16 24 29 33 44 61 69 74 84 87 89 95 96 
3 7 10 13 38 41 46 50 55 70 71 77 84 88 93 
3 9 24 26 46 46 49 49 51 61 64 76 94 98 98 
3 14 15 19 23 37 38 41 41 42 48 73 83 85 89 
4 4 5 6 6 16 27 29 38 42 51 78 81 83 86 
4 5 13 43 47 55 63 66 72 76 78 87 94 96 97 
4 17 21 21 26 32 41 41 50 53 56 67 79 85 97 
5 6 13 17 33 37 37 41 44 60 61 72 78 88 94 
25 33 36 48 53 53 56 58 63 67 71 73 77 82 82 

示例输出 #3

Row: 19, Column: 17
28 40 51 8 76 81 57 43 66 4 52 81 88 88 92 16 16 
39 38 78 10 50 24 53 72 4 43 87 92 75 51 20 62 45 
76 93 5 84 35 92 54 33 1 41 96 8 70 80 21 25 10 
1 58 19 24 42 39 17 93 53 35 64 73 27 13 96 34 55 
13 99 94 54 52 14 73 50 32 2 16 64 40 14 71 70 62 
39 7 43 60 72 66 21 70 74 95 25 29 35 95 56 42 80 
74 41 88 51 55 73 45 41 8 17 8 2 64 91 66 25 37 
23 34 45 71 70 25 63 39 85 38 51 32 75 54 99 44 28 
76 84 81 52 1 22 20 89 13 11 48 82 8 21 67 9 15 
2 16 34 51 54 35 14 86 78 84 93 47 35 77 36 4 20 
23 13 36 24 14 83 38 7 84 9 97 87 62 82 27 43 3 
78 28 8 52 50 24 8 76 36 7 45 75 34 67 30 62 49 
27 52 90 65 19 88 81 78 44 53 51 59 22 51 75 52 40 
89 63 56 65 77 52 91 32 68 2 99 73 94 90 23 34 2 
67 18 43 46 30 16 44 10 86 27 76 7 71 22 15 60 20 
59 59 42 79 24 27 11 98 36 82 29 82 58 85 10 77 15 
44 83 58 21 1 33 30 77 17 94 16 81 36 40 73 46 28 
99 78 78 59 41 75 49 84 41 15 57 55 9 72 64 83 54 
48 15 4 92 37 13 76 1 46 68 52 66 39 29 76 21 70 
After sorting
1 4 13 15 21 29 37 39 46 48 52 66 68 70 76 76 92 
1 5 8 10 21 25 33 35 41 54 70 76 80 84 92 93 96 
1 8 9 11 13 15 20 21 22 48 52 67 76 81 82 84 89 
1 13 17 19 24 27 34 35 39 42 53 55 58 64 73 93 96 
1 16 17 21 28 30 33 36 40 44 46 58 73 77 81 83 94 
2 2 23 32 34 52 56 63 65 68 73 77 89 90 91 94 99 
2 4 14 16 20 34 35 35 36 47 51 54 77 78 84 86 93 
2 8 8 17 25 37 41 41 45 51 55 64 66 73 74 88 91 
2 13 14 14 16 32 40 50 52 54 62 64 70 71 73 94 99 
3 7 9 13 14 23 24 27 36 38 43 62 82 83 84 87 97 
4 8 16 16 28 40 43 51 52 57 66 76 81 81 88 88 92 
4 10 20 24 38 39 43 45 50 51 53 62 72 75 78 87 92 
7 8 8 24 28 30 34 36 45 49 50 52 62 67 75 76 78 
7 10 15 16 18 20 22 27 30 43 44 46 60 67 71 76 86 
7 21 25 29 35 39 42 43 56 60 66 70 72 74 80 95 95 
9 15 41 41 49 54 55 57 59 64 72 75 78 78 83 84 99 
10 11 15 24 27 29 36 42 58 59 59 77 79 82 82 85 98 
19 22 27 40 44 51 51 52 52 53 59 65 75 78 81 88 90 
23 25 28 32 34 38 39 44 45 51 54 63 70 71 75 85 99