数据结构 多关键字排序课设报告

《数据结构 多关键字排序课设报告》由会员分享，可在线阅读，更多相关《数据结构 多关键字排序课设报告（26页珍藏版）》请在装配图网上搜索。

1、数据结构课设报告目录一 设计题目 2 二 需求分析 2 1.程序设计问题描述2 2.基本要求 2 3. 流程图 2三 详细设计 3 1.数据结构定义4 2.主要算法设计 5 3.函数调用关系图84.程序主要流程 8四 调试分析 13五 用户手册 15六 测试结果 19七 源代码（带注释 ）21八参考文献26一设计题目 多关键字排序二需求分析 1.程序设计问题描述 多关键字的排序有其一定的实用范围。例如:在进行高考分数处理时，除了需对总分进行排序外，不同的专业对单科分数的要求不同，因此尚需在总分相同的情况下，按用户提出的单科分数的次序要求排出考生录取的次序。 2.基本要求 (1)假设待排序的记录

2、数不超过10000，表中记录的关键字数不超过5，各个关键字的范围均为0至100。按用户给定的进行排序的关键字的优先关系，输出排序结果。 (2)约定按LSD法进行多关键字的排序。在对各个关键字进行排序时采用两种策略:其一是利用稳定的内部排序法，其二是利用分配和收集的方法。并综合比较这两种策略。 （3）测试数据由随机数生成器产生。开始 3.流程图 输出菜单 输入记录数选择排序方法输入不是1或2，重新输入选择排序方法判断2 1基数排序内部排序显示排序结果输入结束或继续执行判断输入非零值0继续执行退出结束三详细设计 本程序是对语文，数学，英语，体育，综合这5门成绩按照此顺序进行优先排序。各科分数为01

3、00。 由于本实验约定按LSD进行多关键字的排序。在对个关键字进行排序时采用两种策略：其一是利用稳定的内部排序法，其二是利用“分配”和“收集”的方法。所以在一个程序里实现了这两种排序方法。 第一种排序方法由于要使用稳定的排序方法，故参考书上的几种排序方法后，选用了冒泡排序和静态链表存储方式，每一趟排序后，找出最高分 。第二种排序方法利用“分配”与“收集”的基数排序算法，用静态链表存储分数，在一趟排序中，将结点分配到相应的链队列中去，再按从高到低链接起来。 1.数据结构设计（1）稳定的内部排序法结构体定义typedef struct node /定义结构体 int key5; /数据域struc

4、t 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 /定义结

5、构体 int key5; /数据域struct node *next; /指针域*Score,Lnode;基本操作Score RadixSort(Score &L) 初始条件：L为创建的静态链表，代表了一条学生成绩的记录。操作结果：对链表L的第n个关键字进行基数排序。void PrintScore(Score &L) 初始条件：L为创建的静态链表。操作结果：在屏幕上显示链表。2. 主要算法设计（1）稳定的内部排序Score BubbleSort(Score &L) /对链表进行冒泡降序排序，返回指针LScore p,q,s,t,N;int n;t=(Score)malloc(sizeof(no

6、de);N=(Score)malloc(sizeof(node);N-next=L-next; /把N指向链表LL-next=NULL; /L重新指向空s=L; /创建新的链表Lwhile(N-next-next)p=N-next;q=p-next;while(q)n=0;while(p-keyn=q-keyn&nkeynq-keyn) /交换数据域，指针域不变for(int i=0;ikeyi=q-keyi;q-keyi=p-keyi;p-keyi=t-keyi;if(q-next=NULL) /当q指向最后一个结点时，将q插入到链表L的 尾部s-next=q;s=s-next;p-next

7、=NULL; /p指向最后一个结点p=p-next;q=q-next;s-next=N-next; /将第一个结点插到L的尾部delete(N); /销毁指针Nreturn L;（2） “分配”和“收集”的基数排序Score RadixSort(Score &L) /对链表L的第n个关键字进行基数排序Score headradix,tailradix,p,t;int d,i,j,m;for(int n=4;n=0;n-) for(d=1;d=2;d+)for(i=0;inext;while(p)if(d=1) m=p-keyn%10; /第一趟取个位分配else m=p-keyn/10; /第

8、二趟分配if(headm=NULL) /采用尾插法建立单链表headm=p; tailm=p;elsetailm-next=p;tailm=p;p=p-next; /取下一个待排序元素L-next=NULL; for(j=radix-1;j=0;j-) /对每一个链队从大到小进行收集if(headj)if(L-next=NULL)L-next=headj; /L指向链队头t=tailj; /t指向队尾elset-next=headj; /t-next指向下一个链队头t=tailj; t-next=NULL; /最后一个结点指向空return L; /返回L3. 函数调用关系图void main

9、() 调用RadixSort(L) PrintScore(L)BubbleSort(L)PrintScore(L)RandData(L,n)Menu()If（b=2）调用If（b=1）调用调用4. 程序主要流程 1.随机产生数据：输入想要排序的学生成绩记录数并随机产生成绩：typedef struct node /定义结构体 int key5; /数据域struct node *next; /指针域*Score,Lnode;Score RandData(Score &L,int n) /随机生成n个数据并保存到链表L中，返回链表头指针Score p,q;L=(Score)malloc(size

10、of(Lnode); /创建带头结点的链表LL-next=NULL;q=L; srand(time(0); coutn;coutsetw(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;jkeyj=rand()%101; /对每个关键字随机产生0-100的数字q-next=p;q=p;p-next=NULL; /最后一个节点的指针指向空 q=L-next; while(q) for(int k=0;k5;k+)coutsetw(8)

11、keyk;coutnext;return L; /返回结构体指针2. 菜单显示实现： void Menu() /菜单int a,b,n; Score L;double time;cout#endl 本程序可以按关键字的优先关系排序对成绩排序。endl 随机产生数据 endl#endl;RandData(L,n); /随机产生数据coutendlendl#endl 请选择： endl 1.对数据进行冒泡法排序 endl 2.对数据进行基数排序 endl#b; if(b=1)coutsetw(8)语文setw(8)数学setw(8)英语setw(8)体育setw(8)综合endl; BubbleS

12、ort(L); /调用冒泡排序 PrintScore(L); /打印结果 else if(b=2) RadixSort(L); /调用基数排序 PrintScore(L);/ else cout选择的操作不存在！请重新输入（1或者2）next;while(p)for(int i=0;i5;i+) /依次输出5个数据coutsetw(8)keyi;coutnext;coutnext=L-next; /把N指向链表LL-next=NULL; /L重新指向空s=L; /创建新的链表Lwhile(N-next-next)p=N-next;q=p-next;while(q)n=0;while(p-key

13、n=q-keyn&nkeynq-keyn) /交换数据域，指针域不变for(int i=0;ikeyi=q-keyi;q-keyi=p-keyi;p-keyi=t-keyi;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); /销毁指针Nreturn L;5. “分配”与“收集”的基数排序 Score RadixSort(Score &L) /对链表L的第n个关键字进行基数

14、排序Score headradix,tailradix,p,t;int d,i,j,m;for(int n=4;n=0;n-) for(d=1;d=2;d+)for(i=0;inext;while(p)if(d=1) m=p-keyn%10; /第一趟取个位分配else m=p-keyn/10; /第二趟分配if(headm=NULL) /采用尾插法建立单链表headm=p; tailm=p;elsetailm-next=p;tailm=p;p=p-next; /取下一个待排序元素L-next=NULL; for(j=radix-1;j=0;j-) /对每一个链队从大到小进行收集if(head

15、j)if(L-next=NULL)L-next=headj; /L指向链队头t=tailj; /t指向队尾elset-next=headj; /t-next指向下一个链队头t=tailj; t-next=NULL; /最后一个结点指向空return L; /返回L6. 主函数： void main() int c;doMenu(); /调用菜单cout结束？输入0，输入其他继续c;while(c!=0) ; /c等于0停止循环四调试分析： 1.代码设计分析 看到题目“多关键字排序”后，首先对课本的第十章所有的算法复习了一遍并对所有的排序方法进行了总结。内部排序法可详细的分为：插入排序（直接插入

16、排序），快速排序，选择排序（简单选择排序），归并排序，冒泡排序，希尔排序，堆排序，基数排序。通过对算法的分析。可将这些排序方法分为稳定排序和不稳定排序。其中不稳定排序包括快速排序和堆排序，其余都为稳定排序方法。故基于对算法的时间空间复杂度和熟练程度，稳定的内部排序法，我选择了冒泡排序法。由于待排序的记录序列可有3种存储方式：顺序存储，链表存储和地址存储。考虑到算法的执行效率和当前能力，我选择了第二种记录序列的存储方式。故确定了排序方法和记录的存储方式后，开始设计代码。程序的重要设计模块为：结构体定义，算法设计，界面设计和主函数的定义。 2.调试过程中的问题 （1）在基数排序中，输入2后一直无显

17、示，如下图所示：经调试检查后发现是因为排序完一条记录后，没有将指针指向下一条记录。所以在while（）循环结束处添加一条指向下一条记录第指针p=p-next; 如下代码所示：while(p)if(d=1) m=p-keyn%10; else m=p-keyn/10; if(headm=NULL) headm=p; tailm=p;elsetailm-next=p;tailm=p;p=p-next; /添加此行代码 （2）基数排序中始终只能排序一个关键字。不能实现在主关键字相等的情况下此次键字按照从高分到低分的排序。如下情况所示： 经调试后，在每趟分配和收集前添加代码for(int n=4;n=

18、0;n-)，即可进行多关键字排序。成功运行后如下：3. 经验和体会 本次课程设计我做的是多关键字LSD排序，在上数据结构课时，我只是对LSD排序有了一个初步的认识，对“分配”和“收集”的方法也没有深究。在做这次实验时，我又重新翻开书本进行了一次深入的研究，LSD(最低位优先）法是从最次位关键字起进行排序，然后再对高一位的关键字进行排序，依次重复，直至对最高位关键字进行排序后便成为一个有序序列。“分配”和“收集”方法是在一趟排序中，将结点分配到相应的链队列中去，然后再链接起来。编程过程中我还用到了静态链表这个数据结构。在实验中，我还总结了一下选择排序与“分配”和“收集”法的优缺点，在记录较少的情

19、况下，前者是一个不错的选择，但是当记录非常多的时候，后者便体现出优势。从它们所需的辅助储存空间来看，前者很有优势，而后者需要2*RADIX个计数单元。总之，通过这次课程设计，不仅编程能力，找错能力和耐心得到的提高，我对数据结构这门课的理解也更深入了一个层次。在本实验中主要侧重的是排序的方法，考生信息很简单，主要只有分数。要使程序更完美，还可以向结构体中增加其它信息，如姓名、考号、性别等，使信息更完整。五用户手册 按照提示输入想要排序的记录数 比如输入24： 此为随机产生的24条学生成绩的记录，选择输入1或2，进行冒泡排序或基数排序，如先选择1输入一个非零数字，重新开始,如下图：输入24输入2输

20、入0 结束六测试结果（1） 冒泡排序 输入： 输出：（2） 基数排序 输入： 输出：七源代码（带注释） #include#include#include#include#include#define radix 11 /基数using namespace std;typedef struct node /定义结构体 int key5; /数据域struct node *next; /指针域*Score,Lnode;Score RandData(Score &L,int n) /随机生成n个数据并保存到链表L中，返回链表头指针Score p,q;L=(Score)malloc(sizeof(Ln

21、ode); /创建带头结点的链表LL-next=NULL;q=L; srand(time(0); coutn;coutsetw(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;jkeyj=rand()%101; /对每个关键字随机产生0-100的数字q-next=p;q=p;p-next=NULL; /最后一个节点的指针指向空 q=L-next; while(q) /将数据写入文件new.txt，以及在屏幕输出for(int k=0

22、;k5;k+)coutsetw(8)keyk;coutnext;return L; /返回结构体指针Score BubbleSort(Score &L) /对链表进行冒泡降序排序，返回指针LScore p,q,s,t,N;int n;t=(Score)malloc(sizeof(node);N=(Score)malloc(sizeof(node);N-next=L-next; /把N指向链表LL-next=NULL; /L重新指向空s=L; /创建新的链表Lwhile(N-next-next)p=N-next;q=p-next;while(q)n=0;while(p-keyn=q-keyn&n

23、keynq-keyn) /交换数据域，指针域不变for(int i=0;ikeyi=q-keyi;q-keyi=p-keyi;p-keyi=t-keyi;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); /销毁指针Nreturn L;Score RadixSort(Score &L) /对链表L的第n个关键字进行基数排序Score headradix,tailradix,

24、p,t;int d,i,j,m; for(int n=4;n=0;n-) for(d=1;d=2;d+)for(i=0;inext;while(p)if(d=1) m=p-keyn%10; /第一趟取个位分配else m=p-keyn/10; /第二趟分配if(headm=NULL) /采用尾插法建立单链表headm=p; tailm=p;elsetailm-next=p;tailm=p;p=p-next; /取下一个待排序元素L-next=NULL; for(j=radix-1;j=0;j-) /对每一个链队从大到小进行收集if(headj)if(L-next=NULL)L-next=hea

25、dj; /L指向链队头t=tailj; /t指向队尾elset-next=headj; /t-next指向下一个链队头t=tailj; t-next=NULL; /最后一个结点指向空return L; /返回Lvoid PrintScore(Score &L) /在屏幕上显示链表Score p;p=L-next;while(p)for(int i=0;i5;i+) /依次输出5个数据coutsetw(8)keyi;coutnext;coutendl;void Menu() /菜单int a,b,n; Score L;double time;cout#endl 本程序可以按关键字的优先关系排序对

26、成绩排序。endl 随机产生数据 endl#endl;RandData(L,n); /随机产生数据coutendlendl#endl 请选择： endl 1.对数据进行冒泡法排序 endl 2.对数据进行基数排序 endl#b; if(b=1)coutsetw(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;doMenu(); /调用菜单cout结束？输入0，输入其他继续c;while(c!=0) ; /c等于0停止循环八参考文献 1.数据结构（c语言版） 严蔚敏 吴伟民 编著第 25 页 共 26 页