学号-姓名-C语言程序设计实训课程设计报告.doc

齐鲁工业大学信息学院 《数据结构》课程设计报告 题目：图书管理系统 专业班级：计科（外包）15-2 学号：201503091063 姓名：杨朔蓬 时间：2016.5.30 需求分析 本演示程序中，堆中元素为整数，堆的大小无限制，堆的输入方式与整型数组输入相同，本程序主要是利用堆排序原理进行设计，实现对输入数据的排序和最大元的输出。 演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运行命令；相应的输入数据和运算结果显示在其后。 程序执行命令包括： 新建大根堆 输出最大元素 插入元素至大根堆 输出大根堆数组 输出大根堆(按行) 销毁堆 概要设计 抽象数据类型定义 ADT HeapSort{ 数据对象: 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,int s) 初始条件：堆已存在 操作结果：把s调到堆中合适位置 HeapSort(L) 初始条件：堆已存在 操作结果：无序数列调整为一个大顶堆 DelMax(L) 初始条件：堆已存在 操作结果：取出最大元素 DeleteHeap(L) 操作结果：销毁堆 PutList(L) 初始条件：堆已存在 操作结果：按行输出堆中元素 Load_sq(L) 初始条件：堆已存在 操作结果：输出堆数组 }ADT HeapSort 详细设计 #include stdio.h #include stdlib.h typedef struct{ int *key; int length; } SqList; void Load_sq(SqList L){ //打印堆数组 int i; if(L.length){ printf(堆数组为\n: ); for(i=1; i=L.length; i++) printf(%d ,L.key[i]); printf(\n); } else printf(堆为空!!\n); system(pause); system(cls); } void PutList(SqList L){// 按行打印堆 int h=0,sum=0,item=1; int i,j,cnt=1,tmp=1; if(L.length){ while(sum L.length){ sum+=item; h++; item*=2; } printf(\n------------------------\n); printf(堆中元素：\n); for(i=0;ih;i++){ printf(第%d行元素 ,i+1); for(j=0;jtmpcnt=L.length;j++) printf(%d ,L.key[cnt++]); printf(\n); tmp*=2; } printf(\n); } else printf(堆为空!!\n); system(pause); system(cls); } void HeapAdjust(SqList *L,int s){ //调整堆 int j; 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]; } void HeapSort(SqList* L){//建立大顶堆 int i; for(i=L-length/2; i0; i--) HeapAdjust(L,i); } int Init_Sq(SqList