數(shù)據(jù)結(jié)構(gòu)教學(xué)課件：第三講 線性表

1、數(shù)據(jù)結(jié)構(gòu)第三講1數(shù)據(jù)結(jié)構(gòu)這門課就是研究：邏輯結(jié)構(gòu)+物理結(jié)構(gòu)+算法線性表就是一種最簡單的結(jié)構(gòu)。邏輯結(jié)構(gòu)就是 物理結(jié)構(gòu)有兩種： 連續(xù)存儲的，順序表。非連續(xù)存儲的，單鏈表。上機(jī)學(xué)會了：單鏈表的建立過程。2例:在單鏈表中實現(xiàn)線性表的插入運(yùn)算INSERT（L,x,i)算法思想：(1)先將指針定位在第i-1個結(jié)點(diǎn)(2)然后在第i-1個結(jié)點(diǎn)之后插入結(jié)點(diǎn)x。單鏈表主要操作及算法：3按序號查找（知道循環(huán)的次數(shù)）設(shè)單鏈表的長度為n，要查找表中第i個結(jié)點(diǎn)，算法思想如下：從頭結(jié)點(diǎn)開始順鏈摸瓜，用指針p指向當(dāng)前摸到的結(jié)點(diǎn)，用j作統(tǒng)計已走過的結(jié)點(diǎn)數(shù)的計數(shù)器，當(dāng)p轉(zhuǎn)移到下一個結(jié)點(diǎn)時，j自動加1。P的初值指向頭結(jié)點(diǎn)，j的初值

2、為0。當(dāng)j=i時，指針p所指的結(jié)點(diǎn)就是第i個結(jié)點(diǎn)。4按序號查找算法描述GET(head,i) /先設(shè)計一個“定位”函數(shù)，省略了定義 int j; list *p; p=head;j=0; while(p-next!=null&(jnext;j+; /這是核心！ if (i=j) return p; /*找到第i個結(jié)點(diǎn)*/ else return null; /*找不到，返回空/*end*/沒*號？5在指定序號前插入算法實現(xiàn)：INSERT（L,x,i)list *p; int j; j=i-1; p=GET(L，j）；/*找到第i-1個結(jié)點(diǎn)*p*/if (p=null) printf(“找不到插

3、入點(diǎn)n“）else INSERT(p,x)/*end*/6刪除運(yùn)算（刪除單鏈表中*p的后繼）list *p;DeleteA(p) /*刪除*p的后繼結(jié)點(diǎn)*r,設(shè)*r存在*/list *r;if(p-next!=null)r=p-next; p rp-next=r-next; free(p);/*enddelete*/存儲池7思考：（1）如何刪除單鏈表中p結(jié)點(diǎn)本身？（2）如何刪除單鏈表中p結(jié)點(diǎn)的前趨結(jié)點(diǎn)？ 8和插入操作類似：在單鏈表上實現(xiàn)線性表的刪除運(yùn)算Delete(L,i)。算法思路：先找到被刪結(jié)點(diǎn)（第i個）的前趨結(jié)點(diǎn)，即第i-1個結(jié)點(diǎn)*p,然后刪除*p的后繼（ 需引用函數(shù)GET（L,i) )

4、。9刪除算法的實現(xiàn)：DELETE(L,i)JD *p;int j;j=i-1;p=GET(L，j)；/*找到第i-1個結(jié)點(diǎn)*p*/if (p!=null)&(P-next!=null)DeleteA(P);else printf(“errorn”)/*end*/思考：如何實現(xiàn)刪除線性表head中數(shù)據(jù)域為a的結(jié)點(diǎn)（循環(huán)次數(shù)不知道）。10循環(huán)鏈表整個鏈表形成一個環(huán)，從表中任一結(jié)點(diǎn)出發(fā)均可找到表中其它結(jié)點(diǎn)。特點(diǎn)：（1）表中最后一個結(jié)點(diǎn)的指針指向第一個結(jié)點(diǎn)或表頭結(jié)點(diǎn)（如有表頭結(jié)點(diǎn)的話）。h . (非空表） h (空表）a1 an 11（2）循環(huán)鏈表的運(yùn)算與線性鏈表基本一致。但兩者判斷是否到表尾的條件不

5、同：線性表：判斷某結(jié)點(diǎn)的鏈域是否為空。循環(huán)鏈表：判斷某結(jié)點(diǎn)的鏈域值是否等于頭指針。12（3）用頭指針表示的單循環(huán)鏈表查找結(jié)點(diǎn)：找a1(開始結(jié)點(diǎn)) O(1)找an 需要遍歷表 O(n)由于在實際問題中，對表的操作常在表的首尾位置進(jìn)行，因此可增加一個尾指針(rear)，則：找a1(開始結(jié)點(diǎn)) ：rear-next-next O(1)找an rear O(1)實用中多用尾指針表示單循環(huán)鏈表。13循環(huán)鏈表headhead非空表空表rearrear14表的合并：在鏈表上實現(xiàn)將兩個線性表(a1,a2,.,an)和(b1,b2bm)鏈接成一個線性表(a1,a2,.,an,b1,b2,.,bm)的運(yùn)算。分析：

6、若在單鏈表或頭指針表示的單循環(huán)鏈表上做這種鏈接運(yùn)算，都要遍歷第一個鏈表找到結(jié)點(diǎn)an，然后將結(jié)點(diǎn)b1鏈接到an的后面，其執(zhí)行時間為O（n）。算法思想：在尾指針表示的單循環(huán)鏈表上實現(xiàn)，則只需修改指針，無需遍歷，其執(zhí)行時間為O（1）。15兩個單循環(huán)鏈表（用尾指針表示）的鏈接示意圖rarbp16JD *CONNECT(ra,rb)JD *ra,*rb;JD *p; p=ra-next;/*保存鏈表ra的頭結(jié)點(diǎn)地址*/ra-next=rb-next-next;/*將表rb的開始結(jié)點(diǎn)鏈接到表ra的終結(jié)點(diǎn)之后*/free(rb-next);/*釋放鏈表rb的頭結(jié)點(diǎn)*/rb-next=p；/*鏈表ra的頭結(jié)點(diǎn)

7、鏈到鏈表rb的終端結(jié)點(diǎn)之后*/return rb ;/*返回新循環(huán)鏈表的尾指針*/ /*ENDCONNECT*/17循環(huán)鏈表的典型應(yīng)用：約瑟芬問題，又稱海盜問題。N個海盜打撈上一箱財寶，為了分出天意，制定了一個規(guī)則：全體海盜站成一圈，從第一個開始報數(shù)，報到約定的數(shù)字m，這個海盜就退出分財寶的行列，從下一個海盜開始重新報數(shù)直到隊伍里只剩下一個海盜，所有財寶歸他。18雙向鏈表（Double linked list)單鏈表查找特點(diǎn)的回顧：只能順鏈向后（順著直接后繼指針）查找。若要找某一結(jié)點(diǎn)的前趨，則：單鏈表：從頭順鏈找。O(n)單循環(huán)鏈表：可從任一已知結(jié)點(diǎn)出發(fā)查。O(n)19雙向鏈表（Double

8、linked list)-單鏈表的每個結(jié)點(diǎn)再增加一個指向其前趨的指針域 prior，這樣形成的鏈表有兩條不同方向的鏈，稱之為雙（向）鏈表。特點(diǎn)：雙鏈表一般也由頭指針head唯一確定。每一結(jié)點(diǎn)均有： 數(shù)據(jù)域（data) 左鏈域 （prior)指向前趨結(jié)點(diǎn). 右鏈域 （next)指向后繼。是一種對稱結(jié)構(gòu)（既有前趨，又有后繼）。20（1）雙向鏈表的分類：非循環(huán)雙向鏈表循環(huán)雙向鏈表此外，為了定義運(yùn)算方便起見，還可添加一表頭結(jié)點(diǎn)。（2）雙鏈表的結(jié)點(diǎn)類型描述typedef struct dnodedatatype data;struct dnode *prior,*next;dlinklist;dlink

9、list *head;21(3)結(jié)點(diǎn)結(jié)構(gòu)示意圖22雙鏈表結(jié)構(gòu)對稱性描述：p-prior-next=p-next-prior=p即：結(jié)點(diǎn)*p的存儲位置既存放在其前趨結(jié)點(diǎn)（*p-prior)的后繼指針域中；也存放在其后繼結(jié)點(diǎn)（*p-next)的前趨指針域中。23雙鏈表的基本運(yùn)算：插入、刪除、查找在單鏈表中，前插不如后插方便；刪除某結(jié)點(diǎn)自身不如刪除該結(jié)點(diǎn)的后繼方便。而在雙向鏈表中，上述的運(yùn)算均十分方便。24(前)插入操作（將結(jié)點(diǎn)x插入*p之前）/*在帶頭結(jié)點(diǎn)的雙鏈表中，將值為x的新結(jié)點(diǎn)插入到*p 之前。*/dinsert(p,x)dlinklist *p;datatype x;dlinklist *

10、s;s= (dlinklist) malloc(sizeof(dlinklist);s-data=x;s-prior=p-prior;s-next=p;p-prior-next=s;p-prior=s;/*enddinsert*/25spxa26刪除操作（在雙向鏈表中刪除p結(jié)點(diǎn)）Ddelete(p)dlinklist *p;p-prior-next=p-next;p-next-prior=p-prior;free(p);/*endDdelete*/27查找（在帶頭結(jié)點(diǎn)雙向循環(huán)鏈表中查找結(jié)點(diǎn)x）算法思想：從第一個結(jié)點(diǎn)開始（頭結(jié)點(diǎn)的后繼）依次比較每個結(jié)點(diǎn)的數(shù)據(jù)域的值，若找到結(jié)點(diǎn)x則返回指向該結(jié)點(diǎn)的指針；否則：若又回到頭結(jié)點(diǎn)，說明表中不存在頭結(jié)點(diǎn)x，則返回空指針。28關(guān)于順序表和鏈表的小結(jié)：（1）順序是用數(shù)組實現(xiàn)的，而鏈表是用指針或“游標(biāo)”來實現(xiàn)的。（2）當(dāng)線性表的長度變化較大，難以估計其存儲規(guī)模時， 益采用動態(tài)鏈表作為存儲結(jié)構(gòu)為佳；當(dāng)線性表的長度變化不大，易于事先確定其大小時，為了節(jié)約存儲空間，宜采用順序表作為存儲結(jié)構(gòu)。（基于空間的考