數(shù)據(jù)結(jié)構(gòu)葉核亞線性表

數(shù)據(jù)結(jié)構(gòu)葉核亞線性表《數(shù)據(jù)結(jié)構(gòu)（Java版）（第2版）》第一頁，共二十五頁，編輯于2023年，星期三《數(shù)據(jù)結(jié)構(gòu)（Java版）（第2版）》第2章線性表2.1線性表的抽象數(shù)據(jù)類型2.2線性表的順序表示和實現(xiàn)2.3線性表的鏈?zhǔn)奖硎竞蛯崿F(xiàn)目的：實現(xiàn)線性表抽象數(shù)據(jù)類型。要求：掌握兩種存儲結(jié)構(gòu)實現(xiàn)線性表。重點：順序表類，單鏈表類。難點：單鏈表，雙鏈表。第二頁，共二十五頁，編輯于2023年，星期三2.1線性表的抽象數(shù)據(jù)類型LinearList=(a0，a1，…，an－1)publicinterfaceLList<E> //線性表接口{

booleanisEmpty();//判斷線性表是否為空intlength();//返回線性表長度

Eget(intindex);//返回序號為index的對象Eset(intindex,Eelement);//設(shè)置序號為index對象為

booleanadd(intindex,Eelement);//在index處插入element對象booleanadd(Eelement);//在順序表最后插入element對象Eremove(intindex);//移去序號為index的對象并返回

voidclear(); //清空線性表}第三頁，共二十五頁，編輯于2023年，星期三2.2線性表的順序表示和實現(xiàn)線性表的順序存儲結(jié)構(gòu)第四頁，共二十五頁，編輯于2023年，星期三2.順序表的插入和刪除操作第五頁，共二十五頁，編輯于2023年，星期三publicclassSeqList<E>implementsLList<E>{//順序表類，實現(xiàn)線性表接口

privateObject[]table;//對象數(shù)組，私有成員

privateintn;//順序表長度}順序表操作的效率分析如果在各位置插入元素的概率相同，則有3.順序表類第六頁，共二十五頁，編輯于2023年，星期三【例2.1】使用順序表類求解約瑟夫環(huán)問題。第七頁，共二十五頁，編輯于2023年，星期三2.3線性表的鏈?zhǔn)奖硎竞蛯崿F(xiàn)2.3.1線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)2.3.2單鏈表2.3.3雙鏈表第八頁，共二十五頁，編輯于2023年，星期三2.3.1線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)第九頁，共二十五頁，編輯于2023年，星期三單鏈表結(jié)點類publicclassNode<E>{//單鏈表結(jié)點類

publicEdata;//數(shù)據(jù)域，保存數(shù)據(jù)元素

publicNode<E>next;//地址域，引用后繼結(jié)點}Node<String>p,q;p=newNode<String>("A");q=newNode<String>("B");p.next=q;2.3.2單鏈表第十頁，共二十五頁，編輯于2023年，星期三2.單鏈表的遍歷操作Node<E>p=head;while(p!=null){訪問p結(jié)點;p=p.next;}第十一頁，共二十五頁，編輯于2023年，星期三3.單鏈表的插入操作第十二頁，共二十五頁，編輯于2023年，星期三4.單鏈表的刪除操作頭刪除head=head.next;中間/尾刪除if(p.next!=null)p.next=p.next.next;第十三頁，共二十五頁，編輯于2023年，星期三5.單鏈表類publicclassSinglyLinkedList<E>implementsLList<E>{ //單鏈表類，實現(xiàn)線性表接口

protectedNode<E>head;//頭指針

publicSinglyLinkedList(){//構(gòu)造空單鏈表

this.head=null;}}（P59）單鏈表操作的效率分析第十四頁，共二十五頁，編輯于2023年，星期三【例2.2】采用單鏈表求解約瑟夫環(huán)問題。第十五頁，共二十五頁，編輯于2023年，星期三7.單鏈表是遞歸結(jié)構(gòu)publicStringtoString(){return"("+this.toString(this.head)+")";}publicStringtoString(Node<E>p){ //遞歸算法

if(p!=null)returnp.data.toString()+","+this.toString(p.next);return"";}第十六頁，共二十五頁，編輯于2023年，星期三【例2.3】單鏈表逆轉(zhuǎn)。第十七頁，共二十五頁，編輯于2023年，星期三8.帶頭結(jié)點的單鏈表【例2.4】建立排序的單鏈表。第十八頁，共二十五頁，編輯于2023年，星期三9.循環(huán)單鏈表第十九頁，共二十五頁，編輯于2023年，星期三2.3.3雙鏈表雙鏈表結(jié)構(gòu)p=p.next.prev=p.prev.next第二十頁，共二十五頁，編輯于2023年，星期三2.雙鏈表的插入和刪除操作(1)插入q=newDLinkNode(x);q.prev=p.prev;q.next=p;p.prev.next=q;p.prev=q;第二十一頁，共二十五頁，編輯于2023年，星期三（2）刪除p.prev.next=p.next;if(p.next!=null)(p.next).prev=p.prev;第二十二頁，共二十五頁，編輯于2023年，星期三3.循環(huán)雙鏈表第二十三頁，共二十五頁，編輯于2023年，星期三4.雙鏈表類publicclassDLinkNode<E>{//雙鏈表結(jié)點類

publicEdata;//數(shù)據(jù)元素publicDLinkNode<E>prev,next; //前驅(qū)、后繼結(jié)點}publicclassCHDoublyLinkedLis