C语言中数据结构之链式基数排序
实现效果图：
实例代码：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
|
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
typedef int Status;
typedef int ElemType;
#define MAX_NUM_OF_KEY 8 //关键字项数最大值
#define RADIX 10 //关键字基数，此时是十进制整数的基数
#define MAX_SPACE 100 //书上为10000
#define ord(ch) ((ch)-'0')
#define succ(x) ((x)+1)
typedef char KeyType;
typedef struct
{
KeyType keys[MAX_NUM_OF_KEY]; //关键字
int next;
}SLCell; //静态链表的结点类型
typedef struct
{
SLCell r[MAX_SPACE]; //静态链表的可利用空间，r[0]为头结点
int keynum; //记录当前关键字个数
int recnum; //静态链表的当前长度
}SLList; //静态链表类型
typedef int ArrType[RADIX]; //指针数组类型
/*******************************声明部分****************************************/
/*******************************函数部分****************************************/
void Distribute(SLCell r[],int i,ArrType f,ArrType e)
{
int j,p;
for(j = 0;j<RADIX;++j){
f[j] = 0;
e[j] = 0;
}
for(p = r[0].next; p ;p = r[p].next){
j = ord(r[p].keys[i]);
if(!f[j])
f[j] = p;
else
r[e[j]].next = p;
e[j] = p;
}
}
void Collect(SLCell r[],int i,ArrType f,ArrType e)
{
int j,t;
for(j = 0; j<RADIX&&!f[j] ; j = succ(j)); //找到第一个非空子表，succ为求后继函数
if(j<RADIX){
r[0].next = f[j];
t = e[j];
while(j<RADIX){
for(j = succ(j) ; j<RADIX-1 && !f[j]; j = succ(j));
if(f[j] && j<=RADIX-1){
r[t].next = f[j];
t = e[j];
}
}
r[t].next = 0;
}
}
void RadixSort(SLList *L)
{
int i;
ArrType f,e;
for(i = 0;i<L->keynum;i++){
Distribute(L->r,i,f,e);
Collect(L->r,i,f,e);
}
}
void CreateSLL(SLList *L)
{
char s[100];
int i,n,ct;
L->recnum = 0;
/* printf("请输入关键字个数：\n");
scanf("%d",&L->keynum);
printf("请输入链表长度：\n");
scanf("%d",&n);*/
L->keynum = 3;
n = 10;
printf("依次输入:278 109 063 963 589 184 505 269 008 083 \n");
for(ct = 0;ct<n;ct++){
// printf("请输入关键字：\n");
scanf("%s",&s);
L->recnum++;
for(i = 0;i<L->keynum;++i)
L->r[L->recnum].keys[L->keynum-1-i] = s[i];
}
for(i = 0;i<L->recnum;++i)
L->r[i].next = i+1;
L->r[L->recnum].next = 0;
}
void TraverseSLL(SLList L)
{
int i,j;
for(i = L.r[0].next; i ;i = L.r[i].next){
for(j = L.keynum-1;j>=0;j--)
printf("%c",L.r[i].keys[j]);
printf(" ");
}
printf("\n");
}
/*******************************主函数部分**************************************/
int main()
{
SLList L;
printf("创建静态链表\n");
CreateSLL(&L);
printf("创建完成：\n");
TraverseSLL(L);
printf("\n基数排序：\n");
RadixSort(&L);
TraverseSLL(L);
return 0;
}
|
如有疑问请留言或者到本站社区交流讨论，感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！
原文链接：http://blog.csdn.net/vit_rose/article/details/52787756