带有动态n × 2多维数组的C qsort()

ukqbszuj  于 2023-01-16  发布在  其他
关注(0)|答案(7)|浏览(117)

首先，我定义了一个2列10行的动态数组，整数number在这里被设置为10，这只是一个例子。

int** array;
int number = 10;

array = malloc(number * sizeof(int*));

for (i = 0; i < number; i++)
    array[i] = malloc(2 * sizeof(int));

然后我尝试在它上面使用qsort()。

qsort( array, number, sizeof array[0], compare );

这是我的比较函数。它按第一列的整数值排序，然后按第二列排序，同时保留第一列的顺序。例如，"02，17，01"将变为"01，02，17"。

int compare ( const void *pa, const void *pb ) {
    int (*a)[1] = pa;
    int (*b)[1] = pb;
    if ( (a[0][0] < b[0][0]) || (a[0][0] == b[0][0])&&(a[1][0] < b[1][0]) ) return -1;
    if ( (a[0][0] > b[0][0]) || (a[0][0] == b[0][0])&&(a[1][0] > b[1][0]) ) return +1;
    return 0;
}
    • 问题**

这对静态数组有效，我知道现在不行了，因为我有一个动态数组，它是一个指针数组。
如何修改这段代码以使用动态创建的多维数组？

c

7条答案

按热度按时间
xt0899hw

xt0899hw1#

样本码

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

int compare ( const void *pa, const void *pb ) {
    const int *a = *(const int **)pa;
    const int *b = *(const int **)pb;
    if(a[0] == b[0])
        return a[1] - b[1];
    else
        return a[0] - b[0];
}
/*
#define NUMCMP(x,y) (((x) < (y)) ? -1 : ((x) > (y)) ? 1 : 0)

int compare ( const void *pa, const void *pb ) {
    const int (*a)[2] = *(const int (**)[2])pa;
    const int (*b)[2] = *(const int (**)[2])pb;
    int tmp;
    if((tmp=NUMCMP((*a)[0], (*b)[0]))==0)
        return NUMCMP((*a)[1], (*b)[1]);
    else
        return tmp;
}
*/    
int main(void){
    int **array;
    int number = 10;
    int i;

    array = malloc(number * sizeof(int*));
    for (i = 0; i < number; i++){
        array[i] = malloc(2 * sizeof(int));
        array[i][0] = rand()%20;
        array[i][1] = rand()%20;
    }
    for(i = 0;i < number;++i)
        printf("%2d, %2d\n", array[i][0], array[i][1]);

    printf("\n");

    qsort(array, number, sizeof array[0], compare);

    for(i = 0;i < number;++i)
        printf("%2d, %2d\n", array[i][0], array[i][1]);

    return 0;
}

什么一个月

数组= {（整数 *），（整数 *），（整数 *），...，（整数 *）}
qsort需要每个元素的地址（对于交换等，因为元素的大小和个数以及起始地址自只给出信息）。
例如&（整数 *），&（整数 *）
因此(int **)传递给函数compare。
调用compare(int **, int **)&(int*)表示参数int**
比较函数原型是cmp(const void*, const void*)
将转换(const int**)pa转换为传递的原始指针。
*((const int **)pa)是取消引用的原始元素指针（int*）

赞(0）分享  回复(0）举报  2023-01-16
uqcuzwp8

uqcuzwp82#

既然你现在有了一个指针数组，那么你的比较函数的参数就是指向指针的指针。

int *const *a = pa;
int *const *b = pb;

现在你有了a和b作为两个指针指向你要排序的数组，每一个指针指向排序函数要求你检查的一个元素，你可以用*a和*b或者a[0]和b[0]来访问这些元素，但是不能用a[1]或者b[1]。如果sort函数要求比较数组中的第一个元素（*a）和第五个元素（*b），那么a[1]和b[1]就是数组中的第二个和第六个元素--这与您要进行的比较完全无关。
在第一级解引用之后，你可以做任何你需要做的事情来检查被比较的元素，因为你的数组元素本身就是指向数组的指针（每个2 x 1 m 12 n 1 x），int可以作为a[0][0]a[0][1]b[0][0]b[0][1]进行访问。请注意，这与a[1][0]和b[1][0]的顺序相反。
将它们写成(*a)[0]会提醒我们第一级间接寻址是一个“单元素访问”指针，我不确定这是否会使整个事情变得更清楚。

赞(0）分享  回复(0）举报  2023-01-16
jc3wubiy

jc3wubiy3#

我遇到了这个线程在寻找我的一个同上的问题，我最后结束了做下面的事情。

static int compareMatrixElements(const void *p1, const void *p2)
{
    return ((*(int const *) p1) - (*(int const *) p2));
}

void sortMatrix(int** matrix, int r, int c)
{
    int sort_matrix[r][c];

    for(int i = 0; i < r; i++) {

        memcpy(sort_matrix[i], matrix[i], c * sizeof(int));
    }

    qsort(sort_matrix, r*c, sizeof(int), compareMatrixElements);

    for(int i = 0; i < r; i++) {

        memcpy(matrix[i], sort_matrix[i], c * sizeof(int));
    }
}

在我上面的代码中，我直接使用了qsort API，你可以在一个连续的内存上使用这个API或者其他排序算法，但是如果你有一个矩阵，它的行是指向它的列的内存的指针呢（就像在我的情况下，以及在这个线程的问题中描述的）。因此，我复制这样的矩阵到一个连续的内存中，对该连续存储器运行排序，并将排序后的元素复制回矩阵。
上面的解决方案对我很有效，我想它可能对其他人有帮助，所以我发布了它，建议任何改进相同的。

赞(0）分享  回复(0）举报  2023-01-16
wfypjpf4

wfypjpf44#

const int *a = *(const int **)pa;
const int *b = *(const int **)pb;

@BLUEPIXY，这个不对，刚好

const int *a = pa;
const int *b = pb;

因为pa是const void *（数组[0]），它很好地转换为const int *

赞(0）分享  回复(0）举报  2023-01-16
mbyulnm0

mbyulnm05#

const int (*a)[2] = *(const int (**)[2])pa;
const int (*b)[2] = *(const int (**)[2])pb;

@BLUEPIXY，这个不对，刚好

const int (*a)[2] = (int(*)[])pa;
const int (*b)[2] = (int(*)[])pb;
赞(0）分享  回复(0）举报  2023-01-16
lf5gs5x2

lf5gs5x26#

//(C) Adam W. 
   #include<iostream>
    using namespace std;
   // If needed, change all instances of "float" with "int","double" etc.
   // Qsort algorithm from scratch, using 2 dimentional dynamic array
    
    float MyPartition(float MyArray[], int SortFromRowNumber,int SortInColumnNumber,int RowX, int Rows, int Columns);
    void MyQuickSort(float MyArray[], int SortFromRowNumber,int SortInColumnNumber,int RowX, int Rows,int Columns);
    
int main()
    {
        int Rows, Columns, SortFromRowNumber, SortInColumnNumber,RowX;
    
        Rows = 4;                                  //how many Rows    in matrix
        Columns = 4;                               //how many Columns in matrix
        SortFromRowNumber = 0;                     //start sorting from specified  row
        SortInColumnNumber = 0;                    //Sort in specified column
        RowX = Rows;                               //Used for counting cells in RAM
    
        float *MyArray = new float [Rows*Columns]{};    //create dynamic array
    
    //             Row       Column   Data
    //              |          |       |    
        *(MyArray + 0 + (RowX* 0 )) = 4.1 ;            //First  column  assign  data RAM cell 0
        *(MyArray + 1 + (RowX* 0 )) = 3.1 ;            //First  column  assign  data RAM cell 1
        *(MyArray + 2 + (RowX* 0 )) = 2.1 ;            //First  column  assign  data RAM cell 2
        *(MyArray + 3 + (RowX* 0 )) = 1.1 ;            //First  column  assign  data RAM cell 3
    
        *(MyArray + 0 + (RowX* 1 )) = 4.2 ;            //Second column  assign  data RAM cell 4
        *(MyArray + 1 + (RowX* 1 )) = 2.2 ;            //Second column  assign  data RAM cell 5
        *(MyArray + 2 + (RowX* 1 )) = 3.2 ;            //Second column  assign  data RAM cell 6
        *(MyArray + 3 + (RowX* 1 )) = 1.2 ;            //Second column  assign  data RAM cell 7
    
        *(MyArray + 0 + (RowX* 2 )) = 3.3 ;           //Third  column  assign  data RAM cell 8
        *(MyArray + 1 + (RowX* 2 )) = 4.3 ;           //Third  column  assign  data RAM cell 9
        *(MyArray + 2 + (RowX* 2 )) = 1.3 ;            //Third  column  assign  data RAM cell 10
        *(MyArray + 3 + (RowX* 2 )) = 2.3 ;            //Third  column  assign  data RAM cell 11
    
        *(MyArray + 0 + (RowX* 3 )) = 2.4;           //Third  column  assign  data RAM cell 12
        *(MyArray + 1 + (RowX* 3 )) = 3.4 ;           //Third  column  assign  data RAM cell 13
        *(MyArray + 2 + (RowX* 3 )) = 4.4 ;           //Third  column  assign  data RAM cell 14
        *(MyArray + 3 + (RowX* 3 )) = 1.4 ;           //Third  column  assign  data RAM cell 15
    
    
    
        cout << *(MyArray+ 0 +(RowX* 0 ))<< " " ;   //First  column output data
        cout << *(MyArray+ 0 +(RowX* 1 ))<< " " ;   //Second column output data
        cout << *(MyArray+ 0 +(RowX* 2 ))<< " ";    //Third  column output data
        cout << *(MyArray+ 0 +(RowX* 3 ))<< endl;   //Fourth column output data
    
        cout << *(MyArray+ 1 +(RowX* 0 ))<< " ";    //First  column output data
        cout << *(MyArray+ 1 +(RowX* 1 ))<< " " ;   //Second column output data
        cout << *(MyArray+ 1 +(RowX* 2 ))<< " ";    //Third  column output data
        cout << *(MyArray+ 1 +(RowX* 3 ))<< endl;   //Fourth column output data
    
        cout << *(MyArray+ 2 +(RowX* 0 ))<< " ";    //First  column output data
        cout << *(MyArray+ 2 +(RowX* 1 ))<< " " ;   //Second column output data
        cout << *(MyArray+ 2 +(RowX* 2 ))<< " ";    //Third  column output data
        cout << *(MyArray+ 2 +(RowX* 3 ))<< endl ;  //Fourth column output data
    
        cout << *(MyArray+ 3 +(RowX* 0 ))<< " ";    //First  column output data
        cout << *(MyArray+ 3 +(RowX* 1 ))<< " " ;   //Second column output data
        cout << *(MyArray+ 3 +(RowX* 2 ))<< " ";    //Third  column output data
        cout << *(MyArray+ 3 +(RowX* 3 ))<< endl ;  //Fourth column output data
        
        cout <<"------------------------------------------------------" << endl;
        MyQuickSort (MyArray,SortFromRowNumber,SortInColumnNumber,RowX,Rows-1,Columns); //sort data
        cout << "sorted in col:" ;
        cout << SortInColumnNumber;
        cout << "  from row:" ;
        cout <<SortFromRowNumber<< endl;
    
    
        cout << *(MyArray+ 0 +(RowX* 0 ))<< " " ;   //First  column output data
        cout << *(MyArray+ 0 +(RowX* 1 ))<< " " ;   //Second column output data
        cout << *(MyArray+ 0 +(RowX* 2 ))<< " ";    //Second column output data
        cout << *(MyArray+ 0 +(RowX* 3 ))<< endl;   //Second column output data
    
        cout << *(MyArray+ 1 +(RowX* 0 ))<< " ";    //First  column output data
        cout << *(MyArray+ 1 +(RowX* 1 ))<< " " ;   //Second column output data
        cout << *(MyArray+ 1 +(RowX* 2 ))<< " ";    //Third column output data
        cout << *(MyArray+ 1 +(RowX* 3 ))<< endl;   //Third column output data
    
        cout << *(MyArray+ 2 +(RowX* 0 ))<< " ";    //First  column output data
        cout << *(MyArray+ 2 +(RowX* 1 ))<< " " ;   //Second column output data
        cout << *(MyArray+ 2 +(RowX* 2 ))<< " ";    //Third  column output data
        cout << *(MyArray+ 2 +(RowX* 3 ))<< endl;   //Third column output data
    
        cout << *(MyArray+ 3 +(RowX* 0 ))<< " ";    //First  column output data
        cout << *(MyArray+ 3 +(RowX* 1 ))<< " " ;   //Second column output data
        cout << *(MyArray+ 3 +(RowX* 2 ))<< " ";    //Third  column output data
        cout << *(MyArray+ 3 +(RowX* 3 ))<< endl;   //Third column output data
    
        delete [] MyArray;
    
        return 0;
    }
float MyPartition(float MyArray[], int SortFromRowNumber,int SortInColumnNumber,int RowX, int Rows, int Columns)
           {
             float x = MyArray[SortFromRowNumber+(SortInColumnNumber*RowX)];
             int i = SortFromRowNumber, j = Rows;
             float TemporaryForCopying;
             while (true)
                  {
                   while (MyArray[j+SortInColumnNumber*RowX] > x) j--;
                   while (MyArray[i+SortInColumnNumber*RowX] < x) i++;
                   if (i < j)
                     {
                      for (int k=0;k<Columns;k++)
                        {
                         TemporaryForCopying = MyArray[i+k*RowX];
                         MyArray[i+k*RowX] = MyArray[j+k*RowX];
                         MyArray[j+k*RowX] = TemporaryForCopying;
                        }
                       i++;
                       j--;
                     }
                else
                    {return j;}
                }
           }
void MyQuickSort(float MyArray[], int SortFromRowNumber,int SortInColumnNumber,int RowX, int Rows,int Columns)
        {
         int SplitPoint;
         if (SortFromRowNumber < Rows)
           {
            SplitPoint = MyPartition(MyArray,SortFromRowNumber,SortInColumnNumber,RowX,Rows, Columns);//split table
            MyQuickSort(MyArray, SortFromRowNumber,SortInColumnNumber,RowX, SplitPoint,Columns);    //sort in split1
            MyQuickSort(MyArray, SplitPoint+1,SortInColumnNumber,RowX, Rows,Columns);               //sort in split2
           }
        }
赞(0）分享  回复(0）举报  2023-01-16
mwngjboj

mwngjboj7#

对于此静态数组，数组[0]的大小将为“2 * sizeof（int）"。

int array[10][2];

对于此指针到指针，数组[0]的大小将为“大小（int*）"。对于此指针到指针，数组[0][0]的大小将为“大小（int）"。

int **array;

所以，首先你不能使用“qsort（数组，数字，数组[0]的大小，比较）;“在指针到指针实现的情况下。

赞(0）分享  回复(0）举报  2023-01-16
我来回答

相关问题

    查看更多

    热门标签

    更多
    JavaquerypythonNode开发语言requestUtil数据库Table后端算法LoggerMessageElementParser

    最新问答

    更多
    • 蜀ICP备2022004421号-2 NULL123 https://www.null123.com © All rights reserved
    • 本站内容来源互联网,如果侵犯您的权益请联系我们删除, 联系方式：448109455@qq.com