基于链表的基数排序

数据结构与算法分析——c语言描述 第三章的基数排序

还是使用链表，特点是使用了基数排序的算法。去visualgo看一看算法动画什么都清楚了。代码参照了blackboy的。

link.h

typedef int ElementType;
#ifndef _List_H
#define _List_H

struct Node;
typedef struct Node *PtrToNode;
typedef PtrToNode List;
typedef PtrToNode Position;



List MakeEmpty(List L);
int IsEmpty(List L);
int IsLast(Position P, List L);
Position Find(ElementType X, List L);
void Delete(ElementType X, List L);
Position FindPrevious(ElementType X, List L);
void Insert(ElementType X, List L, Position P);
void DeleteList(List L);
Position Header(List L);
Position First(List L);
Position Advance(Position P);
ElementType Retrieve(Position P);
void  InsertFront(ElementType, List);
void  InsertBack(ElementType, List);
#endif
           

link.c

#include"link.h"
#include<stdlib.h>
#include"fatal.h"

struct  Node
{
	ElementType Element;
	Position Next;
};

List MakeEmpty(List L) {
	if (L != NULL){
		DeleteList(L);
		L->Next = NULL;
		return L;
	}
	else {
		L = malloc(sizeof(struct Node));
		if (L == NULL)
			FatalError("Out of memory");
		L->Next = NULL;
		return L;
	}
}

int IsEmpty(List L) {
	return L->Next == NULL;
}

int IsLast(Position P, List L) {
	return P->Next == NULL;
}

Position Find(ElementType X, List L) {
	Position P;
	P = L->Next;
	while (P != NULL&&P->Element != X)
	{
		P = P->Next;
	}
	return P;
}

void Delete(ElementType X, List L) {
	Position P;
	P = FindPrevious(X, L);
	if (!IsLast(P, L)) {
		Position TmpCell = P->Next;
		P->Next = TmpCell->Next;
		free(TmpCell);
	}
}

Position FindPrevious(ElementType X, List L) {
	Position P;
	P = L;
	while (P->Next != NULL&&P->Next->Element != X)
		P = P->Next;
	return P;
}

void Insert(ElementType X, List L, Position P) {
	Position tmpCell;
	tmpCell = malloc(sizeof(struct Node));
	if (tmpCell == NULL)
		FatalError("Out of space!!");
	tmpCell->Element = X;
	tmpCell->Next = P->Next;
	P->Next = tmpCell;
}

void DeleteList(List L) {
	Position p;
	p = L->Next;
	L->Next = NULL;
	while (p != NULL) {
		Position tmp;
		tmp = p->Next;
		free(p);
		p = tmp;
	}
}

Position Header(List L) {
	return L;
}

Position First(List L) {
	return L->Next;
}

Position Advance(Position P) {
	return P->Next;
}

ElementType Retrieve(Position P) {
	return P->Element;
}

void  InsertFront(ElementType X, List L) {
	Insert(X, L, L);
}

void  InsertBack(ElementType X, List L) {
	Position last;
	last = L;
	while (last->Next != NULL)
		last = last->Next;
	Insert(X, L, last);
}
           

radixsort.c

#include"link.h"
#include<stdio.h>
#define BUCKETS 10 //桶的数量
#define N 10//需要排序数字数量
#define BITS 3 //位数

void radixSort(int arr[]);
int getDigital(int x, int cnt);
void print(int arr[]);

int main() {
	int arr[N]= { 64, 8, 216, 512, 27, 729, 0, 1, 343, 125 };
	print(arr);
	radixSort(arr);
	print(arr);
}

void radixSort(int arr[]) {
	List bucket[BUCKETS];
	int i,j,k;
	for (i = 0; i < BUCKETS; i++) {
		bucket[i] = MakeEmpty(NULL);
	}
	for (i = 0; i < BITS; i++) {
		for (j = 0; j < BUCKETS; j++)
			MakeEmpty(bucket[j]);
		for (k = 0; k < N; k++){
			InsertBack(arr[k], bucket[getDigital(arr[k], i)]);
		}
		for (int i = 0,k=0; i < N; i++) {
			Position p;
			p = First(bucket[i]);
			while (p != NULL) {
				arr[k++] = Retrieve(p);
				p = Advance(p);
			}
		}
	}
	for (i = 0; i<BUCKETS; ++i)
		DeleteList(bucket[i]);
}

int getDigital(int x, int cnt) {
	for (int i = 0; i < cnt; i++)
		x /= 10;
	return x % 10;
}

void print(int arr[]){
	for (int i = 0; i < N; i++) {
		printf("%d ", arr[i]);
	}
	printf("\n");
}