我想使用队列创建一个基数排序实现。
我不知道我的代码的哪一部分有问题或者我应该阅读哪些资源。我的代码可能完全错误,但这是我没有任何帮助的实现(我还没有上过数据结构和算法课程)。
我创建了一个函数,但它不起作用。在进行研究时,我看到了一些代码示例,但它们对我来说似乎更复杂。
首先我想找到所有整数的最低有效位 然后将它们排序到下标匹配的队列元素中, 然后在排序后将所有队列复制到第 11 个队列元素的末尾。再次在第 11 个队列元素中进行此排序,直到达到最高有效位。
我可以找到最低有效数字。并按照这个数字排序。但是,我无法分析其他数字。例如; 我可以对 1, 2 , 4, 5, 3 进行排序,但是当需要对 2 个或更多数字进行排序时,它会失败......
我希望,我很清楚并简要解释了我的问题。
// My function declaration
// Pre: arrInts holds the linked list of integers which are going to be sort.
// Post: queue will return result and its 11th element should hold sorted integers in
// that queue
queue_node_t * radixSort(const queue_node_t *arrInts, queue_t *queue[], int size){
queue_node_t *curNodep = arrInts; // Node to be checked
int i, curNum = curNodep->element.key;
if(curNodep == NULL){
// If there is no other node left then assign them into 11th queue.
for(i=0;i<=9;i++){
if(queue[i]->rearp!=NULL){
if(queue[10]->size == 0){
queue[10]->rearp = (queue_node_t *)malloc (sizeof(queue_node_t));
queue[10]->frontp = queue[10]->rearp;
} else {
queue[10]->rearp->restp = (queue_node_t *)malloc(sizeof(queue_node_t));
queue[10]->rearp = queue[10]->rearp->restp;
}
queue[10]->rearp = queue[i]->rearp;
queue[10]->size += queue[i]->size;
}
}
queue[10]->rearp = radixSort(queue[10]->rearp, queue, size);
} else {
// I used switch statement to handle least significant digit
switch(curNum%10){
case 0:
if(queue[0]->size == 0){
queue[0]->rearp = (queue_node_t *)malloc (sizeof(queue_node_t));
queue[0]->frontp = queue[0]->rearp;
} else {
queue[0]->rearp->restp = (queue_node_t *)malloc(sizeof(queue_node_t));
queue[0]->rearp = queue[0]->rearp->restp;
}
++(queue[0]->size);
queue[0]->rearp->element = curNodep->element;
queue[0]->rearp->restp = NULL;
radixSort(curNodep->restp, queue, size);
break;
case 1:
if(queue[1]->size == 0){
queue[1]->rearp = (queue_node_t *)malloc (sizeof(queue_node_t));
queue[1]->frontp = queue[0]->rearp;
} else {
queue[1]->rearp->restp = (queue_node_t *)malloc(sizeof(queue_node_t));
queue[1]->rearp = queue[1]->rearp->restp;
}
++(queue[1]->size);
queue[1]->rearp->element = curNodep->element;
queue[1]->rearp->restp = NULL;
// I tried to make recursion but I guess this is one the problems
radixSort(curNodep->restp, queue, size);
break;
case 2:
if(queue[2]->size == 0){
queue[2]->rearp = (queue_node_t *)malloc (sizeof(queue_node_t));
queue[2]->frontp = queue[2]->rearp;
} else {
queue[2]->rearp->restp = (queue_node_t *)malloc(sizeof(queue_node_t));
queue[2]->rearp = queue[2]->rearp->restp;
}
++(queue[2]->size);
queue[2]->rearp->element = curNodep->element;
queue[2]->rearp->restp = NULL;
radixSort(curNodep->restp, queue, size);
break;
case 3:
if(queue[3]->size == 0){
queue[3]->rearp = (queue_node_t *)malloc (sizeof(queue_node_t));
queue[3]->frontp = queue[3]->rearp;
} else {
queue[3]->rearp->restp = (queue_node_t *)malloc(sizeof(queue_node_t));
queue[3]->rearp = queue[3]->rearp->restp;
}
++(queue[3]->size);
queue[3]->rearp->element = curNodep->element;
queue[3]->rearp->restp = NULL;
queue[10]->rearp = radixSort(curNodep->restp, queue, size);
break;
case 4:
if(queue[4]->size == 0){
queue[4]->rearp = (queue_node_t *)malloc (sizeof(queue_node_t));
queue[4]->frontp = queue[4]->rearp;
} else {
queue[4]->rearp->restp = (queue_node_t *)malloc(sizeof(queue_node_t));
queue[4]->rearp = queue[4]->rearp->restp;
}
++(queue[4]->size);
queue[4]->rearp->element = curNodep->element;
queue[4]->rearp->restp = NULL;
radixSort(curNodep->restp, queue, size);
break;
case 5:
if(queue[5]->size == 0){
queue[5]->rearp = (queue_node_t *)malloc (sizeof(queue_node_t));
queue[5]->frontp = queue[5]->rearp;
} else {
queue[5]->rearp->restp = (queue_node_t *)malloc(sizeof(queue_node_t));
queue[5]->rearp = queue[5]->rearp->restp;
}
++(queue[5]->size);
queue[5]->rearp->element = curNodep->element;
queue[5]->rearp->restp = NULL;
radixSort(curNodep->restp, queue, size);
break;
case 6:
if(queue[6]->size == 0){
queue[6]->rearp = (queue_node_t *)malloc (sizeof(queue_node_t));
queue[6]->frontp = queue[6]->rearp;
} else {
queue[6]->rearp->restp = (queue_node_t *)malloc(sizeof(queue_node_t));
queue[6]->rearp = queue[6]->rearp->restp;
}
++(queue[6]->size);
queue[6]->rearp->element = curNodep->element;
queue[6]->rearp->restp = NULL;
radixSort(curNodep->restp, queue, size);
break;
case 7:
if(queue[7]->size == 0){
queue[7]->rearp = (queue_node_t *)malloc (sizeof(queue_node_t));
queue[7]->frontp = queue[7]->rearp;
} else {
queue[7]->rearp->restp = (queue_node_t *)malloc(sizeof(queue_node_t));
queue[7]->rearp = queue[7]->rearp->restp;
}
++(queue[7]->size);
queue[7]->rearp->element = curNodep->element;
queue[7]->rearp->restp = NULL;
radixSort(curNodep->restp, queue, size);
break;
case 8:
if(queue[8]->size == 0){
queue[8]->rearp = (queue_node_t *)malloc (sizeof(queue_node_t));
queue[8]->frontp = queue[8]->rearp;
} else {
queue[8]->rearp->restp = (queue_node_t *)malloc(sizeof(queue_node_t));
queue[8]->rearp = queue[8]->rearp->restp;
}
++(queue[8]->size);
queue[8]->rearp->element = curNodep->element;
queue[8]->rearp->restp = NULL;
radixSort(curNodep->restp, queue, size);
break;
case 9:
if(queue[9]->size == 0){
queue[9]->rearp = (queue_node_t *)malloc (sizeof(queue_node_t));
queue[9]->frontp = queue[9]->rearp;
} else {
queue[9]->rearp->restp = (queue_node_t *)malloc(sizeof(queue_node_t));
queue[9]->rearp = queue[9]->rearp->restp;
}
++(queue[9]->size);
queue[9]->rearp->element = curNodep->element;
queue[9]->rearp->restp = NULL;
radixSort(curNodep->restp, queue, size);
break;
}
}
return queue[10]->rearp;
}
编辑1(取得了一些进展)
我听从了威廉·莫里斯的建议。我不得不在 CodeReview 上问同样的问题,他给了我一些说明,让我的代码更清晰。
我将我的函数划分为函数,并且也停止使用递归。
首先,我创建了一个 add_to_q 函数,它为相关队列增加了价值,它有助于摆脱代码重复。顺便说一句,James Khoury 的方法是最简单的,但它再次使用递归。
void add_to_q(queue_t *queue_arr[], int value, int pos) {
if(queue_arr[pos]->size == 0){
queue_arr[pos]->rearp = (queue_node_t *)malloc (sizeof(queue_node_t));
queue_arr[pos]->frontp = queue_arr[pos]->rearp;
} else {
queue_arr[pos]->rearp->restp = (queue_node_t *)malloc(sizeof(queue_node_t));
queue_arr[pos]->rearp = queue_arr[pos]->rearp->restp;
}
queue_arr[pos]->rearp->element = value;
queue_arr[pos]->size++;
}
其次,我创建了其他辅助函数。一个是 add_to_eleventh,它简单地将所有队列元素添加到第十一个队列的后面。在我看来,它正在做问题想要的事情。
queue_t * add_to_eleventh(queue_t *queue[]) {
int i;
for(i=0;i<=9;i++){
while(queue[i]->frontp != NULL){
if(queue[10]->size == 0){
queue[10]->rearp = (queue_node_t *)malloc (sizeof(queue_node_t));
queue[10]->frontp = queue[10]->rearp;
} else {
queue[10]->rearp->restp = (queue_node_t *)malloc(sizeof(queue_node_t));
queue[10]->rearp = queue[10]->rearp->restp;
}
if ( queue[i]->size != 0 ){
queue[10]->rearp->element = queue[i]->frontp->element;
printf("---%d***",queue[i]->frontp->element);
}
queue[10]->size+=1;
queue[i]->frontp = queue[i]->frontp->restp;
queue[10]->rearp->restp = NULL;
}
}
return queue[10];
}
第三,我的最后一个辅助函数是 back_to_ints。其目的是将第 11 个队列中的元素除以 10 并以整数数组的形式返回。
void back_to_ints(queue_t *arr[], int *new_arr) {
queue_node_t *cur_nodep;
cur_nodep = arr[10]->frontp;
int i = 0, digit;
while(cur_nodep != NULL){
cur_nodep->element/=10;
digit = cur_nodep->element / 10;
new_arr[i++] = digit;
cur_nodep = cur_nodep->restp;
}
}
最后,我的新排序函数现在对同一位数的整数进行排序。这样,数字[7] = {112,133,122,334,345,447,346};
queue_t * radix_sort(int *arr, const int size,queue_t *sorted_arr[]) {
int i, digit[size], initials[size],j;
for(i=0;i<size;i++)
initials[i] = arr[i];
i = 0;
while(initials[i] != 0){
j = i;
printf("initialssss%d", initials[--j]);
back_to_ints(sorted_arr, initials);
for(i=0;i<size;i++){
digit[i] = initials[i] % 10;
switch (digit[i]) {
case 0:
add_to_q(sorted_arr, arr[i], 0);
break;
case 1:
add_to_q(sorted_arr, arr[i], 1);
break;
case 2:
add_to_q(sorted_arr, arr[i], 2);
break;
case 3:
add_to_q(sorted_arr, arr[i], 3);
break;
case 4:
add_to_q(sorted_arr, arr[i], 4);
break;
case 5:
add_to_q(sorted_arr, arr[i], 5);
break;
case 6:
add_to_q(sorted_arr, arr[i], 6);
break;
case 7:
add_to_q(sorted_arr, arr[i], 7);
break;
case 8:
add_to_q(sorted_arr, arr[i], 8);
break;
case 9:
add_to_q(sorted_arr, arr[i], 9);
break;
}
}
sorted_arr[10] = add_to_eleventh(sorted_arr);
i++;
}
return sorted_arr[10];
}
我部分解决了这个问题。如果您想对相同数字的数字进行排序,它可以工作。否则,它会失败。例如,您的输入是 112,133,122,334,345,447,346 那么结果将是112 122 133 334 345 346 447。但是,如果用户想要对类似的东西进行排序(111,13,12,334,345,447,1),它会给出111 1 12 13 334 345 447。那么,我该如何克服这个问题。
另外,我已经稍微更改了我的头文件。
#ifndef RADIX_H_
#define RADIX_H_
typedef struct queue_node_s {
int element;
struct queue_node_s *restp;
}queue_node_t;
typedef struct {
queue_node_t *frontp,
*rearp;
int size;
}queue_t;
queue_t * radix_sort(int *arr,const int size, queue_t *sorted_arr[]);
void add_to_q(queue_t *queue_arr[], int value, int pos);
queue_t * add_to_eleventh(queue_t *queue[]);
void back_to_ints(queue_t *arr[], int *new_arr);
void displayRadixed(queue_t *sorted[]);
#endif /* RADIX_H_ */
感谢您重新打开我的线程...