数据结构课设报告第 0 页 共 26 页目录1 设计题目 2 2需求分析 2 1.程序设计问题描述22.基本要求 2 3.流程图 23详细设计 3 1.数据结构定义42.主要算法设计 53.函数调用关系图84.程序主要流程 84调试分析 135用户手册 156测试结果 197源代码（带注释 ）21八参考文献26数据结构课设报告第 1 页 共 26 页一设计题目 多关键字排序二需求分析1.程序设计问题描述 多关键字的排序有其一定的实用范围。例如:在进行高考分数处理时，除了需对总分进行排序外，不同的专业对单科分数的要求不同，因此尚需在总分相同的情况下，按用户提出的单科分数的次序要求排出考生录取的次序。 2.基本要求(1)假设待排序的记录数不超过 10000，表中记录的关键字数不超过 5，各个关键字的范围均为 0 至 100。按用户给定的进行排序的关键字的优先关系，输出排序结果。(2)约定按 LSD 法进行多关键字的排序。在对各个关键字进行排序时采用两种策略:其一是利用稳定的内部排序法，其二是利用分配和收集的方法。并综合比较这两种策略。（3）测试数据由随机数生成器产生。3.流程图开始输出菜单输入记录数选择排序方法判断1 2内部排序 基数排序输入不是 1 或 2，重新输入选择排序方法数据结构课设报告第 2 页 共 26 页三详细设计本程序是对语文，数学，英语，体育，综合这 5 门成绩按照此顺序进行优先排序。各科分数为 0100。由于本实验约定按 LSD 进行多关键字的排序。在对个关键字进行排序时采用两种策略：其一是利用稳定的内部排序法，其二是利用“分配”和“收集”的方法。所以在一个程序里实现了这两种排序方法。第一种排序方法由于要使用稳定的排序方法，故参考书上的几种排序方法后，选用了冒泡排序和静态链表存储方式，每一趟排序后，找出最高分 。第二种排序方法利用“分配”显示排序结果输入结束或继续执行判断输入退出结束0非零值继续执行数据结构课设报告第 3 页 共 26 页与“收集”的基数排序算法，用静态链表存储分数，在一趟排序中，将结点分配到相应的链队列中去，再按从高到低链接起来。1.数据结构设计（1）稳定的内部排序法结构体定义typedef struct node /定义结构体 int key5; /数据域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 key5; /数据域struct node *next; /指针域*Score,Lnode;基本操作数据结构课设报告第 4 页 共 26 页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=(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=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;dnext;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=headj; /L 指向链队头t=tailj; /t 指向队尾else数据结构课设报告第 7 页 共 26 页t-next=headj; /t-next 指向下一个链队头t=tailj; t-next=NULL; /最后一个结点指向空return L; /返回 L3.函数调用关系图4.程序主要流程1.随机产生数据：输入想要排序的学生成绩记录数并随机产生成绩：typedef struct node /定义结构体 void main() Menu()BubbleSort(L)PrintScore(L)RandData(L,n) RadixSort(L) PrintScore(L)调用If（b=1）调用 If（b=2）调用调用数据结构课设报告第 8 页 共 26 页int key5; /数据域struct node *next; /指针域*Score,Lnode;Score RandData(Score &L,int n) /随机生成 n 个数据并保存到链表 L 中，返回链表头指针Score p,q;L=(Score)malloc(sizeof(Lnode); /创建带头结点的链表 LL-next=NULL;q=L; srand(time(0); coutn;coutkeyj=rand()%101; /对每个关键字随机产生 0-100 的数字q-next=p;q=p;p-next=NULL; /最后一个节点的指针指向空 q=L-next; while(q) for(int k=0;kkeyk;coutnext;return L; /返回结构体指针2.菜单显示实现：void Menu() /菜单int a,b,n; Score L;数据结构课设报告第 9 页 共 26 页double time;coutb;if(b=1)coutnext;while(p)for(int i=0;ikeyi;coutnext;数据结构课设报告第 10 页 共 26 页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-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; /p 指向最后一个结点p=p-next;q=q-next;s-next=N-next; /将第一个结点插到 L 的尾部delete(N); /销毁指针 N数据结构课设报告第 11 页 共 26 页return L;5.“分配”与“收集”的基数排序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;dnext;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-ne