數(shù)據(jù)結構葉核亞線性表《數(shù)據(jù)結構（Java版）（第2版）》第1頁，課件共25頁，創(chuàng)作于2023年2月《數(shù)據(jù)結構（Java版）（第2版）》第2章線性表2.1線性表的抽象數(shù)據(jù)類型2.2線性表的順序表示和實現(xiàn)2.3線性表的鏈式表示和實現(xiàn)目的：實現(xiàn)線性表抽象數(shù)據(jù)類型。要求：掌握兩種存儲結構實現(xiàn)線性表。重點：順序表類，單鏈表類。難點：單鏈表，雙鏈表。第2頁，課件共25頁，創(chuàng)作于2023年2月2.1線性表的抽象數(shù)據(jù)類型LinearList=(a0，a1，…，an－1)publicinterfaceLList<E> //線性表接口{

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

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

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

voidclear(); //清空線性表}第3頁，課件共25頁，創(chuàng)作于2023年2月2.2線性表的順序表示和實現(xiàn)線性表的順序存儲結構第4頁，課件共25頁，創(chuàng)作于2023年2月2.順序表的插入和刪除操作第5頁，課件共25頁，創(chuàng)作于2023年2月publicclassSeqList<E>implementsLList<E>{//順序表類，實現(xiàn)線性表接口

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

privateintn;//順序表長度}順序表操作的效率分析如果在各位置插入元素的概率相同，則有3.順序表類第6頁，課件共25頁，創(chuàng)作于2023年2月【例2.1】使用順序表類求解約瑟夫環(huán)問題。第7頁，課件共25頁，創(chuàng)作于2023年2月2.3線性表的鏈式表示和實現(xiàn)2.3.1線性表的鏈式存儲結構2.3.2單鏈表2.3.3雙鏈表第8頁，課件共25頁，創(chuàng)作于2023年2月2.3.1線性表的鏈式存儲結構第9頁，課件共25頁，創(chuàng)作于2023年2月單鏈表結點類publicclassNode<E>{//單鏈表結點類

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

publicNode<E>next;//地址域，引用后繼結點}Node<String>p,q;p=newNode<String>("A");q=newNode<String>("B");p.next=q;2.3.2單鏈表第10頁，課件共25頁，創(chuàng)作于2023年2月2.單鏈表的遍歷操作Node<E>p=head;while(p!=null){訪問p結點;p=p.next;}第11頁，課件共25頁，創(chuàng)作于2023年2月3.單鏈表的插入操作第12頁，課件共25頁，創(chuàng)作于2023年2月4.單鏈表的刪除操作頭刪除head=head.next;中間/尾刪除if(p.next!=null)p.next=p.next.next;第13頁，課件共25頁，創(chuàng)作于2023年2月5.單鏈表類publicclassSinglyLinkedList<E>implementsLList<E>{ //單鏈表類，實現(xiàn)線性表接口

protectedNode<E>head;//頭指針

publicSinglyLinkedList(){//構造空單鏈表

this.head=null;}}（P59）單鏈表操作的效率分析第14頁，課件共25頁，創(chuàng)作于2023年2月【例2.2】采用單鏈表求解約瑟夫環(huán)問題。第15頁，課件共25頁，創(chuàng)作于2023年2月7.單鏈表是遞歸結構publicStringtoString(){return"("+this.toString(this.head)+")";}publicStringtoString(Node<E>p){ //遞歸算法

if(p!=null)returnp.data.toString()+","+this.toString(p.next);return"";}第16頁，課件共25頁，創(chuàng)作于2023年2月【例2.3】單鏈表逆轉。第17頁，課件共25頁，創(chuàng)作于2023年2月8.帶頭結點的單鏈表【例2.4】建立排序的單鏈表。第18頁，課件共25頁，創(chuàng)作于2023年2月9.循環(huán)單鏈表第19頁，課件共25頁，創(chuàng)作于2023年2月2.3.3雙鏈表雙鏈表結構p=p.next.prev=p.prev.next第20頁，課件共25頁，創(chuàng)作于2023年2月2.雙鏈表的插入和刪除操作(1)插入q=newDLinkNode(x);q.prev=p.prev;q.next=p;p.prev.next=q;p.prev=q;第21頁，課件共25頁，創(chuàng)作于2023年2月（2）刪除p.prev.next=p.next;if(p.next!=null)(p.next).prev=p.prev;第22頁，課件共25頁，創(chuàng)作于2023年2月3.循環(huán)雙鏈表第23頁，課件共25頁，創(chuàng)作于2023年2月4.雙鏈表類publicclassDLinkNode<E>{//雙鏈表結點類

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