// RadixSort.cpp : 定义控制台应用程序的入口点。 #include "stdafx.h" #include <iostream> using namespace std; //定义队列的节点 struct Node {  int data;  Node* next; }; //定义程序所需的特殊队列 class Queue { public:  Queue()  {   Node* p = new Node;   p->data = NULL;   p->next = NULL;   front = p;   rear = p;  }  ~Queue()  {   Node* p = front;   Node* q;   while (p)   {    q = p;    p = p->next;    delete q;   }  }  //在队列的尾部添加一个元素，节点不存在，需要程序创建  void push(int e)  {   Node* p = new Node;   p->data = e;   p->next = NULL;   rear->next = p;   rear = p;  }  //在队列的尾部添加一个节点，节点原来就存在  void push(Node* p)  {   p->next = NULL;   rear->next = p;   rear = p;  }  //数据元素中最大位数  int lenData()  {   int temp(0);//数据元素的最大位数   int n(0);   //单个数据元素具有的位数   int d;      //用来存储待比较的数据元素   Node* p = front->next;   while (p != NULL)   {    d = p->data;    while (d > 0)    {     d /= 10;     n++;    }    p = p->next;    if (temp < n)    {     temp = n;    }    n = 0;   }   return temp;  }  //判断队列是否为空  bool empty()  {   if (front == rear)   {    return true;   }   return false;  }  //清除队列中的元素  void clear()  {   front->next = NULL;   rear = front;  }  //输出队列中的元素  void print(Queue& que)  {   Node* p = que.front->next;   while (p != NULL)   {    cout << p->data << " ";    p = p->next;   }  }  //基数排序  void RadixSort(Queue& que)  {   //定义一个指针数组，数组中存放十个分别指向十个队列的指针   Queue* arr[10];   for (int i = 0; i < 10; i++)   {    arr[i] = new Queue;   }   int d = 1;   int m = que.lenData(); //取得待排序数据元素中的最大位数   //将初始队列中的元素分配到十个队列中   for(int i = 0; i < m; i++)   {    Node* p = que.front->next;    Node* q;    int k;  //余数为k，则存储在arr[k]指向的队列中    while (p != NULL)    {     k = (p->data/d);     q = p->next;     arr[k]->push(p);     p = q;    }    que.clear(); //清空原始队列    //将十个队列中的数据收集到原始队列中    for (int i = 0; i < 10; i++)    {     if (!arr[i]->empty())     {      Node* p = arr[i]->front->next;      Node* q;      while (p != NULL)      {       q = p->next;       que.push(p);       p = q;      }     }    }    for (int i = 0; i < 10; i++)//清空十个队列    {     arr[i]->clear();    }    d *= 10;   }   print(que); //输出队列中排好序的元素  } private:  Node* front;  Node* rear; }; int _tmain(int argc, _TCHAR* argv[]) {  Queue oldque;  int i;  cout << "Please input the integer numbers you want to sort.Input ctrl+z to the end:" << endl;  while (cin >> i)  {   oldque.push(i);  }  oldque.RadixSort(oldque);     cout << endl;  return 0; }

#include <iostream> using namespace std; const int base=10; struct wx {         int num;         wx *next;         wx()         {                 next=NULL;         } }; wx *headn,*curn,*box[base],*curbox[base]; void basesort(int t) {         int i,k=1,r,bn;         for(i=1;i<=t;i++)         {                 k*=base;         }         r=k*base;         for(i=0;i<base;i++)         {                 curbox[i]=box[i];         }         for(curn=headn->next;curn!=NULL;curn=curn->next)         {                 bn=(curn->num%r)/k;                 curbox[bn]->next=curn;                 curbox[bn]=curbox[bn]->next;         }         curn=headn;         for(i=0;i<base;i++)         {                 if(curbox[i]!=box[i])                 {                         curn->next=box[i]->next;                         curn=curbox[i];                 }         }         curn->next=NULL; } void printwx() {         for(curn=headn->next;curn!=NULL;curn=curn->next)         {                 cout<<curn->num<<' ';         }         cout<<endl; } int main() {         int i,n,z=0,maxn=0;         curn=headn=new wx;         cin>>n;         for(i=0;i<base;i++)         {                 curbox[i]=box[i]=new wx;         }         for(i=1;i<=n;i++)         {                 curn=curn->next=new wx;                 cin>>curn->num;                 maxn=max(maxn,curn->num);         }         while(maxn/base>0)         {                 maxn/=base;                 z++;         }         for(i=0;i<=z;i++)         {                 basesort(i);         }         printwx();         return 0; }