使代表整数数组的索引

问题描述：

我们被要求作在返回一个整数指针的函数，并采取参数使代表整数数组的索引

int *func(int *list,int size)

我想创建一个整数数组的数组，其条目描述的位置原始数组中的条目在该数组进行排序时会有，但是不对原始数组进行排序，这应该在函数内完成，然后将指向数组的指针返回到主函数。例如：

主阵列

3,17,9,2,11,26,5

返回的数组是：

1,5,3,0,4,6,2

我正在考虑将其复制到另一个数组排序后，主阵！所以主要的顺序不会丢失，然后将它们进行比较以填充所需的索引数组，我认为这是有点长的任何其他想法？

这实在是不清楚你的要求。 “函数的工作是在函数体内部创建一个整数数组，并将该数组的初始地址返回给main”听起来像是故意实现一个错误，或者你打算使用动态分配？你能发布函数的代码吗？另外我不明白“这个数组的元素必须是主数组的索引”是如何对应于你的例子中的数据的。它似乎就像函数给出了数字在排序数组中的索引。这没有任何意义...... – Lundin 2015-03-25 12:52:14

我不清楚什么算法用于确定从主数组返回的数组。你应该考虑改进你的问题来获得答案。 – juhist 2015-03-25 12:52:38

据我不知道你想创建一个整数数组，其条目描述了原始数组中的条目在该数组排序时的位置，但没有对原始数组进行排序，对不对？ – 2015-03-25 12:59:52

答

这应该这样做，但我不禁感觉有一个更简单的方法。

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

typedef struct { 
    int value; 
    int index; 
    int index2; 
} sorter; 

int cmp(const void *a, const void *b) { 
    return ((sorter*)a)->value - ((sorter*)b)->value; 
} 

int cmp2(const void *a, const void *b) { 
    return ((sorter*)a)->index - ((sorter*)b)->index; 
} 

int *func(int *list, int size) { 
    int i, *iarray; 
    sorter *sarray = malloc(size * sizeof(sorter)); 
    if (sarray == NULL) 
     return NULL; 
    for (i=0; i<size; i++) { 
     sarray[i].index = i;     // original position 
     sarray[i].value = list[i];    // element value 
    } 
    qsort (sarray, size, sizeof(sorter), cmp); // sort by value 
    for (i=0; i<size; i++)      
     sarray[i].index2 = i;     // sorted position 
    qsort (sarray, size, sizeof(sorter), cmp2); // sort by original position 
    iarray = malloc(size * sizeof(int)); 
    if (iarray == NULL) { 
     free (sarray); 
     return NULL; 
    } 
    for (i=0; i<size; i++) 
     iarray[i] = sarray[i].index2;   // position when sorted 
    free (sarray); 
    return iarray; 
} 

int main(void) 
{ 
    int i, size, *sorted, list[] = {3,17,9,2,11,26,5}; 
    size = sizeof(list)/sizeof(int); 
    sorted = func(list, size); 
    if (sorted == NULL) 
     printf("Error in func\n"); 
    else { 
     for (i=0; i<size; i++) 
      printf("%d, ", sorted[i]); 
     printf("\n"); 
     free(sorted); 
    } 
    return 0; 
}

程序输出：

1, 5, 3, 0, 4, 6, 2,

答

您的任务涉及同时排序两个数组（值和位置）。要做到这一点，你可以：

创建一个辅助的数组，你重新组织阵列，以保持价值与地位彼此旁边，这样就可以使用它qsort;
使用（不方便）非标准qsort_r，它允许你通过void * ointer或
滚动自己的排序算法，既保持同步阵列考绩额外信息的排序例程。

第一种方法是最常用和便携的方法。标准排序功能qsort可以在阵列上工作，阵列元素可以有任何大小。所以：创建的（值，位置）对，排序的辅助阵列，通过位置和填充结果数组，它必须在堆上分配：

struct pair { 
    int val; 
    int pos; 
}; 

int paircmp(const void *pa, const void *pb) 
{ 
    const struct pair *a = pa; 
    const struct pair *b = pb; 

    return (a->val > b->val) - (a->val < b->val); 
} 

int *func(int array[], int n) 
{ 
    struct pair pair[n]; 
    int *result; 
    int i; 

    for (i = 0; i < n; i++) { 
     pair[i].val = array[i]; 
     pair[i].pos = i; 
    } 

    qsort(pair, n, sizeof(*pair), paircmp); 

    result = malloc(n * sizeof(*result)); 

    for (i = 0; i < n; i++) { 
     result[pair[i].pos] = i; 
    } 

    return result; 
}

这里，paircmp为qsort比较回调函数。

[qsort_r][qsort_r]方法很好，很干净，但qsort_r函数是一个不可移植的GNU扩展。它仍然需要一个辅助数组。（如果你的数组是一个有序的索引数组，那么你甚至不需要这个）

这些步骤和以前一样：创建一个索引的辅助数组，排序，使数组条目在这些指标进行排序，然后创建你的结果数组：

int indexcmp(const void *pa, const void *pb, void *data) 
{ 
    const int *a = pa; 
    const int *b = pb; 
    const int *array = data; 

    return (array[*a] > array[*b]) - (array[*a] < array[*b]); 
} 

int *func2(int array[], int n) 
{ 
    int *result = malloc(n * sizeof(*result)); 
    int pos[n]; 
    int i; 

    for (i = 0; i < n; i++) pos[i] = i; 

    qsort_r(pos, n, sizeof(*pos), indexcmp, array); 

    for (i = 0; i < n; i++) result[pos[i]] = i; 

    return result; 
}

比较函数indexcmp需要一个额外的参数。

第三个选项，滚动你自己的排序功能，是最有趣的，但我会留给你。

使代表整数数组的索引

相关推荐