数据结构实验五-查找与排序的实现

实验报告课程名称数据结构实验名称查找与排序得实现系别专业班级指导教师１1学号姓名实验日期实验成绩一、实验目得掌握交换排序算法（冒泡排序)得基本思想;掌握交换排序算法（冒泡排序)得实现方法；掌握折半查找算法得基本思想；掌握折半查找算法得实现方法;二、实验内容对同一组数据分别进行冒泡排序，输出排序结果。要求：设计三种输入数据序列：正序、反序、无序修改程序:将序列采用手工输入得方式输入增加记录比较次数、移动次数得变量并输出其值,分析三种序列状态得算法时间复杂性对给定得有序查找集合,通过折半查找与给定值k相等得元素。在冒泡算法中若设置一个变量lａstEｘchaｎｇｅIndex来标记每趟排序时经过交换得最后位置,算法如何改进？三、设计与编码1、本实验用到得理论知识2、算法设计３、编码packａｇesoｒt_seaｒch；imｐoｒｔjavａ、utｉl、Sｃａnner；ｐuｂliｃｃlassＳoｒｔ_Sｅaｒch｛／/冒泡排序算法ﻩｐuｂｌｉcvoiｄBubblｅSoｒt（ｉntr[］){ ｉnttemp;ﻩ ｉｎｔcouｎt＝0，move=0；ﻩ ｂｏｏｌeanｆlaｇ=trｕｅ;ﻩ fｏｒ(intｉ＝1;i〈r、lｅnｇｔh＆＆flag；i++){ﻩﻩ ｆlaｇ=fａlse；ﻩﻩ cｏｕｎt++；ﻩ ｆor（inｔｊ=０;j<r、leｎgｔｈ－i;j＋＋）{ if(ｒ[ｊ］＞ｒ[j＋1]）{ ﻩ teｍp=ｒ[j]；ﻩ ﻩﻩｒ［ｊ］=ｒ［j+1］; r［j+1］＝temp； ﻩﻩ moｖe＋+； flａg＝true;ﻩ ﻩ }ﻩﻩﻩ｝ﻩ ｝ﻩﻩＳystem、oｕt、priｎtｌｎ（＂排序后得数组为:”）;ﻩ for（iｎti=０;i〈r、length；ｉ++）{ﻩ ﻩSystｅｍ、oｕt、prinｔ（r［ｉ］＋"”);ﻩ ｝ Sysｔｅｍ、out、println（)；ﻩ System、out、printlｎ(＂比较次数为:"+cｏunt)；ﻩﻩSysteｍ、oｕt、prｉnｔｌn（"移动次数为:”＋ｍove); ｝ﻩｐublicｓtatiｃｉntＢinaｒySeaｒcｈ（iｎｔr[],intkey)｛//折半查找算法ﻩ iｎｔlow=０，hｉgh=ｒ、ｌeｎｇtｈ-1；ﻩ whｉｌe（ｌow＜=hｉgh）{ﻩ inｔmiｄ=（low+hｉgh）/2；ﻩ ﻩif（r［ｍｉd］==key)｛ ﻩｒetuｒnmｉd； ﻩﻩ｝ ﻩﻩelseif(r［mid］>ｋｅy)｛ high=miｄ—1；ﻩﻩ ｝ﻩﻩ elsｅ{ ﻩﻩﻩlｏw=mid＋１; ﻩﻩ｝ ﻩ}ﻩﻩretｕrn－１；ﻩ}//测试 publｉcｓtaｔicvoidmain（Ｓtｒing[］ａrgs)｛ﻩ Ｓoｒｔ_Ｓearchsｓ=newSoｒt＿Searｃh(）； ｉｎtｔ［]=nｅwint［1３]；ﻩ Sｙsｔｅｍ、oｕt、prinｔln(”依次输入１3个整数为："）；ﻩ Ｓcannerｓc＝newScanner（Sｙstem、in）； ﻩｆor（ｉnti=0;ｉ〈t、length；i++）｛ ﻩﻩt[i］=sｃ、nextＩnt()； ﻩ}ﻩﻩSyｓtｅm、ｏuｔ、pｒｉnｔｌｎ("排序前得数组为："）;ﻩ for（iｎｔi=0；i＜t、length；ｉ+＋）｛ﻩ Sysｔem、ouｔ、print（t［ｉ］+"”）；ﻩ } ﻩSystｅm、ｏut、pｒintln(）；ﻩﻩｓｓ、BubblｅSort(t）;//查找 ﻩｗｈile（true）{ﻩﻩSｙstｅm、oｕt、ｐｒinｔｌｎ（＂请输入要查找得数:”); ﻩ ﻩintk=ｓc、nexｔInt（）; ﻩif（BｉnarySeａrch(t,k）>0） System、oｕt、println（k＋＂在数组中得位置就是第：＂+BｉnａrySeａrcｈ(t,k）)；ﻩﻩｅｌse ﻩﻩSｙsｔeｍ、oｕｔ、prｉntｌn（k+”在数组中查找不到！"）；ﻩ }ﻩ}｝四、运行与调试在调试程序得过程中遇到什么问题,就是如何解决得?问题:在计算比较次数与移动次数时，计算数据明显出错。原因:在进行移动与比较得过程中，没有更新标志，导致计数出错。解决办法：在比较与移动得过程中,有进行比较与移动得操作时，更新标志.然后按标志计数。设计了哪些测试数据?预计结果就是什么?说明:测试了ｉｎt类型数据：24117234５３７43１43１１89３310１177预计排序后结果为:４11172331333７４345８9101177241比较次数：=1\*GB３\*MＥRGEFORMＡT①无序：8次＝2\＊ＧＢ3\*MＥＲGＥFＯRＭAT②正序：1次=3\＊GB3\*MEＲＧＥＦORMAT③反序：12次移动次数:=1\＊GＢ3\＊ＭERＧEＦORMAT①无序：３0次=2\＊ＧＢ3＼*MERGＥFORＭAT②正序:0次=3\*ＧB3＼＊ＭＥRGEFORMＡT③反序:78次查找数3３得位置为：5查找数１01得位置为：10查找数100得结果为：查找不到程序运行得结果如何=１＼*ROＭAN＼＊MERGEFOＲMATＩ、无序输入:=2\＊ＲOＭAＮ\*MERGEFORＭATII、正序输入:=3\＊ROMＡＮ\*MERGEFＯRMATＩII、反序输入：五、总结与心得六、思考题已知奇偶转换排序如下：第一趟对所有奇数得i，将a[i]与a［i＋１］进行比较