板蓝根使用队列排序 [英] Radix Sorting with using queue
问题描述
我想创建一个基数排序实现使用队列。
I've wanted to create a radix sort implementation using queues.
我无法弄清楚这我code的一部分有问题或资源，我应该阅读。
我的code可以完全错了，但这是我的执行没有任何帮助的（我还没有采取一个数据结构和放大器;算法当然还）。
I couldn't figure out which part of my code has problems or which resources should I read. My code may be totally wrong but this is my implementation without any help (I haven't taken a data structures & algorithms course yet).
我创建了一个功能，但没有奏效。虽然做研究，我看到一些code样品，但他们似乎对我来说更加复杂。
I created a function but it didn't work. While doing research, I saw some code samples but they seemed to be more complex for me.
首先我想找到所有整数的最低位显著
，然后在队列元素，其下标匹配排序，
，然后排序后全部复制队列结束11日的队列元素。
再次做这样的11排队元素，直到达到最显著的数字。
Firstly I wanted to find the least significant digit of all integers Then sort them in queue element whose subscript matches, then after sort copy all queues to end of 11th queue element. Do this sort in 11th queue element again until reach most significant digit.
我能找到的最显著数字。和排序根据这个数字。但是，我无法分析其他数字。例如;
我可以排序1，2，4，5，3但当时机成熟时2个或多个数字排序，失败...
I could find least significant digit. And sort according to this digit. But, I couldn't analyse other digits. For instance; I could sort 1, 2 , 4, 5, 3 but when time comes to sort 2 or more digits, it fails...
我希望，我是清楚和简要说明我的问题。
I hope, I was clear and explained my problem briefly.
// 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，他给了我一些指导，使我的code清晰。
I followed suggestions from William Morris. I had to ask same question on CodeReview and he gave me some instructions to make my code clearer.
我将我的功能分为功能和使用递归也停了。
I divided my function into functions and also stopped using recursion.
的首先的，我创建了一个add_to_q功能，增加价值，相关的队列中，它有助于摆脱code重复。顺便说一句詹姆斯·扈利的方式是最简单的一个，但它再次使用递归。
Firstly, I created a add_to_q function which adds value to related queue and it helped to get rid of code duplication. By the way James Khoury's way is simplest one but it again uses recursion.
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它简单地将所有的队列元素第十队列的后面。在我看来，它是做的问题想要什么。
Secondly I created other helper functions. One is add_to_eleventh which simply adds all queue elements to the eleventh queue's rear. In my opinion, it is doing what question wants.
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分他们在整数数组归还。
Thirdly, my last helper function is back_to_ints. Its purpose is take the elements in 11th queue and divide them by ten and return them in a integer array.
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};
Finally my new sorting function which is now sorts the integers in same digit. Such that, numbers[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 。所以，我怎么能解决这个问题。
I solved the question partially. If you want to sort the numbers in same digit, it works. Otherwise, it fails. For instance, your inputs are 112,133,122,334,345,447,346 then the result will be 112 122 133 334 345 346 447. But, if the user wants to sort something like that(111,13,12,334,345,447,1) it gives 111 1 12 13 334 345 447. So, how can I overcome this problem.
另外，我已经改变了我的头文件1位。
Also, I have changed my header file a bit.
#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_ */
感谢您对我的重新开放主题...
Thank you for reopening my thread...
推荐答案
我修改队列一点。为了更好地理解code，我用的前部和后部为全局变量。
I've modified your queue a bit. To better understand the code, I use front and rear as global variables.
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 */
所以增加了队列的操作变得
So the operation of adding to queue becomes
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;
}
和添加从队列中删除的操作（返回数据）的
And add an operation of deleting from a queue(return the data as well)
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;
}
所以，现在我们可以实现基数排序。它可能会更容易将数据移动到队列的实际数量，而不是一个单一的数字。请注意，不需要排队11，如果你可以修改你的测试数组*改编，而你的radix_sort功能可能是这样的：
So now we can implement the radix sort. It may be easier to move your data into queue with the actual numbers rather than a single digit. Note that the 11th queue is not needed if you can modify your test array *arr, and your radix_sort function could be like this:
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）测试，充分code是
And finally you can test by calling radix_sort(your_array, your_array_size), the full code is
#include <stdio.h>
#include <stdlib.h>
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
这篇关于板蓝根使用队列排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
