[工学]数据结构课程设.ppt

考核方案 1．个人考核和小组考核都为优秀的同学最终成绩评定为优秀； 2. 个人考核和小组考核有一个为优秀，另一个为良好的同学最终成绩评定为良好； 3．个人考核和小组考核都为良好的同学最终成绩评定为良好； 4. 个人考核和小组考核有一个为不及格的同学最终成绩评定为不及格； 5. 个人考核和小组考核的成绩等级情况不在上述四者中的，最终成绩均评定为合格； * 《数据结构课程设计》 课程名称：数据结构课程设计 总学时：30学时，2学分 授课教师：陈一飞 办公室：位育楼519 课程资源： 49 用户名 cyfstu 课程设计任务安排 第一周，完成个人任务，并出具个人任务的课程设计报告； 第二周，完成小组任务； 第三周，测试系统，完成小组课程设计报告，准备.ppt文件和最后的答辩。 课程内容 一、个人任务：每位同学必须完成 (1) 直接插入排序 (2) 折半插入排序 (3) 冒泡排序 (4) 简单选择排序 (5) 快速排序 (6) 堆排序 (7) 归并排序 个人任务的内容和要求 [问题描述]：用程序实现多种排序算法 [基本要求]：利用随机函数产生随机整数(20000)，对这些数据进行多种方法进行排序。要求： 采用以上各种方法实现问题求解，并把排序后的结果保存在不同的文件中。 统计每种排序方法的性能(以上机运行所花费的时间为准进行对比)。 并完成这些算法的性能分析（从时间复杂度和空间复杂度两个方面进行比较分析）报告。 #include stdio.h#include stdlib.h#include time.h int main(){ clock_t begin, end; double? cost; begin = clock(); /* 程序代码 */ end = clock(); cost = (double)(end - begin) /CLOCKS_PER_SEC; printf(%lf seconds\n, cost); return 0;} 排序方法 插入排序 选择排序 交换排序 归并排序 直接插入排序 折半插入排序 简单选择排序 堆排序 冒泡排序 快速排序 希尔插入排序 锦标赛排序 ★ 基数排序 1、直接插入排序 排序过程：整个排序过程为n-1趟插入，即先将序列中第1个记录看成是一个有序子序列，然后从第2个记录开始，逐个进行插入，直至整个序列有序。 例 49 38 65 97 76 13 27 i=2 38 (38 49) 65 97 76 13 27 i=3 65 (38 49 65) 97 76 13 27 i=4 97 (38 49 65 97) 76 13 27 i=5 76 (38 49 65 76 97) 13 27 i=6 13 (13 38 49 65 76 97) 27 i=1 ( ) i=7 (13 38 49 65 76 97) 27 27 j j j j j j 97 76 65 49 38 27 (13 27 38 49 65 76 97) 排序结果： 0 1 2 3 4 5 6 7 折半插入排序 排序过程：用折半查找方法确定插入位置的排序叫~ 例 i=1 (30) 13 70 85 39 42 6 20 i=2 13 (13 30) 70 85 39 42 6 20 i=7 6 (6 13 30 39 42 70 85 ) 20 …... i=8 20 (6 13 30 39 42 70 85 ) 20 low high mid i=8 20