VC课程设计报告 (shell排序+分块查找).doc

编号：12河北工业大学计算机软件技术基础（VC）课程设计报告学院 管理学院 班级 经济学类102姓名 学号 成绩 _ _一、题目：数据查询问题二（shell排序+分块查找）（编号12）二、设计思路1、总体设计1）分析程序的功能输入若干同学的若干科成绩（无序），求出每人总成绩。用希尔排序法使总成绩有序。然后输入想寻找的总成绩，用分块查找的方法查找该总成绩，若找到则输出该成绩，否则输出未找到信息。2）系统总体结构：设计程序的组成模块，简述各模块功能主函数：完成程序主体运行。输入求和函数：输入要处理的数据，完成对每人总成绩的求和。排序函数：用希尔排序法使以总成绩为关键字的输入数据有序。查找函数：用分块查找法在有序数据中查找某个数据。2、各功能模块的设计：说明各功能模块的实现方法主函数：通过调用已声明的各个函数完成对数据的求和、排序、查找。输入求和函数：用循环输入数据，用定义的结构体储存输入的数据以及求得的和（用独立函数完成）。排序函数：再次利用定义的结构体，以结构体中的和为关键字，用希尔排序法使数据有序（用独立函数完成）。查找函数：把有序数据分成若干份，确定要查找的数据所在的大体范围，然后用折半查找法具体确定数据的位置；若没有找到则判断要查找的数据不在该有序数据中（用独立函数完成）。3、设计中的主要困难及解决方案在这部分论述设计中遇到的主要困难及解决方案1）困难1将无序数据转换成有序数据。解决方案：定义一个结构体，并利用近似黄金数列确定两个元素最大距离（可以提高排序效率）以及循环嵌套的方法完成希尔排序法。2）困难2从有序数据中查找某个数据。解决方案：继续使用定义的结构体，用数据总数开方得数为分组长度（可以提高查找效率）以及循环（可以避免最后一个分组数据的单独处理）的方式完成分块查找。3）困难3折半查找的使用。解决方案:取有序数据的最大值、最小值和中间值，判断要查找的数据在其大概位置，即前半部分或后半部分（用函数完成），确定后改变最大值、最小值和中间值，再次返回该函数，直到确定该数据在或者不在其中。4、你所设计的程序最终完成的功能1）说明你编制的程序能完成的功能求出输入无序数据的和，排列各个和使其有序，并确定某数是否是其和中一个，如果是则输出该数和其对应位置，否则输出未找到数据。2）准备的测试数据及运行结果准备的测试数据人数：3编号为1的同学：第一科成绩:89 第二科成绩:78 第三科成绩:79编号为2的同学：第一科成绩:88 第二科成绩:67 第三科成绩:69编号为3的同学：第一科成绩:93 第二科成绩:78 第三科成绩:84要找的总成绩：246运行结果三、程序清单#include#include#includeusing namespace std;struct subject int mark3; int sum;void create(subject *,int);void sort(subject *,int);int search(subject *,int,int);int binarySearch(subject *,int,int,int);int min(int,int);void main() int size,key,result; coutsize; subject *grade=new subjectsize; create(grade,size); sort(grade,size);coutThe sorted sums are: endl;for(int k=0;ksize;k+)coutThis is k+1th studentn;coutgradek.sumendl; coutkey; result=search(grade,size,key); if(result=-1) coutNot foundn; else coutfound sum of key at listresult+1n; system(pause);void create(subject *list,int size) int mark,sum; for(int i=0;isize;i+) sum=0; coutThis is i+1 studentn; for(int j=0;j3;j+) coutPlease insert the j+1mark; (list+i)-markj=mark; sum+=mark; (list+i)-sum=sum; void sort(subject *list,int size) int i, j; int gap = 0; subject back; subject *temp=&back; while (gap 0) for ( i = gap; i = 0 ) & (listj.sumtemp-sum) listj + gap = listj; j = j - gap; listj + gap = *temp; gap = ( gap - 1 ) /3; int search(subject *list,int size,int key) int t=0; int b=(int)sqrt(size); while (listmin(b,size)-1.sum=size) return -1 ; if(keylistsize-1.sum) return -1; return binarySearch(list,key,t,min(size,b)-1);int binarySearch(subject *list,int value,int low,int high) int mid; if(highvalue) return binarySearch(list,value,low,mid-1); else if(listmid.sumvalue) return binarySearch(list,value,mid+1,high); else return mid;int min(int a,int b) return ab?a:b;四、对该设计题目有何更完善的方案1、对自己完成程序进行自我评价我较好的完成了题目要求，考虑到排序效率、查找效率等问题，并避免了分块查找中最后一组数据的单独处理。创新部分有，使用结构描述数据，多次使用单独函数，并且在输出已找到数据的基础上，输出了数据在已排序数据中的位置。2、对课题提出更完善的方案鉴于处理数据不多，在分块查找中可以用顺序查找法处理数据，使代码更简洁。五、收获及心得体会1、通过本次课程设计，自己在哪些方面的能力有所提高。通过本次设计我更加了解了函数的声明、定义及调用，了解了结构体的使用，接触