• 竞技宝
  • 自查报告
  • 情况报告
  • 事迹材料
  • 申报材料
  • 社会实践报告
  • 实习报告
  • 述职报告
  • 述廉报告
  • 调研报告
  • 调查报告
  • 考察报告
  • 实验报告
  • 整改措施
  • 整改报告
  • 开题报告
  • 辞职报告
  • 申请报告
  • 可行性报告
  • 报告写作指导
  • 社会调查报告
  • 离职报告
  • 结题报告
  • 竞聘报告
  • 学习报告
  • 请示报告
  • 寒假实践报告
  • 实习周记
  • 暑期实践报告
  • 研究报告
  • 实习日记
  • 实验报告 当前位置:池锝网 > 竞技宝 > 竞技宝 > 实验报告 > 正文 池锝网手机站

    鸿运手机版首页

    【实验报告】 池锝网 2018-06-16本文已影响

    篇一:数据结构实验报告排序

    滁 州 学 院 课 程 设 计 报 告 课程名称: 数据结构 设计题目 : 排序算法实现及比较 系 别: 计算机信息工程学院 专 业: 计算机科学与技术 组 别: 第*组 起止日期: 12 年 5 月 1 日 ~ 12 年 6 月 1 日 指导教师: *** 计算机与信息工程学院二○一二年制 课程设计任务书 课程设计题目 排序算法实现将比较 组长 *** 学号 20****** 班级 *** 系别 计算机与信息工程学院 专业 计算机科学与技术 组员 *** 指导教师 *** 课程设计目的 ⑴加深对常见排序算法理解 ⑵通过程序比较常见算法优越性 ⑶熟悉加深对数据结构的了解及认识 课程设计所需环境 Windows xp; VC++6.0 课程设计任务要求 ⑴实现常见排序算法程序化 ⑵测试程序比较算法优越性 ⑶了解常见算法的实际应用 课程设计工作进度计划 序号 起止日期 工 作 内 容 分工情况 1 分析实验类容 2 分工 3 算法改编成程序 4 将子程序合并及调试 数据测试及记录 5 编写报告 指导教师签字: 年 月 日 系(教研室) 审核意见: 系(教研室) 主任签字: 年 月 日 目 录 1.引言 .............................................................................................................................................................. 4 2.需求分析 ...................................................................................................................................................... 4 3.详细设计 ...................................................................................................................................................... 4 3.1 直接插入排序 .................................................................................................................................. 4 3.2 折半排序 ........................................................................................................................................... 5 3.3 希尔排序 .......................................................................................................................................... 6 3.4 简单选择排序 ................................................................................................................................... 6 3.5 堆排序 ............................................................................................................................................... 6 3.6 归并排序 ........................................................................................................................................... 7 3.7 冒泡排序 ........................................................................................................................................... 9 4.调试 ............................................................................................................................................................ 10 5.调试及检验 ................................................................................................................................................ 11 5.1 直接插入排序 ................................................................................................................................ 11 5.2 折半插入排序 ................................................................................................................................. 11 5.3 希尔排序 ........................................................................................................................................ 12 5.4 简单选择排序 ................................................................................................................................. 12 5.5 堆排序 ............................................................................................................................................. 13 5.6 归并排序 ......................................................................................................................................... 14 5.7 冒泡排序 ......................................................................................................................................... 14 6.测试与比较 ................................................................................................................................................ 15 6.1 调试步骤 ......................................................................................................................................... 15 6.2 结论 ................................................................................................................................................. 16 7.实验心得与分析 ........................................................................................................................................ 16 8.附录 ............................................................................................................................................................ 17 8.1 直接插入排序 ................................................................................................................................. 17 8.2 折半插入排序 ................................................................................................................................. 18 8.3 希尔排序 ......................................................................................................................................... 20 8.4 简单选择排序 ................................................................................................................................. 22 8.5 堆排序 ............................................................................................................................................. 23 8.6 归并排序 ......................................................................................................................................... 26 8.7 冒泡排序 ......................................................................................................................................... 29 8.8 主程序 ............................................................................................................................................. 30 1.引言 伴随着社会的发展, 数据也变得越来越庞大。

    如何将庞大的数据进行很好的排序, 使用户更加方便的查找资料, 成了一件越来越重要的问题。

    对于程序员来说, 这将是一个挑战

    经常查找资料的朋友都会知道, 面对海量的资料, 如果其查找的资料没有进行排序, 那么其查找资料将会是一件非常痛苦的事情。

    针对这一问题, 我们自此通过一个课程设计来解决它。

    理论上排序算法有很多种, 不过本课程设计只涉及到七种算法。

    这七种算法共包括: 直接插入排序, 折半插入排序, 希尔排序, 简单选择排序, 堆排序, 归并排序, 冒泡排序。

    本课程设计通过对这七种算法的运行情况进行对比, 选择最优秀的算法来提供给用户。

    希望通过我们的努力能给用户解决一些问题, 带来一些方便。

    2.需求分析 本课程题目是排序算法的实现, 由于各方面的原因, 本课程设计一共要设计七种排序算法。

    这七种算法共包括: 直接插入排序, 折半插入排序, 希尔排序, 简单选择排序, 堆排序, 归并排序, 冒泡排序。

    七种排序各有独到之处, 因此我们要通过各种调试分析来比较其优劣长短。

    为了小组分工的方便, 我们特意把子函数写成 Header File 文件。

    这样操作不仅可以使小组分工更加简洁明了, 还可以方便子函数的调用, 更可以使写主函数时一目了然。

    为了运行时的方便, 我们将七种排序方法进行编号, 其中 1 为直接插入排序, 2 为折半插入排序,3 为希尔排序, 4 为简单选择排序, 5 为堆排序, 6 为归并排序, 7 为冒泡排序。

    通过这七种选项,可以让用户简单明了的去选择使用哪一种排序方法。

    本课程就是通过对 5 组占用内存大小不同的数据调试来测试这七种算法运行的时间长短, 从中选择面对不同大小的文件时, 哪一种算法更为快捷。

    软件环境本课程设计所用操作系统为 Windows-XP操作系统, 所使用的软件为 Microsoft Visual C++ 6.0; 3.详细设计 3.1 直接插入排序 ⑴算法思想: 直接插入排序是一种最简单的排序方法, 它的基本操作是将一个记录插入到一个已排好序的有序表中, 从而得到一个新的、 记录数增一的有序表。

    在自 i-1 起往前搜索的过程中, 可以同时后移记录。

    整个排序过程为进行 n-1 趟插入, 即: 先将序列中的第一个记录看成是一个有序的子序列, 然后从第二个记录起逐个进行插入, 直至整个序列变成按关键字非递减有序序列为止。

    ⑵程序实现及核心代码的注释: for (i = 1 ; i r.length ;++i ) for(j=0;j ++j) if(r.base[i] r.base[j]) { temp = r.base[i]; //保存待插入记录 for(i= i ;i --i ) r.base[i] = r.base[i-1]; //记录后移 r.base[j] = temp; //插入到正确的为位置 } r.base[r.length] ="\0"; 3.2 折半排序 ⑴算法思想: 由于折半插入排序的基本操作是在一个有序表中进行查找和插入, 这个 查找 操作可利用折半查找来实现, 由此进行的插入排序称之为折半插入排序。

    折半插入排序所需附加存储空间和直接插入排序相同, 从时间上比较, 这般插入排序仅减少了关键字间的比较次数, 而记录的移动次数 不变。

    因此, 这般插入排序的时间复杂度仍为 O(n2)。

    ⑵程序实现及核心代码的注释: void zb(FILE *fp) { //对顺序表作折半插入排序 for ( i = 1 ; i r.length ; i++ ) { temp=r.base[i]; //将 r.base[i]寄存在 temp 中 low=0; high=i-1; while( low = high ) //在 base[low]到 key[high]中折 半查找有序插入的位置 { m = (low+high)/2; //折半 if ( temp r.base[m] ) high = m-1; //插入低半区 else low = m+1; //插入高半区 } for( j=i-1; j =high+1; --j ) r.base[j+1]= r.base[j]; //记录后移 r.base[high+1]=temp; //插入 } 3.3 希尔排序 ⑴算法思想: 先将整个待排记录序列分割成为若干子序列分别进行直接插入排序, 待整个序列中的记录 基本有序 时, 再对全体记录进行一次直接插入排序。

    其中, 子序列的构成不是简单的 逐段分割 , 而是将分隔某个 增量 的记录组成一个子序列。

    ⑵程序实现及核心代码的注释: for(k = 0; k 10 ; k++) { m = 10 - k; for( i = m ; i r.length; i ++ ) if(r.base[i] r.base[i - m]) { temp = r.base[i]; //保存待插记录 for(j = i - m ; j = 0 temp r.base[j]; j -= m) r.base[ j + m ] = r.base[j]; //记录后移, 查找插入位置 r.base[ j + m ] = temp; //插入 } } 3.4 简单选择排序 ⑴算法思想: 在要排序的一组数中, 选出最小的一个数与第一个位置的数交换; 然后在剩下的数当中再找最小的与第二个位置的数交换, 如此循环到倒数第二个数和最后一个数比较为止。

    ⑵程序实现及核心代码的注释: for ( i = 0 ; i r.length ; i++ ) { //i 为排好序的数的下标, 依次往后存放排 //好序的数 temp=r.base[i]; //将待放入排好序的数的下标的数保存 for( j = i,m = j +1 ; m r.length ; m++) //找出未排序的数中最小的数的循环; if(r.base[j] r.base[m]) j = m; r.base[i] = r.base[j]; //把下标为 j 的数与 i 数互换; r.base[j] = temp; } 3.5 堆排序 ⑴算法思想: 堆排序只需要一个记录大小的辅助空间, 每个待排序的记录仅占有一个存储空间。

    将序列所存储的元素A[N]看做是一棵完全二叉树的存储结构, 则堆实质上是满足如下性质的完全二叉树: 树中任一非叶结点的元素均不大于(或不小于)其左右孩子(若存在)结点的元素。

    算法的平均时间复杂度为O(N log N)。

    ⑵程序实现及核心代码的注释: void dp(FILE *fp) { for(i = r.length / 2;i = 1 ; --i) //把 r.base[1...r.length]建成大顶堆 HeapAdjust(r.base,i,r.length); for(i = r.length ;i = 2 ; --i) { temp = r.base[1]; r.base[1] = r.base[i]; r.base[i] = temp; HeapAdjust(r.base,1,i-1); //将 r.base[1...i-1]重新调整为大顶堆 } void HeapAdjust(char *r,int k,int m) { i=k; x=r[i]; j=2*i; //沿 key 较大的孩子节点向下筛选 while(j =m) //j 为 key 较大的记录的下标 { if( (j m) (r[j] r[j+1]) ) j++; if(x r[j]) { //插入字符比当前的大, 交换 r[i] =r[j]; i = j; j *= 2; } else //否则比较停止。

    j = m + 1; } r[i] = x; //把字符 x 插入到该位置, 元素插入实现 } 3.6 归并排序 ⑴算法思想: 先将相邻的个数为 1 的每两组数据进行排序合并; 然后对上次归并所得到的大小为 2的组进行相邻归并; 如此反复, 直到最后并成一组, 即排好序的一组数据。

    ⑵程序实现及核心代码的注释: void merge(SqList6 r,int h ,int m ,int w ,SqList6 t) { //对相邻两组数据进行组合排序; int i,j,k; i = h ; j = m + 1; //j 为合并的第二组元素的第一个数位置 k =h-1; // k 为存入 t 中的数的位置; while((i = m) (j = w)) { //依次排列两组数据 k++; if(r.base[i] = r.base[j]) //将第一组数据与第二组数据分别比较; t.base[k] = r.base[i++]; else t.base[k] = r.base[j++]; } if(i m) //第一组数据先排完的情况 while(j = w) t.base[++k]=r.base[j++]; else while(i = m) t.base[++k]=r.base[i++]; } void tgb(int s,int n,SqList6 r,SqList6 t) { //对数据进行每组 s 个数的归并排序; int i=1; //i 为要合并两组元素的第一个数位置; while(i =(n-2*s+1)) { merge(r,i,i+s-1,i+2*s-1,t); //i+s-1 为要合并的第一组元素的最后一 //数位置、 i+2*s-1 为要合并的两组元素 //最后一个数位置; i=i+2*s; } if(i (n-s+1)) //考虑 n 不能被 s 整除, 如果余下的数少于 //2*s 但大于 s, 也就是余下的数不能凑成 //两组, 凑一组有余,则把余下的数进行组 //合, 并对其进行排序; merge(r,i,i+s-1,n,t); else //如果余下的数少于s, 则余下的数进行组//合,并进行排序; while(i =n) t.base[i]=r.base[i++]; } void gb(FILE *fp) // 归并主函数; { n = r.length; SqList6 t; t.base=(char *) malloc(r.stacksize*sizeof(char)); //给待排序的数组 t 申请内存; while(s n) //每组元素不断增加循环进行合并排序; { tgb(s,n,r,t); // s 为每组元素的个数、 n 为元素总个数、 r //为原数组, t 为待排序的数组, 进行归并排 s*=2; //序; 把元素个数相同的两组合并 并进行重新 //定义成新的一组, 此组元素个数为 2*s; if(s n){ tgb(s,n,t,r); s *= 2; } //当元素个数小于 n 时, 对其进行合并排序; else //当元素个数大于 n 时, 对剩下的数排序; { i=0; while(i =n) { r.base[i]=t.base[i+1]; i++; } } } } 3.7 冒泡排序 ⑴算法思想: 1、 先将一组未排序的数组的最后一个数与倒数第二个数进行比较, 并将较小的数放于两个数中较前的位置, 然后将比较后的较小的数与倒数第三个进行比较, 依次比较到第一个数, 即可得到第一个数是所有数中最小的数; 2、 然后再将数组的最后一个数与倒数第二个数进行比较, 并将较小的数放于两个数中较前的位置, 依次比较到第二个数, 3、 如此循环到只剩最后两个比较, 即得到排好序的一组数。

    ⑵程序实现及核心代码的注释: for( i=0; i r.length ;i++ ) // i 为排好序的数的下标, 依次往后存放排好序的数; { for( j = r.length-2;j j -- ) //从后往前依次两两比较, 较小的被调换到前面 ; if(r.base[j+1] r.base[j]) //比较相邻两个数, 如果后面的小于前面的, 向下执行; { temp = r.base[j+1]; //将后面的较小的数保存起来; r.base[j+1] = r.base[j]; //将前面的较大的数放在后面较小的数的位置; r.base[j] = temp; //将较小的数放在前面的较大的数的位置; } } 4.调试 检测主函数是否能够稳定运行(如图 4-1): 图 4-1 5.调试及检验 5.1 直接插入排序 输入字符并保存(如图 5-1.1): 调用算法【1】 处理文件(如图 5-1.2): 处理结果(如图 5-1.3): 图 5-1 . 1 图 5-1 . 2 图 5-1 . 3 5.2 折半插入排序 输入字符并保存(如图 5-2.1): 调用算法【2】 处理文件(如图 5-2.2): 处理结果(如图 5-2.3): 图 5-2. 1 图 5-2. 2图 5-2. 3 5.3 希尔排序 输入字符并保存(如图 5-3.1): 调用算法【3】 处理文件(如图 5-3.2): 处理结果(如图 5-3.3): 图 5-3. 1 图 5-3. 2 图 5-3. 3 5.4 简单选择排序 输入字符并保存(如图 5-4.1): 调用算法【4】 处理文件(如图 5-4.2): 处理结果(如图 5-4.3): 图 5-4. 1 图 5-4. 2 图 5-4. 3 5.5 堆排序 输入字符并保存(如图 5-5.1): 调用算法【5】 处理文件(如图 5-5.2): 处理结果(如图 5-5.3): 图 5-5. 1 图 5-5. 2 图 5-5. 3 5.6 归并排序 输入字符并保存(如图 5-6.1): 调用算法【6】 处理文件(如图 5-6.2): 处理结果(如图 5-6.3): 图 5-6. 1 图 5-6. 2 图 5-6. 3 5.7 冒泡排序 输入字符并保存(如图 5-7.1): 调用算法【7】 处理文件(如图 5-7.2): 处理结果(如图 5-7.3): 图 5-7. 1 图 5-7. 2 图 5-7. 3 6.测试与比较 6.1 调试步骤 ⑴在 kcsj 文本文件中随机输入一串字符串, 然后保存下来并且复制备份在桌面上。

    运行程序, 调用不算法去处理文件。

    用秒表计算从开始到结束所用的时间, 并记录下来。

    ⑵将文件夹中的 kcsj 文本文件删除, 将桌面上的备份文件考入文件夹来代替原文件, 以保障被操作数据的一致性。

    ⑶用同样的方法依次测试七种算法所用的时间, 并记录下来。

    ⑷再将数据依次改变为占用内存大小为 50KB 、 100KB、 200KB、 512KB、 1024KB 的数字串, 重复以上的操作。

    ⑸将记录的数据(如表 6-1)。

    表 6-1 同一文件不同算法处理的时间表 直接插入排序 折半插入排序 希尔排序 简单选择排序 堆排序 归并排序 冒泡排序 50KB 1m 1.5s 0.2s 6.0s 0.1s 0.1s 6.1s 100KB 3m 5.5s 1.1s 23s 0.1s 0.1s 24s 200KB -- 20s 3.8s -- 0.1s 0.1s 1m 512KB -- 1m 14s -- 0.1s 0.1s 3m 1024KB -- 3m 1m -- 0.2s 0.3s 10m --: 表示时间过长 6.2 结论 通过实验结果的比较与分析我们发现: 直接插入排序、 冒泡排序、 简单选择排序及折半插入排序是低效率的排序方式; 所以我们实际编程重要尽可能的避免他们的出现; 我们应该用较先进的归并排序及堆排序。

    7.实验心得与分析 通过本次课程设计, 我们小组的每个成员都学到了很多东西。

    首先要说的是我们的编程能力, 在这一次的课程设计中我们的编程能力均得到了一定程度的提升。

    并且通过这次课程设计, 我们更加熟悉了如何使用 Header File 文件。

    本次课程设计, 让我们对于直接插入排序, 折半插入排序, 希尔排序, 简单选择排序, 堆排序, 归并排序, 冒泡排序等七种排序算法的思想有了进一步的认识, 同时对七种算法的应用有了更进一步的掌握。

    通过这次课程设计, 我们对于解决实际问题的能力有了进一步提高。

    最重要的是, 这次课程设计大大的训练了我们的小组团队协作能力。

    通过这次课程设计我们小组各成员的团队协作能力都有了很大的提升。

    这种团队协作能力对于我们学编程的来说是极其重要的, 同时也是必不可少的。

    当然, 我们写程序的时候遇到了很多困难。

    而且在程序调试过程中出现了很多错误与警告, 不过在队员及老师的帮助下均得到了解决。

    当程序可以运行后, 程序的运行过程中同样也也出现了很多错误, 甚至出现了不兼容的情况。

    不过, 后来在队员及老师的帮助下也均得到了解决。

    然而, 我们的程序还有一点瑕疵让我们感到美中不足。

    那就是在归并算法运行过程中, 当输入为 9 个字符时,排序结果会出现偶然误差。

    经过分析, 我们认为这点是系统的问题。

    不过, 这仍然是一点让我们感到遗憾的地方。

    8.附录 8.1 直接插入排序 #include stdio.h #include stdlib.h #define Q 1000 typedef struct { char *base ; int stacksize ; int length; }SqList1; void zj(FILE *fp) { SqList1 r; int i,j; char temp,*p; r.base=(char *) malloc(Q*sizeof(char)); r.stacksize = Q; r.length = 0; while(!feof(fp)) { fscanf(fp, %c ,r.base); r.base++; r.length++; if(r.length == r.stacksize ) { r.base= r.base - r.length; r.base=(char *) realloc(r.base,(r.stacksize + Q) * sizeof(char)); if(!r.base) { printf( ERROR return ; } r.base = r.base + r.stacksize; r.stacksize += Q; } } r.length --; r.base --; r.base= r.base - r.length; for (i = 1 ; i r.length ;++i ) for(j=0;j ++j) if(r.base[i] r.base[j]) { temp = r.base[i]; for(i= i ;i --i ) r.base[i] = r.base[i-1]; r.base[j] = temp; } r.base[r.length] ="\0"; rewind(fp); fprintf(fp, %s ,r.base); fclose(fp); free(r.base); } 8.2 折半插入排序 #include stdio.h #include stdlib.h #define Q 1000 typedef struct { char *base ; int stacksize ; int length; }SqList2; void zb(FILE *fp) { SqList2 r; int i,j ,m, low, high; char temp; r.base=(char *) malloc(1000*sizeof(char)); r.stacksize = 1000; r.length = 0; while(!feof(fp)) { fscanf(fp, %c ,r.base); r.base++; r.length++; if(r.length == r.stacksize ) { r.base= r.base - r.length; r.base=(char *) realloc(r.base,(r.stacksize + Q) * sizeof(char)); if(!r.base) { printf( ERROR return ; } r.base = r.base + r.stacksize; r.stacksize += Q; } } r.length --; r.base --; r.base= r.base - r.length; for ( i = 1 ; i r.length ; i++ ) { temp=r.base[i]; low=0; high=i-1; while( low = high ) { m = (low+high)/2; if ( temp r.base[m] ) high = m-1; else low = m+1; } for( j=i-1; j =high+1; --j ) r.base[j+1]= r.base[j]; r.base[high+1]=temp; } r.base[r.length] ="\0"; rewind(fp); fprintf(fp, %s ,r.base); fclose(fp); free(r.base); } 8.3 希尔排序 #include stdio.h #include stdlib.h #define Q 1000 typedef struct { char *base ; int stacksize ; int length; }SqList3; void xe(FILE *fp) { SqList3 r; int i,j,k,m; char temp; r.length = 0; r.base=(char *) malloc(1000*sizeof(char)); r.stacksize = 1000; while(!feof(fp)) { fscanf(fp, %c ,r.base); r.base++; r.length++; if(r.length == r.stacksize ) { r.base= r.base - r.length; r.base=(char *) realloc(r.base,(r.stacksize + Q) * sizeof(char)); if(!r.base) { printf( ERROR return ; } r.base = r.base + r.stacksize; r.stacksize += Q; } } r.length --; r.base --; r.base= r.base - r.length; for(k = 0; k 10 ; k++) { m = 10 - k; for( i = m ; i r.length; i ++ ) if(r.base[i] r.base[i - m]) { temp = r.base[i]; for(j = i - m ; j = 0 temp r.base[j]; j -= m) r.base[ j + m ] = r.base[j]; r.base[ j + m ] = temp; } } rewind(fp); fprintf(fp, %s ,r.base); fclose(fp); free(r.base); } 8.4 简单选择排序 #include stdio.h #include stdlib.h #define Q 1000 typedef struct { char *base ; int stacksize ; int length; }SqList4; void jd(FILE *fp) { SqList4 r; int i,j ,m; char temp; r.base=(char *) malloc(1000*sizeof(char)); r.stacksize = 1000; r.length = 0; while(!feof(fp)) { fscanf(fp, %c ,r.base); r.base++; r.length++; if(r.length == r.stacksize ) { r.base= r.base - r.length; r.base=(char *) realloc(r.base,(r.stacksize + Q) * sizeof(char)); if(!r.base) { printf( ERROR return ; } r.base = r.base + r.stacksize; r.stacksize += Q; } } r.length --; r.base --; r.base= r.base - r.length; for ( i = 0 ; i r.length ; i++ ) { temp=r.base[i]; for( j = i,m = j +1 ; m r.length ; m++) if(r.base[j] r.base[m]) j = m; r.base[i] = r.base[j]; r.base[j] = temp; } r.base[r.length] ="\0"; rewind(fp); fprintf(fp, %s ,r.base); fclose(fp); free(r.base); } 8.5 堆排序 #include stdio.h #include stdlib.h #define Q 1000 typedef struct { char *base ; int stacksize ; int length; }SqList5; void HeapAdjust(char *r,int s,int m); void dp(FILE *fp) { SqList5 r; int i,j; char temp,*k; r.length = 0; r.base=(char *) malloc(1000*sizeof(char)); r.stacksize = 1000; r.base += 1; while(!feof(fp)) { fscanf(fp, %c ,r.base); r.base++; r.length++; if(r.length == (r.stacksize - 1) ) { r.base= r.base - r.length - 1; r.base=(char *) realloc(r.base,(r.stacksize + Q) * sizeof(char)); if(!r.base) { printf( ERROR return ; } r.base = r.base + r.stacksize; r.stacksize += Q; } } r.length --; r.base --; r.base= r.base - r.length - 1; for(i = r.length / 2;i = 1 ; --i) HeapAdjust(r.base,i,r.length); for(i = r.length ;i = 2 ; --i) { temp = r.base[1]; r.base[1] = r.base[i]; r.base[i] = temp; HeapAdjust(r.base,1,i-1); } k = (char *) malloc((r.length+1)*sizeof(char)); for(i = r.length,j = 0; i = 1; i--,j++) k[j] = r.base[i]; k[j]="\0"; rewind(fp); fprintf(fp, %s ,k); fclose(fp); free(k); free(r.base); } void HeapAdjust(char *r,int k,int m) { int i,j; char x; i=k; x=r[i]; j=2*i; while(j =m) { if( (j m) (r[j] r[j+1]) ) j++; if(x r[j]) { r[i] =r[j]; i = j; j *= 2; } else j = m + 1; } r[i] = x; } 8.6 归并排序 #include stdio.h #include stdlib.h #define Q 1000 typedef struct { char *base ; int stacksize ; int length; }SqList6; void merge(SqList6 r,int h,int m,int w,SqList6 t) { int i,j,k; i = h; j = m + 1; k = h - 1; while((i = m) (j = w)) { k++; if(r.base[i] = r.base[j]) t.base[k] = r.base[i++]; else t.base[k] = r.base[j++]; } if(i m) while(j = w) t.base[++k]=r.base[j++]; else while(i = m) t.base[++k]=r.base[i++]; } void tgb(int s,int n,SqList6 r,SqList6 t) { int i=1; while(i =(n-2*s+1)) { merge(r,i,i+s-1,i+2*s-1,t); i=i+2*s; } if(i (n-s+1)) merge(r,i,i+s-1,n,t); else while(i =n) t.base[i]=r.base[i++]; } void gb(FILE *fp) { SqList6 r; r.length = 0; r.base=(char *) malloc(1000*sizeof(char)); r.stacksize = 1000; r.base += 1; while(!feof(fp)) { fscanf(fp, %c ,r.base); r.base++; r.length++; if(r.length == (r.stacksize - 1) ) { r.base= r.base - r.length - 1; r.base=(char *) realloc(r.base,(r.stacksize + Q) * sizeof(char)); if(!r.base) { printf( ERROR return ; } r.base = r.base + r.stacksize; r.stacksize += Q; } } r.length --; r.base= r.base - r.length - 2; int i,j,n,s=1; n = r.length; SqList6 t; t.base=(char *) malloc(r.stacksize*sizeof(char)); while(s n) { tgb(s,n,r,t); s*=2; if(s n){ tgb(s,n,t,r); s *= 2; } else { i=0; while(i =n) { r.base[i]=t.base[i+1]; i++; } } } r.base[r.length] ="\0"; rewind(fp); fprintf(fp, %s ,r.base); fclose(fp); free(t.base); free(r.base); } 8.7 冒泡排序 #include stdio.h #include stdlib.h #define Q 1000 typedef struct { char *base ; int stacksize ; int length; }SqList7; void mp(FILE *fp) { SqList7 r; int i,j ,m; char temp; r.length = 0; r.base = (char *) malloc(1000*sizeof(char)); r.stacksize = 1000; while(!feof(fp)) { fscanf(fp, %c ,r.base); r.base++; r.length++; if(r.length == r.stacksize ) { r.base= r.base - r.length; r.base=(char *) realloc(r.base,(r.stacksize + Q) * sizeof(char)); if(!r.base) { printf( ERROR return ; } r.base = r.base + r.stacksize; r.stacksize += Q; } } r.length --; r.base --; r.base= r.base - r.length; for( i=0; i r.length ;i++ ) { m=1; for( j = r.length-2;j j -- ) if(r.base[j+1] r.base[j]) { temp = r.base[j+1]; r.base[j+1] = r.base[j]; r.base[j] = temp; m = 0; } if( m ) break; } r.base[r.length] ="\0"; rewind(fp); fprintf(fp, %s ,r.base); fclose(fp); free(r.base); } 8.8 主程序 #include stdio.h #include zj.h #include zb.h #include xe.h #include jd.h #include mp.h #include dp.h #include gb.h void main() { FILE *fp; int sign; while(sign != 0) { printf( 请选择: printf( %6c [1]直接插入排序 ," "); printf( %6c [2]折半插入排序 ," "); printf( %6c [3]希尔排序 ," "); printf( %6c [4]简单选择排序 ," "); printf( %6c [5]堆排序 ," "); printf( %6c [6]归并排序 ," "); printf( %6c [7]冒泡排序 ," "); printf( %6c [0]退出 ," "); printf( 请输入: scanf( %d , sign); if((fp=fopen( kcsj.txt , r+ ))==NULL) { printf( File open error! return; } switch(sign) { case 1: zj(fp); break; case 2: zb(fp); break; case 3: xe(fp); break; case 4: jd(fp); break; case 5: dp(fp); break; case 6: gb(fp); break; case 7: mp(fp); break; case 0: break; } printf( } } 评语: 评阅教师签名: 年 月 日 成 绩

    篇二:数据结构实验报告排序

    数据结构实验报告实验名称: 实验4——排序 学生姓名: 2012211103班内序号: 03 2013年12 月18 1.实验要求使用简单数组实现下面各种排序算法,并进行比较。

    排序算法: 1、插入排序 2、希尔排序 3、冒泡排序 4、快速排序 5、简单选择排序 6、堆排序(选作) 7、归并排序(选作) 8、基数排序(选作) 9、其他 要求: 1、测试数据分成三类:正序、逆序、随机数据 2、对于这三类数据,比较上述排序算法中关键字的比较次数和移动 次数(其中关键字交换计为3 次移动)。

    3、对于这三类数据,比较上述排序算法中不同算法的执行时间,精 确到微秒(选作) 的结果进行分析,验证上述各种算法的时间复杂度编写测试main()函数测试线性表的正确性。

    程序分析北京邮电大学信息与通信工程学院 (1)、设计一个菜单,格式如下:1、直接插入排序 2、希尔排序 3、冒泡排序 4、快速排序 5、选择排序 6、堆排序 7、退出 (2)、选择不同的菜单但进行相应的排序,并给出排序的关键字序列。

    2.1 存储结构 2.2 关键算法分析 本程序包含了9 个函数,它们分别是: (1)、直接插入排序的算法函数InsertSort()。

    void InsertSort(SqList L.r[i];L.r[i] j=i-2;(L.r[0].key L.r[j];L.r[j+1] (2)、希尔排序的算法函数ShellSort()。void ShellSort(SqList intdk 1;//增量while(dk 0) (3)、冒泡排序算法函数BubbleSort()。void BubbleSort(SqList intflag for(j=0;j=H.r[j].key) break; H.r[s] voidHeapSort(HeapType RedTypetemp; HeapAdjust(H,i,H.length); for(i=H.length; H.r[1];H.r[1] H.r[i];H.r[i] temp;HeapAdjust(H,1,i-1); (7)、对存储数字的遍历函数Visit()、初始化函数InitSqList()。void Visit(SqList voidInitSqList(SqList &L,int length;i++)L.r[i].key (8)、主函数main()。关键算法的时间、空间复杂度: 排序法 平均时间 最差情形 稳定度 额外空间 备注 冒泡 小时较好交换 小时较好选择 小时较好插入 大部分已排序时较好北京邮电大学信息与通信工程学院 ShellO(nlogn) 是所选分组快速 O(nlogn) 不稳定O(nlogn) 大时较好归并 O(nlogn) O(nlogn) 稳定 O(nlogn)O(nlogn) 不稳定 大时较好2.3 其他 程序运行结果主函数流程: 主函数main 初始化随机数组 直接插入 排序 InsertSort() 希尔排序 ShellSort() 冒泡排序 BubbleSort 快速排序Qsort() 堆排序 HeapSort() 北京邮电大学信息与通信工程学院 总结首先,对程序的设计缺少优化,本次程序需要运行之后手动进行输入数据,以后可以尝 试把数据改为在源代码中输入,这样就可以运行之后上显示数据,这样就避免了相同数据 的重复输入。

    此外,生成数组函数及本程序中的代码有的采用了递归形式,如果考虑用栈来模拟的话, 效率会有提升,所以运行时间还和代码的实现有关。

    本程序出现过的问题是主函数对个函数的调用以及对存储数组的调用上出现了问题,导 致排序的结果以及排序的界面出现了问题,得不到实现。后来对算法进行改进,最终把问题 得以解决。而且以后可以试着去写一段可以计算出时间的函数。

    代码 #include #include #include using namespace std; int j,temp,k;//设置全局变量long double GetNowTime() //取系统时间 LARGE_INTEGERlitmp; LONG64 QPart; QueryPerformanceCounter( QPart=litmp.QuadPart; return (long double)QPart; //插入排序void InsertSort(int intmove=0, compare=0; long double start=0,end=0,time=0; start=GetNowTime(); if(r[i]0&&r[0]>a[i]; //滁a href="http://www.canlanjiao.com/yongzuowen/" target="_blank" class="keylink">蛹淌淙氪判蚣锹贾 catch(char*wrong) px(a,numv);//调用排序函数 cout>b[i]; //从键盘输入待排序记录值 catch(char*wrong) px(b,numv);//调用排序函数 cout>c[i]; //从键盘输入待排序记录值 catch(char*wrong) px(c,numv);//调用排序函数 return

    篇三:数据结构实验报告排序

    2018-01-082018-02-222018-01-172018-01-152018-01-142018-02-252018-02-092018-01-062018-01-152018-02-032018-02-112018-03-092018-03-102018-01-062018-02-282018-02-022018-01-052018-03-092018-03-082018-03-11上一页1

    相关热词搜索:数据结构排序实验总结 数据结构排序实验心得 数据结构实验报告排序

    【实验报告】图文推荐
    网友评论

    Copyright © 2006 - 2016 canlanjiao.com All Rights Reserved

    池锝网 版权所有