完整版信管實驗報告

1、管理學院信管專業(yè)12(1)班學號3112004734姓名鐘臻華協(xié)作者:無教師評定實驗題目線性表的基本操作實驗評分表指導教帥評分標準序號評分項目評分標準滿分打分1完成度按要求獨立完成實驗準備、程序調試、實驗報告撰寫。202實驗內容(1) 完成功能需求分析、存儲結構設計；(2) 程序功能完善、可止常運行；(3) 測試數據正確，分析正確，結論正確。303實驗報告內容齊全，符合要求，文理通順，排版美觀。404總結對實驗過程遇到的問題能初步獨立分析，解決后能總結問題原因及解決方法，有心得體會。10實驗報告1. 實驗目的與要求本實驗通過對線性表各種操作的算法設計，理解和掌握線性表的概念、存儲結構及操作要求

2、，體會順序和鏈式兩種存儲結構的特點；根據操作的不同要求，選擇合適的存儲結構，設計并實現算法，對算法進行時間復雜度分析，從而達到掌握數據結構的研究方法、算法設計和分析方法的目的。1. 實驗內容分別用順序表、單鏈表、單循環(huán)鏈表實現約瑟夫問題的求解，并分析基于不同存儲結構算法的時間復雜度。如果采用順序表實現時，每個元素出環(huán)并不執(zhí)行刪除操作，而將相應位置元素值設置為空，但計數時必須跳過值為空的元素，實現這種算法，并分析執(zhí)行效率。1. 順序表的不刪除出環(huán)元素算法實現publicclassJosephus3(publicJosephus3(intnumber,intstart,intdistance)(/

3、倉U建約瑟夫環(huán)并求角犁，參數指定環(huán)長度,起始位置，計數/采用線性順序表存儲約瑟夫環(huán)的元素，元素類型是字符串，構造方法參數指定順序表的容量SeqList<String>list=newSeqList<String>(number);Stringa=newString("null");for(inti=0;i<number;i+)list.append(char)('A'+i)+"");System.out.print("約瑟夫環(huán)("+number+","+start+&q

4、uot;,"+distance+"),");System.out.println(list.toString();inti=start+distance-1;for(intj=1;j<list.length();j+)(intnum=distance;list.set(i,a);while(num!=0)(i=(i+1)%list.length();if(!list.get(i).equals("null")(num-;System.out.println(list.toString();if(!list.get(j).equals(&q

5、uot;null")System.out.println("被赦免者是"+list.get(j).toString();publicstaticvoidmain(Stringargs)(newJosephus3(5,0,2);運行結果：DjE)(AnullC,nullE)(AnullC,nulIE)SA鎏名號匚JI(inuUBnullJC?mullE)(nullnulljCjnulljE)(nuLljfiuLLjCnulljE(mjlljHullfC,nullj=)(nullnull/C;nullrull)I'rr、(null,nullCnull,null

6、)(nullriullCnull,null)(nulljrnilljCnull,null)(rnjlljnulljCjnulljnuH)(nulLjnulljCjnulLfnull)2. 使用單鏈表實現的算法classJosephus1(publicJosephus1(intnumber,intstart,intdistance)(/倉U建約瑟夫環(huán),參數指定環(huán)長度起始位置，計數/采用單鏈表存儲約瑟夫環(huán)的元素，元素類型是字符串，構造方法參數指定單鏈表的容量SinglyLinkedList<String>list=newSinglyLinkedList<String>(nu

7、mber);for(inti=0;i<number;i+)(list.append(char)('A'+i)+"");/添加字符串對象System.out.print("約瑟夫環(huán)("+number+","+start+","+distance+"),");/輸出約瑟夫環(huán)的環(huán)長度，起始位置，計數System.out.println(list.toString();/輸出單鏈表的描述字符串A,B,C,D,Einti=start;while(list.length()>1)

8、(/多于一個對象時的循環(huán)i=(i+distance-1)%list.length();/計數按循環(huán)規(guī)律變化，單鏈表可以看作是環(huán)形結構(循環(huán)單鏈表)System.out.print("刪除”+list.remove(i)+",");System.out.println(list.toString();System.out.println("被赦免者是"+list.get(0).toString();publicstaticvoidmain(Stringargs)(newJosephus1(5,1,2);蘭*(加SD(A,D)2A")毓站

9、者是n書本例題的約瑟夫環(huán)的算法publicclassJosephus(publicJosephus(intnumber,intstart,intdistance)(SeqList<String>list=newSeqList<String>(number);for(inti=0;i<number;i+)list.append(char)('A'+i)+"");System.out.print("約瑟夫環(huán)("+number+","+start+","+distance+&

10、quot;),");System.out.println(list.toString();inti=start;while(list.length()>1)(i=(i+distance-1)%olist.length();/循環(huán)順序表System.out.print("刪除"+list.remove(i).toString()+",");System.out.println(list.toString();System.out.println("被赦免者是"+list.get(0).toString();publics

11、taticvoidmain(Stringargs)(newJosephus(5,0,2);2. 實現教材P74實驗內容(3)的各成員方法。publicclassSinglyLinkedList<T>implementsLList<T>帶頭結點的單鏈表類，實現線性表接口publicNode<T>head;頭指針,指向單鏈表的頭結點publicSinglyLinkedList(intnumber)/默認構造方法，構造空單鏈表創(chuàng)建頭結點,data和next值均為nullthis.head=newNode<T>();publicSinglyLinkedL

12、ist(Telement,intnumber)/由指定數組中的多個對象構造單鏈表，采用尾插入構造單鏈表this(number);/創(chuàng)建空單鏈表，只有頭結點Node<T>rear=this.head;/rear指向單鏈表最后一個結點for(inti=0;i<element.length;i+)/若element=null,拋出空對象異常/element.length=0時，構造空鏈表rear.next=newNode<T>(elementi,null);/尾插入，創(chuàng)建結點鏈入rear結點之后rear=rear.next;/rear指向新的鏈尾結點/判斷單鏈表是否為空

13、,0(1)publicbooleanisEmpty()(returnthis.head.next=null;以下length。、toString()、get()、set()方法基于單鏈表遍歷算法publicintlength()(inti=0;Node<T>p=this.head.next;/p從單鏈表第一結點開始while(p!=null)(i+;p=p.next;returni;返回單鏈表的所有元素的描述字符串，形式為"(,)”，覆蓋Object類額toString()方法,O(n)publicStringtoString()(Stringstr="(&qu

14、ot;Node<T>p=this.head.next;/p從單鏈表的第一結點開始while(p!=null)(str+=p.data.toString();if(p.next!=null)str+=",”;p=p.next;returnstr+")"publicTget(inti)/返回第i(i>=0)個元素，若i指定序號無效，則返回null返回單鏈表的第i個元素的算法(if(i>=0)(Node<T>p=this.head.next;/p從單鏈表的第一個結點開始頭結點是單鏈表的第一個結點之前的一個特殊的結點，并非單鏈表的第一個

15、結點for(intj=0;p!=null&&j<i;j+)p=p.next;if(p!=null)returnp.data;/p指向第i個結點returnnull;/設置第i(i>=0)個元素值為x,若i指定序號無效則拋出序號越界異常publicvoidset(inti,Tx)(if(x=null)return;/不能設置空對象if(i>=0)(Node<T>p=this.head.next;/p從單鏈表的第一個結點開始for(intj=0;p!=null&&j<i;j+)p=p.next;if(p!=null)p.data=

16、x;/p指向第i個結點elsethrownewIndexOutOfBoundsException(i+"");/拋出序號越界異常以下insert()、appendQB法實現單鏈表插入操作publicvoidinsert(inti,Tx)(/將x對象插入在序號為i結點前，也即插入在序號為i-1結點后,O(n)if(x=null)/不能插入空對象return;/p指向頭結點Node<T>p=this.head;/尋找插入位置頭結點(i=0)for(intj=0;p.next!=null&&j<i;j+)p=p.next;/循環(huán)停止時，p指向第i

17、-1結點或最后一個結點插入x作為p結點的后繼結點，包括頭插入(i<=0)、中間/尾插入(i>0)p.next=newNode<T>(x,p.next);在單鏈表的最后添加對象，O(n)publicvoidappend(Tx)insert(Integer.MAX_VALUE,x);以下remove。、removeAll算法實現單鏈表的刪除操作刪除序號為i的結點，也即刪除序號為i-1的后繼結點，若操作成功,則返回被被刪除的對象，否則返回null,O(n)publicTremove(inti)if(i>=0)Node<T>p=this.head;for(in

18、tj=0;p.next!=null&&j<i;j+)/定位到待刪除結點(i)的前驅結點(i-1)頭結點(i=0)p=p.next;/遍歷算法if(p.next!=null)Told=p.next.data;/嵌得原對象p.next=p.next.next;/刪除p的后繼結點returnold;returnnull;刪除單鏈表的所有元素,java將白動收回各結點的所占用的內存空間publicvoidremoveAll()(this.head=null;查找，返回首次出現的關鍵字為key的元素，方法實現見8.2.1節(jié)publicTsearch(Tkey)(returnkey;

19、/查找算法以下聲明對單鏈表元素進行查找，包含，替換，刪除等方法，以查找算法為基礎publicTsearch_1(Tx)(if(x=null)/關鍵字x不能為空，空則返回nullreturnnull;/順序查找關鍵字為x的元素，返回首次出現的元素，若查找不成功返回nullNode<T>P=this.head.next;/佚結點的下一個結點while(p!=null)if(p.data.equals(x)returnp.data;/返回首次出現的元素returnnull;publicbooleancontain(Tx)(/判斷線性表是否包含關鍵字為x的兀素returnthis.sear

20、ch(x)!=null;/以查找的結果獲得判斷結果刪除單鏈表中指定元素關鍵字x的remove()函數聲明如下，使用順序查找算法但未調用查找算法publicvoidremove(Tx)(/刪除首次出現的值為x的結點，若沒有找到指定結點則不刪除if(this.head.next=null|x=null)/關鍵字x不能為空，且?guī)в蓄^結點的單鏈表不能為空return;Node<T>front=this.head,p=front.next;/p指向頭結點的下一個結點,front指向頭結點while(p!=null&&!p.data.equals(x)(front=p;p=p.

21、next;if(p!=null)front.next=p.next;/頭刪除,中間/尾刪除中間刪除publicvoidremoveAll(Tx)(publicvoidreplace(Tx,Ty)(if(this.head.next=null|x=null|y=null)return;publicvoidreplaceAll(Tx,Ty)(x=y;以下聲明按迭代方式遍歷單鏈表的成員方法publicNode<T>getFirst()if(this.head.next=null)returnhead;/單鏈表不能為空returnthis.head.next;/返回單鏈表的第一個結點，非頭

22、結點publicNode<T>getNext(Node<T>p)Node<T>p1=this.head;/p指向頭結點while(p1!=null)p1=p1.next;returnpl.next;publicNode<T>getPrevious(Node<T>p)(Node<T>p1=this.head;while(p1!=null)(p1=p1.next;returnp1;publicNode<T>getLast()Node<T>p=this.head;while(p!=null)for(int

23、j=0;p.next!=null&&j<Integer.MAX_VALUE;j+)/定位于最后一個結點之前的前一個結點p=p.next;returnp.next;以下聲明對單鏈表的子表進行操作的求子表、包含、插入、刪除、替換等方法publicSinglyLinkedList<T>sub(inti,intn)(if(i>=0)(Node<T>p=this.head;for(intj=0;p.next!=null&&j<i;j+)/定位于i-1的結點p=p.next;if(p.next!=null)(Told=p.next.

24、data;returnold;returnnull;for(inti=0;i<n;i+)p=p.next;returnp;publicvoidremove(inti,intn)(if(i>=0)(Node<T>p=this.head;for(intj=0;p.next!=null&&j<i;j+)/定位于i-1的結點if(p.next!=null)(Told=p.next.data;p.next=p.next.next;returnold;returnnull;for(inti=0;i<n;i+)p=p.next;publicvoidinse

25、rt(inti,SinglyLinkedList<T>list)(publicSinglyLinkedList(SinglylinkedList<T>list)(/復制單鏈表所有結點的深拷貝構造方法this();/創(chuàng)建空單鏈表，只有頭結點Node<T>p=this.head.next;Node<T>rear=this.head;while(p!=null)(rear.next=newNode<T>(p.data,null);rear=rear.next;if(SinkedlinkedList=null)return;Node<T>p=this.head;/p指向頭結點for(intj=