算數(shù)提高課件ds 2 2線性表

1第二章線性表

算法與數(shù)據(jù)結(jié)構(gòu)張路

2

內(nèi)容提要線性表的概念（邏輯結(jié)構(gòu)）線性表的順序表示和實(shí)現(xiàn)（順序表）線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)（鏈表）線性表的應(yīng)用3

順序表示的優(yōu)缺點(diǎn)優(yōu)點(diǎn):不需要附加空間；隨機(jī)存取任一元素.缺點(diǎn)一開(kāi)始就要分配足夠大的一片連續(xù)的內(nèi)存空間，很難估計(jì)所需空間的大小。更新操作代價(jià)大,插入與刪除運(yùn)算要移動(dòng)大量的元素，效率較低。改進(jìn)：使用鏈接存儲(chǔ)結(jié)構(gòu)（不要求邏輯相鄰物理也相鄰，通過(guò)指針表達(dá)邏輯關(guān)系），克服順序存儲(chǔ)的不足，但失去了隨機(jī)存取的優(yōu)點(diǎn)。4

線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)基本思想:用附加的指針來(lái)表示結(jié)點(diǎn)之間的線性關(guān)系單鏈表循環(huán)鏈表雙向鏈表5

線性表的鏈?zhǔn)奖硎緮?shù)據(jù)域指針域存儲(chǔ)地址數(shù)據(jù)域指針域

1 Li 437 Qian 1313 Sun 1 19 Wang NULL25 Wu 3731 Zhao 737 Zheng1943 Zhou 2531頭指針H6

線性鏈表的邏輯狀態(tài)（不帶頭結(jié)點(diǎn)）LiZhaoQianSunZhouWuZhengWang^Ha1an^a2...H頭結(jié)點(diǎn)

帶頭結(jié)點(diǎn)的線性鏈表

線性鏈表的圖示

（數(shù)據(jù)元素的邏輯順序，不是存儲(chǔ)位置）數(shù)據(jù)域可以存儲(chǔ)任何附加信息指針域存儲(chǔ)指向第一個(gè)節(jié)點(diǎn)7

鏈表的定義運(yùn)算的實(shí)現(xiàn)數(shù)據(jù)域可以有多個(gè)信息。數(shù)據(jù)說(shuō)明structNode; /*單鏈表結(jié)點(diǎn)類型*/typedefstructNode*PNode; /*結(jié)點(diǎn)指針類型*/structNode /*單鏈表結(jié)點(diǎn)結(jié)構(gòu)*/{DataTypeinfo; PNodelink;};typedefstructNode*PLinkList;

/*單鏈表指針類型*/

PLinkListpllist;

/*指向單鏈表*/8

對(duì)于線性表(A,B,C,D,E,F),假定p指向結(jié)點(diǎn)C，則:p->link指向C的后繼Dp->link->link指向?無(wú)頭結(jié)點(diǎn)整個(gè)單鏈表：pllist第一個(gè)結(jié)點(diǎn)：pllist空表判斷：pllist==NULL帶頭結(jié)點(diǎn)整個(gè)單鏈表：pllist頭結(jié)點(diǎn)：pllist第一個(gè)結(jié)點(diǎn)：pllist->link，plist≠NULL空表判斷：plist->link==NULL，plist≠NULLCPDECE^D

plistCE^D

plist9

單鏈表基本運(yùn)算及其實(shí)現(xiàn)

創(chuàng)建空的單鏈表

Plinklist

createNull_link(void)插入結(jié)點(diǎn)

insert_link(PLinkListplist,inti,DataTypex)

刪除結(jié)點(diǎn)

delete_link(PLinkListplist,DataTypex)定位運(yùn)算

locate_link(PlinkListplist,DataTypex)求存儲(chǔ)地址運(yùn)算

find_link(PLinkListplist,inti)判空運(yùn)算

isNull_link(PLinkListplist)10

單鏈表基本運(yùn)算的實(shí)現(xiàn)-1函數(shù)名：createNulllist_link

功能:建立帶有頭節(jié)點(diǎn)的空鏈表程序：PLinkListcreateNulllist_link(void){ PLinkListpllist;pllist=(PLinkList)malloc(sizeof(structNode));if(pllist!=NULL)pllist->link=NULL;return(pllist);}

pllist

11

單鏈表基本運(yùn)算的實(shí)現(xiàn)-2函數(shù)名：insert_link功能:在pllist帶頭結(jié)點(diǎn)的單鏈表中下標(biāo)為i(第i+1個(gè))的結(jié)點(diǎn)前插入一個(gè)值為ｘ的元素，并返回插入成功與否的標(biāo)志。程序：intinsert_link(PLinkListpllist,inti,DataTypex)abxqpq->link=p->link;p->link=q;注：順序不能反abp單鏈表12

intinsert_link(PLinkListpllist,inti,DataTypex){PNodep,q;p=pllist;intj=0;while(p!=NULL&&j<i)/*查找i的前驅(qū)*/{p=p->link;j++;}if(j!=i)/*查找失敗*/{printf(“i=%disnotreasonable.\n”,i);return0;}q=(PNode)malloc(sizeof(structNode));/*申請(qǐng)新節(jié)點(diǎn)*/if(q==NULL)/*申請(qǐng)失敗*/{printf("Outofspace!!!\n");return0;}else/*插入鏈表中*/{ q->info=x;q->link=p->link;p->link=q; return1;}}13

pabcp->link=p->link->link;單鏈表基本運(yùn)算的實(shí)現(xiàn)-3函數(shù)名：delete_link功能:在pllist帶頭結(jié)點(diǎn)的單鏈表中刪除第一個(gè)元素值為ｘ的元素，并返回刪除成功與否的標(biāo)志。程序：intdelete_link(PLinkListpllist,DataTypex)abp單鏈表14

intdelete_link(PLinkListpllist,DataTypex)/*在pllist帶頭結(jié)點(diǎn)的單鏈表中刪除第一個(gè)元素值為ｘ的元素*/{PNodep,q;p=pllist; /*在pllist帶頭結(jié)點(diǎn)的單鏈表中找元素為x的結(jié)點(diǎn)的前驅(qū)*/while(p->link!=NULL&&p->link->info!=x) p=p->link;if(p->link==NULL)/*沒(méi)找到元素為x的結(jié)點(diǎn)*/ {printf(”Notexist!\n”);return(0);}else/*刪除該結(jié)點(diǎn)*/{q=p->link;p->link=q->link;free(q);return(1);}}15

pabx單鏈表基本運(yùn)算的實(shí)現(xiàn)-4函數(shù)名：locate_link功能:在pllist帶頭結(jié)點(diǎn)的單鏈表中定位第一個(gè)元素值為ｘ的元素，并返回該元素的標(biāo)志。程序：PNodelocate_link(PLinkListplist,DataTypex)ec……16

PNode*locate_link(PlinkListplist,DataTypex)/*在pllist帶頭結(jié)點(diǎn)的單鏈表中定位第一個(gè)元素值為ｘ的元素*/{PNodep,q;p=pllist; /*在pllist帶頭結(jié)點(diǎn)的單鏈表中找元素為x的結(jié)點(diǎn)的前驅(qū)*/while(p->link!=NULL&&p->link->info!=x) p=p->link;

/*返回元素為x的結(jié)點(diǎn)的位置*/return(p->link);}17

單鏈表運(yùn)算的時(shí)間復(fù)雜度由于“插入/刪除運(yùn)算”首先需要定位，而定位必須從頭結(jié)點(diǎn)開(kāi)始順鏈一個(gè)一個(gè)結(jié)點(diǎn)進(jìn)行比較，因此其“基本的操作”為比較運(yùn)算。比較運(yùn)算的執(zhí)行次數(shù)與結(jié)點(diǎn)的位置有關(guān)最好情況時(shí)為1次（第一個(gè)結(jié)點(diǎn)），最壞為n次（所有結(jié)點(diǎn)皆比較一次）時(shí)間復(fù)雜度為O(n)平均情況下需要查找n/2個(gè)元素時(shí)間復(fù)雜度為O(n)插入與刪除元素時(shí)所花費(fèi)時(shí)間只是申請(qǐng)結(jié)點(diǎn)和修改指針的時(shí)間，時(shí)間復(fù)雜度為O(1)18

單鏈表與順序表的比較存儲(chǔ)順序表為靜態(tài)結(jié)構(gòu)，而鏈表為動(dòng)態(tài)結(jié)構(gòu)。單鏈表的存儲(chǔ)密度比順序表低；在許多情況下鏈?zhǔn)降姆峙浔软樞蚍峙溆行В恍薷脑趩捂湵砝镞M(jìn)行插入、刪除運(yùn)算比在順序表里容易得多；順序表通過(guò)數(shù)據(jù)元素移動(dòng)完成，而鏈表通過(guò)修改指針完成。定位對(duì)于順序表，可通過(guò)簡(jiǎn)單的定位公式隨機(jī)訪問(wèn)任一個(gè)元素;而在單鏈表中，需要順著鏈逐個(gè)進(jìn)行查找。因此，順序表為隨機(jī)存取結(jié)構(gòu)，而鏈表不是。19

（1）有利于基本運(yùn)算的實(shí)現(xiàn)頻繁訪問(wèn)：順序表（隨機(jī)存取）；頻繁插入、刪除：鏈表（2）有利于數(shù)據(jù)的特性順序表：難于事先估計(jì)數(shù)據(jù)元素個(gè)數(shù)，過(guò)大浪費(fèi)空間，過(guò)小易產(chǎn)生溢出；鏈表：動(dòng)態(tài)申請(qǐng)，但存儲(chǔ)密度比順序表低；（3）有利于軟件環(huán)境（程序設(shè)計(jì)語(yǔ)言）程序設(shè)計(jì)語(yǔ)言是否支持動(dòng)態(tài)分配？Fortran、Basic等不支持動(dòng)態(tài)分配，此時(shí)只能選擇順序表。

單鏈表與順序表的選擇20

單鏈表存在的問(wèn)題單鏈表的表長(zhǎng)是一個(gè)隱含的值（后繼為空）在單鏈表最后插入一個(gè)元素時(shí)，需要遍歷整個(gè)鏈表在鏈表中，元素的位序概念淡化，結(jié)點(diǎn)的概念強(qiáng)化改進(jìn)鏈表的設(shè)置21

線性表的鏈?zhǔn)奖硎緮U(kuò)充單鏈表循環(huán)鏈表雙向鏈表22

無(wú)頭結(jié)點(diǎn)：循環(huán)條件：p->link==pclist表空條件：pclist==NULL帶頭結(jié)點(diǎn)：循環(huán)條件：p->link==pclist表空條件：pclist->link==NULLpclist…infoa1an頭結(jié)點(diǎn)建立：將最后一個(gè)結(jié)點(diǎn)的指針項(xiàng)指向第一個(gè)結(jié)點(diǎn)（或頭結(jié)點(diǎn)），構(gòu)成一個(gè)循環(huán)鏈。循環(huán)鏈表的優(yōu)點(diǎn)：

從任何一個(gè)結(jié)點(diǎn)出發(fā)，可以訪問(wèn)表中任何一個(gè)結(jié)點(diǎn)元素。循環(huán)鏈表23

上面循環(huán)鏈表的缺點(diǎn)：

如果要訪問(wèn)最后一個(gè)結(jié)點(diǎn)，仍要訪問(wèn)表中所有的結(jié)點(diǎn)。改進(jìn)：

修改pclist指向最后一個(gè)結(jié)點(diǎn)，方便某些操作(如兩個(gè)鏈表合并等）。pclist…a1a2an最后結(jié)點(diǎn)：pclist第一個(gè)結(jié)點(diǎn)：pclist->link循環(huán)條件：p==pclist空表判斷：pclist==NULL思考問(wèn)題1：如何將一個(gè)單循環(huán)鏈表（無(wú)頭結(jié)點(diǎn)，且pclist指向第一個(gè)結(jié)點(diǎn)）倒置？

(a1,a2,…,an)=>(an,an-1,…,a1)24

palist…a0an-1pblist…b0bn-1…a0an-1pmlist…b0bn-1思考問(wèn)題2：將僅設(shè)尾指針的兩個(gè)循環(huán)鏈表合并25

線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)單鏈表循環(huán)鏈表雙向鏈表26

鏈表的另一種定義structNode; /*單鏈表結(jié)點(diǎn)類型*/typedefstructNode*PNode; /*結(jié)點(diǎn)指針類型*/structNode /*單鏈表結(jié)點(diǎn)結(jié)構(gòu)*/{ DataTypeinfo; PNodelink;};structLinkList /*單鏈表類型定義*/{ PNodehead; /*指向單鏈表中的第一個(gè)結(jié)點(diǎn)*/};typedefstructLinkList*PLinkList; /*單鏈表類型的指針類型*/PLinkListplist;27

無(wú)頭結(jié)點(diǎn)整個(gè)單鏈表：plist第一個(gè)結(jié)點(diǎn)：plist->headplist≠NULL空表判斷：plist->head=NULL，plist≠NULL帶頭結(jié)點(diǎn)整個(gè)單鏈表：plist頭結(jié)點(diǎn)：plist->headplist≠NULL第一個(gè)結(jié)點(diǎn)：plist->head->linkplist->head≠NULL空表判斷：plist->head->link=NULL，plist->head≠NULLCE^D

plist

headCE^D

plist

head28

單鏈表缺點(diǎn)：找后繼容易，找前驅(qū)必須從頭開(kāi)始查找。雙向鏈表：既可以找前驅(qū)，也可以找后繼。不帶頭結(jié)點(diǎn) 空表判斷：pdlist->head=NULL

最后結(jié)點(diǎn)判斷：p->rlink=NULL

第一個(gè)結(jié)點(diǎn)：pdlist->head

最后結(jié)點(diǎn)：pdlist->rear結(jié)點(diǎn)結(jié)構(gòu)：infollinkrlinkpdlist^k1k2kn……^headrearP->rlink->llink=p->llink->rlink=p

雙向鏈表29

雙向鏈表特點(diǎn)：既可以找前驅(qū)，也可以找后繼。數(shù)據(jù)說(shuō)明：structDoubleNode /*雙鏈表結(jié)點(diǎn)結(jié)構(gòu)*/{DataTypeinfo;structDoubleNode*llink,*rlink;};typedefstructDoubleNode*PDoubleNode;/*結(jié)點(diǎn)指針類型*/llinkrlinkinfo雙向鏈表定義30

structDoubleList /*雙鏈表類型*/{PDoubleNodehead;/*指向第一個(gè)結(jié)點(diǎn)*/PDoubleNoderear;/*指向最后一個(gè)結(jié)點(diǎn)*/};typedefstructDoubleList*PDoubleList; PDoubleListpdList;/*pdlist指向雙鏈表*/pdListpdList->rear….….pdList->head31

刪除雙向鏈表的結(jié)點(diǎn)ABCp(p->llink)->rlink=p->rlinkp->rlink->llink=p->llink雙向鏈表結(jié)點(diǎn)刪除圖示free(p)32

往雙向鏈表中p前插入結(jié)點(diǎn)(1)q->llink=p->llink;(2)p->llink->rlink=q;(3)q->rlink=p;(4)p->llink=q;ABCqp雙向鏈表結(jié)點(diǎn)插入的圖示p指向結(jié)點(diǎn)后插入新結(jié)點(diǎn)s:q->llink=p;(3)p->rlink->llink=q;q->rlink=p->rlink;(4)p->rlink=q;(1)(2)(4)(3)ABCpq(1)(4)(3)(2)q=(PDoubleNode)malloc(sizeof(structDoubleNode)33

雙向循環(huán)鏈表PDoubleListpdList;/*pdlist指向雙鏈表*/空表判斷：pdlist->rlink==NULL最后結(jié)點(diǎn)判斷：p->rlink==pdlist或

p==pdlist->llink第一個(gè)結(jié)點(diǎn)：pdlist->rlink最后結(jié)點(diǎn)：pdlist->llinkpdlistk0k1kn-1……34

內(nèi)容提要線性表的概念（邏輯結(jié)構(gòu)）線性表的順序表示和實(shí)現(xiàn)（順序表）線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)（鏈表）線性表的應(yīng)用35

線性表的應(yīng)用——鏈表部分問(wèn)題Josephus問(wèn)題一元多項(xiàng)式表示和運(yùn)算36

循環(huán)鏈表方式實(shí)現(xiàn)步驟：建立循環(huán)鏈表；出列算法；找循環(huán)單鏈表中的第s個(gè)結(jié)點(diǎn)放在指針變量p中，從p所指結(jié)點(diǎn)開(kāi)始計(jì)數(shù)尋找第m個(gè)結(jié)點(diǎn)，輸出該結(jié)點(diǎn)的元素值；刪除該結(jié)點(diǎn)，并將該結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)放在指針變量p中，轉(zhuǎn)去執(zhí)行②，直到所有結(jié)點(diǎn)被刪除為止；主程序時(shí)間復(fù)雜度分析：創(chuàng)建鏈表，求第s個(gè)結(jié)點(diǎn)，求n個(gè)第m個(gè)應(yīng)出列的元素O(n)+O(s)+O(m*n))37

線性表的應(yīng)用——鏈表部分問(wèn)題Josephus問(wèn)題一元多項(xiàng)式表示和運(yùn)算38

一元多項(xiàng)式：Pn(x)=p0+p1x+p2x2+…+pnxn線性表表示：P=(p0,p1,p2,…,pn)順序表表示：只存系數(shù)（第i個(gè)元素存xi的系數(shù)）