学号--C语言程序设计实训课程设计报告

齐鲁工业大学信息学院《数据结构》课程设计报告题目：图书管理系统专业班级：计科（外包）15-2学号：201503091063姓名：杨朔蓬时间：2016.5.30一、需求分析1.本演示程序中，堆中元素为整数，堆的大小无限制，堆的输入方式与整型数组输入相同，本程序主要是利用堆排序原理进行设计，实现对输入数据的排序和最大元的输出。2.演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运行命令；相应的输入数据和运算结果显示在其后。3.程序执行命令包括：1)新建大根堆2)输出最大元素3)插入元素至大根堆4)输出大根堆数组5)输出大根堆(按行)6)销毁堆二、概要设计1.抽象数据类型定义ADTHeapSort{数据对象:D={ai|ai属于Elemset，i=1,2,3........,n,n=0};数据关系：R1={ai=a2i;ai=a2i+1}；基本操作：Init_Sq(&L)操作结果：新建一个堆InitSq(&L)初始条件：堆已存在操作结果：将输入整数插入到大根堆中HeapAdjust(SqList&L,ints)初始条件：堆已存在操作结果：把s调到堆中合适位置HeapSort(&L)初始条件：堆已存在操作结果：无序数列调整为一个大顶堆DelMax(&L)初始条件：堆已存在操作结果：取出最大元素DeleteHeap(&L)操作结果：销毁堆PutList(L)初始条件：堆已存在操作结果：按行输出堆中元素Load_sq(L)初始条件：堆已存在操作结果：输出堆数组}ADTHeapSort三、详细设计#includestdio.h#includestdlib.htypedefstruct{int*key;intlength;}SqList;voidLoad_sq(SqListL){//打印堆数组inti;if(L.length){printf(堆数组为\n:);for(i=1;i=L.length;i++)printf(%d,L.key[i]);printf(\n);}elseprintf(堆为空!!\n);system(pause);system(cls);}voidPutList(SqListL){//按行打印堆inth=0,sum=0,item=1;inti,j,cnt=1,tmp=1;if(L.length){while(sumL.length){sum+=item;h++;item*=2;}printf(\n------------------------\n);printf(堆中元素：\n);for(i=0;ih;i++){printf(第%d行元素,i+1);for(j=0;jtmp&&cnt=L.length;j++)printf(%d,L.key[cnt++]);printf(\n);tmp*=2;}printf(\n);}elseprintf(堆为空!!\n);system(pause);system(cls);}voidHeapAdjust(SqList*L,ints){//调整堆intj;L-key[0]=L-key[s];for(j=2*s;j=L-length;j*=2){if((jL-length)&&(L-key[j]L-key[j+1]))j++;if(L-key[0]=L-key[j])break;L-key[s]=L-key[j];s=j;}L-key[s]=L-key[0];}voidHeapSort(SqList*L){//建立大顶堆inti;for(i=L-length/2;i0;i--)HeapAdjust(L,i);}intInit_Sq(SqList*L){//新建堆inti;printf(请输入初始堆的长度:);scanf(%d,&L-length);L-key=(int*)malloc((L-length+1)*sizeof(int));if(!L-key)exit(1);printf(请输入初始堆的各个元素\n:);for(i=1;i=L-length;i++)scanf(%d,&L-key[i]);HeapSort(L);printf(新建堆成功!\n);system(pause);system(cls);return1;}voidInitSq(SqList*L){//插入元素inta,i,*newkey;intlen=L-length+1;printf(请输入插入元素个数:);scanf(%d,&a);L-length+=a;newkey=(int*)realloc(L-key,(L-length+1)*sizeof(int));if(!newkey)exit(2);L-key=newkey;printf(请输入初始堆的各个元素\n:);for(i=len;i=L-length;i++)scanf(%d,&L-key[i]);HeapSort(L);printf(插入元素成功!\n);system(pause);system(cls);}voidDelMax(SqList*L){//删除最大元if(L-length){printf(最大元素为:%d\n,L-key[1]);L-key[1]=L-key[L-length];L-length--;HeapAdjust(L,1);}elseprintf(堆为空!!\n);system(pause);system(cls);}intDeleteHeap(SqList*L){if(L-length){free(L-key);L-length=0;L=NULL;printf(销毁完成!\n);system(pause);system(cls);return1;}else{printf(已为空，无需销毁!\n);system(pause);system(cls);return0;}}voidmenu(){printf(*****************************\n);printf(#1、新建大根堆#\n);printf(#2、输出最大元素#\n);printf(#3、插入元素至大根堆#\n);printf(#4、输出大根堆数组#\n);printf(#5、输出大根堆(按行)#\n);printf(#6、销毁堆#\n);printf(#7、退出#\n);printf(*****************************\n);printf(请选择\n:);}voidmenu_2(){printf(**********************************\n);printf(*1、从堆中删除后输出*\n);printf(*2、直接输出*\n);printf(**********************************\n);printf(请选择\n:);}intmain(){inti,j;SqListL;L.length=0;while(1){menu();scanf(%d,&i);switch(i){case1:Init_Sq(&L);break;case2:menu_2();scanf(%d,&j);if(j==1)DelMax(&L);elseif(j==2){if(L.length)printf(最大元素为:%d\n,L.key[1]);elseprintf(堆为空!!\n);system(pause);system(cls);}break;case3:InitSq(&L);break;case4:Load_sq(L);break;case5:PutList(L);break;case6:DeleteHeap(&L);break;case7:return0;default:printf(无此项!!!\n);system(pause);system(cls);}}}函数调用关系：MainMenumenu_2Init_SqInitSqDelMaxLoad_sqPutListDeleteHeapHeapSortHeapAdjustSqList四、调试分析在编程过程中遇到很多问题，比如函数之间参数的传递，刚开始总搞不清楚应该传递什么样的参数，还有在设计堆的筛选中，总是搞不清楚应该怎样筛选，后来经过查阅资料解决了这些问题，程序顺利执行。执行过程中发现了一些bug，比如在堆为空时执行输出程序会崩溃，这些bug已经顺利解决了。五、用户手册1.本程序运行环境为dos操作系统，执行文件为Heap.exe。2.进入演示程序即显示文本方式的用户界面：3.选择相应的选项即可进行操作。六、测试结果执行命令1：执行命令2：执行命令3：执行命令4：执行命令5：执行命令6：执行命令7：退出七、附录源程序文件名Heap.c//主程序八、总结与心得在本次程序设计中，运用了堆排序的基本原理，在编程的过程中，首先要了解大顶堆的定义，以及如何利用堆排序的原理进行排序，合理的设计筛选模块，先从主函数开始，正确使用特殊语句，以及关键字，在这过程要用到for、while、switch循环语句，最重要的就是要写出正确的判断语句，搞清楚程序的结束的点以及函数的递归调用，在大顶堆的筛选的时候，要明白堆排序的实质，就是从最后一个非叶子节点开始，从它的左右子树开始比较，顺着子树较大的方向往父节点平移，最后和序列的最后一个数据进行交换，把它放置在闲置的空间内。在编程的完成之后，要进行仔细的检验，找出错误，进行多次验证，确保此程序准确无误，并且要使程序简单明了，便于操作者使用方便。在进行了此次程序设计之后，明白了如何利用堆排序原理进行对数据的排序，对以前所学的知识进行了巩固，增加了实践的经验。