大数据结构实验报告材料2

1、广东金融学院实验报告课程名称：数据结构头验编号 及实验名称实验二：排序和查找实验系别计算机科学与技 术系姓名学号班级实验地点实验日期实验时数6指导教师同组其他成员无成绩一、实验目的及要求1、通过编写和调用直接插入排序、希尔排序、冒泡排序和快速排序四种排序算法实现数据排序，充分理解各种排序算法的算法思想、排序过程及各自的时间复杂度、稳定性。2、通过编写和调用顺序查找和二分查找算法实现数据查找，掌握两个查找算法的基本思想、实 现方法和时间性能。二、实验环境及相关情况(包含使用软件、实验设备、主要仪器及材料等)1、实验设备：微型计算机；2、软件系统： Windows XP、DWMX三、实验内容(一)

2、 排序(1 )参照课本，分别编与Java程序，实现顺序表记录类RecordNode、类KeyType。(2) 参照课本，编写一个Java程序，实现顺序表类SeqList，并在其中添加成员函数：len gth()求顺序表的当前长度；display。输出数组兀素的关键子；直接插入排序算法；带监视哨的直接插入排序；希尔排序算法；起泡排序算法；快速排序算法。(3) 编写主程序，循环选择调用以上5个排序算法，对数组元素排序，并输出排序过程。(二) 查找(1) 在排序实验的基础上，在类SeqList中添加成员函数：不带监视哨的顺序查找算法；带监视哨 的顺序查找算法；二分查找算法。(2) 编写主程序，循环选

3、择调用以上3个查找算法，分别对键入的关键字记录进行成功和不成功查 找public class KeyType implements Comparableprivate int key;public KeyType()public KeyType( int key)this . key =key;public int getKey()return key;public void setKey( int key)this . key=key;public Stri ng toStri ng()return key + ;public int compareTo(KeyType another)in

4、t thisVal= this . key ;int anotherVal=another.key ;return (thisValanotherVal? -1:(thisVal=anotherVal? 0:1);public class RecordNodeprivate Comparable key;private Object element ;public Object getEleme nt()returnelement ;public void setElement(Object element)this . element =element;public Comparable g

5、etKey()return key;public void setKey(Comparable key)this . key =key;public RecordNode(Comparable key)this . key =key;public RecordNode(Comparable key,Object eleme nt)this . key =key;this . element =element;public class SeqListprivate RecordNode r;private int curlen ;public SeqList( int maxSize)this

6、. r=new RecordNodemaxSize;this . curlen =0;public RecordNodegetRecord()return r;public void setRecord(RecordNoder)this . r=r;public int length()returncurlen ;public void display()for (int i=0;i curlen ;i+)System. out .print(r i.getKey()+ );public void insert( int i,RecordNode x) throws Exceptionif (

7、 curlen =r. length )throw new Exception(顺序表已满)；if (i curlen )throw new Exception(插入位置不合理)；for ( int j= curlen ;ji;j-)rj= rj-1;r i=x;this . curlen +;public void insertSort() / 直接插入RecordNode temp;int i,j;for (i=1;i=0&temp.getKey().compareTo(r j.getKey()0;j-)r j+1= r j;r j+1=temp;public void shellSort

8、( int d)/ 希尔RecordNode temp;int i,j;for (int k=0;kd. length ;k+)int dk=dk;for (i=dk;i=0&temp.getKey().compareTo(r j.getKey()0;j-=dk)r j+dk=temp;public void insertSortWithGuard()/ 带监视哨的直接插入int i,j;for (i=1;ithis . curlen ;i+)r0= ri;for (j=i-1;r 0.getKey().compareTo(rj.getKey()0;j-)r j+1= rj;r j+1= r0

9、;public void bubbleSort()/ 冒泡RecordNode temp; boolean flag= true ;for (int i=1;i this . curlen &flag;i+)flag= false ;for (int j=0;j0) temp=rjrj= rj+1;r j+1=temp;flag= true ;public int Partition( int i, int j)RecordNode pivot = r j;while (ij)while (ij & pivot.getKey().compareTo(rj.getKey()=0)j-;if (i

10、j)ri= rj;i+;while (i0)i+;if (ij)rj= ri;j-;r i=pivot; return i;public void qSort( int low, int high) if (lowhigh)int pivotloc = Partition(low,high); qSort(low,pivotloc-1);qSort(pivotloc + 1,high);public void quickSort() qSort(0, this . curlen - 1);public int seqSearch(Comparable key)int i=0;int n=len

11、gth();while (in& r i.getKey().compareTo(key)!=O) i+;if (i0) return i;else return -1;public int binarySearch(Comparable key)if (length()0)int low=0;int high=length()-1;while (low0)high=mid-1;else low=mid+1;return -1;package paixu;importjava.util.Sca nner;importimportpaixu.RecordNode;paixu.SeqList;pub

12、licclass Test2public static void main(String args)throws ExceptionSca nner in= new Sca nn er(System.in);while (true )SeqList a= new SeqList(6);String d=25 , 20 , 15 , 35 , 10 , 55 ;for (int i=0;i6;i+)RecordNode c= n ewRecordNode(di);a.i nsert(i,c);System. out.print(原数组：);a.display();System. out.prin

13、tln();System. out.println(输入 05进行选择);System, out .println( 1 直接插入排序)；System, out .println( 2带监视哨的直接插入排序”)；System. out.println( 3 希尔排序);System. out .println( 4 冒泡排序”);System. out .println( 5 快速排序”);System. out.println( 0退岀);int g=in.nextInt();switch (g)case 0:return ;case 1:a.i nsertSort();System. ou

14、t .print(排序后:);a.display();System. out .println();break;case 2:a.i nsertSortWithGuard();System. out .print(排序后:);a.display();System. out .println();break;case 3:int aa=1,3,5;a.shellSort(aa);System. out .print(排序后:);a.display();System. out .println();break;case 4:a.bubbleSort();System. out .print(排序后

15、:);a.display();System. out .println();break;case 5:a.quickSort();System. out .print(排序后:);a.display();System. out .println();break;import java.util.Scanner;public class Testpublic static voidmain( Stri ng args)while (12)SeqList a=new SeqList ;Scanner in=new Scanner(System. in );for (int i=0;i4;i+)tr

16、y System. out.println( 输入第+i+ 个元素：)； Stri ng c=i n.n ext();RecordNode d= new RecordNode(c);a.i nsert(i, d); catch (Exception e)System. out.println( 错误：+e.getMessage();a.display(););不带监视哨顺序查找方法查找1的结果为+a.seqSearch( 1);带监视哨顺序查找方法查找2的结果为+a.seqSearchWithGuard( 2);二分查找方法查找 3的结果为+a.binarySearch(3);System.

17、out .println(System. out .println(System. out .println(System. out .println(四、实验步骤及结果（包含简要的实验步骤流程、结论陈述，可附页） 排序运行结果：原数菊匕2520 1S 3510输入”E进行选择居接插人卅序2帯监视哨的頁接插入排序|指泡排序首快速扌非序0退出样序后；X 丄W ：0253555原数组；252Q 15 351055输入S5逬行选择1直接插入擀序端监视哨的直接插入排序病尔卅序厝泡卅序吕快速排序6退出55- 55OS 1315205彳出白2入哨序序序: s m &3 LF LFr LFTz Luis e fa T-iJdJdJ 处接监乐泡速岀查找运行结果：谕入第力个元素!渝入第丄个元素;嗚入第2个元素:4输入第2个元素:不带监视哨顺序查我方法查找二的结果为0 带监视哨顺序査找方法査找d的结果为1 二分查找方法查找的结果为-丄愉入第0个元素：五、