C语言实现基数排序——基于链队列实现

C语言实现基数排序

文章目录

C语言实现基数排序基数排序算法1.定义链结构2.定义链队列结构3.初始化带头结点的链队列4.判断带头结点的链队列是否为空5.带头结点的链队列入队操作6.带头结点的链队列出队操作7.取a的个位、十位、百位.....的值8.检索表中最大的值是几位数9.基数排序算法的实现项目完整代码运行效果图

基数排序算法

1.定义链结构

//定义链结构
typedef struct LinkNode {int data;struct LinkNode *next;
} LinkNode;

2.定义链队列结构

//定义链队列
typedef struct {LinkNode *front, *rear;
} LinkQueue;

3.初始化带头结点的链队列

//初始化带头结点的链式队列
void InitQueue(LinkQueue &Q) {//初始时 front和rear都指向头结点Q.front = Q.rear = (LinkNode *) malloc(sizeof(LinkNode));Q.front->next = NULL;
}

4.判断带头结点的链队列是否为空

//初始化带头结点的链式队列
void InitQueue(LinkQueue &Q) {//初始时 front和rear都指向头结点Q.front = Q.rear = (LinkNode *) malloc(sizeof(LinkNode));Q.front->next = NULL;
}
}

5.带头结点的链队列入队操作

//带头结点的链式队列入队操作
void EnQueue(LinkQueue &Q, int x) {LinkNode *p = (LinkNode *) malloc(sizeof(LinkNode));p->data = x;p->next = NULL;Q.rear->next = p;Q.rear = p;
}

6.带头结点的链队列出队操作

//带头结点的链式队列出队操作
bool DeQueue(LinkQueue &Q, int &x) {if (Q.front == Q.rear)          //判断是否为空队return false;LinkNode *p = Q.front->next;    //将要出队的结点命名为px = p->data;                    //用变量x返回队头元素Q.front->next = p->next;        //修改头结点的next指针if (Q.rear == p)                //判断要出队的是否为最后一个结点Q.rear = Q.front;           //如果是最后一个，就将队尾指针rear指向队头frontfree(p);                        //释放要删除结点的空间return true;
}

7.取a的个位、十位、百位…的值

//取各个位的值
int GetNum(int a, int i) {int n;if (i == 1)n = a / 1 % 10;else {int k = (int) pow(10, i - 1);n = a / k % 10;}return n;
}

8.检索表中最大的值是几位数

//检索表中最大值的位数
int HowMany(int A[], int len) {if (len == 0)return -1;int index = 1;for (int i = 0; i < len; ++i) {int temp = 1;int a = 10;while (A[i] / a > 0) {temp++;a *= 10;}if (index < temp)index = temp;}return index;
}

9.基数排序算法的实现

//基数排序
void BaseSort(int A[], LinkQueue Q[], int index, int len) {for (int i = 1; i <= index; ++i) {      //表中最大值是几位数就需要循环几趟for (int j = 0; j < len; ++j) {int k = GetNum(A[j], i);        //获取A表中各个值在第i位上的值EnQueue(Q[k], A[j]);         //将A表中各个值按照第i位的值插入对应队列}for (int j = 9, p = 0; j >= 0 && p < len; --j) {    //循环所有的链队列while (!IsEmpty(Q[j])) {        //若队列非空，循环出队并将出队的元素依次插入A表中int x;DeQueue(Q[j], x);A[p] = x;p++;}}}
}

项目完整代码

//基数排序（稳定的）
#include <stdio.h>
#include <stdlib.h>
#include <cmath>//定义链结构
typedef struct LinkNode {int data;struct LinkNode *next;
} LinkNode;//定义链队列
typedef struct {LinkNode *front, *rear;
} LinkQueue;//初始化带头结点的链式队列
void InitQueue(LinkQueue &Q) {//初始时 front和rear都指向头结点Q.front = Q.rear = (LinkNode *) malloc(sizeof(LinkNode));Q.front->next = NULL;
}//判断带头结点的链式队列是否为空
bool IsEmpty(LinkQueue Q) {if (Q.front == Q.rear || Q.front->next == NULL)return true;elsereturn false;
}//带头结点的链式队列入队操作
void EnQueue(LinkQueue &Q, int x) {LinkNode *p = (LinkNode *) malloc(sizeof(LinkNode));p->data = x;p->next = NULL;Q.rear->next = p;Q.rear = p;
}//带头结点的链式队列出队操作
bool DeQueue(LinkQueue &Q, int &x) {if (Q.front == Q.rear)          //判断是否为空队return false;LinkNode *p = Q.front->next;    //将要出队的结点命名为px = p->data;                    //用变量x返回队头元素Q.front->next = p->next;        //修改头结点的next指针if (Q.rear == p)                //判断要出队的是否为最后一个结点Q.rear = Q.front;           //如果是最后一个，就将队尾指针rear指向队头frontfree(p);                        //释放要删除结点的空间return true;
}//取各个位的值
int GetNum(int a, int i) {int n;if (i == 1)n = a / 1 % 10;else {int k = (int) pow(10, i - 1);n = a / k % 10;}return n;
}//检索表中最大值的位数
int HowMany(int A[], int len) {if (len == 0)return -1;int index = 1;for (int i = 0; i < len; ++i) {int temp = 1;int a = 10;while (A[i] / a > 0) {temp++;a *= 10;}if (index < temp)index = temp;}return index;
}//基数排序
void BaseSort(int A[], LinkQueue Q[], int index, int len) {for (int i = 1; i <= index; ++i) {      //表中最大值是几位数就需要循环几趟for (int j = 0; j < len; ++j) {int k = GetNum(A[j], i);        //获取A表中各个值在第i位上的值EnQueue(Q[k], A[j]);         //将A表中各个值按照第i位的值插入对应队列}for (int j = 9, p = 0; j >= 0 && p < len; --j) {    //循环所有的链队列while (!IsEmpty(Q[j])) {        //若队列非空，循环出队并将出队的元素依次插入A表中int x;DeQueue(Q[j], x);A[p] = x;p++;}}}
}int main() {//声明链队列LinkQueue Q[10];//初始化链队列for (int i = 0; i < 10; ++i) {InitQueue(Q[i]);}int A[] = {520, 211, 456, 888, 8, 111, 985, 666, 996, 233, 168, 66, 9999};int len = sizeof(A) / sizeof(int);//检索表中最大值的位数int index = HowMany(A, len);//基数排序BaseSort(A, Q, index, len);//将排序后的结果输出printf("基数排序的结果为：");for (int i = 0; i < len; ++i) {printf("%d ", A[i]);}return 0;
}

运行效果图

    int A[] = {520, 211, 456, 888, 8, 111, 985, 666, 996, 233, 168, 66, 9999};