《数据结构多关键字排序课设报告》由会员分享，可在线阅读，更多相关《数据结构多关键字排序课设报告（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)假设待排序的记录数不超过1000
2、0，表中记录的关键字数不超过5，各个关键字的范围均为0至100。按用户给定的进行排序的关键字的优先关系，输出排序结果。 (2)约定按LSD法进行多关键字的排序。在对各个关键字进行排序时采用两种策略:其一是利用稳定的内部排序法，其二是利用分配和收集的方法。并综合比较这两种策略。 （3）测试数据由随机数生成器产生。开始 3.流程图 输出菜单 输入记录数选择排序方法输入不是1或2，重新输入选择排序方法判断2 1基数排序内部排序显示排序结果输入结束或继续执行判断输入非零值0继续执行退出结束三详细设计 本程序是对语文，数学，英语，体育，综合这5门成绩按照此顺序进行优先排序。各科分数为0100。 由于本实
3、验约定按LSD进行多关键字的排序。在对个关键字进行排序时采用两种策略：其一是利用稳定的内部排序法，其二是利用“分配”和“收集”的方法。所以在一个程序里实现了这两种排序方法。 第一种排序方法由于要使用稳定的排序方法，故参考书上的几种排序方法后，选用了冒泡排序和静态链表存储方式，每一趟排序后，找出最高分 。第二种排序方法利用“分配”与“收集”的基数排序算法，用静态链表存储分数，在一趟排序中，将结点分配到相应的链队列中去，再按从高到低链接起来。 1.数据结构设计（1）稳定的内部排序法结构体定义typedef struct node /定义结构体 int key5; /数据域struct node *
4、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 k
5、ey5; /数据域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(node);N=(S
6、core)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=NULL; /
7、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; /第二趟分配if(h
8、eadm=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() 调用Rad
9、ixSort(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(sizeof(Lnode
10、); /创建带头结点的链表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)keyk;coutnext;return L; /返回结构体指针2. 菜单显示实现： void Menu() /菜单int a,b,n; Score L;double time;cout#
