资源描述：
《起泡排序及其改进实验报告》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、数据结构实验报告成绩学号1407405010姓名杨帆批阅教师专业信息与计算科学实验报告递交日期实验题目编制改进的起泡排序算法函数；选择好的排序方法改进已有算法。需求分析1.程序实现的功能：编写函数，可输入一组记录，通过起泡排序算法函数排序，输出记录关键字，再用改进后的函数进行排序，输出关键字，并11比较两个函数的优劣。2.数据输入的内容、输入形式与范围：输入记录关键字，以整型数据输入。3.数据输出的内容与形式有序地输出所有记录关键字。4.编制函数：1)・建立记录存储数组,返回记录个数intcreat(rectypeR[])2).显示
2、输入的记录关键字voidlist(intn,rectypeR[])3).传统起泡排序返冋逐个扫描次数intbubblesort1(intn,rectypeR[])4).改进后起泡排序返回逐个扫描次数intbubblesort2(intn,rectypeR
3、
4、)5).主函数main()完成功能：a).调用函数建立记录存储数组；b).循环赋值，复制一个新的记录数组；c).显示输入后的记录关键字d).调用传统起泡排序函数进行排序并显示其排序后记录关键字和逐个扫描次数。e).调用改进后起泡排序函数进行排序并显示显示其排序后记录关键字和逐个扫
5、描次数。主要算法的算法思想.1.建立记录存储数组：判断当前输入数据是否为・1,若是则停止输入，反之则继续输入数据，最后返回输入数据个数(包括了最后的・1)。2.显示输入的记录关键字从主函数传入n和数组起始地址，循环打卬每个记录的关键字。3.传统起泡排序算法函数外层循坏保证最坏情况排序n・l次，置标志为1,内层循环从后向前依次比较相邻两位记录关键字，如果后一位小，则交换他们并且将标志置为0。且每逐个扫描一次k++。判断标志是否为1,若是则弹岀外层循环。4.改进起泡排序算法函数外层循环保证最坏情况排序ml次，置标志为1,首先判断外层循环
6、次数奇偶,若为偶，则从后向前依次比较相邻两位记录关键字，如果后一位小，则交换他们并且将标志置为0,并且记住数组最后变化的位置。若是奇，则从前向后依次比较相邻两位记录关键字，如果后一位小，则交换他们并且将标志置为0,并且记住数组最后变化的位置。且每逐个扫描一次k++。判断标志是否为1,若是则弹出外层循环。5.主函数调用函数建立记录存储数组；•循环赋值，复制一个新的记录数组；显示输入后的记录关键字。调用传统起泡排序函数进行排序并显示具排序后记录关键字和逐个扫描次数。调用改进后起泡排序函数进行排序并显示显示其排序后记录关键字和逐个扫描次数
7、。三•设计:1.线性表存储结构：顺序表。顺序表每个单元类型定义：typedefstruct{intkey;datatypeother;}rectype;2.参数表（列出所有的符号常量与全局变量）参数名数据传递方式数据内容传递所属函数NULL符号常量空指针0所有函数max符号常量数值100所有函数3.函数间的调用关系图主函数4.列出每个函数的函数芦明、函数作用、函数值、形参内容与形式、主要算法步骤等1).创建存储记录的数组函数函数首部：intcreat(rectypeR[])形参：R[]数组起始地址函数作用：将输入的数据存储在数组中函
8、数值：输入记录关键字个数局部变量i：记录数据个数的累加器scanf(”％d”,&R[i].key);while(R[i].key!=-1)scanf(”％d”，&R[++i].key);return(i);输入一个结点算法主要步骤：(a)输入数据(b)判断数组当前数据是否为(c)若是继续输入数据，数组指针后移(d)返冋输入记录关键字个数2).显示输入的记录关键字函数函数首部：voidlist(intn,rectypeR[])形参：R[]数组起始地址n记录关键字个数函数作用：将存储在数组屮的关键字打印出来两数值：无局部变量L计数器输入
9、一个结点算法主要步骤：(a)建立循环，规定次数for(i=0;i<=n;i++)(b)打印当前数组中第i・l个记录的关键字printf(H%d”,R[i].key);3).传统起泡排序算法函数函数首部：intbubblesort1(intn,rectypeR[])形参：R[]数组起始地址n记录关键字个数函数作用：将记录按其关键字大小顺序进行排序函数值：逐个扫描次数局部变量L循环次数的累加器j：循环次数的累加器k:逐个扫描次数的累加器noswap:标志符号temp:数据交换的中间存储空间变量输入一个结点算法主要步骤：(a)外层循环保证
10、最差扫描n-1次(b)置标志位为1(c)内层循环从开始扫描到最后(d)判断连续两个记录的关键字(e)若后而一个关键字小则交换记录(f)置标志符号为0(g)逐个扫描计数自加for(i=0;i
