數(shù)據(jù)結(jié)構(gòu)第二章線性表課件

1．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)

2、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)A．線性結(jié)構(gòu)B．非線性結(jié)構(gòu)A順序存儲(chǔ)B鏈?zhǔn)酱鎯?chǔ)線性表?xiàng)ｊ?duì)列樹圖數(shù)據(jù)結(jié)構(gòu)(物理結(jié)構(gòu))數(shù)據(jù)結(jié)構(gòu)：是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。

邏輯結(jié)構(gòu)：結(jié)構(gòu)定義中的“關(guān)系”描述的是數(shù)據(jù)元素之間的邏輯關(guān)系，因此稱為數(shù)據(jù)的邏輯結(jié)構(gòu)。

存儲(chǔ)結(jié)構(gòu)：是數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示（又稱映像）。前一章復(fù)習(xí)10/14/20221<識(shí)記>線性結(jié)構(gòu)的特點(diǎn)；線性表的相關(guān)概念；線性表上定義的基本運(yùn)算和用基本運(yùn)算構(gòu)造出的較復(fù)雜的運(yùn)算。<重點(diǎn)>掌握順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的描述方法，以及各種基本操作的實(shí)現(xiàn)。<綜合應(yīng)用>能夠從時(shí)間復(fù)雜度的角度綜合比較線性表兩種存儲(chǔ)結(jié)構(gòu)的不同特點(diǎn)及其適用場合。<難點(diǎn)>使用本章所學(xué)的基本知識(shí)設(shè)計(jì)有效算法解決與線性表相關(guān)的應(yīng)用問題。本章知識(shí)點(diǎn)10/14/202222.1線性表的類型定義本章目錄2.2線性表的順序表示和實(shí)現(xiàn)2.3線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)第2章線性表本節(jié)總結(jié)2.4一元多項(xiàng)式的表示及相加10/14/20223線性結(jié)構(gòu)的特點(diǎn)：在數(shù)據(jù)元素的非空有限集中，(1)存在唯一的一個(gè)被稱為第一個(gè)的數(shù)據(jù)元素；(2)存在唯一的一個(gè)被稱為最后一個(gè)的數(shù)據(jù)元素；(3)除第一個(gè)之外，集合中的每個(gè)數(shù)據(jù)元素均只有一個(gè)前驅(qū)；(4)除最后一個(gè)之外，集合中每個(gè)數(shù)據(jù)元素均只有一個(gè)后繼。第2章線性表線性表是一種最常用最簡單的線性結(jié)構(gòu)。10/14/202242.1線性表的類型定義

線性表是n個(gè)數(shù)據(jù)元素的有限序列。每個(gè)數(shù)據(jù)元素可以是一個(gè)數(shù)或一個(gè)符號(hào),也可是一頁書,甚至更復(fù)雜的信息。如,26個(gè)英文字母的字母表(A,B,C,…,Z)是一個(gè)線性表,表中的數(shù)據(jù)元素是單個(gè)字母字符。又如,某校從1978年到1983年各種型號(hào)的計(jì)算機(jī)擁有量的變化情況,可用線性表的形式給出(6,17,28,50,92,188)表中的數(shù)據(jù)元素是整數(shù)。在稍復(fù)雜的線性表中,一個(gè)數(shù)據(jù)元素可以由若干個(gè)數(shù)據(jù)項(xiàng)組成。這種情況下，把數(shù)據(jù)元素稱為記錄。含有大量記錄的線性表稱文件。10/14/20225例如,一個(gè)學(xué)校的學(xué)生健康情況登記表,表中的每個(gè)學(xué)生的情況為一個(gè)記錄,它由姓名,學(xué)號(hào),性別,年齡,班級(jí)和健康狀況等6個(gè)數(shù)據(jù)項(xiàng)組成.圖2.1學(xué)生健康狀況登記表文件記錄10/14/20226由上述例子可以看出，線性表中的數(shù)據(jù)元素可以是各種各樣的。但同一線性表中的元素具有相同特性，即屬同一數(shù)據(jù)對(duì)象，相鄰數(shù)據(jù)元素之間存在著序偶關(guān)系。將線性表記為（a1,.....

ai-1,ai,ai+1.....an），ai+1是ai直接后繼元素，ai-1是ai直接前驅(qū)元素。當(dāng)i=1,2,...,n-1時(shí),ai有且僅有一個(gè)直接后繼，當(dāng)i=2,3,...,n時(shí),ai有且僅有一個(gè)直接前驅(qū)。10/14/20227線性表中的元素個(gè)數(shù)n(n≥0)定義為線性表的長度，n=0稱為空表。在非空表中，每個(gè)數(shù)據(jù)元素都有一個(gè)確定的位置，如a1是第一個(gè)數(shù)據(jù)元素，an是最后一個(gè)數(shù)據(jù)元素，ai是第i個(gè)數(shù)據(jù)元素，稱i為ai在線性表中的位序。線性表是一個(gè)相當(dāng)靈活的數(shù)據(jù)結(jié)構(gòu)，長度可以增長或縮短，即對(duì)線性表的數(shù)據(jù)元素不僅可以進(jìn)行訪問，還可以進(jìn)行插入和刪除。10/14/20228ADTList{

數(shù)據(jù)對(duì)象：D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}稱n為線性表的長度;稱n=0時(shí)的線性表為空表。

數(shù)據(jù)關(guān)系：R1＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n}設(shè)線性表為(a1，a2,...，ai，...，an),稱i為ai在線性表中的位序。抽象數(shù)據(jù)類型線性表的定義﹕10/14/20229類型一：結(jié)構(gòu)初始化InitList(&L)

操作結(jié)果：構(gòu)造一個(gè)空的線性表L。類型二：結(jié)構(gòu)銷毀DestroyList(&L)

初始條件：線性表L已存在。操作結(jié)果：銷毀線性表L。類型三：引用型操作ListLength(L)

初始條件：線性表L已存在。

操作結(jié)果：返回L中元素個(gè)數(shù)?；静僮鳎?0/14/202210GetElem(L,i,&e)

初始條件：線性表L已存在，1≤i≤ListLength(L)

操作結(jié)果：用e返回L中第i個(gè)元素的值。LocateElem(L,e,compare())

初始條件：線性表L已存在，compare()是元素判 定函數(shù)。操作結(jié)果：返回L中第1個(gè)與e滿足關(guān)系compare() 的元素的位序。若這樣的元素不存在， 則返回值為0。ListEmpty(L)

初始條件：線性表L已存在。操作結(jié)果：若L為空表，則返回TRUE，否則返回 FALSE。10/14/202211PriorElem(L,cur_e,&pre_e)

初始條件：線性表L已存在。操作結(jié)果：若cur_e是L的數(shù)據(jù)元素，且不是第一個(gè)，則用pre_e返回它的前驅(qū)，否則操作失敗，pre_e無定義。NextElem(L,cur_e,&next_e)

初始條件：線性表L已存在。操作結(jié)果：若cur_e是L的數(shù)據(jù)元素，且不是最后一個(gè)，則用next_e返回它的后繼，否則操作失敗，next_e無定義。10/14/202212類型四：加工型操作ListInsert(&L,i,e)

初始條件：線性表L已存在，1≤i≤ListLength(L)+1

操作結(jié)果：在L的第i個(gè)位置之前插入新的元素e，L的 長度增1。

ListDelete(&L,i,&e)

初始條件：線性表L已存在且非空，1≤i≤ListLength(L)

操作結(jié)果：刪除L的第i個(gè)元素，并用e返回其值，L的 長度減1。ClearList(&L)

初始條件：線性表L已存在。操作結(jié)果：將L重置為空表。}10/14/202213例2-1假設(shè):有兩個(gè)集合A和B分別用兩個(gè)線性表LA和LB表示，即：線性表中的數(shù)據(jù)元素即為集合中的成員?，F(xiàn)要求一個(gè)新的集合A＝A∪B。利用上述定義的線性表,可以實(shí)現(xiàn)其它更復(fù)雜的操作10/14/202214上述問題可演繹為要求對(duì)線性表作如下操作：擴(kuò)大線性表LA，將存在于線性表LB中而不存在于線性表LA中的數(shù)據(jù)元素插入到線性表LA中去。10/14/2022151．從線性表LB中依次取得每個(gè)數(shù)據(jù)元素;2．依值在線性表LA中進(jìn)行查訪;3．若不存在（上述函數(shù)返回0），則插入之。GetElem(LB,i,e)

LocateElem(LA,e,equal（）)

ListInsert(LA,++LA_len,e)操作步驟：10/14/202216GetElem(Lb,i,e);//取Lb中第i個(gè)數(shù)據(jù)元素賦給eif(!LocateElem(La,e,equal()))

ListInsert(La,++La_len,e);//La中不存在和

e相同的數(shù)據(jù)元素，則插入之voidunion(List&La,ListLb){La_len=ListLength(La);

Lb_len=ListLength(Lb);//求線性表的長度for(i=1;i<=Lb_len;i++){}}//union時(shí)間復(fù)雜度

O(ListLength(LA)*ListLength(LB))10/14/202217例2-2已知線性表LA和LB中的數(shù)據(jù)元素按值非遞減有序排列，現(xiàn)要求將LA和LB歸并為一個(gè)新的線性表LC，且LC中的數(shù)據(jù)元素仍按值非遞減有序排列。若線性表中的數(shù)據(jù)元素相互之間可以比較，并且數(shù)據(jù)元素在線性表中依值非遞減或非遞增有序排列，即ai≥ai-1或ai≤ai-1(i=2,3,…,n)，則稱該線性表為有序表(OrderedList)。非遞減有序線性表舉例：LA=（3，5，8，11）；LB＝（2，6，8，9，11，15，20）LC＝？10/14/202218voidMergeList(ListLa,ListLb,List&Lc){//本算法將非遞減的有序表La和Lb歸并為Lcwhile((i<=La_len)&&(j<=Lb_len)){//La和Lb均不空GetElem(La,i,ai);GetElem(Lb,j,bj);if(ai<=bj){ListInsert(Lc,++k,ai);++i;}else{ListInsert(Lc,++k,bj);++j;}}InitList(Lc);//構(gòu)造空的線性表Lci=j=1;k=0;La_len=ListLength(La);Lb_len=ListLength(Lb);10/14/202219

while(i<=La_len){//當(dāng)La不空時(shí)

GetElem(La,i++,ai);

ListInsert(Lc,++k,ai);}//插入La表中剩余元素

while(j<=Lb_len){//當(dāng)Lb不空時(shí)

GetElem(Lb,j++,bj);

ListInsert(Lc,++k,bj);}//插入Lb表中剩余元素}//merge_list時(shí)間復(fù)雜度o(ListLength(LA)+ListLength(LB))10/14/202220

線性表的順序表示指的是用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的數(shù)據(jù)元素。an……..ai……..a2a1bb+Lb+(i-1)*Lb+（n-1)*L存儲(chǔ)地址內(nèi)存狀態(tài)圖2.2線性表的順序存儲(chǔ)結(jié)構(gòu)示意圖設(shè)每個(gè)元素需占L個(gè)存儲(chǔ)單元，以所占的第一個(gè)單元的存儲(chǔ)地址作為數(shù)據(jù)元素的存儲(chǔ)位置。2.2線性表的順序表示和實(shí)現(xiàn)10/14/202221Loc(ai)=Loc(a1)+（i-1）*L每個(gè)元素所占用的存儲(chǔ)單元個(gè)數(shù)LOC（a1）是線性表的起始地址或基地址。線性表中第i+1個(gè)數(shù)據(jù)元素的存儲(chǔ)位置Loc（ai+1）和第i個(gè)數(shù)據(jù)元素的存儲(chǔ)位置Loc（ai）之間滿足下列關(guān)系：Loc(ai+1)=Loc(ai)+L

線性表的第i個(gè)數(shù)據(jù)元素ai的存儲(chǔ)位置為：10/14/202222線性表的這種機(jī)內(nèi)表示稱作線性表的順序存儲(chǔ)結(jié)構(gòu)或順序映象，稱這種存儲(chǔ)結(jié)構(gòu)的線性表為順序表。

以元素在計(jì)算機(jī)內(nèi)的物理位置相鄰來表示線性表中數(shù)據(jù)元素之間的邏輯關(guān)系。每個(gè)數(shù)據(jù)元素的存儲(chǔ)位置都和線性表的起始位置相差一個(gè)和數(shù)據(jù)元素在線性表中的位序成正比的常數(shù)。因此，只要確定了線性表的起始位置，線性表中任一數(shù)據(jù)元素都可隨機(jī)存取，所以線性表的順序存儲(chǔ)結(jié)構(gòu)是一種隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)。10/14/202223#defineLIST_INIT_SIZE100//線性表存儲(chǔ)空間的初始分配量

#defineLISTINCREMENT10//線性表存儲(chǔ)空間的分配增量

typedefstruct{//定義一個(gè)SqList這樣的類型(結(jié)構(gòu)體類型)

ElemType*elem;//存儲(chǔ)空間基址,指示線性表基地址

intlength;//當(dāng)前長度

intlistsize;//當(dāng)前分配的存儲(chǔ)容量(以sizeof(ElemType)為單位)

}SqList;//----線性表的動(dòng)態(tài)分配順序存儲(chǔ)結(jié)構(gòu)------10/14/202224線性表的基本操作在順序表中的實(shí)現(xiàn)InitList_Sq(&L)//結(jié)構(gòu)初始化LocateElem_Sq(L,e,compare())//查找ListInsert_Sq(&L,i,e)//插入元素ListDelete_Sq(&L,i)//刪除元素10/14/202225StatusInitList_Sq(SqList&L){//構(gòu)造一個(gè)空的線性表

L.elem=(ElemType*)malloc(LIST_INIT_SIZEsizeof(ElemType));if(!L.elem)exit(OVERFLOW);L.length=0;L.listsize=LIST_INIT_SIZEreturnOK;}//InitList_Sq算法1：構(gòu)造一個(gè)空的線性表10/14/202226算法思想：檢查i值是否超出所允許的范圍（1≤i≤n+1），若超出，則進(jìn)行“超出范圍”錯(cuò)誤處理；將線性表的第i個(gè)元素和它后面的所有元素均向后移動(dòng)一個(gè)位置；將新元素寫入到空出的第i個(gè)位置上；使線性表的長度增1。算法2：在線性表中指定位置前插入一個(gè)元素插入元素時(shí)，線性表的邏輯結(jié)構(gòu)由(a1,…,ai-1,ai,…,an)改變?yōu)?a1,…,ai-1,e,ai,…,an),在第i-1個(gè)數(shù)據(jù)元素和第i個(gè)數(shù)據(jù)元素之間插入新的數(shù)據(jù)元素。10/14/202227

(a1,…,ai-1,ai,…,an)改變?yōu)?/p>

(a1,…,ai-1,e,ai,…,an)a1a2…ai-1ai

…ana1a2…ai-1

…aiean<ai-1,ai><ai-1,e>,<e,ai>表的長度增加10/14/202228圖2.3線性表插入前后的狀況(a)插入前n=8;(b)插入后n=9插入2510/14/202229StatusListInsert_Sq(SqList&L,inti,ElemTypee){//在順序線性表L的第i個(gè)元素之前插入新的元素e//i的合法值為1≤i≤Listlength_Sq(L)+1if(i<1||i>L.length+1)returnERROR;//插入位置不合法if(L.length>=L.listsize){//當(dāng)前存儲(chǔ)空間已滿，增加分配newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));在線性表中指定位置前插入一個(gè)元素10/14/202230if(!newbase)exit(OVERFLOW);//存儲(chǔ)分配失敗L.elem=newbase;//新基址L.listsize+=LISTINCREMENT;//增加存儲(chǔ)容量}q=&(L.elem[i-1]);//q指示插入位置for(p=&(L.elem[L.length-1]);p>=q;--p)*(p+1)=*p;//插入位置及之后的元素右移*q=e;//插入e++L.length;//表長增1returnOK;}//ListInsert_Sq10/14/202231

realloc可以對(duì)給定的指針?biāo)傅目臻g進(jìn)行擴(kuò)大或者縮小，無論是擴(kuò)大或是縮小，原有內(nèi)存中的內(nèi)容將保持不變。當(dāng)然，對(duì)于縮小，則被縮小的那一部分的內(nèi)容會(huì)丟失。

realloc

并不保證調(diào)整后的內(nèi)存空間和原來的內(nèi)存空間保持同一內(nèi)存地址。相反，realloc返回的指針很可能指向一個(gè)新的地址。所以，在代碼中，我們必須將realloc返回的值，重新賦值給p。10/14/2022322118307542568721183075例如：ListInsert_Sq(L,5,66)L.length-10pppq87564266q=&(L.elem[i-1]);//q指示插入位置for(p=&(L.elem[L.length-1]);p>=q;--p)*(p+1)=*p;p10/14/202233一般情況下，在第i(1≤i≤n)個(gè)元素之前插入一個(gè)元素時(shí)，需將第n至第i(共n-i+1個(gè))元素向后移動(dòng)一個(gè)位置。Pi是在第i個(gè)數(shù)據(jù)元素之前插入一個(gè)元素的概率。在長度為n的線性表中插入一個(gè)元素時(shí)所需移動(dòng)元素次數(shù)的期望值（平均次數(shù)）為插入時(shí)移動(dòng)次數(shù)的期望值（平均次數(shù)）10/14/202234算法思想:檢查i值是否超出所允許的范圍（1≤i≤n），若超出，則進(jìn)行“超出范圍”錯(cuò)誤處理；將線性表的第i個(gè)元素后面的所有元素均向前移動(dòng)一個(gè)位置；使線性表的長度減1。算法3：在線性表中刪除第i個(gè)元素

刪除元素時(shí)，線性表的邏輯結(jié)構(gòu)由(a1,…,ai-1,ai,ai+1,…,an)改變?yōu)?a1,…,ai-1,ai+1,…,an)。10/14/202235

(a1,…,ai-1,ai,ai+1,…,an)改變?yōu)?/p>

(a1,…,ai-1,ai+1,…,an)ai+1…an<ai-1,ai>,<ai,ai+1><ai-1,ai+1>表的長度減少a1a2…ai-1aiai+1…ana1a2…ai-1

10/14/202236圖2.4線性表刪除前后的情況(a)刪除前n=8;(b)刪除后n=7刪除2410/14/202237StatusListDelete_Sq(SqList&L,inti,ElemType&e){//在順序線性表L中刪除第i個(gè)元素，并用e返回其值。//i的合法值為1≤i≤ListLength_Sq(L)if((i<1)||(i>L.length))returnERROR;//刪除位置不合法在順序線性表L中刪除第i個(gè)元素10/14/202238p=&(L.elem[i-1]);//p為被刪除元素的位置e=*p;//被刪除元素的值賦給eq=L.elem+L.length-1;//表尾元素的位置for(++p;p<=q;++p)*(p-1)=*p;//被刪除元素之后的元素左移--L.length;//表長減1returnOK;}//ListDelete_Sq10/14/2022392118307542568721183075L.length-10pppq8756p=&(L.elem[i-1]);q=L.elem+L.length-1;for(++p;p<=q;++p)*(p-1)=*p;例如：ListDelete_Sq(L,5,e)

p10/14/202240一般情況下，刪除第i(1≤i≤n)個(gè)元素時(shí)，需將第i+1至第n(共n-i個(gè))元素依次向前移動(dòng)一個(gè)位置。qi是刪除第i個(gè)元素的概率。在長度為n的線性表中刪除一個(gè)元素時(shí)所需移動(dòng)元素次數(shù)的期望值（平均值）為刪除第i個(gè)元素的移動(dòng)次數(shù)的期望值（平均值）10/14/202241例如：順序表23754138546217L.elemL.lengthL.listsizee=38pppppi12341850p可見，基本操作是：將順序表中的元素逐個(gè)和給定值e相比較。算法4：在順序表中查找是否存在和e相同的數(shù)據(jù)元素

10/14/202242

intLocateElem_Sq(SqListL,ElemTypee,Status(*compare)(ElemType,ElemType)){//在順序表中查詢第一個(gè)滿足判定條件的數(shù)據(jù)元素，//若存在，則返回它的位序，否則返回0i=1;//i的初值為第1元素的位序p=L.elem;//p的初值為第1元素的存儲(chǔ)位置while(i<=L.length&&!(*compare)(*p++,e))++i;if(i<=L.length)returni;elsereturn0;}//LocateElem_Sq10/14/202243算法思想：分別從LA和LB中取得當(dāng)前元素ai和bj；若ai≤bj，則將ai插入到LC中，否則將bj插入到LC中。算法5：線性表合并已知線性表LA和LB中的數(shù)據(jù)元素按值非遞減有序排列，現(xiàn)要求將LA和LB歸并為一個(gè)新的線性表LC，求得線性表LC中的數(shù)據(jù)元素仍按值非遞減有序排列。設(shè)LA=(a1,…,ai,…,an)，LB=(b1,…,bj,…,bm)。LC=(c1,…,ck,…,cm+n)10/14/202244voidMergeList_Sq(SqList

La,SqList

Lb,SqList&Lc){//已知順序線性表La和Lb的元素按值非遞減排列//歸并La和Lb得到新的順序線性表Lc,Lc的元素也按值非遞減排列pa=La.elem;pb=Lb.elem;Lc.listsize=Lc.length=La.length+Lb.length;pc=Lc.elem=(ElemType*)malloc(Lc.listsize*sizeof(ElemType));if(!Lc.elem)exit(OVERFLOW);//存儲(chǔ)分配失敗接下頁10/14/202245pa_last=La.elem+La.length-1;pb_last=Lb.elem+Lb.length-1;while(pa<=pa_last&&pb<=pb_last){//歸并if(*pa<=*pb)*pc++=*pa++;else*pc++=*pb++;}while(pa<=pa_last)*pc++=*pa++;//插入La的剩余元素while(pb<=pb_last)*pc++=*pb++;//插入Lb的剩余元素}//MergeList_Sq10/14/202246作業(yè)：設(shè)順序表va中的數(shù)據(jù)元素遞增有序，試寫一算法，將x插入到順序表的適當(dāng)位置上，以保持該表的有序性。順序表結(jié)構(gòu)的定義遵從教材P22“線性表動(dòng)態(tài)分配存儲(chǔ)結(jié)構(gòu)”10/14/2022472.3線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)

線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)特點(diǎn)：用一組任意的存儲(chǔ)單元(可以是連續(xù)的,也可以是不連續(xù)的)存放線性表的數(shù)據(jù)元素。10/14/202248為了表示每個(gè)數(shù)據(jù)元素與其直接后繼之間的邏輯關(guān)系，對(duì)數(shù)據(jù)元素ai來說,除了存儲(chǔ)其本身的信息之外，還需存儲(chǔ)一個(gè)指示其直接后繼的信息(即直接后繼的存儲(chǔ)位置)。這兩部分信息組成數(shù)據(jù)元素ai的存儲(chǔ)映象，稱為結(jié)點(diǎn)。它含有兩個(gè)域：存儲(chǔ)數(shù)據(jù)元素信息的域稱為數(shù)據(jù)域。存儲(chǔ)直接后繼存儲(chǔ)位置的域稱為指針域。指針域中存儲(chǔ)的信息稱作指針或鏈。數(shù)據(jù)域指針域結(jié)點(diǎn)2.3.1線性鏈表10/14/202249

n個(gè)結(jié)點(diǎn)鏈成一個(gè)鏈表，即為線性表（a1,a2,…,an）的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。由于鏈表的每個(gè)結(jié)點(diǎn)中只包含一個(gè)指針域，又稱線性鏈表或單鏈表。整個(gè)鏈表的存取需從頭指針開始進(jìn)行，頭指針指示鏈表中第一個(gè)結(jié)點(diǎn)（即第一個(gè)數(shù)據(jù)元素的存儲(chǔ)映象）的存儲(chǔ)位置。由于最后一個(gè)數(shù)據(jù)元素沒有直接后繼，則線性表中最后一個(gè)結(jié)點(diǎn)的指針為空(NULL)。

指針為數(shù)據(jù)之間邏輯關(guān)系的映像，則邏輯上相鄰的兩個(gè)數(shù)據(jù)元素其存儲(chǔ)的物理位置不要求緊鄰，這種存儲(chǔ)結(jié)構(gòu)為非順序映像或鏈?zhǔn)接诚瘛?0/14/202250typedefstruct

LNode{

ElemTypedata；

struct

Lnode*next；}LNode，*LinkList；線性表的單鏈表存儲(chǔ)結(jié)構(gòu)10/14/202251假設(shè)p是指向第i個(gè)元素ai的指針，則p→next是指向第i+1個(gè)數(shù)據(jù)元素ai+1的指針。若p→data=ai則p→next→data=ai+1下圖為(ZHAO，QIAN，SUN，LI，ZHOU，WU，ZHENG，WANG)線性表的線性鏈表存儲(chǔ)結(jié)構(gòu)，存儲(chǔ)從頭指針開始進(jìn)行。10/14/20225243131NULL3771925數(shù)據(jù)域指針域LIQIANSUNWANGWUZHAOZHENGZHOU存儲(chǔ)地址1713192531374331HZHAOQIANSUNLIZHOUWUZHENGWANG^H圖2.6線性鏈表的邏輯狀態(tài)圖2.5線性鏈表示例頭指針空指針10/14/202253a1a2an∧圖2.7帶頭結(jié)點(diǎn)的單鏈表L(a)非空表(b)空表在單鏈表的第一個(gè)結(jié)點(diǎn)之前附設(shè)一個(gè)結(jié)點(diǎn)，稱之為頭結(jié)點(diǎn)。頭結(jié)點(diǎn)的數(shù)據(jù)域可以不存儲(chǔ)任何信息，也可存儲(chǔ)如線性表的長度等類的附加信息，頭結(jié)點(diǎn)的指針域存儲(chǔ)指向第一個(gè)結(jié)點(diǎn)的指針。單鏈表的頭指針指向頭結(jié)點(diǎn)。若線性表為空表，則頭結(jié)點(diǎn)的指針域?yàn)榭?。L10/14/202254單鏈表操作的實(shí)現(xiàn)GetElem_L(L,i,&e)//取第i個(gè)數(shù)據(jù)元素ListInsert_L(&L,i,e)//插入數(shù)據(jù)元素ListDelete_L(&L,i,&e)//刪除數(shù)據(jù)元素CreateList_L(&L,n)

//生成含n個(gè)數(shù)據(jù)元素的鏈表10/14/202255L線性表的操作GetElem_L(L,3,&e)在單鏈表中的實(shí)現(xiàn):211830754256∧pppj12310/14/202256單鏈表是一種順序存取的結(jié)構(gòu)，為找第i個(gè)數(shù)據(jù)元素，必須先找到第i-1個(gè)數(shù)據(jù)元素。因此，查找第i個(gè)數(shù)據(jù)元素的基本操作為：移動(dòng)指針，比較j和i。令指針p始終指向線性表中第j個(gè)數(shù)據(jù)元素。

10/14/202257

StatusGetElem_L(LinkListL,inti,ElemType&e){//L是帶頭結(jié)點(diǎn)的鏈表的頭指針，以e返回第

i個(gè)元素p=L->next;j=1;//p指向第一個(gè)結(jié)點(diǎn)，j為計(jì)數(shù)器while(p&&j<i){p=p->next;++j;}//順指針向后查找，直到p指向第i個(gè)元素或p為空if(!p||j>i) returnERROR;//第i個(gè)元素不存在e=p->data;//取得第i個(gè)元素returnOK;}//GetElem_L算法時(shí)間復(fù)雜度為:O(ListLength(L))10/14/202258ai-1

線性表的操作ListInsert(&L,i,e)

在單鏈表中的實(shí)現(xiàn)：有序?qū)?lt;ai-1,ai>

改變?yōu)?lt;ai-1,e>和<e,ai>eaiai-110/14/202259因此，在單鏈表中第i個(gè)結(jié)點(diǎn)之前進(jìn)行插入的基本操作為:找到線性表中第i-1個(gè)結(jié)點(diǎn)，然后修改其指向后繼的指針?？梢?，在鏈表中插入結(jié)點(diǎn)只需要修改指針。但同時(shí)，若要在第i個(gè)結(jié)點(diǎn)之前插入元素，修改的是第i-1個(gè)結(jié)點(diǎn)的指針。10/14/202260StatusListInsert_L(LinkListL,inti,ElemTypee){//L為帶頭結(jié)點(diǎn)的單鏈表的頭指針，本算法

//在鏈表中第i個(gè)結(jié)點(diǎn)之前插入新的元素ep=L;j=0;while(p&&j<i-1){p=p->next;++j;}//尋找第i-1個(gè)結(jié)點(diǎn)if(!p||j>i-1)returnERROR;//i大于表長或者小于1算法的時(shí)間復(fù)雜度為:O(ListLength(L))……}//LinstInsert_L10/14/202261s=(LinkList)malloc(sizeof(LNode));

//生成新結(jié)點(diǎn)s->data=e;s->next=p->next;p->next=s;//插入returnOK;eai-1aiai-1sp10/14/202262線性表的操作ListDelete_L(&L,i,&e)在鏈表中的實(shí)現(xiàn):有序?qū)?lt;ai-1,ai>和<ai,ai+1>

改變?yōu)?lt;ai-1,ai+1>ai-1aiai+1ai-110/14/202263在單鏈表中刪除第i個(gè)結(jié)點(diǎn)的基本操作為:找到線性表中第i-1個(gè)結(jié)點(diǎn)，修改其指向后繼的指針。ai-1aiai+1ai-1q=p->next;p->next=q->next;e=q->data;free(q);pq10/14/202264

StatusListDelete_L(LinkListL,inti,ElemType&e){//刪除以L為頭指針(帶頭結(jié)點(diǎn))的單鏈表中第i個(gè)結(jié)點(diǎn)p=L;j=0;while(p->next&&j<i-1)//尋找第i個(gè)結(jié)點(diǎn)，并令p指向其前驅(qū){p=p->next;++j;}if(!(p->next)||j>i-1)returnERROR;//刪除位置不合理q=p->next;p->next=q->next;//刪除并釋放結(jié)點(diǎn)e=q->data;free(q);returnOK;}//ListDelete_L算法的時(shí)間復(fù)雜度為:O(ListLength(L))10/14/202265如何從線性表得到單鏈表？ 鏈表是一個(gè)動(dòng)態(tài)結(jié)構(gòu)。整個(gè)可用存儲(chǔ)空間可為多個(gè)鏈表共用，每個(gè)鏈表占用的空間不需預(yù)先分配劃定，可由系統(tǒng)應(yīng)需求即時(shí)生成。因此生成鏈表的過程是一個(gè)結(jié)點(diǎn)“逐個(gè)插入”的過程。10/14/202266例如：逆位序輸入n個(gè)數(shù)據(jù)元素的值，建立帶頭結(jié)點(diǎn)的單鏈表。操作步驟：一、建立一個(gè)“空表”；二、輸入數(shù)據(jù)元素an，建立結(jié)點(diǎn)并插入；三、輸入數(shù)據(jù)元素an-1，建立結(jié)點(diǎn)并插入；ananan-1四、依次類推，直至輸入a1為止。創(chuàng)建帶頭結(jié)點(diǎn)的單鏈線性表

10/14/202267voidCreateList_L(LinkList&L,intn){//逆序輸入n個(gè)數(shù)據(jù)元素，建立帶頭結(jié)點(diǎn)的單鏈表L=(LinkList)malloc(sizeof(LNode));L->next=NULL;//先建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表for(i=n;i>0;--i){p=(LinkList)malloc(sizeof(LNode));

scanf(&p->data);//輸入元素值

p->next=L->next;L->next=p;//插入到表頭}}//CreateList_L算法的時(shí)間復(fù)雜度為:O(Listlength(L))10/14/202268線性表合并將兩個(gè)有序鏈表合并為一個(gè)有序鏈表。設(shè)立三個(gè)指針pa、pb和pc分別用來指向兩個(gè)有序鏈表和合并表的當(dāng)前元素。比較兩個(gè)表的當(dāng)前元素的大小，將小的元素鏈接到pc所指結(jié)點(diǎn)之后，即，讓pc指向該元素，然后，修改指針。在歸并兩個(gè)鏈表為一個(gè)鏈表時(shí)，不需要另建新表的結(jié)點(diǎn)空間，而只需將原來兩個(gè)鏈表中結(jié)點(diǎn)之間的關(guān)系解除，重新建立關(guān)系。10/14/202269VoidMergeList_L(LinkList&La,LinkList&Lb,LinkList&Lc){//已知單鏈線性表La和Lb的元素按值非遞減排列//歸并La和Lb得到新的單鏈線性表Lc,Lc的元素也按值非遞減排列pa=La->next;pb=Lb->next;Lc=pc=La;//用La的頭結(jié)點(diǎn)作為Lc的頭結(jié)點(diǎn)While(pa&&pb){if(pa->data<=pb->data){pc->next=pa;pc=pa;pa=pa->next;}else{pc->next=pb;pc=pb;pb=pb->next;}}pc->next=pa?pa:pb;//插入剩余段free(Lb);//釋放Lb的頭結(jié)點(diǎn)}//MergeList_L條件賦值變量名＝條件表達(dá)式？表達(dá)式T：表達(dá)式F；

if(pa)

pc->next

=

pa;

else

pc->next

=

pb;10/14/202270

25

38LaLbpapbLcpcpa=La->next;pb=Lb->next;Lc=pc=La;10/14/202271

25

38LaLbpapbLcpcWhile(pa&&pb){if(pa->data<=pb->data){pc->next=pa;pc=pa;pa=pa->next;}else{pc->next=pb;pc=pb;pb=pb->next;}}10/14/202272

25

38LaLbpapbLcpcWhile(pa&&pb){if(pa->data<=pb->data){pc->next=pa;pc=pa;pa=pa->next;}else{pc->next=pb;pc=pb;pb=pb->next;}}10/14/202273

25

38LaLbpbLcpcWhile(pa&&pb){if(pa->data<=pb->data){pc->next=pa;pc=pa;pa=pa->next;}else{pc->next=pb;pc=pb;pb=pb->next;}}pa=null10/14/202274

25

38LaLbpbLcpcpc->next=pa?pa:pb;free(Lb);10/14/202275 用上述定義的單鏈表實(shí)現(xiàn)線性表的操作時(shí)，存在的問題：1．單鏈表的表長是一個(gè)隱含的值；2．在單鏈表的最后一個(gè)元素之后插入元素時(shí)，需遍歷整個(gè)鏈表；10/14/202276a1a2…...an和單鏈表的差別僅在于，判別鏈表中最后一個(gè)結(jié)點(diǎn)的條件不再是“后繼是否為空”，而是“后繼是否為頭結(jié)點(diǎn)”。循環(huán)單鏈表特點(diǎn)：最后一個(gè)結(jié)點(diǎn)的指針域指向頭結(jié)點(diǎn)，整個(gè)鏈表形成一個(gè)環(huán)。由此，從表中任一結(jié)點(diǎn)出發(fā)均可找到其它結(jié)點(diǎn)?？毡?.3.2循環(huán)鏈表10/14/202277在每個(gè)結(jié)點(diǎn)中有兩個(gè)指針域，一個(gè)指向直接后繼，一個(gè)指向直接前驅(qū)。typedefstruct

DuLNode{ElemTypedata;struct

DuLNode*prior;struct

DuLNode*next;}DuLNode,*DuLinkList;線性表的雙向鏈表存儲(chǔ)結(jié)構(gòu)2.3.3雙向鏈表10/14/202278雙向循環(huán)鏈表空表非空表a1a2…...an雙向鏈表有循環(huán)表，鏈表中有兩個(gè)環(huán)，在雙向鏈表中，若d為指向表中某一結(jié)點(diǎn)的指針（即d為DuLinkList型變量），則顯然有d->next->prior=d->prior->next=d10/14/202279雙向鏈表的操作特點(diǎn)：“查詢”和單鏈表相同?！安迦搿焙汀皠h除”時(shí)需要同時(shí)修改兩個(gè)方向上的指針。10/14/202280ai-1aies->next=p->next;p->next=s;s->next->prior=s;s->prior=p;psai-1ai插入10/14/202281ai-1刪除aiai+1p->next=p->next->next;p->next->prior=p;pai-110/14/202282一個(gè)帶頭結(jié)點(diǎn)的線性鏈表類型typedefstruct

LNode{//結(jié)點(diǎn)類型

ElemTypedata;

struct

LNode*next;}*Link,*Position;typedef

struct{//鏈表類型

Linkhead,tail;

//分別指向頭結(jié)點(diǎn)和最后一個(gè)結(jié)點(diǎn)的指針

int

len;//指示鏈表長度

}LinkList;10/14/202283StatusMakeNode(Link&p,ElemTypee);//分配由p指向的值為e的結(jié)點(diǎn)，并返回OK，若分配失敗，則返回ERRORvoidFreeNode(Link&p);

//釋放p

所指結(jié)點(diǎn)鏈表的基本操作:10/14/202284StatusInitList(LinkList&L);

//構(gòu)造一個(gè)空的線性鏈表LStatusDestroyList(LinkList&L);

//銷毀線性鏈表L，L不再存在。10/14/202285StatusAppend(LinkList&L,Links);

//將指針s所指的一串結(jié)點(diǎn)鏈接在線性鏈表L的最后一個(gè)結(jié)點(diǎn)StatusInsFirst(Linkh,Links);

//h指向頭結(jié)點(diǎn)，將s所指結(jié)點(diǎn)插入在第一個(gè)結(jié)點(diǎn)之前StatusDelFirst(Linkh,Link&q);

//h指向頭結(jié)點(diǎn)，刪除第一個(gè)結(jié)點(diǎn)并以q返回10/14/202286StatusNextPos(LinkListL,Linkp);//p指向一個(gè)結(jié)點(diǎn)，返回p所指結(jié)點(diǎn)的直接后繼的位置，若無后繼，則返回NULLStatus

SetCurElem(Link

&p,ElemTypee);//p指向一個(gè)結(jié)點(diǎn)，用e更新p所指結(jié)點(diǎn)中數(shù)據(jù)元素的值ElemType

GetCurElem(Linkp);//p指向一個(gè)結(jié)點(diǎn)，返回p所指結(jié)點(diǎn)中數(shù)據(jù)元素的值PositionGetHead(LinkListL);//返回線性鏈表L中頭結(jié)點(diǎn)的位置

StatusLocatePos(LinkListL,inti,Link&p);//返回p指示線性鏈表L中第i個(gè)結(jié)點(diǎn)的位置并返回OK，i值不合法時(shí)返回ERROR。10/14/202287StatusListInsert_L(LinkListL,inti,ElemTypee){//在帶頭結(jié)點(diǎn)的單鏈線性表L的第i個(gè)元素之前插入元素e}//ListInsert_L

利用上述定義的線性鏈表如何完成線性表的其它操作？if(!LocatePos(L,i-1,h))returnERROR;//i值不合法。//LocatePos(L,i-1,h)中h指示第i-1個(gè)結(jié)點(diǎn)的位置，并返回OK,不合法時(shí)返回ERROR。if(!MakeNode(s,e))returnERROR;//結(jié)點(diǎn)存儲(chǔ)分配失敗InsFirst(h,s);//對(duì)于從第i個(gè)結(jié)點(diǎn)開始的鏈表，第i-1個(gè)結(jié)點(diǎn)是它的頭結(jié)點(diǎn)。h指向頭結(jié)點(diǎn)，s所指結(jié)點(diǎn)插入在第一個(gè)結(jié)點(diǎn)之前returnOK;例110/14/202288StatusMergeList_L(LinkList&La,LinkList&Lb,LinkList&Lc,int(*compare)(ElemType,ElemType)){//已知單鏈線性表La和Lb的元素按值非遞減排列。//歸并La和Lb得到新的單鏈線性表Lc,Lc的元素也按值非遞減排列。If(!InitList(Lc))returnERROR;//存儲(chǔ)空間分配失敗ha=GetHead(La);hb=GetHead(Lb);//ha和hb分別指向La和Lb的頭結(jié)點(diǎn)pa=NextPos(La,ha);pb=NextPos(Lb,hb);//pa和pb分別指向La和Lb中當(dāng)前結(jié)點(diǎn)，返回直接后繼while(pa&&pb){//La和Lb均非空a=GetCurElem(pa);b=GetCurElem(pb);//a和b為兩表中當(dāng)前比較元素例2接下頁…10/14/202289if((*compare)(a,b)<=0){//a<=bDelFirst(ha,q);Append(Lc,q);//ha是頭指針pa=NextPos(La,pa);}//返回pa所指結(jié)點(diǎn)直接后繼Else{DelFirst(hb,q);Append(Lc,q);//hb是頭指針pb=NextPos(Lb,pb);}//返回pb所指結(jié)點(diǎn)直接后繼}if(pa)Append(Lc,pa);//鏈接La中剩余結(jié)點(diǎn)elseAppend(Lc,pb);//鏈接Lb中剩余結(jié)點(diǎn)FreeNode(ha);FreeNode(hb);//釋放La和Lb的頭結(jié)點(diǎn)ReturnOK;}//MergeList_L10/14/202290在計(jì)算機(jī)中，可以用一個(gè)線性表來表示:P=(p0,p1,…，pn)一元多項(xiàng)式2.4一元多項(xiàng)式的表示10/14/202291但是對(duì)于形如

S(x)=1+3x10000–2x20000的多項(xiàng)式，上述表示方法是否合適？10/14/202292一般情況下的一元n次多項(xiàng)式可寫成

Pn(x)=p1xe1+p2xe2+…+pmxem其中：pi

是指數(shù)為ei

的項(xiàng)的非零系數(shù)，

0≤e1<e2<…<em=n可以用下列線性表表示：（（p1,e1）,(p2,e2),…,(pm,em)）10/14/202293P999(x)=7x3-2x12-8x999例如:可用線性表

((7,3),(-2,12),(-8,999))表示10/14/202294ADTPolynomial{

數(shù)據(jù)對(duì)象：

數(shù)據(jù)關(guān)系：抽象數(shù)據(jù)類型一元多項(xiàng)式的定義如下：D＝{ai|ai∈TermSet,i=1,2,...,m,m≥0

TermSet

中的每個(gè)元素包含一個(gè)表示系數(shù)的實(shí)數(shù)和表示指數(shù)的整數(shù)}R1＝{<ai-1,ai>|ai-1,ai∈D,且ai-1中的指數(shù)值＜ai中的指數(shù)值i=2,...,n}10/14/202295CreatPolyn(&P,m)DestroyPolyn(&P)

PrintPolyn(&P)基本操作：操作結(jié)果：輸入

m項(xiàng)的系數(shù)和指數(shù)，建立一元多項(xiàng)式

P。初始條件：一元多項(xiàng)式P已存在。操作結(jié)果：銷毀一元多項(xiàng)式P。初始條件：一元多項(xiàng)式P已存在。操作結(jié)果：打印輸出一元多項(xiàng)式P。10/14/202296PolynLength(P)

AddPolyn(&Pa,&Pb)SubtractPolyn(&Pa,&Pb)……MultiplyPolyn(&Pa,&Pb)……}ADTPolynomial初始條件：一元多項(xiàng)式P已存在。操作結(jié)果：返回一元多項(xiàng)式P中的項(xiàng)數(shù)。初始條件：一元多項(xiàng)式Pa和Pb已存在。操作結(jié)果：完成多項(xiàng)式相加運(yùn)算，即：

Pa=Pa＋Pb，并銷毀一元多項(xiàng)式Pb。10/14/202297抽象數(shù)據(jù)類型一元多項(xiàng)式的實(shí)現(xiàn)：typedefstruct{//項(xiàng)的表示,多項(xiàng)式的項(xiàng)作為LinkList的數(shù)據(jù)元素

floatcoef;//系數(shù)

intexpn;//指數(shù)}term,ElemType;//兩個(gè)類型名：term用于本ADT,ElemType為LinkList的數(shù)據(jù)對(duì)象名10/14/202298typedefstruct

LNode{

ElemTypedata；

struct

Lnode*next；}LNode，*LinkList；線性表的單鏈表存儲(chǔ)結(jié)構(gòu)typedefLinkListpolynomial;//用帶表頭結(jié)點(diǎn)的有序鏈表表示多項(xiàng)式10/14/202299-1A703198517^-1B81227-98^-1C70111227517^A(x)=7+3x+9x8+5x1710/14/2022100 核心算法AddPolyn是把分別由pa和pb所指的兩個(gè)多項(xiàng)式相加，結(jié)果為pa所指的多項(xiàng)式。相加時(shí)，首先設(shè)兩個(gè)指針變量qa和qb分別從多項(xiàng)式的首項(xiàng)開始掃描，比較qa和qb所指結(jié)點(diǎn)指數(shù)域的值，可能出現(xiàn)下列三種情況之一：（1）qa->exp大于qb->exp,摘取qb指針?biāo)附Y(jié)點(diǎn)插入到“和多項(xiàng)式”鏈表中去（2）qa->exp小于qb->exp,摘取qa指針?biāo)附Y(jié)點(diǎn)插入到“和多項(xiàng)式”鏈表中去。10/14/2022101

掃描過程一直進(jìn)行到qa或qb有一個(gè)為空為止，然后將有剩余結(jié)點(diǎn)的鏈表接在結(jié)果鏈表上。所得pa指向的鏈表即為兩個(gè)多項(xiàng)式之和。（3）qa->exp等于qb->exp,則將其系數(shù)相加。若相加結(jié)果不為零，修改qa所指結(jié)點(diǎn)的系數(shù)值，并釋放qb所指結(jié)點(diǎn)。否則同時(shí)釋放qa和qb所指結(jié)點(diǎn)。然后qa、qb繼續(xù)向后掃描。10/14/2022102VoidCreatPolyn(polynomail&P,intm){

//輸入m項(xiàng)的系數(shù)和指數(shù)，建立表示一元多項(xiàng)式的有序鏈表PInitList(P);h=GetHead(P);e.coef=0.0;e.expn=-1;SetCurElem(h,e);//設(shè)置頭結(jié)點(diǎn)的數(shù)據(jù)元素for(i=1;i<=m;++i){//依次輸入m個(gè)非零項(xiàng)scanf(e.coef,e.expn);if(!LocateElem(P,e,q,(*cmp)())){//當(dāng)前鏈表中不存在該指數(shù)項(xiàng)

if(MakeNode(s,e))InsFirst(q,s);}//生成結(jié)點(diǎn)并插入

}}//CreatPolyn10/14/2022103VoidAddPolyn(polynomial&Pa,polynomial&Pb){ha=GetHead(Pa);hb=GetHead(Pb);qa=NextPos(Pa,ha)