大數(shù)據(jù)結(jié)構(gòu)實驗報告材料2

1、廣東金融學院實驗報告課程名稱：數(shù)據(jù)結(jié)構(gòu)頭驗編號 及實驗名稱實驗二：排序和查找實驗系別計算機科學與技 術(shù)系姓名學號班級實驗地點實驗日期實驗時數(shù)6指導教師同組其他成員無成績一、實驗目的及要求1、通過編寫和調(diào)用直接插入排序、希爾排序、冒泡排序和快速排序四種排序算法實現(xiàn)數(shù)據(jù)排序，充分理解各種排序算法的算法思想、排序過程及各自的時間復雜度、穩(wěn)定性。2、通過編寫和調(diào)用順序查找和二分查找算法實現(xiàn)數(shù)據(jù)查找，掌握兩個查找算法的基本思想、實 現(xiàn)方法和時間性能。二、實驗環(huán)境及相關(guān)情況(包含使用軟件、實驗設備、主要儀器及材料等)1、實驗設備：微型計算機；2、軟件系統(tǒng)： Windows XP、DWMX三、實驗內(nèi)容(一)

2、 排序(1 )參照課本，分別編與Java程序，實現(xiàn)順序表記錄類RecordNode、類KeyType。(2) 參照課本，編寫一個Java程序，實現(xiàn)順序表類SeqList，并在其中添加成員函數(shù)：len gth()求順序表的當前長度；display。輸出數(shù)組兀素的關(guān)鍵子；直接插入排序算法；帶監(jiān)視哨的直接插入排序；希爾排序算法；起泡排序算法；快速排序算法。(3) 編寫主程序，循環(huán)選擇調(diào)用以上5個排序算法，對數(shù)組元素排序，并輸出排序過程。(二) 查找(1) 在排序?qū)嶒灥幕A上，在類SeqList中添加成員函數(shù)：不帶監(jiān)視哨的順序查找算法；帶監(jiān)視哨 的順序查找算法；二分查找算法。(2) 編寫主程序，循環(huán)選

3、擇調(diào)用以上3個查找算法，分別對鍵入的關(guān)鍵字記錄進行成功和不成功查 找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()/ 帶監(jiān)視哨的直接插入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(原數(shù)組：);a.display();System. out.prin

13、tln();System. out.println(輸入 05進行選擇);System, out .println( 1 直接插入排序)；System, out .println( 2帶監(jiān)視哨的直接插入排序”)；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(););不帶監(jiān)視哨順序查找方法查找1的結(jié)果為+a.seqSearch( 1);帶監(jiān)視哨順序查找方法查找2的結(jié)果為+a.seqSearchWithGuard( 2);二分查找方法查找 3的結(jié)果為+a.binarySearch(3);System.

17、out .println(System. out .println(System. out .println(System. out .println(四、實驗步驟及結(jié)果（包含簡要的實驗步驟流程、結(jié)論陳述，可附頁） 排序運行結(jié)果：原數(shù)菊匕2520 1S 3510輸入”E進行選擇居接插人卅序2帯監(jiān)視哨的頁接插入排序|指泡排序首快速扌非序0退出樣序后；X 丄W ：0253555原數(shù)組；252Q 15 351055輸入S5逬行選擇1直接插入搟序端監(jiān)視哨的直接插入排序病爾卅序厝泡卅序呂快速排序6退出55- 55OS 1315205彳出白2入哨序序序: s m &3 LF LFr LFTz Luis e fa T-iJdJdJ 處接監(jiān)樂泡速岀查找運行結(jié)果：諭入第力個元素!渝入第丄個元素;嗚入第2個元素:4輸入第2個元素:不帶監(jiān)視哨順序查我方法查找二的結(jié)果為0 帶監(jiān)視哨順序査找方法査找d的結(jié)果為1 二分查找方法查找的結(jié)果為-丄愉入第0個元素：五、