Liny_@NotePad

沉迷ACG中

基数排序实现

YOYO posted @ 2009年3月12日 21:29 in 【算法】与【数据结构】 with tags 基数排序 , 2261 阅读

rt……

  1. #include<iostream>
  2. using namespace std;
  3.  
  4. struct Node{
  5.         int key;
  6.         Node * prior;
  7.         Node * next;
  8. };
  9.  
  10. int power(int n,int t){
  11.         int x = n;
  12.         while(--t)x*=n;
  13.         return x;
  14. }
  15.  
  16. Node* createNode(int n){
  17.         Node *p;
  18.         if((p = new Node())==NULL){
  19.                 cout<<"无法分配内存！"<<endl;
  20.         }
  21.         p->key = n;
  22.         p->prior = NULL;
  23.         p->next = NULL;
  24.         return p;
  25. }
  26.  
  27. void viewAllNodes(Node *L){
  28.         Node *h = L->next;
  29.         while(h!=L){
  30.                 cout<<h->key<<" ";
  31.                 h = h->next;       
  32.         };
  33.         cout<<endl;
  34. }
  35.  
  36. template<class Type>
  37. void radix_sort(Type *L, int k){
  38.         Type *Lhead[10], *p;
  39.         int i,j;
  40.         for(i=0; i<10; i++){
  41.                 Lhead[i] = new Type;
  42.         }
  43.         for(i=0; i<k; i++){
  44.                 for(j=0; j<10; j++){
  45.                         Lhead[j]->prior = Lhead[j] -> next = Lhead[j];
  46.                 }
  47.                 while(L->next!=L){
  48.                         p = del_entry(L);
  49.                         j = get_digital(p,i);
  50.                         add_entry(Lhead[j], p);
  51.                 }
  52.                 for(j=0;j<10;j++){
  53.                         append(L,Lhead[j]);
  54.                 }
  55.         }
  56.         for(i=0; i<10; i++){
  57.                 delete(Lhead[i]);
  58.         }
  59. }
  60.  
  61. template <class Type>
  62. Type *del_entry(Type *L){
  63.         Type *p;
  64.         p = L->next;
  65.         if(p!=L){
  66.                 p->prior->next = p->next;
  67.                 p->next->prior = p->prior;
  68.         }
  69.         else {
  70.                 p = NULL;
  71.         }
  72.         return p;
  73. }
  74.  
  75. template <class Type>
  76. void add_entry(Type *L, Type *p){
  77.         p->prior = L->prior;
  78.         p->next = L;
  79.         L->prior->next = p;
  80.         L->prior = p;
  81. }
  82.  
  83. template <class Type>
  84. int get_digital(Type *p, int i){
  85.         int key;
  86.         key = p->key;
  87.         if(i!=0){
  88.                 key = key/power(10,i);
  89.         }
  90.         return key%10;
  91. }
  92.  
  93. template<class Type>
  94. void append(Type *L, Type* L1){
  95.         if(L1->next!=L1){
  96.                 L->prior->next = L1 ->next;
  97.                 L1->next->prior = L->prior;
  98.                 L1->prior->next = L;
  99.                 L->prior = L1->prior;
  100.         }
  101. }
  102.  
  103. int main(){
  104.         Node *h,*p;
  105.         int n,k, value;
  106.  
  107.         cout<<"请输入数组的长度：";
  108.         cin>>n;
  109.         cout<<"请输入数组元素的最多位数：";
  110.         cin>>k;
  111.         cout<<"请输入数组元素：";
  112.         h = createNode(0);
  113.         h->next = h->prior = h;
  114.         for(int i=0;i<n;i++){
  115.                 cin>>value;
  116.                 p = createNode(value);
  117.                 add_entry(h,p);
  118.         }
  119.         radix_sort(h,k);
  120.         viewAllNodes(h);
  121.         return 0;
  122. }
  • 无匹配
Small_feed 评论 (0)

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter