數(shù)據(jù)結(jié)構(gòu)(Java版) 線性表的實現(xiàn)與應(yīng)用完整版

1、實 驗 報 告課程名稱 數(shù)據(jù)結(jié)構(gòu) 實驗項目 線性表的實現(xiàn)及應(yīng)用 實驗儀器 PC機一臺 學(xué) 院_ 專 業(yè) 班級/學(xué)號 姓名 實驗日期 成 績 指導(dǎo)教師 北京信息科技大學(xué)信息管理學(xué)院（數(shù)據(jù)結(jié)構(gòu)課程上機）實驗報告專業(yè): 班級: 學(xué)號: 姓名: 成績: 實驗名稱線性表的實現(xiàn)及應(yīng)用實驗地點實驗時間1. 實驗?zāi)康模海?） 理解用順序表實現(xiàn)線性表的特點；熟練掌握順序表的基本操作；學(xué)會利用順序表解決實際應(yīng)用問題。（2） 熟練掌握單鏈表的使用；理解用鏈表實現(xiàn)線性表的特點；了解鏈表的多種形式；學(xué)會利用單鏈表解決實際應(yīng)用問題。2. 實驗要求：（1） 學(xué)時為8學(xué)時；（2） 能在機器上正確、調(diào)試運行程序；（3） 本實驗

2、需提交實驗報告；（4） 實驗報告文件命名方法：數(shù)據(jù)結(jié)構(gòu)實驗_信管16xx_學(xué)號_姓名.doc。3. 實驗內(nèi)容和步驟：第一部分 順序表的實現(xiàn)與應(yīng)用（1）基于順序表實現(xiàn)線性表的以下基本操作：public interface LList<T> /線性表接口，泛型參數(shù)T表示數(shù)據(jù)元素的數(shù)據(jù)類型 boolean isEmpty(); /判斷線性表是否空 int size(); /返回線性表長度 T get(int i); /返回第i（i0）個元素 void set(int i, T x); /設(shè)置第i個元素值為x void insert(int i, T x); /插入x作為第i個元素 voi

3、d insert(T x); /在線性表最后插入x元素 T remove(int i); /刪除第i個元素并返回被刪除對象 int search(T key); /查找，返回首次出現(xiàn)的關(guān)鍵字為key的元素的位序void removeAll(); /刪除線性表所有元素 public String toString();/返回順序表所有元素的描述字符串，形式為“（，）”要求：實現(xiàn)后應(yīng)編寫代碼段對每個基本操作做測試。（2）順序表的簡單應(yīng)用a) 運用基本操作編寫算法刪除第i個開始的k個元素。b) 編寫高效算法刪除第i個開始的k個元素。c) 將兩個順序表合并為一個順序表（表中元素有序）；d) 若兩個元素

4、按值遞增有序排列的順序表A和B，且同一表中的元素值各不相同。試構(gòu)造一個順序表C，其元素為A和B中元素的交集，且表C中的元素也按值遞增有序排列；（3）利用順序表解決約瑟夫環(huán)問題：已知n個人（以編號1，2，3.n分別表示）圍坐在一張圓桌周圍。從編號為k的人開始報數(shù)，數(shù)到m的那個人出列；他的下一個人又從1開始報數(shù)，數(shù)到m的那個人又出列；依此規(guī)律重復(fù)下去，直到圓桌周圍的人全部出列。要求：輸出出列次序。第二部分 單鏈表的實現(xiàn)與應(yīng)用（4）基于單鏈表實現(xiàn)線性表的以下基本操作（不需要建立接口，直接建立帶頭結(jié)點的單鏈表類）：ADT List<T>boolean isEmpty(); /判斷線性表是否

5、空 int size(); /返回線性表長度 T get(int i); /返回第i（i0）個元素 void set(int i, T x); /設(shè)置第i個元素值為x Node<T> insert(int i, T x); /插入x作為第i個元素 Node<T> insert(T x); /在線性表最后插入x元素 T remove(int i); /刪除第i個元素并返回被刪除對象 void removeAll(); /刪除線性表所有元素 Node<T> search(T key); /查找，返回首次出現(xiàn)的關(guān)鍵字為key元素public String toSt

6、ring(); /返回順序表所有元素的描述字符串，形式為“（，）”要求：實現(xiàn)后應(yīng)編寫代碼段對每個基本操作做測試。（5）實現(xiàn)單鏈表的子類排序單鏈表，覆蓋單鏈表如下方法：void set(int i, T x); /設(shè)置第i個元素值為xNode<T> insert(int i, T x); /插入x作為第i個元素Node<T> insert(T x); /在線性表最后插入x元素Node<T> search(T key); /查找，返回首次出現(xiàn)的關(guān)鍵字為key元素（6）基于排序單鏈表實現(xiàn)線性表的以下綜合應(yīng)用：e) 刪除第i個開始的k個元素。f) 刪除遞增有序單鏈表

7、中所有值大于mink且小于maxk的元素。g) 將兩個單鏈表合并為一個單鏈表，保持有序。h) 若兩個元素按值遞增有序排列的單鏈表A和B，且同一表中的元素值各不相同。試構(gòu)造一個單鏈表C，其元素為A和B中元素的交集，且表C中的元素也按值遞增有序排列。要求利用原有鏈表中的元素。（7）一元多項式的基本運算用排序單鏈表表示一元多項式，并實現(xiàn)以下基本運算：l 一元多項式的建立l 一元多項式的減法運算（要求：在運算過程中不能創(chuàng)建新結(jié)點 即A=A-B）（8）備份自己程序4. 實驗準(zhǔn)備：復(fù)習(xí)教材第2章線性表的知識點熟悉Java編程環(huán)境提前熟悉實驗內(nèi)容，設(shè)計相關(guān)算法5. 實驗過程：第一部分：（1）package

8、ex1;public interface LList<T> /線性表接口，泛型參數(shù)T表示數(shù)據(jù)元素的數(shù)據(jù)類型 boolean isEmpty(); /判斷線性表是否空 int length(); /返回線性表長度 T get(int i); /返回第i（i0）個元素 void set(int i, T x); /設(shè)置第i個元素值為x int insert(int i, T x); /插入x作為第i個元素 int append(T x); /在線性表最后插入x元素 T remove(int i); /刪除第i個元素并返回被刪除對象 void removeAll(); /刪除線性表所有元

9、素 int search(T key); /查找，返回首次出現(xiàn)的關(guān)鍵字為key的元素的位序類名：public class SeqList<T> implements LList<T> protected Object element;protected int n; public SeqList(int length) /構(gòu)造容量為length的空表 this.element = new Objectlength; /申請數(shù)組的存儲空間，元素為null。 /若length<0，Java拋出負(fù)數(shù)組長度異常 java.lang.NegativeArraySizeExc

10、eption this.n = 0; public SeqList() /創(chuàng)建默認(rèn)容量的空表，構(gòu)造方法重載 this(64); /調(diào)用本類已聲明的指定參數(shù)列表的構(gòu)造方法 public SeqList(T values) /構(gòu)造順序表，由values數(shù)組提供元素，忽略其中空對象 this(values.length*2); /創(chuàng)建2倍values數(shù)組容量的空表 /若values=null，用空對象調(diào)用方法，Java拋出空對象異常NullPointerException for (int i=0; i<values.length; i+) /復(fù)制非空的數(shù)組元素。O(n) if (values

11、i!=null) this.elementthis.n+ = valuesi; /對象引用賦值 public boolean isEmpty() /判斷線性表是否空return this.n=0; public int length() /返回線性表長度 return this.n; public T get(int i) /返回第i（i0）個元素 if (i>=0 && i<this.n) return (T)this.elementi; /返回數(shù)組元素引用的對象，傳遞對象引用/ return this.elementi; /編譯錯，Object對象不能返回T對象

12、 return null; public void set(int i, T x) /設(shè)置第i個元素值為x if (x=null) throw new NullPointerException("x=null"); /拋出空對象異常 if (i>=0 && i<this.n) this.elementi = x; else throw new java.lang.IndexOutOfBoundsException(i+"");/拋出序號越界異常 public int insert(int i, T x) /插入x作為第i個元素

13、 if (x=null) throw new NullPointerException("x=null"); /拋出空對象異常 if (i<0) i=0; /插入位置i容錯，插入在最前 if (i>this.n) i=this.n; /插入在最后 Object source = this.element; /數(shù)組變量引用賦值，source也引用element數(shù)組 if (this.n=element.length) /若數(shù)組滿，則擴充順序表的數(shù)組容量 this.element = new Objectsource.length*2; /重新申請一個容量更大的數(shù)組

14、 for (int j=0; j<i; j+) /復(fù)制當(dāng)前數(shù)組前i-1個元素 this.elementj = sourcej; for (int j=this.n-1; j>=i; j-) /從i開始至表尾的元素向后移動，次序從后向前 this.elementj+1 = sourcej; this.elementi = x; this.n+; return i; /返回x序號 public int append(T x) /在線性表最后插入x元素 return this.insert(this.n, x); public T remove(int i) /刪除第i個元素并返回被刪除

15、對象 if (this.n>0 && i>=0 && i<this.n) T old = (T)this.elementi; /old中存儲被刪除元素 for (int j=i; j<this.n-1; j+) this.elementj = this.elementj+1; /元素前移一個位置 this.elementthis.n-1=null; /設(shè)置數(shù)組元素對象為空，釋放原引用實例 this.n-; return old; /返回old局部變量引用的對象，傳遞對象引用 return null; public void removeA

16、ll() /刪除線性表所有元素 this.n=0; public int search(T key) /查找，返回首次出現(xiàn)的關(guān)鍵字為key的元素的位 System.out.print(this.getClass().getName()+".indexOf("+key+")，"); for (int i=0; i<this.n; i+) if (key.equals(this.elementi) /執(zhí)行T類的equals(Object)方法，運行時多態(tài) return i; return -1; public String toString() Str

17、ing str=this.getClass().getName()+"(" /返回類名 if (this.n>0) str += this.element0.toString(); /執(zhí)行T類的toString()方法，運行時多態(tài) for (int i=1; i<this.n; i+) str += ", "+this.elementi.toString(); /執(zhí)行T類的toString()方法，運行時多態(tài) return str+") " public static void main (String args) Seq

18、List<Integer> list=new SeqList<Integer>(20); Integer values=10,1,2,3,4,5,6,7,8,9; SeqList<Integer> list1=new SeqList<Integer>(values); System.out.print("輸出順序表:"); System.out.println(list1.toString(); System.out.println("順序表List是否為空"+list.isEmpty()+",L

19、ist1是否為空"+list1.isEmpty(); System.out.println("list的長度"+list.length()+",list1的長度"+list1.length(); System.out.println("返回list1的第7個元素是:"+list1.get(6); System.out.println("重新設(shè)置第5個元素為19:"); list1.set(4, 19); list1.insert(2, 100); list1.append(20); System.out.

20、println("刪除8:"+list1.remove(8); System.out.print("修改后的順序表:"); System.out.println(list1.toString(); list1.removeAll(); System.out.println("刪除后的順序表："+list1.toString(); /為空 System.out.println("尋找元素50:"+list1.search(50); （2）a) package ex1;public class Del public D

21、el(int i,int k) String values="A","b","C","d","e","f","g","h" int n =values.length; for(int j=0;j<n;j+) System.out.print(valuesj+" "); System.out.println(); for(int j=i+k;j<n;j+) valuesj-k=valuesj; n=n-k;

22、 for(int j=0;j<n;j+) System.out.print(valuesj+ " " ); System.out.println(); public static void main(String args) new Del(2,3); b)package ex1;public class Del2 public Del2(int i,int k) String values="A","x","y","y","b","c","

23、;h" SeqList<String> list=new SeqList<String>(values); System.out.println(list.toString(); for(int j=1;j<=k;j+) list.remove(i); System.out.println(list.toString(); public static void main(String args) new Del2(2,3); c) package ex1;public class Merge public Merge() Integer values1=

24、1,3,5,11; SeqList<Integer> list1=new SeqList<Integer>(values1); Integer values2=2,4,5,22,23; SeqList<Integer> list2=new SeqList<Integer>(values2); SeqList<Integer> list3=new SeqList<Integer>(); int i=0,j=0; while(i<list1.length()&&j<list2.length() if

25、(list1.get(i)<list2.get(j) list3.append(list1.get(i); i+; else list3.append(list2.get(j); j+; while(i<list1.length() list3.append(list1.get(i); i+; while(j<list2.length() list3.append(list2.get(j) ; j+; System.out.println(list1.toString(); System.out.println(list2.toString(); System.out.pri

26、ntln(list3.toString(); public static void main(String args) new Merge(); d) package test;import ex1.SeqList;public class Intersection public Intersection() Integer values1=1,3,5,11,12,13,22,23,50; SeqList<Integer> list1=new SeqList<Integer>(values1); Integer values2=2,4,5,12,19,20,22,23,

27、; SeqList<Integer> list2=new SeqList<Integer>(values2); SeqList<Integer> list3=new SeqList<Integer>(); int i=0,j=0; while(i<list1.length()&&j<list2.length() if(list1.get(i)<list2.get(j) i+; else if(list1.get(i)>list2.get(j) j+; else list3.append(list1.get(

28、i); i+; j+; System.out.println(list1.toString(); System.out.println(list2.toString(); System.out.println(list3.toString(); public static void main(String args) new Intersection(); 3. （1）package ex1;public class Josephus public Josephus(int n, int k, int m) System.out.println("Josephus("+n+

29、","+k+","+m+")，"); SeqList<String> list = new SeqList<String>(n); /創(chuàng)建順序表實例，元素類型是數(shù)字字符，只能排到n=9,否則達(dá)不到效果 for (int i=0; i<n; i+) list.append(char)('1'+i)+""); /順序表尾插入，O(1) / System.out.println(list.toString(); /輸出順序表的描述字符串，O(n) int i = k; /計數(shù)

30、起始位置 while (list.length()>1) /多于一個元素時循環(huán)，計數(shù)O(1) i = (i+m-1) % list.length(); /按循環(huán)方式對順序表進(jìn)行遍歷,圓桌循環(huán) System.out.print("出列"+list.remove(i).toString()+"，"); /刪除i位置對象，O(n) / System.out.println(list.toString(); System.out.println("出列"+list.get(0).toString();/get(0)獲得元素，O(1) p

31、ublic static void main(String args) new Josephus(9,1,3); （2）package test;import ex1.SeqList;public class JosephusA public JosephusA(int n, int k, int m) System.out.println("Josephus("+n+","+k+","+m+")，"); SeqList<Integer> list = new SeqList<Integer>

32、;(n); /創(chuàng)建順序表實例，元素類型是數(shù)字字符，只能排到n=9,否則達(dá)不到效果 for (int i=0; i<n; i+) list.append(i); /順序表尾插入，O(1) / System.out.println(list.toString(); /輸出順序表的描述字符串，O(n) int i = k; /計數(shù)起始位置 while (list.length()>1) /多于一個元素時循環(huán)，計數(shù)O(1) i = (i+m-1) % list.length(); /按循環(huán)方式對順序表進(jìn)行遍歷,圓桌循環(huán) System.out.print("出列"+lis

33、t.remove(i).toString()+"，"); /刪除i位置對象，O(n) / System.out.println(list.toString(); System.out.println("出列"+list.get(0).toString();/get(0)獲得元素，O(1) public static void main(String args) new JosephusA(15,2,9); 第二部分：（4）、package ex2;public class Node<T> public T data;/數(shù)據(jù)域public No

34、de<T> next;/地址域，后繼結(jié)點/構(gòu)造結(jié)點public Node(T data,Node<T> next)this.data =data;this.next=next;/構(gòu)造空結(jié)點public Node()this(null,null);/描述字符串public String toString()return this.data.toString();package ex2;public class SinglyList<T> public Node<T>head;/構(gòu)造空單鏈表public SinglyList()head=new No

35、de<T>();/構(gòu)造單鏈表，由values數(shù)組數(shù)組提供元素public SinglyList(T values)this();Node<T>rear=this.head;for(int i=0;i<values.length ;i+)rear.next=new Node<T>(valuesi,null);rear=rear.next;public boolean isEmpty() /判斷線性表是否空return this.head.next =null; public T get(int i) /返回第i（i0）個元素 Node<T>p

36、=head.next ; for(int j=0;p!=null&&j<i;j+) p=p.next; return (p!=null&&i>=0) ? p.data:null; public void set(int i, T x) /設(shè)置第i個元素值為x if(x=null) throw new NullPointerException("x=null"); /拋出空對象異常 Node<T>p=this.head.next;/0 for(int j=0;p!=null&&j<i;j+) /遍歷

37、尋找第i個結(jié)點（p指向） p=p.next; if(i>0&&p!=null) p.data=x; public int size() /返回線性表長度 int i=0;for(Node<T>p=this.head.next;p!=null;p=p.next)i+; return i; public Node<T> insert(int i, T x) /插入x作為第i個元素 if(x=null) throw new NullPointerException("x=null"); Node<T>front=this.

38、head ;/指定頭結(jié)點 for(int j=0;front.next!=null&&j<i;j+) front=front.next;/以此循環(huán)找i-1 front.next=new Node<T>(x,front.next ); return front.next; public Node<T> insert(T x) if (x=null) throw new NullPointerException("x=null"); /拋出空對象異常 Node<T> front=this.head; /front指向頭結(jié)

39、點 for (; front.next!=null;) /尋找第i-1個或最后一個結(jié)點（front指向） front = front.next; front.next = new Node<T>(x, front.next); /在front之后插入值為x結(jié)點，包括頭插入、中間/尾插入 return front.next; public T remove(int i) /刪除第i個元素并返回被刪除對象 Node<T>p=this.head;/讓p指向頭結(jié)點 for(int j=0;j<i&&p.next!=null;j+) p=p.next; if

40、(p.next!=null) T old=p.next.data ; p.next=p.next.next; return old; return null; public void removeAll() /刪除線性表所有元素 this.head.next=null;/讓頭結(jié)點直接為空 public Node<T> search(T key) /查找，返回首次出現(xiàn)的關(guān)鍵字為key元素 for(Node<T> p =this.head;p.next!=null;p=p.next) if( key.equals(p.data) return p; return null;

41、 public String toString() /返回順序表所有元素的描述字符串，形式為“（，）” String str=this.getClass().getName()+"(" /返回類名 for (Node<T> p=this.head.next; p!=null; p=p.next)/p遍歷單鏈表 str += p.data.toString(); if (p.next!=null) str += "," /不是最后一個結(jié)點時，加分隔符 return str+")" （5）、package ex2;public

42、 class SortedSinglyList<T extends Comparable <? super T>> extends SinglyList<T>/構(gòu)造空排序單鏈表public SortedSinglyList()super();/默認(rèn)調(diào)用父類構(gòu)造方法SinglyList()public SortedSinglyList(SinglyList<T> list) super(); /構(gòu)造空單鏈表 for (Node<T> p=list.head.next; p!=null; p=p.next)/直接插入排序，每趟插入1個元素

43、 this.insert(p.data); /排序單鏈表按值插入 /構(gòu)造 ，將values數(shù)組中的所有對象按值插入public SortedSinglyList(T values)super();for(int i=0;i<values.length;i+)this.insert(valuesi);public void set(int i, T x) /設(shè)置第i個元素值為x throw new UnsupportedOperationException("set(int i, T x)"); /不支持父類方法，覆蓋并拋出異常 public Node<T> insert(int i, T