Radix使用队列排序

我想用队列创建一个基数排序实现。

我无法弄清楚我的代码的哪个部分有问题或我应该阅读哪些资源。 我的代码可能完全错误，但这是我的实现没有任何帮助（我尚未采用数据结构和算法课程）。

我创建了一个函数，但它没有用。 在做研究时，我看到了一些代码示例，但对我来说它们似乎更复杂。

首先，我想找到所有整数的最低有效位然后在其下标匹配的队列元素中对它们进行排序， 然后在排序后将所有队列复制到第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;irearp!=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;ifrontp != 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_ */ 

谢谢你重新打开我的post……

Answer 1

我已经修改了你的队列了一下。 为了更好地理解代码，我使用front和rear作为全局变量。

 typedef struct queue *queue_ptr; struct queue { int data; queue_ptr next; }; queue_ptr front[10], rear[10]; /* For base 10, The 11th queue is not needed */ 

所以添加到队列的操作就变成了

 void add_queue(int i, int data) { queue_ptr tmp; tmp = (queue_ptr) malloc(sizeof(*tmp)); tmp->next = NULL; tmp->data = data; if (front[i]) { rear[i]->next = tmp; } else { front[i] = tmp; } rear[i] = tmp; } 

并添加从队列中删除的操作（也返回数据）

 int delete_queue(int i) { int data; queue_ptr tmp; tmp = front[i]; if (!tmp) { return -1; /* So that we can check if queue is empty */ } data = tmp->data; front[i] = tmp->next; free(tmp); return data; } 

所以现在我们可以实现基数排序。 使用实际数字而不是单个数字将数据移动到队列中可能更容易。 请注意，如果您可以修改测试数组* arr，则不需要第11个队列，并且您的radix_sort函数可能如下所示：

 void radix_sort(int *arr, const int size) { int i, j, k, radix, digits, tmp; if (size < 1) { return; /* don't do anything if invalid size */ } /* get the number of digits */ for (digits = 0, radix = 1; arr[0] >= radix; digits++, radix *= 10); /* perform sort (digits) times from LSB to MSB */ for (i = 0, radix = 1; i < digits; i++, radix *= 10) { /* distribute into queues */ for (j = 0; j < size; j++) { add_queue((arr[j] / radix) % 10, arr[j]); } /* take them out from each queue to the original test array */ for (j = 0, k = 0; j < 10; j++) { for (tmp = delete_queue(j); tmp != -1;\ tmp = delete_queue(j), k++) { arr[k] = tmp; } } } } 

最后你可以通过调用radix_sort（your_array，your_array_size）来测试，完整的代码是

 #include  #include  typedef struct queue *queue_ptr; struct queue { int data; queue_ptr next; }; queue_ptr front[10], rear[10]; /* For base 10, The 11th queue is not needed */ void add_queue(int i, int data) { queue_ptr tmp; tmp = (queue_ptr) malloc(sizeof(*tmp)); tmp->next = NULL; tmp->data = data; if (front[i]) { rear[i]->next = tmp; } else { front[i] = tmp; } rear[i] = tmp; } int delete_queue(int i) { int data; queue_ptr tmp; tmp = front[i]; if (!tmp) { return -1; /* So that we can check if queue is empty */ } data = tmp->data; front[i] = tmp->next; free(tmp); return data; } void radix_sort(int *arr, const int size) { int i, j, k, radix, digits, tmp; if (size < 1) { return; /* don't do anything if invalid size */ } /* get the number of digits */ for (digits = 0, radix = 1; arr[0] >= radix; digits++, radix *=10); /* perform sort (digits) times from LSB to MSB */ for (i = 0, radix = 1; i < digits; i++, radix *= 10) { /* distribute to queues */ for (j = 0; j < size; j++) { add_queue((arr[j] / radix) % 10, arr[j]); } /* take them out from each queue to the original test array */ for (j = 0, k = 0; j < 10; j++) { for (tmp = delete_queue(j); tmp != -1;\ tmp = delete_queue(j), k++) { arr[k] = tmp; } } } } int main(void) { int i; int a[5] = {133, 34, 555, 111, 12}, b[12] = {1, 1, 1, 4, 5, 6, 7, 8, 9, 11, 11, 12}; radix_sort(a, 5); radix_sort(b, 5); for (i = 0; i < 5; i++) { printf("%d ", a[i]); } printf("\n"); for (i = 0; i < 12; i++) { printf("%d ", b[i]); } printf("\n"); return 0; } 

而输出是

 12 34 111 133 555 1 1 1 4 5 6 7 8 9 11 11 12 

Answer 2

这里有一些很好的信息。 在更高的层次上，调试代码将很困难，因为它比它需要的更复杂。 下面是一个使用C以更惯用的方式表达算法的不同代码。

总的来说，在代码方面，通常更少：简单是你的朋友。 这里显示的function：

1. 用于队列的循环单链表。 队列是指向列表尾节点的指针。 有了这个，追加和连接是快速的恒定时间操作。
2. 逻辑，可重用的function分解。
3. 只有大约80 SLOC包括一个简单的测试。 sort函数是18 SLOC。
4. 轻微测试。

这是排序：

 // Radix sort the given queue. void sort(QUEUE *queue) { unsigned i, j, div; QUEUE queues[RADIX], accum; // Handle case of nothing to sort. if (*queue == NULL) return; // Accumulator queue initially holds unsorted input. accum = *queue; // Make one pass per radix digit. for (i = 0, div = RADIX; i < MAX_DIGITS; i++, div *= RADIX) { // Clear the radix queues. for (j = 0; j < RADIX; j++) queues[j] = NULL; // Append accumulator nodes onto radix queues based on current digit. NODE *p = accum, *p_next = p->next; do { // Save p->next here because append below will change it. p = p_next; p_next = p->next; append_node(&queues[p->val / div % RADIX], p); } while (p != accum); // Gather all the radix queues into the accumulator again. for (accum = NULL, j = 0; j < RADIX; j++) cat(&accum, queues[j]); } // Accumulator now holds sorted input. *queue = accum; } 

其余的：

 #include  #include  #include  #define RADIX 10 #define MAX_DIGITS 9 // Node and circular queue. A queue is either null or a pointer to the _tail_ node. typedef struct node_s { struct node_s *next; unsigned val; } NODE, *QUEUE; // Make a new node with given value. NODE *new_node(unsigned val) { NODE *node = calloc(1, sizeof *node); // Must trap null return value here in production code! node->val = val; return node; } // Append given node to the tail of a queue. void append_node(QUEUE *queue, NODE *node) { NODE *tail = *queue; if (tail) { node->next = tail->next; tail->next = node; } else { node->next = node; } *queue = node; } // Concatenate the second queue onto the tail of the first. // First queue is changed (because it's a pointer to a tail node). void cat(QUEUE *a, QUEUE b_tail) { NODE *a_tail, *a_head; if (b_tail == NULL) return; a_tail = *a; if (a_tail) { a_head = a_tail->next; a_tail->next = b_tail->next; b_tail->next = a_head; } *a = b_tail; } // Sort code above goes here if you're compiling it. // And test main goes here. 

小测试主要：

 int main(void) { int i; unsigned data[] = { 98, 111, 42, 1111, 21 , 997, 0, 99999, 20903}; // Make a queue from data. QUEUE a = NULL; for (i = 0; i < sizeof data / sizeof data[0]; i++) append_node(&a, new_node(data[i])); sort(&a); // Print the circular list. NODE *p = a; do { p = p->next; printf("%u\n", p->val); } while (p != a); return 0; } 

Answer 3

免责声明：我之前没有实现基数排序或测试下面的代码。 我会把它留给你作为练习。

当你发现自己复制粘贴的东西不止一次停下来思考：必须有一个模式。

你的switch语句有很多复制粘贴。 在case 1:你有一条线：

 queue[1]->frontp = queue[0]->rearp; 

我猜它应该是：

 queue[1]->frontp = queue[1]->rearp; 

如果你重新考虑了这段代码，你可能会更容易看到这个？

用以下内容替换整个switch语句怎么样？

 int leastSignificantDigit = curNum%10; if(queue[leastSignificantDigit]->size == 0){ queue[leastSignificantDigit]->rearp = (queue_node_t *)malloc (sizeof(queue_node_t)); queue[leastSignificantDigit]->frontp = queue[leastSignificantDigit]->rearp; } else { queue[leastSignificantDigit]->rearp->restp = (queue_node_t *)malloc(sizeof(queue_node_t)); queue[leastSignificantDigit]->rearp = queue[leastSignificantDigit]->rearp->restp; } ++(queue[leastSignificantDigit]->size); queue[leastSignificantDigit]->rearp->element = curNodep->element; queue[leastSignificantDigit]->rearp->restp = NULL; radixSort(curNodep->restp, queue, size); 

Answer 4

我在第一个代码示例中看到的问题是

curNum = curNodep-> element.key

curNum总是有完整的数字，而switch语句总是做curNum％10 ，这只测试最后一位数。

在递归解决方案（递归不是问题）中，您必须传递一个参数来知道它必须处理的数字。

我知道这种技术是沉浸式的。

如果您看到在答案结尾处放置的样本，您可以看到最后一个数字是orderer，您可以更改输入样本以更好地了解这一点。 使用较小的最后一个数字添加大数字，例如’901’，查看结果。

对不起我的英语不好…