第02章 線性表-Java版課件

第2章線性表2.1線性表抽象數(shù)據(jù)類型2.2線性表的順序表示和實現(xiàn)2.3線性表的鏈式表示和實現(xiàn)2.4線性表的應(yīng)用：多項式的表示及運算第02章線性表-Java版目的和要求目的：實現(xiàn)線性表抽象數(shù)據(jù)類型。內(nèi)容：將線性表的順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu) 實現(xiàn)分別封裝成順序表類、單鏈表類、循環(huán) 雙鏈表類等，比較這兩種實現(xiàn)的特點以及各 種基本操作算法的效率。要求：理解線性表抽象數(shù)據(jù)類型，掌握順序和鏈式 存儲結(jié)構(gòu)實現(xiàn)線性表的方法。重點：順序表、單鏈表、循環(huán)雙鏈表等線性表的設(shè) 計訓(xùn)練。難點：使用指針實現(xiàn)鏈式存儲結(jié)構(gòu)，通過指針操作 改變結(jié)點間的鏈接關(guān)系。實驗：掌握單鏈表的遍歷、插入、刪除、復(fù)制等操 作算法，熟悉循環(huán)單鏈表、雙鏈表和循環(huán)雙 鏈表的結(jié)構(gòu)和基本操作。掌握MyEclipse集 成開發(fā)環(huán)境的程序調(diào)試技術(shù)。第02章線性表-Java版2.1線性表的抽象數(shù)據(jù)類型LinearList=(a0，a1，…，an－1)publicinterfaceLList<T>{ //線性表接口，泛型參數(shù)T表示數(shù)據(jù)元素的數(shù)據(jù)類型booleanisEmpty();//判斷線性表是否空

intlength();//返回線性表長度

Tget(inti);//返回第i（i≥0）個元素

voidset(inti,Tx);//設(shè)置第i個元素值為xvoidinsert(inti,Tx);//插入x作為第i個元素

voidappend(Tx);//在線性表最后插入x元素

Tremove(inti);//刪除第i個元素并返回被刪除對象

voidremoveAll();//刪除線性表所有元素

Tsearch(Tkey);//查找，返回首次出現(xiàn)的關(guān)鍵字為key元素}publicclassSeqList<T>implementsLList<T>//順序表類publicclassSinglyLinkedList<T>implementsLList<T>//單鏈表類第02章線性表-Java版2.2線性表的順序表示和實現(xiàn)線性表的順序存儲結(jié)構(gòu)第02章線性表-Java版publicclassSeqList<T>implementsLList<T>{ //順序表類，實現(xiàn)線性表接口protectedObject[]element;//對象數(shù)組

protectedintlen;//順序表長度，記載元素個數(shù)}2.順序表類第02章線性表-Java版4.順序表的刪除操作3.順序表的插入操作第02章線性表-Java版【例2.1】使用順序表類求解約瑟夫環(huán)問題。第02章線性表-Java版順序表的靜態(tài)特性很好，動態(tài)特性很差，具體說明如下。①順序表元素的物理存儲順序直接反映線性表元素的邏輯順序，順序表是一種隨機存取結(jié)構(gòu)。get()、set()方法時間復(fù)雜度是O(1)。②插入和刪除操作效率很低。如果在各位置插入元素的概率相同，則有5.順序表操作的效率分析第02章線性表-Java版6.順序表的淺拷貝與深拷貝一個類的拷貝構(gòu)造方法聲明格式如下：類(類對象)（1）順序表的淺拷貝publicSeqList(SeqList<T>list)//淺拷貝構(gòu)造方法{this.element=list.element;//數(shù)組引用賦值，兩個變量共用一個數(shù)組，錯誤

this.len=list.len;}第02章線性表-Java版執(zhí)行拷貝構(gòu)造方法SeqList<String>listb=newSeqList<String>(lista);第02章線性表-Java版（2）順序表的深拷貝第02章線性表-Java版7.順序表比較相等兩個順序表相等是指，它們各對應(yīng)元素相等并且長度相同。第02章線性表-Java版2.3線性表的鏈式表示和實現(xiàn)2.3.1線性表的鏈式存儲結(jié)構(gòu)2.3.2單鏈表2.3.3雙鏈表第02章線性表-Java版2.3.1線性表的鏈式存儲結(jié)構(gòu)第02章線性表-Java版單鏈表結(jié)點類publicclassNode<T>//單鏈表結(jié)點類{publicTdata;//數(shù)據(jù)域，保存數(shù)據(jù)元素

publicNode<T>next;//地址域，引用后繼結(jié)點}Node<String>p,q;p=newNode<String>("A",null);q=newNode<String>("B",null);p.next=q;2.3.2單鏈表第02章線性表-Java版2.單鏈表的遍歷操作Node<T>p=head;while(p!=null){System.out.print(p.data.toString()+""); //執(zhí)行訪問p結(jié)點的相關(guān)操作p=p.next;}第02章線性表-Java版如果語句p=p.next寫成p.next=p第02章線性表-Java版3.單鏈表的插入操作

（1）空表插入/頭插入if(head==null) //空表插入head=newNode<T>(x,null);else //頭插入{Node<T>q=newNode<T>(x,null);q.next=head;head=q;}即head=newNode<T>(x,head);第02章線性表-Java版（2）中間插入/尾插入Node<T>q=newNode<T>(x,null);q.next=p.next;//q的后繼結(jié)點應(yīng)是p的原后繼結(jié)點p.next=q;//q作為p的后繼結(jié)點即p.next=newNode<T>(x,p.next);第02章線性表-Java版如果上述后兩條語句次序顛倒，則產(chǎn)生錯誤Node<T>q=newNode<T>(x,null);p.next=q;q.next=p.next;第02章線性表-Java版4.單鏈表的刪除操作頭刪除head=head.next;中間/尾刪除if(p.next!=null)p.next=p.next.next;第02章線性表-Java版5.帶頭結(jié)點的單鏈表第02章線性表-Java版【例2.2】采用單鏈表求解約瑟夫環(huán)問題。第02章線性表-Java版6.單鏈表操作的效率分析isEmpty()方法的時間復(fù)雜度是O(1)。length()方法要遍歷單鏈表，時間復(fù)雜度是O(n)。get(i)和set(i)方法的時間復(fù)雜度是O(n)，不是隨機存取結(jié)構(gòu)。insert(i,x)和remove(i)時間復(fù)雜度是O(n)。第02章線性表-Java版在p結(jié)點之前插入結(jié)點q刪除結(jié)點p要尋找其前驅(qū)結(jié)點front第02章線性表-Java版7.提高單鏈表操作效率的措施publicbooleanappend(Tx){returninsert(this.length(),x); //需遍歷單鏈表兩次，效率較低}returninsert(Integer.MAX_VALUE,x); //遍歷一次第02章線性表-Java版作用于順序表的時間復(fù)雜度是O(n)，但作用于單鏈表的時間復(fù)雜度則是publicStringtoString(){Stringstr="(";if(this.length()!=0){for(inti=0;i<this.length()-1;i++)str+=this.get(i).toString()+",";str+=this.get(this.length()-1).toString();}returnstr+")";}第02章線性表-Java版例2.3求整數(shù)單鏈表的平均值。第02章線性表-Java版【例2.4】單鏈表逆轉(zhuǎn)。第02章線性表-Java版8.單鏈表的淺拷貝與深拷貝publicSinglyLinkedList(SinglyLinkedList<T>list) //拷貝構(gòu)造函數(shù)，淺拷貝{this.head=list.head;//導(dǎo)致兩個引用變量指向同一個結(jié)點}第02章線性表-Java版8.單鏈表的深拷貝第02章線性表-Java版9.單鏈表比較相等兩條單鏈表相等是指，它們各對應(yīng)元素相等并且長度相同。第02章線性表-Java版10.排序單鏈表第02章線性表-Java版11.循環(huán)單鏈表第02章線性表-Java版2.3.3雙鏈表雙鏈表結(jié)構(gòu)p=p.next.pred=p.pred.next第02章線性表-Java版2.雙鏈表的插入和刪除操作插入在p結(jié)點之前插入值為x結(jié)點q=newDLinkNode<T>(x,p.pred,p);p.pred.next=q;p.pred=q;第02章線性表-Java版在p結(jié)點之后插入值為x結(jié)點q=newDLinkNode<T>(x,p,p.next); //當p.next==null時，尾插入if(p.next!=null)p.next.pred=q;//中間插入時執(zhí)行p.next=q;第02章線性表-Java版（2）雙鏈表的刪除操作p.pred.next=p.next;//有p.pred!=nullif(p.next!=null)p.next.pred=p.pred;第02章線性表-Java版3.循環(huán)雙鏈表第02章線性表-Java版4.排序循環(huán)雙鏈表第02章線性表-Java版2.4線性表的應(yīng)用：多項式的表示及運算2.4.1一元多項式的表示及運算2.4.2二元多項式的表示及運算第02章線性表-Java版2.4.1一元多項式的表示及運算第02章線性表-Java版一元多項式的順序存儲結(jié)構(gòu)第02章線性表-Java版

一元多項式的鏈式存儲結(jié)構(gòu)（1）一元多項式的項類（2）多項式單鏈表第02章線性表-Java版（3）多項式類

①多項式類Polynomial聲明及相加運算第02章線性表-Java版【例2.6】一元多項式的表示及相加運算。第02章線性表-Java版②多項式深度拷貝及應(yīng)用第02章線性表-Java版③比較兩個多項式是否相等publicbooleanequals(Objectobj) //比較兩個多項式是否相等{