7-1 链式基数排序 (20 分)

实现链式基数排序，待排序关键字n满足1≤n≤1000，最大关键字数位≤5。

第一行输入待排序个数n（1≤n≤1000）,再输入n个数(n的数位≤5)。

10
278 109 63 930 589 184 505 269 8 83

输出每趟分配-收集后链表中的关键字，趟数为序列中最大值的数位（如样例中930的数位为3），每行结尾有空格。

930 63 83 184 505 278 8 109 589 269 
505 8 109 930 63 269 278 83 184 589 
8 63 83 109 184 269 278 505 589 930 

#include 
#include 
#include 
using namespace std;

struct node{
    int number;
    struct node * next;
};

int num, maxN = 1;
node *head;
queue q[10];

void init() {
    cin >> num;
    head = (node*) malloc(sizeof(node));
    head->next = nullptr;
    node *temp, *p = head;
    for (int i = 0; i < num; ++i) {
        temp = (node*) malloc(sizeof(node));
        p->next = temp;
        temp->next = nullptr;
        p = temp;
        cin >> temp->number;
        while (temp->number >= maxN) maxN *= 10;
    }
}
void printOut() {
    node *p = head->next;
    while (p != nullptr) {
        cout << p->number << ' ';
        p = p->next;
    }
    cout << endl;
}
void CS() {
    for (auto &i: q)
        while (!i.empty()) i.pop();
    node *p;
    for (int position = 1; position < maxN; position *= 10) {
        p = head->next;
        while (p != nullptr) {
            q[p->number / position % 10].push(p);
            p = p->next;
        }
        p = head;
        for (auto & i : q)
            while (!i.empty()) {
                p->next = i.front();
                p = p->next;
                p->next = nullptr;
                i.pop();
            }
        printOut();
    }
}
int main() {
    init();
    CS();
}