數(shù)據(jù)結(jié)構(gòu)課件：第2章 線性表1鏈式

1、一元多項式的表示及相加第2章 線性表線性表的類型定義線性表的順序表示和實現(xiàn)線性表的鏈式表示和實現(xiàn)2.3 線性表的鏈式表示及實現(xiàn)線性表的鏈式表示線性表的鏈式實現(xiàn)鏈表的運算效率分析線性表的鏈式表示邏輯上相鄰，物理上不一定相鄰 2.3 線性表的鏈式表示及實現(xiàn) a 201BH b 1087H z NULL a1 a2 an / HeadHeadDataLinkDataLinkDataLinkDataLink鏈表存放示意圖如下：(a，b，c，d，e , z)線性表的鏈式表示線性表的鏈式存儲結(jié)構(gòu)，也稱為鏈表。數(shù)據(jù)元素通過指針表示數(shù)據(jù)元素之間的關(guān)系。 2.3 線性表的鏈式表示及實現(xiàn) a1 a2 an / H

2、ead特點1：每個存儲結(jié)點都包含兩部分：數(shù)據(jù)和 。特點2：在單鏈表中，除了首元結(jié)點外，任一結(jié)點的存儲位置 由 指示。 其直接前驅(qū)結(jié)點的鏈域的值指針域(鏈域)線性鏈表的有關(guān)術(shù)語結(jié)點: 數(shù)據(jù)元素的存儲映像。由數(shù)據(jù)域和指針域兩部分組成； 鏈表: n個結(jié)點由指針鏈組成一個鏈表。它是線性表的鏈式存儲映像，稱為鏈式存儲結(jié)構(gòu)2.3 線性表的鏈式表示及實現(xiàn)信息域 指針域結(jié)點的結(jié)構(gòu) info next a1 a2 an / Head線性鏈表的有關(guān)術(shù)語頭指針: 是指向鏈表中第一個結(jié)點(或為頭結(jié)點或為首元結(jié)點)的指針。單鏈表可由一個頭指針唯一確定。2.3 線性表的鏈式表示及實現(xiàn) a1 a2 an / Head頭指針

3、線性鏈表的有關(guān)術(shù)語頭結(jié)點: 是在鏈表的首元結(jié)點之前附設(shè)的一個結(jié)點；數(shù)據(jù)域內(nèi)只放空表標志和表長等信息;首元結(jié)點: 存儲第一個數(shù)據(jù)元素a1的結(jié)點2.3 線性表的鏈式表示及實現(xiàn) a1 an / Head首元結(jié)點頭結(jié)點線性鏈表的有關(guān)術(shù)語鏈表設(shè)置頭結(jié)點的作用插入或刪除表中任何結(jié)點，都需修改前一結(jié)點的指針域。若鏈表沒有頭結(jié)點，則首元素結(jié)點沒有前驅(qū)結(jié)點，在其前插入結(jié)點或刪除結(jié)點時需單獨處理，操作較復雜。帶頭結(jié)點的鏈表，鏈表指針是指向頭結(jié)點的非空指針，因此空表與非空表的處理是一樣的。2.3 線性表的鏈式表示及實現(xiàn)一個線性表的邏輯結(jié)構(gòu)為:2.3 線性表的鏈式表示及實現(xiàn)（ZHAO,QIAN,SUN,LI,ZHOU

4、,WU,ZHENG,WANG），其存儲結(jié)構(gòu)用單鏈表表示如下，請問其頭指針的值是多少？存儲地址數(shù)據(jù)域指針域1LI437QIAN1313SUN119WANGNULL25WU3731ZHAO737ZHENG1943ZHOU25答：頭指針是指向鏈表中第一個結(jié)點的指針，因此關(guān)鍵是要尋找第一個結(jié)點的地址。 ZHAO 7 HeadDataLink31上例鏈表的邏輯結(jié)構(gòu)示意圖有以下兩種形式2.3 線性表的鏈式表示及實現(xiàn)區(qū)別： 無頭結(jié)點 有頭結(jié)點 ZHAO QIAN SUN LI Head ZHOU WU ZHENG WANG / ZHAO QIAN SUN LI Head ZHOU WU ZHENG WANG

5、 / 線性表的單鏈表存儲結(jié)構(gòu)2.3 線性表的鏈式表示及實現(xiàn)Typedef struct Lnode ElemType data; /數(shù)據(jù)域 struct Lnode *next; /指針域Lnode, *LinkList; / *LinkList為Lnode類型的指針線性鏈表的實現(xiàn)1.單鏈表的建立2.單鏈表的查找3.單鏈表的插入4.單鏈表的刪除5.其它鏈表形式2.3 線性表的鏈式表示及實現(xiàn)單鏈表的建立難點分析：每個數(shù)據(jù)元素在內(nèi)存中是“零散”存放的，其首地址怎么找？又怎么一一鏈接？實現(xiàn)思路：先開辟頭指針，然后陸續(xù)為每個數(shù)據(jù)元素開辟存儲空間并賦值，并及時將地址送給前面的指針。2.3 線性表的鏈式表

6、示及實現(xiàn)單鏈表的建立2.3 線性表的鏈式表示及實現(xiàn)操作步驟：一、建立一個“空表”；二、輸入數(shù)據(jù)元素an， 建立結(jié)點并插入；三、輸入數(shù)據(jù)元素an-1， 建立結(jié)點并插入；an四、依次類推，直至輸入a1為止。anan-1單鏈表的建立2.3 線性表的鏈式表示及實現(xiàn)Void CreateList_L (LinkList &L, int n) /逆位序輸入n個元素的值,建立帶表頭結(jié)點的單鏈線性表L. L = (LinkList) malloc (sizeof(LNode); Lnext = NULL; / 先建立一個帶頭結(jié)點的單鏈表 for ( i =n; i0; -i) p=(LinkList)mall

7、oc (sizeof(LNode); / 生成新結(jié)點 scanf (&p data); / 輸入元素值 pnext = Lnext ; Lnext = p; / 插入到表頭 / CreateList_L單鏈表的查找難點：單鏈表中想取得第i個元素，必須從頭指針出發(fā)尋找(順藤摸瓜)，不能隨機存取 。思路：要修改第i個數(shù)據(jù)元素，關(guān)鍵是要先找到該結(jié)點的指針p，然后用p-data=new_value 即可。2.3 線性表的鏈式表示及實現(xiàn)單鏈表的查找例1：單鏈表中 GetElem(L,i,&e) 的實現(xiàn)2.3 線性表的鏈式表示及實現(xiàn)L211830754256pppj123單鏈表的查找2.3 線性表的鏈式表

8、示及實現(xiàn)Status GetElem_L(LinkList L, int i, ElemType &e) / L為帶頭結(jié)點的單鏈表的頭指針 / 當?shù)趇個元素存在時,其值賦給e并返回OK,否則返回ERROR P = L-next; j=1; / 初始化 ,p指向第一個結(jié)點,j為計數(shù)器 while(p&jnext; +j; / 順指針向后查找,直到p指向第i個元素或p為空 if(!p|ji) return ERROR; / 第i個元素不存在 e=p-data; / 取第i個元素 return OK; / GetElem_L單鏈表的插入單鏈表中 ListInsert(&L,i,e) 的實現(xiàn)2.3 線

9、性表的鏈式表示及實現(xiàn) 改變?yōu)?和 eai-1ai-1spai單鏈表的插入2.3 線性表的鏈式表示及實現(xiàn)s = new LNode; / 生成新結(jié)點if ( s = NULL) return ERROR;s-data = e; s-next = p-next; p-next = s; / 插入return OK;(2)(1)(3) eai-1ai-1spai單鏈表的插入可見，在鏈表中插入結(jié)點只需修改指針。但同時，若要在第 i個結(jié)點之前插入元素，修改的是第 i-1個結(jié)點的指針。因此，在單鏈表中第 i個結(jié)點之前進行插入的基本操作為：找到線性表中第i-1個結(jié)點，然后修改其指向后繼的指針。2.3 線性表

10、的鏈式表示及實現(xiàn)單鏈表的插入2.3 線性表的鏈式表示及實現(xiàn)status ListInsert(LinkList &L,int i,ElemType e ) /在帶頭結(jié)點的單鏈表L中第i個位置之前插入元素e p = L; j = 0; while (p& j next; +j; if (! p | j i-1) return ERROR; s = (LinkList) malloc (sizeof(LNode); s - data=e; s-next= p - next; p - next = s; return OK; / ListInsert_l算法的時間復雜度為：O(ListLength(

11、L)ai-1ai-1單鏈表的刪除單鏈表中 ListDelete(&L,i,&e) 的實現(xiàn)找到鏈表中第i-1個結(jié)點，修改其指向后繼的指針2.3 線性表的鏈式表示及實現(xiàn)ai+1aiq = p-next; p-next = q-next; e = q-data; free(q);pq單鏈表的刪除2.3 線性表的鏈式表示及實現(xiàn)Status ListDelete_L(LinkList &L,int i,ElemType &e) / 刪除以L為頭指針(帶頭結(jié)點)的單鏈表中第i個結(jié)點 p = L; j = 0; while (p-next & j next; +j; / 尋找第 i 個結(jié)點，并令 p 指向其

12、前趨 if (!(p-next) | j i-1) return ERROR; / 刪除位置不合理 q = p-next; p-next = q-next; / 刪除并釋放結(jié)點 e = q-data; free(q); return OK; / ListDelete_L算法的時間復雜度為:O(ListLength(L)2.3 線性表的鏈式表示及實現(xiàn)考慮如何將兩個有序鏈表并為一個有序鏈表？單鏈表的合并已知：線性表 A、B，分別由單鏈表 LA , LB 存儲，其中數(shù)據(jù)元素按值非遞減有序排列，要求：將 A ，B 歸并為一個新的線性表C , C 的數(shù)據(jù)元素仍按值非遞減排列 。設(shè)線性表 C 由單鏈表 L

13、C 存儲。假設(shè): A=(3，5，8，11) B=(2，6，8，9，11)預測:合并后 C =(2 , 3 , 5 , 6 , 8 , 8 , 9 , 11 , 11)2.3 線性表的鏈式表示及實現(xiàn)單鏈表的合并A、B、C用鏈表可表示為2.3 線性表的鏈式表示及實現(xiàn) 3 511 / 8 LA 2 611 / 8 LB 9 2 3 6 5 LC 811 8 911 /單鏈表的合并算法主要包括：搜索、比較、插入三個操作：搜索：需要兩個指針搜索兩個鏈表；比較：比較結(jié)點數(shù)據(jù)域中數(shù)據(jù)的大小；插入：將兩個結(jié)點中數(shù)據(jù)小的結(jié)點插入新鏈表2.3 線性表的鏈式表示及實現(xiàn)單鏈表的合并2.3 線性表的鏈式表示及實現(xiàn) 3

14、511 / 8 LA 2 611 / 8 LB 9 2 3 5 6 LC 8 8 911 11 /PaPbPcPcPaPbPaPbPaPbPbPcPcPcPcPcPcPc單鏈表的合并2.3 線性表的鏈式表示及實現(xiàn) Void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc) /按值排序的單鏈表LA,LB，歸并為LC后也按值排序 free(Lb); /釋放Lb的頭結(jié)點 /MergeList_L pc-next = pa?pa:pb ; /插入剩余段 while(pa&pb) /將pa 、pb結(jié)點按大小依次插入C中 if(pa-datadata)

15、 pc-next=pa; pc=pa; pa=pa-next; else pc-next=pb; pc=pb; pb=pb-next pa=La-next; pb=Lb-next; Lc=pc=La； /初始化 其它鏈表形式2.3 線性表的鏈式表示及實現(xiàn)1）雙向鏈表：有兩個指針域的鏈表，稱為雙鏈表。 # Head prior data nextA. 結(jié)點結(jié)構(gòu)B. 特點：可以雙向查找表中結(jié)點 a1 a2 an / # Head空表其它鏈表形式2.3 線性表的鏈式表示及實現(xiàn)1）雙向鏈表：插入運算 s-next = p-next; p-next = s;s-next-prior = s; s-pri

16、or = p; ai-1 ai esp其它鏈表形式2.3 線性表的鏈式表示及實現(xiàn)1）雙向鏈表：刪除運算 p-next = p-next-next;p-next-prior = p; ai-1 aip ai+1其它鏈表形式2.3 線性表的鏈式表示及實現(xiàn)2）循環(huán)鏈表：將表中最后一個結(jié)點的指針域指向頭結(jié) 點( p-next=head)，整個鏈表形成一個環(huán)。 # a1 an HeadB.與單鏈表的區(qū)別 (循環(huán)條件) 和單鏈表的差別僅在于，判別鏈表中最后一個結(jié)點的條件不再是“后繼是否為空”，而是“后繼是否為頭結(jié)點”。A.特點：從任一結(jié)點出發(fā)均可找到表中其他結(jié)點。時間效率分析查找: 因線性鏈表只能順序存取，即在查找時要從頭指針找起，查找的時間復雜度為 O(n)。插入和刪除: 因線性鏈表不需要移動元素，只要修改指針，一般情況下時間復雜度為 O(1)。但如果要在單鏈表中進行前插或刪除操作，由于要查找前驅(qū)結(jié)點，所耗時間復雜度為 O(n)。2.3 線性表的鏈式表示及實現(xiàn)空間效率分析鏈表中每個結(jié)點都要增加一個指針空間，相當于總共增加了n個整型變量，空間復雜度為 O(n)。2.3 線性表的鏈式表示及實現(xiàn)(1)順序表是用數(shù)組實現(xiàn)的，而鏈表是用指針來實現(xiàn)的。(