工學(xué)數(shù)據(jù)結(jié)構(gòu)第04次課線性表B課件

每課一貼：原來(lái)很簡(jiǎn)單有個(gè)小弟在腳踏車店當(dāng)學(xué)徒，有人送來(lái)一部故障的腳踏車，小弟除了將車修好，還把車子整理的漂亮如新，其它學(xué)徒笑他多此一舉，后來(lái)雇主將腳踏車領(lǐng)回去的第二天，小弟被挖角到那位雇主的公司上班。原來(lái)出人頭地很簡(jiǎn)單，吃點(diǎn)虧就可以了。有一個(gè)網(wǎng)球教練對(duì)學(xué)生說(shuō)：「如果一個(gè)網(wǎng)球掉進(jìn)草堆里，應(yīng)該如何找？」有人答：「從草堆中心線開(kāi)始找。」有人答：「從草堆的最凹處開(kāi)始找?！褂腥舜穑骸笍牟葑铋L(zhǎng)的地方開(kāi)始找。」教練宣布正確答案：「按部就班的從草地的一頭，搜尋到草地的另一頭。原來(lái)尋找成功的方法很簡(jiǎn)單，從一數(shù)到十不要跳過(guò)就可以了。

1每課一貼：原來(lái)很簡(jiǎn)單1上堂課要點(diǎn)回顧線性結(jié)構(gòu)(包括表、棧、隊(duì)、數(shù)組）的定義和特點(diǎn)：僅一個(gè)首、尾結(jié)點(diǎn)，其余元素僅一個(gè)直接前驅(qū)和一個(gè)直接后繼。2.線性表邏輯結(jié)構(gòu)：“一對(duì)一”或1:1存儲(chǔ)結(jié)構(gòu)：順序、鏈?zhǔn)竭\(yùn)算：修改、插入、刪除3.順序存儲(chǔ)特征：邏輯上相鄰，物理上也相鄰；優(yōu)點(diǎn)：隨機(jī)查找快O(1)缺點(diǎn)：插入、刪除慢O(n)2上堂課要點(diǎn)回顧線性結(jié)構(gòu)(包括表、棧、隊(duì)、數(shù)組）的定義和特點(diǎn)：2.3線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)2.3.1鏈表的表示2.3.2鏈表的實(shí)現(xiàn)2.3.3鏈表的運(yùn)算效率分析鏈表小結(jié)32.3線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)2.3.1鏈表的表示鏈表2.3.1鏈表的表示1536元素21400元素11346元素3∧元素41345h存儲(chǔ)地址存儲(chǔ)內(nèi)容指針1345元素114001346元素4∧…….……..…….1400元素21536…….……..…….1536元素31346h42.3.1鏈表的表示1536元素21400元素1134鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)特點(diǎn)：其結(jié)點(diǎn)在存儲(chǔ)器中的位置是隨意的，即邏輯上相鄰的數(shù)據(jù)元素在物理上不一定相鄰。如何實(shí)現(xiàn)？通過(guò)指針來(lái)實(shí)現(xiàn)注意：每個(gè)存儲(chǔ)結(jié)點(diǎn)都包含兩部分：

數(shù)據(jù)域和指針域2.3.1鏈表的表示5鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)特點(diǎn)：其結(jié)點(diǎn)在存儲(chǔ)器中的位置是隨意的，即邏輯上相例1畫(huà)出26個(gè)英文字母表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。該字母表在內(nèi)存的鏈?zhǔn)酱娣攀疽鈭D如下：

解：該字母表的邏輯結(jié)構(gòu)為：（a,b,…,y,z）aheadb/\z……各結(jié)點(diǎn)由兩個(gè)域組成：數(shù)據(jù)域：存儲(chǔ)元素?cái)?shù)值數(shù)據(jù)；指針域：存儲(chǔ)直接后繼或者直接前驅(qū)的存儲(chǔ)位置。指針數(shù)據(jù)指針數(shù)據(jù)指針或樣式：6例1畫(huà)出26個(gè)英文字母表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。該字母表在與鏈?zhǔn)酱鎯?chǔ)有關(guān)的術(shù)語(yǔ)：1、結(jié)點(diǎn)：數(shù)據(jù)元素的存儲(chǔ)映像。由數(shù)據(jù)域和指針域兩部分組成；2、鏈表：

n個(gè)結(jié)點(diǎn)由指針鏈組成一個(gè)鏈表。它是線性表的鏈?zhǔn)酱鎯?chǔ)映像，稱為線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。3、單鏈表、雙鏈表、多鏈表、循環(huán)鏈表：結(jié)點(diǎn)只有一個(gè)指針域的鏈表，稱為單鏈表或線性鏈表；有兩個(gè)指針域的鏈表，稱為雙鏈表；有多個(gè)指針域的鏈表，稱為多鏈表；首尾相接的鏈表稱為循環(huán)鏈表。a1heada2an……h(huán)ead循環(huán)鏈表示意圖：7與鏈?zhǔn)酱鎯?chǔ)有關(guān)的術(shù)語(yǔ)：1、結(jié)點(diǎn)：數(shù)據(jù)元素的存儲(chǔ)映像。由數(shù)據(jù)域4、頭指針、頭結(jié)點(diǎn)和首元結(jié)點(diǎn)

示意圖如下：頭指針頭結(jié)點(diǎn)首元結(jié)點(diǎn)a1heada2…infoan^頭指針是指向鏈表中第一個(gè)結(jié)點(diǎn)（或?yàn)轭^結(jié)點(diǎn)或?yàn)槭自Y(jié)點(diǎn)）的指針；頭結(jié)點(diǎn)是在鏈表的首元結(jié)點(diǎn)之前附設(shè)的一個(gè)結(jié)點(diǎn)；數(shù)據(jù)域內(nèi)只放空表標(biāo)志和表長(zhǎng)等信息;首元結(jié)點(diǎn)是指鏈表中存儲(chǔ)線性表第一個(gè)數(shù)據(jù)元素a1的結(jié)點(diǎn)。84、頭指針、頭結(jié)點(diǎn)和首元結(jié)點(diǎn)示意圖如下：頭指針頭結(jié)點(diǎn)首元結(jié)一個(gè)線性表的邏輯結(jié)構(gòu)為：（ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG），其存儲(chǔ)結(jié)構(gòu)用單鏈表表示如下，請(qǐng)問(wèn)其頭指針的值是多少？存儲(chǔ)地址數(shù)據(jù)域指針域1LI437QIAN1313SUN119WANGNULL25WU3731ZHAO737ZHENG1943ZHOU25例：答：頭指針是指向鏈表中第一個(gè)結(jié)點(diǎn)的指針，因此關(guān)鍵是要尋找第一個(gè)結(jié)點(diǎn)的地址。7ZHAOH31∴頭指針的值是319一個(gè)線性表的邏輯結(jié)構(gòu)為：（ZHAO,QIAN,SUN,LI,上例鏈表的邏輯結(jié)構(gòu)示意圖有以下兩種形式：①ZHAOQIANLISUNZHOUWUZHENG/\WANGH②ZHAOQIANLISUNZHOUWUZHENG/\WANGH區(qū)別：①

無(wú)頭結(jié)點(diǎn)②

有頭結(jié)點(diǎn)10上例鏈表的邏輯結(jié)構(gòu)示意圖有以下兩種形式：①ZHAOQIANL討論1.在鏈表中設(shè)置頭結(jié)點(diǎn)有什么好處？頭結(jié)點(diǎn)即在鏈表的首元結(jié)點(diǎn)之前附設(shè)的一個(gè)結(jié)點(diǎn)，該結(jié)點(diǎn)的數(shù)據(jù)域中不存儲(chǔ)線性表的數(shù)據(jù)元素，其作用是為了對(duì)鏈表進(jìn)行操作時(shí)，可以對(duì)空表、非空表的情況以及對(duì)首元結(jié)點(diǎn)進(jìn)行統(tǒng)一處理，編程更方便。答：討論2.頭結(jié)點(diǎn)的數(shù)據(jù)域內(nèi)裝的是什么？頭結(jié)點(diǎn)的數(shù)據(jù)域可以為空，也可存放線性表長(zhǎng)度等附加信息，但此結(jié)點(diǎn)不能計(jì)入鏈表長(zhǎng)度值。答：頭結(jié)點(diǎn)的數(shù)據(jù)域H11討論1.在鏈表中設(shè)置頭結(jié)點(diǎn)有什么好處？頭結(jié)點(diǎn)即在鏈表的首元討論4.鏈表的數(shù)據(jù)元素有兩個(gè)域，不再是簡(jiǎn)單數(shù)據(jù)類型，編程時(shí)該如何表示？因每個(gè)結(jié)點(diǎn)至少有兩個(gè)分量，所以要采用結(jié)構(gòu)數(shù)據(jù)類型。答：什么是結(jié)構(gòu)類型？如何書(shū)寫(xiě)表達(dá)？

答：討論3.如何表示空表？無(wú)頭結(jié)點(diǎn)時(shí)，當(dāng)頭指針的值為空時(shí)表示空表；有頭結(jié)點(diǎn)時(shí)，當(dāng)頭結(jié)點(diǎn)的指針域?yàn)榭諘r(shí)表示空表。^頭指針^頭指針頭結(jié)點(diǎn)無(wú)頭結(jié)點(diǎn)有頭結(jié)點(diǎn)12討論4.鏈表的數(shù)據(jù)元素有兩個(gè)域，不再是簡(jiǎn)單數(shù)據(jù)類型，編程時(shí)實(shí)現(xiàn)typedefstructnode{

Elemtype

data;structnode*link;}LNode，*LinkList;linklist*h,*p;datalinkp結(jié)點(diǎn)（*p）(*p)表示p所指向的結(jié)點(diǎn)(*p).datap->data表示p指向結(jié)點(diǎn)的數(shù)據(jù)域(*p).linkp->link表示p指向結(jié)點(diǎn)的指針域生成一個(gè)LNode型新結(jié)點(diǎn)：p=(linklist)malloc(sizeof(LNode));系統(tǒng)回收p結(jié)點(diǎn)：free(p)3.線性鏈表的實(shí)現(xiàn)定義：結(jié)點(diǎn)中只含一個(gè)指針域的鏈表叫~，也叫單鏈表13實(shí)現(xiàn)typedefstructnode{linkli用一組任意的存儲(chǔ)單元存儲(chǔ)線性表的數(shù)據(jù)元素利用指針實(shí)現(xiàn)了用不相鄰的存儲(chǔ)單元存放邏輯上相鄰的元素每個(gè)數(shù)據(jù)元素ai，除存儲(chǔ)本身信息外，還需存儲(chǔ)其直接后繼的地址結(jié)點(diǎn) 數(shù)據(jù)域：元素本身信息指針域：指示直接后繼的存儲(chǔ)位置數(shù)據(jù)域指針域結(jié)點(diǎn)簡(jiǎn)單總結(jié)：線性表的鏈?zhǔn)奖硎镜幕咎卣鳎?4數(shù)據(jù)域指針域結(jié)點(diǎn)簡(jiǎn)單總結(jié)：線性表的鏈?zhǔn)奖硎镜幕咎卣鳎?4.單鏈表的基本運(yùn)算While循環(huán)中語(yǔ)句頻度為若找到結(jié)點(diǎn)X，為結(jié)點(diǎn)X在表中的序號(hào)否則，為n算法評(píng)價(jià)查找：查找單鏈表中是否存在結(jié)點(diǎn)X，若有則返回指向X結(jié)點(diǎn)的指針；否則返回NULL查找、插入、刪除、創(chuàng)建、原地逆序算法描述類似算法：求長(zhǎng)度等，舉一反三P36查找154.單鏈表的基本運(yùn)算While循環(huán)中語(yǔ)句頻度為若找到結(jié)點(diǎn)Xpabxs插入:在線性表兩個(gè)數(shù)據(jù)元素a和b間插入x，已知p指向as->link=p->link;p->link=s;算法描述算法評(píng)價(jià)注意前插和后插的區(qū)別16pabxs插入:在線性表兩個(gè)數(shù)據(jù)元素a和b間插入x，已知p算法描述pabc算法評(píng)價(jià)刪除：?jiǎn)捂湵碇袆h除b，設(shè)p指向ap->link=p->link->link;17算法描述pabc算法評(píng)價(jià)刪除：?jiǎn)捂湵碇袆h除b，設(shè)p指向ap-

動(dòng)態(tài)建立單鏈表算法：設(shè)線性表n個(gè)元素已存放在數(shù)組a中，建立一個(gè)單鏈表，h為頭指針?biāo)惴枋鏊惴ㄔu(píng)價(jià)h頭結(jié)點(diǎn)an^0h頭結(jié)點(diǎn)an-10an^a2…...h頭結(jié)點(diǎn)an-10an^ha1a2頭結(jié)點(diǎn)an^…...0h頭結(jié)點(diǎn)0^注意前插和后插的區(qū)別P35/3618動(dòng)態(tài)建立單鏈表算法：設(shè)線性表n個(gè)元素已存放在數(shù)組a中，建立單鏈表原地逆序算法：設(shè)線性表n個(gè)元素已存放在鏈表a中，要求在不改變其元素位置的條件下將鏈表逆序排列，h為頭指針?biāo)惴枋鏊惴ㄔu(píng)價(jià)ha1a2頭結(jié)點(diǎn)an^…...0hanan-1頭結(jié)點(diǎn)a1^…...019單鏈表原地逆序算法：設(shè)線性表n個(gè)元素已存放在鏈表a中，要求在5.應(yīng)用舉例：兩個(gè)鏈表的歸并（教材P41）算法要求：已知：線性表A、B，分別由單鏈表LA,LB存儲(chǔ)，其中數(shù)據(jù)元素按值非遞減有序排列，要求：將A，B歸并為一個(gè)新的線性表C,C的數(shù)據(jù)元素仍按值非遞減排列。設(shè)線性表C由單鏈表

LC存儲(chǔ)。假設(shè)：A=（3，5，8，11），B=（2，6，8，9，11）預(yù)測(cè)：合并后C=（2,3,5,6,8,8,9,11，11）205.應(yīng)用舉例：兩個(gè)鏈表的歸并（教材P41）算法要求：20用鏈表可表示為：3511/\8

La2611/\8

Lb92365

Lc8頭結(jié)點(diǎn)21用鏈表可表示為：3511/\8La2611/La3

5

8

11^

Lb2

6

8

11^9

PaPbPaPbPa、Pb用于搜索La和Lb，

Pc指向新鏈表當(dāng)前結(jié)點(diǎn)Lc

…

Pa3

PcPa5

Pc11^Pc2

PbPcPa22La35811^Lb26811^9PaPb算法分析：算法主要包括：搜索、比較、插入三個(gè)操作：搜索：需要兩個(gè)指針?biāo)阉鲀蓚€(gè)鏈表；比較：比較結(jié)點(diǎn)數(shù)據(jù)域中數(shù)據(jù)的大?。徊迦耄簩蓚€(gè)結(jié)點(diǎn)中數(shù)據(jù)小的結(jié)點(diǎn)插入新鏈表。23算法分析：算法主要包括：搜索、比較、插入三個(gè)操作：23算法實(shí)現(xiàn)：

VoidMergeList_L(LinkListLa,LinkListLb,LinkList*Lc){//按值排序的單鏈表LA,LB，歸并為L(zhǎng)C后也按值排序free(Lb);//釋放Lb的頭結(jié)點(diǎn)}//MergeList_L

pc->next=pa?pa:pb;//插入剩余段while(pa&&pb)//將pa、pb結(jié)點(diǎn)按大小依次插入C中{if(pa->data<=pb->data){pc->next=pa;pc=pa;pa=pa->next;}

else{pc->next=pb;pc=pb;pb=pb->next}}pa=La->next;pb=Lb->next;pc=Lc->next；//初始化

24算法實(shí)現(xiàn)：VoidMergeList_L(Link思考：1、不用Lc，直接把La表插到Lb表中；或者把Lb表插到La表中，如何編程？2、要求不能有重復(fù)的數(shù)據(jù)元素，如何編程？VoidMergeList_L(LinkList*La,LinkListLb)相同元素不進(jìn)行歸并25思考：1、不用Lc，直接把La表插到Lb表中；或者把Lb表2答：能。只要定義一個(gè)結(jié)構(gòu)類型（含數(shù)據(jù)域和指示域）數(shù)組，就可以完全描述鏈表，這種鏈表稱為靜態(tài)鏈表。注：數(shù)據(jù)域含義與前面相同，指示域相當(dāng)于前面的指針域。討論1：用一維數(shù)組也能存放鏈表嗎？怎樣實(shí)現(xiàn)？靜態(tài)鏈表的插入與刪除操作與普通鏈表一樣，不需要移動(dòng)元素，只需修改指示器就可以了。具體實(shí)現(xiàn)過(guò)程可見(jiàn)教材P32-34。26答：能。只要定義一個(gè)結(jié)構(gòu)類型（含數(shù)據(jù)域和指示域）數(shù)組，就可以討論2：鏈表能不能首尾相連？怎樣實(shí)現(xiàn)？答：能。只要將表中最后一個(gè)結(jié)點(diǎn)的指針域指向頭結(jié)點(diǎn)即可(P->next=head;)。這種形成環(huán)路的鏈表稱為循環(huán)鏈表。討論3：?jiǎn)捂湵碇荒懿檎医Y(jié)點(diǎn)的直接后繼，能不能查找直接前驅(qū)？如何實(shí)現(xiàn)？答：能。只要把單鏈表再多開(kāi)一個(gè)指針域即可(例如用*next和*prior;)。雙向鏈表在非線性結(jié)構(gòu)（如樹(shù)結(jié)構(gòu)）中將大量使用。priordatanext這種有兩個(gè)指針的鏈表稱為雙向鏈表。其特點(diǎn)是可以雙向查找表中結(jié)點(diǎn)。參見(jiàn)教材P36－38。27討論2：鏈表能不能首尾相連？怎樣實(shí)現(xiàn)？答：能。只要將表中最循環(huán)鏈表是表中最后一個(gè)結(jié)點(diǎn)p的指針指向頭結(jié)點(diǎn)，使鏈表構(gòu)成環(huán)狀p->next=head;特點(diǎn)：從表中任一結(jié)點(diǎn)出發(fā)均可找到表中其他結(jié)點(diǎn)，提高查找效率操作與單鏈表基本一致,循環(huán)條件不同單鏈表p或p->link=NULL循環(huán)鏈表p或p->link=Hhh空表循環(huán)鏈表(circularlinkedlist)28循環(huán)鏈表是表中最后一個(gè)結(jié)點(diǎn)p的指針指向頭結(jié)點(diǎn)，使鏈表構(gòu)成環(huán)狀雙向鏈表（doublelinkedlist）單鏈表具有單向性的缺點(diǎn)typedefstructnode{datatypeelement;structnode*prior,*next;}JD;priorelementnextL空雙向循環(huán)鏈表：結(jié)點(diǎn)定義非空雙向循環(huán)鏈表：LABbcapp->prior->next=p=p->next->proir;29雙向鏈表（doublelinkedlist）typedebcaPvoiddel_dulist(JD*p){p->prior->next=p->next;

p->next->prior=p->prior;

free(p);}刪除算法描述算法評(píng)價(jià)：T(n)=O(1)p->prior->next=p->next;p->next->prior=p->prior;30bcaPvoiddel_dulist(JD*p)刪除voidins_dulist(JD*p,intx){JD*s;s=(JD*)malloc(sizeof(JD));s->element=x;

s->prior=p->prior;

p->prior->next=s;s->next=p;

p->prior=s;}算法描述算法評(píng)價(jià)：T(n)=O(1)xSbaP插入31voidins_dulist(JD*p,intx)算法5.鏈表的運(yùn)算效率分析1.查找因線性鏈表不能順序存取，即在查找時(shí)要從頭指針找起，查找的時(shí)間復(fù)雜度為

O(n)。時(shí)間效率分析2.插入和刪除因線性鏈表不需要移動(dòng)元素，只要修改指針，一般情況下時(shí)間復(fù)雜度為

O(1)。但是，如果要在單鏈表中進(jìn)行前插或刪除操作，由于要從頭查找前驅(qū)結(jié)點(diǎn)，所耗時(shí)間復(fù)雜度為O(n)。325.鏈表的運(yùn)算效率分析1.查找因線性鏈表不能順序存練：空間效率分析鏈表中每個(gè)結(jié)點(diǎn)都要增加一個(gè)指針空間，相當(dāng)于總共增加了n

個(gè)整型變量，空間復(fù)雜度為

O(n)。在n個(gè)結(jié)點(diǎn)的單鏈表中要?jiǎng)h除已知結(jié)點(diǎn)*P，需找到它的，其時(shí)間復(fù)雜度為。

前驅(qū)結(jié)點(diǎn)的地址O(n)33練：空間效率分析鏈表中每個(gè)結(jié)點(diǎn)都要增加一個(gè)指針空間，相當(dāng)于總線性表的實(shí)現(xiàn)與表示方法小結(jié)：

線性表邏輯結(jié)構(gòu)特點(diǎn)是，只有一個(gè)首結(jié)點(diǎn)和尾結(jié)點(diǎn)；除首尾結(jié)點(diǎn)外其他結(jié)點(diǎn)只有一個(gè)直接前驅(qū)和一個(gè)直接后繼。簡(jiǎn)言之，線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是一對(duì)一（1:1）的。問(wèn)1：線性表的邏輯結(jié)構(gòu)特點(diǎn)是什么？其順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)是什么？答：

順序存儲(chǔ)時(shí)，相鄰數(shù)據(jù)元素的存放地址也相鄰（邏輯與物理統(tǒng)一）；要求內(nèi)存中可用存儲(chǔ)單元的地址必須是連續(xù)的。

鏈?zhǔn)酱鎯?chǔ)時(shí)，相鄰數(shù)據(jù)元素可隨意存放，但所占存儲(chǔ)空間分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放表示結(jié)點(diǎn)間關(guān)系的指針。34線性表的實(shí)現(xiàn)與表示方法小結(jié)：線性表邏輯結(jié)構(gòu)特點(diǎn)是，只順序存儲(chǔ)的優(yōu)點(diǎn)是存儲(chǔ)密度大(＝1)，存儲(chǔ)空間利用率高。缺點(diǎn)是插入或刪除元素效率低。鏈?zhǔn)酱鎯?chǔ)的優(yōu)點(diǎn)是插入或刪除元素時(shí)效率高，使用靈活。缺點(diǎn)是存儲(chǔ)密度?。?lt;1），存儲(chǔ)空間利用率低。答：?jiǎn)?：順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)各有哪些優(yōu)缺點(diǎn)？事實(shí)上，鏈表插入、刪除運(yùn)算的快捷是以空間代價(jià)來(lái)?yè)Q取時(shí)間。35順序存儲(chǔ)的優(yōu)點(diǎn)是存儲(chǔ)密度大(＝1)，存儲(chǔ)空間利用率高2.4應(yīng)用舉例一元多項(xiàng)式的數(shù)學(xué)通式？用C語(yǔ)言如何描述它的定義？如何編程實(shí)現(xiàn)兩個(gè)一元多項(xiàng)式相加？一元多項(xiàng)式的計(jì)算(參見(jiàn)嚴(yán)教材P46–55)討論：362.4應(yīng)用舉例一元多項(xiàng)式的數(shù)學(xué)通式？一元多項(xiàng)式的計(jì)算(1.一元多項(xiàng)式的數(shù)學(xué)通式？一元多項(xiàng)式的通式可表示為：假定m<n371.一元多項(xiàng)式的數(shù)學(xué)通式？一元多項(xiàng)式的通式可表示為：假定分析：一元多項(xiàng)式在計(jì)算機(jī)內(nèi)存儲(chǔ)時(shí)，既可用順序表存儲(chǔ)，又可用鏈表存儲(chǔ)。那么實(shí)際應(yīng)用中如何選取采用哪種存儲(chǔ)方式呢？p0p1p2…pn-1pn順序表鏈表a1

02283

104^多項(xiàng)式的次數(shù)不高且零系數(shù)項(xiàng)較少時(shí)多項(xiàng)式的次數(shù)很高且零系數(shù)項(xiàng)較多時(shí)（通常設(shè)計(jì)兩個(gè)數(shù)據(jù)域和一個(gè)指針域）38分析：一元多項(xiàng)式在計(jì)算機(jī)內(nèi)存儲(chǔ)時(shí)，既可用順序表存儲(chǔ)，又可用鏈2.用C語(yǔ)言如何具體描述它的定義？法一：用類C語(yǔ)言，參見(jiàn)教材P42法二：用標(biāo)準(zhǔn)C語(yǔ)言：typedefstructpoly_node

*poly_pointer;typedefstructpoly_node{intcoef;

//coefficient系數(shù)intexpon;//exponent指數(shù)

poly_pointerlink;};

poly_pointera,b,c;coefexponlink392.用C語(yǔ)言如何具體描述它的定義？法一：用類C語(yǔ)言，參見(jiàn)4.如何編程實(shí)現(xiàn)兩個(gè)一元多項(xiàng)式相加？3142810a^814－310106b^例：運(yùn)算規(guī)則：兩多項(xiàng)式中指數(shù)相同的項(xiàng)對(duì)應(yīng)系數(shù)相加，若和不為0,則構(gòu)成多項(xiàng)式c(=a+b)中的一項(xiàng)；a和b中所有指數(shù)不相同的項(xiàng)均應(yīng)復(fù)制到c中。404.如何編程實(shí)現(xiàn)兩個(gè)一元多項(xiàng)式相加？3142實(shí)現(xiàn)思路：依次比較Pa和Pb所指結(jié)點(diǎn)中的指數(shù)項(xiàng)，依Pa->expon==

<

>Pb->expon等情況，再?zèng)Q定是將兩系數(shù)域的數(shù)值相加（并判其和是否為0），還是將較高指數(shù)項(xiàng)的結(jié)點(diǎn)插入到新表c中。3142810^aPa814-310106^bPb1114-3102810^cPc106+41實(shí)現(xiàn)思路：依次比較Pa和Pb所指結(jié)點(diǎn)中的指數(shù)項(xiàng)，依31.設(shè)p,q分別指向A,B中某一結(jié)點(diǎn)，p,q初值是第一結(jié)點(diǎn)2.比較p->exp與q->expp->exp<q->exp:p結(jié)點(diǎn)是和多項(xiàng)式中的一項(xiàng)

p后移,q不動(dòng)p->exp>q->exp:q結(jié)點(diǎn)是和多項(xiàng)式中的一項(xiàng)

將q插在p之前,q后移,p不動(dòng)p->exp==q->exp:系數(shù)相加0：從A表中刪去p,

釋放p,q，p,q后移0：修改p系數(shù)域,

釋放q，p,q后移3.直到p或q為NULL若q==NULL，結(jié)束若p==NULL，將B中剩余部分連到A上即可運(yùn)算規(guī)則（將A，B兩多項(xiàng)式的和存儲(chǔ)在A中）421.設(shè)p,q分別指向A,B中某一結(jié)點(diǎn)，p,q初值是第一結(jié)點(diǎn)加法運(yùn)算的拓展－乘法:43加法運(yùn)算的拓展－乘法:43本章小結(jié)1.線性表邏輯結(jié)構(gòu)：“一對(duì)一”或1:1存儲(chǔ)結(jié)構(gòu)：順序、鏈?zhǔn)竭\(yùn)算：修改、插入、刪除3.鏈?zhǔn)酱鎯?chǔ)特征：邏輯上相鄰，物理上不一定相鄰；優(yōu)點(diǎn)：插入刪除效率高O(1)（后）缺點(diǎn)：查找慢O(n)2.順序存儲(chǔ)特征：邏輯上相鄰，物理上也相鄰；優(yōu)點(diǎn)：隨機(jī)查找快O(1)缺點(diǎn)：插入、刪除慢O(n)有獎(jiǎng)思考題：在實(shí)際應(yīng)用中如何選用順序表和鏈表？44本章小結(jié)1.線性表邏輯結(jié)構(gòu)：“一對(duì)一”或1:13.鏈?zhǔn)阶鳂I(yè)請(qǐng)下周上課時(shí)交來(lái)！2.2自測(cè)

2.4，2.7，有獎(jiǎng)附加2.13第一次實(shí)驗(yàn)：第一次作業(yè)程序?qū)崿F(xiàn)，地點(diǎn)：電氣信息樓2樓實(shí)驗(yàn)室45作業(yè)請(qǐng)下周上課時(shí)交來(lái)！2.2自測(cè)第一次實(shí)驗(yàn)：第一每課一貼：原來(lái)很簡(jiǎn)單有個(gè)小弟在腳踏車店當(dāng)學(xué)徒，有人送來(lái)一部故障的腳踏車，小弟除了將車修好，還把車子整理的漂亮如新，其它學(xué)徒笑他多此一舉，后來(lái)雇主將腳踏車領(lǐng)回去的第二天，小弟被挖角到那位雇主的公司上班。原來(lái)出人頭地很簡(jiǎn)單，吃點(diǎn)虧就可以了。有一個(gè)網(wǎng)球教練對(duì)學(xué)生說(shuō)：「如果一個(gè)網(wǎng)球掉進(jìn)草堆里，應(yīng)該如何找？」有人答：「從草堆中心線開(kāi)始找?！褂腥舜穑骸笍牟荻训淖畎继庨_(kāi)始找?！褂腥舜穑骸笍牟葑铋L(zhǎng)的地方開(kāi)始找?！菇叹毿颊_答案：「按部就班的從草地的一頭，搜尋到草地的另一頭。原來(lái)尋找成功的方法很簡(jiǎn)單，從一數(shù)到十不要跳過(guò)就可以了。

46每課一貼：原來(lái)很簡(jiǎn)單1上堂課要點(diǎn)回顧線性結(jié)構(gòu)(包括表、棧、隊(duì)、數(shù)組）的定義和特點(diǎn)：僅一個(gè)首、尾結(jié)點(diǎn)，其余元素僅一個(gè)直接前驅(qū)和一個(gè)直接后繼。2.線性表邏輯結(jié)構(gòu)：“一對(duì)一”或1:1存儲(chǔ)結(jié)構(gòu)：順序、鏈?zhǔn)竭\(yùn)算：修改、插入、刪除3.順序存儲(chǔ)特征：邏輯上相鄰，物理上也相鄰；優(yōu)點(diǎn)：隨機(jī)查找快O(1)缺點(diǎn)：插入、刪除慢O(n)47上堂課要點(diǎn)回顧線性結(jié)構(gòu)(包括表、棧、隊(duì)、數(shù)組）的定義和特點(diǎn)：2.3線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)2.3.1鏈表的表示2.3.2鏈表的實(shí)現(xiàn)2.3.3鏈表的運(yùn)算效率分析鏈表小結(jié)482.3線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)2.3.1鏈表的表示鏈表2.3.1鏈表的表示1536元素21400元素11346元素3∧元素41345h存儲(chǔ)地址存儲(chǔ)內(nèi)容指針1345元素114001346元素4∧…….……..…….1400元素21536…….……..…….1536元素31346h492.3.1鏈表的表示1536元素21400元素1134鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)特點(diǎn)：其結(jié)點(diǎn)在存儲(chǔ)器中的位置是隨意的，即邏輯上相鄰的數(shù)據(jù)元素在物理上不一定相鄰。如何實(shí)現(xiàn)？通過(guò)指針來(lái)實(shí)現(xiàn)注意：每個(gè)存儲(chǔ)結(jié)點(diǎn)都包含兩部分：

數(shù)據(jù)域和指針域2.3.1鏈表的表示50鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)特點(diǎn)：其結(jié)點(diǎn)在存儲(chǔ)器中的位置是隨意的，即邏輯上相例1畫(huà)出26個(gè)英文字母表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。該字母表在內(nèi)存的鏈?zhǔn)酱娣攀疽鈭D如下：

解：該字母表的邏輯結(jié)構(gòu)為：（a,b,…,y,z）aheadb/\z……各結(jié)點(diǎn)由兩個(gè)域組成：數(shù)據(jù)域：存儲(chǔ)元素?cái)?shù)值數(shù)據(jù)；指針域：存儲(chǔ)直接后繼或者直接前驅(qū)的存儲(chǔ)位置。指針數(shù)據(jù)指針數(shù)據(jù)指針或樣式：51例1畫(huà)出26個(gè)英文字母表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。該字母表在與鏈?zhǔn)酱鎯?chǔ)有關(guān)的術(shù)語(yǔ)：1、結(jié)點(diǎn)：數(shù)據(jù)元素的存儲(chǔ)映像。由數(shù)據(jù)域和指針域兩部分組成；2、鏈表：

n個(gè)結(jié)點(diǎn)由指針鏈組成一個(gè)鏈表。它是線性表的鏈?zhǔn)酱鎯?chǔ)映像，稱為線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。3、單鏈表、雙鏈表、多鏈表、循環(huán)鏈表：結(jié)點(diǎn)只有一個(gè)指針域的鏈表，稱為單鏈表或線性鏈表；有兩個(gè)指針域的鏈表，稱為雙鏈表；有多個(gè)指針域的鏈表，稱為多鏈表；首尾相接的鏈表稱為循環(huán)鏈表。a1heada2an……h(huán)ead循環(huán)鏈表示意圖：52與鏈?zhǔn)酱鎯?chǔ)有關(guān)的術(shù)語(yǔ)：1、結(jié)點(diǎn)：數(shù)據(jù)元素的存儲(chǔ)映像。由數(shù)據(jù)域4、頭指針、頭結(jié)點(diǎn)和首元結(jié)點(diǎn)

示意圖如下：頭指針頭結(jié)點(diǎn)首元結(jié)點(diǎn)a1heada2…infoan^頭指針是指向鏈表中第一個(gè)結(jié)點(diǎn)（或?yàn)轭^結(jié)點(diǎn)或?yàn)槭自Y(jié)點(diǎn)）的指針；頭結(jié)點(diǎn)是在鏈表的首元結(jié)點(diǎn)之前附設(shè)的一個(gè)結(jié)點(diǎn)；數(shù)據(jù)域內(nèi)只放空表標(biāo)志和表長(zhǎng)等信息;首元結(jié)點(diǎn)是指鏈表中存儲(chǔ)線性表第一個(gè)數(shù)據(jù)元素a1的結(jié)點(diǎn)。534、頭指針、頭結(jié)點(diǎn)和首元結(jié)點(diǎn)示意圖如下：頭指針頭結(jié)點(diǎn)首元結(jié)一個(gè)線性表的邏輯結(jié)構(gòu)為：（ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG），其存儲(chǔ)結(jié)構(gòu)用單鏈表表示如下，請(qǐng)問(wèn)其頭指針的值是多少？存儲(chǔ)地址數(shù)據(jù)域指針域1LI437QIAN1313SUN119WANGNULL25WU3731ZHAO737ZHENG1943ZHOU25例：答：頭指針是指向鏈表中第一個(gè)結(jié)點(diǎn)的指針，因此關(guān)鍵是要尋找第一個(gè)結(jié)點(diǎn)的地址。7ZHAOH31∴頭指針的值是3154一個(gè)線性表的邏輯結(jié)構(gòu)為：（ZHAO,QIAN,SUN,LI,上例鏈表的邏輯結(jié)構(gòu)示意圖有以下兩種形式：①ZHAOQIANLISUNZHOUWUZHENG/\WANGH②ZHAOQIANLISUNZHOUWUZHENG/\WANGH區(qū)別：①

無(wú)頭結(jié)點(diǎn)②

有頭結(jié)點(diǎn)55上例鏈表的邏輯結(jié)構(gòu)示意圖有以下兩種形式：①ZHAOQIANL討論1.在鏈表中設(shè)置頭結(jié)點(diǎn)有什么好處？頭結(jié)點(diǎn)即在鏈表的首元結(jié)點(diǎn)之前附設(shè)的一個(gè)結(jié)點(diǎn)，該結(jié)點(diǎn)的數(shù)據(jù)域中不存儲(chǔ)線性表的數(shù)據(jù)元素，其作用是為了對(duì)鏈表進(jìn)行操作時(shí)，可以對(duì)空表、非空表的情況以及對(duì)首元結(jié)點(diǎn)進(jìn)行統(tǒng)一處理，編程更方便。答：討論2.頭結(jié)點(diǎn)的數(shù)據(jù)域內(nèi)裝的是什么？頭結(jié)點(diǎn)的數(shù)據(jù)域可以為空，也可存放線性表長(zhǎng)度等附加信息，但此結(jié)點(diǎn)不能計(jì)入鏈表長(zhǎng)度值。答：頭結(jié)點(diǎn)的數(shù)據(jù)域H56討論1.在鏈表中設(shè)置頭結(jié)點(diǎn)有什么好處？頭結(jié)點(diǎn)即在鏈表的首元討論4.鏈表的數(shù)據(jù)元素有兩個(gè)域，不再是簡(jiǎn)單數(shù)據(jù)類型，編程時(shí)該如何表示？因每個(gè)結(jié)點(diǎn)至少有兩個(gè)分量，所以要采用結(jié)構(gòu)數(shù)據(jù)類型。答：什么是結(jié)構(gòu)類型？如何書(shū)寫(xiě)表達(dá)？

答：討論3.如何表示空表？無(wú)頭結(jié)點(diǎn)時(shí)，當(dāng)頭指針的值為空時(shí)表示空表；有頭結(jié)點(diǎn)時(shí)，當(dāng)頭結(jié)點(diǎn)的指針域?yàn)榭諘r(shí)表示空表。^頭指針^頭指針頭結(jié)點(diǎn)無(wú)頭結(jié)點(diǎn)有頭結(jié)點(diǎn)57討論4.鏈表的數(shù)據(jù)元素有兩個(gè)域，不再是簡(jiǎn)單數(shù)據(jù)類型，編程時(shí)實(shí)現(xiàn)typedefstructnode{

Elemtype

data;structnode*link;}LNode，*LinkList;linklist*h,*p;datalinkp結(jié)點(diǎn)（*p）(*p)表示p所指向的結(jié)點(diǎn)(*p).datap->data表示p指向結(jié)點(diǎn)的數(shù)據(jù)域(*p).linkp->link表示p指向結(jié)點(diǎn)的指針域生成一個(gè)LNode型新結(jié)點(diǎn)：p=(linklist)malloc(sizeof(LNode));系統(tǒng)回收p結(jié)點(diǎn)：free(p)3.線性鏈表的實(shí)現(xiàn)定義：結(jié)點(diǎn)中只含一個(gè)指針域的鏈表叫~，也叫單鏈表58實(shí)現(xiàn)typedefstructnode{linkli用一組任意的存儲(chǔ)單元存儲(chǔ)線性表的數(shù)據(jù)元素利用指針實(shí)現(xiàn)了用不相鄰的存儲(chǔ)單元存放邏輯上相鄰的元素每個(gè)數(shù)據(jù)元素ai，除存儲(chǔ)本身信息外，還需存儲(chǔ)其直接后繼的地址結(jié)點(diǎn) 數(shù)據(jù)域：元素本身信息指針域：指示直接后繼的存儲(chǔ)位置數(shù)據(jù)域指針域結(jié)點(diǎn)簡(jiǎn)單總結(jié)：線性表的鏈?zhǔn)奖硎镜幕咎卣鳎?9數(shù)據(jù)域指針域結(jié)點(diǎn)簡(jiǎn)單總結(jié)：線性表的鏈?zhǔn)奖硎镜幕咎卣鳎?4.單鏈表的基本運(yùn)算While循環(huán)中語(yǔ)句頻度為若找到結(jié)點(diǎn)X，為結(jié)點(diǎn)X在表中的序號(hào)否則，為n算法評(píng)價(jià)查找：查找單鏈表中是否存在結(jié)點(diǎn)X，若有則返回指向X結(jié)點(diǎn)的指針；否則返回NULL查找、插入、刪除、創(chuàng)建、原地逆序算法描述類似算法：求長(zhǎng)度等，舉一反三P36查找604.單鏈表的基本運(yùn)算While循環(huán)中語(yǔ)句頻度為若找到結(jié)點(diǎn)Xpabxs插入:在線性表兩個(gè)數(shù)據(jù)元素a和b間插入x，已知p指向as->link=p->link;p->link=s;算法描述算法評(píng)價(jià)注意前插和后插的區(qū)別61pabxs插入:在線性表兩個(gè)數(shù)據(jù)元素a和b間插入x，已知p算法描述pabc算法評(píng)價(jià)刪除：?jiǎn)捂湵碇袆h除b，設(shè)p指向ap->link=p->link->link;62算法描述pabc算法評(píng)價(jià)刪除：?jiǎn)捂湵碇袆h除b，設(shè)p指向ap-

動(dòng)態(tài)建立單鏈表算法：設(shè)線性表n個(gè)元素已存放在數(shù)組a中，建立一個(gè)單鏈表，h為頭指針?biāo)惴枋鏊惴ㄔu(píng)價(jià)h頭結(jié)點(diǎn)an^0h頭結(jié)點(diǎn)an-10an^a2…...h頭結(jié)點(diǎn)an-10an^ha1a2頭結(jié)點(diǎn)an^…...0h頭結(jié)點(diǎn)0^注意前插和后插的區(qū)別P35/3663動(dòng)態(tài)建立單鏈表算法：設(shè)線性表n個(gè)元素已存放在數(shù)組a中，建立單鏈表原地逆序算法：設(shè)線性表n個(gè)元素已存放在鏈表a中，要求在不改變其元素位置的條件下將鏈表逆序排列，h為頭指針?biāo)惴枋鏊惴ㄔu(píng)價(jià)ha1a2頭結(jié)點(diǎn)an^…...0hanan-1頭結(jié)點(diǎn)a1^…...064單鏈表原地逆序算法：設(shè)線性表n個(gè)元素已存放在鏈表a中，要求在5.應(yīng)用舉例：兩個(gè)鏈表的歸并（教材P41）算法要求：已知：線性表A、B，分別由單鏈表LA,LB存儲(chǔ)，其中數(shù)據(jù)元素按值非遞減有序排列，要求：將A，B歸并為一個(gè)新的線性表C,C的數(shù)據(jù)元素仍按值非遞減排列。設(shè)線性表C由單鏈表

LC存儲(chǔ)。假設(shè)：A=（3，5，8，11），B=（2，6，8，9，11）預(yù)測(cè)：合并后C=（2,3,5,6,8,8,9,11，11）655.應(yīng)用舉例：兩個(gè)鏈表的歸并（教材P41）算法要求：20用鏈表可表示為：3511/\8

La2611/\8

Lb92365

Lc8頭結(jié)點(diǎn)66用鏈表可表示為：3511/\8La2611/La3

5

8

11^

Lb2

6

8

11^9

PaPbPaPbPa、Pb用于搜索La和Lb，

Pc指向新鏈表當(dāng)前結(jié)點(diǎn)Lc

…

Pa3

PcPa5

Pc11^Pc2

PbPcPa67La35811^Lb26811^9PaPb算法分析：算法主要包括：搜索、比較、插入三個(gè)操作：搜索：需要兩個(gè)指針?biāo)阉鲀蓚€(gè)鏈表；比較：比較結(jié)點(diǎn)數(shù)據(jù)域中數(shù)據(jù)的大??；插入：將兩個(gè)結(jié)點(diǎn)中數(shù)據(jù)小的結(jié)點(diǎn)插入新鏈表。68算法分析：算法主要包括：搜索、比較、插入三個(gè)操作：23算法實(shí)現(xiàn)：

VoidMergeList_L(LinkListLa,LinkListLb,LinkList*Lc){//按值排序的單鏈表LA,LB，歸并為L(zhǎng)C后也按值排序free(Lb);//釋放Lb的頭結(jié)點(diǎn)}//MergeList_L

pc->next=pa?pa:pb;//插入剩余段while(pa&&pb)//將pa、pb結(jié)點(diǎn)按大小依次插入C中{if(pa->data<=pb->data){pc->next=pa;pc=pa;pa=pa->next;}

else{pc->next=pb;pc=pb;pb=pb->next}}pa=La->next;pb=Lb->next;pc=Lc->next；//初始化

69算法實(shí)現(xiàn)：VoidMergeList_L(Link思考：1、不用Lc，直接把La表插到Lb表中；或者把Lb表插到La表中，如何編程？2、要求不能有重復(fù)的數(shù)據(jù)元素，如何編程？VoidMergeList_L(LinkList*La,LinkListLb)相同元素不進(jìn)行歸并70思考：1、不用Lc，直接把La表插到Lb表中；或者把Lb表2答：能。只要定義一個(gè)結(jié)構(gòu)類型（含數(shù)據(jù)域和指示域）數(shù)組，就可以完全描述鏈表，這種鏈表稱為靜態(tài)鏈表。注：數(shù)據(jù)域含義與前面相同，指示域相當(dāng)于前面的指針域。討論1：用一維數(shù)組也能存放鏈表嗎？怎樣實(shí)現(xiàn)？靜態(tài)鏈表的插入與刪除操作與普通鏈表一樣，不需要移動(dòng)元素，只需修改指示器就可以了。具體實(shí)現(xiàn)過(guò)程可見(jiàn)教材P32-34。71答：能。只要定義一個(gè)結(jié)構(gòu)類型（含數(shù)據(jù)域和指示域）數(shù)組，就可以討論2：鏈表能不能首尾相連？怎樣實(shí)現(xiàn)？答：能。只要將表中最后一個(gè)結(jié)點(diǎn)的指針域指向頭結(jié)點(diǎn)即可(P->next=head;)。這種形成環(huán)路的鏈表稱為循環(huán)鏈表。討論3：?jiǎn)捂湵碇荒懿檎医Y(jié)點(diǎn)的直接后繼，能不能查找直接前驅(qū)？如何實(shí)現(xiàn)？答：能。只要把單鏈表再多開(kāi)一個(gè)指針域即可(例如用*next和*prior;)。雙向鏈表在非線性結(jié)構(gòu)（如樹(shù)結(jié)構(gòu)）中將大量使用。priordatanext這種有兩個(gè)指針的鏈表稱為雙向鏈表。其特點(diǎn)是可以雙向查找表中結(jié)點(diǎn)。參見(jiàn)教材P36－38。72討論2：鏈表能不能首尾相連？怎樣實(shí)現(xiàn)？答：能。只要將表中最循環(huán)鏈表是表中最后一個(gè)結(jié)點(diǎn)p的指針指向頭結(jié)點(diǎn)，使鏈表構(gòu)成環(huán)狀p->next=head;特點(diǎn)：從表中任一結(jié)點(diǎn)出發(fā)均可找到表中其他結(jié)點(diǎn)，提高查找效率操作與單鏈表基本一致,循環(huán)條件不同單鏈表p或p->link=NULL循環(huán)鏈表p或p->link=Hhh空表循環(huán)鏈表(circularlinkedlist)73循環(huán)鏈表是表中最后一個(gè)結(jié)點(diǎn)p的指針指向頭結(jié)點(diǎn)，使鏈表構(gòu)成環(huán)狀雙向鏈表（doublelinkedlist）單鏈表具有單向性的缺點(diǎn)typedefstructnode{datatypeelement;structnode*prior,*next;}JD;priorelementnextL空雙向循環(huán)鏈表：結(jié)點(diǎn)定義非空雙向循環(huán)鏈表：LABbcapp->prior->next=p=p->next->proir;74雙向鏈表（doublelinkedlist）typedebcaPvoiddel_dulist(JD*p){p->prior->next=p->next;

p->next->prior=p->prior;

free(p);}刪除算法描述算法評(píng)價(jià)：T(n)=O(1)p->prior->next=p->next;p->next->prior=p->prior;75bcaPvoiddel_dulist(JD*p)刪除voidins_dulist(JD*p,intx){JD*s;s=(JD*)malloc(sizeof(JD));s->element=x;

s->prior=p->prior;

p->prior->next=s;s->next=p;

p->prior=s;}算法描述算法評(píng)價(jià)：T(n)=O(1)xSbaP插入76voidins_dulist(JD*p,intx)算法5.鏈表的運(yùn)算效率分析1.查找因線性鏈表不能順序存取，即在查找時(shí)要從頭指針找起，查找的時(shí)間復(fù)雜度為

O(n)。時(shí)間效率分析2.插入和刪除因線性鏈表不需要移動(dòng)元素，只要修改指針，一般情況下時(shí)間復(fù)雜度為

O(1)。但是，如果要在單鏈表中進(jìn)行前插或刪除操作，由于要從頭查找前驅(qū)結(jié)點(diǎn)，所耗時(shí)間復(fù)雜度為O(n)。775.鏈表的運(yùn)算效率分析1.查找因線性鏈表不能順序存練：空間效率分析鏈表中每個(gè)結(jié)點(diǎn)都要增加一個(gè)指針空間，相當(dāng)于總共增加了n

個(gè)整型變量，空間復(fù)雜度為

O(n)。在n個(gè)結(jié)點(diǎn)的單鏈表中要?jiǎng)h除已知結(jié)點(diǎn)*P，需找到它的，其時(shí)間復(fù)雜度為。

前驅(qū)結(jié)點(diǎn)的地址O(n)78練：空間效率分析鏈表中每個(gè)結(jié)點(diǎn)都要增加一個(gè)指針空間，相當(dāng)于總線性表的實(shí)現(xiàn)與表示方法小結(jié)：

線性表邏輯結(jié)構(gòu)特點(diǎn)是，只有一個(gè)首結(jié)點(diǎn)和尾結(jié)點(diǎn)；除首尾結(jié)點(diǎn)外其他結(jié)點(diǎn)只有一個(gè)直接前驅(qū)和一個(gè)直接后繼。簡(jiǎn)言之，線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是一對(duì)一（1:1）的。問(wèn)1：線性表的邏輯結(jié)構(gòu)特點(diǎn)是什么？其順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)是什么？答：

順序存儲(chǔ)時(shí)，相鄰數(shù)據(jù)元素的存放地址也相鄰（邏輯與物理統(tǒng)一）；要求內(nèi)存中可用存儲(chǔ)單元的地址必須是連續(xù)的。

鏈?zhǔn)酱鎯?chǔ)時(shí)，相鄰數(shù)據(jù)元素可隨意存放，但所占存儲(chǔ)空間分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放表示結(jié)點(diǎn)間關(guān)系的指針。79線性表的實(shí)現(xiàn)與表示方法小結(jié)：線性表邏輯結(jié)構(gòu)特點(diǎn)是，只順序存儲(chǔ)的優(yōu)點(diǎn)是存儲(chǔ)密度大(＝1)，存儲(chǔ)空間利用率高。缺點(diǎn)是插入或刪除元素效率低。鏈?zhǔn)酱鎯?chǔ)的優(yōu)點(diǎn)是插入或刪除元素時(shí)效率高，使用靈活。缺點(diǎn)是存儲(chǔ)密度?。?lt;1），存儲(chǔ)空間利用率低。答：?jiǎn)?：順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)各有哪些優(yōu)缺點(diǎn)？事實(shí)上，鏈表插入、刪除運(yùn)算的快捷是以空間代價(jià)來(lái)?yè)Q取時(shí)間。80順序存儲(chǔ)的優(yōu)點(diǎn)是存儲(chǔ)密度大(＝1)，存儲(chǔ)空間利用率高2.4應(yīng)用舉例一元多項(xiàng)式的數(shù)學(xué)通式？用C語(yǔ)言如何