radixbd.cpp

数据结构中排序的实例分析

#include <iostream.h>

#define KEYDEF
#define key(X) X.key

#include "..\include\book.h"

typedef struct elem {
  int key, next;
} ELEM;

typedef struct quelem {
  int front, rear;
} QUELEM;
 
void print(ELEM* array, int p) {
  int tmp;

  tmp = p;

  while (tmp != -1) {
    cout << array[tmp].key << " ";
    tmp = array[tmp].next;    
  }
  cout << '\n';
}

inline int ith_key(int key, int i) {
  int  k;
  for (k=0; k<i-1; k++)
    key = key/10;
  return key % 10;
}

void distribute(ELEM* array, int p, int i, int d, int r, QUELEM* qu)  {
  int k;
  for (k=0; k<r; k++)  {   // 初始化子序列队列指针
    qu[k].front = -1;
//  qu[k].rear = -1;
  }
  while (p != -1) {   // 对整个静态链进行分配
    k = ith_key(key(array[p]), i); // 取第i位关键码数字
    // 把array[p]分配到子序列中
    if (qu[k].front == -1)
      qu[k].front = p;    // 第一个
    else array[qu[k].rear].next = p;  // 加入到子序列中
    qu[k].rear = p;
    p = array[p].next;
  }
}
  
void collect(ELEM* array, int& p, int i, int d, int r, QUELEM* qu)  {
  int tail, k=0;
  while (qu[k].front == -1) // 查找第一个非空子序列
    k++;
  p = qu[k].front; 
  tail = qu[k].rear;
  while (k<r-1) {
    k++;
    while (k<r-1 && qu[k].front==-1)
      k++;
    if (qu[k].front != -1) {
      array[tail].next = qu[k].front;
      tail = qu[k].rear;
    }
  }
  array[tail].next = -1;
}

// d为组合关键码个数，r为基数个数
void radix(ELEM* array, int n, int d, int r)  {
  int i, p=0;    // p指向静态链中第一个记录
  QUELEM *qu;

  // 申请子序列队列指针数组空间
  qu = new QUELEM[r];

  for (i=0; i<n; i++)	// 建链
    array[i].next = i+1;
  array[n-1].next = -1;

  print(array, 0);

  for (i=0; i<d; i++) {
    distribute(array, p, i, d, r, qu);
    collect(array, p, i, d, r, qu); 
	print(array, p);
  }

  print(array, p);
}

void sort(ELEM* array, int listsize) {
  radix(array, listsize, 7, 10);
}