Question

一道C语言 数据结构 链表 求基数排序问题

就最后要把数组重新排列的refill 不会写
求大神帮忙看看问题在哪里

code 如下
mian.c
#include <stdio.h>
#include "list.h"
#include <stdlib.h>
#include "numberinterface.h"
#include <math.h>
void static refill( int A[] , list Bins[] ) ;
int static getdigit( int number, int position ) ;
int main( int argc, char *argv[] ) {
int A[500000] ;
list Bins[10] ;
int i, j, k, n, digit ;
n = atoi( argv[1] ) ;
for ( i = 0 ; i < n ; i++ ) { A[i] = rand() % 10000; }
printf("\n ");
for ( i = 0 ; i < 20 ; i++ ) printf(" %d ", A[i] );
printf("\n");
for ( i = 0 ; i < 10 ; i++ ) init_list( &Bins[i] ) ;
for ( i = 1 ; i <= 4 ; i++ ) {
printf("Pass %d: ", i ) ;
for ( j = 0 ; j < n ; j++ ) {
digit = getdigit( A[j] , i-1 ) ;
appendanumber( &Bins[digit], A[j] ) ;
}
refill( A, Bins ) ;
for ( k = 0 ; k < 20 ; k++ ) printf(" %d ", A[k] ); printf("\n");
}
return 0 ;
}

static int getdigit( int number, int position ) {
int digit, i , t = 1 ;
for( i = 0 ; i <= position ; i++ ) t = t * 10 ;
digit = ( number % t ) / ( t / 10 ) ;
return digit ;
}
static void refill( int A[], list Bins[] ) {
int i, j = 0 ;
for( i = 0 ; i < 10 ; i++ ) {
while( !empty_list( Bins[i] ) ) {
？？？？？？？？
在这需要call getnextnumber()
}
}
}

list.c 如下
#include <stdlib.h>
#include "numberinterface.h"
#include "globals.h"
#include "list.h"
status appendanumber( list *p_L , int n ) {
int *t_ptr ;
t_ptr = (int *) malloc( sizeof( int ) ) ;
*t_ptr = n ;
if( append( p_L, (generic_ptr)t_ptr ) == ERROR ) {
free(t_ptr) ;
return ERROR;
}
return OK ;
}
status getnextnumber( list *p_L, int *p_n ) {
int *t_ptr ;
if( delete( p_L, (generic_ptr *) &t_ptr ) == ERROR )
return ERROR ;
*p_n = *t_ptr ;
free(t_ptr) ;
return OK ;
}

Answer 1

假如不用基数列表，通过逐位借助栈似乎也可以高效地得到结果（从“嵌套调用”改写为“借助栈”），但是不好理解。其实主要思路不复杂：随机计算至少20个四位数，然后排序，可以用先除再求余数的方法，先得到高位数，把所有四位数分别整理到基数列表（最好可以同步记录余数到列表项），此时就可以开始遍历基数列表（从0到9，每个数所代表的列表对应一组“记录了余数的对象”），对于每个子列表中的所有对象，逐个排列出来到原有数组空间（也就是refill），清理基数列表以便再次使用(记得在每次refill的时候，也需要clearlist，注意访问的顺序不能打乱，可以将上次从表尾加入的列表项找到，从表头结点后清理)；然后从数组空间里这些对象的余数找到其最高位数，即百位数，再次整理到基数列表，同步逐个排列出来到原有数组空间；以此类推，经过四轮处理就有结果了。