數(shù)據(jù)結(jié)構(gòu)主講人：張靜常州信息職業(yè)技術(shù)學(xué)院2.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)鏈表線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為線性鏈表，簡稱鏈表；常見的鏈表有單鏈表、循環(huán)鏈表和雙向鏈表。引言Introduction存儲一個數(shù)據(jù)元素的存儲單元稱為結(jié)點（Node），一個結(jié)點至少包含兩個部分：結(jié)點（數(shù)據(jù)域，地址域）Part01單鏈表的結(jié)構(gòu)每個結(jié)點只有一個地址域的線性鏈表稱為單鏈表（SinglyLinkedList），結(jié)點結(jié)構(gòu)如下：單鏈表結(jié)點（數(shù)據(jù)域data，后繼結(jié)點地址域next）單鏈表的定義單鏈表有帶頭結(jié)點和不帶頭結(jié)點兩種單鏈表的結(jié)構(gòu)不帶頭結(jié)點單鏈表的插入操作實現(xiàn)兩種單鏈表的區(qū)別objhead…∧datanexts…p在非開始結(jié)點前插入一個新結(jié)點不帶頭結(jié)點單鏈表的插入操作實現(xiàn)兩種單鏈表的區(qū)別objhead…∧datanexts…p在開始結(jié)點前插入一個新結(jié)點帶頭結(jié)點單鏈表的插入操作實現(xiàn)兩種單鏈表的區(qū)別objhead…∧datanextspPart02單鏈表的Java表示public

classNode<T>{//單鏈表結(jié)點類，T是數(shù)據(jù)元素的類型

publicTdata;//數(shù)據(jù)域，存儲數(shù)據(jù)元素

publicNode<T>next;//地址域，引用后續(xù)結(jié)點

publicNode(Tdata,Node<T>next){//由指定的兩個域來構(gòu)造結(jié)點

this.data=data;

this.next=next;}

publicNode(){//空構(gòu)造

this(null,null);}

publicStringtoString(){

return

this.data.toString();//返回結(jié)點數(shù)據(jù)域的描述字符串}}單鏈表結(jié)點類單鏈表的Java表示public

classSinglyLinkedList<T>implementsLinearList<T>{

publicNode<T>head;//單鏈表的頭指針，指向頭結(jié)點

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

head=newNode<T>();//創(chuàng)建頭結(jié)點，data和next的值均為null} //實現(xiàn)接口方法，具體代碼在2.3.3節(jié)介紹

publicTget(int

i){ … }

public

voidset(int

i,Tt){ … }

public

intinsert(Tt){… }

public

intinsert(int

i,Tt){… }

publicTremove(int

i){ … }

public

booleancontains(Tkey){… }

public

intindexOf(Tkey){… }

public

intsize(){ … }

public

voidclear(){ … }

public

booleanisEmpty(){… }

public

voidprintList(){ … }}單鏈表類單鏈表的Java表示Part03單鏈表的基本操作1.尾插法創(chuàng)建單鏈表單鏈表的基本操作headrear（1）創(chuàng)建只有頭結(jié)點的單鏈表；（2）將指向尾結(jié)點的指針指向頭結(jié)點；values[0]∧（3）從數(shù)組中讀入數(shù)據(jù)，由數(shù)組中的數(shù)據(jù)生成一個新結(jié)點，將新結(jié)點插入表尾；∧（4）使尾指針指向新的表尾；重復(fù)執(zhí)行（3）~（4），直到數(shù)組中所有數(shù)據(jù)均插入鏈表。1.尾插法創(chuàng)建單鏈表單鏈表的基本操作publicSinglyLinkedList(T[]values){//構(gòu)造單鏈表，由數(shù)組提供元素

this();//創(chuàng)建只有頭結(jié)點的單鏈表Node<T>rear=this.head;//rear指向單鏈表的尾結(jié)點

for(int

i=0;i<values.length;i++){

rear.next=newNode<T>(values[i],null);

//尾插法，創(chuàng)建結(jié)點鏈接入rear結(jié)點之后

rear=rear.next;//rear指向新的尾結(jié)點}}2.存取操作單鏈表的基本操作

獲取值設(shè)置值

3.求表長、清空、判斷表空單鏈表的基本操作public

intsize(){//返回單鏈表的長度int

n=0;Nodep=this.head.next;

while(p!=null){

n++;p=p.next;}

return

n;}求表長//清空單鏈表public

voidclear(){

this.head.next=null; }//判斷單鏈表是否為空

public

booleanisEmpty(){return

this.head.next==null;}清空判斷表空4.遍歷單鏈表單鏈表的基本操作public

voidprintList(){//遍歷單鏈表Nodep=this.head.next;

while(p!=null){System.out.println(p.data);//輸出結(jié)點的數(shù)據(jù)域

p=p.next;//指針后移一個結(jié)點}}時間復(fù)雜度：O(n)5.單鏈表的查找單鏈表的基本操作//在單鏈表查找首次出現(xiàn)的與key相等元素，返回元素位置，若不存在返回-1public

intindexOf(Tkey){int

i=0; Nodep=this.head.next;for(;p!=null;p=p.next){//遍歷單鏈表if(p.data.equals(key)){

return

i;}

i++;}

return-1;}//判斷單鏈表中是否包含key元素public

booleancontains(Tkey){ Nodep=this.head.next;for(;p!=null;p=p.next){//遍歷單鏈表

if(p.data.equals(key)){

return

true;} }

return

false; }時間復(fù)雜度：O(n)6.單鏈表的插入單鏈表的基本操作head…∧datanextp…頭結(jié)點

ts（3）使p的地址域引用新結(jié)點s，即p.next=s，最后完成插入并返回i的值。單鏈表的插入-算法實現(xiàn)單鏈表的基本操作時間復(fù)雜度：O(n)

//在順序表的最后插入元素t，返回t序號public

intinsert(Tt){

return

this.insert(this.size(),t);}7.單鏈表的刪除單鏈表的基本操作head…datanextp頭結(jié)點

∧…單鏈表的刪除-算法實現(xiàn)單鏈表的基本操作時間復(fù)雜度：O(n)

用單鏈表實現(xiàn)學(xué)生信息的管理，包括學(xué)生信息的存取、插入、刪除、查找等操作，學(xué)生信息包括：學(xué)號、姓名、成績。提示：定義學(xué)生類Student，重寫equals方法，將單鏈表實現(xiàn)代碼中的泛型T替換成Student。課堂實踐Part04循環(huán)單鏈表循環(huán)鏈表是一種首尾相接的鏈表。將單鏈表中的尾結(jié)點的next域指向head，則整個鏈表成為一個環(huán)，這樣從鏈表中的任意結(jié)點出發(fā)都可找到表中其他的結(jié)點，這樣的單鏈表稱為循環(huán)單鏈表（CircularSinglyLinkedList）。基本概念循環(huán)單鏈表的結(jié)構(gòu)空表：head.next=head循環(huán)單鏈表非空表：rear.next=head循環(huán)單鏈表的基本操作循環(huán)單鏈表帶頭結(jié)點的循環(huán)單鏈表的各種操作的實現(xiàn)算法與帶頭結(jié)點的單鏈表的實現(xiàn)算法類似，只需將相應(yīng)算法中p!=null或p.next!=null改為p!=head或p.next!=headPart05雙向鏈表雙向鏈表的結(jié)點類雙向鏈表給單鏈表的每個結(jié)點再增加一個指向其直接前驅(qū)結(jié)點的引用域prev，這樣鏈表中就有兩條不同方向的鏈，此鏈表稱為雙向鏈表（DoublyLinkedList）。public

classDoubleNode<T>{//雙向鏈表結(jié)點類，T是數(shù)據(jù)元素的類型publicTdata;//數(shù)據(jù)域，存儲數(shù)據(jù)元素publicDoubleNode<T>prev,next;//地址域，prev引用前驅(qū)結(jié)點，next引用后續(xù)結(jié)點publicDoubleNode(Tdata,DoubleNode<T>prev,DoubleNode<T>next){//由指定域值構(gòu)造結(jié)點

this.data=data; this.prev=prev;

this.next=next;}publicDoubleNode(){//空構(gòu)造

this(null,null,null);}publicStringtoString(){

return

this.data.toString();//返回結(jié)點數(shù)據(jù)域的描述字符串}}雙向鏈表的結(jié)構(gòu)雙向鏈表空表：head.next==nullhead.prev==null非空表：p.next.prev==pp.prev.next==p雙向鏈表的基本操作雙向鏈表…pts①②③④…①s.prev=p.prev;②p.prev.next=s;③p.prev=s;④s.next=p;【思考】如果②和③兩步操作次序顛倒，會怎樣？（1）雙向鏈表的