《數(shù)據(jù)結(jié)構(gòu)與算法》課件chap02-2

1、2.3 線性表的鏈式存儲和實現(xiàn) 線性表的鏈式存儲結(jié)構(gòu)是用一組任意的存儲單元存儲線性表的各個數(shù)據(jù)元素。為了表示線性表中元素的先后關系，每個元素除了需要存儲自身的信息外還需保存直接前趨元素或直接后繼元素的存儲位置。ai+1a1ai-1a2aian2.3 線性表的鏈式存儲和實現(xiàn) 2.3.1 線性鏈表 一 線性鏈表的概念 二 線性鏈表的基本操作算法 三 線性鏈表的其它操作 2.3.2 循環(huán)鏈表 2.3.3 雙向鏈表 一 雙向鏈表的概念 二 雙向鏈表的基本操作算法一 線性鏈表的概念1 線性鏈表2. 3. 1 線性鏈表a4a3a1a2 01010102410141010101210141016101810

2、20102210241026 用一組任意的存儲單元存儲線性表中的數(shù)據(jù)元素，對每個數(shù)據(jù)元素除了保存自身信息外，還保存了直接后繼元素的存儲位置。 用線性鏈表存儲線性表時，數(shù)據(jù)元素之間的關系是通過保存直接后繼元素的存儲位置來表示的ai-1aia2a1ai+1nan結(jié)點：數(shù)據(jù)元素及直接后繼的存儲位置（地址）組成一個數(shù)據(jù)元素的存儲結(jié)構(gòu)，稱為一個結(jié)點；結(jié)點的數(shù)據(jù)域 ：結(jié)點中用于保存數(shù)據(jù)元素的部分;結(jié)點的指針域 ：結(jié)點中用于保存數(shù)據(jù)元素直接后繼存儲地址的部分; 線性鏈表有關術語2. 3. 1 線性鏈表存儲數(shù)據(jù)元素存儲后繼結(jié)點 存儲地址結(jié)點數(shù)據(jù)域指針域2. 3. 1 線性鏈表頭指針：用于存放線性鏈表中第一個結(jié)

3、點的存儲地址;空指針：不指向任何結(jié)點，線性鏈表最后一個結(jié)點的指針通常是空指針;頭結(jié)點：線性鏈表的第一元素結(jié)點前面的一個附加結(jié)點，稱為頭結(jié)點；帶頭結(jié)點的線性鏈表：第一元素結(jié)點前面增加一個附加結(jié)點的線性鏈表稱為 帶頭結(jié)點的線性鏈表； head是頭指針ai-1aia2a1ai+1nan 頭結(jié)點 空指針head線性鏈表的每個結(jié)點中只有一個指針域故也稱為單鏈表2. 3. 1 線性鏈表怎樣在計算機上實現(xiàn)線性鏈表？ 2. 3. 1 線性鏈表結(jié)點變量圖示 struct node int data; Struct node *next;typedef struct node NODE;Node：結(jié)構(gòu)類型名； N

4、ode類型結(jié)構(gòu)變量有兩個域： data：用于存放線性表的數(shù)據(jù)元素， next：用于存放元素直接后繼結(jié)點的地址；該類型結(jié)構(gòu)變量用于表示線性鏈表中的一個結(jié)點；NODE *p： p為指向結(jié)點(結(jié)構(gòu))的指針變量； 數(shù)據(jù)域指針域 data next node類型 結(jié)構(gòu)變量pp是NODE類型的指針變量 線性鏈表的結(jié)點類型定義及指向結(jié)點的指針類型定義2.3 線性鏈表兩個C 函數(shù)1) malloc(int size) 功能：在系統(tǒng)內(nèi)存中分配size個的存儲單元，并返回該空間的基址。使用方法： p = (NODE *) malloc(sizeof(NODE ); 為p申請一個結(jié)點p p = (NODE *)ma

5、lloc(sizeof(NODE); 圖示2.2 線性鏈表 調(diào)用free ( p ) 0 1 2 99p 調(diào)用free ( p ) 圖示2) free ( p ) 功能：將指針變量p所指示的存儲空間，回收到系統(tǒng)內(nèi)存空間中去使用方法： . NODE *p; p = (NODE *) malloc (sizeof (NODE); / 一旦p所指示的內(nèi)存空間不再使用， /調(diào)用free( ) 回收之 free(p);2. 3. 1 線性鏈表ai-1aia2a1ai+1nanP二 線性鏈表基本操作的算法如何在線性鏈表上實現(xiàn)線性表的基本操作？如何建表？如何插入？刪除？約定用帶頭結(jié)點的線性鏈表存儲線性表2.

6、3.1 線性鏈表head算法：NODE *create_head ( ) NODE *head head = (NODE *)malloc(sizeof(NODE); head-next = null; Return (head); 1）初始化操作 功能： 建空線性鏈表參數(shù)： head 為線性鏈表的頭指針主要步驟：調(diào)用malloc ( )分配一結(jié)點的空間,并將其地址賦值給head；建立鏈表NODE *create_link(n) /*建立有n個結(jié)點的線性單鏈表的算法 NODE *head, *p, *q; int i; p=( NODE *)malloc(sizeof(NODE);head=p

7、; for(i=1;idata=i; q-next=NULL; p-next=q;p=q;return(head); 算法的時間復雜度為:O(n) 插入結(jié)點q=(NODE *)malloc(sizeof(NODE); q-deta=a; q-next=p-next; p-link=q;headzyxpyxzpheada3 插入操作 Insert_link(NODE *head, int x, int i) 功能：在線性鏈表的第i個元素結(jié)點之前插入一個新元素結(jié)點x； 插入操作圖示：2. 3. 1 線性鏈表插入前插入后 ai-1aia2a1ai+1nanheadai-1aia2a1ai+1nanx

8、head2. 3. 1 線性鏈表插入操作主要步驟：1）查找鏈表L的第 i-1個元素結(jié)點；2）為新元素建立結(jié)點；3）修改第 i-1個元素結(jié)點的指針和新元素結(jié)點指針完成插入；Int insert_link(NODE *head,int x, int i) NODE *p,*s;int j; p=head;j=0; while (p!=NULL)&(jnext;j+;if(p=NULL)return(0);s=(NODE *(malloc(sizcof(NODE);s-data=x;s-next=p-next;p-next=s;return(1); 算法的時間復為:O(ListLength(L) 刪

9、除結(jié)點q=p-next; p-next=q-next; free(q);headzyxqyxzqheadpp2. 3. 1 線性鏈表刪除操作主要步驟：1）查找鏈表的第 i-1個元素結(jié)點,使指針p指向它, 將指針q指向第i個結(jié)點；2）修改第 i-1個元素結(jié)點指針，使其指向第i個元素結(jié)點的后繼；3) 回收q指針所指的第i個結(jié)點空間； 2. 3. 1 線性鏈表刪除前刪除后ai-1aia2a1ai+1nanheadai-1aia2a1ai+1nanheadppqq在線性鏈表中刪除第i個結(jié)點Int delete_link(NODE *head, int i) NODE *p,*q;int j; p=he

10、ad;j=0; while (p-next!=NULL)&(jnext;j+;if(p=NULL)return(0);q=p-next;p-next=q-next;free(q);return(1); 2.3.1 線性鏈表三 線性鏈表的其他操作的實現(xiàn)例：將兩個遞增有序線性鏈表歸并成一個遞減有序表。 設線性表A、B分別用頭指針為head_a 、 head_b 的兩個帶頭結(jié)點的線性鏈表存儲, 歸并后的遞減有序表頭指針為head, 將兩表數(shù)據(jù)較小的結(jié)點依次取出插入到新表利用基本操作直接對鏈表進行操作2.3.1 線性鏈表線性鏈表歸并操作圖示73n952n7head_ahead_b79n2head387

11、85NODE * merge_link( NODE *head_a, NODE *head_b) NODE *p, *q, *head; head=(NODE *)malloc(sizeof (NODE); head-next=NULL; p=head_a-next; q=head_b-next; while(p!=NULL) &(q!=NULL) If (p-datadata) head_a-next=p-next;p-next=head-next; head-next=p; p=head_a-next; else head_b-next=q-next;q-next=head-next; h

12、ead-next=q; q=head_b-next;while(p!=NULL) head_a-next=p-next;p-next=head-next; head-next=p; p=head_a-next; while(q!=NULL) head_b-next=q-next;q-next=head-next; head-next=q; q=head_b-next; free(head_a); free(head_b); return(head);2. 3. 1 線性鏈表小結(jié)線性鏈表是線性表的一種鏈式存儲結(jié)構(gòu) 線性鏈表的特點 1 通過保存直接后繼元素的存儲位置來表示 數(shù)據(jù)元素之間的邏輯關系；

13、 2 插入刪除操作通過修改結(jié)點的指針實現(xiàn)； 3 不能隨機存取元素；其他形式的鏈表圖2. 靜態(tài)鏈表靜態(tài)鏈表下面先請看圖2.22 ，在下圖中，規(guī)模較大的結(jié)構(gòu)數(shù)組 sdMAXSIZE 中有兩個鏈表：其中鏈表SL是一個帶頭結(jié)點的單鏈表，表示了線性表(a1, a2, a3, a4, a5)，而另一個單鏈表AV是將當前 sd 中的空結(jié)點組成的鏈表。 datanextSL=0041a452a233a314a125a5-1 AV=6677889910101111-1數(shù)組sd的定義如下： #define MAXSIZE /*足夠大的數(shù)*/ typedef struct datatype data; int ne

14、xt; SNode; /*結(jié)點類型*/ SNode sdMAXSIZE; int SL,AV; /*兩個頭指針變量*/ 這種鏈表的結(jié)點中也有數(shù)據(jù)域data和指針域next，與前面所講的鏈表中的指針不同的是，這里的指針是結(jié)點的相對地址(數(shù)組的下標)，稱之為靜態(tài)指針，這種鏈表稱之為靜態(tài)鏈表，空指針用-1表示，因為上面定義的數(shù)組中沒有下標為-1的單元。在上圖中，SL是用戶的線性表，AV模擬的是系統(tǒng)存儲池中空閑結(jié)點組成的鏈表，當用戶需要結(jié)點時，例如向線性表中插入一個元素，需自己向AV申請，而不能用系統(tǒng)函數(shù)malloc來申請 。向AV申請的相關語句為：if(AV!=-1) t=AV; AV=sdAV.n

15、ext; 所得到的結(jié)點地址(下標)存入了 t 中；不難看出當AV表非空時，摘下了第一個結(jié)點給用戶。當用戶不再需要某個結(jié)點時，需通過該結(jié)點的相對地址 t 將它還給AV，相關語句為： sdt.next=AV; AV=t;而不能調(diào)用系統(tǒng)的 free 函數(shù)。交給AV表的結(jié)點鏈在了AV的頭部。 下面通過線性表插入這個例子看靜態(tài)鏈表操作。例、 在帶頭結(jié)點的靜態(tài)鏈表SL的第i個結(jié)點之前插入一個值為x的新結(jié)點。設靜態(tài)鏈表的存儲區(qū)域sd為全局變量。int Insert_SList( int SL, datatype x, int i) int p,s; p=SL; j=0; while(sdp.next!=-1

16、 & jnext是否為NULL,而是它們是否等于首指針； 對循環(huán)鏈表，有時不給出頭指針，而是給出尾指針aa1an給出尾指針的循環(huán)鏈表2. 4 單向 循環(huán)鏈表baa1anbb1bnaa1anb1bnqqppp=a-next; q=b-next;a-next=q-next;b-next=p;free(q);約瑟夫回環(huán)問題設編號為1，2， n的n個人圍坐一圈，約定編號為k（1=knext!=p) while(inext!=p) i+; q=p; p=p-next; if (p-next!=p) i=1; printf( “%d”, p-data); q-next=p-next; q=p; p=p-n

17、ext; free(q); else printf(“%d”, p-data); 1 雙向鏈表的概念 2. 5 雙向鏈表(a)結(jié)點圖示數(shù)據(jù)域指針域指針域結(jié)點存儲數(shù)據(jù)元素存儲后繼結(jié)點 的地址存儲前趨結(jié)點 的地址 雙向鏈表中，每個結(jié)點有兩個指針域，一個指向直接后繼元素結(jié)點，另一個指向直接前趨元素結(jié)點。2.5 雙向鏈表2 雙向鏈表圖示head (b)空的雙向循環(huán)鏈表（c）非空的雙向循環(huán)鏈表headabStruct node int data struct node * prior, *next;在雙向鏈表中刪除結(jié)點時指針變化情況在雙向鏈表中插入一個結(jié)點時指針的變化情況pai-1xaipaiai+1a

18、i-12.5 雙向鏈表3、雙向鏈表的基本操作算法2.5 雙向鏈表1）插入操作算法 (在p 所指結(jié)點之前插入q 結(jié)點的過程 )q=(NODE *)malloc(sizeof (NODE);q-data=x;q-next=p; q-prior=p-prior;(p-prior)-next=q; p-prior=q;2.5 雙向鏈表2）刪除操作算法(p-prior)-next=p-next;(p-next)-prior=p-prior;free(p);aiai+1pai-12. 6 一元多項式的表示及相加 計算機 領域： P= (p0, p1, p2 , pn) Q= (q0, q1, q2, qm

19、) R= (p0+q0, p1+q1, , pm+qm, pm+1, , pn )P (x) = p0 + p1 x + p2 x2 + + pn xnQ (x) = q0 + q1 x + q2 x2+ + qm xm 不失一般性，設mn 則兩個多項式相加可表為R (x) = (p0 +q0) + (p1+q1) x + +(pn+qm)xm + pm+1 xm + +pn xn一、一元多項式的表示 數(shù)學上：為用計算機實現(xiàn)多項式運算，如何表示一元多項式？ 24 一元多項式的表示及相加 例： S (x) = 1 + 3 x 1000 + 2 x 2000 非零系數(shù)指數(shù)線性表: (1,0), (

20、3,1000), (2,2000)系數(shù)線性表( 1,0,0,3,0,0,2) 如何存儲一元多項式？例：求兩多項式的和多項式 A (x) = 7 +3 x + 9 x 8 + 5 x 17 B (x) = 8 x + 22 x 7 9 x 8 C (x) = A (x) + B (x) = 7 + 11x +22 x 7 + 5 x 17A=( (7,0),(3,1),(9,8),(5,17)B=( (8,1),(22,7),(-9,8)C=(7,0),(11,1),(22,7),(5,17)26 一元多項式的表示及相加1）元素的類型定義struct nodeint coef ; /存儲項系數(shù)i

21、nt index; /存儲項指數(shù)struct node * next ;typedef struct node NODE;2 一元多項式鏈式存儲結(jié)構(gòu)為用線性鏈表表示一元多項式，我們要給出數(shù)據(jù)元素的類型定義 coef index nextADT Polynomial 數(shù)據(jù)對象： 數(shù)據(jù)關系：抽象數(shù)據(jù)類型一元多項式的定義如下：D ai | ai TermSet, i=1,2,.,m, m0 TermSet 中的每個元素包含一個 表示系數(shù)的實數(shù)和表示指數(shù)的整數(shù) R1 |ai-1 ,aiD, i=2,.,n 且ai-1中的指數(shù)值ai中的指數(shù)值 CreatPolyn ( &P, m ) DestroyPo

22、lyn ( &P ) PrintPolyn ( &P ) 基本操作：操作結(jié)果：輸入 m 項的系數(shù)和指數(shù)， 建立一元多項式 P。初始條件：一元多項式 P 已存在。操作結(jié)果：銷毀一元多項式 P。初始條件：一元多項式 P 已存在。操作結(jié)果：打印輸出一元多項式 P。 PolynLength( P ) AddPolyn ( &Pa, &Pb ) SubtractPolyn ( &Pa, &Pb ) ADT Polynomial初始條件：一元多項式 P 已存在。操作結(jié)果：返回一元多項式 P 中的項數(shù)。初始條件：一元多項式 Pa 和 Pb 已存在。操作結(jié)果：完成多項式相加運算，即： Pa = PaPb，并銷

23、毀一元多項式 Pb。26 一元多項式的表示及相加 一元多項式鏈式存儲結(jié)構(gòu)圖示head-1 1 0 3 10002 2000頭結(jié)點24 一元多項式的表示及相加例：求兩多項式的和多項式 A (x) = 7 +3 x + 9 x 8 + 5 x 17 B (x) = 8 x + 22 x 7 9 x 8三、一元多項式的相加算法 C (x) = A (x) + B (x) = 7 + 11x +22 x 7 + 5 x 17 一元多項式的相加ah-17 03 19 85 17bh-18 122 7-9 8 2.4 一元多項式的表示及相加和多項式鏈表 設多項式A (x) ，B (x)分別用帶表頭結(jié)點的線

24、性鏈表ah,bh表示，和多項式C (x)用帶表頭結(jié)點的線性鏈表ch表示 如何實現(xiàn)用這種線性鏈表表示的多項的加法運算？ch=ah+bh ah=ah+bhbh=ah+bh-17 011 15 1722 7ch26 一元多項式的表示及相加 一元多項式的相加算法圖示ah-17 03 19 85 17bh-18 122 7-9 822 7-17 011 15 17ah26 一元多項式的表示及相加 一元多項式加法算法主要步驟分別對兩個鏈表ah 、bh進行掃描，設p 、q 分別指向線性鏈表ah 、 bh的當前進行比較的某個結(jié)點：p-index index ： p 所指結(jié)點應為和多項式中的結(jié)點p-index

25、= q-index ：將p所指結(jié)點的系數(shù)“加”到q所指結(jié)點的系數(shù)上相加；p-index q-index ： 從表bh中刪除q 所指結(jié)點，并將其插入到ah表p所指結(jié)點之前；一元多項式的相加算法（算法2.8） void addpoly(NODE *ah, NODE * bh) NODE *pre_p, *p, *q, *temp; char comp; pre_p=ah; p=ah-next; q=bh-next; while (p!=NULL)&(q!=NULL) comp=compare(p-index, q-index) switch(comp)（接下頁）續(xù) case next; break; case =: /兩者的指數(shù)值相等 p-coef+=q-coef ; if (p-coef =0. 0) / 合并后系數(shù)為0 pre_p-next=p-next; free(p); else pre_p=p; p=pre_p-next; temp=q; q=q-next; free(temp); break; case : /多項式A中當前結(jié)點的指數(shù)值大 temp=q-next; q-next=p; pre_p-next=q; pre_p=q; q=temp; 續(xù) if (q!=NULL) pre_p-next=q; free(bh); char c