搜索
数据结构课设报告第1页共26页目录一．设计题目……………………………………2二．需求分析……………………………………21.程序设计问题描述…………………………………22.基本要求…………………………………………23.流程图…………………………………………2三．详细设计………………………………………31.数据结构定义………………………………………42.主要算法设计……………………………………53.函数调用关系图……………………………………84.程序主要流程……………………………………8四．调试分析………………………………………13五．用户手册………………………………………15六．测试结果………………………………………19七．源代码（带注释）………………………………21八．参考文献…………………………………………26数据结构课设报告第2页共26页一．设计题目多关键字排序二．需求分析1.程序设计问题描述多关键字的排序有其一定的实用范围。例如:在进行高考分数处理时，除了需对总分进行排序外，不同的专业对单科分数的要求不同，因此尚需在总分相同的情况下，按用户提出的单科分数的次序要求排出考生录取的次序。2.基本要求(1)假设待排序的记录数不超过10000，表中记录的关键字数不超过5，各个关键字的范围均为0至100。按用户给定的进行排序的关键字的优先关系，输出排序结果。(2)约定按LSD法进行多关键字的排序。在对各个关键字进行排序时采用两种策略:其一是利用稳定的内部排序法，其二是利用分配和收集的方法。并综合比较这两种策略。（3）测试数据由随机数生成器产生。3.流程图开始输出菜单输入记录数选择排序方法判断12内部排序基数排序输入不是1或2，重新输入选择排序方法数据结构课设报告第3页共26页三．详细设计本程序是对语文，数学，英语，体育，综合这5门成绩按照此顺序进行优先排序。各科分数为0～100。由于本实验约定按LSD进行多关键字的排序。在对个关键字进行排序时采用两种策略：其一是利用稳定的内部排序法，其二是利用“分配”和“收集”的方法。所以在一个程序里实现了这两种排序方法。第一种排序方法由于要使用稳定的排序方法，故参考书上的几种排序方法后，选用了冒泡排序和静态链表存储方式，每一趟排序后，找出最高分。第二种排序方法利用“分配”与“收集”的基数排序算法，用静态链表存储分数，在一趟排序中，将结点分配到相应的链显示排序结果输入结束或继续执行判断输入退出结束0非零值继续执行数据结构课设报告第4页共26页队列中去，再按从高到低链接起来。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)初始条件：L为创建的静态链表。操作结果：在屏幕上显示链表。（2）“分配”与“收集”的基数排序结构体定义typedefstructnode//定义结构体{intkey[5];//数据域structnode*next;//指针域}*Score,Lnode;基本操作ScoreRadixSort(Score&L)初始条件：L为创建的静态链表，代表了一条学生成绩的记录。数据结构课设报告第5页共26页操作结果：对链表L的第n个关键字进行基数排序。voidPrintScore(Score&L)初始条件：L为创建的静态链表。操作结果：在屏幕上显示链表。2.主要算法设计（1）稳定的内部排序ScoreBubbleSort(Score&L)//对链表进行冒泡降序排序，返回指针L{Scorep,q,s,t,N;intn;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-key[n]==q-key[n]&&n5)//当前关键字相等则比较下一关键字{n++;}if(p-key[n]q-key[n])//交换数据域，指针域不变{for(inti=0;i5;i++){t-key[i]=q-key[i];数据结构课设报告第6页共26页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);//销毁指针NreturnL;}（2）“分配”和“收集”的基数排序ScoreRadixSort(Score&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;iradix;i++)//初始化各链队首尾指针head[i]=tail[i]=NULL;数据结构课设报告第7页共26页p=L-next;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;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];数据结构课设报告第8页共26页}}t-next=NULL;//最后一个结点指向空}}returnL;//返回L}3.函数调用关系图4.程序主要流程1.随机产生数据：输入想要排序的学生成绩记录数并随机产生成绩：typedefstructnode//定义结构体{intkey[5];//数据域structnode*next;//指针域voidmain()Menu()BubbleSort(L)PrintScore(L)RandData(L,n)RadixSort(L)PrintScore(L)调用If（b=1）调用If（b=2）调用调用数据结构课设报告第9页共26页}*Score,Lnode;ScoreRandData(Score&L,intn)//随机生成n个数据并保存到链表L中，返回链表头指针{Scorep,q;L=(Score)malloc(sizeof(Lnode));//创建带头结点的链表LL-next=NULL;q=L;srand(time(0));cout输入你所需的数据个数：;cinn;coutsetw(8)语文setw(8)数学setw(8)英语setw(8)体育setw(8)综合endl;for(inti=1;i=n;i++){p=(Score)malloc(sizeof(Lnode));for(intj=0;j5;j++){p-key[j]=rand()%101;//对每个关键字随机产生0--100的数字}q-next=p;q=p;}p-next=NULL;//最后一个节点的指针指向空q=L-next;while(q){for(intk=0;k5;k++){coutsetw(8)q-key[k];}coutendl;q=q-next;}returnL;//返回结构体指针}2.菜单显示实现：voidMenu()//菜单{inta,b,n;ScoreL;doubletime;cout##################################################endl本程序可以按关键字的优先关系排序对成绩排序。endl随机产生数据endl数据结构课设报告第10页共26页##################################################endl;RandData(L,n);//随机产生数据coutendlendl#################################################endl请选择：endl1.对数据进行冒泡法排序endl2.对数据进行基数排序endl#################################################endl;do{cinb;if(b==1){coutsetw(8)语文setw(8)数学setw(8)英语setw(8)体育setw(8)综合endl;BubbleSort(L);//调用冒泡排序PrintScore(L);//打印结果}elseif(b==2){RadixSort(L);//调用基数排序PrintScore(L);//}}elsecout选择的操作不存在！！请重新输入（1或者2）endl;}while(b!=1&&b!=2);}3.屏幕上显示链表voidPrintScore(Score&L)//在屏幕上显示链表{Scorep;p=L-next;while(p){for(inti=0;i5;i++)//依次输出5个数据coutsetw(8)p-key[i];coutendl;p=p-next;}coutendl;}4.内部稳定排序算法数据结构课设报告第11页共26页ScoreBubbleSort(Score&L)//对链表进行冒泡降序排序，返回指针L{Scorep,q,s,t,N;intn;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-key[n]==q-key[n]&&n5)//当前关键字相等则比较下一关键字{n++;}if(p-key[n]q-key[n])//交换数据域，指针域不变{for(inti=0;i5;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-nex