數(shù)據(jù)結(jié)構(gòu)(第二章-線性表)

數(shù)據(jù)結(jié)構(gòu)第2章線性表

線性結(jié)構(gòu)是最常用、最簡單的一種數(shù)據(jù)結(jié)構(gòu)。而線性表是一種典型的線性結(jié)構(gòu)。其基本特點是線性表中的數(shù)據(jù)元素是有序且是有限的。線性結(jié)構(gòu)基本特征：①存在一個唯一的被稱為“第一個”的數(shù)據(jù)元素；②存在一個唯一的被稱為“最后一個”的數(shù)據(jù)元素；③除第一個元素外，每個元素均有唯一一個直接前驅(qū)；④除最后一個元素外，每個元素均有唯一一個直接后繼。線性結(jié)構(gòu)主要內(nèi)容2.1線性表抽象數(shù)據(jù)類型2.2線性表的順序表示和實現(xiàn)2.3線性表的鏈?zhǔn)奖硎竞蛯崿F(xiàn)2.4線性表的應(yīng)用：多項式的表示及運算2.1線性表抽象數(shù)據(jù)類型線性表的定義線性表是指n(n>=0)個類型相同的數(shù)據(jù)元素a0,a1,...an-1組成的有限序列，其一般描述為：LinearList=(a0，a1，…，an－1)。

其中LinearList稱為線性表的名稱每個ai（n-1≥i≥0）稱為線性表的數(shù)據(jù)元素，可以是整數(shù)、浮點數(shù)、字符或類表中相鄰元素之間存在著順序關(guān)系：將ai-1

稱為ai

的前驅(qū)（Predecessor），ai+1

稱為ai

的后繼（Successor）。a0沒有前驅(qū)元素，an-1沒有后繼元素具體n的值稱為線性表中包含有數(shù)據(jù)元素的個數(shù)，也稱為線性表的長度（Length）當(dāng)n的值等于0時，表示該線性表是空表2.1線性表抽象數(shù)據(jù)類型線性表的定義線性表的定義中每個數(shù)據(jù)元素ai的含義在不同情況下各不相同，它們可能是一個字母、一個數(shù)字、也可以是一條記錄等。一般情況下，在線性表中每個ai描述的是一組相同屬性的數(shù)據(jù)，例如：英文字母表（A，B，C，…，Z）是一個長度為26的線性表，其中的每一個字母就是一個數(shù)據(jù)元素某公司2015年每月產(chǎn)值表（400，420，500，…，600，650）(單位：萬元)是一個長度為12的線性表，其中的每一個數(shù)值就是一個數(shù)據(jù)元素在一些復(fù)雜的線性表中，每一個數(shù)據(jù)元素又可以由若干個數(shù)據(jù)項組成，在這種情況下，通常將數(shù)據(jù)元素稱為記錄（record），比如學(xué)生信息記錄線性表的離散（數(shù)學(xué)）定義如下：B=<A,R>,其中A包含n個結(jié)點的集合(a0，a1，…，an－1)，R是關(guān)系的集合 {(ai-1,ai)|i=1,2,..n-1}，可見R只有一種類型的關(guān)系，即線性關(guān)系2.1線性表抽象數(shù)據(jù)類型線性表的定義2.1線性表抽象數(shù)據(jù)類型線性表的特征從線性表的定義可以看出線性表的特征：有且僅有一個開始結(jié)點(表頭結(jié)點)a0，它沒有直接前驅(qū)，只有一個直接后繼;有且僅有一個終端結(jié)點(表尾結(jié)點)an-1，它沒有直接后繼，只有一個直接前驅(qū);其它結(jié)點都有一個直接前驅(qū)和直接后繼；元素之間為一對一的線性關(guān)系。線性表的抽象數(shù)據(jù)類型定義如下：ADT LinearList{數(shù)據(jù)對象:D＝{ai|ai∈元素集合,i=0,1,2,..n-1 n>=1}數(shù)據(jù)關(guān)系:R={<ai-1,ai>|ai-1,ai∈元素集合,i=1,2,..n-1}基本操作：{插入，刪除，查找等}} ADT list2.1線性表抽象數(shù)據(jù)類型線性表的抽象數(shù)據(jù)類型線性表的基本操作求長度：求線性表的數(shù)據(jù)元素個數(shù)。訪問：對線性表中指定位置的數(shù)據(jù)元素進行存取、替換等操作。插入：在線性表指定位置上，插入一個新的數(shù)據(jù)元素，插入后仍為一個線性表。刪除：刪除線性表指定位置的數(shù)據(jù)元素，同時保證更改后的線性表仍然具有線性表的連續(xù)性。復(fù)制：重新復(fù)制一個線性表。合并：將兩個或兩個以上的線性表合并起來，形成一個新的線性表。查找：在線性表中查找滿足某種條件的數(shù)據(jù)元素。排序：對線性表中的數(shù)據(jù)元素按關(guān)鍵字值，以遞增或遞減的次序進行排列。遍歷：按次序訪問線性表中的所有數(shù)據(jù)元素，并且每個數(shù)據(jù)元素恰好訪問一次。2.1線性表抽象數(shù)據(jù)類型線性表的抽象數(shù)據(jù)類型2.1線性表抽象數(shù)據(jù)類型線性表的抽象數(shù)據(jù)類型聲明線性表抽象數(shù)據(jù)類型ADTList<T>//線性表抽象數(shù)據(jù)類型，數(shù)據(jù)元素的數(shù)據(jù)類型為T{booleanisEmpty()//判斷線性表是否為空intsize()//返回線性表長度

Tget(inti)//返回第i個元素

voidset(inti,Tx)//設(shè)置第i個元素為xStringtoString()//所有元素的描述字符串

intinsert(inti,Tx)//插入x作為第i個元素2.1線性表抽象數(shù)據(jù)類型線性表的抽象數(shù)據(jù)類型

intinsert(Tx)//在線性表最后插入x元素Tremove(inti)//刪除第i個元素

voidclear()//刪除所有元素

intsearch(Tkey)//查找與key相等元素booleancontains(Tkey)//判斷是否包含key元素

intinsertDifferent(Tx)//插入不重復(fù)元素

Tremove(Tkey)//刪除與key相等元素

booleanequals(Objectobj)//比較是否相等voidaddAll(List<T>list)//添加list所有元素}2.1線性表抽象數(shù)據(jù)類型線性表的分類線性表有兩種存儲方式，對應(yīng)地把線性表分成了兩類：順序存儲結(jié)構(gòu)的順序表（或稱向量存儲、一維數(shù)組存儲）鏈?zhǔn)酱鎯Y(jié)構(gòu)的鏈表線性表的實現(xiàn)：publicclassSeqList<T>//順序表類publicclassSinglyLinkedList<T>//單鏈表類線性表的存儲結(jié)構(gòu)

2.1線性表抽象數(shù)據(jù)類型線性表的分類2.2線性表的順序存儲和實現(xiàn)線性表的順序存儲結(jié)構(gòu)數(shù)組：是實現(xiàn)順序存儲結(jié)構(gòu)的基礎(chǔ)。數(shù)組（Array）存儲具有相同數(shù)據(jù)類型的元素集合。一維數(shù)組占用一塊內(nèi)存空間，每個存儲單元的地址是連續(xù)的，計算第i個元素地址所需時間復(fù)雜度是一個常量，與元素序號i無關(guān)。存取任何一個元素的時間復(fù)雜度是O(1)的數(shù)據(jù)結(jié)構(gòu)稱為隨機存取結(jié)構(gòu)。因此，數(shù)組是隨機存取結(jié)構(gòu)。2.2線性表的順序存儲和實現(xiàn)線性表的順序存儲結(jié)構(gòu)數(shù)組的特點：通過下標(biāo)識別元素，下標(biāo)是其存儲單元序號，表示元素在數(shù)組中的位置N維數(shù)組有n個下標(biāo)數(shù)組地址和容量不能更改2.2線性表的順序存儲和實現(xiàn)順序表-順序表定義順序存儲方法：即用一組連續(xù)的內(nèi)存單元依次存放線性表中的數(shù)據(jù)元素（元素在內(nèi)存的物理存儲次序與它們在線性表中的邏輯次序相同）在內(nèi)存中開辟一片連續(xù)存儲空間，但該連續(xù)存儲空間的大小要大于或等于順序表的長度，然后讓線性表中第一個元素存放在連續(xù)存儲空間第一個位置，第二個元素緊跟著第一個之后，其余依此類推順序表定義：用順序存儲方法存儲的線性表簡稱為順序表（SequentialList）2.2線性表的順序存儲和實現(xiàn)順序表-順序表定義在程序設(shè)計語言中，通常利用一維數(shù)組來表示順序表的數(shù)據(jù)存儲區(qū)域，這是因為數(shù)組具有如下特點：數(shù)據(jù)中的元素間的地址是連續(xù)的數(shù)組中所有元素的數(shù)據(jù)類型是相同的這與線性表的順序存儲結(jié)構(gòu)(順序表)是類似的考慮：數(shù)組存儲有什么缺點？？？2.2線性表的順序存儲和實現(xiàn)順序表-順序表定義采用一維數(shù)組存儲數(shù)據(jù)元素，數(shù)據(jù)元素在內(nèi)存的物理存儲次序反映了線性表數(shù)據(jù)元素之間的邏輯次序。順序表是隨機存取結(jié)構(gòu)

2.2線性表的順序存儲和實現(xiàn)順序表-順序表定義若定義數(shù)組A[n]={a0，a1，a2，…，an-1}，假設(shè)每一個數(shù)組元素占用d個字節(jié)，則數(shù)組元素A[0]，A[1]，A[2]，…，A[n-1]的地址分別為Loc(A[0])，Loc(A[0])+d，Loc(A[0])+2d，…，Loc(A[0])+（n-1）d。其結(jié)構(gòu)如圖所示：2.2線性表的順序存儲和實現(xiàn)順序表-順序表定義由上可知，數(shù)據(jù)的存儲邏輯位置由數(shù)組的下標(biāo)決定。所以相鄰的元素之間地址的計算公式為（假設(shè)每個數(shù)據(jù)元素占有d個存儲單元）：LOC（ai）=LOC（ai-1）+d對線性表的所有數(shù)據(jù)元素，假設(shè)已知第一個數(shù)據(jù)元素a0的地址為LOC（a0），每個結(jié)點占有d個存儲單元，則第i個數(shù)據(jù)元素ai的地址為：LOC（ai）=LOC（a0）+i*d線性表的第一個數(shù)據(jù)元素的位置通常稱做起始位置或基地址。在使用一維數(shù)組時，數(shù)組的下標(biāo)起始位置根據(jù)給定的問題確定，或者根據(jù)實際的高級語言的規(guī)定確定。2.2線性表的順序存儲和實現(xiàn)順序表-順序表的實現(xiàn)順序表的實現(xiàn)定義:順序表可以直接使用一維數(shù)組描述為：typearrayname[]；//type的類型根據(jù)實際需要確定//該代碼只是對應(yīng)用數(shù)組的聲明，還沒有對該數(shù)組分配空間，因此不能訪問數(shù)組。只有對數(shù)組進行初始化并申請內(nèi)存資源后，才能夠?qū)?shù)組中元素進行使用和訪問arrayname=newtype[arraysize]其作用是給名稱為arrayname的數(shù)組分配arraysize個類型為type大小的空間其中arraysize表示數(shù)組的長度，它可以是整型的常量和變量；如果arraysize是常量，則分配固定大小的空間，如果是變量，則表示根據(jù)參數(shù)動態(tài)分配數(shù)組的空間2.2線性表的順序存儲和實現(xiàn)順序表-順序表的實現(xiàn)書上P18定義的順序表//順序表類，實現(xiàn)ADTList<T>聲明的方法，T表示數(shù)據(jù)元素//的數(shù)據(jù)類型publicclassSeqList<T>extendsObject//順序表類。//publicclassSeqList<T>extendsMyAbstractList<T>（繼承抽象列表類）{

protectedObject[]element;//對象數(shù)組，保護成員

protectedintn;//順序表元素個數(shù)（長度）2.2線性表的順序存儲和實現(xiàn)順序表-順序表的實現(xiàn)P18書上定義的順序表注意：n<=element.length（書上錯誤?。?，順序表元素個數(shù)SeqList<T>類聲明為實現(xiàn)線性表接口ADTList<T>的泛型類，T表示線性表元素的數(shù)據(jù)類型。當(dāng)聲明SeqList類的一個對象并創(chuàng)建實例時，指定泛型參數(shù)T為一個確定的類，如 SeqList<String>list=newSeqList<String>();泛型T的實際參數(shù)必須是類，不能是基本數(shù)據(jù)類型成員變量是保護類型數(shù)據(jù)元素不能是空對象（null）注意回憶理解Java類是引用數(shù)據(jù)類型（與基本數(shù)據(jù)類型相區(qū)別）2.2線性表的順序存儲和實現(xiàn)順序表-順序表的基本操作初始化操作（由構(gòu)造函數(shù)實現(xiàn)）：創(chuàng)建順序表對象為其分配內(nèi)存空間，另外，還需要設(shè)定當(dāng)前順序表的長度算法如下（注意書上P20下對Java語言構(gòu)造函數(shù)的解釋！）

//1.構(gòu)造、存取

publicSeqList(intlength)//構(gòu)造容量為length的空表

{this.element=newObject[length];//申請數(shù)組的存儲空間，元素為null。 //若length<0，Java拋出異常java.lang.NegativeArraySizeExceptionthis.n=0;}publicSeqList()//創(chuàng)建默認容量的空表，構(gòu)造方法重載

{this(64);//調(diào)用本類已聲明的指定參數(shù)列表的構(gòu)造方法

}初始化操作（由構(gòu)造函數(shù)實現(xiàn)）：publicSeqList(T[]values)//構(gòu)造順序表，由values數(shù)組提供元素，忽略其中空對象

{this(values.length);//創(chuàng)建容量為values.length的空表

//若values==null，用空對象調(diào)用方法，Java拋出空對象異常NullPointerExceptionfor(inti=0;i<values.length;i++)//復(fù)制數(shù)組元素，O(n)this.element[i]=values[i];//對象引用賦值

this.n=element.length;//也可this.insert(values[i]);//尾插入，this.n++。暫且不用，因為還沒有講到

//也可for(Tx:values)//數(shù)組逐元循環(huán)//this.insert(x);//尾插入，this.n+1}2.2線性表的順序存儲和實現(xiàn)順序表-順序表的基本操作2.2線性表的順序存儲和實現(xiàn)順序表-順序表的基本操作Stringvalues[]={"A","B","C","D","E"};SeqList<String>lista=newSeqList<String>(values); //lista引用順序表實例，元素是String對象泛型類與創(chuàng)建實例2.2線性表的順序存儲和實現(xiàn)順序表-順序表的基本操作釋放操作（由析構(gòu)函數(shù)實現(xiàn)）： Java類不需要聲明析構(gòu)方法判斷順序表的空與滿： 順序表為空：n=0;

順序表為滿：n>=element.length算法如下：publicbooleanisEmpty()//判斷順序表是否空，若空返回true，O(1){returnthis.n==0;}2.2線性表的順序存儲和實現(xiàn)順序表-順序表的基本操作2.2線性表的順序存儲和實現(xiàn)順序表-順序表的基本操作返回順序表的長度：

n是長度算法如下：publicintsize()//返回順序表元素個數(shù)，O(1){returnthis.n;}2.2線性表的順序存儲和實現(xiàn)順序表-順序表的基本操作獲得（get）順序表的第i個數(shù)據(jù)元素值： 需要注意i的有效性，然后根據(jù)數(shù)組的下標(biāo)從0開始，來考慮到底返回哪一個元素算法如下：//存取操作

publicTget(inti)//返回第i個元素，0≤i<n。若i越界，返回null。O(1){if(i>=0&&i<this.n)return(T)this.element[i];//返回數(shù)組元素引用的對象，傳遞對象引用//returnthis.element[i];編譯錯，Object對象不能返回T對象注意前面的定//義Object[]element;

returnnull;}2.2線性表的順序存儲和實現(xiàn)順序表-順序表的基本操作設(shè)置（set）順序表的第i個數(shù)據(jù)元素值為x： 需要注意x的有效性，考慮如下：

1）如果x已經(jīng)是被賦值的元素，如何處理

2）如果x還沒有被賦值，如何處理

2.2線性表的順序存儲和實現(xiàn)順序表-順序表的基本操作設(shè)置（set）順序表的第i個數(shù)據(jù)元素值：算法如下：//設(shè)置第i個元素為x，0≤i<n。若i越界，拋出序號越界異常；若x==null，拋出空對象異常。O(1)publicvoidset(inti,Tx){if(x==null)thrownewNullPointerException("x==null");//拋出空對象異常

if(i>=0&&i<this.n)this.element[i]=x;elsethrownewjava.lang.IndexOutOfBoundsException(i+"");//拋出序號越界異常

}toString()采用字符串形式描述對象的屬性值（遍歷）：//返回順序表所有元素的描述字符串，形式為“(,)”。覆蓋Object類的//toString()方法1，注意P21下的解釋—運行時多態(tài)！

publicStringtoString(){Stringstr=this.getClass().getName()+"(";//返回類名//Stringstr="(";if(this.n>0)str+=this.element[0].toString();//執(zhí)行T類的toString()方法，運行時多態(tài)

for(inti=1;i<this.n;i++)str+=","+this.element[i].toString();//執(zhí)行T類的toString()方法，運行時多態(tài)

returnstr+")";//空表返回()}2.2線性表的順序存儲和實現(xiàn)順序表-順序表的基本操作2.2線性表的順序存儲和實現(xiàn)順序表-順序表的基本操作toString()采用字符串形式描述對象的屬性值（遍歷）：//返回順序表所有元素的描述字符串，形式為“(,)”。覆蓋Object類的//toString()方法2//可行，效率同上

publicStringtoString(){Stringstr="(";if(this.n!=0){for(inti=0;i<this.n-1;i++)str+=this.get(i).toString()+",";str+=this.get(this.n-1).toString();//單獨追加最后一個元素，不加逗號}returnstr+")";}2.2線性表的順序存儲和實現(xiàn)順序表-順序表的基本操作isEmpty()、size()、get(i)、set(i,x)方法，時間復(fù)雜度為O(1)。為什么？toString()方法需要遍歷順序表，時間復(fù)雜度為O(n)。為什么？操作的效率分析插入操作： 線性表的插入是指在表的第i個位置上插入一個值為x的新元素，插入后使原表長為n的表:(a0，a1，...，ai-1，ai，ai+1，...，an－1)

成為表長為n+1表:(a0，a1，...，ai-1，x，ai，ai+1，...，an－1) i的取值范圍為0<=i<=n

。2.2線性表的順序存儲和實現(xiàn)順序表-順序表的基本操作2.2線性表的順序存儲和實現(xiàn)順序表-順序表的基本操作插入操作：

2.2線性表的順序存儲和實現(xiàn)順序表-順序表的基本操作插入操作算法設(shè)計：參數(shù)：插入位置i插入元素x操作步驟：書上例子中先對i值進行修正（也可以直接報錯）將ai～an-1

順序向下移動，為新元素讓出位置將x置入空出的第i個位置修改表長2.2線性表的順序存儲和實現(xiàn)順序表-順序表的基本操作插入操作算法設(shè)計：注意：當(dāng)插入一個元素時，如果數(shù)組element已滿，為了能使插入操作正常進行，insert()方法創(chuàng)建一個容量為原數(shù)組兩倍的新數(shù)組，并將原數(shù)組中的元素復(fù)制到新數(shù)組中若使用new申請存儲空間失敗，java虛擬機將產(chǎn)生內(nèi)存溢出，并終止程序邊界的取值方法實現(xiàn)：intinsert(inti,Tx)//插入x作為第i個元素intinsert(Tx)//尾插入x元素。重載2.2線性表的順序存儲和實現(xiàn)順序表-順序表的基本操作插入操作若數(shù)組滿，則擴充順序表的數(shù)組容量插入操作數(shù)組擴容，理解對象引用賦值2.2線性表的順序存儲和實現(xiàn)順序表-順序表的基本操作插入操作

//插入x作為第i個元素，x!=null，返回x序號。若x==null，拋出空對象異常。O(n)//對序號i采取容錯措施，若i<0，插入x在最前；若i>n，插入x在最后

publicintinsert(inti,Tx){if(x==null)thrownewNullPointerException("x==null");//拋出空對象異常

if(i<0)i=0;//插入位置i容錯，插入在最前

if(i>this.n)i=this.n;//插入在最后

Object[]source=this.element;//數(shù)組變量引用賦值，source也引用element數(shù)組

if(this.n==element.length)//若數(shù)組滿，則擴充順序表的數(shù)組容量

{this.element=newObject[source.length*2];//重新申請一個容量更大的數(shù)組

for(intj=0;j<i;j++)//復(fù)制當(dāng)前數(shù)組前i-1個元素

this.element[j]=source[j];}for(intj=this.n-1;j>=i;j--)//從i開始至表尾的元素向后移動，次序從后向前

this.element[j+1]=source[j];this.element[i]=x;this.n++;returni;//返回x序號

}2.2線性表的順序存儲和實現(xiàn)順序表-順序表的基本操作插入操作publicintinsert(Tx)//順序表尾插入x元素，返回x序號。成員方法重載{returnthis.insert(this.n,x);//插入操作中，this.n加1}2.2線性表的順序存儲和實現(xiàn)順序表-順序表的基本操作插入操作當(dāng)在順序存儲結(jié)構(gòu)的線性表中某個位置上插入一個數(shù)據(jù)元素時,其時間消耗主要在移動元素上,而移動元素的個數(shù)取決于插入或者刪除元素的位置考慮，時間復(fù)雜度？？？2.2線性表的順序存儲和實現(xiàn)順序表-順序表的基本操作刪除操作：線性表的刪除運算是指將表中第i個元素從線性表中去掉，刪除后使原表長為n的線性表： (a0，a1，...，ai-1，ai，ai+1，...，an－1)

成為表長為n－1的線性表：

(a0，a1，...，ai-1，ai+1，...，an－1) i的取值范圍為：0<=i<=n-1

。2.2線性表的順序存儲和實現(xiàn)順序表-順序表的基本操作刪除操作：2.2線性表的順序存儲和實現(xiàn)順序表-順序表的基本操作順序表上完成這一運算的步驟如下：找到要刪除的位置i依次將ai+1～an-1

順序向上移動修改表長方法實現(xiàn)：Tremove(inti)//返回刪除第i（0≤i<n）個元素voidclear()//刪除線性表所有元素刪除操作：2.2線性表的順序存儲和實現(xiàn)順序表-順序表的基本操作本算法注意以下問題：刪除第i個元素，i的取值為0=<i=<element.length-1否則第i個元素不存在，因此，要檢查刪除位置的有效性。當(dāng)表空(element.length==0)時不能做刪除。刪除ai之后，該數(shù)據(jù)已不存在，如果需要，先取出ai，再做刪除。刪除操作：2.2線性表的順序存儲和實現(xiàn)順序表-順序表的基本操作順序表的刪除操作

publicTremove(inti)//刪除第i個元素，0≤i<n，返回被刪除元素。若i越界，返回null。//？？若i越界，拋出序號越界異常

{if(this.n>0&&i>=0&&i<this.n){Told=(T)this.element[i];//old中存儲被刪除元素

for(intj=i;j<this.n-1;j++)this.element[j]=this.element[j+1];//元素前移一個位置

this.element[this.n-1]=null;//設(shè)置數(shù)組元素對象為空，釋放原引用實例

this.n--;returnold;//返回old局部變量引用的對象，傳遞對象引用

}returnnull;//thrownewIndexOutOfBoundsException(i+"");//拋出序號越界異常

}2.2線性表的順序存儲和實現(xiàn)順序表-順序表的基本操作publicvoidclear()//刪除線性表所有元素

{this.n=0;//設(shè)置長度為0，未釋放數(shù)組空間}刪除操作：2.2線性表的順序存儲和實現(xiàn)順序表-順序表的基本操作

當(dāng)在順序存儲結(jié)構(gòu)的線性表中某個位置上刪除一個數(shù)據(jù)元素時,其時間消耗主要在移動元素上,而移動元素的個數(shù)取決于插入或者刪除元素的位置.考慮：時間復(fù)雜度？？？刪除元素平均移動次數(shù)（n-1）/2時間復(fù)雜度為O(n)刪除操作：2.2線性表的順序存儲和實現(xiàn)順序表-順序表的基本操作【例2.1】求解約瑟夫環(huán)問題約瑟夫環(huán)（Josephus）問題：1.古代某法官要判決N個犯人的死刑，他有一條荒唐的法律，將犯人站成一個圓圈，從第S個人開始數(shù)起，每數(shù)到第D個犯人，就拉出來處決，然后再數(shù)D個，數(shù)到的在處決……直到剩下的最后一個可赦免。2.設(shè)編號為1、2、···、n的n個人圍坐一圈，約定編號為k(1<=k<=n)的人從1開始報數(shù)，數(shù)到m的那個人出列，他的下一位又從1開始報數(shù)，數(shù)到m的那個人出列，依次類推，知道所有人出列為止，由此產(chǎn)生一個出隊編號的序列。2.2線性表的順序存儲和實現(xiàn)順序表-順序表的基本操作使用順序表求解Josephus環(huán)number=5start=0distance=2時的執(zhí)行示意圖如何設(shè)計算法？【例2.1】求解約瑟夫環(huán)問題2.2線性表的順序存儲和實現(xiàn)順序表-順序表的基本操作//注意：泛型<T>的實際參數(shù)只能是類，不能是基本類型char、int等//importdataStructure.*;//聲明導(dǎo)入指定包中的類或接口publicclassJosephus{//【例2.1】求解Josephus環(huán)問題。

//創(chuàng)建Josephus環(huán)并求解，參數(shù)指定環(huán)長度、起始位置、計數(shù)

publicJosephus(intnumber,intstart,intdistance){System.out.print("Josephus("+number+","+start+","+distance+")，");SeqList<String>list=newSeqList<String>(number);//創(chuàng)建順序表實例，元素類型是字符串，構(gòu)造方法參數(shù)指定順序表容量，省略//時取默認值

for(inti=0;i<number;i++)

list.insert((char)(‘A’+i)+“”);//順序表尾插入，O(1),char類型+””轉(zhuǎn)化為string類型System.out.println(list.toString());//輸出順序表的描述字符串，O(n)【例2.1】求解約瑟夫環(huán)問題2.2線性表的順序存儲和實現(xiàn)順序表-順序表的基本操作inti=start;//計數(shù)起始位置

while(list.size()>1)//多于一個元素時循環(huán)，計數(shù)O(1){i=(i+distance-1)%list.size();//按循環(huán)方式對順序表進行遍歷 System.out.print("刪除"+list.remove(i).toString()+"，"); //刪除i位置對象，O(n)System.out.println(list.toString());}System.out.println("被赦免者是"+list.get(0).toString());//get(0)獲得元素，O(1)}【例2.1】求解約瑟夫環(huán)問題2.2線性表的順序存儲和實現(xiàn)順序表-順序表的基本操作publicstaticvoidmain(Stringargs[]){

//【例2.1】求解Josephus環(huán)問題。

newJosephus(5,0,2);}【例2.1】求解約瑟夫環(huán)問題2.2線性表的順序存儲和實現(xiàn)順序表-順序表的基本操作/*程序運行結(jié)果如下：Josephus(5,0,2)，(A,B,C,D,E)刪除B，(A,C,D,E)刪除D，(A,C,E)刪除A，(C,E)刪除E，(C)被赦免者是CJosephus(5,0,2)，SeqList(A,B,C,D,E)刪除B，SeqList(A,C,D,E)刪除D，SeqList(A,C,E)刪除A，SeqList(C,E)刪除E，SeqList(C)被赦免者是C【例2.1】求解約瑟夫環(huán)問題2.2線性表的順序存儲和實現(xiàn)順序表-順序表的基本操作查找操作//順序查找算法//順序查找首次出現(xiàn)的與key相等元素，返回元素序號i；查找不成功返回-1。//若key==null，Java拋出空對象異常NullPointerExceptionpublicintsearch(Tkey){for(inti=0;i<this.n;i++)if(key.equals(this.element[i])) //執(zhí)行T類的equals(Object)方法，運行時多態(tài)

returni;return-1; //空表或未找到時}booleancontains(Tkey)//包含{ returnthis.search(key)!=-1;}2.2線性表的順序存儲和實現(xiàn)順序表-順序表的基本操作//插入不重復(fù)元素。查找不成功時，尾插入intinsertDifferent(Tx){ returnthis.search(x)==-1?this.insert(x):-1;}Tremove(Tkey)//刪除首個與key相等元素{returnthis.remove(this.search(key));//先查找，再調(diào)用remove(i)。//若查找不成功，返回-1，則不刪除}2.2線性表的順序存儲和實現(xiàn)順序表-順序表的基本操作查找操作Object類publicbooleanequals(Objectobj){ return(this==obj);//若兩個對象引用同一個實例，返回true}Object類中equals(Object)函數(shù)比較兩個是對象是否引用同一個實例。其他類繼承Object類時會覆蓋equals(Object)方法，例如：publicfinalclassIntegerextendsNumberimplementsComparable<Integer>{privatefinalintvalue;publicbooleanequals(Objectobj)//覆蓋Object類的方法

{

if(objinstanceofInteger)returnvalue==((Integer)obj).intValue();//比較兩個Integer對象的值

returnfalse;}}2.2線性表的順序存儲和實現(xiàn)順序表-順序表的基本操作查找操作考慮線性表的其他基本操作：置表為空遍歷順序表并輸出求前驅(qū)求后繼復(fù)制合并排序2.2線性表的順序存儲和實現(xiàn)順序表-順序表的基本操作順序表的靜態(tài)特性很好，動態(tài)特性很差，具體說明如下：①順序表元素的物理存儲順序直接反映線性表元素的邏輯順序，順序表是一種隨機存取結(jié)構(gòu)。get()、set()方法時間復(fù)雜度是O(1)。②插入和刪除操作效率很低（O(n)）。2.2線性表的順序存儲和實現(xiàn)小結(jié)順序表-順序表的基本操作順序表的淺拷貝與深拷貝（自學(xué)）2.2線性表的順序存儲和實現(xiàn)順序表-順序表的基本操作比較相等操作習(xí)題2-5SeqList類以下聲明有什么錯誤？為什么？publicbooleanequals(Objectobj)//比較兩個順序表是否相等，覆蓋{returnthis.n==list.n&&this.element==obj.element;}注意：1.使用“==”比較兩個對象時，比較的是兩個對象的內(nèi)存地址，所以不相等即使它們內(nèi)容相等，但是不同對象的內(nèi)存地址也是不相同的。2.兩個線性表相等是指，它們各對應(yīng)元素相等并且長度相同(使用equal()函數(shù))。2.2線性表的順序存儲和實現(xiàn)順序表-順序表的基本操作//習(xí)題解答2-5比較相等操作2.2線性表的順序存儲和實現(xiàn)順序表-順序表的基本操作比較相等操作2.2線性表的順序存儲和實現(xiàn)順序表-順序表的基本操作//SeqList<T>類聲明覆蓋

publicbooleanequals(Objectobj){ if(this==obj)//引用同一個實例

returntrue;if(objinstanceofSeqList<?>)//若obj引用順序表實例。//SeqList<?>是所有SeqList<T>的父類

{

SeqList<T>list=(SeqList<T>)obj;

if(this.n==list.n) //比較長度

{for(inti=0;i<this.n;i++)//比較所有元素

if(!(this.get(i).equals(list.get(i))))//運行時多態(tài)

returnfalse;returntrue;}}returnfalse;}比較相等操作2.2線性表的順序存儲和實現(xiàn)順序表-順序表的基本操作線性表的順序存儲結(jié)構(gòu)中任意數(shù)據(jù)元素的存儲地址可由公式直接導(dǎo)出，因此順序存儲結(jié)構(gòu)的線性表是可以隨機存取其中的任意元素。也就是說定位操作可以直接實現(xiàn)。高級程序設(shè)計語言提供的數(shù)組數(shù)據(jù)類型可以直接定義順序存儲結(jié)構(gòu)的線性表，使其程序設(shè)計十分方便。2.2線性表的順序存儲和實現(xiàn)順序表-順序表的存儲結(jié)構(gòu)優(yōu)點但是，順序存儲結(jié)構(gòu)也有一些不便之處，表現(xiàn)在：數(shù)據(jù)元素最大個數(shù)需預(yù)先確定，使得高級程序設(shè)計語言編譯系統(tǒng)需預(yù)先分配相應(yīng)的存儲空間。插入與刪除運算的效率很低。為了保持線性表中的數(shù)據(jù)元素的順序，在插入操作和刪除操作時需移動大量數(shù)據(jù)。這對于插入和刪除操作頻繁的線性表、以及每個數(shù)據(jù)元素所占字節(jié)較大的問題將導(dǎo)致系統(tǒng)的運行速度難以提高。順序存儲結(jié)構(gòu)的線性表的存儲空間不便于擴充。當(dāng)一個線性表分配順序存儲空間后，如果線性表的存儲空間已滿，但還需要插入新的元素，則會發(fā)生“上溢”錯誤。在這種情況下，如果在原線性表的存儲空間后找不到與之連續(xù)的可用空間，則會導(dǎo)致運算的失敗或中斷。2.2線性表的順序存儲和實現(xiàn)順序表-順序表的存儲結(jié)構(gòu)缺點從線性表的順序存儲結(jié)構(gòu)的討論中可知，對于大的線性表，特別是元素變動頻繁的大線性表不宜采用順序存儲結(jié)構(gòu)，而應(yīng)采用鏈?zhǔn)酱鎯Y(jié)構(gòu)。線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)就是用若干地址分散的存儲單元（可以是不連續(xù)的）存儲線性表的數(shù)據(jù)元素。采用鏈?zhǔn)酱鎯Y(jié)構(gòu)表示的線性表稱為線性鏈表在鏈?zhǔn)酱鎯Y(jié)構(gòu)方式下，存儲數(shù)據(jù)元素的結(jié)點空間可以不連續(xù)，各數(shù)據(jù)結(jié)點的存儲順序與數(shù)據(jù)元素之間的邏輯關(guān)系可以不一致（邏輯上相鄰的數(shù)據(jù)元素在物理位置上不一定相鄰?。?，而數(shù)據(jù)元素之間的邏輯關(guān)系由指針域（地址域）來確定。2.3線性表的鏈?zhǔn)酱鎯蛯崿F(xiàn)線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)對線性表中的每一個結(jié)點，都至少需用兩部分來存儲：一部分用于存放數(shù)據(jù)元素值，稱為數(shù)據(jù)域；另一部分用于存放直接前驅(qū)或直接后繼結(jié)點的地址（指針），稱為地址域（指針域），我們把這種存儲單元稱為結(jié)點。用結(jié)點來存儲線性表中的每一個數(shù)據(jù)元素。2.3線性表的鏈?zhǔn)酱鎯蛯崿F(xiàn)線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)-結(jié)點線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)L=(a1,a2,……,an)示意圖（單鏈表），其中(a)為非空表，(b)為空表。2.3線性表的鏈?zhǔn)酱鎯蛯崿F(xiàn)線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)-帶頭結(jié)點鏈表2.3線性表的鏈?zhǔn)酱鎯蛯崿F(xiàn)線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)-不帶頭結(jié)點（帶頭指針）鏈表下面將介紹幾個線性鏈表（linearlinkedlist）類型的實現(xiàn)：單鏈表（singlylinkedlist）雙鏈表（doublylinkedlist）循環(huán)鏈表（circularlinkedlist）2.3線性表的鏈?zhǔn)酱鎯蛯崿F(xiàn)線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)-鏈表分類每個結(jié)點只有一個地址域的線性鏈表稱為單鏈表任意存儲單元（結(jié)點）存儲單向鏈表的數(shù)據(jù)元素時，其形式如下圖所示：DATANEXT其中data是數(shù)據(jù)域，存放數(shù)據(jù)元素的值；next是地址域，存放相鄰的下一個結(jié)點的地址單向鏈表是指結(jié)點中的指針域只有一個沿著同一個方向表示的鏈?zhǔn)酱鎯Y(jié)構(gòu)。因為結(jié)點是一個獨立的對象，所以能夠?qū)崿F(xiàn)獨立的結(jié)點類。2.3線性表的鏈?zhǔn)酱鎯蛯崿F(xiàn)單鏈表單鏈表是由多個元素（結(jié)點）組成的前驅(qū)結(jié)點和后繼結(jié)點鏈表的存貯方式是：在內(nèi)存中利用存貯單元(可以不連續(xù))來存放元素值及相關(guān)元素在內(nèi)存中的地址，各個元素的存放順序及位置都可以以任意順序進行，原來相鄰的元素存放到計算機內(nèi)存后不一定相鄰，從一個元素找下一個元素必須通過地址(指針)才能實現(xiàn)。故不能像順序表一樣可隨機訪問，而只能按順序訪問2.3線性表的鏈?zhǔn)酱鎯蛯崿F(xiàn)單鏈表

a2180

a4170

a6NULL

a1110

a5140

a3130

150

地址

data域

next域

110

120

130

140

150

160

170

180

head

頭指針

a1

a2

a3

a4

a5

a6

^

單鏈表的邏輯表示示意圖

單鏈表物理存儲示意圖

head2.3線性表的鏈?zhǔn)酱鎯蛯崿F(xiàn)單鏈表考慮：如何實現(xiàn)單鏈表類？？？關(guān)鍵在于結(jié)點如何實現(xiàn)單鏈表結(jié)點類？？？成員變量包含哪些？構(gòu)造函數(shù)如何定義？有哪些常用的操作？2.3線性表的鏈?zhǔn)酱鎯蛯崿F(xiàn)單鏈表-單鏈表的類實現(xiàn)成員變量：結(jié)點元素是一個自引用的數(shù)據(jù)，當(dāng)前結(jié)點對象中具有下一個結(jié)點元素的對象構(gòu)造方法：構(gòu)造一個結(jié)點元素時，其值被存儲到對象中，并且結(jié)點元素包括一個指向鏈表中下一個元素的引用其他方法：訪問一個類對象的數(shù)據(jù)時，使用所給方法直接訪問（讀或?qū)懀?shù)據(jù)域及引用域2.3線性表的鏈?zhǔn)酱鎯蛯崿F(xiàn)單鏈表-單鏈表的結(jié)點類實現(xiàn)//1.單鏈表結(jié)點類publicclassNode<T>//單鏈表結(jié)點類，T指定結(jié)點的元素類型{publicTdata;//數(shù)據(jù)域，存儲數(shù)據(jù)元素

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

publicNode(Tdata,Node<T>next)//構(gòu)造結(jié)點，data指定數(shù)據(jù)元素，next指定后繼結(jié)點

{this.data=data;//T對象引用賦值

this.next=next;//Node<T>對象引用賦值

}publicNode(){this(null,null);}2.3線性表的鏈?zhǔn)酱鎯蛯崿F(xiàn)單鏈表-單鏈表的結(jié)點類實現(xiàn)publicStringtoString()//返回結(jié)點數(shù)據(jù)域的描述字符串

{returnthis.data.toString();}}//教材沒有寫，沒有直接調(diào)用

publicbooleanequals(Objectobj)//比較兩個結(jié)點值是否相等，覆蓋Object類的equals(obj)方法

{returnobj==this||objinstanceofNode<?>&&this.data.equals(((Node<T>)obj).data);}2.3線性表的鏈?zhǔn)酱鎯蛯崿F(xiàn)單鏈表-單鏈表的結(jié)點類實現(xiàn)注意：Node<T>有兩個成員變量，data表示結(jié)點的數(shù)據(jù)域，保存數(shù)據(jù)元素本身，數(shù)據(jù)類型是T；next表示結(jié)點的地址域，保存后繼結(jié)點的地址Node類中成員變量next的數(shù)據(jù)類型是Node<T>類自己，Node類是“自引用的類”自引用的類(Self-referentialClass)是指一個類聲明包含引用當(dāng)前類實例的成員變量2.3線性表的鏈?zhǔn)酱鎯蛯崿F(xiàn)單鏈表-單鏈表的結(jié)點類實現(xiàn)注意：一個Node<T>類的實例只表示鏈表中的一個結(jié)點，如何將兩個結(jié)點鏈接起來？成員變量設(shè)計為共有，合適否？其他方法需要否，比如直接訪問（讀或?qū)懀?shù)據(jù)域及引用域？單鏈表的頭指針如何設(shè)定？2.3線性表的鏈?zhǔn)酱鎯蛯崿F(xiàn)單鏈表-單鏈表的結(jié)點類實現(xiàn)一個Node<T>類的實例只表示鏈表中的一個結(jié)點，如何將兩個結(jié)點鏈接起來？通過next域?qū)蓚€結(jié)點鏈接起來語句如下：Node<String>p,q;p=newNode<String>("A",null);q=newNode<String>("B",null);p.next=q;所以若干結(jié)點通過next鏈指定相互之間的順序關(guān)系，形成一條單鏈表2.3線性表的鏈?zhǔn)酱鎯蛯崿F(xiàn)單鏈表-單鏈表的結(jié)點類實現(xiàn)成員變量設(shè)計為公有，合適否？便于訪問（更改結(jié)點間的鏈接關(guān)系）根據(jù)封裝性，應(yīng)該設(shè)置為private或protected2.3線性表的鏈?zhǔn)酱鎯蛯崿F(xiàn)單鏈表-單鏈表的結(jié)點類實現(xiàn)其他方法需要否，比如直接訪問（讀或?qū)懀?shù)據(jù)域及引用域？如果將Node類的data和next封裝成私有成員，則必須提供一組公有的getData()、getNext()、setData()、setNext()等方法2.3線性表的鏈?zhǔn)酱鎯蛯崿F(xiàn)單鏈表-單鏈表的結(jié)點類實現(xiàn)單鏈表的頭指針如何設(shè)定？單鏈表的頭指針head也是一個結(jié)點引用，聲明如下： Node<T>head=null;當(dāng)head==null時，表示空單鏈表2.3線性表的鏈?zhǔn)酱鎯蛯崿F(xiàn)單鏈表-單鏈表的結(jié)點類實現(xiàn)對于單鏈表來說，整個鏈表的存取必須是從頭指針開始，頭指針指示鏈表中第0個（起始）結(jié)點的存儲位置。同時由于最后一個數(shù)據(jù)元素，沒有直接后繼，則線性鏈表中最后一個結(jié)點的指針為“空”（null）。2.3線性表的鏈?zhǔn)酱鎯蛯崿F(xiàn)單鏈表-單鏈表的實現(xiàn)開始時單鏈表為空表建立單鏈表時依次在鏈表尾部插入一個新建的結(jié)點考慮：如何實現(xiàn)關(guān)鍵的尾部插入？插入的第一個結(jié)點是否單獨處理？結(jié)論：需要使用new創(chuàng)建Node類型的對象，并依次鏈入鏈表的尾部，注意參數(shù)的值是什么需要對第一個結(jié)點單獨處理插入結(jié)點作為鏈表結(jié)點的初始化來看待，所以利用構(gòu)造函數(shù)實現(xiàn)建立單鏈表2.3線性表的鏈?zhǔn)酱鎯蛯崿F(xiàn)單鏈表-單鏈表的實現(xiàn)設(shè)rear指向原鏈表的最后一個結(jié)點，q指向新創(chuàng)建的結(jié)點，則將q結(jié)點鏈在rear結(jié)點之后的語句是：

rear.next=q；

rear=q；需要考慮開始為空的特殊情況建立單鏈表2.3線性表的鏈?zhǔn)酱鎯蛯崿F(xiàn)單鏈表-單鏈表的實現(xiàn)其他需要考慮的問題：rear可否作為SingLinkedList類的保護成員存在假設(shè)插入的元素為隨機數(shù)建立單鏈表2.3線性表的鏈?zhǔn)酱鎯蛯崿F(xiàn)單鏈表-單鏈表的實現(xiàn)實現(xiàn)過程：產(chǎn)生隨機數(shù)新建以隨機數(shù)為元素的結(jié)點，并把新結(jié)點鏈入到第一個位置修改rear產(chǎn)生隨機數(shù)新建以隨機數(shù)為元素的結(jié)點q把q放到結(jié)點的尾部修改rear循環(huán)4～7步建立單鏈表2.3線性表的鏈?zhǔn)酱鎯蛯崿F(xiàn)單鏈表-單鏈表的實現(xiàn)遍歷單鏈表是指從第0個結(jié)點開始，沿著結(jié)點的next鏈，依次訪問單鏈表中的每個結(jié)點，并且每個結(jié)點只訪問一次。單鏈表的遍歷操作2.3線性表的鏈?zhǔn)酱鎯蛯崿F(xiàn)單鏈表-單鏈表的實現(xiàn)遍歷單鏈表操作不能改變頭指針head，因此需要聲明一個變量p指向當(dāng)前訪問結(jié)點p從head指向的結(jié)點（第0個—引用結(jié)點）開始訪問，再沿著next鏈到達后繼結(jié)點，逐個訪問，直到最后一個結(jié)點，完成一次遍歷單鏈表的遍歷操作2.3線性表的鏈?zhǔn)酱鎯蛯崿F(xiàn)單鏈表-單鏈表的實現(xiàn)單鏈表的遍歷操作Node<T>p=head;while(p!=null){p.data.toString()//執(zhí)行訪問p結(jié)點的相關(guān)操作p=p.next;}單鏈表的遍歷操作2.3線性表的鏈?zhǔn)酱鎯蛯崿F(xiàn)單鏈表-單鏈表的實現(xiàn)如果語句p=p.next寫成p.next=p？p.next=p;使p.next指向p結(jié)點自己，改變了結(jié)點間的鏈接關(guān)系。遍歷算法死循環(huán)。單鏈表的遍歷操作（思考）2.3線性表的鏈?zhǔn)酱鎯蛯崿F(xiàn)單鏈表-單鏈表的實現(xiàn)在單鏈表中插入新的結(jié)點，根據(jù)插入位置的不同，分四種情況：空表插入頭插入尾插入中間插入關(guān)鍵：插入結(jié)點時，只要改變結(jié)點間的鏈接關(guān)系，不需要移動數(shù)據(jù)元素。插入結(jié)點2.3線性表的鏈?zhǔn)酱鎯蛯崿F(xiàn)單鏈表-單鏈表的實現(xiàn)插入結(jié)點2.3線性表的鏈?zhǔn)酱鎯蛯崿F(xiàn)單鏈表-單鏈表的實現(xiàn)假定鏈表為空（head==null），插入一個結(jié)點，鏈表只有一個結(jié)點語句如下：

head=newNode<T>(x,null)；空表插入2.3線性表的鏈?zhǔn)酱鎯蛯崿F(xiàn)單鏈表-單鏈表的實現(xiàn)haveyournamehead頭插入結(jié)點2.3線性表的鏈?zhǔn)酱鎯蛯崿F(xiàn)單鏈表-單鏈表的實現(xiàn)haveyournameheadq頭插入結(jié)點2.3線性表的鏈?zhǔn)酱鎯蛯崿F(xiàn)單鏈表-單鏈表的實現(xiàn)haveyournamemayheadq頭插入結(jié)點2.3線性表的鏈?zhǔn)酱鎯蛯崿F(xiàn)單鏈表-單鏈表的實現(xiàn)haveyournamemayheadq頭插入結(jié)點2.3線性表的鏈?zhǔn)酱鎯蛯崿F(xiàn)單鏈表-單鏈表的實現(xiàn)haveyournamemayheadq頭插入結(jié)點2.3線性表的鏈?zhǔn)酱鎯蛯崿F(xiàn)單鏈表-單鏈表的實現(xiàn)過程：構(gòu)造一個新的Node對象p在新對象中加入需要的值x讓其指針域指向列表中的第一個元素head指向新對象p頭插入結(jié)點2.3線性表的鏈?zhǔn)酱鎯蛯崿F(xiàn)單鏈表-單鏈表的實現(xiàn)若單鏈表非空（head!=null），則在head結(jié)點之前插入值為x的結(jié)點的關(guān)鍵語句如下：Node<T>p=newNode<T>(x,null)；p.next=head；head=p；考慮：空表插入和頭插入有何相似之處？結(jié)論：空表插入和頭插入的合并結(jié)果head=newNode<T>(x,head);頭插入結(jié)點2.3線性表的鏈?zhǔn)酱鎯蛯崿F(xiàn)單鏈表-單鏈表的實現(xiàn)鏈表不為空的情況：lifeonmoon^head尾插入結(jié)點2.3線性表的鏈?zhǔn)酱鎯蛯崿F(xiàn)單鏈表-單鏈表的實現(xiàn)lifeonmoon^phead尾插入結(jié)點2.3線性表的鏈?zhǔn)酱鎯蛯崿F(xiàn)單鏈表-單鏈表的實現(xiàn)lifeonmoon^phead尾插入結(jié)點2.3線性表的鏈?zhǔn)酱鎯蛯崿F(xiàn)單鏈表-單鏈表的實現(xiàn)lifeonmoon^phead尾插入結(jié)點2.3線性表的鏈?zhǔn)酱鎯蛯崿F(xiàn)單鏈表-單鏈表的實現(xiàn)lifeonmoon^pyes^headq尾插入結(jié)點2.3線性表的鏈?zhǔn)酱鎯蛯崿F(xiàn)單鏈表-單鏈表的實現(xiàn)lifeonmoonpyes^qhead尾插入結(jié)點2.3線性表的鏈?zhǔn)酱鎯蛯崿F(xiàn)單鏈表-單鏈表的實現(xiàn)考慮：如果鏈表為空，如何操作？可否增設(shè)一個尾結(jié)點（rear）？尾插入結(jié)點2.3線性表的鏈?zhǔn)酱鎯蛯崿F(xiàn)單鏈表-單鏈表的實現(xiàn)實現(xiàn)過程：到達鏈表尾部構(gòu)造一個新的Node對象p在新對象中加入需要的值讓最后一個結(jié)點的指針域指向新對象p尾插入結(jié)點2.3線性表的鏈?zhǔn)酱鎯蛯崿F(xiàn)單鏈表-單鏈表的實現(xiàn)關(guān)鍵語句如下：Node<T>p=newNode<T>(x,null)；front.next=p；尾插入結(jié)點2.3線性表的鏈?zhǔn)酱鎯蛯崿F(xiàn)單鏈表-單鏈表的實現(xiàn)若將x插入a和b之間，插入結(jié)點的指針變化如圖所示

①

②

q

a

b

x

p

′

插入結(jié)點時的指針修改

中間插入結(jié)點2.3線性表的鏈?zhǔn)酱鎯蛯崿F(xiàn)單鏈表-單鏈表的實現(xiàn)基于上圖，關(guān)鍵語句如下：Node<T>p=newNode<T>(x,null)；p.next=front.next;front.next=p；

中間插入結(jié)點2.3線性表的鏈?zhǔn)酱鎯蛯崿F(xiàn)單鏈表-單鏈表的實現(xiàn)考慮：單鏈表的插入是否需要移到大量元素對于單鏈表很方便訪問結(jié)點的后繼結(jié)點對于單鏈表訪問結(jié)點的前驅(qū)結(jié)點很不方便，如何實現(xiàn)中間插入結(jié)點2.3線性表的鏈?zhǔn)酱鎯蛯崿F(xiàn)單鏈表-單鏈表的實現(xiàn)考慮：中間插入和尾插入有何相似之處？結(jié)論：中間插入和尾插入的合并實現(xiàn)設(shè)front指向單鏈表中的某個結(jié)點，在front結(jié)點后插入值為x結(jié)點的語句如下：

Node<T>p=newNode<T>(x,null);p.next=front.next;//p的后繼是front的后繼front.next=p;//p作為front的后繼即:front.next=newNode<T>(x,front.next);中間插入結(jié)點2.3線性表的鏈?zhǔn)酱鎯蛯崿F(xiàn)單鏈表-單鏈表的實現(xiàn)【思考】圖（c）中，如果①②兩句次序顛倒，將會怎樣？

Node<T>p=newNode<T>(x,null);front.next=p;//②p.next=front.next;//①

會出現(xiàn)錯誤，丟失后續(xù)鏈表中間插入結(jié)點2.3線性表的鏈?zhǔn)酱鎯蛯崿F(xiàn)單鏈表-單鏈表的實現(xiàn)在單鏈表中刪除已有的結(jié)點，根據(jù)刪除位置的不同，分四種情況：只有一個結(jié)點的鏈表刪除頭部刪除中間刪除尾部刪除關(guān)鍵：刪除單鏈表中的指定結(jié)點，通過改變結(jié)點的next域，就可以改變結(jié)點間的鏈接關(guān)系，不需要移動元素。Java的資源回收機制將自動釋放不再使用的對象，收回其占用的資源。刪除結(jié)點2.3線性表的鏈?zhǔn)酱鎯蛯崿F(xiàn)單鏈表-單鏈表的實現(xiàn)刪除結(jié)點2.3線性表的鏈?zhǔn)酱鎯蛯崿F(xiàn)單鏈表-單鏈表的實現(xiàn)刪除結(jié)點2.3線性表的鏈?zhǔn)酱鎯蛯崿F(xiàn)單鏈表-單鏈表的實現(xiàn)刪除單結(jié)點鏈表，只要使鏈表的引用head為空即可： head=null;刪除結(jié)點（單結(jié)點鏈表）2.3線性表的鏈?zhǔn)酱鎯蛯崿F(xiàn)單鏈表-單鏈表的實現(xiàn)haveyournamehead頭刪除2.3線性表的鏈?zhǔn)酱鎯蛯崿F(xiàn)單鏈表-單鏈表的實現(xiàn)haveyournametemphead頭刪除2.3線性表的鏈?zhǔn)酱鎯蛯崿F(xiàn)單鏈表-單鏈表的實現(xiàn)haveyournametemphead頭刪除2.3線性表的鏈?zhǔn)酱鎯蛯崿F(xiàn)單鏈表-單鏈表的實現(xiàn)操作過程：將第一個元素復(fù)制到一個臨時變量中將head指向第二個元素返回原有的第一個元素的值頭刪除2.3線性表的鏈?zhǔn)酱鎯蛯崿F(xiàn)單鏈表-單鏈表的實現(xiàn)刪除單鏈表head指向的結(jié)點，使head引用其后繼結(jié)點，關(guān)鍵語句如下：head=head.next;考慮：一個結(jié)點的刪除和頭刪除有何相似之處？結(jié)論：一個結(jié)點的刪除和頭刪除的合并

head=head.next;頭刪除2.3線性表的鏈?zhǔn)酱鎯蛯崿F(xiàn)單鏈表-單鏈表的實現(xiàn)列表不為空的情況：lifeonmoon^head尾刪除2.3線性表的鏈?zhǔn)酱鎯蛯崿F(xiàn)單鏈表-單鏈表的實現(xiàn)lifeonmoon^fingerprevioshead尾刪除2.3線性表的鏈?zhǔn)酱鎯蛯崿F(xiàn)單鏈表-單鏈表的實現(xiàn)lifeonmoon^fingerprevioshead尾刪除2.3線性表的鏈?zhǔn)酱鎯蛯崿F(xiàn)單鏈表-單鏈表的實現(xiàn)lifeonmoon^fingerprevioshead尾刪除2.3線性表的鏈?zhǔn)酱鎯蛯崿F(xiàn)單鏈表-單鏈表的實現(xiàn)lifeonmoon^fingerprevios^head尾刪除2.3線性表的鏈?zhǔn)酱鎯蛯崿F(xiàn)單鏈表-單鏈表的實現(xiàn)自己考慮如何實現(xiàn)？尾刪除2.3線性表的鏈?zhǔn)酱鎯蛯崿F(xiàn)單鏈表-單鏈表的實現(xiàn)表尾操作都是先從頭找到表尾，然后開始操作，這種技術(shù)稱為鏈表遍歷技術(shù)。需要注意鏈表為空這種特殊情況，否則程序出錯。編程需要考慮邊界條件，軟件需要健壯性和正確性。尾刪除2.3線性表的鏈?zhǔn)酱鎯蛯崿F(xiàn)單鏈表-單鏈表的實現(xiàn)若將x刪除，刪除結(jié)點的指針變化如圖所示