数据结构上机基本习题课件.ppt

基本要求 1．用随机函数产生1000个（或更多）整数（或浮点数），保存在文件（intfile.dat / realfile.dat）中，然后将文件中的所有整数（或浮点数）读入一个数组A。 （1）用冒泡法对数组A排序； （2）用简单选择排序方法对数组A排序； （3）用直接插入排序法对数组A排序； 将上述排序算法分别用函数实现，输出每种排序过程中元素的比较次数、交换（或移动）次数，以及排序过程所消耗的时间（以s或ms为单位）； 基本要求 2．将问题1中所有1000个（或更多）整数读入数组A，用快速排序算法对数组A中的元素排序，输出排序结果、排序过程中元素的比较和交换（移动）次数、排序算法消耗的时间; 3. 利用上面实现的任意一种排序算法，对实验题目一所产生的学生信息文件studinfo.dat，读取其中的所有学生信息： （1）按学号排序输出学生信息； （2）按姓名排序输出学生信息； （3）按三门课程的平均分从高到低排序输出学生信息（除了学生基本信息外，还要输出每个学生的平均成绩），最后再加一行输出信息：每门课程的平均成绩。 选作内容 用随机函数产生至少10000个整数，保存在文件（intfile.dat）中 （1）通过建立大顶（根）堆实现堆排序，最后输出排序结果； （2）通过建立小顶（根）堆实现堆排序，每找出一个小元素就输出它，从小到大输出排序结果。 选作内容 用随机函数产生至少10000个整数，保存在文件（intfile.dat）中，对其中的数据进行归并排序，最后将排序结果写入文件； 产生两个已经排序的整数数据文件，将两个文件的数据归并成一个有序序列存入文件保存。 随机数 随机函数rand() #include stdlib.h RAND_MAX在stdlib.h中定义，不大于双字节整数的最大值32767 产生[0,RAND_MAX] 之间的随机数 magic = rand(); 产生[0,b-1] 之间的随机数 magic = rand()%b; 产生[a,a+b-1] 之间的随机数 magic = rand()%b + a; 随机数 随机函数srand 为函数rand()设置随机数种子来实现对函数rand所产生的伪随机数的 “随机化” 通过键入随机数种子，产生[0,100]之间的随机数 scanf(%u, seed); srand(seed); magic = rand() % 100 + 1; 使用计算机读取其时钟值并把该值自动设置为随机数种子，产生[0,100]之间的随机数 函数time()返回以秒计算的当前时间值，该值被转换为无符号整数并用作随机数发生器的种子 #include time.h srand((unsigned)time(NULL)); magic = rand() % 100 + 1; 计算代码段运行时间示例 建初始小顶堆 47 36 91 12 53 30 24 85 12 36 85 47 24 30 53 91 元素序列为：47,36,53,91,12,30,24,85 建立小顶堆 建初始堆 47 36 91 12 53 30 24 85 (a) 47 36 85 12 53 30 24 91 (b) 从最后一个具有叶子的结点(编号[n/2])开始建子堆，依次考查结点[n/2]-1,[n/2]-2,...，1等是否为堆，若否则调整为堆 return 建初始堆 47 36 85 12 24 30 53 91 从最后一个具有叶子的结点(编号[n/2])开始建子堆，依次考查结点[n/2]-1,[n/2]-2,...，1等是否为堆，若否则调整为堆 (C) 47 12 85 36 24 30 53 91 (d) 建初始堆 12 47 85 36 24 30 53 91 从最后一个具有叶子的结点(编号[n/2])开始建子堆，依次考查结点[n/2]-1,[n/2]-2,...，1等是否为堆，若否则调整为堆 (e) 12 36 85 47 24 30 53 91 (f) 当以下标1为根的完全二叉树为堆时，初始堆已建立 堆排序算法(续) typedef SqList HeapType; //堆采用顺序存储结构 void HeapSort ( HeapType H) { //对顺序表H进行堆排序 for ( i = H. length/2; i 0; --i) // 把H建成大顶堆 HeapAdjust ( H, i, H. length); for ( i = H. length; i 1; --i) { H.r[1] ←→H.r[