数据结构实验报告2.docx

《数据结构实验报告2.docx》由会员分享，可在线阅读，更多相关《数据结构实验报告2.docx（11页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

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

3、个查找算法，分别对键入的关键字记录进行成功和不成功查 找 publicclassKey Typeimplements Comparable privateintkey;public KeyType( ) )public KeyType( int key) this . key= key;)publicint getKey( ) returnkey;publicvoid setKey( int key) this . key= key;五、实验总结（包括心得体味、问题回答与实验改进意见）答:通过这次试验，编写和调用顺序查找和二分查找算法实现数据查找，我掌握两个查找算 法的基本思想、实现方法和时间

4、性能。六、教师评语1、完成所有规定的实验内容，实验步骤正确，结果正确；2、完成绝大部份规定的实验内容，实验步骤正确，结果正确；3、完成大部份规定的实验内容，实验步骤正确，结果正确；4、基本完成规定的实验内容，实验步骤基本正确，所完成的结果基本正确；5、未能很好地完成规定的实验内容或者实验步骤不正确或者结果不正确。6、其它：评定等级：优秀良好中等与格不与格教师签名：20XX7 月 10 日第10页共10页)public String toString( ) returnkey +;)publicint compareTo( KeyType another) intthisVal= this .

5、key;intanotherVal= another . key;return ( thisVal anotherVal? - 1 : ( thisVal= = anotherVal? 0:1); ) publicclass RecordNodeprivateComparablekey;private Object element ;public ObjectgetElement( ) returnelement;) publicvoid setElement( Object element) this . element= element;)publicComparable getKey(

6、) returnkey;) publicvoidsetKey( Comparable key) this . key= key;)public RecordNode( Comparable key) this . key= key;)public RecordNode( Comparable key, Object element) this . key= key;this . element= element;) publicclass SeqListprivateRecordNode r ;privateintcurlen;publicSeqList( intmaxSize) this -

7、 r= new RecordNode maxSize; this . curlen= 0 ;) public RecordNode getRecord( ) returnr;) publicvoid setRecord( RecordNode r) this . r= r;) publicint length( ) returncurlen; publicvoid display( ) for ( int i= 0 ; i curlen; i+ + ) System . out.print(r i .getKey () +);)publicvoid insert( int i, RecordN

8、ode x) throws Exception if ( curlen= = r . length) thrownew Exception ( 顺序 表已满)； )if (i curlen) thrownew Exception ( 插入位置不合理);)for ( int j= curlen; j i; j - - ) r j = r j - 1；) r i = x; this . curlen+ + ;)publicvoid insertSort( ) / / 直接插入 RecordNode temp;int i, j;for ( i= 1 ; i = 0 & & temp . getKey

9、() pareTo( r j . getKey() ) 0 ; j - - ) r j+l = r j;)r j+ 1 = temp; )publicvoid shellSort( int d) 希尔 RecordNode temp;int i, j;for (int k= 0; k d . length; k+ + ) int dk= d k;for ( i= dk; i = 0 & & temp . getKey()pareTo( r j . getKey( ) ) 0 ; j - = dk) r j+ dk = temp;)publicvoid insertSortWithGuard(

10、) / 带监视哨 的直接插入int i, j;for ( i= 1 ; i this . curlen; i+ + ) r 0 = r i;for (j=i - l;r 0 . getKey( ) pareTo( r j . getKey( ) ) 0 ; j - - ) r j+l = r j3)r j+l = r 0; ) )publicvoid bubbleSort( ) 冒泡RecordNode temp;boolean flag= true;for ( int i= 1 ; i this . curlen& & flag; i+ + ) flag= false;for (int j=

11、 0 ; j 0 ) temp= r j;rr + 1 = temp;flag= true; ) )publicint Partition( int i, int j) RecordNode pivot = r j;while (i j) while (i j & pivot . getKey() pareTo( r j . getKey( ) ) = 0 ) j -；if (i J) r i = r j；i+ + ；)while (i 0 ) i+ + ；if (i J) r j = r i;j-；)r i = pivot;return i;)publicvoid qSort( int lo

12、w, int high) if ( low high) int pivotloc = Partition( low, high);qSort( low, pivotloc - 1 );qSort( pivotloc +1 , high);)publicvoid quickSort( ) qSort( 0 , this . curlen -1 );)publicint seqSearch( Comparable key) int i= 0;int n= length();while (i n&r i . getKey( )pareTo(key) ! = 0) i+ + ；if (i 0 ) in

13、t low= 0;int high= length( ) - 1;while ( low 0) high= mid - 1;elselow= mid+ 1;) ) ) return - 1;) ) package paixu; importjava . util . Scanner;importpaixu . RecordNode;import paixu . SeqList;publicclass Test2 publicstaticvoid main( String args) throws Exception Scanner in= new Scanner( System . in);w

14、hile ( true) SeqList a=new SeqList( 6 );String d = ,；for (int i= 0 ; i 6; i+ + ) RecordNode c= new RecordNode( d i); a . insert( i, c);System . out . printin ( System . out . printin (）；输入。5进行选择）;System . out . printin ( System . out . printin (直接插入排序）;带监视哨的直接插入排序）;System . out . printin ( System .

15、out . printin ( System . out . printin ( System . out . printin ( int g= in . nextlnt();switch ( g) case 0:希尔排序）; 冒泡排序）; 快速排序）; 退出）；return; case 1:a . insertSort();System . out . print ( 排序后 );a . display();System . out . printin ();break; case 2:a - insertSortWithGuard(); System . out . print ( 排序后

16、 System . out . printin ();break;case 3:int aa= 1,3,5;a . shellSort( aa);System . out . print ( 排序后System . out . printin (););a . display();break;case 4:a . bubbleSort();System . out . print ( 排序后System . out . printin (););a . display();break;case 5:a . quickSort();System . out . print ( 排序后System

17、 . out . printin (););a display();break;)；a .display();System . out.print ( 原数组：) )import java . util . Scanner;publicclass Testpublicstaticvoid main( String args) while (12)SeqList a= new SeqList( 4 );Scanner in= new Scanner( System . in);for (int i= 0; iv 4; i+ + ) trySystem . out.printin (输入第 + i

18、+ 个元素 );String c= in . next();RecordNode d= new RecordNode( c); a . insert( i, d); catch ( Exception e) System . out. printin ( 错误： + e . getMessage();) ) a display(); System . out. printin ();System . out . printin (不带监视哨顺序查找方法查找1的结果为+ a . seqSearch ();System . out .printin (带监视哨顺序查找方法查找2的结果为+ a .

19、seqSearchWithGuard ();System . out.printin ( 二分查找方法查找3 的结果为 +a .binarySearch ();四、实验步骤与结果（包含简要的实验步骤流程、结论陈述，可附页） 排序运行结果：原刿组：25201535输入。-5进行选择二直接插入排序2芾监视哨的直接插入排序|3希尔排序宿泡排序5快速排序。退出10排序后;“15 20 25原数组；25201535冶人。-5进行选探二直接插入排序2带监视哨的直接插入排序3希尔排序4冒泡排序5快速排序。退出5555排序后,1。152025原刿组，25201535输入。-5进行选择直接插入排序2芾监视哨的直接插入排序3希尔排序4冒泡排序5快速排序。退出3510查找运行结果：饰人第。个元崇:饰入籍工个元素;愉入第2个元素:渝入第3个元素: e不带监视哨顺序查找方法查找1的结果为。带监视哨顺序交找方法充找2的结果为1 二分查找方法查找3的结果为-1 输入第。个元素，