【数据结构|c语言数据结构基数排序算法】/*
*基数排序算法的大概思想:
*首先创建一个链表用于存储待排序数组 arraynode链表
*创建一个储存头结点的数组 用来储存分配好的节点 0-9
*进行分配 即给group数组进行赋值数据
*首先进行分配的是 次关键字的操作 然后进行主关键字的操作(最高位)
*分别对分配好的数组进行收集 将头节点的指针返回值传回
*最后进行将主关键字的收集链表的头指针进行传回之后
*将链表的所有节点移动到原始数组a中
*输出数组中的数据
*/
#include
#include
#define RADIX 10//基数的数目
typedefstruct node
{
int key;
//关键字
struct node*next;
//指向下一个节点的指针}Node;
//链表节点的结构体
voidArrange(Node*arraynode,Node *group[],int level);
//链表节点分组函数
void Radix_Sort(int a[],int n);
//基数排序函数
Node* collect(Node*group[]);
//对分组的数据进行收集返回链表的头指针
int resolve(int key,int level);
//对关键字进行划分为主关键字 和次关键字
void main()
{
int m;
//数据的个数
int n[100];
//待排序的数组
int i;
//循环变量
printf("请输入数据的个数:\n");
scanf("%d",&m);
printf("请依次输入数据:\n");
for(i=0;
inext;
Arrange(arraynode,group,level);
arraynode=pnode;
}
arraynode=collect(group);
}
pnode=arraynode;
j=0;
//再次初始化循环变量
while(pnode)
{
a[j++]=pnode->key;
pnode=pnode->next;
}
free(arraynode);
//释放链表的空间
}
int resolve(int key,int level)//对关键字进行划分为主关键字 和次关键字
{
switch(level)
{
case 1: key=key%10;
break;
//得到是次关键字
case 2: key=(key%100)/10;
break;
//得到的是主关键字
}
return key;
}
voidArrange(Node*arraynode,Node *group[],int level)//链表节点分组函数
{
int index;
//Node*pnode;
Node*postnode;
//指向最后一个节点的指针
index=resolve(arraynode->key,level);
//pnode=arraynode;
if(group[index]==NULL)
{
group[index]=arraynode;
arraynode->next=NULL;
}
else
{
postnode=group[index];
//分组操作就是对group数组的创建过程
while(postnode->next)//将postnode指针移动到最后一个节点处
{
postnode=postnode->next;
}
postnode->next=arraynode;
arraynode->next=NULL;
}
}
Node* collect(Node*group[])//对分组的数据进行收集
{
int i;
Node*pnode=NULL;
Node*postnode=NULL;
//指向最后一个节点的指针
Node*pHead=NULL;
//要返回的链表的头指针 对其进行初始化
for(i=0;
inext=pnode;
//将其插入到链表的最后一个节点的后面
pnode->next=NULL;
//为下一次的链表的最后一个节点后面插入元素创造条件
}
while(postnode->next)
{
postnode=postnode->next;
}
group[i]=NULL;
//释放group数组的空间}
return pHead;
//返回链表
}
推荐阅读
- C语言学习|第十一届蓝桥杯省赛 大学B组 C/C++ 第一场
- 【C】题目|【C语言】题集 of ⑥
- 单片机|自学单片机好找工作吗(会单片机能找什么工作?)
- 单片机|keil把源代码生成lib的方法
- c语言|一文搞懂栈(stack)、堆(heap)、单片机裸机内存管理malloc
- c语言|C语言初期学习遇到的特殊点 【三子棋详解】【初学者福音,详细总结,复习能手】
- 笔记|C语言数据结构——二叉树的顺序存储和二叉树的遍历
- C语言学习(bit)|16.C语言进阶——深度剖析数据在内存中的存储
- 数据结构和算法|LeetCode 的正确使用方式
- 先序遍历 中序遍历 后序遍历 层序遍历