基数排序

基数排序 计算082 何吉 3080811037 上机实习报告—基数排序 问题描述:当关键字为整数时按从个位到最高位从小到大排序最终得到一组从小到大的 数。 基本要求: (1)测试数据在主程序中已经给出。 (2)用顺序循环队列充当桶。 (3)m位的整数就做m次循环排序出队列入队列 测试数据:,710，342，45，686，6，841，429，134，68，264, 算法思想:设待排序的数据元素关键字是m位d进制整数，设置d个桶，令其编号分别为0,1,2„，d-1。按关键字从最低位到最高位排序m次。因为要实现先进先出，用队列。 模块划分: (1)“SCQueue .h”顺序循环队列实现排序时的先进先出。 (2) Void RadixSort()是基数排序的具体实现 (3)"Jushuxunxu.c"主函数 数据结构: typedef struct { KeyType key; }DataType; 源程序: /*文件 SCQueue .h*/ typedef struct { DataType queue[MaxQueueSize]; int rear; int front; }SCQueue; void QueueInitiate(SCQueue *Q) { Q->rear=0; Q->front=0; } int QueueNotEmpty(SCQueue Q) { if(Q.front==Q.rear) return 0; else return 1; } int QueueAppend(SCQueue *Q,DataType x) { if((Q->rear+1)%MaxQueueSize==Q->front) { printf("队列已满无法插入!\n"); 计算082 何吉 3080811037 return 0; } else { Q->queue[Q->rear]=x; Q->rear=(Q->rear+1)%MaxQueueSize; return 1; } } int QueueDelete(SCQueue *Q,DataType *d) { if(Q->front==Q->rear) { printf("循环队列已空无数据元素出队列!\n"); return 0; } else { *d=Q->queue[Q->front]; Q->front=(Q->front+1)%MaxQueueSize; return 1; } } int QueueGet(SCQueue Q,DataType *d) { if(Q.front==Q.rear) { printf("循环队列已空无数据元素可取!\n"); return 0; } else { *d=Q.queue[Q.front]; return 1; } } /*文件jushuxunxu.c*/ #include #include typedef int KeyType; #define MaxQueueSize 100 typedef struct { 计算082 何吉 3080811037 KeyType key; }DataType; #include"SCQueue.h" void RadixSort(DataType a[],int n,int m,int d) /*对数据元素a[0]——a[n-1]进行关键字为m位d进制整数数值的基数排序*/ /*桶采用链式队列*/ { int i,j,k,power=1; SCQueue *tub; /*把d个队列定义为动态数组*/ tub=(SCQueue *)malloc(sizeof(SCQueue)*d);/*d个队列初始化*/ for(i=0;i