數(shù)據(jù)結(jié)構(gòu)(Java版)線性表2(鏈表)

1、鏈表為什么要使用鏈?zhǔn)酱鎯?chǔ)？ 考慮： 在順序表中插入一個(gè)數(shù)據(jù)元素.該順序表上已經(jīng)排好序的，要求插入新數(shù)據(jù)元素后，仍然保證原來的有序性。應(yīng)該如何插入？主要內(nèi)容1.1.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)2.2.鏈表是什么鏈表是什么? ?3.3.鏈表的種類鏈表的種類4.4.認(rèn)識(shí)單鏈表認(rèn)識(shí)單鏈表 5.5.單鏈表的設(shè)計(jì)與使用單鏈表的設(shè)計(jì)與使用: :例題例題2-3,2-3,用單鏈表實(shí)現(xiàn)學(xué)生成用單鏈表實(shí)現(xiàn)學(xué)生成績(jī)管理程序績(jī)管理程序6.6.項(xiàng)目拓展。修改學(xué)生成績(jī)管理程序。項(xiàng)目拓展。修改學(xué)生成績(jī)管理程序。7.7.提高自己提高自己 。再修改學(xué)生成績(jī)管理程序。再修改學(xué)生成績(jī)管理程序。8.8.項(xiàng)目再實(shí)踐。雙鏈表及其使用項(xiàng)目再實(shí)踐

2、。雙鏈表及其使用9.9.了解循環(huán)鏈表了解循環(huán)鏈表10.10.JavaJava類庫(kù)中的鏈表類庫(kù)中的鏈表java.util.LinkedListjava.util.LinkedList及其使用及其使用11.11.作業(yè)作業(yè): :習(xí)題習(xí)題2.62.61 1、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 對(duì)邏輯上相鄰的元素不要求其物理位置相對(duì)邏輯上相鄰的元素不要求其物理位置相鄰，元素間的邏輯關(guān)系通過附設(shè)的指針鄰，元素間的邏輯關(guān)系通過附設(shè)的指針（或引用）字段來表示，由此得到的存儲(chǔ)（或引用）字段來表示，由此得到的存儲(chǔ)表示稱為表示稱為鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)通，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)通常借助于程序設(shè)計(jì)語言中的指針（或引用）常借助于程序設(shè)

3、計(jì)語言中的指針（或引用）類型來實(shí)現(xiàn)。類型來實(shí)現(xiàn)。2 2、鏈表是什么? ?鏈表鏈表：是具有鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的一種線性結(jié)構(gòu)，它用一組地址任意的存儲(chǔ)單元存放集合中的數(shù)據(jù)元素，邏輯上相鄰的元素在物理上不要求也相鄰，對(duì)鏈表中的元素，不能隨機(jī)存取，只能從鏈表的頭鏈表的頭開始。鏈表中第一個(gè)數(shù)據(jù)元素的存儲(chǔ)地址作為鏈表的鏈表中第一個(gè)數(shù)據(jù)元素的存儲(chǔ)地址作為鏈表的地址，稱為地址，稱為鏈表的頭鏈表的頭 。鏈表中的元素通常描述結(jié)點(diǎn)（Node)。 結(jié)點(diǎn)結(jié)點(diǎn)(數(shù)據(jù)元素) = =數(shù)據(jù)域數(shù)據(jù)域(數(shù)據(jù)元素的映象) + + 指針域指針域(指示后繼元素的存儲(chǔ)位置)3 3、鏈表的種類鏈表有三種鏈表有三種 單鏈表單鏈表雙向鏈表雙向鏈表循環(huán)鏈

4、表（循環(huán)單鏈表、循環(huán)雙鏈表）循環(huán)鏈表（循環(huán)單鏈表、循環(huán)雙鏈表）4、認(rèn)識(shí)單鏈表單鏈表：每個(gè)結(jié)點(diǎn)有一個(gè)指針域，有一個(gè)每個(gè)結(jié)點(diǎn)有一個(gè)指針域，有一個(gè)頭指針h ,而無尾指針，表中最后一個(gè)結(jié)點(diǎn)的指針而無尾指針，表中最后一個(gè)結(jié)點(diǎn)的指針域是空的。其結(jié)構(gòu)簡(jiǎn)單，但查找效率不高（查域是空的。其結(jié)構(gòu)簡(jiǎn)單，但查找效率不高（查某結(jié)點(diǎn)總要從頭開始）某結(jié)點(diǎn)總要從頭開始） 。單鏈表的操作插入結(jié)點(diǎn)刪除結(jié)點(diǎn)遍歷結(jié)點(diǎn)查詢結(jié)點(diǎn)插入結(jié)點(diǎn)在單鏈表中插入結(jié)點(diǎn)有三種情況：在單鏈表中插入結(jié)點(diǎn)有三種情況：?jiǎn)捂湵淼牟僮? 單鏈表的操作- 單鏈表的操作- 在單鏈表中在單鏈表中刪除刪除結(jié)點(diǎn)有三種情況：結(jié)點(diǎn)有三種情況：?jiǎn)捂湵淼牟僮?單鏈表的操作-單鏈表的

5、操作-遍歷結(jié)點(diǎn) 遍歷遍歷通常從鏈表的頭開始，逐個(gè)訪問每個(gè)結(jié)點(diǎn)，并輸出結(jié)點(diǎn)信息。查詢結(jié)點(diǎn)查詢查詢通常也是從鏈表的頭開始，逐個(gè)訪問每個(gè)結(jié)點(diǎn)，根據(jù)用戶提供的關(guān)鍵字關(guān)鍵字與結(jié)點(diǎn)中的字段進(jìn)行比較，找到后輸出相關(guān)信息。5 單鏈表結(jié)構(gòu)java設(shè)計(jì)、實(shí)現(xiàn)與使用1.1.定義結(jié)點(diǎn)定義結(jié)點(diǎn)( (數(shù)據(jù)元素）數(shù)據(jù)元素）：一個(gè)class,其中有一個(gè)屬性是結(jié)點(diǎn)類型的引用（指針）2.2.定義操作定義操作(ADT)(ADT)：一個(gè)interface .3.3.實(shí)現(xiàn)單鏈表實(shí)現(xiàn)單鏈表：一個(gè)實(shí)現(xiàn)了2中接口的類。4.使用單鏈表 完成應(yīng)用程序 實(shí)踐項(xiàng)目 例題例題2-32-3：用單鏈表實(shí)現(xiàn)學(xué)生成績(jī)管：用單鏈表實(shí)現(xiàn)學(xué)生成績(jī)管理程序。程序運(yùn)行

6、界面如下：理程序。程序運(yùn)行界面如下： 項(xiàng)目概述: :用單鏈表實(shí)現(xiàn)學(xué)生成績(jī)管理程序用單鏈表實(shí)現(xiàn)學(xué)生成績(jī)管理程序, ,該程序具該程序具有添加、查詢、修改、顯示學(xué)生信息等功有添加、查詢、修改、顯示學(xué)生信息等功能能項(xiàng)目實(shí)現(xiàn)步驟1 1 定義數(shù)據(jù)元素定義數(shù)據(jù)元素: StudNode: StudNode類。類。2 2 定義單鏈表的操作定義單鏈表的操作: StudOperation: StudOperation接口。接口。3 3 單鏈表：?jiǎn)捂湵恚?StudLinkedListStudLinkedList類，實(shí)現(xiàn)類，實(shí)現(xiàn)StudOperationStudOperation接口接口4 4 使用單鏈表完成學(xué)生成績(jī)管

7、理程序使用單鏈表完成學(xué)生成績(jī)管理程序. . StudLinkedListUserStudLinkedListUser類類課堂實(shí)訓(xùn)調(diào)試并運(yùn)行例題2-36 項(xiàng)目拓展 實(shí)戰(zhàn)演練實(shí)戰(zhàn)演練: 修改完善例題2-3的學(xué)生成績(jī)管理程序。1.修改接口StudOPeration，為程序添加操作如下：獲取學(xué)生記錄個(gè)數(shù)。根據(jù)學(xué)生姓名刪除學(xué)生的信息。2.修改單鏈表類StudLinkedList，實(shí)現(xiàn)上述操作。3.在學(xué)生成績(jī)管理程序中完成上述功能的使用。刪除記錄算法思路 1 1 首先判斷鏈表是否為空，若鏈表為空，則輸出首先判斷鏈表是否為空，若鏈表為空，則輸出“鏈表為空鏈表為空”的信息。的信息。 2 2 當(dāng)鏈表不空時(shí)，用循

8、環(huán)語句實(shí)現(xiàn)刪除。定義一個(gè)當(dāng)鏈表不空時(shí)，用循環(huán)語句實(shí)現(xiàn)刪除。定義一個(gè)booleanboolean變量變量flagflag作為查詢標(biāo)志。作為查詢標(biāo)志。false false 為沒找到，為沒找到，truetrue為找到。初始值設(shè)為為找到。初始值設(shè)為false.false. 1 1）定義）定義currentcurrent為循環(huán)變量，并設(shè)置循環(huán)初始值為為循環(huán)變量，并設(shè)置循環(huán)初始值為head(head(鏈表的頭鏈表的頭) )。 定義定義prepre變量保存變量保存currentcurrent節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)。節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)。 2 2）循環(huán)條件是）循環(huán)條件是currentcurrent的指針域是否為的指針

9、域是否為nullnull。 3 3）循環(huán)體內(nèi)容：如果當(dāng)前（）循環(huán)體內(nèi)容：如果當(dāng)前（ current current ）節(jié)點(diǎn)的相應(yīng)關(guān)鍵字與要?jiǎng)h）節(jié)點(diǎn)的相應(yīng)關(guān)鍵字與要?jiǎng)h除節(jié)點(diǎn)的關(guān)鍵字不相同，則將除節(jié)點(diǎn)的關(guān)鍵字不相同，則將currentcurrent的值保存在的值保存在prepre中中, ,然后修改循然后修改循環(huán)變量環(huán)變量current,current,使其指向下一個(gè)節(jié)點(diǎn)，繼續(xù)查找。否則，如果當(dāng)前使其指向下一個(gè)節(jié)點(diǎn)，繼續(xù)查找。否則，如果當(dāng)前（ current current ）節(jié)點(diǎn)的相應(yīng)關(guān)鍵字與要?jiǎng)h除節(jié)點(diǎn)的關(guān)鍵字相同，則設(shè)）節(jié)點(diǎn)的相應(yīng)關(guān)鍵字與要?jiǎng)h除節(jié)點(diǎn)的關(guān)鍵字相同，則設(shè)置刪除標(biāo)志為置刪除標(biāo)志為tru

10、etrue，并修改鏈表指針。此時(shí)對(duì)要?jiǎng)h除的結(jié)點(diǎn)，并修改鏈表指針。此時(shí)對(duì)要?jiǎng)h除的結(jié)點(diǎn)(current(current所指向的結(jié)點(diǎn)所指向的結(jié)點(diǎn)) )分三種情況進(jìn)行處理。分三種情況進(jìn)行處理。 A)A)該結(jié)點(diǎn)是鏈?zhǔn)坠?jié)點(diǎn)，則使該結(jié)點(diǎn)是鏈?zhǔn)坠?jié)點(diǎn)，則使 head=current.nexthead=current.next B) B)若該結(jié)點(diǎn)為鏈尾節(jié)點(diǎn)，則讓若該結(jié)點(diǎn)為鏈尾節(jié)點(diǎn)，則讓pre.next=nullpre.next=null。 C)C)若要?jiǎng)h除的結(jié)點(diǎn)是鏈表中間位置的一個(gè)，則使若要?jiǎng)h除的結(jié)點(diǎn)是鏈表中間位置的一個(gè)，則使pre.next=current.nextpre.next=current.next。

11、做完上面的操作后結(jié)束循環(huán)。做完上面的操作后結(jié)束循環(huán)。3 3 循環(huán)結(jié)束后循環(huán)結(jié)束后結(jié)結(jié)點(diǎn)計(jì)數(shù)器減點(diǎn)計(jì)數(shù)器減1 1，并，并對(duì)查詢標(biāo)志進(jìn)行判斷，若為對(duì)查詢標(biāo)志進(jìn)行判斷，若為falsefalse，則，則輸出輸出“沒找到。沒找到?！毙畔ⅰＨ魹樾畔?。若為truetrue，輸出，輸出“節(jié)點(diǎn)已刪除節(jié)點(diǎn)已刪除”。7 提高自己 編程實(shí)現(xiàn)31頁(yè) 實(shí)戰(zhàn)演練的 4）算法思路算法思路: :1 1 判斷鏈表是否為空，若為空，則將新結(jié)點(diǎn)作為鏈表的頭；判斷鏈表是否為空，若為空，則將新結(jié)點(diǎn)作為鏈表的頭；2 2 若鏈表不空，則用循環(huán)語句，比較新結(jié)點(diǎn)和鏈表中結(jié)點(diǎn)的若鏈表不空，則用循環(huán)語句，比較新結(jié)點(diǎn)和鏈表中結(jié)點(diǎn)的學(xué)號(hào)學(xué)號(hào), ,找到新

12、結(jié)點(diǎn)要插入的位置找到新結(jié)點(diǎn)要插入的位置, ,將其插入。插入新結(jié)點(diǎn)的將其插入。插入新結(jié)點(diǎn)的位置分為位置分為3 3種情況種情況: : 1) 1)在表頭插入在表頭插入 2)2)在表尾插入在表尾插入 3)3)在表中某個(gè)結(jié)點(diǎn)前插入在表中某個(gè)結(jié)點(diǎn)前插入. .3 3 循環(huán)結(jié)束后循環(huán)結(jié)束后, ,結(jié)點(diǎn)計(jì)數(shù)器加結(jié)點(diǎn)計(jì)數(shù)器加1 1。8 項(xiàng)目再實(shí)踐自己看書學(xué)習(xí)雙鏈表結(jié)構(gòu)及其插入和刪除操作特點(diǎn)。調(diào)試?yán)}2-4，學(xué)習(xí)雙鏈表的設(shè)計(jì)與實(shí)現(xiàn)方法。完成36頁(yè)的實(shí)戰(zhàn)演練。完成習(xí)題二 第2.5題。雙向鏈表的結(jié)構(gòu)雙向鏈表中結(jié)點(diǎn)的指針域具有兩個(gè)指針,一個(gè)指向其后繼結(jié)點(diǎn),另一個(gè)指向其前驅(qū)結(jié)點(diǎn).雙向鏈表具有一個(gè)指向表頭的引用head和一個(gè)指

13、向表尾的引用tail.9 循環(huán)鏈表單循環(huán)鏈表雙循環(huán)鏈表10 Java類庫(kù)中的鏈表及其使用 JavaJava類庫(kù)中的類庫(kù)中的java.util.LinkedListjava.util.LinkedList類實(shí)現(xiàn)了鏈表的功能類實(shí)現(xiàn)了鏈表的功能, ,其中常用其中常用的構(gòu)造器和方法如下的構(gòu)造器和方法如下: :public LinkedLinkedList()/創(chuàng)建鏈表public boolean add(Object obj)/在表尾添加一個(gè)元素public boolean add(int index,Object obj)/將obj添加到表的第index個(gè)位置處public boolean addFirs(Object obj)/在表頭添加一個(gè)元素public boolean addLast(Object obj)/在表尾添加一個(gè)元素public boolean remove(Object obj)/刪除元素objpublic Object removeFisrt()/刪除表頭元素public Object removeLast()/刪除表尾元素public Object remove (i)/刪除表中第i個(gè)元素public int size()/獲取表中元素個(gè)數(shù)pu