1、第二章 線性表線性表的定義、邏輯結(jié)構(gòu)特點(diǎn)及基本運(yùn)算線性表的定義、邏輯結(jié)構(gòu)特點(diǎn)及基本運(yùn)算線性表的線性表的順序存儲(chǔ)順序存儲(chǔ)及基本運(yùn)算及基本運(yùn)算線性表的線性表的鏈?zhǔn)酱鎯?chǔ)鏈?zhǔn)酱鎯?chǔ)及基本運(yùn)算及基本運(yùn)算數(shù)組的邏輯結(jié)構(gòu)定義及其存儲(chǔ)方式數(shù)組的邏輯結(jié)構(gòu)定義及其存儲(chǔ)方式線性表的應(yīng)用線性表的應(yīng)用線性表的定義及特點(diǎn)線性表線性表n(n0)個(gè)具有個(gè)具有相同特性相同特性的數(shù)據(jù)元素的的數(shù)據(jù)元素的有限序列有限序列其中其中n表示線性表的長(zhǎng)度，即數(shù)據(jù)元素的個(gè)數(shù)表示線性表的長(zhǎng)度，即數(shù)據(jù)元素的個(gè)數(shù)n=0時(shí)表為空表時(shí)表為空表n0時(shí)記為時(shí)記為:（a1, a2， ai-1， ai， ai+1， an）基本特征基本特征有且只有一個(gè)有且只有一個(gè)

2、“第一元素第一元素”，有且只有一個(gè)，有且只有一個(gè)“最后元素最后元素”除第一元素之外，其它元素都有唯一的直接前趨除第一元素之外，其它元素都有唯一的直接前趨除最后元素之外，其它元素都有唯一的直接后繼除最后元素之外，其它元素都有唯一的直接后繼元素的含義數(shù)據(jù)元素在不同問題中的含數(shù)據(jù)元素在不同問題中的含義各不相同義各不相同可以是一個(gè)數(shù)、一個(gè)符號(hào)，可以是一個(gè)數(shù)、一個(gè)符號(hào)，一個(gè)記錄，或其它更復(fù)雜的一個(gè)記錄，或其它更復(fù)雜的信息信息這里的學(xué)生成績(jī)表是一個(gè)線這里的學(xué)生成績(jī)表是一個(gè)線性表性表數(shù)據(jù)元素是每一個(gè)學(xué)生的信數(shù)據(jù)元素是每一個(gè)學(xué)生的信息，包括：學(xué)號(hào)、姓名、成息，包括：學(xué)號(hào)、姓名、成績(jī)共三個(gè)數(shù)據(jù)項(xiàng)績(jī)共三個(gè)數(shù)據(jù)項(xiàng)學(xué)

3、號(hào)學(xué)號(hào)姓名姓名計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論04081101陳小潔陳小潔8004081102馬麗麗馬麗麗7504081103林春英林春英8204081104王澄娟王澄娟9004081150張吉祥張吉祥70線性表上常用的的運(yùn)算基本運(yùn)算基本運(yùn)算初始化線性表初始化線性表表置空表置空求線性表中第求線性表中第i個(gè)元素個(gè)元素查找滿足給定條件的數(shù)據(jù)元素查找滿足給定條件的數(shù)據(jù)元素在線性表的第在線性表的第i個(gè)位置之前插入一個(gè)新的數(shù)據(jù)元素個(gè)位置之前插入一個(gè)新的數(shù)據(jù)元素刪除線性表中的第刪除線性表中的第i個(gè)數(shù)據(jù)元素個(gè)數(shù)據(jù)元素查找表中第查找表中第i個(gè)元素的前驅(qū)個(gè)元素的前驅(qū)查找表中第查找表中第i個(gè)元素的后繼個(gè)元素的后繼按一個(gè)或多個(gè)

4、數(shù)據(jù)項(xiàng)值的遞增或遞減次序重新排列線性表中按一個(gè)或多個(gè)數(shù)據(jù)項(xiàng)值的遞增或遞減次序重新排列線性表中的數(shù)據(jù)元素的數(shù)據(jù)元素實(shí)際應(yīng)用中，根據(jù)不同的要求選擇適當(dāng)?shù)幕具\(yùn)算解實(shí)際應(yīng)用中，根據(jù)不同的要求選擇適當(dāng)?shù)幕具\(yùn)算解決問題決問題抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型對(duì)數(shù)據(jù)的對(duì)數(shù)據(jù)的對(duì)關(guān)系的對(duì)關(guān)系的對(duì)運(yùn)算的對(duì)運(yùn)算的D,S,P通過固有數(shù)據(jù)類型來通過固有數(shù)據(jù)類型來抽象數(shù)據(jù)類型ADT triplet數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象: D=V1,V2,V3數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系: R=,基本操作基本操作:ADT triplet線性表的實(shí)現(xiàn)-順序存儲(chǔ)結(jié)構(gòu)在內(nèi)存中開辟連續(xù)的存儲(chǔ)空間，用連續(xù)的存儲(chǔ)單元在內(nèi)存中開辟連續(xù)的存儲(chǔ)空間，用連續(xù)的存儲(chǔ)單元依次存放線性

5、表的數(shù)據(jù)元素依次存放線性表的數(shù)據(jù)元素順序存儲(chǔ)的線性表，稱為順序存儲(chǔ)的線性表，稱為順序表順序表特點(diǎn)特點(diǎn)邏輯上相鄰的數(shù)據(jù)元素邏輯上相鄰的數(shù)據(jù)元素，其物理位置也相鄰，其物理位置也相鄰利用物理位置上的關(guān)系利用物理位置上的關(guān)系，反映元素的邏輯關(guān)系，反映元素的邏輯關(guān)系順序表的類型定義順序表的示意圖順序表上的基本運(yùn)算插入算法插入算法在線性表的第在線性表的第i個(gè)數(shù)據(jù)元素前，插入一個(gè)新數(shù)個(gè)數(shù)據(jù)元素前，插入一個(gè)新數(shù)據(jù)元素，使線性表的長(zhǎng)度從據(jù)元素，使線性表的長(zhǎng)度從n變成變成n+1(a1, , ai-1, ai, , an)(a1, , ai-1, x, ai, , an) 內(nèi)存內(nèi)存a1a2aiai+1an01i-1

6、 下標(biāo)下標(biāo)len-1ilen12i元素序號(hào)元素序號(hào)i+1lenlen+1內(nèi)存內(nèi)存a1a2aiai+1an01i-1 下標(biāo)下標(biāo)len-1ilen12i元素序號(hào)元素序號(hào)i+1lenlen+1an-1x順序表的插入算法判斷線性表的存儲(chǔ)空間是否已滿判斷線性表的存儲(chǔ)空間是否已滿，若已滿，則，若已滿，則進(jìn)行進(jìn)行“溢出溢出”處理處理檢查檢查i值是否超出允許的范圍值是否超出允許的范圍(1ilen+1)，若超，若超出，則進(jìn)行出，則進(jìn)行“超出超出”處理處理如果上述條件都允許如果上述條件都允許, ,則將最后一個(gè)元素到第則將最后一個(gè)元素到第i i個(gè)元素依次向后移動(dòng)一個(gè)位置個(gè)元素依次向后移動(dòng)一個(gè)位置將新的數(shù)據(jù)元素將新的

7、數(shù)據(jù)元素寫到第寫到第i個(gè)位置上個(gè)位置上線性表的長(zhǎng)度增加線性表的長(zhǎng)度增加1,插入成功插入成功詳見算法詳見算法2.22.2插入算法的時(shí)間復(fù)雜度插入算法的主要時(shí)間用于移動(dòng)數(shù)據(jù)元素，該語句插入算法的主要時(shí)間用于移動(dòng)數(shù)據(jù)元素，該語句循環(huán)執(zhí)行的次數(shù)為循環(huán)執(zhí)行的次數(shù)為n-i+1當(dāng)當(dāng)i=n+1時(shí)，移動(dòng)次數(shù)為時(shí)，移動(dòng)次數(shù)為0當(dāng)當(dāng)i=1時(shí)時(shí),移動(dòng)次數(shù)為移動(dòng)次數(shù)為n算法的最壞情況時(shí)間復(fù)雜度：算法的最壞情況時(shí)間復(fù)雜度：O(n)算法的最好情況時(shí)間復(fù)雜度：算法的最好情況時(shí)間復(fù)雜度：O(1)插入算法的時(shí)間復(fù)雜度假設(shè)在第假設(shè)在第i個(gè)元素之前插入一個(gè)元素的概率為個(gè)元素之前插入一個(gè)元素的概率為Pi，所需移動(dòng)數(shù)據(jù)元素的所需移動(dòng)數(shù)據(jù)

8、元素的平均次數(shù)平均次數(shù)為：為：11)1(niiinPEi nOnTninnEinPnii112)1(1111則若認(rèn)為順序表上的基本運(yùn)算刪除操作刪除操作將線性表的第將線性表的第i個(gè)數(shù)據(jù)元素刪去，使長(zhǎng)為個(gè)數(shù)據(jù)元素刪去，使長(zhǎng)為n的的線性表變成長(zhǎng)為線性表變成長(zhǎng)為n-1的線性表的線性表(a1 ,.,ai-1 ,ai ,ai+1 ,.,an )(a1 ,.,ai-1 ,ai+1 ,.,an )內(nèi)存內(nèi)存a1a2aiai+1an01i-1 下標(biāo)下標(biāo)n-1in12i元素序號(hào)元素序號(hào)i+1nn+1內(nèi)存內(nèi)存a1a2ai+1 下標(biāo)下標(biāo)01i-1n-2in-112i元素序號(hào)元素序號(hào)i+1n-1nanai+2順序表的刪除

9、算法算法思路算法思路判斷判斷i值是否超出允許的范圍值是否超出允許的范圍(1ilen），若），若是，則進(jìn)行是，則進(jìn)行“超出范圍超出范圍”處理；處理；否則，保存第否則，保存第i個(gè)元素的值；個(gè)元素的值；將第將第i個(gè)元素后的所有元素依次向前移動(dòng)一個(gè)元素后的所有元素依次向前移動(dòng)一個(gè)位置；個(gè)位置；線性表長(zhǎng)度減線性表長(zhǎng)度減1，刪除成功，刪除成功詳見算法詳見算法2.32.3刪除算法的時(shí)間復(fù)雜度刪除算法的主要時(shí)間用于移動(dòng)數(shù)據(jù)元素，該循環(huán)刪除算法的主要時(shí)間用于移動(dòng)數(shù)據(jù)元素，該循環(huán)語句執(zhí)行的次數(shù)為語句執(zhí)行的次數(shù)為n-i當(dāng)當(dāng)i=1時(shí)，移動(dòng)時(shí)，移動(dòng)n-1 個(gè)個(gè)當(dāng)當(dāng)i=n時(shí)，不需移動(dòng)時(shí)，不需移動(dòng)算法的最壞情況時(shí)間復(fù)雜度：

10、算法的最壞情況時(shí)間復(fù)雜度：O(n)算法的最好情況時(shí)間復(fù)雜度：算法的最好情況時(shí)間復(fù)雜度：O(1)刪除算法的時(shí)間復(fù)雜度設(shè)刪除第設(shè)刪除第i個(gè)元素的概率為個(gè)元素的概率為qi，所需移動(dòng)數(shù)據(jù)元素，所需移動(dòng)數(shù)據(jù)元素的平均次數(shù)為：的平均次數(shù)為： nOnTninnEdnqnii12)(11則若認(rèn)為inqEniid1順序表的基本運(yùn)算求線性表的長(zhǎng)度求線性表的長(zhǎng)度 詳見算法詳見算法2.12.1順序表上的基本運(yùn)算查找查找查找指定數(shù)據(jù)元素查找指定數(shù)據(jù)元素x在表中的位置序號(hào)，若在表中的位置序號(hào)，若vi=x,則算法返回值為則算法返回值為i+1，若不存在數(shù)，若不存在數(shù)據(jù)元素?fù)?jù)元素x，則返回，則返回0詳見算法詳見算法2.42.4

11、順序存儲(chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)靜態(tài)操作容易實(shí)現(xiàn)靜態(tài)操作容易實(shí)現(xiàn)根據(jù)定位公式容易確定表中元素的存儲(chǔ)位置根據(jù)定位公式容易確定表中元素的存儲(chǔ)位置元素隨機(jī)存取元素隨機(jī)存取動(dòng)態(tài)操作實(shí)現(xiàn)效率較低動(dòng)態(tài)操作實(shí)現(xiàn)效率較低插入和刪除結(jié)點(diǎn)困難插入和刪除結(jié)點(diǎn)困難由于表中的結(jié)點(diǎn)連續(xù)存放，在動(dòng)態(tài)操作時(shí)，為由于表中的結(jié)點(diǎn)連續(xù)存放，在動(dòng)態(tài)操作時(shí)，為了保持元素的連續(xù)性，所以必須將某些結(jié)點(diǎn)向了保持元素的連續(xù)性，所以必須將某些結(jié)點(diǎn)向后或向前依次移動(dòng)后或向前依次移動(dòng)擴(kuò)展不靈活，容易造成空間浪費(fèi)擴(kuò)展不靈活，容易造成空間浪費(fèi)建表時(shí)，若估計(jì)不到表的最大長(zhǎng)度，就難以確定建表時(shí)，若估計(jì)不到表的最大長(zhǎng)度，就難以確定分配的空間，影響數(shù)據(jù)擴(kuò)展分配的空間，影響

12、數(shù)據(jù)擴(kuò)展分配的空間過大，則會(huì)造成預(yù)留空間浪費(fèi)分配的空間過大，則會(huì)造成預(yù)留空間浪費(fèi)作業(yè)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)鏈表鏈表以鏈?zhǔn)浇Y(jié)構(gòu)存儲(chǔ)的線性表以鏈?zhǔn)浇Y(jié)構(gòu)存儲(chǔ)的線性表用一組在物理位置上任意的存儲(chǔ)單元來存儲(chǔ)線用一組在物理位置上任意的存儲(chǔ)單元來存儲(chǔ)線性表的結(jié)點(diǎn)性表的結(jié)點(diǎn)存儲(chǔ)單元可以是相鄰的存儲(chǔ)單元可以是相鄰的也可以是不相鄰的也可以是不相鄰的相鄰存儲(chǔ)單元中的數(shù)據(jù)，不一定是相鄰的結(jié)點(diǎn)相鄰存儲(chǔ)單元中的數(shù)據(jù)，不一定是相鄰的結(jié)點(diǎn) 線性表的單鏈存儲(chǔ)示意圖陳小潔陳小潔張吉祥張吉祥1林春英林春英李小林李小林李清李清張桂林張桂林7155440NULL鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)用一組任意位置的存儲(chǔ)單元存儲(chǔ)線性表的數(shù)據(jù)元素用一組任意位置

13、的存儲(chǔ)單元存儲(chǔ)線性表的數(shù)據(jù)元素結(jié)點(diǎn)間的邏輯關(guān)系借助結(jié)點(diǎn)中的結(jié)點(diǎn)間的邏輯關(guān)系借助結(jié)點(diǎn)中的指針指針實(shí)現(xiàn)實(shí)現(xiàn)每個(gè)數(shù)據(jù)元素，除存儲(chǔ)本身信息外，每個(gè)數(shù)據(jù)元素，除存儲(chǔ)本身信息外，還需存儲(chǔ)其直還需存儲(chǔ)其直接后繼的信息接后繼的信息結(jié)點(diǎn)結(jié)點(diǎn)數(shù)據(jù)域：元素本身信息數(shù)據(jù)域：元素本身信息指針域：指示直接后繼的存儲(chǔ)位置指針域：指示直接后繼的存儲(chǔ)位置 數(shù)據(jù)域數(shù)據(jù)域 指針域指針域單鏈表鏈表中，每個(gè)結(jié)點(diǎn)只包含一個(gè)指針域鏈表中，每個(gè)結(jié)點(diǎn)只包含一個(gè)指針域結(jié)點(diǎn)類型的結(jié)點(diǎn)類型的JAVA語言描述：語言描述：public class Lnode /Lnode為結(jié)點(diǎn)類型為結(jié)點(diǎn)類型 public char data; public Lnode

14、 next;帶頭結(jié)點(diǎn)的單鏈表在單鏈表的第一個(gè)結(jié)點(diǎn)前添加一個(gè)輔助結(jié)點(diǎn)，稱為在單鏈表的第一個(gè)結(jié)點(diǎn)前添加一個(gè)輔助結(jié)點(diǎn)，稱為頭結(jié)點(diǎn)或偽結(jié)點(diǎn)頭結(jié)點(diǎn)或偽結(jié)點(diǎn)頭結(jié)點(diǎn)的數(shù)據(jù)域可以不存儲(chǔ)任何信息，也可以存儲(chǔ)頭結(jié)點(diǎn)的數(shù)據(jù)域可以不存儲(chǔ)任何信息，也可以存儲(chǔ)一些附加信息；一些附加信息；頭結(jié)點(diǎn)的指針域存儲(chǔ)頭結(jié)點(diǎn)的指針域存儲(chǔ)如果頭結(jié)點(diǎn)的指針域?yàn)槿绻^結(jié)點(diǎn)的指針域?yàn)椤翱湛铡?，即，即L.next=NULL，表示該鏈表為空表表示該鏈表為空表單鏈表的定義public class LinkedList implements ListIntf Lnode h=null; /頭結(jié)點(diǎn)頭結(jié)點(diǎn) public void setH(Lnode _

15、h) h=_h; public LinkedList() /構(gòu)造方法構(gòu)造方法 public void insertElementAfter(Lnode p,char x). public Lnode search(char x) . /實(shí)現(xiàn)接口方法實(shí)現(xiàn)接口方法 public int size().; public void clear().; public boolean isEmpty().; public Object get(int i) .; public int indexOf(Object obj) .; public Object getPre(Object obj) .; pu

16、blic Object getNext(Object obj) .; public void insertElementAt(Object obj,int i) .; public Object remove(int i) .; public Object remove(Object obj) .;頭插法建立單鏈表算法思路算法思路1.建立一個(gè)頭結(jié)點(diǎn)，使頭結(jié)點(diǎn)的指針域?yàn)榭战⒁粋€(gè)頭結(jié)點(diǎn)，使頭結(jié)點(diǎn)的指針域?yàn)榭?.建立一個(gè)新結(jié)點(diǎn)建立一個(gè)新結(jié)點(diǎn)P,作為待插入的新結(jié)點(diǎn)作為待插入的新結(jié)點(diǎn)3.給新結(jié)點(diǎn)給新結(jié)點(diǎn)P的數(shù)據(jù)域賦值的數(shù)據(jù)域賦值4.將新將新結(jié)點(diǎn)插入到頭結(jié)點(diǎn)的后面，成為第一結(jié)點(diǎn)插入到頭結(jié)點(diǎn)的后面，成為第

17、一個(gè)數(shù)據(jù)結(jié)點(diǎn)個(gè)數(shù)據(jù)結(jié)點(diǎn)5.是否繼續(xù)？如果繼續(xù)，返回是否繼續(xù)？如果繼續(xù)，返回2，否則跳到，否則跳到66.結(jié)束創(chuàng)建結(jié)束創(chuàng)建,創(chuàng)建成功創(chuàng)建成功詳見算法詳見算法2.52.5尾插法創(chuàng)建單鏈表的算法算法思路算法思路1.申請(qǐng)一個(gè)結(jié)點(diǎn)的空間，作為頭結(jié)點(diǎn)申請(qǐng)一個(gè)結(jié)點(diǎn)的空間，作為頭結(jié)點(diǎn)2.申請(qǐng)一個(gè)結(jié)點(diǎn)的空間，作為待插入的新結(jié)點(diǎn)申請(qǐng)一個(gè)結(jié)點(diǎn)的空間，作為待插入的新結(jié)點(diǎn)3.給新結(jié)點(diǎn)的數(shù)據(jù)域賦值，將新結(jié)點(diǎn)插入到鏈給新結(jié)點(diǎn)的數(shù)據(jù)域賦值，將新結(jié)點(diǎn)插入到鏈表尾，使其成為新的尾結(jié)點(diǎn)表尾，使其成為新的尾結(jié)點(diǎn),其指針域?yàn)槠渲羔樣驗(yàn)閚ull4.是否繼續(xù)？如果繼續(xù)，返回是否繼續(xù)？如果繼續(xù)，返回2，否則跳到，否則跳到55.結(jié)束創(chuàng)建結(jié)束創(chuàng)建

18、,創(chuàng)建成功創(chuàng)建成功詳見算法詳見算法2.62.6求單鏈表的長(zhǎng)度的算法求表中元素的個(gè)數(shù)求表中元素的個(gè)數(shù)算法思想算法思想計(jì)數(shù)器清計(jì)數(shù)器清0令指針令指針p=head.next讓指針讓指針P沿著鏈表的指針域向前移動(dòng)沿著鏈表的指針域向前移動(dòng),每移動(dòng)每移動(dòng)一步一步,計(jì)數(shù)器增計(jì)數(shù)器增1當(dāng)指針當(dāng)指針P 為空為空,表示已經(jīng)到了鏈表尾表示已經(jīng)到了鏈表尾此時(shí)此時(shí),計(jì)數(shù)器中就是結(jié)點(diǎn)個(gè)數(shù)計(jì)數(shù)器中就是結(jié)點(diǎn)個(gè)數(shù)時(shí)間復(fù)雜度：時(shí)間復(fù)雜度：O(n)詳見算法詳見算法2.72.7單鏈表的插入算法插入點(diǎn)插入點(diǎn)qp.next=q.next;q.next=p;插入數(shù)據(jù)插入數(shù)據(jù)在單鏈表的第在單鏈表的第i i個(gè)結(jié)點(diǎn)后，插入一個(gè)新結(jié)點(diǎn)個(gè)結(jié)點(diǎn)后，插

19、入一個(gè)新結(jié)點(diǎn)不需進(jìn)行大量數(shù)據(jù)移動(dòng)，只需找到插入點(diǎn)即可不需進(jìn)行大量數(shù)據(jù)移動(dòng)，只需找到插入點(diǎn)即可算法 在單鏈表的第i個(gè)結(jié)點(diǎn)前，插入值為item的結(jié)點(diǎn)算法思想算法思想尋找第尋找第i-1個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn),即插入點(diǎn)即插入點(diǎn)如果如果找不到插入點(diǎn)找不到插入點(diǎn),插入位置不合適插入位置不合適,無法插無法插入入,返回返回FALSE如果找到插入點(diǎn)如果找到插入點(diǎn),則進(jìn)行則進(jìn)行插入操作插入操作詳見算法詳見算法2.92.9刪除算法 刪除刪除刪除單鏈表上的刪除單鏈表上的第第i個(gè)個(gè)結(jié)點(diǎn)結(jié)點(diǎn)算法思想算法思想刪除單鏈表中某結(jié)點(diǎn)刪除單鏈表中某結(jié)點(diǎn)p的后繼結(jié)點(diǎn)的后繼結(jié)點(diǎn)算法思想算法思想將將q q指向指向p p結(jié)點(diǎn)的直接后繼；結(jié)點(diǎn)的直接后

20、繼；改變指針鏈接，把改變指針鏈接，把q q結(jié)點(diǎn)的直接后繼作為結(jié)點(diǎn)的直接后繼作為p p結(jié)點(diǎn)結(jié)點(diǎn)的直接后繼；的直接后繼；從單鏈表中刪除從單鏈表中刪除q q結(jié)點(diǎn)；結(jié)點(diǎn)；釋放釋放q q結(jié)點(diǎn)空間結(jié)點(diǎn)空間刪除算法 詳見算法詳見算法2.102.10按值查找算法查找單鏈表中是否存在數(shù)據(jù)域?yàn)椴檎覇捂湵碇惺欠翊嬖跀?shù)據(jù)域?yàn)閤的結(jié)點(diǎn)。若的結(jié)點(diǎn)。若有該結(jié)點(diǎn)，則返回指向該結(jié)點(diǎn)的指針，否則返有該結(jié)點(diǎn)，則返回指向該結(jié)點(diǎn)的指針，否則返回空回空算法思路算法思路從第一個(gè)結(jié)點(diǎn)開始掃描整個(gè)單鏈表，逐個(gè)從第一個(gè)結(jié)點(diǎn)開始掃描整個(gè)單鏈表，逐個(gè)比較數(shù)據(jù)域值和比較數(shù)據(jù)域值和x找到該結(jié)點(diǎn)后返回指向該結(jié)點(diǎn)的指針找到該結(jié)點(diǎn)后返回指向該結(jié)點(diǎn)的指針詳見算

21、法詳見算法2.112.11讀取線性表中指定位置的元素讀取單鏈表中的第讀取單鏈表中的第i個(gè)元素。如果找到，則返回第個(gè)元素。如果找到，則返回第i個(gè)結(jié)點(diǎn)的存儲(chǔ)地址，否則返回空個(gè)結(jié)點(diǎn)的存儲(chǔ)地址，否則返回空 算法思路算法思路(1)p從單鏈表的第一個(gè)結(jié)點(diǎn)出發(fā)，并定義從單鏈表的第一個(gè)結(jié)點(diǎn)出發(fā)，并定義j=1(2)在單鏈表中移動(dòng)指針在單鏈表中移動(dòng)指針p，同時(shí)累計(jì)，同時(shí)累計(jì)j (3)通過通過j的累計(jì)查找的累計(jì)查找j=i的結(jié)點(diǎn)的結(jié)點(diǎn)(4)重復(fù)重復(fù)(2)、(3)直到直到p為空或?yàn)榭栈騪指向第指向第i個(gè)元素個(gè)元素詳見算法詳見算法2.122.12單鏈表特點(diǎn)是一種動(dòng)態(tài)存儲(chǔ)結(jié)構(gòu)是一種動(dòng)態(tài)存儲(chǔ)結(jié)構(gòu)指針占用了額外的存儲(chǔ)空間指針占

22、用了額外的存儲(chǔ)空間不能隨機(jī)存取，而是順序存取不能隨機(jī)存取，而是順序存取適合做動(dòng)態(tài)操作適合做動(dòng)態(tài)操作帶頭結(jié)點(diǎn)的單鏈表很多時(shí)候可以使算法簡(jiǎn)化帶頭結(jié)點(diǎn)的單鏈表很多時(shí)候可以使算法簡(jiǎn)化循環(huán)鏈表單循環(huán)鏈表單循環(huán)鏈表單鏈表中最后一個(gè)結(jié)點(diǎn)的鏈域值不是單鏈表中最后一個(gè)結(jié)點(diǎn)的鏈域值不是NULL，而是指向頭結(jié)點(diǎn)，整個(gè)表形成一個(gè)環(huán)而是指向頭結(jié)點(diǎn)，整個(gè)表形成一個(gè)環(huán) 特點(diǎn)特點(diǎn)從表中任意結(jié)點(diǎn)出發(fā)均可找到表中其它的結(jié)點(diǎn)從表中任意結(jié)點(diǎn)出發(fā)均可找到表中其它的結(jié)點(diǎn)操作與單鏈表基本一致操作與單鏈表基本一致,循環(huán)條件不同循環(huán)條件不同帶頭結(jié)點(diǎn)的單鏈表：帶頭結(jié)點(diǎn)的單鏈表：p.next=null帶頭結(jié)點(diǎn)的單循環(huán)鏈表：帶頭結(jié)點(diǎn)的單循環(huán)鏈表：p

23、.next=head單循環(huán)鏈表的查找算法單循環(huán)鏈表的查找算法在單循環(huán)鏈表中查找值為在單循環(huán)鏈表中查找值為x x的結(jié)點(diǎn)的結(jié)點(diǎn)單循環(huán)鏈表的查找算法詳見算法詳見算法2.132.13雙向鏈表每一個(gè)結(jié)點(diǎn)中有兩個(gè)指針域每一個(gè)結(jié)點(diǎn)中有兩個(gè)指針域一個(gè)指向直接后繼一個(gè)指向直接后繼,另一個(gè)指向直接前趨另一個(gè)指向直接前趨這樣的鏈表稱為雙向鏈表這樣的鏈表稱為雙向鏈表結(jié)點(diǎn)描述如下結(jié)點(diǎn)描述如下:public class DulNode char data; DulNode next; DulNode prior; 雙向循環(huán)鏈表 將雙向鏈表中的頭結(jié)點(diǎn)和尾結(jié)點(diǎn)鏈接起來，構(gòu)成雙將雙向鏈表中的頭結(jié)點(diǎn)和尾結(jié)點(diǎn)鏈接起來，構(gòu)成雙向循環(huán)

24、鏈表向循環(huán)鏈表雙向循環(huán)鏈表在雙向環(huán)形鏈表中，指針在雙向環(huán)形鏈表中，指針p指向雙向鏈表中的某指向雙向鏈表中的某結(jié)點(diǎn)，則有如下關(guān)系結(jié)點(diǎn)，則有如下關(guān)系p.next.prior pp.prior.next p雙向鏈表的對(duì)稱性雙向鏈表的對(duì)稱性在雙向循環(huán)鏈表結(jié)點(diǎn)在雙向循環(huán)鏈表結(jié)點(diǎn)p之前插入結(jié)點(diǎn)之前插入結(jié)點(diǎn)s改變指針鏈接的語句有改變指針鏈接的語句有 s.prior=p.prior; p.prior.next=s; s.next=p; p.prior=s;雙向循環(huán)鏈表的插入算法雙向循環(huán)鏈表的插入算法在雙向循環(huán)鏈表的第在雙向循環(huán)鏈表的第i個(gè)結(jié)點(diǎn)之前插入值為個(gè)結(jié)點(diǎn)之前插入值為x的的新結(jié)點(diǎn)。如果成功，返回新結(jié)點(diǎn)。如

25、果成功，返回1，否則，返回，否則，返回0。算法思路算法思路通過通過p的移動(dòng)在雙向鏈表中的移動(dòng)在雙向鏈表中查找第查找第i個(gè)元素個(gè)元素如果找到，則建立一個(gè)新結(jié)點(diǎn)如果找到，則建立一個(gè)新結(jié)點(diǎn)s 給新結(jié)點(diǎn)的數(shù)據(jù)域賦值給新結(jié)點(diǎn)的數(shù)據(jù)域賦值將將s和和p以及以及p的前驅(qū)鏈接起來的前驅(qū)鏈接起來使使s的前驅(qū)是的前驅(qū)是p原來的前驅(qū)原來的前驅(qū)s的后繼是的后繼是p詳見算法詳見算法2.142.14雙向循環(huán)鏈表的刪除算法刪除雙向環(huán)形鏈表的結(jié)點(diǎn)刪除雙向環(huán)形鏈表的結(jié)點(diǎn)p改變指針鏈接的語句有改變指針鏈接的語句有p.prior.next=p.next;p.next.prior=p.prior;雙向循環(huán)鏈表的刪除算法刪除雙向環(huán)形鏈表

26、的第刪除雙向環(huán)形鏈表的第i個(gè)結(jié)點(diǎn)。如果成功，返個(gè)結(jié)點(diǎn)。如果成功，返回回1，否則，返回，否則，返回0。算法思路算法思路通過通過p的移動(dòng)在雙向鏈表中查找第的移動(dòng)在雙向鏈表中查找第i個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)如果找到，改變指針鏈接如果找到，改變指針鏈接使使p的前驅(qū)指向的前驅(qū)指向p的后繼的后繼p的后繼結(jié)點(diǎn)的前驅(qū)指針指向的后繼結(jié)點(diǎn)的前驅(qū)指針指向p原來的前驅(qū)原來的前驅(qū)釋放釋放p詳見算法詳見算法2.152.15線性表順序存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ)的比較從時(shí)間的角度從時(shí)間的角度在按位置查找數(shù)據(jù)、或查找元素的前趨和后繼方在按位置查找數(shù)據(jù)、或查找元素的前趨和后繼方面，順序存儲(chǔ)有較大優(yōu)勢(shì)面，順序存儲(chǔ)有較大優(yōu)勢(shì)在插入數(shù)據(jù)、刪除數(shù)據(jù)時(shí)，鏈?zhǔn)酱鎯?chǔ)

27、有較大的優(yōu)在插入數(shù)據(jù)、刪除數(shù)據(jù)時(shí)，鏈?zhǔn)酱鎯?chǔ)有較大的優(yōu)勢(shì)勢(shì). .因?yàn)樵阪湵碇兄灰薷闹羔樇纯?；在順序表因?yàn)樵阪湵碇兄灰薷闹羔樇纯?；在順序表中則平均要移動(dòng)將近一半的數(shù)據(jù)元素中則平均要移動(dòng)將近一半的數(shù)據(jù)元素從空間的角度從空間的角度順序表的存儲(chǔ)空間是靜態(tài)分配的，在程序執(zhí)行之順序表的存儲(chǔ)空間是靜態(tài)分配的，在程序執(zhí)行之前必須規(guī)定其存儲(chǔ)規(guī)模前必須規(guī)定其存儲(chǔ)規(guī)模動(dòng)態(tài)鏈表的存儲(chǔ)空間是動(dòng)態(tài)分配的，只要內(nèi)存空動(dòng)態(tài)鏈表的存儲(chǔ)空間是動(dòng)態(tài)分配的，只要內(nèi)存空間有空閑，就不會(huì)產(chǎn)生溢出間有空閑，就不會(huì)產(chǎn)生溢出線性表的順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)在操作上的比較順序存儲(chǔ)順序存儲(chǔ)鏈?zhǔn)酱鎯?chǔ)鏈?zhǔn)酱鎯?chǔ)循環(huán)變量循環(huán)變量下標(biāo)變量下標(biāo)變量i指針變量指針

28、變量p初始化初始化i=0head=NULL;或或Head.next=NULL;處理對(duì)象處理對(duì)象aip下一對(duì)象下一對(duì)象i+;p=p.next;循環(huán)條件循環(huán)條件ilenp!=NULL線性表的應(yīng)用順序表的原地逆置順序表的原地逆置設(shè)有一個(gè)具有設(shè)有一個(gè)具有n個(gè)元素的線性表存放在一維數(shù)組個(gè)元素的線性表存放在一維數(shù)組AM的的前前n個(gè)數(shù)組單元中，編寫算法將這個(gè)線性表原地逆置個(gè)數(shù)組單元中，編寫算法將這個(gè)線性表原地逆置本算法的要求：本算法的要求： 將原表中的第一個(gè)元素變成新表中的最后一個(gè)元素將原表中的第一個(gè)元素變成新表中的最后一個(gè)元素 原表中的最后一個(gè)元素變成第一個(gè)元素，使原表中的最后一個(gè)元素變成第一個(gè)元素，使a

29、i變成變成ai-1的直接前驅(qū)。的直接前驅(qū)。詳見算法詳見算法2.232.23線性表的應(yīng)用單鏈表的原地逆置單鏈表的原地逆置 算法思想算法思想 可以在遍歷表時(shí)，將各結(jié)點(diǎn)的指針逆轉(zhuǎn)，從原表的可以在遍歷表時(shí)，將各結(jié)點(diǎn)的指針逆轉(zhuǎn)，從原表的第一個(gè)結(jié)點(diǎn)開始，頭結(jié)點(diǎn)的指針在最后修改成指向原第一個(gè)結(jié)點(diǎn)開始，頭結(jié)點(diǎn)的指針在最后修改成指向原表的最后一個(gè)結(jié)點(diǎn)，即新表的第一個(gè)結(jié)點(diǎn)。表的最后一個(gè)結(jié)點(diǎn)，即新表的第一個(gè)結(jié)點(diǎn)。詳見算法詳見算法2.242.24線性表的應(yīng)用有序單鏈表的合并有序單鏈表的合并將兩個(gè)按元素值遞增有序的單鏈表將兩個(gè)按元素值遞增有序的單鏈表A和和B，歸并成一個(gè)按，歸并成一個(gè)按元素值遞增有序排列的單鏈表元素值遞

30、增有序排列的單鏈表C。 對(duì)兩個(gè)或兩個(gè)以上的、結(jié)點(diǎn)按元素值有序排列的單鏈表進(jìn)行對(duì)兩個(gè)或兩個(gè)以上的、結(jié)點(diǎn)按元素值有序排列的單鏈表進(jìn)行操作時(shí)，應(yīng)采用操作時(shí)，應(yīng)采用“”的方法。的方法。 從兩表的第一個(gè)結(jié)點(diǎn)開始沿著鏈表逐個(gè)比較對(duì)應(yīng)元素，復(fù)制從兩表的第一個(gè)結(jié)點(diǎn)開始沿著鏈表逐個(gè)比較對(duì)應(yīng)元素，復(fù)制小的數(shù)據(jù)元素并插入小的數(shù)據(jù)元素并插入C表尾。表尾。當(dāng)兩表中之一已到表尾，則復(fù)制另一個(gè)鏈表的剩余部分，插當(dāng)兩表中之一已到表尾，則復(fù)制另一個(gè)鏈表的剩余部分，插入到入到C表尾。表尾。詳見算法詳見算法2.252.25一元多項(xiàng)式求和一元多項(xiàng)式求和nnnxPxPxPPxP2210)(),(210nPPPPP200001000231)(xxxSemmnxPxPxPxPee2121)(為非零系數(shù)）（iPemee210 emPePePm，2121線性表的應(yīng)用17787178522117)()()(9228)(5937)(xxxxBxAxCxxxxBxxxxA運(yùn)算規(guī)則算法描述詳見算法詳見算法2.252.25線性表的應(yīng)用一元多項(xiàng)式可用帶頭結(jié)點(diǎn)的單鏈表來表示，每個(gè)結(jié)點(diǎn)表示多項(xiàng)一元多項(xiàng)式可用帶頭結(jié)點(diǎn)的單鏈表來表示，每個(gè)結(jié)點(diǎn)表示多項(xiàng)式的一項(xiàng)，包括系數(shù)域、指數(shù)域、指針域。結(jié)點(diǎn)類型定義如下：式的一項(xiàng)，包括系數(shù)域、指數(shù)域、指針域。結(jié)點(diǎn)類型定義如下：class JD i