《數(shù)據(jù)結(jié)構(gòu)》 (java版) 課件 牛小飛 4 線性表

4線性表本章內(nèi)容線性表的定義線性表的數(shù)組描述線性表的鏈?zhǔn)矫枋鼍€性表線性表(linearlist，list)是有限的數(shù)據(jù)集合，數(shù)據(jù)之間有線性次序關(guān)系。即線性表是一個(gè)數(shù)據(jù)序列：a0，a1，…，an-1線性表的長度是數(shù)據(jù)的個(gè)數(shù)長度為0的線性表叫做空表根據(jù)數(shù)據(jù)在線性表的位置，賦予數(shù)據(jù)唯一的編號(Index)，長度為n的線性表的數(shù)據(jù)編號為0、1、…、n–1對

ai而言，i≠0，1，ai-1是前驅(qū)(Predecessor

)，ai+1是后繼(Successor

)稱a0為表頭(Head)，an-1為表尾(Tail)線性表線性表的圖示形式：線性表是從實(shí)際應(yīng)用抽象出來的數(shù)據(jù)結(jié)構(gòu):上體育課時(shí)排成的隊(duì)列、根據(jù)下單時(shí)間形成的訂單序列、根據(jù)學(xué)號大小編排的學(xué)生花名冊等。線性表的操作線性表有若干操作：addremove...add操作向線性表增加編號為i的數(shù)據(jù)：a0，a1，…，ai-1，ai，…，an-1

?a0，a1，…，ai-1，a'i，a'i+1，…，a'n其中，a'i=x，a'i+1=ai，…，a'n=an-1add操作后，線性表的長度由n變?yōu)閚+1

add(c，1)remove操作從線性表刪除編號為i的數(shù)據(jù)：a0，a1，…，ai-1，ai，…，an-1

?a0

，a1，…，ai-1，a'i，a'i+1，…，a'n-2其中，a'i=ai+1，a'i+1=ai+2，…，a'n-2=an-1，

remove操作后，線性表的長度由n變?yōu)閚-1

remove(1)packagelist;public

interfaceIList<T>{

intsize();

voidclear();

booleanisEmpty(); Tget(int

index); Tset(int

index,Tx);

voidadd(int

index,Tx); Tremove(int

index);

intindexOf(Tx);

Iterator<T>iterator();

}抽象數(shù)據(jù)類型線性表是一個(gè)抽象數(shù)據(jù)類型，由IList接口定義。線性表的實(shí)現(xiàn)需要解決三個(gè)問題：如何存放數(shù)據(jù)如何存放數(shù)據(jù)之間的關(guān)系如何高效的實(shí)現(xiàn)操作數(shù)組描述數(shù)組元素存放數(shù)據(jù)，數(shù)據(jù)的索引號和數(shù)組元素下標(biāo)一一對應(yīng)數(shù)組元素的相鄰關(guān)系表示數(shù)據(jù)的前后關(guān)系數(shù)組是引用型數(shù)組：Object[]數(shù)組描述線性表：A，B，C，D簡明畫法：CArrayListCArrayList是使用數(shù)組描述實(shí)現(xiàn)的線性表。public

classCArrayList<T>implementsIList<T>,Iterable<T>,RandomAccess,Cloneable{

privateObject[]elements;//存儲數(shù)據(jù)的數(shù)組

private

int

size;//數(shù)據(jù)個(gè)數(shù)

publicCArrayList(int

maxSize){//空表

elements=newObject[maxSize];

//size=0; }CArrayList的對象CArrayList<Integer>sl=newCArrayList<>(6);Object[]

elementsintsize：0length6...componentTypeObject∧∧CArrayList的對象簡明畫法：Object[]

elementsintsize：0∧∧∧∧∧∧索引號的合法性檢查很多操作都涉及索引號，為了保證代碼的健壯性，需要對輸入的索引號進(jìn)行合法性檢查

private

voidrangeCheckForAdd(int

index){//add用

if(index<0||index>size)

throw

newIndexOutOfBoundsException(String.valueOf(index)); }

private

voidrangeCheck(int

index){//其它方法用

if(index<0||index>=size)

throw

newIndexOutOfBoundsException(String.valueOf(index)); }

public

intsize(){

return

size; }sizesize方法返回線性表的長度(數(shù)據(jù)個(gè)數(shù))

public

booleanisEmpty(){

return

size==0; }isEmptyCArrayList從IList接口繼承了isEmpty方法，這里進(jìn)行了覆蓋。也可以不覆蓋。如果線性表為空表，isEmpty方法返回false，否則返回true。

default

booleanisEmpty(){

return

size()==0; }Tget(intindex)get方法返回編號為index的數(shù)據(jù)。

@SuppressWarnings("unchecked")

publicTget(int

index){ rangeCheck(index);

return(T)elements[index]; }Tset(intindex)set方法修改編號為index的數(shù)據(jù)，并返回修改前的數(shù)據(jù)。

@SuppressWarnings("unchecked")

publicTset(int

index,Tx){ rangeCheck(index); TOldValue=(T)elements[index];

elements[index]=x;

return

OldValue; }voidadd(intindex，Tx)add方法向線性表加入數(shù)據(jù)x，編號為index。add造成結(jié)構(gòu)改變：某些數(shù)據(jù)的先驅(qū)和后繼發(fā)生了變化。(a0,a1,...,aindex-1,aindex,aindex+1,...)(a0,a1,...,aindex-1,

x,

aindex+1,aindex+2,...)錯誤的做法a0a1a2a3a4a5例如，在位置2插入數(shù)據(jù)x。elements[2]=x;a0a1

a3a4a5x向后復(fù)制數(shù)據(jù)a0a1

a2

a2a3a4a5a0a1a2a3a4a5在位置2插入數(shù)據(jù)x。向后復(fù)制數(shù)據(jù)a0a1

a2

a2a3a4a5a0a1a2a3a4a5e[0]e[1]e[2]e[3]e[4]e[5]e[6]e[0]e[1]e[2]e[3]e[4]e[5]e[6]e[6]=e[5]e[5]=e[4]e[4]=e[3]e[3]=e[2]e[k]

=e[k-1]k

=

size，...，index+1向后復(fù)制數(shù)據(jù)

private

voidmoveBackward(int

index){

for(int

i=size;i>index;--i)

elements[i]=elements[i-1]; }voidadd(intindex，Tx)判斷index的合法性判斷表是不是已滿向后復(fù)制，騰出空間賦值++sizevoidadd(intindex，Tx)

public

voidadd(int

index,Tx){ rangeCheckForAdd(index); ensureCapacity(size+1);//確保有空間存放x

//moveBackward(index); System.arraycopy(elements,index,

elements,index+1,size-index);

elements[index]=x; ++size; }

public

static

native

voidarraycopy(Objectsrc,int

srcPos,Objectdest,int

destPos,

int

length);src：sourcedest:destinationsrcPosdestPos

srcPos+length-1System類的arraycopy方法Tremove(intindex)remove方法從線性表刪除編號為index的數(shù)據(jù)，并返回這個(gè)數(shù)據(jù)。remove造成結(jié)構(gòu)改變：某些數(shù)據(jù)的先驅(qū)和后繼發(fā)生了變化。(a0,a1,...,aindex-1,aindex,aindex+1,...)(a0,a1,...,aindex-1,aindex+1,...)錯誤的做法刪除位置2的數(shù)據(jù)a0a1a2

a3a4a5a0a1∧

a3a4a5∧∧∧∧∧∧∧∧向前復(fù)制數(shù)據(jù)刪除位置2的元素a0a1a3

a4

a5

a5a0a1a2a3

a4

a5

∧∧∧∧∧∧∧∧向前復(fù)制數(shù)據(jù)

private

voidmoveForward(int

index){

for(int

i=index;i<size;++i)

elements[i]=elements[i+1]; }Tremove(intindex)判斷下標(biāo)的合法性向前移動(覆蓋被刪除的數(shù)據(jù)元素)--sizeTremove(intindex)

@SuppressWarnings("unchecked")

publicTremove(int

index){ rangeCheck(index); Tvalue=(T)elements[index];

//moveForward(index); System.arraycopy(elements,index+1,

elements,index,size-index-1);

elements[--size]=null;//防止內(nèi)存泄漏

return

value; }intindexOf(Tx)給定一個(gè)值，輸出這個(gè)值在線性表的位置。順序查找算法：位置0到size-1的數(shù)據(jù)元素逐一與x比較，如果有相等的數(shù)據(jù)，則返回它所在的位置；如果所有的數(shù)據(jù)都不等于x，則返回-1。a0a1a2a3...asize-1∧...∧0123...size-1length-1intindexOf(Tx)

public

intindexOf(Tx){

for(int

i=0;i<size;i++){

if(elements[i].equals(x))

return

i;

//必須調(diào)用equals,不能elements[i]==x }

return-1; }xelements[i]

clear刪除所有的數(shù)據(jù)，使線性表成為空表。a0a1a2a3...asize-1∧...∧0123...size-1length-1voidclear()

public

voidclear(){

size=0; }空表：size=0Object[]

elementsintsize：0a0a1a2a3...asize-1∧...∧0123...size-1length-1錯誤的做法

public

voidclear(){

for(int

i=0;i<size;i++)

elements[i]=null;//防止內(nèi)存泄漏

size=0; }Object[]

elementsintsize：0∧∧∧∧...∧∧...∧0123...size-1length-1voidclear()a0a1a2a3a4a5a0a1a2a3a4a5∧∧∧原有的數(shù)組滿了生成新的的數(shù)組，并復(fù)制原數(shù)組的數(shù)據(jù)。例如，將原數(shù)組a擴(kuò)大為a的1.5倍：Arrays.copyOf(a,a.length+a.length/2)由數(shù)組a生成一個(gè)新數(shù)組，新數(shù)組的前l(fā)ength個(gè)數(shù)組元素復(fù)制于a，其它的數(shù)組元素=null。擴(kuò)充容量

private

voidensureCapacity(int

minCapacity){

//overflow-consciouscode

if(minCapacity-elements.length>0)grow(minCapacity);}

private

voidensureCapacity(int

minCapacity){

if(minCapacity>elements.length)//有溢出則錯誤grow(minCapacity);}擴(kuò)充容量有問題的寫法：如果a>0，并且a的值=Byte.MAX_VALUE，則a+1<0如果a<0，并且a的值=Byte.MIN_VALUE，則a-1>0byte的范圍-128～1270-12812701127-128-127-12-2+-128129255254溢出public

classTest{

public

static

voidmain(String[]args){ System.out.println(Byte.MAX_VALUE); System.out.println((byte)(Byte.MAX_VALUE+1)); System.out.println((byte)(Byte.MAX_VALUE+3)); System.out.println();

System.out.println(Byte.MIN_VALUE); System.out.println((byte)(Byte.MIN_VALUE-1)); System.out.println((byte)(Byte.MIN_VALUE-3)); }}127-128-126-128127125溢出

private

static

final

int

MAX_ARRAY_SIZE=Integer.MAX_VALUE-8;

private

voidgrow(int

minCapacity){

//overflow-consciouscode

int

oldCapacity=elements.length;

int

newCapacity=oldCapacity+(oldCapacity>>1);

if(newCapacity-minCapacity<0)

newCapacity=minCapacity;

if(newCapacity-MAX_ARRAY_SIZE>0)

newCapacity=hugeCapacity(minCapacity);

elements=Arrays.copyOf(elements,newCapacity); }擴(kuò)充容量

private

static

inthugeCapacity(int

minCapacity){

if(minCapacity<0)//overflow

throw

newOutOfMemoryError();

return(minCapacity>MAX_ARRAY_SIZE)?Integer.MAX_VALUE:

MAX_ARRAY_SIZE;}擴(kuò)充容量擴(kuò)充容量代碼參考了Java類庫問題的規(guī)模：線性表的數(shù)據(jù)個(gè)數(shù):size，記為n。size()、isEmpty()、get(intindex):O(1)算法復(fù)雜性分析

位置012......n-

1n次數(shù)nn-1

1

0平均次數(shù)（等概率）：(1/(n+1))*(n+n-1+...+1+0)=n/2，即O(n)add(intindex,Tx):主要操作是復(fù)制，復(fù)制次數(shù)n-index

最少復(fù)制次數(shù)？最多復(fù)制次數(shù)？算法復(fù)雜性分析remove(intindex):復(fù)制次數(shù)n-index-1最少復(fù)制次數(shù)？最多復(fù)制次數(shù)？

位置0

1

2...n

-

2n

-

1次數(shù)n

-

1n

-2...1

0平均次數(shù)（等概率）：(1/n)*(n-1+...+1+0)=(n-1)/2，即O(n)算法復(fù)雜性分析indexOf(Tx):主要操作是比較操作。查找成功：最少比較次數(shù)？最多比較次數(shù)？

位置012......n-2n-1次數(shù)12n-1n平均次數(shù)（等概率）：(1/n)*(n+...+1)=(n+1)/2，即O(n)查找失?。簩θ魏尾辉诰€性表的x，都需要比較n次，即O(n)算法復(fù)雜性分析擴(kuò)充容量:除了需要new新對象外，主要操作是復(fù)制原有的數(shù)據(jù)，需要復(fù)制n個(gè)數(shù)據(jù)，O(n)算法復(fù)雜性分析

publicIterator<T>iterator(){

return

newItr(); }

private

classItrimplementsIterator<T>{//內(nèi)部類

private

int

cursor;//下一個(gè)數(shù)據(jù)的下標(biāo)

//publicItr(){

//curPos=0;

//}

public

booleanhasNext(){

return

cursor!=size; }

@SuppressWarnings("unchecked")

publicTnext(){

return(T)elements[cursor++]; } }實(shí)現(xiàn)Iterable接口迭代器提供對線性表的遍歷，即一個(gè)不多一個(gè)不少的給出線性表的數(shù)據(jù)intcursorObject[]

elementsintsizelength6...componentTypeObject[]實(shí)現(xiàn)Iterable接口

for(inti=0;i<sl.size();i++) System.out.print(sl.get(i)+""); System.out.println();

for(Iterator<Integer>i=sl.iterator();i.hasNext();) System.out.print(i.next()+""); System.out.println();

for(Integerele:sl) System.out.print(ele+""); System.out.println();

sl.forEach(System.out::print);實(shí)現(xiàn)了Iterable接口，可以使用如下的方式讀取所有的數(shù)據(jù):實(shí)現(xiàn)Iterable接口importjava.util.RandomAccess;public

classCArrayList<T>implementsIlist<T>,

RandomAccess{ //未實(shí)現(xiàn)了RandomAccess接口，用以下的方法

for(Iterator<Integer>i=sl.iterator();i.hasNext();) System.out.print(i.next()+""); System.out.println(); //實(shí)現(xiàn)了RandomAccess接口，用以下的方法

for(int

i=0;i<sl.size();i++) System.out.print(sl.get(i)); System.out.println();實(shí)現(xiàn)RandomAccess接口 publicstaticvoidmain(String[]args){ CArrayList<Integer>sl=newCArrayList<>(); sl.add(0,1); sl.add(0,2); sl.add(0,3); System.out.println(sl);StringtoString()list.CArrayList@23651e3f

publicStringtoString(){

returngetClass().getName()+"@"+Integer.toHexString(hashCode());}Object類有成員方法：Object的子類可以覆蓋該方法，方便調(diào)試。

publicStringtoString(){ Stringstr=getClass().getName()+":";

for(int

i=0;i<size;i++)

str+=elements[i]+"";

return

str; }StringtoString() publicstaticvoidmain(String[]args){ CArrayList<Integer>sl=newCArrayList<>(); sl.add(0,1); sl.add(0,2); sl.add(0,3); System.out.println(sl);list.CArrayList:3

2

1

StringtoString()

protected

nativeObjectclone()throwsCloneNotSupportedException;Object類有成員方法：Objectclone()如果不覆蓋clone方法而直接調(diào)用，則拋出異常。

@SuppressWarnings("unchecked")

publicObjectclone(){

try{CArrayList<T>v=(CArrayList<T>)super.clone();

return

v;}catch(CloneNotSupportedExceptione){

//thisshouldn'thappen,sinceweareCloneable

throw

newInternalError(e);}}public

classCArrayList<T>implementsIlist<T>,RandomAccess,Cloneable{Objectclone()clone方法采用“淺度”復(fù)制策略，生成一個(gè)新對象，新對象的各字段(成員變量)的值和母體相同。100Hello100HellocloneObjectclone()……elementssizeelementssizeObjectclone()

@SuppressWarnings("unchecked")

publicObjectclone(){

try{CArrayList<T>v=(CArrayList<T>)super.clone();

v.elements=Arrays.copyOf(elements,elements.length);

return

v;}catch(CloneNotSupportedExceptione){

//thisshouldn'thappen,sinceweareCloneable

throw

newInternalError(e);}}public

classCArrayList<T>implementsIlist<T>,RandomAccess,Cloneable{Objectclone()……elementssizeelementssizeObjectclone()……

public

booleanequals(Objectobj){

return(this==obj);}默認(rèn)的equals判斷是不是引用了同一個(gè)對象，引用了同一個(gè)對象當(dāng)然相等。equals方法Object類有equals方法，該方法用于比較兩個(gè)引用變量引用的對象是否相等

public

static

booleanequals(Object[]a,Object[]a2){

if(a==a2)

return

true;

if(a==null||a2==null)

return

false;

int

length=a.length;

if(a2.length!=length)

return

false;

for(int

i=0;i<length;i++){Objecto1=a[i];Objecto2=a2[i];

if(!(o1==null?o2==null:o1.equals(o2)))

return

false;}

return

true;}Arrays.equals兩個(gè)數(shù)組相等的定義：

@SuppressWarnings("unchecked")

public

booleanequals(Objectobj){

if(obj==null)

return

false;

if(this==obj)

return

true;

if(obj

instanceofCArrayList<?>){//語法要求，不能寫成CArrayList<T> CArrayList<T>rhd=(CArrayList<T>)obj;

if(this.size!=rhd.size)

return

false;

for(int

i=0;i<size;i++){

if(!elements[i].equals(rhd.elements[i]))

return

false; }

return

true; }

return

false; }CArrayList相等的定義數(shù)據(jù)個(gè)數(shù)相同對應(yīng)位置的數(shù)據(jù)相等

public

native

inthashCode();Object類有成員方法：2個(gè)對象相等，它們的hashCode必須相等。2個(gè)對象不相等,它們的hashCode不必不相等。inthashCode()

public

inthashCode(){

returnInteger.hashCode(value);}

public

static

inthashCode(int

value){

return

value;}Integer.hashCode

public

inthashCode(){

int

h=hash;//hash的初值=0

if(h==0&&value.length>0){

char

val[]=value;

for(int

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

h=31*h+val[i];}

hash=h;}

return

h;}String.hashCode

public

static

inthashCode(Objecta[]){

if(a==null)

return0;

int

result=1;

for(Objectelement:a)

result=31*result+(element==null?0:element.hashCode());

return

result;}Arrays.hashCodeCArrayList的hashCode

public

inthashCode(){

returnArrays.hashCode(elements); }java類庫：List、ListIterator接口java.util.ArrayList、java.util.Vector（線程安全）

數(shù)組的下標(biāo)與數(shù)據(jù)的編號一一對應(yīng)動態(tài)擴(kuò)展

算法：向前、向后復(fù)制，順序查找小結(jié)部分代碼參考了java類庫的ArrayList類，向作者表示感謝。致謝主要內(nèi)容Node(結(jié)點(diǎn))類單(向)鏈表：用引用變量表示后繼關(guān)系的線性表實(shí)現(xiàn)方式性能分析帶頭結(jié)點(diǎn)的單(向)鏈表循環(huán)單(向)鏈表雙向鏈表：用引用變量表示前驅(qū)和后繼關(guān)系的線性表實(shí)現(xiàn)方式雙向循環(huán)鏈表Node類privatestaticclassNode<T>{//嵌套類 Tdata; Node<T>next; ...}Node類對象之間的引用關(guān)系∧Node對象簡稱結(jié)點(diǎn)privatestaticclassNode<T>{//嵌套類 Tdata; Node<T>next; ...}線性表的鏈?zhǔn)矫枋鯽0a1a2a3使用結(jié)點(diǎn)存儲(引用)數(shù)據(jù)結(jié)點(diǎn)之間的引用關(guān)系與線性表數(shù)據(jù)之間的先后關(guān)系一致線性表的鏈?zhǔn)矫枋?個(gè)數(shù)據(jù)=>4個(gè)結(jié)點(diǎn)，結(jié)點(diǎn)的字段data引用數(shù)據(jù)對象。若數(shù)據(jù)之間有先后關(guān)系，對應(yīng)的結(jié)點(diǎn)之間有引用關(guān)系。SinglyLinkedList(單向鏈表)：由字段next可找到后繼結(jié)點(diǎn)a0a1a2a3∧結(jié)點(diǎn)的相關(guān)約定結(jié)點(diǎn)的編號：1、2、3結(jié)點(diǎn)的命名：用存儲的數(shù)據(jù)命名，結(jié)點(diǎn)a0、結(jié)點(diǎn)a1。首結(jié)點(diǎn)、尾結(jié)點(diǎn)前驅(qū)結(jié)點(diǎn)、后繼結(jié)點(diǎn)a0a1a2a3∧CLinkedListpublic

classCLinkedList<T>implementsIList<T>,Iterable<T>,Cloneable{ privateNode<T>first; private

int

size;...

private

static

classNode<T>{//嵌套類

Tdata;

Node<T>next;

Node(Tdata,Node<T>next){

this.data=data;

this.next=next; } }}CLinkedList是使用單鏈表實(shí)現(xiàn)的線性表。CLinkedList對象firstNode對象size=3a0a1a2CLinkedList的對象∧firstsize=3a0a1a2∧簡明畫法/* CLinkedList(){

first=null; size=0; }*/構(gòu)造器構(gòu)造器構(gòu)建空表。字段size=0，并且字段first=null判斷線性表是否為空表，判斷size==0，或first==nullfirst=∧size=0p=p.next;Node<T>p=first;pp=p.next;通過字段next可以找到后繼結(jié)點(diǎn)。找后繼結(jié)點(diǎn)first∧a0a1a2p=p.next;

=

∧

p=p.next;Node<T>p=first;pp=p.next;pp形象的表示：p跑向下一個(gè)結(jié)點(diǎn)找后繼結(jié)點(diǎn)first∧a0a1a2p=p.next;pfor(Node<T>p=first;p!=null;p=p.next){

…//

處理數(shù)據(jù)}遍歷鏈表：從頭至尾，依次“訪問”各個(gè)數(shù)據(jù)課堂練習(xí)first∧a0a1a2

private

classItrimplementsIterator<T>{

privateNode<T>cursor;

publicItr(){

cursor=first; }

public

booleanhasNext(){

return

cursor!=null; }

publicTnext(){ Tdata=cursor.data;

cursor=cursor.next;

return

data; } }迭代器first∧a0a1a2

public

intindexOf(Tx){

int

index=0;

for(Node<T>p=first;p!=null;p=p.next{if(p.data.equals(x))//這種表達(dá)方式數(shù)據(jù)不能為null

return

index;

index++ }

return-1; }first∧a0a1a2intindexOf(Tx)

public

intindexOf(Tx){

int

index=0;

for(Node<T>p=first;p!=null;p=p.next){if(x.equals(p.data))//這種表達(dá)方式x不能為null

return

index; ++index; }

return-1; }intindexOf(Tx)

public

intindexOf1(Tx){

if(x==null){

int

index=0;

for(Node<T>p=first;p!=null;p=p.next){

if(p.data==null)

return

index; ++index; } }else{

int

index=0;

for(Node<T>p=first;p!=null;p=p.next){

if(x.equals(p.data))

return

index; ++index; } }

return-1; }x可以是null，數(shù)據(jù)中也可以有nullintindexOf(Tx)first∧a0a1a2Tget(intindex)編號為index的數(shù)據(jù)存儲于第index+1個(gè)結(jié)點(diǎn)。如何找到第index+1個(gè)結(jié)點(diǎn)？index=0:p所指的就是，執(zhí)行0次p=p.nextindex=1:執(zhí)行1次p=p.nextindex=2:執(zhí)行2次p=p.nextp=first需要執(zhí)行index次找后繼結(jié)點(diǎn)的操作：p=p.next。 Node<T>p=first;

for(int

i=0;i<index;i++)

p=p.next;Tget(intindex)first∧a0a1a2循環(huán)結(jié)束后，p引用了第index+1個(gè)結(jié)點(diǎn)，它存儲的是編號為index的數(shù)據(jù)。

publicTget(int

index){ rangeCheck(index); Node<T>p=first;

for(int

i=0;i<index;i++)

p=p.next;

return

p.data; }Tget(intindex) Node<T>p=first;

for(int

i=0;i<index-1;i++)

p=p.next;first∧a0a1a2下面的循環(huán)結(jié)束后：p引用了第幾個(gè)結(jié)點(diǎn)？它是第index+1個(gè)結(jié)點(diǎn)的？課堂練習(xí)abcepqabceqp∧為結(jié)點(diǎn)加入新的后繼結(jié)點(diǎn)∧∧新創(chuàng)建一個(gè)結(jié)點(diǎn)(用q引用它)，將它作為結(jié)點(diǎn)p的后繼結(jié)點(diǎn)：abcepqq.next=p.next;p.next=q;或者：p.next=newNode<T>(e,p.next);

為結(jié)點(diǎn)加入新的后繼結(jié)點(diǎn)∧∧q=new

Node<>(e,null);創(chuàng)建結(jié)點(diǎn)，存儲x。將新結(jié)點(diǎn)加入鏈表，它的前驅(qū)結(jié)點(diǎn)是第index個(gè)結(jié)點(diǎn)，后繼結(jié)點(diǎn)是前驅(qū)結(jié)點(diǎn)的后繼結(jié)點(diǎn)。首先使p引用前驅(qū)結(jié)點(diǎn)，然后利用上面介紹的操作即可。注意：首結(jié)點(diǎn)沒有前驅(qū)結(jié)點(diǎn)，需要特殊處理。voidadd(intindex,Tx)

public

voidadd(int

index,Tx){ rangeCheckForAdd(index);

if(index==0){//沒有前驅(qū)結(jié)點(diǎn):空表或加入的數(shù)據(jù)編號為index

first=newNode<T>(x,first);//加入后作為第1個(gè)結(jié)點(diǎn) }else{ Node<T>p=first;

for(int

i=0;i<index-1;i++)

p=p.next;

p.next=newNode<T>(x,p.next); } ++size; }voidadd(intindex,Tx)acdbq.next=p.next;qpq=p;p=p.next;幫助GC：p.next=null;p.data=null;p刪除結(jié)點(diǎn)的后繼結(jié)點(diǎn)∧刪除結(jié)點(diǎn)p的后繼結(jié)點(diǎn)：找到第index+1個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)利用上面介紹的操作即可。注意：首結(jié)點(diǎn)沒有前驅(qū)結(jié)點(diǎn)，需要特殊處理。Tremove(intindex)

publicTremove(int

index){ rangeCheck(index);//空表會拋異常 Node<T>p=first;

if(index==0){//沒有前驅(qū)結(jié)點(diǎn)

first=first.next; }else{//有前驅(qū)結(jié)點(diǎn)

for(int

i=0;i<index-1;i++)

p=p.next; Node<T>q=p;

p=p.next;

q.next=p.next; }

//p指向待刪除結(jié)點(diǎn) Tvalue=p.data;

p.data=null;//幫助GC

p.next=null; --size;

return

value; }Tremove(intindex)voidclear()first=

public

voidclear(){

while(first!=null){//不斷的刪除第1個(gè)結(jié)點(diǎn) Node<T>q=first;//q引用待刪除的結(jié)點(diǎn)

first=first.next;//下一個(gè)結(jié)點(diǎn)

q.data=null;//幫助GC

q.next=null; }

size=0; }qfirsta0a1a2a0a1a2∧∧Node<T>pre=null;for(Node<T>p=first;p!=null;pre=p,p=p.next){….if(p.data….)}如果是空表，則pre=null，沒有前驅(qū)結(jié)點(diǎn)如果滿足條件的結(jié)點(diǎn)是第1個(gè)結(jié)點(diǎn)，

則pre=null，沒有前驅(qū)結(jié)點(diǎn)prefirsta0a1a2p根據(jù)某條件找前驅(qū)結(jié)點(diǎn)∧ Node<T>p=null;//c的前驅(qū)結(jié)點(diǎn) Node<T>c=first; Node<T>q;//q的后繼結(jié)點(diǎn)

while(c!=null){//可替換成其他條件

q=cur.next;//記住c的后繼結(jié)點(diǎn) …處理c引用的結(jié)點(diǎn)

p=c;//準(zhǔn)備處理下一個(gè)結(jié)點(diǎn)

c=q; }pfirsta0a1a3cqa2注意：表頭(a0)和表尾(a3)結(jié)點(diǎn)的特殊性找前驅(qū)和后繼結(jié)點(diǎn)∧a0a1a2firstsizefirstsize

@SuppressWarnings("unchecked")

privateCLinkedList<T>superClone(){

try{

return

(CLinkedList<T>)super.clone();}catch(CloneNotSupportedExceptione){

throw

newInternalError(e);}}Objectclone()∧

publicObjectclone(){ CLinkedList<T>v=superClone();

if(v.first==null)//空表

return

v;

//復(fù)制this的鏈表，賦予v

v.first=newNode<>(first.data,null);

for(Node<T>p=first.next,q=v.first;p!=null;p=p.next,q=q.next)

q.next=newNode<>(p.data,null);

return

v; } }pfirsta0a1a2qv.firsta0a1a2Objectclone()∧∧∧∧pqpq

public

booleanequals(Objectobj){

if(this==obj)

return

true;

if(obj

instanceofCLinkedList<?>){ CLinkedList<?>rhd=(CLinkedList<?>)obj;

if(this.size!=rhd.size)

return

false;

for(Node<?>p=first,q=rhd.first;p!=null;p=p.next,q=q.next){

if(!p.data.equals(q.data))

return

false; }

return

true; }

return

false; }equalsrhd.first∧b0b1b2first∧a0a1a2pqpppqqqisEmpty:O(1)size:O(1)indexOf:主要操作是找后繼結(jié)點(diǎn)和比較。位置0123n

-

1移動次數(shù)0123n

-

1比較次數(shù)1234n查找成功：最少0次，最多n

-

1次。等概率的平均：O(n)查找不成功：移動n

-

1次，比較n次，O(n)算法復(fù)雜性分析add:主要操作是找后繼結(jié)點(diǎn)，O(n)remove:主要操作是找后繼結(jié)點(diǎn)，O(n)get:主要操作是找后繼結(jié)點(diǎn)，O(n)算法復(fù)雜性分析......01234......length-1順序存儲和鏈?zhǔn)酱鎯Φ膮^(qū)別first∧順序的get和set:O(1)隨機(jī)存??；鏈?zhǔn)降膅et和set:O(n)順序存取add和remove的時(shí)間復(fù)雜度都是O(n)，但：順序的add、remove的主要操作是復(fù)制數(shù)據(jù)：listElem[i]=listElem[i+1]，需要讀、寫內(nèi)存鏈?zhǔn)降腶dd、remove的主要操作是找后繼結(jié)點(diǎn)：

p

=

p.next，需要讀內(nèi)存,寫內(nèi)存，p可以優(yōu)化為使用寄存器，但需要注意內(nèi)存體系結(jié)構(gòu)的影響順序存儲和鏈?zhǔn)酱鎯Φ膮^(qū)別如果要逐一讀取表中的所有數(shù)據(jù)：順序存儲：for+get鏈?zhǔn)酱鎯?使用迭代器順序存儲需要一次申請內(nèi)存，必要時(shí)申請更大的內(nèi)存，適合能預(yù)知數(shù)據(jù)量的場合。鏈?zhǔn)酱鎯χ辉谛枰獣r(shí)申請內(nèi)存，不需要時(shí)釋放內(nèi)存，適合動態(tài)數(shù)據(jù)集(變化較大的數(shù)據(jù)集）但是，需要更多的存儲空間(一個(gè)結(jié)點(diǎn)比一個(gè)數(shù)據(jù)元素占用更大的存儲空間)。順序存儲和鏈?zhǔn)酱鎯Φ膮^(qū)別add和remove需要對編號0做特殊處理，原因是編號為0的結(jié)點(diǎn)沒有前驅(qū)結(jié)點(diǎn)，一種解決方案是增加1個(gè)冗余結(jié)點(diǎn)“頭結(jié)點(diǎn)”，使編號為0的結(jié)點(diǎn)也有前驅(qū)結(jié)點(diǎn)。頭結(jié)點(diǎn)firstfirsta0a1a2注意：頭結(jié)點(diǎn)不存儲數(shù)據(jù)，但也可以根據(jù)需要，存儲特殊的數(shù)據(jù)加入頭結(jié)點(diǎn)的目的是為了解決add和remove方法需要判斷index為0的情形帶頭結(jié)點(diǎn)的單(向)鏈表∧∧public

classLinkedListWithfirstNode<T>implementsIlist<T>{

privateNode<T>first;

int

size; LinkedListWithfirstNode(){

first=newNode<>(null,null);//頭結(jié)點(diǎn) }

private

static

classNode<T>{ Tdata; Node<T>next; Node(Tdata,Node<T>next){

this.data=data;

this.next=next; } }帶頭結(jié)點(diǎn)的單(向)鏈表空表：first∧∧

publicTget(int

index){ rangCheck(index); Node<T>p=first.next;//注意：開始的位置

//index次

for(int

i=0;i<index;i++)

p=p.next;

return

p.data; }get

public

voidadd(int

index,Tx){//對比CLinkedList rangeCheckForAdd(index);

//找前驅(qū)結(jié)點(diǎn) Node<T>p=first;

//注意：開始的位置

for(int

i=0;i<index;i++)

p=p.next;

p.next=newNode<>(x,p.next); ++size; }add

publicTremove(int

index){//對比CLinkedList rangeCheck(index); Node<T>p=first;

//找到index的前驅(qū)

for(int

i=0;i<index;i++)

p=p.next;//循環(huán)結(jié)束后，p引用待刪除結(jié)點(diǎn)的前驅(qū) Node<T>q=p.next;//q引用待刪除結(jié)點(diǎn)

p.next=q.next;//將待刪除結(jié)點(diǎn)從鏈表中移除 Tvalue=q.data;

q.data=null;//幫助GC

q.next=null; --size;

return

value; }removefirst

public

voidclear(){

//不斷刪除first引用結(jié)點(diǎn)的后繼結(jié)點(diǎn)，直到剩下頭結(jié)點(diǎn)

while(first.next!=null){ Node<T>q=first.next;//q引用待刪除結(jié)點(diǎn)

first.next=q.next;//將q引用的結(jié)點(diǎn)從鏈表中移除

q.data=null;//幫助GC

q.next=null; }

size=0; }clear∧a0a1a2firstfirst形式一：帶頭結(jié)點(diǎn)的單(向)循環(huán)鏈表構(gòu)造器：public

classCircularLinkedListWithfirstNode<T>implementsIlist<T>,Cloneable{

privateNode<T>first;

int

size; CircularLinkedListWithfirstNode(){

first=newNode<>(null,null);

first.next=first;//循環(huán) }a0a1a2firstfirst如何實(shí)現(xiàn)遍歷？開始結(jié)點(diǎn)：p=first.next結(jié)束條件：p!=first帶頭結(jié)點(diǎn)的單(向)循環(huán)鏈表a0a1a2tailtail形式二：如何實(shí)現(xiàn)遍歷？開始結(jié)點(diǎn)：p=tail.next.next結(jié)束條件：p!=tail.next帶頭結(jié)點(diǎn)的單(向)循環(huán)鏈表課堂練習(xí)因?yàn)橐髏ail始終引用尾結(jié)點(diǎn)，如果刪除的結(jié)點(diǎn)是尾結(jié)點(diǎn)就需要對此進(jìn)行特殊處理，應(yīng)該如何處理？a0a1a2tail一、作用：方便定位一個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)二、結(jié)點(diǎn)的形式aifirstlasta2a1a0三、鏈表的形式size=3雙向鏈表空表：first=nulllast=null雙向鏈表a0只有1個(gè)結(jié)點(diǎn)：firstlast

private

static

classNode<T>{Tdata;Node<T>next;Node<T>prev;Node(Node<T>prev,Telement,Node<T>next){

this.data=element;

this.next=next;

this.prev=prev;}}課堂練習(xí)給出Node<T>的定義：aipublic

classDoublelyLinkedList<T>implementsIlist<T>,Iterable<T>{ Node<T>first; Node<T>last;

int

size;…}課堂練習(xí)給出DoublelyLinkedList的定義：s.next=p.next;s.prev=p;

p.next=s;