基数排序课程设计
- 格式：pdf
- 大小：222.67 KB
- 文档页数：14
课
程
设
计
学院：承德石油高等专科学校 班级：计控 1001 姓名：王森 学号：31 所在系：计算机与信息工程系 指导教师：马秋菊
2011 年 06 月 29 号
1
一 题目与要求
.................................................................................
4
e[0]
e[1]
e[2]
e[3]
e[4]
e[5]
e[6]
e[7]
e[8]
e[9]
83 63 8 184 109 278 269 589 505 930
f[0]
f[1]
f[2]
f[3]
f[4]
f[5]
f[6]
f[7]
f[8]
f[9]
(f) 第三趟按十位数分配，修改结点指针域，将链表中的记录分配到 相应的链队列中
11
while(i) { for(j=L.keynum-1;j>=0;j--) printf("%c",L.r[i].keys[j]); printf(" "); i=L.r[i].next; } } void Print(SLList L) {//按数组序号输出静态链表 int i,j; printf("keynum=%d recnum=%d \n",L.keynum,L.recnum); for(i=1;i<=L.recnum;i++) { printf("keys="); for(j=L.keynum;j>=0;j--) printf("%c",L.r[i].keys[j]); printf("otheritems=%d,next=%d",L.r[i].otheritems,L.r[i].next); printf("\n"); } } void RadixSort(SLList *L)
3
四 实验原理
....................................................................................
3
五、总体设计结构图
.........................................................................
10
连接成 //一个链表，e[0...RADIX-1]为各子表的尾指针 int j,t; for(j=0;!f[j];j=Succ(j));//找第一个非空子表，Succ 为求后继函 数 r[0].next=f[j]; t=e[j];//r[0].next 指向第一个非空子表中的第一个结点 while(j<RADIX-1) { for(j=Succ(j);j<RADIX-1&&!f[j];j=Succ(j));// 找下一个非空 子表 if(f[j]) {//链接两个非空子表 r[t].next=f[j]; t=e[j]; } } r[t].next=0;//t 指向最后一个非空子表中的最后一个结点 } void Printl(SLList L) {//按链表输出静态链表 int i=L.r[0].next,j;
9
//f[0..RADIX-1]和 e[0...RADIX-1] 分别指向各个子表只中第一个 和最后一个记录 int j,p; for(j=0;j<RADIX;++j) f[j]=0;//各子表初始化为空表 for(p=r[0].next;p;p=r[p].next) { j=Ord(r[p].keys[i]);//Ord 将记录中的第 i 个关键字映射到 [0...RADIX-1] if(!f[j]) f[j]=p; else r[e[j]].next=p; e[j]=p;//将 p 所指的结点插入第 j 个子表中 } } int Succ(int i) {//求后继函数 return ++i; } void Collect(SLCell r[],ArrType f,ArrType e) {//本算法按 keys[i]自小至大地将 f[0...RADIX-1]所指各子表一次
3
二 问题的提出
...............................................................................
3
三 功能要求 ..................................................................................
三 功能要求
使程序按着最低位优先的顺序把数据重新整理，最小数据在低位， 大数据在高位。
四 实验原理
多关键码排序按照从最主位关键码到最次位关键码或从最次位到 最主位关键码的顺序逐次排序。 最高位优先法：首先根据关键字最高位有效数字进行排序，然后根 据次高位数字进行排序，以此类推，知道根据最低位（个位）有效数 字.............................................................................
6
七 、基数排序原程序
.................................................................
3
五、 总体设计结构图
278 109 63 930 589 184 505 269 8 83
（a）初始记录静态链表 e[0] e[1] e[2] e[3] e[4] e[5] e[6] e[7] e[8] e[9]
269 83 930 63 184 505 8 278 589 109
f[0]
f[1]
f[2]
f[3]
f[4]
f[5]
f[6]
f[7]
f[8]
f[9]
(b) 第一趟按个位数分配修改结点指针域，将链表中的记录分配到相 应的链队列中
930 63 83 184 505 278 8 109 589 269
(c) 第一趟收集：将各队列链接起来，形成单链表
e[0] e[1] e[2] e[3] e[4] e[5] e[6] e[7] e[8] e[9]
109 8 505 930 63 269 278 83 184 589
(g) 第二趟收集：将各队列链接起来，形成单链表。此时序列已有序
5
六、调试与测试
6
七 、基数排序原程序
#include<string.h> #include<malloc.h>/*malloc()等*/ #include<stdio.h>//EOF(=^z 或 F6),NULL #include<stdlib.h>//atoi() #include<math.h>//floor(0,cell(),abs() #include<iostream> using namespace std; #define MAX_NUM_OF_KEY 8//关键字项数的最大值 #define RADIX 10//关键字基数，此事时十进制整数的基数 #define MAX_SPACE 1000 typedef int InforType;//定义其他数据项的类型 typedef int KeyType;//定义 RedType 类型的关键字为整型 typedef struct { KeyType keys[MAX_NUM_OF_KEY];//关键字数据项 InforType otheritems;//其他数据项 int next; }SLCell;//静态链表的结点类型 typedef struct {
7
八. 程序设计总结
............................................................................ 14
2
一 题目与要求
题目：基数排序
要求：利用数据结构实现对数据进行基数排序
二 问题的提出
给定一组数据{278,1}，{109,2}，{63,3}，{930,4}，{589,5}， {184,6}，{505,7}，{269,8}，{8,9}，{83,10}，按照最低位优先的 方法完成基数排序
8
(*L).r[i].otheritems=D[i-1].otherinfo; itoa(D[i-1].key,c,10);//将十进制整形转换为字符型，存 入c for(j=strlen(c);j<(*L).keynum;j++)// 若 c 的 长度 的 <max 位数，在 c 前补 0 { strcpy(c1,"0"); strcat(c1,c); strcpy(c,c1); } for(j=0;j<(*L).keynum;j++) (*L).r[i].keys[j]=c[(*L).keynum-1-j]; } } int Ord(char c) {//返回 k 的映射（个数整数） return c-'0'; } void Distribute(SLCell r[],int i,ArrType f,ArrType e) {//静态链表 L 的 r 域中记录已按（keys[0],....,keys[i-1]）有序 //第 i 个关键字 keys[i]建立 RADIX 个子表， 使同一个子表记录的 keys[i]相同
7
SLCell r[MAX_SPACE];// 静态链表的可利用空间 ,r[0] 为头结 点 int keynum;//记录的当前关键字个数 int recnum;//静态链表的当前长度 }SLList;//静态链表的类型 typedef int ArrType[RADIX];//指针数组类型 typedef struct { KeyType key;//关键字项 InforType otherinfo;//其他数据项 }RedType; void InitList(SLList *L,RedType D[],int n) {//初始化静态链表 L(把数组 D 中的数据存于 L 中) char c[MAX_NUM_OF_KEY],c1[MAX_NUM_OF_KEY]; int i,j,max=D[0].key;//max 为关键字的最大值 for(i=1;i<n;i++) if(max<D[i].key) max=D[i].key; (*L).keynum=(int)(ceil(log10(max))); (*L).recnum=n; for(i=1;i<n;i++) {
程
设
计
学院：承德石油高等专科学校 班级：计控 1001 姓名：王森 学号：31 所在系：计算机与信息工程系 指导教师：马秋菊
2011 年 06 月 29 号
1
一 题目与要求
.................................................................................
4
e[0]
e[1]
e[2]
e[3]
e[4]
e[5]
e[6]
e[7]
e[8]
e[9]
83 63 8 184 109 278 269 589 505 930
f[0]
f[1]
f[2]
f[3]
f[4]
f[5]
f[6]
f[7]
f[8]
f[9]
(f) 第三趟按十位数分配，修改结点指针域，将链表中的记录分配到 相应的链队列中
11
while(i) { for(j=L.keynum-1;j>=0;j--) printf("%c",L.r[i].keys[j]); printf(" "); i=L.r[i].next; } } void Print(SLList L) {//按数组序号输出静态链表 int i,j; printf("keynum=%d recnum=%d \n",L.keynum,L.recnum); for(i=1;i<=L.recnum;i++) { printf("keys="); for(j=L.keynum;j>=0;j--) printf("%c",L.r[i].keys[j]); printf("otheritems=%d,next=%d",L.r[i].otheritems,L.r[i].next); printf("\n"); } } void RadixSort(SLList *L)
3
四 实验原理
....................................................................................
3
五、总体设计结构图
.........................................................................
10
连接成 //一个链表，e[0...RADIX-1]为各子表的尾指针 int j,t; for(j=0;!f[j];j=Succ(j));//找第一个非空子表，Succ 为求后继函 数 r[0].next=f[j]; t=e[j];//r[0].next 指向第一个非空子表中的第一个结点 while(j<RADIX-1) { for(j=Succ(j);j<RADIX-1&&!f[j];j=Succ(j));// 找下一个非空 子表 if(f[j]) {//链接两个非空子表 r[t].next=f[j]; t=e[j]; } } r[t].next=0;//t 指向最后一个非空子表中的最后一个结点 } void Printl(SLList L) {//按链表输出静态链表 int i=L.r[0].next,j;
9
//f[0..RADIX-1]和 e[0...RADIX-1] 分别指向各个子表只中第一个 和最后一个记录 int j,p; for(j=0;j<RADIX;++j) f[j]=0;//各子表初始化为空表 for(p=r[0].next;p;p=r[p].next) { j=Ord(r[p].keys[i]);//Ord 将记录中的第 i 个关键字映射到 [0...RADIX-1] if(!f[j]) f[j]=p; else r[e[j]].next=p; e[j]=p;//将 p 所指的结点插入第 j 个子表中 } } int Succ(int i) {//求后继函数 return ++i; } void Collect(SLCell r[],ArrType f,ArrType e) {//本算法按 keys[i]自小至大地将 f[0...RADIX-1]所指各子表一次
3
二 问题的提出
...............................................................................
3
三 功能要求 ..................................................................................
三 功能要求
使程序按着最低位优先的顺序把数据重新整理，最小数据在低位， 大数据在高位。
四 实验原理
多关键码排序按照从最主位关键码到最次位关键码或从最次位到 最主位关键码的顺序逐次排序。 最高位优先法：首先根据关键字最高位有效数字进行排序，然后根 据次高位数字进行排序，以此类推，知道根据最低位（个位）有效数 字.............................................................................
6
七 、基数排序原程序
.................................................................
3
五、 总体设计结构图
278 109 63 930 589 184 505 269 8 83
（a）初始记录静态链表 e[0] e[1] e[2] e[3] e[4] e[5] e[6] e[7] e[8] e[9]
269 83 930 63 184 505 8 278 589 109
f[0]
f[1]
f[2]
f[3]
f[4]
f[5]
f[6]
f[7]
f[8]
f[9]
(b) 第一趟按个位数分配修改结点指针域，将链表中的记录分配到相 应的链队列中
930 63 83 184 505 278 8 109 589 269
(c) 第一趟收集：将各队列链接起来，形成单链表
e[0] e[1] e[2] e[3] e[4] e[5] e[6] e[7] e[8] e[9]
109 8 505 930 63 269 278 83 184 589
(g) 第二趟收集：将各队列链接起来，形成单链表。此时序列已有序
5
六、调试与测试
6
七 、基数排序原程序
#include<string.h> #include<malloc.h>/*malloc()等*/ #include<stdio.h>//EOF(=^z 或 F6),NULL #include<stdlib.h>//atoi() #include<math.h>//floor(0,cell(),abs() #include<iostream> using namespace std; #define MAX_NUM_OF_KEY 8//关键字项数的最大值 #define RADIX 10//关键字基数，此事时十进制整数的基数 #define MAX_SPACE 1000 typedef int InforType;//定义其他数据项的类型 typedef int KeyType;//定义 RedType 类型的关键字为整型 typedef struct { KeyType keys[MAX_NUM_OF_KEY];//关键字数据项 InforType otheritems;//其他数据项 int next; }SLCell;//静态链表的结点类型 typedef struct {
7
八. 程序设计总结
............................................................................ 14
2
一 题目与要求
题目：基数排序
要求：利用数据结构实现对数据进行基数排序
二 问题的提出
给定一组数据{278,1}，{109,2}，{63,3}，{930,4}，{589,5}， {184,6}，{505,7}，{269,8}，{8,9}，{83,10}，按照最低位优先的 方法完成基数排序
8
(*L).r[i].otheritems=D[i-1].otherinfo; itoa(D[i-1].key,c,10);//将十进制整形转换为字符型，存 入c for(j=strlen(c);j<(*L).keynum;j++)// 若 c 的 长度 的 <max 位数，在 c 前补 0 { strcpy(c1,"0"); strcat(c1,c); strcpy(c,c1); } for(j=0;j<(*L).keynum;j++) (*L).r[i].keys[j]=c[(*L).keynum-1-j]; } } int Ord(char c) {//返回 k 的映射（个数整数） return c-'0'; } void Distribute(SLCell r[],int i,ArrType f,ArrType e) {//静态链表 L 的 r 域中记录已按（keys[0],....,keys[i-1]）有序 //第 i 个关键字 keys[i]建立 RADIX 个子表， 使同一个子表记录的 keys[i]相同
7
SLCell r[MAX_SPACE];// 静态链表的可利用空间 ,r[0] 为头结 点 int keynum;//记录的当前关键字个数 int recnum;//静态链表的当前长度 }SLList;//静态链表的类型 typedef int ArrType[RADIX];//指针数组类型 typedef struct { KeyType key;//关键字项 InforType otherinfo;//其他数据项 }RedType; void InitList(SLList *L,RedType D[],int n) {//初始化静态链表 L(把数组 D 中的数据存于 L 中) char c[MAX_NUM_OF_KEY],c1[MAX_NUM_OF_KEY]; int i,j,max=D[0].key;//max 为关键字的最大值 for(i=1;i<n;i++) if(max<D[i].key) max=D[i].key; (*L).keynum=(int)(ceil(log10(max))); (*L).recnum=n; for(i=1;i<n;i++) {
