首页 > 代码库 > 基数排序-队列实现

基数排序-队列实现

基数排序是一种不需要比较就能实现排序的算法思维,主要步骤为分配和收集的过程,重复这个过程于最大数的位数后,排序结束。

以下是完全以队列模拟桶的分配收集过程。

头文件(单链表部分):
typedef int ElemType;
typedef struct LNode
{
	ElemType data;
	struct LNode *next;
}LNode,*LinkList;

int InitList_link(LinkList *head)		   //初始化函数
{
	*head=(LinkList)malloc(sizeof(LNode));	    //产生头结点
	if(NULL==*head)
		return -1;		         //初始化失败
	(*head)->next=NULL;
	return 0;	             	//初始化成功
}

int ListEmpty_link(LinkList head)		       //判空函数
{
	if(NULL==head->next)
		return 1;		     //单链表为空
	return 0;		       	//单链表不为空
}

int ListLength_link(LinkList head)        	//求长度函数
{ 
	int len=0;
	LNode *p=head->next;
	while(NULL!=p)
	{
		len++;
		p=p->next;
	}
	return len;
}

int ListGet_link(LinkList head, int i, ElemType *x)	    //取单链表中的某一个元素
{
	LNode *p;
	int j;

	p=head;
	j=-1;
	while(p->next!=NULL&&j<i)              //查找返回
	{
		p=p->next;
		j++;
	}

	if(j!=i)
	{
		printf("取元素位置参数错");
		return 0;
	}

	*x=p->data;
	return 1;
}

int ListInsert_link(LinkList head,int i,ElemType e)      //在任意位置进行插入
{
	int count=0;
	LNode *p=head,*q=NULL;
	while(count<i-1&&NULL!=p)
	{
		p=p->next;
		count++;
	}
	if(count>i-1||NULL==p)
		return -1;
	q=(LNode *)malloc(sizeof(LNode));
	if(NULL==q)
		return -2;
	q->data=http://www.mamicode.com/e;>

基数排序-队列实现