數(shù)據(jù)結(jié)構(gòu)2.線性表

1、一、在內(nèi)存的表示一、在內(nèi)存的表示 loc(ai) = loc(a1)+(i-1)* *len 順序表的訪問(wèn)是順序表的訪問(wèn)是 隨機(jī)的。隨機(jī)的。思考：算法的選擇及效率思考：算法的選擇及效率（1）每次刪除）每次刪除1個(gè)元素，做個(gè)元素，做k次次（2）一次將）一次將k個(gè)元素全部刪除個(gè)元素全部刪除已知順序存儲(chǔ)的線性表已知順序存儲(chǔ)的線性表 la la 和和 lb lb 中元素依值中元素依值 遞增有序排列，歸并這兩個(gè)線性表得到一個(gè)新遞增有序排列，歸并這兩個(gè)線性表得到一個(gè)新 的線性表的線性表 lc , lc lc , lc 中的元素也依值遞增有序中的元素也依值遞增有序 排列的。排列的。分析：分析： （1 1）

2、將將lala表和表和lblb表中的較小值歸并至表中的較小值歸并至lclc表中表中 （2 2） 當(dāng)其中某個(gè)表結(jié)束后，將另一個(gè)表的剩余當(dāng)其中某個(gè)表結(jié)束后，將另一個(gè)表的剩余部分歸并至部分歸并至lclc表中表中 void merge(sqlist lb, sqlist la, sqlist &lc)void merge(sqlist lb, sqlist la, sqlist &lc) / /將兩個(gè)有序表將兩個(gè)有序表lala和和lblb，歸并為一個(gè)新的有序表，歸并為一個(gè)新的有序表lclc i=1,j=1,k=0; i=1,j=1,k=0; /初始化初始化 if (la.length +

3、 lb.length=listsize) if (la.length + lb.length=listsize) lc.length = la.length + lb.length lc.length = la.length + lb.length while (i=la.length & j=lb.length) while (i=la.length & j=lb.length) / / 歸并歸并 if (la.vi=lb.vj) lc.v+k=la.vi+;if (la.vi=lb.vj) lc.v+k=la.vi+; else lc.v+k=lb.vj+; else lc

4、.v+k=lb.vj+; / / 將將lala表和表和lblb表中的較小值歸并至表中的較小值歸并至lclc表中表中 while (i=la.length) lc.v+k=la.vi+;while (i=la.length) lc.v+k=la.vi+; / /將將lala表的剩余部分歸并至表的剩余部分歸并至lclc表中表中 while (j=lwhile (j=lb.length) lc.v+k=lb.vj+;.length) lc.v+k=lb.vj+; / /或或 將將lblb表的剩余部分歸并至表的剩余部分歸并至lclc表中表中 例例2.1.4 2.1.4 已知線性表存于已知線性表存于a1

5、.MAXSIZEa1.MAXSIZE中的前中的前n n個(gè)分量個(gè)分量 中，寫一算法刪除表中所有值為中，寫一算法刪除表中所有值為0 0的元素（將非的元素（將非 0 0元素移到前面來(lái)），各元素間的相對(duì)位置不變。元素移到前面來(lái)），各元素間的相對(duì)位置不變。void alg4( int a, int &n ) /刪除所有值為刪除所有值為0的元素的元素 i=1; while(i=n)&(ai!=0) i=i+1; / 找到第找到第1個(gè)值為個(gè)值為0的結(jié)點(diǎn)的結(jié)點(diǎn) for (j=i+1; jn) error( 參數(shù)錯(cuò)參數(shù)錯(cuò) ); else for (i=1;i=k; i+) for(j=1;j0)

6、 j=1; for(i=2;i=n;i+) k=1; while(k=0)個(gè)元素的有限集。每個(gè)元素的類型是相同個(gè)元素的有限集。每個(gè)元素的類型是相同的，元素之間的位置關(guān)系是一維的，元素之間的位置關(guān)系是一維(線性線性)的。的。二、二、線性表存儲(chǔ)結(jié)構(gòu)線性表存儲(chǔ)結(jié)構(gòu) 1. 順序存儲(chǔ)順序存儲(chǔ) 2. 鏈?zhǔn)酱鎯?chǔ)鏈?zhǔn)酱鎯?chǔ)三、線性表的操作三、線性表的操作 插入、刪除插入、刪除、 定位、查找、排序定位、查找、排序 等等2.2 線性鏈表2.2.1 2.2.1 單向鏈表單向鏈表一、在內(nèi)存的表示一、在內(nèi)存的表示 （a,b,c,d)a,b,c,d) 在在b,cb,c之間插入之間插入x:x:(a,b,x,c,d)(a,b,

7、x,c,d)思考：比較順序表與鏈表的不同。思考：比較順序表與鏈表的不同。提示：從下面提示：從下面3 3個(gè)方面考慮個(gè)方面考慮（1 1）數(shù)據(jù)的邏輯順序與物理順序）數(shù)據(jù)的邏輯順序與物理順序（2 2）數(shù)據(jù)的存?。ㄔL問(wèn)）數(shù)據(jù)的存?。ㄔL問(wèn)）（3 3）數(shù)據(jù)的插入和刪除操作）數(shù)據(jù)的插入和刪除操作二、鏈表的表示二、鏈表的表示三算法設(shè)計(jì)三算法設(shè)計(jì)（一）（一）定位算法設(shè)計(jì)定位算法設(shè)計(jì) 1.1.功能功能 在鏈表中查找（定位于）第在鏈表中查找（定位于）第i i個(gè)結(jié)點(diǎn)，若存在，個(gè)結(jié)點(diǎn)，若存在，則返回該結(jié)點(diǎn)的地址，否則，返回空（則返回該結(jié)點(diǎn)的地址，否則，返回空（NULLNULL）。）。 2.2.算法思想算法思想 從頭結(jié)點(diǎn)開(kāi)

8、始，逐個(gè)查找（從頭結(jié)點(diǎn)開(kāi)始，逐個(gè)查找（后移）后移）并計(jì)數(shù)，直到并計(jì)數(shù)，直到第第i i個(gè)止。個(gè)止。3. 3. 算法設(shè)計(jì)算法設(shè)計(jì)node node * *loc(node loc(node * *head, int i) head, int i) /head: /head:帶頭結(jié)點(diǎn)的單鏈表的頭指針，該算法定位于鏈表中的第帶頭結(jié)點(diǎn)的單鏈表的頭指針，該算法定位于鏈表中的第i i個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn) node node * *p=head;p=head; /指針初始化指針初始化, p, p指向頭結(jié)點(diǎn)指向頭結(jié)點(diǎn) j=0; j=0; / j/ j為計(jì)數(shù)器，初值為為計(jì)數(shù)器，初值為0 0 while (p!=NULL)

9、&(ji) while (p!=NULL)&(jnext; j+; p=p-next; j+; /p/p后移，后移，j j計(jì)數(shù)計(jì)數(shù), p, p移至第移至第i i個(gè)結(jié)點(diǎn)止個(gè)結(jié)點(diǎn)止。 return (p); return (p); / p/ p指向第指向第i i個(gè)結(jié)點(diǎn)（返回第個(gè)結(jié)點(diǎn)（返回第i i個(gè)結(jié)點(diǎn)的地址）個(gè)結(jié)點(diǎn)的地址） 4 4算法分析：算法分析： 定位定位(loc)(loc)算法的執(zhí)行時(shí)間與查找位置算法的執(zhí)行時(shí)間與查找位置i i有關(guān)。有關(guān)。要找到第要找到第i i個(gè)位置，指針個(gè)位置，指針p p就后移就后移i i次。次。 設(shè)設(shè)i,i=1,.,ni,i=1,.,n處是等概率的，則指針

10、處是等概率的，則指針p p后移：后移： (1+2+(1+2+（n-1n-1）+n+n）/n = n/2/n = n/2次。次。 所以，算法的時(shí)間復(fù)雜度為所以，算法的時(shí)間復(fù)雜度為 O O（n n）。）。 （二）插入算法設(shè)計(jì)（二）插入算法設(shè)計(jì)1. .功能：在線性表第功能：在線性表第i i處插入其數(shù)值為處插入其數(shù)值為x x新結(jié)點(diǎn)新結(jié)點(diǎn)q q。 2.2.算法思想：算法思想：（1 1） 找到第找到第i-1i-1個(gè)結(jié)點(diǎn)（個(gè)結(jié)點(diǎn)（p p指向第指向第i-1i-1個(gè)結(jié)點(diǎn)）；個(gè)結(jié)點(diǎn)）；（2 2） 在在p p結(jié)點(diǎn)之后插入新結(jié)點(diǎn)結(jié)點(diǎn)之后插入新結(jié)點(diǎn)q q。（二）插入算法設(shè)計(jì)（二）插入算法設(shè)計(jì)1. .功能：在線性表第功能

11、：在線性表第i i處插入其數(shù)值為處插入其數(shù)值為x x新結(jié)點(diǎn)新結(jié)點(diǎn)q q 。 2.2.算法思想：算法思想：（1 1） 找到第找到第i-1i-1個(gè)結(jié)點(diǎn)（個(gè)結(jié)點(diǎn)（p p指向第指向第i-1i-1個(gè)結(jié)點(diǎn)）；個(gè)結(jié)點(diǎn)）；（2 2） 在在p p結(jié)點(diǎn)之后插入新結(jié)點(diǎn)結(jié)點(diǎn)之后插入新結(jié)點(diǎn)q q。3.3.算法設(shè)計(jì)算法設(shè)計(jì)void void ins(node ins(node * *head,int i, node head,int i, node * *q)q) /head:/head:帶頭結(jié)點(diǎn)的單鏈表的頭指針帶頭結(jié)點(diǎn)的單鏈表的頭指針 / / 該算法在第該算法在第i i個(gè)結(jié)點(diǎn)后面插入其數(shù)值為個(gè)結(jié)點(diǎn)后面插入其數(shù)值為x x

12、新結(jié)點(diǎn)新結(jié)點(diǎn) node node * *p=loc(head,i-1);p=loc(head,i-1); / / 令令 p p 指向第指向第i-1i-1個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn) if (p!=NULL)if (p!=NULL) q-next=p-next; p-next=qq-next=p-next; p-next=q; ; / /完成插入完成插入 （三）（三）刪除算法設(shè)計(jì)刪除算法設(shè)計(jì) 1. .功能：刪除鏈表中第功能：刪除鏈表中第i i個(gè)結(jié)點(diǎn)。個(gè)結(jié)點(diǎn)。 2.2.算法思想：算法思想： （1 1） 找到第找到第i-1i-1個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn) ( p( p指向第指向第i-1i-1個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn) ) )；（2 2） 刪除

13、刪除p p的后繼結(jié)點(diǎn)（的后繼結(jié)點(diǎn)（q q）。）。3.3.算法設(shè)計(jì)算法設(shè)計(jì)void del (LinkList head, int i, datatype &e) /head:帶頭結(jié)點(diǎn)的單鏈表的頭指針帶頭結(jié)點(diǎn)的單鏈表的頭指針 node *p=head; j=0; /指針初始化指針初始化,j為計(jì)數(shù)器為計(jì)數(shù)器 while (p-next!=NULL & jnext; j+; / 找第找第i-1個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn) if ( p-next!=NULL & j=i-1 ) q=p-next; /q指向指向p的后繼結(jié)點(diǎn)的后繼結(jié)點(diǎn)(即第即第i個(gè)結(jié)點(diǎn)）個(gè)結(jié)點(diǎn)） p-next=q-next; /

14、刪除第刪除第i個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn) delete q；/ 釋放釋放q結(jié)點(diǎn)結(jié)點(diǎn) 四、鏈表算法設(shè)計(jì)示例四、鏈表算法設(shè)計(jì)示例例2.2.1 已知線性表中的元素按值遞增排列已知線性表中的元素按值遞增排列, 并以單鏈表作存儲(chǔ)并以單鏈表作存儲(chǔ) 結(jié)構(gòu)。寫一高效算法結(jié)構(gòu)。寫一高效算法, 刪除表中所有值大于刪除表中所有值大于min且小于且小于 max的結(jié)點(diǎn)（若表中存在這樣的結(jié)點(diǎn)）。的結(jié)點(diǎn)（若表中存在這樣的結(jié)點(diǎn)）。算法設(shè)計(jì)算法設(shè)計(jì) ：void del_1 (LinkList h, int min, int max) / h:帶頭結(jié)點(diǎn)的單鏈表的頭指針帶頭結(jié)點(diǎn)的單鏈表的頭指針 LinkList q=h，p=h-next; /初

15、值初值 while (p!=NULL & p-datanext; / p指向其值指向其值min的結(jié)點(diǎn)的結(jié)點(diǎn), q是是p的前趨結(jié)點(diǎn)的前趨結(jié)點(diǎn) while (p!=NULL & p-datanext; / 刪除所有的其值刪除所有的其值min并且并且next=p; / del_1例2.2.2 以鏈表作存儲(chǔ)結(jié)構(gòu)以鏈表作存儲(chǔ)結(jié)構(gòu), 實(shí)現(xiàn)線性表就地逆置實(shí)現(xiàn)線性表就地逆置 的算的算 法法, 即將線性表即將線性表: (a1,a2,.an)=(an,.,a2,a1)分析分析：(1)取出原鏈表取出原鏈表(a1,.,an)中的一結(jié)點(diǎn)中的一結(jié)點(diǎn); (2)插入到新鏈表插入到新鏈表(an,.,a1序序)的

16、表頭處的表頭處; (3) 重復(fù)重復(fù)(1)和和(2)步步, 直到原鏈表空止。直到原鏈表空止。void reverse (node *h) /h:帶頭結(jié)點(diǎn)的單鏈表的頭指針帶頭結(jié)點(diǎn)的單鏈表的頭指針 node *s, *p=h-next; /p指向第指向第1個(gè)元素結(jié)點(diǎn)個(gè)元素結(jié)點(diǎn) h-next=NULL; / 將將h用作新鏈表作頭指針用作新鏈表作頭指針 while (p!=NULL) s=p; p=p-next; / 將將s結(jié)點(diǎn)從原鏈中刪除結(jié)點(diǎn)從原鏈中刪除 s-next=h-next; h-next=s; / 將將s插入新鏈?zhǔn)撞坎迦胄骆準(zhǔn)撞?例2.2.3 設(shè)有兩個(gè)按元素值遞增有序排列的線性表設(shè)有兩個(gè)按元

17、素值遞增有序排列的線性表 A A和和B,B,均以單鏈表作存儲(chǔ)結(jié)構(gòu)均以單鏈表作存儲(chǔ)結(jié)構(gòu), , 寫一算法寫一算法 將將A A表和表和B B表歸并成一個(gè)按元素值遞增有序表歸并成一個(gè)按元素值遞增有序 排列線性表排列線性表C C。分析分析：（1 1）當(dāng)）當(dāng)A A表和表和B B表都不空時(shí)表都不空時(shí), , 進(jìn)行比較進(jìn)行比較, , 將較小數(shù)將較小數(shù) 鏈入鏈入C C表表尾表表尾, ,以保證其遞增性以保證其遞增性; ; (2) (2) 若某一鏈表空若某一鏈表空, , 將另一鏈表接在將另一鏈表接在C C表之后表之后 算法設(shè)計(jì)：算法設(shè)計(jì)：void void ( LinkList ha,LinkList hb, Lin

18、kList hc)( LinkList ha,LinkList hb, LinkList hc) / ha,hb,hc / ha,hb,hc分別為分別為A A、B B、C C鏈表的頭指針，均帶頭結(jié)點(diǎn)。鏈表的頭指針，均帶頭結(jié)點(diǎn)。 / / 該算法將有序表該算法將有序表A A和和B B，歸并為一個(gè)新的有序表，歸并為一個(gè)新的有序表C C pa=ha-next; pb=hb-next; pa=ha-next; pb=hb-next; hc=ha; rc=hc; hc=ha; rc=hc;/ hc/ hc、rc:rc:歸并后鏈表的頭指針、尾指針歸并后鏈表的頭指針、尾指針 while (pa!=NULL &

19、amp; pb!=NULL) while (pa!=NULL & pb!=NULL) if (pa-datadata) if (pa-datadata) rc-next=pa; rc=pa; pa=pa-next; rc-next=pa; rc=pa; pa=pa-next; else else rc-next=pb; rc=pb; pb=pb-next; rc-next=pb; rc=pb; pb=pb-next; / (1) / (1) 當(dāng)當(dāng)A A表和表和B B表都不空時(shí)表都不空時(shí), ,將具較小值的結(jié)點(diǎn)鏈入將具較小值的結(jié)點(diǎn)鏈入C C表表尾表表尾 if (pa!=NULL) rc-n

20、ext=pa; else rc-next=pb;if (pa!=NULL) rc-next=pa; else rc-next=pb; / (2) / (2) 若某一鏈表空若某一鏈表空, , 將另一鏈表接在將另一鏈表接在C C表之后表之后 2.2.2 循環(huán)鏈表例例2.2.42.2.4 循環(huán)鏈表（循環(huán)鏈表（n1n1）中即無(wú)頭結(jié)點(diǎn)也無(wú)頭指針，寫一算法）中即無(wú)頭結(jié)點(diǎn)也無(wú)頭指針，寫一算法 刪除刪除p p結(jié)點(diǎn)的前趨結(jié)點(diǎn)。結(jié)點(diǎn)的前趨結(jié)點(diǎn)。viod del-pre(node *p) node *r=p; while ( r-next-next != p ) r=r-next; / r后移后移，到到r-next

21、-next != p 止止 r-next=p; / 刪除刪除r的后繼的后繼 將刪除將刪除p的前驅(qū)結(jié)點(diǎn)的問(wèn)題，看的前驅(qū)結(jié)點(diǎn)的問(wèn)題，看成是刪除成是刪除r的后繼結(jié)點(diǎn)的問(wèn)題。的后繼結(jié)點(diǎn)的問(wèn)題。 例例 2.2.5 2.2.5 約瑟夫環(huán)問(wèn)題約瑟夫環(huán)問(wèn)題 設(shè)有設(shè)有n個(gè)人站成一圈，每個(gè)人有不同的編號(hào)個(gè)人站成一圈，每個(gè)人有不同的編號(hào)i（1in），從編號(hào)為），從編號(hào)為1的的人開(kāi)始按順時(shí)針?lè)较蛉碎_(kāi)始按順時(shí)針?lè)较颉?,2,3,m”循環(huán)報(bào)數(shù)，數(shù)到循環(huán)報(bào)數(shù)，數(shù)到m的人出列。然后從出列者的人出列。然后從出列者的下一個(gè)人重新開(kāi)始報(bào)數(shù)，數(shù)到的下一個(gè)人重新開(kāi)始報(bào)數(shù)，數(shù)到m的人又出列的人又出列., 如此重復(fù)進(jìn)行，直到如此重復(fù)進(jìn)行，

22、直到n個(gè)人個(gè)人都出列為止。都出列為止。 當(dāng)當(dāng)m=4, n=8時(shí)時(shí) , 出列順序?yàn)槌隽许樞驗(yàn)?:48521376算法設(shè)計(jì)：算法設(shè)計(jì)：void josephus_2 (LinkList r, int m, int n) /r：（不帶頭結(jié)點(diǎn)的）單向循環(huán)鏈表的尾指針 LinkList p=r; /p：指向尾指針 for (i=1;i=n; +i) for (j=1;jnext; / p后移m-1次，定位于m-1處（要退席的人之前） q=p-next; /q定位于m人（要退席的人） printf(“%d”,q-data); /第m人報(bào)數(shù) p-next=q-next; /第m人退席，刪除第m人 2.3.4

23、 雙向鏈表 在雙向鏈表中，每個(gè)結(jié)點(diǎn)都有兩個(gè)指針域，用在雙向鏈表中，每個(gè)結(jié)點(diǎn)都有兩個(gè)指針域，用于存放前驅(qū)結(jié)點(diǎn)地址和后繼結(jié)點(diǎn)地址。于存放前驅(qū)結(jié)點(diǎn)地址和后繼結(jié)點(diǎn)地址。 與單鏈表相比，雙向鏈表可以進(jìn)行兩個(gè)方向的與單鏈表相比，雙向鏈表可以進(jìn)行兩個(gè)方向的查找。查找。 一、結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)一、結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)二、雙向鏈表的表示雙向鏈表的表示 struct dnode datatype data; / 數(shù)值域數(shù)值域 struct dnode *prior, * next; / 指針域指針域 ；typedef struct dnode dnode; 三、雙向鏈表的特點(diǎn)雙向鏈表的特點(diǎn) p-next-prior = p

24、 = p-prior-next四、插入四、插入 在在p結(jié)點(diǎn)（第結(jié)點(diǎn)（第i個(gè)結(jié)點(diǎn)）之前插入新結(jié)點(diǎn)：個(gè)結(jié)點(diǎn)）之前插入新結(jié)點(diǎn)： s-prior=p-prior; p-prior-next=s; s-next=p; p-prior=s; 六、刪除六、刪除 刪除第刪除第i個(gè)結(jié)點(diǎn)（結(jié)點(diǎn)個(gè)結(jié)點(diǎn)（結(jié)點(diǎn)p ）：）： p-prior-next=p-next; p-next-prior=p-prior; 例例2.2.6 已知單向循環(huán)鏈表表示的線性表中含有三個(gè)域已知單向循環(huán)鏈表表示的線性表中含有三個(gè)域: pre、data和和next, 其中其中 data為數(shù)據(jù)域?yàn)閿?shù)據(jù)域,next為指為指 針域針域,其值為后繼其值為后

25、繼, pre也是指針域也是指針域, 其值為其值為NULL。 寫一算法寫一算法, 將此鏈改為雙向鏈表。將此鏈改為雙向鏈表。設(shè)計(jì)思想：設(shè)計(jì)思想： 檢查鏈表中的每一結(jié)點(diǎn)檢查鏈表中的每一結(jié)點(diǎn), 若其若其pre為空為空, 則將它指則將它指 向其前趨結(jié)點(diǎn)。向其前趨結(jié)點(diǎn)。 void cre_dulink( dnode *dh) / dh:雙向鏈表的頭指針雙向鏈表的頭指針 dnode *p=dh; while (p-next-pre=NULL) p-next-pre=p; p=p-next; 例例2.2.7 寫出雙向鏈表倒置的算法。寫出雙向鏈表倒置的算法。 分析：分析：p從從next方向，方向，q從從prio

26、r方向逐一對(duì)兩個(gè)結(jié)點(diǎn)方向逐一對(duì)兩個(gè)結(jié)點(diǎn)的數(shù)據(jù)進(jìn)行交換，直至的數(shù)據(jù)進(jìn)行交換，直至p=q或或p-prior=q止。止。 void ds0216(dnode * dh) /dh:指向雙向循環(huán)鏈表的頭結(jié)點(diǎn)指向雙向循環(huán)鏈表的頭結(jié)點(diǎn) dnode *q=dh-prior, *p=dh-next; / q沿前趨指針?lè)较蜓厍摆呏羔樂(lè)较?p沿后繼指針?lè)较蜓睾罄^指針?lè)较?while (p!=q & p-prior!=q) q-datap-datat; p=p-next; q=q-prior ; 2.3 鏈表的應(yīng)用鏈表的應(yīng)用多項(xiàng)式相加多項(xiàng)式相加1一元多項(xiàng)式的表示一元多項(xiàng)式的表示 Pn(x)=P1Xe1+P2Xe2+.+PmXem二二. 存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu) - 鏈表鏈表 struct poly int index; / 指數(shù)指數(shù) int coef; /系數(shù)系數(shù) struct poly *next; ; typedef struct poly polynode ;三三. 多項(xiàng)式相加多項(xiàng)式相加 A(x) = 1 - 10 x6 + 2x8 +7x14 B(x)= - x4 + 10 x6 - 3x10 + 8x14 +