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

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

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

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

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

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

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

無頭結(jié)點②

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

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

Elemtype

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

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

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

La2611/\8

Lb92365

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

5

8

11^

Lb2

6

8

11^9

PaPbPaPbPa、Pb用于搜索La和Lb，

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

…

Pa3

PcPa5

Pc11^Pc2

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

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

pc->next=pa?pa:pb;//插入剩余段while(pa&&pb)//將pa、pb結(jié)點按大小依次插入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算法實現(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答：能。只要定義一個結(jié)構(gòu)類型（含數(shù)據(jù)域和指示域）數(shù)組，就可以完全描述鏈表，這種鏈表稱為靜態(tài)鏈表。注：數(shù)據(jù)域含義與前面相同，指示域相當(dāng)于前面的指針域。討論1：用一維數(shù)組也能存放鏈表嗎？怎樣實現(xiàn)？靜態(tài)鏈表的插入與刪除操作與普通鏈表一樣，不需要移動元素，只需修改指示器就可以了。具體實現(xiàn)過程可見教材P32-34。26答：能。只要定義一個結(jié)構(gòu)類型（含數(shù)據(jù)域和指示域）數(shù)組，就可以討論2：鏈表能不能首尾相連？怎樣實現(xiàn)？答：能。只要將表中最后一個結(jié)點的指針域指向頭結(jié)點即可(P->next=head;)。這種形成環(huán)路的鏈表稱為循環(huán)鏈表。討論3：單鏈表只能查找結(jié)點的直接后繼，能不能查找直接前驅(qū)？如何實現(xiàn)？答：能。只要把單鏈表再多開一個指針域即可(例如用*next和*prior;)。雙向鏈表在非線性結(jié)構(gòu)（如樹結(jié)構(gòu)）中將大量使用。priordatanext這種有兩個指針的鏈表稱為雙向鏈表。其特點是可以雙向查找表中結(jié)點。參見教材P36－38。27討論2：鏈表能不能首尾相連？怎樣實現(xiàn)？答：能。只要將表中最循環(huán)鏈表是表中最后一個結(jié)點p的指針指向頭結(jié)點，使鏈表構(gòu)成環(huán)狀p->next=head;特點：從表中任一結(jié)點出發(fā)均可找到表中其他結(jié)點，提高查找效率操作與單鏈表基本一致,循環(huán)條件不同單鏈表p或p->link=NULL循環(huán)鏈表p或p->link=Hhh空表循環(huán)鏈表(circularlinkedlist)28循環(huán)鏈表是表中最后一個結(jié)點p的指針指向頭結(jié)點，使鏈表構(gòu)成環(huán)狀雙向鏈表（doublelinkedlist）單鏈表具有單向性的缺點typedefstructnode{datatypeelement;structnode*prior,*next;}JD;priorelementnextL空雙向循環(huán)鏈表：結(jié)點定義非空雙向循環(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);}刪除算法描述算法評價：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;}算法描述算法評價：T(n)=O(1)xSbaP插入31voidins_dulist(JD*p,intx)算法5.鏈表的運算效率分析1.查找因線性鏈表不能順序存取，即在查找時要從頭指針找起，查找的時間復(fù)雜度為

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

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

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

O(n)。在n個結(jié)點的單鏈表中要刪除已知結(jié)點*P，需找到它的，其時間復(fù)雜度為。

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

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

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

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

02283

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

*poly_pointer;typedefstructpoly_node{intcoef;

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

poly_pointerlink;};

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

<

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

p后移,q不動p->exp>q->exp:q結(jié)點是和多項式中的一項

將q插在p之前,q后移,p不動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上即可運算規(guī)則（將A，B兩多項式的和存儲在A中）421.設(shè)p,q分別指向A,B中某一結(jié)點，p,q初值是第一結(jié)點加法運算的拓展－乘法:43加法運算的拓展－乘法:43本章小結(jié)1.線性表邏輯結(jié)構(gòu)：“一對一”或1:1存儲結(jié)構(gòu)：順序、鏈?zhǔn)竭\算：修改、插入、刪除3.鏈?zhǔn)酱鎯μ卣鳎哼壿嬌舷噜?，物理上不一定相鄰；?yōu)點：插入刪除效率高O(1)（后）缺點：查找慢O(n)2.順序存儲特征：邏輯上相鄰，物理上也相鄰；優(yōu)點：隨機(jī)查找快O(1)缺點：插入、刪除慢O(n)有獎思考題：在實際應(yīng)用中如何選用順序表和鏈表？44本章小結(jié)1.線性表邏輯結(jié)構(gòu)：“一對一”或1:13.鏈?zhǔn)阶鳂I(yè)請下周上課時交來！2.2自測

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

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

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

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

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

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

無頭結(jié)點②

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

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

Elemtype

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

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

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

La2611/\8

Lb92365

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

5

8

11^

Lb2

6

8

11^9

PaPbPaPbPa、Pb用于搜索La和Lb，

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

…

Pa3

PcPa5

Pc11^Pc2

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

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

pc->next=pa?pa:pb;//插入剩余段while(pa&&pb)//將pa、pb結(jié)點按大小依次插入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算法實現(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答：能。只要定義一個結(jié)構(gòu)類型（含數(shù)據(jù)域和指示域）數(shù)組，就可以完全描述鏈表，這種鏈表稱為靜態(tài)鏈表。注：數(shù)據(jù)域含義與前面相同，指示域相當(dāng)于前面的指針域。討論1：用一維數(shù)組也能存放鏈表嗎？怎樣實現(xiàn)？靜態(tài)鏈表的插入與刪除操作與普通鏈表一樣，不需要移動元素，只需修改指示器就可以了。具體實現(xiàn)過程可見教材P32-34。71答：能。只要定義一個結(jié)構(gòu)類型（含數(shù)據(jù)域和指示域）數(shù)組，就可以討論2：鏈表能不能首尾相連？怎樣實現(xiàn)？答：能。只要將表中最后一個結(jié)點的指針域指向頭結(jié)點即可(P->next=head;)。這種形成環(huán)路的鏈表稱為循環(huán)鏈表。討論3：單鏈表只能查找結(jié)點的直接后繼，能不能查找直接前驅(qū)？如何實現(xiàn)？答：能。只要把單鏈表再多開一個指針域即可(例如用*next和*prior;)。雙向鏈表在非線性結(jié)構(gòu)（如樹結(jié)構(gòu)）中將大量使用。priordatanext這種有兩個指針的鏈表稱為雙向鏈表。其特點是可以雙向查找表中結(jié)點。參見教材P36－38。72討論2：鏈表能不能首尾相連？怎樣實現(xiàn)？答：能。只要將表中最循環(huán)鏈表是表中最后一個結(jié)點p的指針指向頭結(jié)點，使鏈表構(gòu)成環(huán)狀p->next=head;特點：從表中任一結(jié)點出發(fā)均可找到表中其他結(jié)點，提高查找效率操作與單鏈表基本一致,循環(huán)條件不同單鏈表p或p->link=NULL循環(huán)鏈表p或p->link=Hhh空表循環(huán)鏈表(circularlinkedlist)73循環(huán)鏈表是表中最后一個結(jié)點p的指針指向頭結(jié)點，使鏈表構(gòu)成環(huán)狀雙向鏈表（doublelinkedlist）單鏈表具有單向性的缺點typedefstructnode{datatypeelement;structnode*prior,*next;}JD;priorelementnextL空雙向循環(huán)鏈表：結(jié)點定義非空雙向循環(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);}刪除算法描述算法評價：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;}算法描述算法評價：T(n)=O(1)xSbaP插入76voidins_dulist(JD*p,intx)算法5.鏈表的運算效率分析1.查找因線性鏈表不能順序存取，即在查找時要從頭指針找起，查找的時間復(fù)雜度為

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

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

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

O(n)。在n個結(jié)點的單鏈表中要刪除已知結(jié)點*P，需找到它的，其時間復(fù)雜度為。

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

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

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

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