華南農(nóng)業(yè)大學(xué)數(shù)據(jù)結(jié)構(gòu)java版實驗二

1、實驗報告線性表華南農(nóng)業(yè)大學(xué)信息（軟件）學(xué)院數(shù)據(jù)結(jié)構(gòu)（JAVA）綜合性、設(shè)計性實驗成績單班級16信管3班學(xué)號03xx姓名黃xx實驗二線性表的基本操作成績教師簽名開設(shè)時間：2017學(xué)年第二學(xué)期實驗?zāi)康?(1)理解線性表的邏輯結(jié)構(gòu)、兩種存儲結(jié)構(gòu)和數(shù)據(jù)操作，熟練運用 表的基本操作，分析各種操作算法特點和時間復(fù)雜度。掌握單鏈表的遍歷、插入和刪除等操作算法，實現(xiàn)多項式相加。JAVA語言實現(xiàn)線性實驗內(nèi)容:1、設(shè)計一個有序順序表(元素已排序，遞增或遞減) 位置由其值決定。實現(xiàn)：(1)升序排序順序表類名為：SortedSeqList，存成文件;(2 )另外編寫文件來演示調(diào)用排序順序表Public class S

2、ortedSeqList private int MAX_SIZE= 10;private int ary = new intMAX_SIZEI;private int length = 0;p ublic SortedSeqList(i nt array) if (array = null |= 0) =0; else ，實現(xiàn)插入、刪除等操作，元素插入ary = array;len gth =;public void clear() len gth = 0;public boolean I isEmpty() return length = 0；public void delete( int

3、 index ) throws Exception if (length = 0) throw new Exception( "No elment to delete" ); int newAry = new int - 1; for (int i = 0, j = 0; i < ; i+) if (i = index ) continue ; else newAry j+ = ary i;ary = newAry ;length -;public int insert( int value ) throws Exception if (length = MAX_SI

4、ZE) throw new Exception( "List is full, can't insert more" ); int newAry = new int length + 1; int i = 0, j = 0;for (; i < ; i+, j+) if (aryi >= value ) newAry j = value ; break ; else newAry j = ary i;while (i < newAry +j = aryi; i+;ary = newAry ; length +; return value;publi

5、c void display() "nList now is: " );for (int i = 0; i < ; i+) + "t" );(2)文件來演示調(diào)用排序順序表p ublic class SortedSeqList_ex p ublic static void main( Stri ng args) throws Exce pti on in t ary = 1,2, 3, 5, 7;SortedSeqList list = new SortedSeqList(ary);();；();(2);();(3 )實驗結(jié)果wWrElrulHi.

6、Mil舸4|l砂 妙M帀“血|抽 0*±i-l II P4|iLlSl 2 1 碁1? J sL is-t new* if1丄4I Bl件1巧1J4B2、在SinglyLinkedList類中增加下列成員方法。Public SinglyLinkedList(E element);public class Test staticstaticstaticstaticstaticstaticIn teger x=3,5,8,11;In teger x1 =3,5,8,11;In teger x2=2,6,8,9,11,15,20;SinglyLinkedList<Integer>

7、; Listi =new SinglyLinkedList<Integer>( x);SinglyLinkedList<Integer> List2= new SinglyLinkedList<Integer>( x1);SinglyLinkedList<Integer> List3= new SinglyLinkedList<Integer>( x2);public static void disList(SinglyLinkedList List)"%-5d",;for (Node temp=public st

8、atic void concat() (List3);public static void Find()"請輸入需要查找的數(shù)：")；Scanner scan=new Scanner; In teger eleme nt=();Node t=(eleme nt);if(t!= null)else"List1中找不到指定的數(shù)。“);public static void ContainO"請輸入所需包含的數(shù)：")；Scanner scan=new Scanner;In teger eleme nt=();if(eleme nt)"List3

9、 包含指定的數(shù) -5dn" ,element);else"List3 不包含指定的數(shù) %-5dn" ,element);public static void remove()"請輸入指定移除的數(shù)：");Scanner scan=new Scanner;In teger eleme nt=();if(eleme nt)"%-5d 已在 List3中移除 n" ,element);else "%-5d無法在List3中找到，無法移除n" ,element);public static void replace

10、()"請輸入所需交換的兩個數(shù)：");Scanner scan=new Scanner;In teger obj=();In teger eleme nt=();if(obj, eleme nt)"%-5d 與 %-5d兩個數(shù)成功交換 n" ,obj,element);else "無法改動“)；public static void equals()if(List2)"List1與List2兩個單鏈表相等“)；else "List1與List2兩個單鏈表不相等 ");if(List3)"List1與List3

11、兩個單鏈表相等“)；else "List1與List3兩個單鏈表不相等 ");Public static void main(String args) disList(List1);disList(List2);disList(List3);con cat();disList(List1);Fin d();Co ntai n();remove ();rep lace();equals();(2 )實驗結(jié)果電tdmmuted*1 Lkp Appliwtkjn 訓(xùn)忙gidm咅 D 砧3過ifAjdwdw出iw 門01暉5月 IDH 下工 1:QQQ出1467e913,先寫出LL

12、ist接口并寫上要實現(xiàn)的方法的方法頭，再CircSinglyLinkedList類中繼承該接口并實現(xiàn)其方法。(1)寫出 LList接口 ；P ublic in terface LList<T> boolea n isE mp ty();int size();T get(i nt i);void set(i nt i,T x);Stri ng toStri ng();T remove(i nt i);void clear();int search(T key);boolea n contains(T key);T in sertDiffere nt(T x);T remove(T k

13、ey);boolea n equaIsQbject obj);結(jié)點類P ackage Lab2;public class Node<T> p ublic T data;p ublic Node<T> n ext;public Node(T data, Node<T> next)=data;=next;public Node() this(null, null);public Stri ng toStri ng()return (3)CircSinglyLinkedList 類public class CircSinglyLinkedListvTimpleme

14、nts LListvT>p ublic NodevT> head;Overridepublic boolean isEmpty（） .n分別表示）圍坐在一張圓桌周圍。從編號為k的人開始報數(shù)，數(shù)到m的那個人出列；他的下一個人又從1開始報數(shù)，數(shù)到 m的那個人又出列；依此規(guī)律重復(fù)下去，直到圓桌周圍的人全部出列。運作原理：1、一群人圍在一起坐成環(huán)狀（如： N）2、 從某個編號開始報數(shù)（如：K）3、數(shù)到某個數(shù)（如： M）的時候，此人出列，下一個人重新報數(shù)4、一直循環(huán)，直到所有人出列，約瑟夫環(huán)結(jié)束(1)循環(huán)單鏈表P ublic class Jose phus_S in glyL in kedL

15、ist p ublic Jose phus_S in glyL in kedList(i nt nu mber, i nt start, int dista nee) Sin glyL in kedListvStri ng> list = new Sin glyL in kedListvStri ng>(); rint("約瑟夫環(huán)("+ number + "," + start + "," + distanee + ")，");int i = start - 1; oString() + ”，"

16、;);"被赦免者是 ” + (O).toString();p ublic static void main( Stri ng args) new Jose phus_S in glyL in kedList(5, 1,2);(2)循環(huán)雙鏈表public classJosephus_CirDoublyLinkedList /*存儲約瑟夫環(huán)中多個對象*/p rivate CirDoublyLinkedListvStringlist;/*創(chuàng)建約瑟夫環(huán)并求解，參數(shù)指定環(huán)長度、起始位置、計數(shù)* p aram number* p aram start* p aram distance*/p ub

17、lic Jose phus_CirDoublyLinkedList(int number, int start, int distance) =new CirDoublyLinkedList<String>();for (int i = 0; i < number; i+)String(char) ('A' + i) +.print("約瑟夫環(huán)("+ number + "," + start + "," + distance + ")，"); oStringO);public st

18、atic void main(String args) new Jose phus_CirDoublyLinkedList(5, 1,2);(3 )運行結(jié)果(A,C,D,E) (A,C,E) (C,E)(C)B，D，a，E，約瑟夫環(huán)(5,1,2), (A,B,C,D,E) 刪除 刪除 刪除 刪除 被赦免者是C(3)分析操作效率使用循環(huán)鏈表實現(xiàn)約瑟夫環(huán)是一種解法，但是效率不高。采用雙向循環(huán)鏈表刪除操作需要 維護2各指針。不需要記錄 a的指針只要簡單的指針維護即可，雙向鏈表的查找可以在任 意位置開始查找，效率高了一些。8,先給該線性表創(chuàng)建一個迭代器，然后用hasNextO判斷是否存在后繼元素，再利

19、用next()方法來取得這個元素和形參比較。跟相似，只是這里是兩個線性表，然后分別給他們創(chuàng)建一個迭代器，然后將他們的 元素對應(yīng)的逐個逐個的比較，從而比較線性表是否相等。imp ort先給該線性表創(chuàng)建一個迭代器，然后用hasNextO判斷是否存在后繼元素，再利用next()方法來取得這個元素和形參比較。Public class ListIter public static int indexOf(Object s, Object obj)lteratorvObject> iter = (list<Object>) s) iterator。;int idx = 0;while (

20、)Object str =();if(str) return idx;idx+;return -1;跟相似，只是這里是兩個線性表，然后分別給他們創(chuàng)建一個迭代器，然后將他們 的元素對應(yīng)的逐個逐個的比較，從而比較線性表是否相等。Public static boolean equaIsQbject obj1, Object obj2) lteratorvObject> iter1 = (List<Object>) obj1).iterator(): Iterator<Object> iter2 = (List<Obiect>) obi2).iterator(

21、); while () && ()Object str1 =();Object str2 =();if(!(str2) return false:if(!() && !() return true :return false;9,算法實現(xiàn)：多項式相加一條單鏈表可以表示一個一元多項式，每個結(jié)點包含三個域：指數(shù)域、系數(shù)域和后繼 結(jié)點鏈。表示多項式 3x4 6x2 5x 10的單鏈表如圖1所示。給定兩個多項式，實現(xiàn)兩個 多項式相加算法。系數(shù)指數(shù)鏈實現(xiàn)代碼：P ackage Q3;Public class Node<T> p ublic T base;p u

22、blic T in dex;p ublic Node<T> n ext;p ublic Node(T base,T in dex,Node<T> n ext)=base;=in dex;=n ext;public Node()this (null ,null ,null );package Q3;public class Polynomial public static Node<Integer> head;public static Node<Integer> Create( int t) Node<Integer> p= new

23、Node<Integer>(); head=p;for (int i=0;i<i+)=new Node<Integer>(ti0,ti1, null ); p=; print (head ); return head;public static void print(Node<Integer> a)a=;while !=null )"A" +" + ")； a=;"A"+;public static Node<Integer> Add(Node<Integer> a,N

24、ode<Integer> b) Node<Integer> p= new Node<Integer>();head=p;a=;b=; while (a!=null &&b!= null )if<= if=new Node<Integer>+, null );p=;a=;b=;else=new Node<Integer>, null );p=;a=; else=new NodevInteger>” null);P=；b=；if(a=null)while (b!=null)=new NodevInteger&g

25、t;, null);P=；b=;if(b=null)while =null)=new NodevInteger>, null);p=;a=;head;returnp ackage Q3;public class Test extends Polynomialpublic static void main(String args)int 叩 a=1,1,2,4,3,4,1,5,1,6,2,7;in t b=1,1,6,2,3,4,2,5;Nodev In teger>a1= new Nodev In teger>();Nodev In teger>b1= new Node

26、v In teger>(); a1=Create(a);b1=Create (b);prin t(Add(a1,b1);10,有效管理一個 1n的隨機數(shù)序列，要求生成初始序列，保證序列中的元素值不重復(fù)，當(dāng)增加或刪除一個元素的時候，使序列元素值動態(tài)更新。例如，一個MP3播放器使用速記方式播放10首歌曲，曲目播放次序就是由110組成的一個隨機數(shù)序列，當(dāng)增加或刪除一首歌的時候，要及時更新序列中元素值，不重復(fù)播放Public class RandomListvE> p ublic NodevE> head;p ublic Ran domListQ =new NodevE>();p ublic Ran domList(i nt n) this();NodevE> P =;int count = 0;while (co unt v n) int number = (in t) () * (n) + 1;E num = (E) new In teger( nu mber);