武漢軟件工程職業(yè)學(xué)院數(shù)據(jù)結(jié)構(gòu)講義線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)

1、第四講 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)1掌握線性鏈表、單鏈表、靜態(tài)鏈表的概念。2掌握線性鏈表的表示及實(shí)現(xiàn)方法。Ø 教學(xué)重點(diǎn)： 線性鏈表之單鏈表的表示及實(shí)現(xiàn)方法。Ø 教學(xué)難點(diǎn)： 線性鏈表的概念。Ø 授課內(nèi)容2.3 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)由于順序表的存貯特點(diǎn)是用物理上的相鄰實(shí)現(xiàn)了邏輯上的相鄰，它要求用連續(xù)的存儲單元順序存儲線性表中各元素，因此，對順序表插入、刪除時(shí)需要通過移動數(shù)據(jù)元素來實(shí)現(xiàn)，影響了運(yùn)行效率。本節(jié)介紹線性表鏈?zhǔn)酱鎯Y(jié)構(gòu)，它不需要用地址連續(xù)的存儲單元來實(shí)現(xiàn)，因?yàn)樗灰筮壿嬌舷噜彽膬蓚€(gè)數(shù)據(jù)元素物理上也相鄰，它是通過“鏈”建立起數(shù)據(jù)元素之間的邏輯關(guān)系來，因此對線性表的插

2、入、刪除不需要移動數(shù)據(jù)元素。 單鏈表鏈表是通過一組任意的存儲單元來存儲線性表中的數(shù)據(jù)元素的，那么怎樣表示出數(shù)據(jù)元素之間的線性關(guān)系呢？為建立起數(shù)據(jù)元素之間的線性關(guān)系，對每個(gè)數(shù)據(jù)元素ai，除了存放數(shù)據(jù)元素的自身的信息 ai 之外，還需要和ai一起存放其后繼 ai+1 所在的存貯單元的地址，這兩部分信息組成一個(gè)“結(jié)點(diǎn)”，結(jié)點(diǎn)的結(jié)構(gòu)如圖2.6 所示，每個(gè)元素都如此。存放數(shù)據(jù)元素信息的稱為數(shù)據(jù)域，存放其后繼地址的稱為指針域。因此n個(gè)元素的線性表通過每個(gè)結(jié)點(diǎn)的指針域拉成了一個(gè)“鏈子”，稱之為鏈表。因?yàn)槊總€(gè)結(jié)點(diǎn)中只有一個(gè)指向后繼的指針，所以稱其為單鏈表。鏈表是由一個(gè)個(gè)結(jié)點(diǎn)構(gòu)成的，結(jié)點(diǎn)定義如下：圖2.6 單鏈

3、表結(jié)點(diǎn)結(jié)構(gòu)data nexttypedef struct node datatype data; struct node *next; LNode，*LinkList；定義頭指針變量：LinkList H；如圖2.7是線性表 (a1,a2,a3,a4,a5,a6,a7,a8) 對應(yīng)的鏈?zhǔn)酱鎯Y(jié)構(gòu)示意圖。當(dāng)然必須將第一個(gè)結(jié)點(diǎn)的地址160 放到一個(gè)指針變量如 H 中，最后一個(gè)結(jié)點(diǎn)沒有后繼, 其指針域必需置空，表明此表到此結(jié)束，這樣就可以從第一個(gè)結(jié)點(diǎn)的地址開始“順藤摸瓜”，找到每個(gè)結(jié)點(diǎn)。作為線性表的一種存儲結(jié)構(gòu)，我們關(guān)心的是結(jié)點(diǎn)間的邏輯結(jié)構(gòu)，而對每個(gè)結(jié)點(diǎn)的實(shí)際地址并不關(guān)心，所以通常的單鏈表用圖2.8

4、的形式而不用圖2.7的形式表示。通常我們用“頭指針”來標(biāo)識一個(gè)單鏈表，如單鏈表L、單鏈表H等，是指某鏈表的第一個(gè)結(jié)點(diǎn)的地址放在了指針變量 L、H 中， 頭指針為“NULL”則表示一個(gè)空表。110a5200150a2190160a1150190a3210200a6260210a4110 .240a8NULL .260a7240圖2.8 鏈表示意圖a1anHa2Pp->datap->next 圖2.9 申請一個(gè)結(jié)點(diǎn)H160圖2.7 鏈?zhǔn)酱鎯Y(jié)構(gòu) 需要進(jìn)一步指出的是：上面定義的LNode是結(jié)點(diǎn)的類型，LinkList是指向Lnode類型結(jié)點(diǎn)的指針類型。 為了增強(qiáng)程序的可讀性，通常將標(biāo)識一

5、個(gè)鏈表的頭指針說明為LinkList類型的變量，如LinkList L ; 當(dāng)L有定義時(shí)，值要么為NULL，則表示一個(gè)空表；要么為第一個(gè)結(jié)點(diǎn)的地址，即鏈表的頭指針；將操作中用到指向某結(jié)點(diǎn)的指針變量說明為LNode *類型，如LNode *p； 則語句：p=malloc(sizeof(LNode)；則完成了申請一塊 Lnode 類型的存儲單元的操作，并將其地址賦值給變量p。如圖2.9所示。P所指的結(jié)點(diǎn)為*p，*p的類型為LNode型，所以該結(jié)點(diǎn)的數(shù)據(jù)域?yàn)?(*p).data或p->data，指針域?yàn)?(*p).next 或 p->next。free(p)則表示釋放 p 所指的結(jié)點(diǎn)。

6、單鏈表的基本操作1. 建立單鏈表(1)在鏈表的頭部插入結(jié)點(diǎn)建立單鏈表鏈表與順序表不同，它是一種動態(tài)管理的存儲結(jié)構(gòu)，鏈表中的每個(gè)結(jié)點(diǎn)占用的存儲空間不是預(yù)先分配，而是運(yùn)行時(shí)系統(tǒng)根據(jù)需求而生成的，因此建立單鏈表從空表開始，每讀入一個(gè)數(shù)據(jù)元素則申請一個(gè)結(jié)點(diǎn)，然后插在鏈表的頭部，如圖2.10 展現(xiàn)了線性表：（25,45,18,76,29）之鏈表的建立過程，因?yàn)槭窃阪湵淼念^部插入，讀入數(shù)據(jù)的順序和線性表中的邏輯順序是相反的。25452518762976182545251825452525452525圖2.10 在頭部插入建立單鏈表算法如下：LinkList Creat_LinkList1( ) LinkL

7、ist L=NULL；/*空表*/Lnode *s; int x; /*設(shè)數(shù)據(jù)元素的類型為int*/scanf(%d,&x);while (x!=flag) s=malloc(sizeof(LNode); s->data=x; s->next=L; L=s; Scanf (%d,&x); return L;算法2.8(2)在單鏈表的尾部插入結(jié)點(diǎn)建立單鏈表頭插入建立單鏈表簡單，但讀入的數(shù)據(jù)元素的順序與生成的鏈表中元素的順序是相反的，若希望次序一致，則用尾插入的方法。因?yàn)槊看问菍⑿陆Y(jié)點(diǎn)插入到鏈表的尾部，所以需加入一個(gè)指針 r 用來始終指向鏈表中的尾結(jié)點(diǎn)，以便能夠?qū)⑿陆Y(jié)點(diǎn)

8、插入到鏈表的尾部，如圖2.11展現(xiàn)了在鏈表的尾部插入結(jié)點(diǎn)建立鏈表的過程 。算法思路：初始狀態(tài)：頭指針H=NULL，尾指針 r=NULL; 按線性表中元素的順序依次讀入數(shù)據(jù)元素，不是結(jié)束標(biāo)志時(shí)，申請結(jié)點(diǎn)，將新結(jié)點(diǎn)插入到 r 所指結(jié)點(diǎn)的后面，然后 r 指向新結(jié)點(diǎn)（但第一個(gè)結(jié)點(diǎn)有所不同，讀者注意下面算法中的有關(guān)部分）。圖2.11 在尾部插入建立單鏈表H=NULL r=NULL /*初始狀態(tài)*/29rH7629rH187629rH254525187629rH4525187629rH算法如下：LinkList Creat_LinkList2( ) LinkList L=NULL;Lnode *s,*r=

9、NULL; int x; /*設(shè)數(shù)據(jù)元素的類型為int*/scanf(%d,&x);while (x!=flag) s=malloc(sizeof(LNode); s->data=x; if (L=NULL) L=s; /*第一個(gè)結(jié)點(diǎn)的處理*/ else r->next=s; /*其它結(jié)點(diǎn)的處理*/ r=s; /*r 指向新的尾結(jié)點(diǎn)*/ scanf(%d,&x); if ( r!=NULL) r->next=NULL; /*對于非空表，最后結(jié)點(diǎn)的指針域放空指針*/ return L;算法2.9在上面的算法中，第一個(gè)結(jié)點(diǎn)的處理和其它結(jié)點(diǎn)是不同的，原因是第一個(gè)結(jié)點(diǎn)

10、加入時(shí)鏈表為空，它沒有直接前驅(qū)結(jié)點(diǎn)，它的地址就是整個(gè)鏈表的指針， 需要放在鏈表的頭指針變量中；而其它結(jié)點(diǎn)有直接前驅(qū)結(jié)點(diǎn)，其地址放入直接前驅(qū)結(jié)點(diǎn)的指針域?！暗谝粋€(gè)結(jié)點(diǎn)”的問題在很多操作中都會遇到，如在鏈表中插入結(jié)點(diǎn)時(shí)，將結(jié)點(diǎn)插在第一個(gè)位置和其它位置是不同的，在鏈表中刪除結(jié)點(diǎn)時(shí)，刪除第一個(gè)結(jié)點(diǎn)和其它結(jié)點(diǎn)的處理也是不同的，等等，為了方便操作，有時(shí)在鏈表的頭部加入一個(gè)“頭結(jié)點(diǎn)”，頭結(jié)點(diǎn)的類型與數(shù)據(jù)結(jié)點(diǎn)一致，標(biāo)識鏈表的頭指針變量L中存放該結(jié)點(diǎn)的地址，這樣即使是空表，頭指針變量L也不為空了。頭結(jié)點(diǎn)的加入使得“第一個(gè)結(jié)點(diǎn)”的問題不再存在，也使得“空表”和“非空表”的處理成為一致。頭結(jié)點(diǎn)的加入完全是為了運(yùn)算的

11、方便，它的數(shù)據(jù)域無定義，指針域中存放的是第一個(gè)數(shù)據(jù)結(jié)點(diǎn)的地址，空表時(shí)為空。圖2.12(a)、（b）分別是帶頭結(jié)點(diǎn)的單鏈表空表和非空表的示意圖。圖2.12 帶頭結(jié)點(diǎn)的單鏈表H(a)a1a2anH(b)2. 查找操作(1) 按序號查找 Get_Linklist(L,i)算法思路：從鏈表的第一個(gè)元素結(jié)點(diǎn)起，判斷當(dāng)前結(jié)點(diǎn)是否是第i個(gè)，若是，則返回該結(jié)點(diǎn)的指針，否則繼續(xù)后一個(gè)，表結(jié)束為止。沒有第個(gè)結(jié)點(diǎn)時(shí)返回空。算法如下：Lnode * Get_LinkList(LinkList L, Int i);/*在單鏈表L中查找第i個(gè)元素結(jié)點(diǎn)，找到返回其指針，否則返回空*/ Lnode * p=L; int j=

12、0;while (p->next !=NULL && j<i ) p=p->next; j+; if (j=i) return p; else return NULL; 算法2.11(a)(2) 按值查找即定位 Locate_LinkList(L,x)算法思路：從鏈表的第一個(gè)元素結(jié)點(diǎn)起，判斷當(dāng)前結(jié)點(diǎn)其值是否等于x，若是，返回該結(jié)點(diǎn)的指針，否則繼續(xù)后一個(gè)，表結(jié)束為止。找不到時(shí)返回空。算法如下：Lnode * Locate_LinkList( LinkList L, datatype x) /*在單鏈表L中查找值為x的結(jié)點(diǎn)，找到后返回其指針，否則返回空*/ Lno

13、de * p=L->next; while ( p!=NULL && p->data != x) p=p->next; return p; 算法2.11(b)算法2.11(a)、(b)的時(shí)間復(fù)雜度均為O(n)。 3.插入(1)后插結(jié)點(diǎn)：設(shè)p指向單鏈表中某結(jié)點(diǎn)，s指向待插入的值為x的新結(jié)點(diǎn)，將*s插入到*p的后面，插入示意圖如圖2.13。操作如下： s->next=p->next;p->next=s;注意：兩個(gè)指針的操作順序不能交換。圖2.14 在*p之前插入*s s×pq圖2.13 在*p之后插入*s p s× (2)前插

14、結(jié)點(diǎn)：設(shè)指向鏈表中某結(jié)點(diǎn)，指向待插入的值為x的新結(jié)點(diǎn)，將*s插入到*p的前面，插入示意圖如圖2.14，與后插不同的是：首先要找到*p的前驅(qū)*q，然后再完成在*q之后插入*s，設(shè)單鏈表頭指針為L，操作如下：q=L;while (q->next!=p) q=q->next; /*找*p的直接前驅(qū)*/s->next=q->next; q->next=s;后插操作的時(shí)間復(fù)雜性為O(1)，前插操作因?yàn)橐?*p 的前驅(qū)，時(shí)間性能為O(n)；其實(shí)我們關(guān)心的更是數(shù)據(jù)元素之間的邏輯關(guān)系，所以仍然可以將 *s 插入到 *p 的后面，然后將->data與s->data交換

15、即可，這樣即滿足了邏輯關(guān)系，也能使得時(shí)間復(fù)雜性為O(1)。 (3)插入運(yùn)算 Insert_LinkList(L,i,x)算法思路：1.找到第i-1個(gè)結(jié)點(diǎn)；若存在繼續(xù)2，否則結(jié)束2.申請、填裝新結(jié)點(diǎn)； 3.將新結(jié)點(diǎn)插入。結(jié)束。算法如下：int Insert_LinkList( LinkList L, int i, datatype x) /*在單鏈表L的第i個(gè)位置上插入值為x的元素*/ Lnode * p,*s; p=Get_LinkList(L,i-1); /*查找第i-1個(gè)結(jié)點(diǎn)*/ if (p=NULL) printf(參數(shù)i錯(cuò));return 0; /*第i-1個(gè)不存在不能插入*/ els

16、e s=malloc(sizeof(LNode); /*申請、填裝結(jié)點(diǎn)*/ s->data=x; s->next=p->next; /*新結(jié)點(diǎn)插入在第i-1個(gè)結(jié)點(diǎn)的后面*/ p->next=s return 1; 算法2.12算法2.12的時(shí)間復(fù)雜度為O(n)。4. 刪除 (1)刪除結(jié)點(diǎn)：設(shè)p指向單鏈表中某結(jié)點(diǎn)，刪除*p。操作示意圖如圖2.15所示。通過示意圖可見，要實(shí)現(xiàn)對結(jié)點(diǎn)*p的圖2.15 刪除*p pq×刪除，首先要找到*p的前驅(qū)結(jié)點(diǎn)*q，然后完成指針的操作即可。指針的操作由下列語句實(shí)現(xiàn)：q->next=p->next;free(p);顯然找

17、*p前驅(qū)的時(shí)間復(fù)雜性為O(n)。若要刪除*p的后繼結(jié)點(diǎn)(假設(shè)存在)，則可以直接完成：s=p->next;p->next=s->next;free(s);該操作的時(shí)間復(fù)雜性為O(1) 。(2)刪除運(yùn)算：Del_LinkList(L,i)算法思路：1.找到第i-1個(gè)結(jié)點(diǎn)；若存在繼續(xù)2，否則結(jié)束；2.若存在第i個(gè)結(jié)點(diǎn)則繼續(xù)3，否則結(jié)束； 3.刪除第i個(gè)結(jié)點(diǎn)，結(jié)束。算法如下：int Del_LinkList(LinkList L，int i) /*刪除單鏈表L上的第i個(gè)數(shù)據(jù)結(jié)點(diǎn)*/ LinkList p,s; p=Get_LinkList(L,i-1); /*查找第i-1個(gè)結(jié)點(diǎn)*/ if (p=NULL) printf(第i-1個(gè)結(jié)點(diǎn)不存在);return -1; else if