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

1．數(shù)據(jù)的邏輯結(jié)構(gòu)

2、數(shù)據(jù)的存儲結(jié)構(gòu)A．線性結(jié)構(gòu)B．非線性結(jié)構(gòu)A順序存儲B鏈式存儲線性表棧隊列樹圖數(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)。

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

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

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

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

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

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

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

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

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

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

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

初始條件：線性表L已存在，compare()是元素判 定函數(shù)。操作結(jié)果：返回L中第1個與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ù)元素，且不是第一個，則用pre_e返回它的前驅(qū)，否則操作失敗，pre_e無定義。NextElem(L,cur_e,&next_e)

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

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

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

ListDelete(&L,i,&e)

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

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

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

LocateElem(LA,e,equal（）)

ListInsert(LA,++LA_len,e)操作步驟：10/14/202216GetElem(Lb,i,e);//取Lb中第i個數(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時間復雜度

O(ListLength(LA)*ListLength(LB))10/14/202217例2-2已知線性表LA和LB中的數(shù)據(jù)元素按值非遞減有序排列，現(xiàn)要求將LA和LB歸并為一個新的線性表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){//當La不空時

GetElem(La,i++,ai);

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

while(j<=Lb_len){//當Lb不空時

GetElem(Lb,j++,bj);

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

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

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

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

#defineLISTINCREMENT10//線性表存儲空間的分配增量

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

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

intlength;//當前長度

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

}SqList;//----線性表的動態(tài)分配順序存儲結(jié)構(gòu)------10/14/202224線性表的基本操作在順序表中的實現(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)造一個空的線性表

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)造一個空的線性表10/14/202226算法思想：檢查i值是否超出所允許的范圍（1≤i≤n+1），若超出，則進行“超出范圍”錯誤處理；將線性表的第i個元素和它后面的所有元素均向后移動一個位置；將新元素寫入到空出的第i個位置上；使線性表的長度增1。算法2：在線性表中指定位置前插入一個元素插入元素時，線性表的邏輯結(jié)構(gòu)由(a1,…,ai-1,ai,…,an)改變?yōu)?a1,…,ai-1,e,ai,…,an),在第i-1個數(shù)據(jù)元素和第i個數(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個元素之前插入新的元素e//i的合法值為1≤i≤Listlength_Sq(L)+1if(i<1||i>L.length+1)returnERROR;//插入位置不合法if(L.length>=L.listsize){//當前存儲空間已滿，增加分配newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));在線性表中指定位置前插入一個元素10/14/202230if(!newbase)exit(OVERFLOW);//存儲分配失敗L.elem=newbase;//新基址L.listsize+=LISTINCREMENT;//增加存儲容量}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可以對給定的指針所指的空間進行擴大或者縮小，無論是擴大或是縮小，原有內(nèi)存中的內(nèi)容將保持不變。當然，對于縮小，則被縮小的那一部分的內(nèi)容會丟失。

realloc

并不保證調(diào)整后的內(nèi)存空間和原來的內(nèi)存空間保持同一內(nèi)存地址。相反，realloc返回的指針很可能指向一個新的地址。所以，在代碼中，我們必須將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)個元素之前插入一個元素時，需將第n至第i(共n-i+1個)元素向后移動一個位置。Pi是在第i個數(shù)據(jù)元素之前插入一個元素的概率。在長度為n的線性表中插入一個元素時所需移動元素次數(shù)的期望值（平均次數(shù)）為插入時移動次數(shù)的期望值（平均次數(shù)）10/14/202234算法思想:檢查i值是否超出所允許的范圍（1≤i≤n），若超出，則進行“超出范圍”錯誤處理；將線性表的第i個元素后面的所有元素均向前移動一個位置；使線性表的長度減1。算法3：在線性表中刪除第i個元素

刪除元素時，線性表的邏輯結(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個元素，并用e返回其值。//i的合法值為1≤i≤ListLength_Sq(L)if((i<1)||(i>L.length))returnERROR;//刪除位置不合法在順序線性表L中刪除第i個元素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)個元素時，需將第i+1至第n(共n-i個)元素依次向前移動一個位置。qi是刪除第i個元素的概率。在長度為n的線性表中刪除一個元素時所需移動元素次數(shù)的期望值（平均值）為刪除第i個元素的移動次數(shù)的期望值（平均值）10/14/202241例如：順序表23754138546217L.elemL.lengthL.listsizee=38pppppi12341850p可見，基本操作是：將順序表中的元素逐個和給定值e相比較。算法4：在順序表中查找是否存在和e相同的數(shù)據(jù)元素

10/14/202242

intLocateElem_Sq(SqListL,ElemTypee,Status(*compare)(ElemType,ElemType)){//在順序表中查詢第一個滿足判定條件的數(shù)據(jù)元素，//若存在，則返回它的位序，否則返回0i=1;//i的初值為第1元素的位序p=L.elem;//p的初值為第1元素的存儲位置while(i<=L.length&&!(*compare)(*p++,e))++i;if(i<=L.length)returni;elsereturn0;}//LocateElem_Sq10/14/202243算法思想：分別從LA和LB中取得當前元素ai和bj；若ai≤bj，則將ai插入到LC中，否則將bj插入到LC中。算法5：線性表合并已知線性表LA和LB中的數(shù)據(jù)元素按值非遞減有序排列，現(xiàn)要求將LA和LB歸并為一個新的線性表LC，求得線性表LC中的數(shù)據(jù)元素仍按值非遞減有序排列。設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);//存儲分配失敗接下頁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è)：設順序表va中的數(shù)據(jù)元素遞增有序，試寫一算法，將x插入到順序表的適當位置上，以保持該表的有序性。順序表結(jié)構(gòu)的定義遵從教材P22“線性表動態(tài)分配存儲結(jié)構(gòu)”10/14/2022472.3線性表的鏈式表示和實現(xiàn)

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

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

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

LNode{

ElemTypedata；

struct

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

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

10/14/202257

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

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

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

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

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

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

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

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

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

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

p->next=L->next;L->next=p;//插入到表頭}}//CreateList_L算法的時間復雜度為:O(Listlength(L))10/14/202268線性表合并將兩個有序鏈表合并為一個有序鏈表。設立三個指針pa、pb和pc分別用來指向兩個有序鏈表和合并表的當前元素。比較兩個表的當前元素的大小，將小的元素鏈接到pc所指結(jié)點之后，即，讓pc指向該元素，然后，修改指針。在歸并兩個鏈表為一個鏈表時，不需要另建新表的結(jié)點空間，而只需將原來兩個鏈表中結(jié)點之間的關(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é)點作為Lc的頭結(jié)點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é)點}//MergeList_L條件賦值變量名＝條件表達式？表達式T：表達式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 用上述定義的單鏈表實現(xiàn)線性表的操作時，存在的問題：1．單鏈表的表長是一個隱含的值；2．在單鏈表的最后一個元素之后插入元素時，需遍歷整個鏈表；10/14/202276a1a2…...an和單鏈表的差別僅在于，判別鏈表中最后一個結(jié)點的條件不再是“后繼是否為空”，而是“后繼是否為頭結(jié)點”。循環(huán)單鏈表特點：最后一個結(jié)點的指針域指向頭結(jié)點，整個鏈表形成一個環(huán)。由此，從表中任一結(jié)點出發(fā)均可找到其它結(jié)點?？毡?.3.2循環(huán)鏈表10/14/202277在每個結(jié)點中有兩個指針域，一個指向直接后繼，一個指向直接前驅(qū)。typedefstruct

DuLNode{ElemTypedata;struct

DuLNode*prior;struct

DuLNode*next;}DuLNode,*DuLinkList;線性表的雙向鏈表存儲結(jié)構(gòu)2.3.3雙向鏈表10/14/202278雙向循環(huán)鏈表空表非空表a1a2…...an雙向鏈表有循環(huán)表，鏈表中有兩個環(huán)，在雙向鏈表中，若d為指向表中某一結(jié)點的指針（即d為DuLinkList型變量），則顯然有d->next->prior=d->prior->next=d10/14/202279雙向鏈表的操作特點：“查詢”和單鏈表相同。“插入”和“刪除”時需要同時修改兩個方向上的指針。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一個帶頭結(jié)點的線性鏈表類型typedefstruct

LNode{//結(jié)點類型

ElemTypedata;

struct

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

struct{//鏈表類型

Linkhead,tail;

//分別指向頭結(jié)點和最后一個結(jié)點的指針

int

len;//指示鏈表長度

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

//釋放p

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

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

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

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

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

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

SetCurElem(Link

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

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

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

利用上述定義的線性鏈表如何完成線性表的其它操作？if(!LocatePos(L,i-1,h))returnERROR;//i值不合法。//LocatePos(L,i-1,h)中h指示第i-1個結(jié)點的位置，并返回OK,不合法時返回ERROR。if(!MakeNode(s,e))returnERROR;//結(jié)點存儲分配失敗InsFirst(h,s);//對于從第i個結(jié)點開始的鏈表，第i-1個結(jié)點是它的頭結(jié)點。h指向頭結(jié)點，s所指結(jié)點插入在第一個結(jié)點之前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;//存儲空間分配失敗ha=GetHead(La);hb=GetHead(Lb);//ha和hb分別指向La和Lb的頭結(jié)點pa=NextPos(La,ha);pb=NextPos(Lb,hb);//pa和pb分別指向La和Lb中當前結(jié)點，返回直接后繼while(pa&&pb){//La和Lb均非空a=GetCurElem(pa);b=GetCurElem(pb);//a和b為兩表中當前比較元素例2接下頁…10/14/202289if((*compare)(a,b)<=0){//a<=bDelFirst(ha,q);Append(Lc,q);//ha是頭指針pa=NextPos(La,pa);}//返回pa所指結(jié)點直接后繼Else{DelFirst(hb,q);Append(Lc,q);//hb是頭指針pb=NextPos(Lb,pb);}//返回pb所指結(jié)點直接后繼}if(pa)Append(Lc,pa);//鏈接La中剩余結(jié)點elseAppend(Lc,pb);//鏈接Lb中剩余結(jié)點FreeNode(ha);FreeNode(hb);//釋放La和Lb的頭結(jié)點ReturnOK;}//MergeList_L10/14/202290在計算機中，可以用一個線性表來表示:P=(p0,p1,…，pn)一元多項式2.4一元多項式的表示10/14/202291但是對于形如

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

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

是指數(shù)為ei

的項的非零系數(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ù)對象：

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

TermSet

中的每個元素包含一個表示系數(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項的系數(shù)和指數(shù)，建立一元多項式

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

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

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

floatcoef;//系數(shù)

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

LNode{

ElemTypedata；

struct

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

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

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

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

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