起泡排序及其改进实验报告.doc

数据结构实 验 报 告 成绩_学号1407405010姓名杨帆批阅教师 专业信息与计算科学实验报告递交日期实验题目 编制改进的起泡排序算法函数；选择好的排序方法改进已有算法。一 需求分析1.程序实现的功能： 编写函数，可输入一组记录，通过起泡排序算法函数排序，输出记录关键字，再用改进后的函数进行排序，输出关键字，并且比较两个函数的优劣。2 数据输入的内容输入形式与范围: 输入记录关键字，以整型数据输入。3.数据输出的内容与形式 有序地输出所有记录关键字。4. 编制函数：1) .建立记录存储数组，返回记录个数 int creat(rectype R)2) .显示输入的记录关键字 void list(int n, rectype R)3) .传统起泡排序返回逐个扫描次数 int bubblesort1(int n, rectype R)4) .改进后起泡排序返回逐个扫描次数 int bubblesort2(int n, rectype R) 5) .主函数 main ()完成功能：a) .调用函数建立记录存储数组； b).循环赋值，复制一个新的记录数组；c).显示输入后的记录关键字 d).调用传统起泡排序函数进行排序并显示其排序后记录关键字和逐个扫描次数。 e).调用改进后起泡排序函数进行排序并显示显示其排序后记录关键字和逐个扫描次数。二. 主要算法的算法思想.1.建立记录存储数组： 判断当前输入数据是否为-1，若是则停止输入，反之则继续输入数据，最后返回输入数据个数（包括了最后的-1）。2. 显示输入的记录关键字 从主函数传入n和数组起始地址，循环打印每个记录的关键字。3. 传统起泡排序算法函数 外层循环保证最坏情况排序n-1次，置标志为1，内层循环从后向前依次比较相邻两位记录关键字，如果后一位小，则交换他们并且将标志置为0。且每逐个扫描一次k+。判断标志是否为1，若是则弹出外层循环。4. 改进起泡排序算法函数 外层循环保证最坏情况排序n-1次，置标志为1，首先判断外层循环次数奇偶，若为偶，则从后向前依次比较相邻两位记录关键字，如果后一位小，则交换他们并且将标志置为0，并且记住数组最后变化的位置。若是奇，则从前向后依次比较相邻两位记录关键字，如果后一位小，则交换他们并且将标志置为0，并且记住数组最后变化的位置。且每逐个扫描一次k+。判断标志是否为1，若是则弹出外层循环。5. 主函数 调用函数建立记录存储数组；.循环赋值，复制一个新的记录数组；显示输入后的记录关键字。调用传统起泡排序函数进行排序并显示其排序后记录关键字和逐个扫描次数。调用改进后起泡排序函数进行排序并显示显示其排序后记录关键字和逐个扫描次数。三. 设计：1线性表存储结构：顺序表。顺序表每个单元类型定义：typedef structint key;datatype other;rectype;2参数表（列出所有的符号常量与全局变量）参数名数据传递方式数据内容传递所属函数NULL符号常量空指针0所有函数max符号常量数值100所有函数3 函数间的调用关系图4 列出每个函数的函数声明、函数作用、函数值、形参内容与形式、主要算法步骤等 1)创建存储记录的数组函数函数首部：int creat(rectype R) 形参：R 数组起始地址 函数作用：将输入的数据存储在数组中 函数值：输入记录关键字个数 局部变量 i：记录数据个数的累加器 输入一个结点算法主要步骤：(a) 输入数据 scanf(%d, &Ri.key);(b) 判断数组当前数据是否为-1 while (Ri.key != -1) (c) 若是继续输入数据，数组指针后移 scanf(%d, &R+i.key); (d) 返回输入记录关键字个数 return(i); 2)显示输入的记录关键字函数函数首部：void list(int n, rectype R) 形参：R 数组起始地址 n 记录关键字个数 函数作用：将存储在数组中的关键字打印出来 函数值：无 局部变量 i：计数器 输入一个结点算法主要步骤：(a) 建立循环，规定次数 for (i = 0; i = n; i+) (b) 打印当前数组中第i-1个记录的关键字 printf(%d ,Ri.key); 3)传统起泡排序算法函数函数首部：int bubblesort1(int n, rectype R) 形参：R 数组起始地址 n 记录关键字个数 函数作用：将记录按其关键字大小顺序进行排序 函数值：逐个扫描次数局部变量 i：循环次数的累加器 j：循环次数的累加器 k: 逐个扫描次数的累加器 noswap:标志符号 temp: 数据交换的中间存储空间变量 输入一个结点算法主要步骤：(a) 外层循环保证最差扫描n-1次 for (i = 0; i = i; j-) (d) 判断连续两个记录的关键字 if (Rj + 1.key Rj.key)(e) 若后面一个关键字小则交换记录 temp = Rj + 1;Rj + 1 = Rj;Rj = temp;(f)置标志符号为0 noswap = 0;(g)逐个扫描计数自加 k+;(h)若标志符号为1,则跳出 if (noswap = 1)break;(i)返回逐个扫描次数 return(k); 4)改进起泡排序算法函数函数首部：int bubblesort2(int n, rectype R) 形参：R 数组起始地址 n 记录关键字个数 函数作用：将记录按其关键字大小顺序进行排序 函数值：逐个扫描次数局部变量 i：循环次数的累加器 j：循环次数的累加器 k: 逐个扫描次数的累加器 m: 从后往前扫描最后变化的位置 p: 从后往前扫描最后变化的位置 q: 从前往后扫描最后变化的位置（m为循环条件所以找个中间变量来传递） noswap:标志符号 temp: 数据交换的中间存储空间变量 输入一个结点算法主要步骤：(a) 外层循环保证最差扫描n-1次 for (i = 0; i = i; j-) (e) 判断连续两个记录的关键字 if (Rj + 1.key Rj.key)(f) 若后面一个关键字小则交换记录 temp = Rj + 1;Rj + 1 = Rj;Rj = temp;(g) 置标志符号为0 noswap = 0;(h) 记住最后变化位置 q = j;(i) 逐个扫描计数自加 k+;(j) 记住下一次待排的数组首位 m =q + 1;(k) 若为奇内层循环从开始扫描到最后 for (j = m; j Rj + 1.key)(m) 若后面一个关键字小则交换记录 temp = Rj + 1;Rj + 1 = Rj;Rj = temp;(n) 置标志符号为0 noswap = 0;(o) 记住最后变化位置 q = j;(p) 逐个扫描计数自加 k+;(q) 记住下一次待排的数组首位 p = q - 1;(r) 若标志符号为1,则跳出 if (noswap = 1)break;(s) 返回逐个扫描次数 return(k); 四. 调试分析： 1).创建存储记录的数组函数 函数首部： int creat(rectype R) T(n)=O(n) 2).显示输入的记录关键字函数 函数首部：void list(int n, rectype R) T(n)=O(n) 3)传统起泡排序算法函数 函数首部：int bubblesort1(int n, rectype R) T(n)=O(n2) 4)改进起泡排序算法函数 函数首部：int bubblesort2(int n, rectype R) T(n)=O(n2) 主函数 main () T(n)=O(n2)五. 使用说明：如何使用你编制的程序、操作步骤. 编译程序成功后，按界面提示输入所有记录关键字序列并最后以-1结尾。6. 测试结果：输入输出数据内容：窗口显示如下：(下划线部分为输入部分，其余为输出部分)测试数据一：请输入记录的关键字(并以-1结束输入)：2 3 5 1 9 3 7 2 -1显示记录的关键字：2 3 5 1 9 3 7 2显示记录的关键字：1 2 2 3 3 5 7 9扫描次数：22显示记录的关键字：1 2 2 3 3 5 7 9扫描次数：21请按任意键继续. . .测试数据二：请输入记录的关键字(并以-1结束输入)：1 2 3 4 5 6 21 2 23 43 23 2 14 43 56 67 78 89 90 -1显示记录的关键字：1 2 3 4 5 6 21 2 23 43 23 2 14 43 56 67 78 89 90显示记录的关键字：1 2 2 2 3 4 5 6 14 21 23 23 43 43 56 67 78 89 90扫描次数：66显示记录的关键字：1 2 2 2 3 4 5 6 14 21 23 23 43 43 56 67 78 89 90扫描次数：48请按任意键继续. . .测试数据三：请输入记录的关键字(并以-1结束输入)：1 2 3 4 5 6 0 -1显示记录的关键字：1 2 3 4 5 6 0显示记录的关键字：0 1 2 3 4 5 6扫描次数：11显示记录的关键字：0 1 2 3 4 5 6扫描次数：11请按任意键继续. . .测试数据四：请输入记录的关键字(并以-1结束输入)：1 2 3 4 5 12 5 312 32 45 31 6 7 8 9 10 11 21 3 25 64 6 123 54 55 56 57 58 -1显示记录的关键字：1 2 3 4 5 12 5 312 32 45 31 6 7 8 9 10 11 21 3 25 64 6 123 5455 56 57 58显示记录的关键字：1 2 3 3 4 5 5 6 6 7 8 9 10 11 12 21 25 31 32 45 54 55 56 57 58 64 123 312扫描次数：357显示记录的关键字：1 2 3 3 4 5 5 6 6 7 8 9 10 11 12 21 25 31 32 45 54 55 56 57 58 64 123 312扫描次数：165请按任意键继续. . .注释！由实验数据知，当数据较为离散时，两种方法扫描次数差异不大。而当数据出现有连续有序序列时，改进后的算法在扫描次数上明显减少许多！七源代码清单/ ConsoleApplication2.cpp : 定义控制台应用程序的入口点。/#include stdafx.h#include stdio.h#include stdlib.h#define max 100#define NULL 0typedef char datatype;typedef structint key;datatype other;rectype;int creat(rectype R)int i=0;printf(请输入记录的关键字(并以-1结束输入)：n);scanf(%d, &Ri.key);while (Ri.key != -1)scanf(%d, &R+i.key);return(i);void list(int n, rectype R)int i;printf(显示记录的关键字：);for (i = 0; i = n; i+)printf(%d ,Ri.key);printf(n);int bubblesort1(int n, rectype R)int i, j,k=0, noswap;rectype temp;for (i = 0; i = i; j-)if (Rj + 1.key Rj.key)temp = Rj + 1;Rj + 1 = Rj;Rj = temp;noswap = 0;k+;if (noswap = 1)break;return(k);int bubblesort2(int n, rectype R)int i, j, k = 0, noswap,m=0,p=n-2,q;rectype temp;for (i = 0; i = m; j-)if (Rj + 1.key Rj.key)temp = Rj + 1;Rj + 1 = Rj;Rj = temp;noswap = 0;q = j;k+;m =q + 1;elsefor (j = m; j Rj + 1.key)temp = Rj + 1;Rj + 1 = Rj;Rj = temp;noswap = 0;q = j;k+;p = q - 1;if (no