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};
更多推荐
基数,队列,语言
发布评论