数据结构 多关键字排序课设报告
目录
一．设计题目 ……………………………………2
二．需求分析 ……………………………………2
1.程序设计问题描述…………………………………2
2.基本要求 …………………………………………2
3.流程图 …………………………………………2
三．详细设计 ………………………………………3
1.数据结构定义………………………………………4
2.主要算法设计 ……………………………………5
3.函数调用关系图……………………………………8
4.程序主要流程 ……………………………………8
四．调试分析………………………………………13
五．用户手册 ………………………………………15
六．测试结果 ………………………………………19
七．源代码（带注释 ）………………………………21
八．参考文献…………………………………………26
一．设计题目
多关键字排序
二．需求分析
1.程序设计问题描述
多关键字的排序有其一定的实用范围。例如:在进行高考分数处理时，除了需对总分进行排序外，不同的专业对单科分数的要求不同，因此尚需在总分相同的情况下，按用户提出的单科分数的次序要求排出考生录取的次序。
2.基本要求
(1)假设待排序的记录数不超过10000，表中记录的关键字数不超过5，各个关键字的范围均为0至100。按用户给定的进行排序的关键字的优先关系，输出排序结果。
(2)约定按LSD法进行多关键字的排序。在对各个关键字进行排序时采用两种策略:其一是利用稳定的内部排序法，其二是利用"分配"和"收集"的方法。并综合比较这两种策略。
（3）测试数据由随机数生成器产生。
3.流程图
三．详细设计
本程序是对语文，数学，英语，体育，综合这5门成绩按照此顺序进行优先排序。各科分数为0～100。
由于本实验约定按LSD进行多关键字的排序。在对个关键字进行排序时采用两种策略：其一是利用稳定的内部排序法，其二是利用“分配”和“收集”的方法。所以在一个程序里实现了这两种排序方法。
第一种排序方法由于要使用稳定的排序方法，故参考书上的几种排序方法后，选用了冒泡排序和静态链表存储方式，每一趟排序后，找出最高分 。第二种排序方法利用“分配”与“收集”的基数排序算法，用静态链表存储分数，在一趟排序中，将结点分配到相应的链队列中去，再按从高到低链接起来。
1.数据结构设计
（1）稳定的内部排序法
结构体定义
typedef struct node //定义结构体
{
int key[5]; //数据域
struct node *next; //指针域
}*Score,Lnode;
基本操作
Score RandData(Score &L,int n)
初始条件：L为创建的静态链表，代表了一个学生成绩的记录，n为生成的随机数个数。
操作结果：随机生成n个数据并保存到链表L中，返回链表头指针。
Score BubbleSort(Score &L)
初始条件：L为创建的静态链表
操作结果：对链表进行冒泡降序排序，返回指针L。
void PrintScore(Score &L)
初始条件：L为创建的静态链表。
操作结果：在屏幕上显示链表。
（2）“分配”与“收集”的基数排序
结构体定义
typedef struct node //定义结构体
{
int key[5]; //数据域
struct node *next; //指针域
}*Score,Lnode;
基本操作
Score RadixSort(Score &L)
初始条件：L为创建的静态链表，代表了一条学生成绩的记录。
操作结果：对链表L的第n个关键字进行基数排序。
void PrintScore(Score &L)
初始条件：L为创建的静态链表。
操作结果：在屏幕上显示链表。
2.主要算法设计
（1）稳定的内部排序
Score BubbleSort(Score &L) //对链表进行冒泡降序排序，返回指针L
{
Score p,q,s,t,N;
int n;
t=(Score)malloc(sizeof(node));
N=(Score)malloc(sizeof(node));
N->next=L->next; //把N指向链表L
L->next=NULL; //L重新指向空
s=L; //创建新的链表L
while(N->next->next)
{
p=N->next;
q=p->next;
while(q)
{
n=0;
while(p->key[n]==q->key[n]&&n<5) //当前关键字相等则比较下一关键字
{n++;}
if(p->key[n]>q->key[n]) //交换数据域，指针域不变
{
for(int i=0;i<5;i++)
{
t->key[i]=q->key[i];
q->key[i]=p->key[i];
p->key[i]=t->key[i];
}
}
if(q->next==NULL) //当q指向最后一个结点时，将q插入到链表L的 尾部
{
s->next=q;
s=s->next;
p->next=NULL; //p指向最后一个结点
}
p=p->next;
q=q->next;
}
}
s->next=N->next; //将第一个结点插到L的尾部
delete(N); //销毁指针N
return L;
}
（2）“分配”和“收集”的基数排序
Score RadixSort(Score &L) //对链表L的第n个关键字进行基数排序
{
Score head[radix],tail[radix],p,t;
int d,i,j,m;
for(int n=4;n>=0;n--)
{
for(d=1;d<=2;d++)
{
for(i=0;i<radix;i++) //初始化各链队首尾指针
head[i]=tail[i]=NULL;
p=L->next;
while(p)
{
if(d==1) m=p->key[n]%10; //第一趟取个位分配
else m=p->key[n]/10; //第二趟分配
if(head[m]==NULL) //采用尾插法建立单链表
{
head[m]=p;
tail[m]=p;
}
else
{
tail[m]->next=p;
tail[m]=p;
}
p=p->next; //取下一个待排序元素
}
L->next=NULL;
for(j=radix-1;j>=0;j--) //对每一个链队从大到小进行收集
if(head[j])
{
if(L->next==NULL)
{
L->next=head[j]; //L指向链队头
t=tail[j]; //t指向队尾
}
else
{
t->next=head[j]; //t->next指向下一个链队头
t=tail[j];
}
}
t->next=NULL; //最后一个结点指向空
}
}
return L; //返回L
}
3.函数调用关系图
4.程序主要流程
1.随机产生数据：输入想要排序的学生成绩记录数并随机产生成绩：
typedef struct node //定义结构体
{
int key[5]; //数据域
struct node *next; //指针域
}*Score,Lnode;
Score RandData(Score &L,int n) //随机生成n个数据并保存到链表L中，返回链表头指针
{
Score p,q;
L=(Score)malloc(sizeof(Lnode)); //创建带头结点的链表L
L->next=NULL;
q=L;
srand(time(0));
cout<<"输入你所需的数据个数：";
cin>>n;
cout<<setw(8)<<"语文"<<setw(8)<<"数学"<<setw(8)<<"英语"<<setw(8)<<"体育"<<setw(8)<<"综合"<<endl;
for(int i=1;i<=n;i++)
{
p=(Score)malloc(sizeof(Lnode));
for(int j=0;j<5;j++)
{
p->key[j]=rand()%101; //对每个关键字随机产生0--100的数字
}
q->next=p;
q=p;
}
p->next=NULL; //最后一个节点的指针指向空
q=L->next;
while(q)
{
for(int k=0;k<5;k++)
{
cout<<setw(8)<<q->key[k];
}
cout<<endl;
q=q->next;
}
return L; //返回结构体指针
}
2.菜单显示实现：
void Menu() //菜单
{
int a,b,n;
Score L;
double time;
cout<<"##################################################"<<endl
<<" 本程序可以按关键字的优先关系排序对成绩排序。"<<endl
<<" 随机产生数据 "<<endl
<<"##################################################"<<endl;
RandData(L,n); //随机产生数据
cout<<endl<<endl
<<"#################################################"<<endl
<<" 请选择： "<<endl
<<" 1.对数据进行冒泡法排序 "<<endl
<<" 2.对数据进行基数排序 "<<endl
<<"#################################################"<<endl;
do
{
cin>>b;
if(b==1)
{
cout<<setw(8)<<"语文"<<setw(8)<<"数学"<<setw(8)<<"英语"<<setw(8)<<"体育"<<setw(8)<<"综合"<<endl;
BubbleSort(L); //调用冒泡排序
PrintScore(L); //打印结果
}
else if(b==2)
{
RadixSort(L); //调用基数排序
PrintScore(L);
//}
}
else cout<<"选择的操作不存在！！请重新输入（1或者2）"<<endl;
}while(b!=1&&b!=2);
}
3.屏幕上显示链表
void PrintScore(Score &L) //在屏幕上显示链表
{
Score p;
p=L->next;
while(p)
{
for(int i=0;i<5;i++) //依次输出5个数据
cout<<setw(8)<<p->key[i];
cout<<endl;
p=p->next;
}
cout<<endl;
}
4.内部稳定排序算法
Score BubbleSort(Score &L) //对链表进行冒泡降序排序，返回指针L
{
Score p,q,s,t,N;
int n;
t=(Score)malloc(sizeof(node));
N=(Score)malloc(sizeof(node));
N->next=L->next; //把N指向链表L
L->next=NULL; //L重新指向空
s=L; //创建新的链表L
while(N->next->next)
{
p=N->next;
q=p->next;
while(q)
{
n=0;
while(p->key[n]==q->key[n]&&n<5) //当前关键字相等则比较下一关键字
{n++;}
if(p->key[n]>q->key[n]) //交换数据域，指针域不变
{
for(int i=0;i<5;i++)
{
t->key[i]=q->key[i];
q->key[i]=p->key[i];
p->key[i]=t->key[i];
}
}
if(q->next==NULL) //当q指向最后一个结点时，将q插入到链表L的尾部
{
s->next=q;
s=s->next;
p->next=NULL; //p指向最后一个结点
}
p=p->next;
q=q->next;
}
}
s->next=N->next; //将第一个结点插到L的尾部
delete(N); //销毁指针N
return L;
}
5.“分配”与“收集”的基数排序
Score RadixSort(Score &L) //对链表L的第n个关键字进行基数排序
{
Score head[radix],tail[radix],p,t;
int d,i,j,m;
for(int n=4;n>=0;n--)
{
for(d=1;d<=2;d++)
{
for(i=0;i<radix;i++) //初始化各链队首尾指针
head[i]=tail[i]=NULL;
p=L->next;
while(p)
{
if(d==1) m=p->key[n]%10; //第一趟取个位分配
else m=p->key[n]/10; //第二趟分配
if(head[m]==NULL) //采用尾插法建立单链表
{
head[m]=p;
tail[m]=p;
}
else
{
tail[m]->next=p;
tail[m]=p;
}
p=p->next; //取下一个待排序元素
}
L->next=NULL;
for(j=radix-1;j>=0;j--) //对每一个链队从大到小进行收集
if(head[j])
{
if(L->next==NULL)
{
L->next=head[j]; //L指向链队头
t=tail[j]; //t指向队尾
}
else
{
t->next=head[j]; //t->next指向下一个链队头
t=tail[j];
}
}
t->next=NULL; //最后一个结点指向空
}
}
return L; //返回L
}
6.主函数：
void main()
{
int c;
do
{
Menu(); //调用菜单
cout<<"结束？输入0，输入其他继续"<<endl;
cin>>c;
}
while(c!=0) ; //c等于0停止循环
}
四．调试分析：
1.代码设计分析
看到题目“多关键字排序”后，首先对课本的第十章所有的算法复习了一遍并对所有的排序方法进行了总结。内部排序法可详细的分为：插入排序（直接插入排序），快速排序，选择排序（简单选择排序），归并排序，冒泡排序，希尔排序，堆排序，基数排序。通过对算法的分析。可将这些排序方法分为稳定排序和不稳定排序。其中不稳定排序包括快速排序和堆排序，其余都为稳定排序方法。故基于对算法的时间空间复杂度和熟练程度，稳定的内部排序法，我选择了冒泡排序法。由于待排序的记录序列可有3种存储方式：顺序存储，链表存储和地址存储。考虑到算法的执行效率和当前能力，我选择了第二种记录序列的存储方式。故确定了排序方法和记录的存储方式后，开始设计代码。程序的重要设计模块为：结构体定义，算法设计，界面设计和主函数的定义。
2.调试过程中的问题
（1）在基数排序中，输入2后一直无显示，如下图所示：
经调试检查后发现是因为排序完一条记录后，没有将指针指向下一条记录。所以在while（）循环结束处添加一条指向下一条记录第指针p=p->next; 如下代码所示：
while(p)
{
if(d==1) m=p->key[n]%10;
else m=p->key[n]/10;
if(head[m]==NULL)
{
head[m]=p;
tail[m]=p;
}
else
{
tail[m]->next=p;
tail[m]=p;
}
p=p->next; //添加此行代码
}
（2）基数排序中始终只能排序一个关键字。不能实现在主关键字相等的情况下此次键字按照从高分到低分的排序。如下情况所示：
经调试后，在每趟分配和收集前添加代码for(int n=4;n>=0;n--)，即可进行多关键字排序。
成功运行后如下：
3.经验和体会
本次课程设计我做的是多关键字LSD排序，在上数据结构课时，我只是对LSD排序有了一个初步的认识，对“分配”和“收集”的方法也没有深究。在做这次实验时，我又重新翻开书本进行了一次深入的研究，LSD(最低位优先）法是从最次位关键字起进行排序，然后再对高一位的关键字进行排序，依次重复，直至对最高位关键字进行排序后便成为一个有序序列。“分配”和“收集”方法是在一趟排序中，将结点分配到相应的链队列中去，然后再链接起来。编程过程中我还用到了静态链表这个数据结构。在实验中，我还总结了一下选择排序与“分配”和“收集”法的优缺点，在记录较少的情况下，前者是一个不错的选择，但是当记录非常多的时候，后者便体现出优势。从它们所需的辅助储存空间来看，前者很有优势，而后者需要2*RADIX个计数单元。总之，通过这次课程设计，不仅编程能力，找错能力和耐心得到的提高，我对数据结构这门课的理解也更深入了一个层次。在本实验中主要侧重的是排序的方法，考生信息很简单，主要只有分数。要使程序更完美，还可以向结构体中增加其它信息，如姓名、考号、性别等，使信息更完整。
五．用户手册
按照提示输入想要排序的记录数 比如输入24：
此为随机产生的24条学生成绩的记录，选择输入1或2，进行冒泡排序或基数排序，如先选择1
输入一个非零数字，重新开始,如下图：
输入24
输入2
输入0 结束
六．测试结果
（1）冒泡排序
输入：
输出：
（2）基数排序
输入：
输出：
七．源代码（带注释）
#include<iostream>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<fstream>
#define radix 11 //基数
using namespace std;
typedef struct node //定义结构体
{
int key[5]; //数据域
struct node *next; //指针域
}*Score,Lnode;
Score RandData(Score &L,int n) //随机生成n个数据并保存到链表L中，返回链表头指针
{
Score p,q;
L=(Score)malloc(sizeof(Lnode)); //创建带头结点的链表L
L->next=NULL;
q=L;
srand(time(0));
cout<<"输入你所需的数据个数：";
cin>>n;
cout<<setw(8)<<"语文"<<setw(8)<<"数学"<<setw(8)<<"英语"<<setw(8)<<"体育"<<setw(8)<<"综合"<<endl;
for(int i=1;i<=n;i++)
{
p=(Score)malloc(sizeof(Lnode));
for(int j=0;j<5;j++)
{
p->key[j]=rand()%101; //对每个关键字随机产生0--100的数字
}
q->next=p;
q=p;
}
p->next=NULL; //最后一个节点的指针指向空
q=L->next;
while(q) //将数据写入文件new.txt，以及在屏幕输出
{
for(int k=0;k<5;k++)
{
cout<<setw(8)<<q->key[k];
}
cout<<endl;
q=q->next;
}
return L; //返回结构体指针
}
Score BubbleSort(Score &L) //对链表进行冒泡降序排序，返回指针L
{
Score p,q,s,t,N;
int n;
t=(Score)malloc(sizeof(node));
N=(Score)malloc(sizeof(node));
N->next=L->next; //把N指向链表L
L->next=NULL; //L重新指向空
s=L; //创建新的链表L
while(N->next->next)
{
p=N->next;
q=p->next;
while(q)
{
n=0;
while(p->key[n]==q->key[n]&&n<5) //当前关键字相等则比较下一关键字
{n++;}
if(p->key[n]>q->key[n]) //交换数据域，指针域不变
{
for(int i=0;i<5;i++)
{
t->key[i]=q->key[i];
q->key[i]=p->key[i];
p->key[i]=t->key[i];
}
}
if(q->next==NULL) //当q指向最后一个结点时，将q插入到链表L的尾部
{
s->next=q;
s=s->next;
p->next=NULL; //p指向最后一个结点
}
p=p->next;
q=q->next;
}
}
s->next=N->next; //将第一个结点插到L的尾部
delete(N); //销毁指针N
return L;
}
Score RadixSort(Score &L) //对链表L的第n个关键字进行基数排序
{
Score head[radix],tail[radix],p,t;
int d,i,j,m;
for(int n=4;n>=0;n--)
{
for(d=1;d<=2;d++)
{
for(i=0;i<radix;i++) //初始化各链队首尾指针
head[i]=tail[i]=NULL;
p=L->next;
while(p)
{
if(d==1) m=p->key[n]%10; //第一趟取个位分配
else m=p->key[n]/10; //第二趟分配
if(head[m]==NULL) //采用尾插法建立单链表
{
head[m]=p;
tail[m]=p;
}
else
{
tail[m]->next=p;
tail[m]=p;
}
p=p->next; //取下一个待排序元素
}
L->next=NULL;
for(j=radix-1;j>=0;j--) //对每一个链队从大到小进行收集
if(head[j])
{
if(L->next==NULL)
{
L->next=head[j]; //L指向链队头
t=tail[j]; //t指向队尾
}
else
{
t->next=head[j]; //t->next指向下一个链队头
t=tail[j];
}
}
t->next=NULL; //最后一个结点指向空
}
}
return L; //返回L
}
void PrintScore(Score &L) //在屏幕上显示链表
{
Score p;
p=L->next;
while(p)
{
for(int i=0;i<5;i++) //依次输出5个数据
cout<<setw(8)<<p->key[i];
cout<<endl;
p=p->next;
}
cout<<endl;
}
void Menu() //菜单
{
int a,b,n;
Score L;
double time;
cout<<"##################################################"<<endl
<<" 本程序可以按关键字的优先关系排序对成绩排序。"<<endl
<<" 随机产生数据 "<<endl
<<"##################################################"<<endl;
RandData(L,n); //随机产生数据
cout<<endl<<endl
<<"#################################################"<<endl
<<" 请选择： "<<endl
<<" 1.对数据进行冒泡法排序 "<<endl
<<" 2.对数据进行基数排序 "<<endl
<<"#################################################"<<endl;
do
{
cin>>b;
if(b==1)
{
cout<<setw(8)<<"语文"<<setw(8)<<"数学"<<setw(8)<<"英语"<<setw(8)<<"体育"<<setw(8)<<"综合"<<endl;
BubbleSort(L); //调用冒泡排序
PrintScore(L); //打印结果
}
else if(b==2)
{
RadixSort(L); //调用基数排序
PrintScore(L);
//}
}
else cout<<"选择的操作不存在！！请重新输入（1或者2）"<<endl;
}while(b!=1&&b!=2);
}
void main()
{
int c;
do
{
Menu(); //调用菜单
cout<<"结束？输入0，输入其他继续"<<endl;
cin>>c;
}
while(c!=0) ; //c等于0停止循环
}
八．参考文献
1.数据结构（c语言版） 严蔚敏 吴伟民 编著
-
《数据结构》实验报告——排序
数据结构实验报告排序实验题目输入十个数从插入排序快速排序选择排序三类算法中各选一种编程实现实验所使用的数据结构内容及编程思路1插入…
-
数据结构排序实验报告
数据结构课程设计报告实验五排序一需求分析本演示程序用C60编写完成各种排序的实现对输入的一组数字实现不同的排序方法对其由小到大顺序…
- 数据结构排序算法实验报告
-
数据结构实验报告——排序
1实验要求实验目的学习实现对比各种排序算法掌握各种排序算法的优劣以及各种算法使用的情况实验内容使用简单数组实现下面各种排序算法并进…
-
数据结构实验8排序
实验八排序一实验目的1熟悉掌握教材中所介绍的几种排序方法2学会分析各种内排序算法的性能二实验内容1随机产生20位整数2输入序列编写…
-
数据结构课程设计报告
CENTRALSOUTHUNIVERSITY数据结构课程设计报告题目学生姓名指导教师学院专业班级完成时间交通旅游图的最短路径问题摘…
-
数据结构课程设计总结
课程设计说明书课程名：《数据结构课程设计》题目：一元多项式运算系统20##年1月一、课程认识数据结构课程主要是研究非数值计算的程序…
-
数据结构课程设计报告(含代码)
西安郵電學院数据结构课程设计报告题目校园导航系统院系名称计算机学院专业名称计算机科学与技术班级学生姓名学号8位指导教师设计起止时间…
-
数据结构课程设计报告(模版)
攀枝花学院学生课程设计论文题目学生姓名学号20xx108010所在院系数学与计算机学院专业计算机科学与技术专业班级20xx级计算机…
-
数据结构课程设计报告
数据结构课程设计报告学生姓名学号班级地信10901长江大学20XX.6目录1.需求分析......................…
-
顺序表-数据结构与算法课程设计报告
合肥学院计算机科学与技术系课程设计报告20xx20xx学年第二学期课程数据结构与算法设计顺序表结构的相关函数库课程设计名称学学专指…