線性表的鏈式表示和實現(xiàn)

1、1第第2 2章章 線性表線性表22.3 2.3 線性表的鏈式表示和實現(xiàn)線性表的鏈式表示和實現(xiàn)3 鏈式存儲結(jié)構(gòu)特點：鏈式存儲結(jié)構(gòu)特點：其結(jié)點在存儲器中的位置是隨意的，即邏輯上其結(jié)點在存儲器中的位置是隨意的，即邏輯上相鄰的數(shù)據(jù)元素在物理上不一定相鄰。相鄰的數(shù)據(jù)元素在物理上不一定相鄰。如何實現(xiàn)？ 通過來實現(xiàn)！讓每個存儲結(jié)點都包含兩部分：讓每個存儲結(jié)點都包含兩部分：數(shù)據(jù)域數(shù)據(jù)域和和指針域指針域指針指針數(shù)據(jù)數(shù)據(jù)指針指針指針指針或或樣式：樣式：數(shù)據(jù)域：數(shù)據(jù)域：存儲存儲元素數(shù)值數(shù)據(jù)元素數(shù)值數(shù)據(jù)指針域：指針域：存儲直接后繼或存儲直接后繼或者直接前驅(qū)的存儲位置者直接前驅(qū)的存儲位置2.3.1 2.3.1 鏈表的表

2、示鏈表的表示4鏈表存放示意圖如下： a1heada2/an討論討論1 1：每個存儲結(jié)點都包含兩部分：數(shù)據(jù)域和每個存儲結(jié)點都包含兩部分：數(shù)據(jù)域和討論討論2 2：在單鏈表中，除了首元結(jié)點外，任一結(jié)點的在單鏈表中，除了首元結(jié)點外，任一結(jié)點的存儲位置由存儲位置由 指示。指示。 其直接前驅(qū)結(jié)點的鏈域的值其直接前驅(qū)結(jié)點的鏈域的值(2) (2) 與鏈式存儲有關(guān)的術(shù)語與鏈式存儲有關(guān)的術(shù)語：1 1）結(jié)點）結(jié)點：數(shù)據(jù)元素的存儲映像。由數(shù)據(jù)域和指針域兩數(shù)據(jù)元素的存儲映像。由數(shù)據(jù)域和指針域兩部分組成；部分組成；2 2）鏈表）鏈表： n n 個結(jié)點由個結(jié)點由指針鏈指針鏈組成一個鏈表。它是線性組成一個鏈表。它是線性表的鏈

3、式存儲映像表的鏈式存儲映像，稱為線性表的鏈式存儲結(jié)構(gòu)稱為線性表的鏈式存儲結(jié)構(gòu)。只包含一個指針域的稱為單鏈表或線性鏈表只包含一個指針域的稱為單鏈表或線性鏈表指針域指針域53 3）頭指針、頭結(jié)點和首元結(jié)點的區(qū)別）頭指針、頭結(jié)點和首元結(jié)點的區(qū)別頭指針頭指針頭結(jié)點頭結(jié)點首元結(jié)點首元結(jié)點a1heada2infoan首元結(jié)點首元結(jié)點是指鏈表中存儲線性表第一個數(shù)據(jù)元素是指鏈表中存儲線性表第一個數(shù)據(jù)元素a a1 1的的結(jié)點。結(jié)點。頭結(jié)點頭結(jié)點是在鏈表的首元結(jié)點之前是在鏈表的首元結(jié)點之前附設附設的一個結(jié)點；數(shù)的一個結(jié)點；數(shù)據(jù)域內(nèi)只放空表標志和表長等信息，它不計入據(jù)域內(nèi)只放空表標志和表長等信息，它不計入表長度。表

4、長度。頭指針頭指針是指向鏈表中第一個結(jié)點（或為頭結(jié)點、或為是指向鏈表中第一個結(jié)點（或為頭結(jié)點、或為首元結(jié)點）的指針；首元結(jié)點）的指針；示意圖如下：示意圖如下：6討論討論2 2： 在鏈表中設置在鏈表中設置頭結(jié)點頭結(jié)點有什么好處？有什么好處？討論討論1 1： 如何表示如何表示空表空表？因為任何結(jié)點都有前驅(qū)結(jié)點，而在做插入和刪除操因為任何結(jié)點都有前驅(qū)結(jié)點，而在做插入和刪除操作時，都需修改其前驅(qū)結(jié)點的指針域，作時，都需修改其前驅(qū)結(jié)點的指針域，因此對首元結(jié)點因此對首元結(jié)點可以統(tǒng)一處理。即簡化插入和刪除操作；可以統(tǒng)一處理。即簡化插入和刪除操作；表頭指針是指向頭結(jié)點的非空指針，因此空表和非表頭指針是指向頭結(jié)

5、點的非空指針，因此空表和非空表的處理一樣?？毡淼奶幚硪粯?。無頭結(jié)點時，當無頭結(jié)點時，當頭指針頭指針的值為的值為空空時表示空表；時表示空表；頭指針頭指針無頭結(jié)點無頭結(jié)點頭指針頭指針頭結(jié)點頭結(jié)點有頭結(jié)點有頭結(jié)點有頭結(jié)點時，當有頭結(jié)點時，當頭結(jié)點頭結(jié)點的的指針域為空指針域為空時表示空表。時表示空表。7一個線性表的邏輯結(jié)構(gòu)為：一個線性表的邏輯結(jié)構(gòu)為：（ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANGZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG），其存），其存儲結(jié)構(gòu)用儲結(jié)構(gòu)用單鏈表單鏈表表示如下，表示如下，請問其請問其頭指針的值頭指針的值是多少？是多少？存

6、儲地址存儲地址數(shù)據(jù)域數(shù)據(jù)域指針域指針域1LI437QIAN1313SUN119WANGNULL25WU3731ZHAO737ZHENG1943ZHOU25答：答：頭指針頭指針是指向鏈表是指向鏈表中中第一個第一個結(jié)點的指針，結(jié)點的指針，因此關(guān)鍵是要尋找因此關(guān)鍵是要尋找第一第一個結(jié)點的地址。個結(jié)點的地址。7ZHAOH31稱：頭指針稱：頭指針H的值是的值是31（3 3）舉例）舉例例例1：8 現(xiàn)有一個具有五個元素的線性表現(xiàn)有一個具有五個元素的線性表L=23L=23，1717，4747，0505，3131，若它以鏈接方式存儲在下列若它以鏈接方式存儲在下列100100119119號地號地址址空間中，每個結(jié)

7、點由數(shù)據(jù)（占空間中，每個結(jié)點由數(shù)據(jù)（占2 2個字節(jié)個字節(jié)）和指針）和指針（占（占2 2個字節(jié)個字節(jié)）組成，如下圖所示。）組成，如下圖所示。其中指針其中指針X X，Y Y，Z Z的值分別為多少？該線性表的首結(jié)的值分別為多少？該線性表的首結(jié)點起始地址為多少？末結(jié)點的起始地址為多少？點起始地址為多少？末結(jié)點的起始地址為多少？答：答：X=X= Y= Y= Z= Z= , , 首址首址= = 末址末址= = 。例例2 2：9討論討論: : 鏈表的數(shù)據(jù)元素有鏈表的數(shù)據(jù)元素有兩個域兩個域，不再是簡單數(shù)據(jù)，不再是簡單數(shù)據(jù)類型，編程時該如何表示？類型，編程時該如何表示？因每個結(jié)點至少有兩個分量，且數(shù)據(jù)類型通常不

8、因每個結(jié)點至少有兩個分量，且數(shù)據(jù)類型通常不一致，所以要采用一致，所以要采用結(jié)構(gòu)結(jié)構(gòu)數(shù)據(jù)類型。數(shù)據(jù)類型。答：答：設每個結(jié)點用變量設每個結(jié)點用變量表示，表示，其指針用其指針用 表示，兩個分量分表示，兩個分量分別用別用和和表示，這兩表示，這兩個分量如何賦值？個分量如何賦值？p方式方式1： 直接表示為直接表示為 node.data；node.next=方式方式2：p指向結(jié)點首地址指向結(jié)點首地址 p-data=; p-next= ; 方式方式3：p指向結(jié)點首地址指向結(jié)點首地址 (*p).data=； (*p).next10單鏈表的抽象數(shù)據(jù)類型描述如下單鏈表的抽象數(shù)據(jù)類型描述如下（參見教材（參見教材P28

9、P28）：typedef struct LNode ElemType data; /數(shù)據(jù)域 struct LNode *next; /指針域LNode, *LinkList; / *LinkList為Lnode類型的指針Q1Q1：第一行的第一行的LNodeLNode 與最后一行的與最后一行的LNodeLNode是不是一回事？是不是一回事？A1A1：不是。前者不是。前者LNodeLNode是結(jié)構(gòu)名，后者是結(jié)構(gòu)名，后者LNodeLNode是對整個是對整個structstruct類型的一種類型的一種“縮寫縮寫”，是一種，是一種“新定義名新定義名”，它只，它只是對現(xiàn)有類型名的補充，而不是取代。是對現(xiàn)有

10、類型名的補充，而不是取代。這就是我們在復習這就是我們在復習c語言時講的語言時講的自引用結(jié)構(gòu)自引用結(jié)構(gòu)11Q2Q2： 那為何兩處要同名那為何兩處要同名( (LNodeLNode和和LNodeLNode）？太不嚴謹）？太不嚴謹了吧？了吧？A2A2：同名是為了表述起來方便。因為描述的對象相同，同名是為了表述起來方便。因為描述的對象相同，方便閱讀和理解。方便閱讀和理解。Q3Q3：結(jié)構(gòu)體中間的那個：結(jié)構(gòu)體中間的那個structstruct LNodeLNode是何意？是何意？A3A3：在：在“縮寫縮寫” LNodeLNode還沒出現(xiàn)之前，只能用原始的還沒出現(xiàn)之前，只能用原始的struct LNodest

11、ruct LNode來進行變量說明。此處說明了指針分量來進行變量說明。此處說明了指針分量的數(shù)據(jù)類型是的數(shù)據(jù)類型是struct LNodestruct LNode。返返 回回122.3.2 2.3.2 鏈表的實現(xiàn)鏈表的實現(xiàn)13（1 1） 單鏈表的存取單鏈表的存取思路：思路：要存取第要存取第i i個數(shù)據(jù)元素，必須從頭指針起一直找到個數(shù)據(jù)元素，必須從頭指針起一直找到該結(jié)點的指針該結(jié)點的指針p p，然后才能執(zhí)行，然后才能執(zhí)行 p-data=new_value p-data=new_value 。訪問第訪問第i i個數(shù)據(jù)元素的操作函數(shù)可寫為：個數(shù)據(jù)元素的操作函數(shù)可寫為：Status GetElem_L(

12、LinkList L, int i, ElemType e)p=L-next; j=1; /帶頭結(jié)點的鏈表while(p&jnext; +j;if ( !p ji ) return ERROR; /i不合法p-data =e; /若是讀取則為：e=p-data; return OK;/ GetElem_L缺點：缺點：想尋找單鏈表中第想尋找單鏈表中第i i個元素，只能從頭指針開個元素，只能從頭指針開始逐一查詢（始逐一查詢（順藤摸瓜順藤摸瓜），無法隨機存?。瑹o法隨機存取 。14在鏈表中第在鏈表中第i i個位置前插入一個元素個位置前插入一個元素x 的示意圖如下：的示意圖如下：X Xsai-

13、1aip鏈表插入的核心語句：鏈表插入的核心語句：p-nexts-nextX 結(jié)點的生成方式：結(jié)點的生成方式：s=(Lnode*)malloc(m);s-data= x ;s-next= ?aiai-1pX X （2 2） 單鏈表的插入單鏈表的插入（重點）重點）15 Status ListInsert_L(LinkList L, int i, ElemType e) / LinstInsert_L算法的時間復雜度為算法的時間復雜度為: :O(ListLength(L)p = L; j = 0;while (p & j next; +j; / 尋找第 i-1 個結(jié)點if (!p | j i

14、-1) return ERROR; /i不合法 s = (LinkList)malloc(sizeof(LNode) s-data = e; s-next = p-next; p-next = s; / / 插入插入return OK;16在鏈表中刪除某元素在鏈表中刪除某元素ai的示意圖如下：的示意圖如下：ai+1 ai-1 aip刪除動作的核心語句（要借助輔助指針變量刪除動作的核心語句（要借助輔助指針變量q q）：）：q = p-next; /首先保存首先保存a ai i的指針，靠它才能找到的指針，靠它才能找到a ai+1i+1 p-next(p-next) - nextq（3 3） 單鏈表

15、的刪除單鏈表的刪除（重點）重點）p-next=q-next；/將將a ai-1i-1與與a ai+1i+1兩結(jié)點相連兩結(jié)點相連, ,淘汰淘汰a ai i結(jié)點結(jié)點free(q); 17 Status ListDelete_L(LinkList L, int i, ElemType &e) / 刪除以 L 為頭指針(帶頭結(jié)點)的單鏈表中第 i 個結(jié)點 / ListDelete_L算法的時間復雜度為算法的時間復雜度為: :O(ListLength(L)p = L; j = 0;while (p-next & j next; +j; / 尋找第 i 個結(jié)點，并令 p 指向其前趨if (

16、!(p-next) | j i-1) return ERROR; / 刪除位置不合理q = p-next; p-next = q-next; /刪除并釋放結(jié)點 e = q-data; free(q);return OK;18空間效率分析空間效率分析鏈表中每個結(jié)點都要增加一個指針空間，相當于總鏈表中每個結(jié)點都要增加一個指針空間，相當于總共增加了共增加了n n 個整型變量，空間復雜度為個整型變量，空間復雜度為 O(n)O(n)。在在n n個結(jié)點的單鏈表中要刪除已知結(jié)點個結(jié)點的單鏈表中要刪除已知結(jié)點* *P P，需找到它，需找到它的的 ，其時間復雜度，其時間復雜度 。 O(n)O(n)練習：練習：1

17、9操作步驟：操作步驟：一、建立一個一、建立一個“空表空表”；二、輸入數(shù)據(jù)元素二、輸入數(shù)據(jù)元素a an n， 建立結(jié)點并插入；建立結(jié)點并插入；三、輸入數(shù)據(jù)元素三、輸入數(shù)據(jù)元素a an-1n-1， 建立結(jié)點并插入表頭；建立結(jié)點并插入表頭；ananan-1四、依次類推，直至輸入四、依次類推，直至輸入a a1 1為止為止。（4 4）單鏈表的建立）單鏈表的建立例如：例如：頭插法頭插法輸入輸入 n n 個數(shù)據(jù)元素的值，建立帶頭結(jié)個數(shù)據(jù)元素的值，建立帶頭結(jié)點的單鏈表。點的單鏈表。鏈表是一個動態(tài)的結(jié)構(gòu)，它不需要預先分配空間，因鏈表是一個動態(tài)的結(jié)構(gòu)，它不需要預先分配空間，因此生成鏈表的過程是一個結(jié)點此生成鏈表的

18、過程是一個結(jié)點“逐個插入逐個插入” ” 的過程。的過程。頭插法建表頭插法建表該方法從一個空表開始，重復讀入數(shù)據(jù)，生成新結(jié)該方法從一個空表開始，重復讀入數(shù)據(jù)，生成新結(jié)點，將讀入數(shù)據(jù)存放到新結(jié)點的數(shù)據(jù)域中，然后點，將讀入數(shù)據(jù)存放到新結(jié)點的數(shù)據(jù)域中，然后將將新結(jié)點插入到當前鏈表的表頭上新結(jié)點插入到當前鏈表的表頭上，直到讀入結(jié)束標，直到讀入結(jié)束標志為止。志為止。執(zhí) 行 的 語 句 組 為 :s next L next； L next s；L(a) 建空表c1ss 指向新申請的結(jié)點s data c1(b) 申請新結(jié)點并賦值Lci 1s(c) 插入第一個結(jié)點Lc2c1cic1s(d) 插入第i個元素21v

19、oid CreateList_L(LinkList &L, int n) / 頭插法建立帶頭結(jié)點的單鏈表 / CreateList_L算法的時間復雜度算法的時間復雜度為:O(Listlength(L)L = (LinkList) malloc (sizeof (LNode);L-next = NULL; / 先建立一個帶頭結(jié)點的單鏈表for (i = n; i 0; -i) s = (LinkList) malloc (sizeof (LNode); scanf(&s-data); / 輸入元素值 s-next = L-next; L-next = s; / 插入尾插法建表尾插

20、法建表該方法是將新結(jié)點插入到當前鏈表的表尾上，為此該方法是將新結(jié)點插入到當前鏈表的表尾上，為此必須必須增加一個尾指針增加一個尾指針r，使其始終指向當前鏈表的尾，使其始終指向當前鏈表的尾結(jié)點結(jié)點rs；r始終指向單鏈表的表尾L(a) 建空表c1ss 指向新申請的結(jié)點空間sdatac1(b) 申請新結(jié)點并賦值Lc1s(c) 插入第一個結(jié)點Lc2c1rrr nexts；(d) 插入第二個結(jié)點sr尾插法尾插法建表建表 void CreateList_L(LinkList &L, int n) tail = L = (LinkList) malloc( sizeof (LNode) );/尾指針初

21、始化為表頭指針尾指針初始化為表頭指針 L-next = NULL; for( i=n; i0; -i) s = (LinkList) malloc( sizeof (LNode) ); scanf( &s-data); s-next = NULL; tail-next = s; tail = s; 24算法要求：算法要求：已知：已知：線性表線性表 A A和和B B，分別由單鏈表分別由單鏈表 LaLa和和Lb Lb 存儲存儲，其中，其中數(shù)據(jù)元素按值非遞減有序排列（即已經(jīng)有序）；數(shù)據(jù)元素按值非遞減有序排列（即已經(jīng)有序）；要求：要求：將將A A和和B B歸并為一個新的線性表歸并為一個新的線性

22、表C , CC , C的數(shù)據(jù)元素仍的數(shù)據(jù)元素仍按值非遞減排列。設線性表按值非遞減排列。設線性表C C由單鏈表由單鏈表 Lc Lc 存儲。存儲。假設：假設：A=A=（3 3，5 5，8 8，1111），），B=B=（2 2，6 6，8 8，9 9，1111）預測：預測：合并后的合并后的C =C =（2, 3, 5, 6, 8, 8, 9, 112, 3, 5, 6, 8, 8, 9, 11，1111）例例1 1：兩個鏈表的歸并（教材：兩個鏈表的歸并（教材P31P31例）例）算法設計：算法設計：算法主要包括搜索、比較、插入三個操作：算法主要包括搜索、比較、插入三個操作：搜索：搜索：需要設立三個指針

23、來指向需要設立三個指針來指向La La 、LbLb和和LcLc鏈表；鏈表；請將該例子和請將該例子和ch2-1的的ppt的第的第18頁進行比較！頁進行比較！25La3 5 8 11 Lb2 6 8 119 PaPbPaPbPaPa、PbPb用于搜索用于搜索LaLa和和LbLb， PcPc指向新鏈表當前結(jié)點。指向新鏈表當前結(jié)點。歸并過程示意如下：歸并過程示意如下：Lc=LaPbPaPaPb比較：比較：比較比較LaLa和和LbLb表中結(jié)點數(shù)據(jù)的大?。槐碇薪Y(jié)點數(shù)據(jù)的大??；插入：插入：將將LaLa和和LbLb表中數(shù)據(jù)較小的結(jié)點插入新鏈表表中數(shù)據(jù)較小的結(jié)點插入新鏈表Lc Lc 。請注意鏈表的特點，僅改變指

24、針便可實現(xiàn)請注意鏈表的特點，僅改變指針便可實現(xiàn)數(shù)據(jù)的移動數(shù)據(jù)的移動, ,即即“數(shù)據(jù)不動，指針動數(shù)據(jù)不動，指針動”26 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é)點按大小依次插入Lc中 if (pa-datadata) pc-next=pa;

25、pc=pa; pa=pa-next; else pc-next=pb; pc=pb; pb=pb-next pa=LaLa-next; pb=LbLb-next; Lc=pc=La； /有頭結(jié)點思考：思考：重復的數(shù)據(jù)元素不需要插入，怎么修改？重復的數(shù)據(jù)元素不需要插入，怎么修改？練習：練習：已知已知L是帶頭結(jié)點的非空單鏈表，指針是帶頭結(jié)點的非空單鏈表，指針p所指的所指的結(jié)點既不是第一個結(jié)點，也不是最后一個結(jié)點結(jié)點既不是第一個結(jié)點，也不是最后一個結(jié)點l 刪除刪除*p結(jié)點的直接后繼結(jié)點的語句序列結(jié)點的直接后繼結(jié)點的語句序列 q = p-next; p-next = q-next; free(q);l

26、 刪除刪除*p結(jié)點的直接前驅(qū)結(jié)點的語句序列結(jié)點的直接前驅(qū)結(jié)點的語句序列 q = L; while( q-next-next != p) q = q-next; s = q-next;/s即所要找到的即所要找到的p的前驅(qū)的前驅(qū) q-next = p;/鏈接鏈接 free(s);l 刪除刪除*p結(jié)點的語句序列結(jié)點的語句序列 q = L; while( q-next != p) q = q-next; q-next = p-next; free(p);l 刪除首元結(jié)點的語句序列刪除首元結(jié)點的語句序列 q = L-next; L-next = q-next; free(q);l 刪除最后一個結(jié)點的語句

27、序列刪除最后一個結(jié)點的語句序列 while(p-next-next != NULL) p = p-next; q = p-next; p-next = NULL; free(q);29用上述定義的單鏈表實現(xiàn)線性表的操作時，存在的用上述定義的單鏈表實現(xiàn)線性表的操作時，存在的問題問題：改進鏈表的設置：改進鏈表的設置：1 1單鏈表的表長是一個隱含的值；單鏈表的表長是一個隱含的值； 1. 1. 增加增加“表長表長”、“表尾指針表尾指針” 和和 “當前位置的指當前位置的指針針” 三個數(shù)據(jù)域；三個數(shù)據(jù)域； 2. 2. 將基本操作中的將基本操作中的“位序位序 i i ”改變?yōu)楦淖優(yōu)椤爸羔樦羔?p p ”。2

28、 2在單鏈表的最后一個元素之后插入元素時，需遍在單鏈表的最后一個元素之后插入元素時，需遍歷整個鏈表；歷整個鏈表；3 3在鏈表中，元素的在鏈表中，元素的“位序位序”概念淡化，結(jié)點的概念淡化，結(jié)點的“位位置置”概念加強。概念加強。返返 回回30typedef struct LNode /結(jié)點類型 Elemtype data; struct LNode *next; *Link, *Positiontypedef struct /鏈表類型 Link head, tail; /分別指向鏈表頭尾結(jié)點 int len; /鏈表中元素個數(shù)（長度） Linklist;2.3.3 2.3.3 一個帶頭結(jié)點的線性

29、鏈表類型定義如下：一個帶頭結(jié)點的線性鏈表類型定義如下：（用類（用類C C語言，見語言，見P37P37）：）：結(jié)點的結(jié)點的結(jié)構(gòu)結(jié)構(gòu)表結(jié)構(gòu)表結(jié)構(gòu)基本操作（略）基本操作（略）返返 回回31 最后一個結(jié)點的指針域的指針又指回第一個結(jié)點的最后一個結(jié)點的指針域的指針又指回第一個結(jié)點的鏈表。從表中任一結(jié)點出發(fā)均可找到表中其它結(jié)點鏈表。從表中任一結(jié)點出發(fā)均可找到表中其它結(jié)點 a1 a2 . an 1. 1. 循環(huán)鏈表循環(huán)鏈表 和單鏈表的差別僅在于，判別鏈表中最后一個結(jié)和單鏈表的差別僅在于，判別鏈表中最后一個結(jié)點的條件不再是點的條件不再是“后繼是否為空后繼是否為空”，而是，而是“后繼是后繼是否為頭結(jié)點否為頭結(jié)點

30、”即即p-next?=headhead2.3.4 2.3.4 其它形式的鏈表其它形式的鏈表32單鏈表中查找只能從前往后，而不能從后往前查。為了單鏈表中查找只能從前往后，而不能從后往前查。為了查找方便，提高查找速度，可以在結(jié)點上增加一個指針查找方便，提高查找速度，可以在結(jié)點上增加一個指針域，用來存結(jié)點的直接前驅(qū)，這樣的鏈表稱為域，用來存結(jié)點的直接前驅(qū)，這樣的鏈表稱為雙向鏈表雙向鏈表。其其結(jié)點的結(jié)構(gòu)結(jié)點的結(jié)構(gòu)為：為：typedef struct DuLNode ElemType data; /數(shù)據(jù)域 struct DuLNode *prior; /前驅(qū)指針域 struct DuLNode *nex

31、t; /后繼指針域 DuLNode , *DuLinkList ; 雙向鏈表類型的定義如下：雙向鏈表類型的定義如下：2.3.4 2.3.4 其它形式的鏈表其它形式的鏈表2. 2. 雙向鏈表雙向鏈表設指針p指向某一結(jié)點，則雙向鏈表結(jié)構(gòu)的對稱性雙向鏈表結(jié)構(gòu)的對稱性描述如下描述如下： (pprior)next = p = (pnext)prior,即結(jié)點*p的存儲位置既存放在其前趨結(jié)點*(pprior)的直接后繼指針域中，也存放在它的后繼結(jié)點*(pnext)的直接前趨指針域中ai-1aiai+1p343.3.雙向循環(huán)鏈雙向循環(huán)鏈表表空表空表非空表非空表 a1 a2 . anhead-prior=he

32、ad-next=headhead35雙向鏈表插入操作（重點）：雙向鏈表插入操作（重點）：設設p p已指向第已指向第 i 元素，請在第元素，請在第 i 元素元素前前插插入元素入元素x ai-1的后繼從的后繼從 ai ( ( 指針是指針是p)變?yōu)樽優(yōu)?x（指針是指針是s) : s-next = p ; p-prior-next = s ; ai 的前驅(qū)從的前驅(qū)從 ai-1 ( 指針是指針是p-prior)變?yōu)樽優(yōu)?x ( 指針是指針是s); s-prior = p -prior ; p-prior = s ; 注意：要修改注意：要修改雙向指針！雙向指針！x sai-1 ai p指針域的變化指針域的

33、變化：void dinsertbefor(DuLNode *p，ElemType x)DuLNode *s=malloc(sizeof(DuLNode);sdata=x;snext=p; ppriornext=s;sprior=pprior; pprior=s; 問：（問：（1） （2） （3）,（4）位置是否可交換？）位置是否可交換？原則是什么？原則是什么？改成如下代碼試試：改成如下代碼試試：sprior=pprior;snext=p;ppriornext=s;pprior=s;改成如下代碼試試：改成如下代碼試試：snext=p;sprior=pprior;pprior=s;ppriorne

34、xt=s;37指針域的變化：指針域的變化： ai-1的后繼由的后繼由 ai 變?yōu)樽優(yōu)?ai+1( (指針指針 p -next );); p -prior-next = p-next ; ai+1 的前驅(qū)由的前驅(qū)由 ai 變?yōu)樽優(yōu)閍i-1 (指針指針 p - prior ); p-next-prior = p -prior ; ai-1 ai+1 ai p雙向鏈表刪除操作：雙向鏈表刪除操作：設設p指向第指向第i個元素個元素, ,刪除第刪除第i個元素個元素注意：要注意：要修改雙向修改雙向指針！指針！void ddeletenode(dlistnode *p)ppriornext=pnext; pn

35、extprior=pprior;free(p);39動態(tài)鏈表樣式：動態(tài)鏈表樣式：靜態(tài)鏈表樣式：靜態(tài)鏈表樣式：指針指針數(shù)據(jù)指針指針數(shù)據(jù)指針指針數(shù)據(jù)指示指示數(shù)據(jù)指示指示數(shù)據(jù)指示指示數(shù)據(jù)指示指示數(shù)據(jù)指示指示數(shù)據(jù)數(shù)組中每個元數(shù)組中每個元素都至少有兩素都至少有兩個分量，屬于個分量，屬于結(jié)構(gòu)型數(shù)組結(jié)構(gòu)型數(shù)組。常用于無指針常用于無指針類型的高級語類型的高級語言中。言中。用一片連續(xù)空間（一維數(shù)組）實現(xiàn)鏈式存儲，這種用一片連續(xù)空間（一維數(shù)組）實現(xiàn)鏈式存儲，這種方式稱為方式稱為靜態(tài)鏈表靜態(tài)鏈表。具體實現(xiàn)方法：具體實現(xiàn)方法：定義一個結(jié)構(gòu)型數(shù)組（每個元素都含定義一個結(jié)構(gòu)型數(shù)組（每個元素都含有有數(shù)據(jù)域數(shù)據(jù)域和和指示域指

36、示域），就可以完全描述鏈表，），就可以完全描述鏈表，指示域指示域就相當于動態(tài)鏈表中的指針就相當于動態(tài)鏈表中的指針, ,指示結(jié)點在數(shù)組中的相指示結(jié)點在數(shù)組中的相對位置。對位置。4.4.靜態(tài)鏈表（自學）靜態(tài)鏈表（自學）40 靜態(tài)單鏈表的類型定義如下：靜態(tài)單鏈表的類型定義如下：#define MAXSIZE 1000 /預分配鏈表的最大長度 typedef struct ElemType data ; /數(shù)據(jù)域 int cur ; /指示域 component ,SLinkListMAXSIZE; /這是一維結(jié)構(gòu)型數(shù)組前例前例1 1：一：一線性表線性表 S S = ( ZHAO, QIAN, SUN

37、, LI, ZHOU, = ( ZHAO, QIAN, SUN, LI, ZHOU, WU )WU )，用靜態(tài)鏈表如何表示？，用靜態(tài)鏈表如何表示？說明說明1 1：假設假設S S為為SLinkListSLinkList型變量，則型變量，則SMAXSIZESMAXSIZE 為一為一個靜態(tài)鏈表；個靜態(tài)鏈表；S0.curS0.cur則表示第則表示第1 1個結(jié)點在數(shù)組中的位置。個結(jié)點在數(shù)組中的位置。41說明說明2 2：如果數(shù)組的第如果數(shù)組的第i i個分量表示鏈表的第個分量表示鏈表的第k k個結(jié)點，個結(jié)點，則：則：Si.dataSi.data表示第表示第k k個結(jié)點的數(shù)據(jù)；個結(jié)點的數(shù)據(jù)； Si.curSi

38、.cur 表示第表示第k+1k+1個結(jié)點個結(jié)點( (即即k k的直接后繼的直接后繼) )的位置。的位置。data1 1ZHAO3LI5QIAN6WU0ZHOU4SUN2curi說明說明3 3：靜態(tài)鏈表的插入與刪除靜態(tài)鏈表的插入與刪除操作與普通鏈表一樣，不需要移操作與普通鏈表一樣，不需要移動元素，只需修改指示器就可以動元素，只需修改指示器就可以了。了。例如：在線性表例如：在線性表 S = ( ZHAO, S = ( ZHAO, QIAN, SUN, LI, ZHOU, WU )QIAN, SUN, LI, ZHOU, WU )的的QIAN, SUNQIAN, SUN之間之間LIULIU，可以這樣

39、實現(xiàn)：可以這樣實現(xiàn)：42Step1:Step1:將將QIANQIAN的指示器原內(nèi)容備份到臨時變量的指示器原內(nèi)容備份到臨時變量temptemp：temp = S3.cur；Step2:Step2:將將QIANQIAN的指示器換為新元的指示器換為新元素素LIULIU的位置：的位置：Step3:Step3:將將LIULIU的指示器變?yōu)楹蟮闹甘酒髯優(yōu)楹罄^繼SUNSUN的位置：的位置：data2SUN4ZHOU0WU6QIAN5LI3ZHAO1 1curi data cur 0 6 1 2 2 a 3 3 b 4 4 c 5 5 d 0 6 7 7 0 li = si.cur; 指針后移操作指針后移操作lMalloc: i = s0.cur; 第一個可用結(jié)點位置第一個可用結(jié)點位置 if(s0.cur) s0.cur = si.cur;lF