完整版信管實(shí)驗(yàn)報(bào)告

1、管理學(xué)院信管專(zhuān)業(yè)12(1)班學(xué)號(hào)3112004734姓名鐘臻華協(xié)作者:無(wú)教師評(píng)定實(shí)驗(yàn)題目線性表的基本操作實(shí)驗(yàn)評(píng)分表指導(dǎo)教帥評(píng)分標(biāo)準(zhǔn)序號(hào)評(píng)分項(xiàng)目評(píng)分標(biāo)準(zhǔn)滿分打分1完成度按要求獨(dú)立完成實(shí)驗(yàn)準(zhǔn)備、程序調(diào)試、實(shí)驗(yàn)報(bào)告撰寫(xiě)。202實(shí)驗(yàn)內(nèi)容(1) 完成功能需求分析、存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)；(2) 程序功能完善、可止常運(yùn)行；(3) 測(cè)試數(shù)據(jù)正確，分析正確，結(jié)論正確。303實(shí)驗(yàn)報(bào)告內(nèi)容齊全，符合要求，文理通順，排版美觀。404總結(jié)對(duì)實(shí)驗(yàn)過(guò)程遇到的問(wèn)題能初步獨(dú)立分析，解決后能總結(jié)問(wèn)題原因及解決方法，有心得體會(huì)。10實(shí)驗(yàn)報(bào)告1. 實(shí)驗(yàn)?zāi)康呐c要求本實(shí)驗(yàn)通過(guò)對(duì)線性表各種操作的算法設(shè)計(jì)，理解和掌握線性表的概念、存儲(chǔ)結(jié)構(gòu)及操作要求

2、，體會(huì)順序和鏈?zhǔn)絻煞N存儲(chǔ)結(jié)構(gòu)的特點(diǎn)；根據(jù)操作的不同要求，選擇合適的存儲(chǔ)結(jié)構(gòu)，設(shè)計(jì)并實(shí)現(xiàn)算法，對(duì)算法進(jìn)行時(shí)間復(fù)雜度分析，從而達(dá)到掌握數(shù)據(jù)結(jié)構(gòu)的研究方法、算法設(shè)計(jì)和分析方法的目的。1. 實(shí)驗(yàn)內(nèi)容分別用順序表、單鏈表、單循環(huán)鏈表實(shí)現(xiàn)約瑟夫問(wèn)題的求解，并分析基于不同存儲(chǔ)結(jié)構(gòu)算法的時(shí)間復(fù)雜度。如果采用順序表實(shí)現(xiàn)時(shí)，每個(gè)元素出環(huán)并不執(zhí)行刪除操作，而將相應(yīng)位置元素值設(shè)置為空，但計(jì)數(shù)時(shí)必須跳過(guò)值為空的元素，實(shí)現(xiàn)這種算法，并分析執(zhí)行效率。1. 順序表的不刪除出環(huán)元素算法實(shí)現(xiàn)publicclassJosephus3(publicJosephus3(intnumber,intstart,intdistance)(/

3、倉(cāng)U建約瑟夫環(huán)并求角犁，參數(shù)指定環(huán)長(zhǎng)度,起始位置，計(jì)數(shù)/采用線性順序表存儲(chǔ)約瑟夫環(huán)的元素，元素類(lèi)型是字符串，構(gòu)造方法參數(shù)指定順序表的容量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);運(yùn)行結(jié)果：DjE)(AnullC,nullE)(AnullC,nulIE)SA鎏名號(hào)匚JI(inuUBnullJC?mullE)(nullnulljCjnulljE)(nuLljfiuLLjCnulljE(mjlljHullfC,nullj=)(nullnull/C;nullrull)I'rr、(null,nullCnull,null

6、)(nullriullCnull,null)(nulljrnilljCnull,null)(rnjlljnulljCjnulljnuH)(nulLjnulljCjnulLfnull)2. 使用單鏈表實(shí)現(xiàn)的算法classJosephus1(publicJosephus1(intnumber,intstart,intdistance)(/倉(cāng)U建約瑟夫環(huán),參數(shù)指定環(huán)長(zhǎng)度起始位置，計(jì)數(shù)/采用單鏈表存儲(chǔ)約瑟夫環(huán)的元素，元素類(lèi)型是字符串，構(gòu)造方法參數(shù)指定單鏈表的容量SinglyLinkedList<String>list=newSinglyLinkedList<String>(nu

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

8、(/多于一個(gè)對(duì)象時(shí)的循環(huán)i=(i+distance-1)%list.length();/計(jì)數(shù)按循環(huán)規(guī)律變化，單鏈表可以看作是環(huán)形結(jié)構(gòu)(循環(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書(shū)本例題的約瑟夫環(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. 實(shí)現(xiàn)教材P74實(shí)驗(yàn)內(nèi)容(3)的各成員方法。publicclassSinglyLinkedList<T>implementsLList<T>帶頭結(jié)點(diǎn)的單鏈表類(lèi)，實(shí)現(xiàn)線性表接口publicNode<T>head;頭指針,指向單鏈表的頭結(jié)點(diǎn)publicSinglyLinkedList(intnumber)/默認(rèn)構(gòu)造方法，構(gòu)造空單鏈表創(chuàng)建頭結(jié)點(diǎn),data和next值均為nullthis.head=newNode<T>();publicSinglyLinkedL

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

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

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

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

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

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

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

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

20、ch(x)!=null;/以查找的結(jié)果獲得判斷結(jié)果刪除單鏈表中指定元素關(guān)鍵字x的remove()函數(shù)聲明如下，使用順序查找算法但未調(diào)用查找算法publicvoidremove(Tx)(/刪除首次出現(xiàn)的值為x的結(jié)點(diǎn)，若沒(méi)有找到指定結(jié)點(diǎn)則不刪除if(this.head.next=null|x=null)/關(guān)鍵字x不能為空，且?guī)в蓄^結(jié)點(diǎn)的單鏈表不能為空return;Node<T>front=this.head,p=front.next;/p指向頭結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn),front指向頭結(jié)點(diǎn)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;/返回單鏈表的第一個(gè)結(jié)點(diǎn)，非頭

22、結(jié)點(diǎn)publicNode<T>getNext(Node<T>p)Node<T>p1=this.head;/p指向頭結(jié)點(diǎn)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+)/定位于最后一個(gè)結(jié)點(diǎn)之前的前一個(gè)結(jié)點(diǎn)p=p.next;returnp.next;以下聲明對(duì)單鏈表的子表進(jìn)行操作的求子表、包含、插入、刪除、替換等方法publicSinglyLinkedList<T>sub(inti,intn)(if(i>=0)(Node<T>p=this.head;for(intj=0;p.next!=null&&j<i;j+)/定位于i-1的結(jié)點(diǎn)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的結(jié)點(diǎn)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)(/復(fù)制單鏈表所有結(jié)點(diǎn)的深拷貝構(gòu)造方法this();/創(chuàng)建空單鏈表，只有頭結(jié)點(diǎn)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指向頭結(jié)點(diǎn)for(intj=