c语言程序设计，数组编号，求思路 - 编程论坛

#2

wlcsss1232019-12-22 14:16

感觉好难啊白学了几个月

#3

八画小子2019-12-22 16:34

程序代码：

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

#define COUNT 10

#define SIZE_OF_ARRAY(array) (sizeof(array) / sizeof(array[0]))

typedef struct
{
    int value;
    int original_order;
    int sorted_order;
} value_order_t;

void display_array(int * array, size_t size)
{
    printf("[ ");
    for(int i = 0; i < size; i++)
    {
        printf("%d ", array[i]);
    }
    printf("]\n");
}

int main(void)
{
    const int array_count = COUNT;
    int input_array[array_count];
    value_order_t value_order_array[array_count];
    int order_array[array_count];


    printf("Please input integer array: ");
    if(scanf("%d %d %d %d %d %d %d %d %d %d", &input_array[0], &input_array[1], &input_array[2], &input_array[3], &input_array[4], &input_array[5], &input_array[6], &input_array[7], &input_array[8], &input_array[9])!= 10)
    {
        fprintf(stderr, "Size of integer array isn't %d", array_count);
        return EXIT_FAILURE;
    }
    printf("\n");

    printf("Original integer array: ");
    display_array(input_array, SIZE_OF_ARRAY(input_array));

    for(int i = 0; i < array_count; i++)
    {
        value_order_array[i].value = input_array[i];
        value_order_array[i].original_order = i;
        value_order_array[i].sorted_order = -1;
    }

    for(int i = 0; i < array_count - 1; i++)
    {
        for(int j = i; j < array_count; j++)
        {
            if(value_order_array[i].value > value_order_array[j].value)
            {
                value_order_t temp = value_order_array[i];
                value_order_array[i] = value_order_array[j];
                value_order_array[j] = temp;
            }
        }
    }

    value_order_array[0].sorted_order = 0;
    for(int i = 1; i < array_count; i++)
    {
        if(value_order_array[i].value == value_order_array[i - 1].value)
        {
            value_order_array[i].sorted_order = value_order_array[i - 1].sorted_order;
        }
        else
        {
            value_order_array[i].sorted_order = value_order_array[i - 1].sorted_order + 1;
        }
    }

    for(int i = 0; i < array_count; i++)
    {
        for(int j = 0; j < array_count; j++)
        {
            if(value_order_array[j].original_order == i)
            {
                order_array[i] = value_order_array[j].sorted_order + 1;
            }
        }
    }

    printf("Sorted order: ");
    display_array(order_array, SIZE_OF_ARRAY(order_array));

    return EXIT_SUCCESS;
}

[此贴子已经被作者于2019-12-22 16:39编辑过]

#4

八画小子2019-12-22 16:35

随便写的一个算法。应该有更好的算法，因为这个算法是最低效的。你可以在找找看。

#5

rjsp2019-12-22 17:33

这个题目不太好，因为数据的数量太小了，才10个。即便想出一个高效的算法，可能也体现不出效率来。

a. 已知：
   5 3 4 7 3 5 6 9 21 100

b. 添上序号
   5 3 4 7 3 5 6 9 21 100
   1 2 3 4 5 6 7 8  9  10

c. 根据第一行排序，得
   3 3 4 5 5 6 7 9 21 100
   2 5 3 1 6 7 4 8  9  10

d. 添上序号，得
   3 3 4 5 5 6 7 9 21 100 // 这一行其实没用了
   2 5 3 1 6 7 4 8  9  10
   1 1 2 3 3 4 5 6  7   8

e. 根据d中第二行排序，得
   5 3 4 7 3 5 6 9 21 100 // 这一行其实就是a
   1 2 3 4 5 6 7 8  9  10
   3 1 2 5 2 3 4 6  7   8

f. 输出e中的第一行和第三行

假如我用C++来做的话，代码应该是

程序代码：

#include <cstdio>
#include <utility>
#include <algorithm>
using namespace std;

void foo( const int (&a)[10] )
{
    pair<int,int> b[] = { {a[0],1}, {a[1],2}, {a[2],3}, {a[3],4}, {a[4],5}, {a[5],6}, {a[6],7}, {a[7],8}, {a[8],9}, {a[9],10} };
    sort( begin(b), end(b), [](auto& lhs,auto& rhs){return lhs.first<rhs.first;} );

    int index=1, pre=b[0].first;
    for( auto& value : b )
    {
        if( value.first != pre )
        {
            pre = value.first;
            ++index;
        }
        value.first = index;
    }
    sort( begin(b), end(b), [](auto& lhs,auto& rhs){return lhs.second<rhs.second;} );

    for( size_t i=0; i!=size(a); ++i )
        printf( "%d%c", a[i], " \n"[i+1==size(a)] );
    for( size_t i=0; i!=size(b); ++i )
        printf( "%d%c", b[i].first, " \n"[i+1==size(b)] );
}

int main( void )
{
    int a[] = { 5, 3, 4, 7, 3, 5, 6, 9, 21, 100 };
    foo( a );
}

#6

rjsp2019-12-22 18:07

C代码是

程序代码：

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

int cmp_b_first( const void* pl, const void* pr )
{
    if( *(int*)pl < *(int*)pr )
        return -1;
    if( *(int*)pl > *(int*)pr )
        return +1;
    return 0;
}

void foo( const int a[static 10] )
{
    int b[][2] = { {a[0],1}, {a[1],2}, {a[2],3}, {a[3],4}, {a[4],5}, {a[5],6}, {a[6],7}, {a[7],8}, {a[8],9}, {a[9],10} };
    qsort( b, 10, sizeof(*b), &cmp_b_first );

    int index=1, pre=b[0][0];
    for( size_t i=0; i!=10; ++i )
    {
        if( b[i][0] != pre )
        {
            pre = b[i][0];
            ++index;
        }
        b[i][0] = index;
    }

    int c[10];
    for( size_t i=0; i!=10; ++i )
        c[b[i][1]-1] = b[i][0];

    for( size_t i=0; i!=10; ++i )
        printf( "%d%c", a[i], " \n"[i+1==10] );
    for( size_t i=0; i!=10; ++i )
        printf( "%d%c", c[i], " \n"[i+1==10] );
}

int main( void )
{
    int a[] = { 5, 3, 4, 7, 3, 5, 6, 9, 21, 100 };
    foo( a );
}

#7

八画小子2019-12-22 22:10

回复 6楼 rjsp

" \n"[i+1==10]
这是个什么用法？

#8

八画小子2019-12-22 22:13

回复 6楼 rjsp

已经了解。非常佩服你这么简练地处理这个问题。受教了。