第2章 線性表3

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

2、性表中的數(shù)據(jù)元素。據(jù)元素。（地址可以是連續(xù)的，也可以不連續(xù)）（地址可以是連續(xù)的，也可以不連續(xù)）一一. 單鏈表單鏈表數(shù)據(jù)域數(shù)據(jù)域(存儲存儲數(shù)據(jù)元素數(shù)據(jù)元素信息的域信息的域) +指針域指針域(存儲存儲直接后繼直接后繼存儲位置的域存儲位置的域) = 結(jié)點結(jié)點 (表示數(shù)據(jù)元素的表示數(shù)據(jù)元素的存儲映象存儲映象)指針域指針域(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存儲地址1713192531374331H頭指針6頭結(jié)點頭結(jié)點: :在單鏈表在單鏈表第一個結(jié)點前第一個結(jié)點前附設一個結(jié)點叫附設一個結(jié)點叫頭結(jié)頭結(jié)點點。令令頭結(jié)點頭結(jié)點中中指針域指針域的指針指向的指針指向第一個元素第一個元素結(jié)點，并結(jié)點，并令令頭指針頭指針指向指向頭結(jié)點頭結(jié)點。通常稱這類單鏈表為通常稱這類單鏈表為 帶頭結(jié)點的單鏈表帶頭結(jié)點的單鏈表 。a1an a2頭結(jié)點頭結(jié)點指針域指針域為為空，空，表示線性表為表示線性表為空表空表。7頭結(jié)點頭結(jié)點 a1 a2 . an 頭指針頭指針頭指針空指針空指針線性表為空表時，線性表為空表時，頭結(jié)點的指針域

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

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

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

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

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

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

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

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

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

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

14、-1aiai+1ai-124刪除一個結(jié)點，刪除一個結(jié)點，刪除結(jié)點數(shù)據(jù)元素刪除結(jié)點數(shù)據(jù)元素的同時，還要的同時，還要刪除刪除該結(jié)點的指針該結(jié)點的指針。但是，不能因為結(jié)點的刪除造成單鏈表的但是，不能因為結(jié)點的刪除造成單鏈表的脫節(jié)脫節(jié)，所以，所以，刪除操作的關鍵在于單鏈表刪除操作的關鍵在于單鏈表內(nèi)部關系的調(diào)整內(nèi)部關系的調(diào)整。在單鏈表中刪除第在單鏈表中刪除第 i 個結(jié)點的個結(jié)點的基本操作基本操作為：為：找到線性找到線性表中第表中第i-1個結(jié)點個結(jié)點，修改其指向，修改其指向后繼后繼的指針。的指針。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é)點帶頭結(jié)點)的單鏈表中第的單鏈表中第 i 個結(jié)點個結(jié)點 p = L; j = 0; while(p-next & j next; +j; / 尋找第尋找第 i 個結(jié)點，并令個結(jié)點，并令 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é)點釋放結(jié)點 return OK; / ListDelete_L算法時間復雜度為算法時間復雜度為: O( ListLength(L) )27鏈表是一個鏈表是一個動態(tài)的結(jié)構(gòu)動態(tài)的結(jié)構(gòu)，它不需要預分配連續(xù)的存儲，它不需要預分配連續(xù)的存儲空間，因此生成鏈表的過程是一個空間，因此生成鏈表的過程是一個結(jié)點結(jié)點“逐個插入逐個插入” 的過程。的過程?！纠磕嫖恍蜉斎搿纠磕嫖恍蜉斎?n 個數(shù)據(jù)元素的值，建立帶頭結(jié)點的個數(shù)據(jù)元素的值，建立帶頭結(jié)點的單鏈表。單鏈表。28操作步驟：操作步驟：1. 建立一個空表；建立一個空表；2. 輸入數(shù)據(jù)元素

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

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

19、頭結(jié)點的單鏈表先建立一個帶頭結(jié)點的單鏈表 for (i = n; i 0; -i) p = (LinkList) malloc (sizeof (LNode); / 創(chuàng)建結(jié)點創(chuàng)建結(jié)點 scanf(&p-data); / 輸入數(shù)據(jù)元素值輸入數(shù)據(jù)元素值 p-next = L-next; L-next = p; / 插入結(jié)點插入結(jié)點 / CreateList_L算法時間復雜度為算法時間復雜度為: O( ListLength(L) )3132分析：分析：設設 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 表當前的表尾表當前的表尾 /pa和和pb分別指向分別指向La表和表和Lb表中第一個結(jié)點。表

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

22、還丟失了一些順序表有的長處，如線性表的“表長表長”（單鏈表中表長是一個隱含值，必須從前到后遍歷整（單鏈表中表長是一個隱含值，必須從前到后遍歷整個表才能得到）個表才能得到）和數(shù)據(jù)元素在線性表中的和數(shù)據(jù)元素在線性表中的“位序位序”；(3)不便于在表尾插入元素不便于在表尾插入元素，需遍歷整個表才能找到插入，需遍歷整個表才能找到插入的位置。的位置。 36【例【例2-1】假設】假設:有兩個集合有兩個集合 A 和和 B 分別用兩個線性表分別用兩個線性表 LA 和和 LB 表示?，F(xiàn)求一個新的集合表示?，F(xiàn)求一個新的集合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;當以當以鏈式映像鏈式映像實現(xiàn)抽象數(shù)據(jù)類型線性表時為實現(xiàn)抽象數(shù)據(jù)類型線性表時為: O( ListLength(La)ListLength(Lb) )單單鏈鏈