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

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

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

稱為ai

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

稱為ai

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

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

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

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

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

voidclear()//刪除所有元素

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

this.n=element.length;//也可this.insert(values[i]);//尾插入，this.n++。暫且不用，因?yàn)檫€沒(méi)有講到

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

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

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

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

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

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

2）如果x還沒(méi)有被賦值，如何處理

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

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

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

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

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

returnstr+")";//空表返回()}2.2線性表的順序存儲(chǔ)和實(shí)現(xiàn)順序表-順序表的基本操作2.2線性表的順序存儲(chǔ)和實(shí)現(xiàn)順序表-順序表的基本操作toString()采用字符串形式描述對(duì)象的屬性值（遍歷）：//返回順序表所有元素的描述字符串，形式為“(,)”。覆蓋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();//單獨(dú)追加最后一個(gè)元素，不加逗號(hào)}returnstr+")";}2.2線性表的順序存儲(chǔ)和實(shí)現(xiàn)順序表-順序表的基本操作isEmpty()、size()、get(i)、set(i,x)方法，時(shí)間復(fù)雜度為O(1)。為什么？toString()方法需要遍歷順序表，時(shí)間復(fù)雜度為O(n)。為什么？操作的效率分析插入操作： 線性表的插入是指在表的第i個(gè)位置上插入一個(gè)值為x的新元素，插入后使原表長(zhǎng)為n的表:(a0，a1，...，ai-1，ai，ai+1，...，an－1)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

成為表長(zhǎng)為n－1的線性表：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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)問(wèn)題2.2線性表的順序存儲(chǔ)和實(shí)現(xiàn)順序表-順序表的基本操作inti=start;//計(jì)數(shù)起始位置

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

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

newJosephus(5,0,2);}【例2.1】求解約瑟夫環(huán)問(wèn)題2.2線性表的順序存儲(chǔ)和實(shí)現(xiàn)順序表-順序表的基本操作/*程序運(yù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)問(wèn)題2.2線性表的順序存儲(chǔ)和實(shí)現(xiàn)順序表-順序表的基本操作查找操作//順序查找算法//順序查找首次出現(xiàn)的與key相等元素，返回元素序號(hào)i；查找不成功返回-1。//若key==null，Java拋出空對(duì)象異常NullPointerExceptionpublicintsearch(Tkey){for(inti=0;i<this.n;i++)if(key.equals(this.element[i])) //執(zhí)行T類的equals(Object)方法，運(yùn)行時(shí)多態(tài)

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

{

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

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

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

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

{

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

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

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

if(!(this.get(i).equals(list.get(i))))//運(yùn)行時(shí)多態(tài)

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

^

單鏈表的邏輯表示示意圖

單鏈表物理存儲(chǔ)示意圖

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

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

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

{this.data=data;//T對(duì)象引用賦值

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

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

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

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

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

rear.next=q；

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

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

①

②

q

a

b

x

p

′

插入結(jié)點(diǎn)時(shí)的指針修改

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

中間插入結(jié)點(diǎn)2.3線性表的鏈?zhǔn)酱鎯?chǔ)和實(shí)現(xiàn)單鏈表-單鏈表的實(shí)現(xiàn)考慮：?jiǎn)捂湵淼牟迦胧欠裥枰频酱罅吭貙?duì)于單鏈表很方便訪問(wèn)結(jié)點(diǎn)的后繼結(jié)點(diǎn)對(duì)于單鏈表訪問(wèn)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)很不方便，如何實(shí)現(xiàn)中間插入結(jié)點(diǎn)2.3線性表的鏈?zhǔn)酱鎯?chǔ)和實(shí)現(xiàn)單鏈表-單鏈表的實(shí)現(xiàn)考慮：中間插入和尾插入有何相似之處？結(jié)論：中間插入和尾插入的合并實(shí)現(xiàn)設(shè)front指向單鏈表中的某個(gè)結(jié)點(diǎn)，在front結(jié)點(diǎn)后插入值為x結(jié)點(diǎn)的語(yǔ)句如下：

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é)點(diǎn)2.3線性表的鏈?zhǔn)酱鎯?chǔ)和實(shí)現(xiàn)單鏈表-單鏈表的實(shí)現(xiàn)【思考】圖（c）中，如果①②兩句次序顛倒，將會(huì)怎樣？

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

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

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