第三章線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)教案

1、第3章 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)l 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)l 線性表的應(yīng)用舉例線性表順序存儲結(jié)構(gòu)的特點它是一種簡單、方便的存儲方式。它要求線性表的數(shù)據(jù)元素依次存放在連續(xù)的存儲單元中，從而利用數(shù)據(jù)元素的存儲順序表示相應(yīng)的邏輯順序，這種存儲方式屬于靜態(tài)存儲形式。暴露的問題l 在做插入或刪除元素的操作時，會產(chǎn)生大量的數(shù)據(jù)元素移動；l 對于長度變化較大的線性表，要一次性地分配足夠的存儲空間，但這些空間常常又得不到充分的利用；l 線性表的容量難以擴(kuò)充。第一節(jié) 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)是指用一組任意的存儲單元（可以連續(xù)，也可以不連續(xù)）存儲線性表中的數(shù)據(jù)元素。為了反映數(shù)據(jù)元素之間的邏輯關(guān)系，對于每

2、個數(shù)據(jù)元素不僅要表示它的具體內(nèi)容，還要附加一個表示它的直接后繼元素存儲位置的信息。假設(shè)有一個線性表（a,b,c,d），可用下圖所示的形式存儲：存儲地址內(nèi)容直接后繼存儲地址100b120.首元素位置120c160.144a100.160dnull.術(shù)語表示每個數(shù)據(jù)元素的兩部分信息組合在一起被稱為結(jié)點；其中表示數(shù)據(jù)元素內(nèi)容的部分被稱為數(shù)據(jù)域（data）；表示直接后繼元素存儲地址的部分被稱為指針或指針域（next）。單鏈表簡化的圖形描述形式headd cba其中，head是頭指針，它指向單鏈表中的第一個結(jié)點，這是單鏈表操作的入口點。由于最后一個結(jié)點沒有直接后繼結(jié)點，所以，它的指針域放入一個特殊的值n

3、ull。null值在圖示中常用（）符號表示。帶頭結(jié)點的單鏈表為了簡化對鏈表的操作，人們經(jīng)常在鏈表的第一個結(jié)點之前附加一個結(jié)點，并稱為頭結(jié)點。這樣可以免去對鏈表第一個結(jié)點的特殊處理。如下圖所示：headd cba鏈?zhǔn)酱鎯Y(jié)構(gòu)的特點（1）線性表中的數(shù)據(jù)元素在存儲單元中的存放順序與邏輯順序不一定一致；（2）在對線性表操作時，只能通過頭指針進(jìn)入鏈表，并通過每個結(jié)點的指針域向后掃描其余結(jié)點，這樣就會造成尋找第一個結(jié)點和尋找最后一個結(jié)點所花費(fèi)的時間不等，具有這種特點的存取方式被稱為順序存取方式。在c語言中，實現(xiàn)線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)的類型定義typedef strcut node /結(jié)點類型 entryty

4、pe item; struct node *next;node;typedef struct /鏈表類型 node *head;link_list;典型操作的算法實現(xiàn)（1）初始化鏈表lint initlist(link_list *l) l->head=(*node)malloc(sizeof(node); /為頭結(jié)點分配存儲單元 if (l->head) l->head->next=null; return ok; else return error ;（2）銷毀鏈表l void destorylist(link_list *l) node *p; while (l-

5、>head) /依次刪除鏈表中的所有結(jié)點 p=l->head; l->head=l->head->next; free(p); （3）清空鏈表l void clearlist(link_list *l) node *p; while (l->head->next) p=l->head->next; /p指向鏈表中頭結(jié)點后面的第一個結(jié)點 l->head->next=p->next; /刪除p結(jié)點 free(p); /釋放p結(jié)點占據(jù)的存儲空間 （4）求鏈表l的長度int listlength(link_list l) node

6、 *p; int len; for(p=l.head, len=0;p->next=null; p=p->next,len+); return(len);（5）判鏈表l空否。 int isempty(link_list l) if (l.head->next=null) return true; else return false; （6）通過e返回鏈表l中第i個數(shù)據(jù)元素的內(nèi)容void getelem(link_list l,int i,entrytype *e) node *p; int j; if (i<1|i>listlength(l) exit error

7、; /檢測i值的合理性 for (p=l.head,j=0; j!=i;p=p->next,j+); /找到第i個結(jié)點 *e=p->item; /將第i個結(jié)點的內(nèi)容賦給e指針?biāo)赶虻拇鎯卧校?）在鏈表l中檢索值為e的數(shù)據(jù)元素node *locateelem(link_list l,entrytype e) node *p; for (p=l.head->next;p&&p->item!=e;p=p->next); /尋找滿足條件的結(jié)點 return(p);（8）返回鏈表l中結(jié)點e的直接前驅(qū)結(jié)點node *priorelem(link_list

8、l,node* e) node *p; if (l.head->next=e) return null; /檢測第一個結(jié)點 for (p=l.head;p->next&&p->next!=e;p=p->next); if (p->next=e) return p; esle return null; （9）返回鏈表l中結(jié)點e的直接后繼結(jié)點node *nextelem(link_list l,node* e) node *p; for(p=l.head->next;p&&p!=e;p=p->next); if (p) p=

9、p->next; return p;（10）在鏈表l中第i個數(shù)據(jù)元素之前插入數(shù)據(jù)元素e int listinsert(link_list *l,int i,entrytype e) node *p,*s; int j; if (i<1|i>listlength(l)+1) return error; s=(node*)malloc(sizeof(node); if (s=null) return error; s->item=e; for (p=l->head,j=0;p&&j<i-1;p=p->next;j+); /尋找第i-1個結(jié)點

10、 s->next=p->next; p->next=s; /將s結(jié)點插入 return ok;（11）將鏈表l中第i個數(shù)據(jù)元素刪除，并將其內(nèi)容保存在e中。int listdelete(link_list *l,int i,entrytype *e) node *p*s; int j; if (i<1|i>listlength(l) return error; /檢查i值的合理性 for(p=l->head, j=0;j<i-1;p=p->next,j+); /尋找第i-1個結(jié)點 s=p->next; /用s指向?qū)⒁獎h除的結(jié)點 *e=s-&g

11、t;item; p->next=s->next; /刪除s指針?biāo)赶虻慕Y(jié)點 free(s); return ok;循環(huán)鏈表若將鏈表中最后一個結(jié)點的next域指向head圖2-7 帶頭結(jié)點的循環(huán)鏈表示意圖實現(xiàn)循環(huán)鏈表的類型定義與單鏈表完全相同，它的所有操作也都與單鏈表類似。只是判斷鏈表結(jié)束的條件有所不同。下面我們就列舉兩個循環(huán)鏈表操作的算法示例。（1）初始化鏈表clint initlist(link_list *cl) cl->head=(*node)malloc(sizeof(node); if (cl->head) cl->head->next=cl-&g

12、t;head; return ok; /讓next域指向它自身 else return error ;（2）在循環(huán)鏈表cl中檢索值為e的數(shù)據(jù)元素node *locateelem(link_list cl,entrytype e) node *p; for (p=cl.head->next;(p!=cl.head)&&(p->item!=e);p=p->next); if (p!=cl.head) return p; else return null ;雙向循環(huán)鏈表在循環(huán)鏈表中，訪問結(jié)點的特點訪問后繼結(jié)點，只需要向后走一步，而訪問前驅(qū)結(jié)點，就需要轉(zhuǎn)一圈。結(jié)論：循

13、環(huán)鏈表并不適用于經(jīng)常訪問前驅(qū)結(jié)點的情況。解決方法：在需要頻繁地同時訪問前驅(qū)和后繼結(jié)點的時候，使用雙向鏈表。所謂雙向鏈表。雙向鏈表就是每個結(jié)點有兩個指針域。一個指向后繼結(jié)點，另一個指向前驅(qū)結(jié)點。head用c語言實現(xiàn)雙向循環(huán)鏈表的類型定義typedef strcut du_node /雙向鏈表的結(jié)點類型 entrytype item; struct du_node *prior,*next;du_node;typedef struct /雙向鏈表類型 du_node *head;prioritemnextdu_link_list;（1）初始化雙向循環(huán)鏈表dlint initdulist(du_li

14、nk_list *dl) dl->head=(du_node*)malloc(sizeof(du_node); /為頭結(jié)點分配存儲單元 if (dl->head=null) return error; dl->head->next=dl->head; /讓頭結(jié)點的next域指向自身 dl->head->prior=dl->head; /讓頭結(jié)點的prior域指向自身 return ok;（2）在雙向循環(huán)鏈表dl中，第i個數(shù)據(jù)元素之前插入數(shù)據(jù)元素eps在一個結(jié)點之前插入一個新結(jié)點的過程。在雙向循環(huán)鏈表中的p結(jié)點之前插入s結(jié)點應(yīng)使用下列語句序列：s-

15、>next=p;s->prior=p->prior;p->prior->next=s;p->prior=s;完整的算法：int dulistinsert(du_link_list *l,int i,entrytype e) du_node *p,*s; int j; if (i<1|i>listlength(dl)+1) return error; /檢測i值的合理性 s=(du_node*)malloc(sizeof(du_node); /為新結(jié)點分配存儲單元 if (s=null) return error; s->item=e; fo

16、r (p=l->head,j=0;p&&j<i;p=p->next;j+); /尋找第i 個結(jié)點 s->next=p; s->prior=p->prior; /將新結(jié)點插入 p->prior->next=s; p->prior=s; return ok;（3）創(chuàng)建雙向循環(huán)鏈表dl。void create_du_link_list(du_link_list *dl) if (initdulist(dl)=error) exit error; scanf(“%d”,&data); for (int i=1;data;i+

17、) dulistinsert(dl,i,data); scanf(“%d”,&data); 第二節(jié) 線性表的順序與鏈?zhǔn)酱鎯Y(jié)構(gòu)的比較順序存儲結(jié)構(gòu)特點：用數(shù)組實現(xiàn)，操作簡便，但如果在操作時插入，刪除元素過多，則需要移動大量元素，會降低程序的效率。鏈?zhǔn)酱鎯Y(jié)構(gòu)特點：用鏈表實現(xiàn)，操作相對復(fù)雜，但對于移動大量元素的情況，可有效地利用空間。第三節(jié) 線性表的應(yīng)用舉例約瑟夫（joseph）問題：編號為1，2，···，n的n個人按順時針方向圍坐在一張圓桌旁，每個人手中持有一個密碼（正整數(shù)）。首先輸入一個正整數(shù)作為報數(shù)上限值m，然后，從第一個人開始按順時針方向自1開始順序報

18、數(shù)，報到m的人離開桌旁，并將他手中的密碼作為新的m值，從順時針方向的下一個就坐在桌旁的人人開始重新從1報數(shù)，如此下去，直至所有人全部離開桌旁為止。假設(shè)有7個人，編號從1到7，他們手中的密碼分別是3，1，7，2，4，8，4，最初的m=2，通過報數(shù)，這7個人離開桌旁的順序應(yīng)該是：2，3，5，4，7，6，1。數(shù)據(jù)結(jié)構(gòu)的分析這個問題的主角是n個人，每個人需要描述的信息有：編號、密碼和是否在桌旁的狀態(tài)。假設(shè)有7個人，他們的信息可以表示成下面的形式。編號密碼是否在桌旁的狀態(tài)131211371421541681741順序存儲結(jié)構(gòu)算法描述讓n個人圍坐在一張圓桌旁；for (i=1;i<=n;i+) 從1

19、開始報數(shù)，報到m停止； 報到m的人離開桌子；最終的算法實現(xiàn)#define list_max_length 7#define n list_max_lengthtypedef int entrytype; /將entrytype定義為int類型void joseph(int code,int n)/通過一維數(shù)組code帶入n個人手中的密碼，n是開始就坐在桌旁的人數(shù) sq_list people; int temp,m; /m是報數(shù)的上限值 scanf(“%d”,&m); /輸入最初的m if (initlist(&people)=error) exit error; for (i

20、=1;i<=n;i+) if (listinsert(&people,i,codei-1)=error) exit error; position=0; /記錄當(dāng)前報數(shù)人的編號 for (i=1;i<=n;i+) count=0; /記錄當(dāng)前所報的數(shù)目 do /報數(shù) position=(position+1)%n; getelem(people,position,&temp); if (temp>0) count+; while (count!=m); printf(“%d”,position); /輸出當(dāng)前離開桌旁人的編號 getelem(people,position,&m); people.itemposition-1=-people.itemposition-1; /將密碼變?yōu)樨?fù)值 鏈?zhǔn)酱鎯Y(jié)構(gòu)使用一個不帶頭結(jié)點的循環(huán)單鏈表結(jié)構(gòu)。結(jié)點結(jié)構(gòu)為：no code next用c語言定義typedef struct /循環(huán)鏈表中每個結(jié)點的數(shù)據(jù)域部分的類型 int no; /編號 int code; /密碼info;typedef info entrytype;算法void joseph(int code,int n) link