数据结构 多关键字排序课设报告Word下载.docx
- 文档编号:6932712
- 上传时间:2023-05-07
- 格式:DOCX
- 页数:33
- 大小:295.15KB
数据结构 多关键字排序课设报告Word下载.docx
《数据结构 多关键字排序课设报告Word下载.docx》由会员分享,可在线阅读,更多相关《数据结构 多关键字排序课设报告Word下载.docx(33页珍藏版)》请在冰点文库上搜索。
(3)测试数据由随机数生成器产生。
3.流程图
三.详细设计
本程序是对语文,数学,英语,体育,综合这5门成绩按照此顺序进行优先排序。
各科分数为0~100。
由于本实验约定按LSD进行多关键字的排序。
在对个关键字进行排序时采用两种策略:
其一是利用稳定的内部排序法,其二是利用“分配”和“收集”的方法。
所以在一个程序里实现了这两种排序方法。
第一种排序方法由于要使用稳定的排序方法,故参考书上的几种排序方法后,选用了冒泡排序和静态链表存储方式,每一趟排序后,找出最高分。
第二种排序方法利用“分配”与“收集”的基数排序算法,用静态链表存储分数,在一趟排序中,将结点分配到相应的链队列中去,再按从高到低链接起来。
1.数据结构设计
(1)稳定的内部排序法
结构体定义
typedefstructnode//定义结构体
{
intkey[5];
//数据域
structnode*next;
//指针域
}*Score,Lnode;
基本操作
ScoreRandData(Score&
L,intn)
初始条件:
L为创建的静态链表,代表了一个学生成绩的记录,n为生成的随机数个数。
操作结果:
随机生成n个数据并保存到链表L中,返回链表头指针。
ScoreBubbleSort(Score&
L)
L为创建的静态链表
对链表进行冒泡降序排序,返回指针L。
voidPrintScore(Score&
L为创建的静态链表。
在屏幕上显示链表。
(2)“分配”与“收集”的基数排序
ScoreRadixSort(Score&
L为创建的静态链表,代表了一条学生成绩的记录。
对链表L的第n个关键字进行基数排序。
2.主要算法设计
(1)稳定的内部排序
L)//对链表进行冒泡降序排序,返回指针L
Scorep,q,s,t,N;
intn;
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->
q=p->
while(q)
{
n=0;
while(p->
key[n]==q->
key[n]&
&
n<
5)//当前关键字相等则比较下一关键字
{n++;
}
if(p->
key[n]>
q->
key[n])//交换数据域,指针域不变
{
for(inti=0;
i<
5;
i++)
{
t->
key[i]=q->
key[i];
q->
key[i]=p->
p->
key[i]=t->
}
}
if(q->
next==NULL)//当q指向最后一个结点时,将q插入到链表L的尾部
s->
next=q;
s=s->
p->
//p指向最后一个结点
p=p->
q=q->
}
}
s->
next=N->
//将第一个结点插到L的尾部
delete(N);
//销毁指针N
returnL;
(2)“分配”和“收集”的基数排序
L)//对链表L的第n个关键字进行基数排序
Scorehead[radix],tail[radix],p,t;
intd,i,j,m;
for(intn=4;
n>
=0;
n--)
for(d=1;
d<
=2;
d++)
for(i=0;
radix;
i++)//初始化各链队首尾指针
head[i]=tail[i]=NULL;
p=L->
while(p)
if(d==1)m=p->
key[n]%10;
//第一趟取个位分配
elsem=p->
key[n]/10;
//第二趟分配
if(head[m]==NULL)//采用尾插法建立单链表
head[m]=p;
tail[m]=p;
else
tail[m]->
next=p;
}
p=p->
//取下一个待排序元素
for(j=radix-1;
j>
j--)//对每一个链队从大到小进行收集
if(head[j])
if(L->
next==NULL)
L->
next=head[j];
//L指向链队头
t=tail[j];
//t指向队尾
else
t->
//t->
next指向下一个链队头
t->
//最后一个结点指向空
//返回L
3.函数调用关系图
4.程序主要流程
1.随机产生数据:
输入想要排序的学生成绩记录数并随机产生成绩:
L,intn)//随机生成n个数据并保存到链表L中,返回链表头指针
Scorep,q;
L=(Score)malloc(sizeof(Lnode));
//创建带头结点的链表L
q=L;
srand(time(0));
cout<
<
"
输入你所需的数据个数:
;
cin>
>
n;
setw(8)<
语文"
数学"
英语"
体育"
综合"
endl;
for(inti=1;
=n;
i++)
p=(Score)malloc(sizeof(Lnode));
for(intj=0;
j<
j++)
p->
key[j]=rand()%101;
//对每个关键字随机产生0--100的数字
q->
q=p;
p->
//最后一个节点的指针指向空
q=L->
while(q)
for(intk=0;
k<
k++)
cout<
key[k];
cout<
q=q->
//返回结构体指针
2.菜单显示实现:
voidMenu()//菜单
inta,b,n;
ScoreL;
doubletime;
##################################################"
endl
<
本程序可以按关键字的优先关系排序对成绩排序。
随机产生数据"
RandData(L,n);
//随机产生数据
endl<
#################################################"
endl
请选择:
"
1.对数据进行冒泡法排序"
2.对数据进行基数排序"
do
cin>
b;
if(b==1)
BubbleSort(L);
//调用冒泡排序
PrintScore(L);
//打印结果
elseif(b==2)
RadixSort(L);
//调用基数排序
PrintScore(L);
//}
elsecout<
选择的操作不存在!
!
请重新输入(1或者2)"
}while(b!
=1&
b!
=2);
3.屏幕上显示链表
voidPrintScore(Score&
L)//在屏幕上显示链表
Scorep;
for(inti=0;
i++)//依次输出5个数据
p->
4.内部稳定排序算法
ScoreBubbleSort(Score&
next==NULL)//当q指向最后一个结点时,将q插入到链表L的尾部
5.“分配”与“收集”的基数排序
ScoreRadixSort(Score&
6.主函数:
voidmain()
intc;
Menu();
//调用菜单
结束?
输入0,输入其他继续"
c;
while(c!
=0);
//c等于0停止循环
四.调试分析:
1.代码设计分析
看到题目“多关键字排序”后,首先对课本的第十章所有的算法复习了一遍并对所有的排序方法进行了总结。
内部排序法可详细的分为:
插入排序(直接插入排序),快速排序,选择排序(简单选择排序),归并排序,冒泡排序,希尔排序,堆排序,基数排序。
通过对算法的分析。
可将这些排序方法分为稳定排序和不稳定排序。
其中不稳定排序包括快速排序和堆排序,其余都为稳定排序方法。
故基于对算法的时间空间复杂度和熟练程度,稳定的内部排序法,我选择了冒泡排序法。
由于待排序的记录序列可有3种存储方式:
顺序存储,链表存储和地址存储。
考虑到算法的执行效率和当前能力,我选择了第二种记录序列的存储方式。
故确定了排序方法和记录的存储方式后,开始设计代码。
程序的重要设计模块为:
结构体定义,算法设计,界面设计和主函数的定义。
2.调试过程中的问题
(1)在基数排序中,输入2后一直无显示,如下图所示:
经调试检查后发现是因为排序完一条记录后,没有将指针指向下一条记录。
所以在while()循环结束处添加一条指向下一条记录第指针p=p->
如下代码所示:
while(p)
if(head[m]==NULL)
//添加此行代码
(2)基数排序中始终只能排序一个关键字。
不能实现在主关键字相等的情况下此次键字按照从高分到低分的排序。
如下情况所示:
经调试后,在每趟分配和收集前添加代码for(intn=4;
n--),即可进行多关键字排序。
成功运行后如下:
3.经验和体会
本次课程设计我做的是多关键字LSD排序,在上数据结构课时,我只是对LSD排序有了一个初步的认识,对“分配”和“收集”的方法也没有深究。
在做这次实验时,我又重新翻开书本进行了一次深入的研究,LSD(最低位优先)法是从最次位关键字起进行排序,然后再对高一位的关键字进行排序,依次重复,直至对最高位关键字进行排序后便成为一个有序序列。
“分配”和“收集”方法是在一趟排序中,将结点分配到相应的链队列中去,然后再链接起来。
编程过程中我还用到了静态链表这个数据结构。
在实验中,我还总结了一下选择排序与“分配”和“收集”法的优缺点,在记录较少的情况下,前者是一个不错的选择,但是当记录非常多的时候,后者便体现出优势。
从它们所需的辅助储存空间来看,前者很有优势,而后者需要2*RADIX个计数单元。
总之,通过这次课程设计,不仅编程能力,找错能力和耐心得到的提高,我对数据结构这门课的理解也更深入了一个层次。
在本实验中主要侧重的是排序的方法,考生信息很简单,主要只有分数。
要使程序更完美,还可以向结构体中增加其它信息,如姓名、考号、性别等,使信息更完整。
五.用户手册
按照提示输入想要排序的记录数比如输入24:
此为随机产生的24条学生成绩的记录,选择输入1或2,进行冒泡排序或基数排序,如先选择1
输入一个非零数字,重新开始,如下图:
输入24
输入2
输入0结束
六.测试结果
(1)冒泡排序
输入:
输出:
(2)基数排序
七.源代码(带注释)
#include<
iostream>
#include<
cstdlib>
iomanip>
ctime>
fstream>
#defineradix11//基数
usingnamespacestd;
while(q)//将数据写入文件new.txt,以及在屏幕输出
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 多关键字排序课设报告 关键字 排序 报告