1、精選優質文檔-傾情為你奉上實 驗 報 告課程名稱 數據結構 實驗項目 線性表的實現及應用 實驗儀器 PC機一臺 學 院_ 專 業 班級/學號 姓名 實驗日期 成 績 指導教師 北京信息科技大學信息管理學院（數據結構課程上機）實驗報告專業: 班級: 學號: 姓名: 成績: 實驗名稱線性表的實現及應用實驗地點實驗時間1. 實驗目的：（1） 理解用順序表實現線性表的特點；熟練掌握順序表的基本操作；學會利用順序表解決實際應用問題。（2） 熟練掌握單鏈表的使用；理解用鏈表實現線性表的特點；了解鏈表的多種形式；學會利用單鏈表解決實際應用問題。2. 實驗要求：（1） 學時為8學時；（2） 能在機器上正確、調

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

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

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

5、 size(); /返回線性表長度 T get(int i); /返回第i（i0）個元素 void set(int i, T x); /設置第i個元素值為x Node insert(int i, T x); /插入x作為第i個元素 Node insert(T x); /在線性表最后插入x元素 T remove(int i); /刪除第i個元素并返回被刪除對象 void removeAll(); /刪除線性表所有元素 Node search(T key); /查找，返回首次出現的關鍵字為key元素public String toString(); /返回順序表所有元素的描述字符串，形式為“（，）

6、”要求：實現后應編寫代碼段對每個基本操作做測試。（5）實現單鏈表的子類排序單鏈表，覆蓋單鏈表如下方法：void set(int i, T x); /設置第i個元素值為xNode insert(int i, T x); /插入x作為第i個元素Node insert(T x); /在線性表最后插入x元素Node search(T key); /查找，返回首次出現的關鍵字為key元素（6）基于排序單鏈表實現線性表的以下綜合應用：e) 刪除第i個開始的k個元素。f) 刪除遞增有序單鏈表中所有值大于mink且小于maxk的元素。g) 將兩個單鏈表合并為一個單鏈表，保持有序。h) 若兩個元素按值遞增有序排

7、列的單鏈表A和B，且同一表中的元素值各不相同。試構造一個單鏈表C，其元素為A和B中元素的交集，且表C中的元素也按值遞增有序排列。要求利用原有鏈表中的元素。（7）一元多項式的基本運算用排序單鏈表表示一元多項式，并實現以下基本運算：l 一元多項式的建立l 一元多項式的減法運算（要求：在運算過程中不能創建新結點 即A=A-B）（8）備份自己程序4. 實驗準備：復習教材第2章線性表的知識點熟悉Java編程環境提前熟悉實驗內容，設計相關算法5. 實驗過程：第一部分：（1）package ex1;public interface LList /線性表接口，泛型參數T表示數據元素的數據類型 boolean

8、isEmpty(); /判斷線性表是否空 int length(); /返回線性表長度 T get(int i); /返回第i（i0）個元素 void set(int i, T x); /設置第i個元素值為x int insert(int i, T x); /插入x作為第i個元素 int append(T x); /在線性表最后插入x元素 T remove(int i); /刪除第i個元素并返回被刪除對象 void removeAll(); /刪除線性表所有元素 int search(T key); /查找，返回首次出現的關鍵字為key的元素的位序類名：public class SeqList

9、 implements LList protected Object element;protected int n; public SeqList(int length) /構造容量為length的空表 this.element = new Objectlength; /申請數組的存儲空間，元素為null。 /若length0，Java拋出負數組長度異常 java.lang.NegativeArraySizeException this.n = 0; public SeqList() /創建默認容量的空表，構造方法重載 this(64); /調用本類已聲明的指定參數列表的構造方法 publi

10、c SeqList(T values) /構造順序表，由values數組提供元素，忽略其中空對象 this(values.length*2); /創建2倍values數組容量的空表 /若values=null，用空對象調用方法，Java拋出空對象異常NullPointerException for (int i=0; i=0 & i=0 & ithis.n) this.elementi = x; else throw new java.lang.IndexOutOfBoundsException(i+);/拋出序號越界異常 public int insert(int i, T x) /插入x作

11、為第i個元素 if (x=null) throw new NullPointerException(x=null); /拋出空對象異常 if (ithis.n) i=this.n; /插入在最后 Object source = this.element; /數組變量引用賦值，source也引用element數組 if (this.n=element.length) /若數組滿，則擴充順序表的數組容量 this.element = new Objectsource.length*2; /重新申請一個容量更大的數組 for (int j=0; j=i; j-) /從i開始至表尾的元素向后移動，次序

12、從后向前 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個元素并返回被刪除對象 if (this.n0 & i=0 & ithis.n) T old = (T)this.elementi; /old中存儲被刪除元素 for (int j=i; jthis.n-1; j+) this.elementj = thi

13、s.elementj+1; /元素前移一個位置 this.elementthis.n-1=null; /設置數組元素對象為空，釋放原引用實例 this.n-; return old; /返回old局部變量引用的對象，傳遞對象引用 return null; public void removeAll() /刪除線性表所有元素 this.n=0; public int search(T key) /查找，返回首次出現的關鍵字為key的元素的位 System.out.print(this.getClass().getName()+.indexOf(+key+)，); for (int i=0; i0

14、) str += this.element0.toString(); /執行T類的toString()方法，運行時多態 for (int i=1; ithis.n; i+) str += , +this.elementi.toString(); /執行T類的toString()方法，運行時多態 return str+) ; public static void main (String args) SeqList list=new SeqList(20); Integer values=10,1,2,3,4,5,6,7,8,9; SeqList list1=new SeqList(values

15、); System.out.print(輸出順序表:); System.out.println(list1.toString(); System.out.println(順序表List是否為空+list.isEmpty()+,List1是否為空+list1.isEmpty(); System.out.println(list的長度+list.length()+,list1的長度+list1.length(); System.out.println(返回list1的第7個元素是:+list1.get(6); System.out.println(重新設置第5個元素為19:); list1.set

16、(4, 19); list1.insert(2, 100); list1.append(20); System.out.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

17、Del public Del(int i,int k) String values=A,b,C,d,e,f,g,h; int n =values.length; for(int j=0;jn;j+) System.out.print(valuesj+ ); System.out.println(); for(int j=i+k;jn;j+) valuesj-k=valuesj; n=n-k; for(int j=0;jn;j+) System.out.print(valuesj+ ); System.out.println(); public static void main(String a

18、rgs) new Del(2,3); b)package ex1;public class Del2 public Del2(int i,int k) String values=A,x,y,y,b,c,h; SeqList list=new SeqList(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

19、) package ex1;public class Merge public Merge() Integer values1=1,3,5,11; SeqList list1=new SeqList(values1); Integer values2=2,4,5,22,23; SeqList list2=new SeqList(values2); SeqList list3=new SeqList(); int i=0,j=0; while(ilist1.length()&jlist2.length() if(list1.get(i)list2.get(j) list3.append(list

20、1.get(i); i+; else list3.append(list2.get(j); j+; while(ilist1.length() list3.append(list1.get(i); i+; while(jlist2.length() list3.append(list2.get(j) ; j+; System.out.println(list1.toString(); System.out.println(list2.toString(); System.out.println(list3.toString(); public static void main(String a

21、rgs) 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 list1=new SeqList(values1); Integer values2=2,4,5,12,19,20,22,23,; SeqList list2=new SeqList(values2); SeqList list3=new SeqList(); int i=0,j=0; while

22、(ilist1.length()&jlist2.length() if(list1.get(i)list2.get(j) j+; else list3.append(list1.get(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 cl

23、ass Josephus public Josephus(int n, int k, int m) System.out.println(Josephus(+n+,+k+,+m+)，); SeqList list = new SeqList(n); /創建順序表實例，元素類型是數字字符，只能排到n=9,否則達不到效果 for (int i=0; i1) /多于一個元素時循環，計數O(1) i = (i+m-1) % list.length(); /按循環方式對順序表進行遍歷,圓桌循環 System.out.print(出列+list.remove(i).toString()+，); /刪除i位

24、置對象，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 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+,+

25、m+)，); SeqList list = new SeqList(n); /創建順序表實例，元素類型是數字字符，只能排到n=9,否則達不到效果 for (int i=0; i1) /多于一個元素時循環，計數O(1) i = (i+m-1) % list.length(); /按循環方式對順序表進行遍歷,圓桌循環 System.out.print(出列+list.remove(i).toString()+，); /刪除i位置對象，O(n) / System.out.println(list.toString(); System.out.println(出列+list.get(0).toStri

26、ng();/get(0)獲得元素，O(1) public static void main(String args) new JosephusA(15,2,9); 第二部分：（4）、package ex2;public class Node public T data;/數據域public Node next;/地址域，后繼結點/構造結點public Node(T data,Node next)this.data =data;this.next=next;/構造空結點public Node()this(null,null);/描述字符串public String toString()retur

27、n this.data.toString();package ex2;public class SinglyList public Nodehead;/構造空單鏈表public SinglyList()head=new Node();/構造單鏈表，由values數組數組提供元素public SinglyList(T values)this();Noderear=this.head;for(int i=0;ivalues.length ;i+)rear.next=new Node(valuesi,null);rear=rear.next;public boolean isEmpty() /判斷線

28、性表是否空return this.head.next =null; public T get(int i) /返回第i（i0）個元素 Nodep=head.next ; for(int j=0;p!=null&j=0) ? p.data:null; public void set(int i, T x) /設置第i個元素值為x if(x=null) throw new NullPointerException(x=null); /拋出空對象異常 Nodep=this.head.next;/0 for(int j=0;p!=null&j0&p!=null) p.data=x; public in

29、t size() /返回線性表長度 int i=0;for(Nodep=this.head.next;p!=null;p=p.next)i+; return i; public Node insert(int i, T x) /插入x作為第i個元素 if(x=null) throw new NullPointerException(x=null); Nodefront=this.head ;/指定頭結點 for(int j=0;front.next!=null&ji;j+) front=front.next;/以此循環找i-1 front.next=new Node(x,front.next

30、); return front.next; public Node insert(T x) if (x=null) throw new NullPointerException(x=null); /拋出空對象異常 Node front=this.head; /front指向頭結點 for (; front.next!=null;) /尋找第i-1個或最后一個結點（front指向） front = front.next; front.next = new Node(x, front.next); /在front之后插入值為x結點，包括頭插入、中間/尾插入 return front.next; p

31、ublic T remove(int i) /刪除第i個元素并返回被刪除對象 Nodep=this.head;/讓p指向頭結點 for(int j=0;ji&p.next!=null;j+) p=p.next; if(p.next!=null) T old=p.next.data ; p.next=p.next.next; return old; return null; public void removeAll() /刪除線性表所有元素 this.head.next=null;/讓頭結點直接為空 public Node search(T key) /查找，返回首次出現的關鍵字為key元素

32、for(Node p =this.head;p.next!=null;p=p.next) if( key.equals(p.data) return p; return null; public String toString() /返回順序表所有元素的描述字符串，形式為“（，）” String str=this.getClass().getName()+(; /返回類名 for (Node p=this.head.next; p!=null; p=p.next)/p遍歷單鏈表 str += p.data.toString(); if (p.next!=null) str += ,; /不是最

33、后一個結點時，加分隔符 return str+); （5）、package ex2;public class SortedSinglyListT extends Comparable extends SinglyList/構造空排序單鏈表public SortedSinglyList()super();/默認調用父類構造方法SinglyList()public SortedSinglyList(SinglyList list) super(); /構造空單鏈表 for (Node p=list.head.next; p!=null; p=p.next)/直接插入排序，每趟插入1個元素 this

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