第2章 線性表3

1、12.1 線性表的邏輯結(jié)構(gòu)線性表的邏輯結(jié)構(gòu)2.2 線性表的順序表示和實(shí)現(xiàn)線性表的順序表示和實(shí)現(xiàn)2.3 線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)2.4 一元多項(xiàng)式的表示一元多項(xiàng)式的表示22.3 線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)特點(diǎn)：用一組地址特點(diǎn)：用一組地址任意任意的存儲(chǔ)單元存放線性表中的數(shù)的存儲(chǔ)單元存放線性表中的數(shù)據(jù)元素。據(jù)元素。（地址可以是連續(xù)的，也可以不連續(xù)）（地址可以是連續(xù)的，也可以不連續(xù)）一一. 單鏈表單鏈表指針域指針域(next)(next)數(shù)據(jù)域數(shù)據(jù)域(data)(data)32.3 線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)特點(diǎn)：用一組地址特點(diǎn)：用一組地址任意任意的存儲(chǔ)單元存放線性表中的數(shù)的存儲(chǔ)單元存放線

2、性表中的數(shù)據(jù)元素。據(jù)元素。（地址可以是連續(xù)的，也可以不連續(xù)）（地址可以是連續(xù)的，也可以不連續(xù)）一一. 單鏈表單鏈表數(shù)據(jù)域數(shù)據(jù)域(存儲(chǔ)存儲(chǔ)數(shù)據(jù)元素?cái)?shù)據(jù)元素信息的域信息的域) +指針域指針域(存儲(chǔ)存儲(chǔ)直接后繼直接后繼存儲(chǔ)位置的域存儲(chǔ)位置的域) = 結(jié)點(diǎn)結(jié)點(diǎn) (表示數(shù)據(jù)元素的表示數(shù)據(jù)元素的存儲(chǔ)映象存儲(chǔ)映象)指針域指針域(next)(next)數(shù)據(jù)域數(shù)據(jù)域(data)(data)4a1ana25ZHAOQIANSUNLIZHOUWUZHENGWANGH例例:線性表線性表(ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)43131NULL3771925數(shù)據(jù)域數(shù)據(jù)域指針域指針域LI

3、QIANSUNWANGWUZHAOZHENGZHOU存儲(chǔ)地址1713192531374331H頭指針6頭結(jié)點(diǎn)頭結(jié)點(diǎn): :在單鏈表在單鏈表第一個(gè)結(jié)點(diǎn)前第一個(gè)結(jié)點(diǎn)前附設(shè)一個(gè)結(jié)點(diǎn)叫附設(shè)一個(gè)結(jié)點(diǎn)叫頭結(jié)頭結(jié)點(diǎn)點(diǎn)。令令頭結(jié)點(diǎn)頭結(jié)點(diǎn)中中指針域指針域的指針指向的指針指向第一個(gè)元素第一個(gè)元素結(jié)點(diǎn)，并結(jié)點(diǎn)，并令令頭指針頭指針指向指向頭結(jié)點(diǎn)頭結(jié)點(diǎn)。通常稱這類單鏈表為通常稱這類單鏈表為 帶頭結(jié)點(diǎn)的單鏈表帶頭結(jié)點(diǎn)的單鏈表 。a1an a2頭結(jié)點(diǎn)頭結(jié)點(diǎn)指針域指針域?yàn)闉榭?，空，表示線性表為表示線性表為空表空表。7頭結(jié)點(diǎn)頭結(jié)點(diǎn) a1 a2 . an 頭指針頭指針頭指針空指針空指針線性表為空表時(shí)，線性表為空表時(shí)，頭結(jié)點(diǎn)的指針域

4、為空頭結(jié)點(diǎn)的指針域?yàn)榭?帶頭結(jié)點(diǎn)鏈表的引入是為了使帶頭結(jié)點(diǎn)鏈表的引入是為了使算法算法判空判空和和處理處理一致。一致。如果不特別聲明的話，那么以后各節(jié)中討論的單鏈如果不特別聲明的話，那么以后各節(jié)中討論的單鏈表都指的是這種表都指的是這種帶頭結(jié)點(diǎn)帶頭結(jié)點(diǎn)的鏈表。的鏈表。 8Typedef struct LNode ElemType data; / 數(shù)據(jù)域數(shù)據(jù)域 struct Lnode *next; / 指針域指針域 LNode, *LinkList; 二二. 結(jié)點(diǎn)和單鏈表的結(jié)點(diǎn)和單鏈表的 C 語(yǔ)言描述語(yǔ)言描述LinkList L； / L 為單鏈表的為單鏈表的頭指針頭指針9data nextp 表

5、示所指向結(jié)點(diǎn)占據(jù)內(nèi)存段的表示所指向結(jié)點(diǎn)占據(jù)內(nèi)存段的起始地址起始地址(*p)表示表示p所指向的所指向的結(jié)點(diǎn)結(jié)點(diǎn)(*p).data p-data表示表示p所指向結(jié)點(diǎn)的所指向結(jié)點(diǎn)的數(shù)據(jù)域數(shù)據(jù)域(*p).next p-next表示表示p所指向結(jié)點(diǎn)的所指向結(jié)點(diǎn)的指針域指針域101112三、單鏈表操作的實(shí)現(xiàn)三、單鏈表操作的實(shí)現(xiàn)GetElem(L, i, &e) / 取第取第i i個(gè)數(shù)據(jù)元素個(gè)數(shù)據(jù)元素ListInsert(&L, i, e) / 插入插入數(shù)據(jù)元素?cái)?shù)據(jù)元素ListDelete(&L, i, &e) / 刪除刪除數(shù)據(jù)元素?cái)?shù)據(jù)元素ClearList(&L) / 重置線性表為重置線性表為空表空表In

6、itList(&L ) / 初始化初始化 DestroyList(&L) / 銷毀銷毀線性表線性表13單鏈表初始化操作實(shí)現(xiàn)：?jiǎn)捂湵沓跏蓟僮鲗?shí)現(xiàn)：OVERFLOW三、單鏈表操作的實(shí)現(xiàn)三、單鏈表操作的實(shí)現(xiàn)14單鏈表銷毀結(jié)構(gòu)操作實(shí)現(xiàn)：?jiǎn)捂湵礓N毀結(jié)構(gòu)操作實(shí)現(xiàn)：/銷毀以銷毀以L為頭指針為頭指針的單鏈表，釋放鏈表中的單鏈表，釋放鏈表中所有結(jié)點(diǎn)空間所有結(jié)點(diǎn)空間L所指結(jié)點(diǎn)的所指結(jié)點(diǎn)的指針域指針域內(nèi)容賦值給內(nèi)容賦值給L.即即L指向指向L的后繼結(jié)點(diǎn)的后繼結(jié)點(diǎn).為安全起見，置為安全起見，置L為為 “空空”，以防止對(duì)系統(tǒng)空間的訪問。以防止對(duì)系統(tǒng)空間的訪問。 15操作 ClearList(&L) 的實(shí)現(xiàn)：void C

7、learList(&L) / 將單鏈表置為一個(gè)將單鏈表置為一個(gè)空表空表/ 從從第第1個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)開始依次刪除開始依次刪除 while (L-next) p=L-next; L-next=p-next; delete p; / free(p); / ClearList算法時(shí)間復(fù)雜度為算法時(shí)間復(fù)雜度為: O( ListLength(L) )p所指結(jié)點(diǎn)的所指結(jié)點(diǎn)的指針域指針域內(nèi)容內(nèi)容賦值給賦值給L的指針域。的指針域。即即L的指針域的指針域指向指向p的的后后繼繼結(jié)點(diǎn)結(jié)點(diǎn).16線性表的操作 GetElem(L, i, &e) 的實(shí)現(xiàn)：例：查找第3個(gè)元素L211830754256pppj1 2 33017

8、查找第查找第 i 個(gè)數(shù)據(jù)元素的基本操作為：個(gè)數(shù)據(jù)元素的基本操作為：移動(dòng)指針移動(dòng)指針p，比，比較較 j 和和 i 。 單鏈表是一種單鏈表是一種順序存取順序存取的結(jié)構(gòu)，整個(gè)鏈表的存取必的結(jié)構(gòu)，整個(gè)鏈表的存取必須須從頭指針從頭指針開始進(jìn)行，為找第開始進(jìn)行，為找第 i 個(gè)數(shù)據(jù)元素，必須先個(gè)數(shù)據(jù)元素，必須先找到第找到第 i-1 個(gè)數(shù)據(jù)元素。個(gè)數(shù)據(jù)元素。因此，不論因此，不論 i 為多少，都必須為多少，都必須從頭結(jié)點(diǎn)從頭結(jié)點(diǎn)開始開始“點(diǎn)數(shù)點(diǎn)數(shù)”， 一直數(shù)到第一直數(shù)到第 i 個(gè)為止。個(gè)為止。頭結(jié)點(diǎn)頭結(jié)點(diǎn)可看成是可看成是第第0個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)。單鏈表是單鏈表是非隨機(jī)存儲(chǔ)非隨機(jī)存儲(chǔ)的結(jié)構(gòu)。的結(jié)構(gòu)。令指針令指針 p 始

9、終指向始終指向線性表中線性表中第第 j 個(gè)個(gè)數(shù)據(jù)元素。數(shù)據(jù)元素。18Status GetElem_L(LinkList L, int i, ElemType &e) / L是帶頭結(jié)點(diǎn)的鏈表的頭指針，以是帶頭結(jié)點(diǎn)的鏈表的頭指針，以 e 返回第返回第 i 個(gè)元素個(gè)元素 p = L-next; j = 1; / p指向第一個(gè)結(jié)點(diǎn)，指向第一個(gè)結(jié)點(diǎn)，j為計(jì)數(shù)器為計(jì)數(shù)器 while (p & jnext; +j; / 順指針向后查找，直到順指針向后查找，直到 p 指向第指向第 i 個(gè)元素或個(gè)元素或 p 為空為空 if ( !p | ji ) return ERROR; / 第第 i 個(gè)元素不存在個(gè)元素不存

10、在 e = p-data; / 取得第取得第 i 個(gè)元素個(gè)元素 return OK; / GetElem_L基本操作：比較基本操作：比較i和和j并后移指針并后移指針p算法時(shí)間復(fù)雜度為算法時(shí)間復(fù)雜度為: O( ListLength(L) )19ai-1線性表的操作 ListInsert(&L, i, e) 的實(shí)現(xiàn)：加工型操作，修改對(duì)象的加工型操作，修改對(duì)象的邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)；邏輯結(jié)構(gòu)邏輯結(jié)構(gòu) 變?yōu)樽優(yōu)?和和 ；在單鏈表中，意味著一個(gè)指針變?yōu)閮蓚€(gè)指針。在單鏈表中，意味著一個(gè)指針變?yōu)閮蓚€(gè)指針。 eaiai-120因此，在單鏈表中第因此，在單鏈表中第 i 個(gè)結(jié)點(diǎn)之前進(jìn)行插入的個(gè)結(jié)點(diǎn)之前進(jìn)行插入的基本操

11、基本操作作為：找到線性表中為：找到線性表中第第i-1個(gè)個(gè)結(jié)點(diǎn)，然后結(jié)點(diǎn)，然后修改修改其指向其指向后后繼繼的指針。的指針?？梢?，為插入數(shù)據(jù)元素可見，為插入數(shù)據(jù)元素e，首先要生成一個(gè)，首先要生成一個(gè)數(shù)據(jù)域?yàn)閿?shù)據(jù)域?yàn)閑的結(jié)點(diǎn)的結(jié)點(diǎn)，然后插入在單鏈表中。，然后插入在單鏈表中。在鏈表中在鏈表中插入結(jié)點(diǎn)插入結(jié)點(diǎn)只需要只需要修改指針修改指針。但同時(shí)，若要。但同時(shí)，若要在在第第 i 個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)之前插入元素，修改的是之前插入元素，修改的是第第 i-1 個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)的的指針。指針。21Status ListInsert_L(LinkList &L, int i, ElemType e) / L 為帶頭結(jié)點(diǎn)的單鏈

12、表的頭指針，為帶頭結(jié)點(diǎn)的單鏈表的頭指針，/ 在第在第 i 個(gè)結(jié)點(diǎn)之前插入新的數(shù)據(jù)元素個(gè)結(jié)點(diǎn)之前插入新的數(shù)據(jù)元素 e p = L; j = 0; while (p & j next; +j; / 尋找第尋找第 i-1 個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn) if (!p | j i-1) return ERROR; / i 大于表長(zhǎng)或者小于大于表長(zhǎng)或者小于1 s = (LinkList) malloc (sizeof (LNode); / 生成新結(jié)點(diǎn)生成新結(jié)點(diǎn) s （空結(jié)點(diǎn)）（空結(jié)點(diǎn)） s = new LNode; （C+） If(!s) exit(OVERFLOW);/存儲(chǔ)分配失敗存儲(chǔ)分配失?。ㄏ马?yè)）（下頁(yè)）22 s-

13、data = e; / 為新結(jié)點(diǎn)為新結(jié)點(diǎn) s 賦值賦值(e) s-next = p-next; / 修改新結(jié)點(diǎn)修改新結(jié)點(diǎn) s 指針指針 p-next = s; / 插入新結(jié)點(diǎn)插入新結(jié)點(diǎn) s return OK; / ListInsert_L算法時(shí)間復(fù)雜度為算法時(shí)間復(fù)雜度為: O( ListLength(L) ) eai-1aiai-1sp23線性表的操作 ListDelete (&L, i, &e) 的實(shí)現(xiàn)：加工型操作加工型操作，修改對(duì)象為，修改對(duì)象為邏輯結(jié)構(gòu)；邏輯結(jié)構(gòu)；邏輯結(jié)構(gòu)邏輯結(jié)構(gòu) 和和 改變?yōu)楦淖優(yōu)?；在單鏈表中，意味著兩個(gè)指針變?yōu)橐粋€(gè)指針。在單鏈表中，意味著兩個(gè)指針變?yōu)橐粋€(gè)指針。ai

14、-1aiai+1ai-124刪除一個(gè)結(jié)點(diǎn)，刪除一個(gè)結(jié)點(diǎn)，刪除結(jié)點(diǎn)數(shù)據(jù)元素刪除結(jié)點(diǎn)數(shù)據(jù)元素的同時(shí)，還要的同時(shí)，還要?jiǎng)h除刪除該結(jié)點(diǎn)的指針該結(jié)點(diǎn)的指針。但是，不能因?yàn)榻Y(jié)點(diǎn)的刪除造成單鏈表的但是，不能因?yàn)榻Y(jié)點(diǎn)的刪除造成單鏈表的脫節(jié)脫節(jié)，所以，所以，刪除操作的關(guān)鍵在于單鏈表刪除操作的關(guān)鍵在于單鏈表內(nèi)部關(guān)系的調(diào)整內(nèi)部關(guān)系的調(diào)整。在單鏈表中刪除第在單鏈表中刪除第 i 個(gè)結(jié)點(diǎn)的個(gè)結(jié)點(diǎn)的基本操作基本操作為：為：找到線性找到線性表中第表中第i-1個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)，修改其指向，修改其指向后繼后繼的指針。的指針。25ai-1aiai+1ai-1pqq = p-next; p-next = q-next; e = q-da

15、ta; delete q;26Status ListDelete_L(LinkList &L, int i, ElemType &e) / 刪除以刪除以 L 為頭指針為頭指針(帶頭結(jié)點(diǎn)帶頭結(jié)點(diǎn))的單鏈表中第的單鏈表中第 i 個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn) p = L; j = 0; while(p-next & j next; +j; / 尋找第尋找第 i 個(gè)結(jié)點(diǎn)，并令個(gè)結(jié)點(diǎn)，并令 p 指向其前趨指向其前趨(ai-1) if (!(p-next) | j i-1) return ERROR; / 刪除位置不合理刪除位置不合理 q = p-next; p-next = q-next; / 修改指針修改指針 e =

16、 q-data; delete q; / free(q);(C+) 釋放結(jié)點(diǎn)釋放結(jié)點(diǎn) return OK; / ListDelete_L算法時(shí)間復(fù)雜度為算法時(shí)間復(fù)雜度為: O( ListLength(L) )27鏈表是一個(gè)鏈表是一個(gè)動(dòng)態(tài)的結(jié)構(gòu)動(dòng)態(tài)的結(jié)構(gòu)，它不需要預(yù)分配連續(xù)的存儲(chǔ)，它不需要預(yù)分配連續(xù)的存儲(chǔ)空間，因此生成鏈表的過程是一個(gè)空間，因此生成鏈表的過程是一個(gè)結(jié)點(diǎn)結(jié)點(diǎn)“逐個(gè)插入逐個(gè)插入” 的過程。的過程。【例】逆位序輸入【例】逆位序輸入 n 個(gè)數(shù)據(jù)元素的值，建立帶頭結(jié)點(diǎn)的個(gè)數(shù)據(jù)元素的值，建立帶頭結(jié)點(diǎn)的單鏈表。單鏈表。28操作步驟：操作步驟：1. 建立一個(gè)空表；建立一個(gè)空表；2. 輸入數(shù)據(jù)元素

17、輸入數(shù)據(jù)元素an，建立結(jié)點(diǎn)并插入；建立結(jié)點(diǎn)并插入；3. 輸入數(shù)據(jù)元素輸入數(shù)據(jù)元素an-1，建立結(jié)點(diǎn)并插入；建立結(jié)點(diǎn)并插入；ananan-14. 依次類推，直至輸入依次類推，直至輸入a1為止。為止。29void CreateList_L(LinkList &L, int n) /C+版版/ 逆序輸入逆序輸入 n 個(gè)數(shù)據(jù)元素，建立帶頭結(jié)點(diǎn)的單鏈表個(gè)數(shù)據(jù)元素，建立帶頭結(jié)點(diǎn)的單鏈表 L = new LNode; if (!L) exit(1); L-next = NULL; / 先建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表先建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表 for (i = n; i 0; -i) p = new LNode;

18、 if (!p) exit(1); / 創(chuàng)建結(jié)點(diǎn)創(chuàng)建結(jié)點(diǎn) cin p-data; / 輸入數(shù)據(jù)元素值輸入數(shù)據(jù)元素值 p-next = L-next; L-next = p; / 插入結(jié)點(diǎn)插入結(jié)點(diǎn) / CreateList_L算法時(shí)間復(fù)雜度為算法時(shí)間復(fù)雜度為: O( ListLength(L) )30void CreateList_L(LinkList &L, int n) /C版版/ 逆序輸入逆序輸入 n 個(gè)數(shù)據(jù)元素，建立帶頭結(jié)點(diǎn)的單鏈表個(gè)數(shù)據(jù)元素，建立帶頭結(jié)點(diǎn)的單鏈表 L = (LinkList) malloc (sizeof (LNode); L-next = NULL; / 先建立一個(gè)帶

19、頭結(jié)點(diǎn)的單鏈表先建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表 for (i = n; i 0; -i) p = (LinkList) malloc (sizeof (LNode); / 創(chuàng)建結(jié)點(diǎn)創(chuàng)建結(jié)點(diǎn) scanf(&p-data); / 輸入數(shù)據(jù)元素值輸入數(shù)據(jù)元素值 p-next = L-next; L-next = p; / 插入結(jié)點(diǎn)插入結(jié)點(diǎn) / CreateList_L算法時(shí)間復(fù)雜度為算法時(shí)間復(fù)雜度為: O( ListLength(L) )3132分析：分析：設(shè)設(shè) La = (a1, , ai, , an), Lb = (b1, , bj, , bm) Lc = (c1, , ck, , cm+n)且已由且

20、已由(a1, , ai-1)和和(b1, ,bj-1)歸并得歸并得 (c1, , ck-1)則則 jijjiikbabbaack = 1, 2, , m+n33/已知單鏈線性表已知單鏈線性表 La 和和 Lb 的元素按值非遞減排列。的元素按值非遞減排列。 /本算法歸并本算法歸并 La 和和 Lb 得到新的單鏈線性表得到新的單鏈線性表 Lc， Lc /的元素也按值非遞減排列。操作之后的元素也按值非遞減排列。操作之后 La 和和 Lb 消失消失/ 建空表，建空表，Lc 為頭指針，為頭指針，rc指示指示 Lc 表當(dāng)前的表尾表當(dāng)前的表尾 /pa和和pb分別指向分別指向La表和表和Lb表中第一個(gè)結(jié)點(diǎn)。表

21、中第一個(gè)結(jié)點(diǎn)。34/ 將將 *pa 插入插入Lc表，指針表，指針 pa 后移后移/ if/ 將將 *pb 插入插入Lc表，指針表，指針 pb 后移后移/ else/ while/ 插入剩余段插入剩余段/釋放釋放La和和Lb的頭結(jié)點(diǎn)的頭結(jié)點(diǎn)/ MergeList_L35單鏈表優(yōu)點(diǎn)：?jiǎn)捂湵韮?yōu)點(diǎn)：(1) 能能有效利用有效利用存儲(chǔ)空間；存儲(chǔ)空間；(2) 用用“指針指針”指示數(shù)據(jù)元素之間的后繼關(guān)系，便于進(jìn)行指示數(shù)據(jù)元素之間的后繼關(guān)系，便于進(jìn)行“插入插入”、“刪除刪除”等操作。等操作。單鏈表缺點(diǎn)：?jiǎn)捂湵砣秉c(diǎn)：(1)不能隨機(jī)存取不能隨機(jī)存取數(shù)據(jù)元素?cái)?shù)據(jù)元素 ；(2)它還丟失了一些順序表有的長(zhǎng)處，如線性表的它

22、還丟失了一些順序表有的長(zhǎng)處，如線性表的“表長(zhǎng)表長(zhǎng)”（單鏈表中表長(zhǎng)是一個(gè)隱含值，必須從前到后遍歷整（單鏈表中表長(zhǎng)是一個(gè)隱含值，必須從前到后遍歷整個(gè)表才能得到）個(gè)表才能得到）和數(shù)據(jù)元素在線性表中的和數(shù)據(jù)元素在線性表中的“位序位序”；(3)不便于在表尾插入元素不便于在表尾插入元素，需遍歷整個(gè)表才能找到插入，需遍歷整個(gè)表才能找到插入的位置。的位置。 36【例【例2-1】假設(shè)】假設(shè):有兩個(gè)集合有兩個(gè)集合 A 和和 B 分別用兩個(gè)線性表分別用兩個(gè)線性表 LA 和和 LB 表示?，F(xiàn)求一個(gè)新的集合表示?，F(xiàn)求一個(gè)新的集合AAB。void union(List &La, List Lb) La_len = Lis

23、tLength(La); Lb_len =ListLength(Lb); for (i = 1; i = Lb_len; i+) GetElem(Lb, i, e); if (!LocateElem(La, e, equal( ) ListInsert(La, +La_len, e); /for / union控制結(jié)構(gòu)：控制結(jié)構(gòu)：基本操作：基本操作：GetElemLocateElemListInsertfor 循環(huán)循環(huán)37void union( SqList &la, SqList lb) la_len=la.length; lb_len=lb.length;bool find=false;for( int i=0;i=lb_len-1;i+) for( int j=0;jnext; LNode * pre=lb;while(q) p=la-next;while(p) if(q-data= =p-data) break; else p=p-next;if(!p) pre-next=q-next; q-next=la-next; la-next=q; else pre=q; q=pre-next;當(dāng)以當(dāng)以鏈?zhǔn)接诚矜準(zhǔn)接诚駥?shí)現(xiàn)抽象數(shù)據(jù)類型線性表時(shí)為實(shí)現(xiàn)抽象數(shù)據(jù)類型線性表時(shí)為: O( ListLength(La)ListLength(Lb) )單單鏈鏈