第二章-線性表

第二章線性表2.1線性表的類型定義2.2線性表的順序表示和實現(xiàn)2.3線性表的鏈?zhǔn)奖硎竞蛯崿F(xiàn)

2.3.1線性鏈表

2.3.2循環(huán)鏈表

2.3.3雙向鏈表2.4一元多項式的表示及相加第二章線性表重點：理解線性表的邏輯結(jié)構(gòu)特性熟練掌握線性表的順序存儲結(jié)構(gòu)的描述方法，以及在該存儲結(jié)構(gòu)下的基本操作熟練掌握線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)的描述方法，靈活使用單鏈表、雙鏈表、循環(huán)鏈表，學(xué)會在相應(yīng)存儲結(jié)構(gòu)下實現(xiàn)其各種基本算法及相關(guān)的時間性能分析一元多項式的表示和相加第二章線性表難點：能夠從時間和空間復(fù)雜度的角度綜合比較線性表兩種存儲結(jié)構(gòu)的不同特點及其應(yīng)用場合使用本章所學(xué)的基本知識設(shè)計有效算法，解決與線性表相關(guān)的應(yīng)用問題第二章線性表線性結(jié)構(gòu)的特點：在數(shù)據(jù)元素的非空有限集中，1）存在唯一的一個被稱為“第一個”的數(shù)據(jù)元素2）存在唯一的一個被稱為“最后一個”的數(shù)據(jù)元素3）除第一個之外，集合中的每個數(shù)據(jù)元素均只有一個前驅(qū)4）除最后一個之外，集合中的每個數(shù)據(jù)元素均只有一個后繼1.線性表：定義：簡稱為表，是零個或多個元素的有窮序列，通?？梢员硎境?a1,a2,…,an)(n

0)表的長度：表中所含元素的個數(shù)

n空表：長度為零的表表項：表中的元素ai位序：數(shù)據(jù)元素ai在線性表中的位置2.1線性表的類型定義1.線性表：線性表中的數(shù)據(jù)元素在不同的情況下可以有不同的具體含義，它可以是一個數(shù)、一個符號，也可是其它更復(fù)雜的信息例1.26個字母(A,B,…,Z)

例2.班級人數(shù)(33,32,35,30)例3.學(xué)生情況登記表：數(shù)據(jù)元素為記錄，有若干個數(shù)據(jù)項組成（如姓名，學(xué)號，性別，年齡…)P182.1線性表的類型定義2.線性表的特點：線性表中的數(shù)據(jù)元素是各種各樣的，但同一線性表中的元素必定具有相同特性，即屬于同一數(shù)據(jù)對象，比如數(shù)據(jù)元素都是整數(shù)。相鄰數(shù)據(jù)元素之間存在序偶關(guān)系

(a1,a2,…,ai-1,ai,ai+1,…,an)ai-1是ai的直接前驅(qū)元素，ai+1是ai的直接后繼元素相當(dāng)靈活，長度可以增長或縮短。即可對線性表中的元素進(jìn)行訪問，還可進(jìn)行插入和刪除等。2.1線性表的類型定義3.線性表的基本運算在線性表中插入一個元素；在線性表中刪除某個元素；在線性表中查找某個特定元素；在線性表中查找某個元素的后繼元素；在線性表中查找某個元素的前驅(qū)元素；創(chuàng)建空線性表；判別一個線性表是否為空表。……由基本運算可以構(gòu)成其它較為復(fù)雜的運算2.1線性表的類型定義4.抽象數(shù)據(jù)類型線性表的定義P19ADTList{

數(shù)據(jù)對象：D={ai|aiElemSet,i=1,2,…,n,n

0}

數(shù)據(jù)關(guān)系：R1={<ai-1,ai>|

ai-1,

aiD,i=1,2,…,n}

基本操作：

InitList(&L)

操作結(jié)果：構(gòu)造一個空的線性表L

DestroyList(&L)

初始條件：線性表L已存在操作結(jié)果：銷毀線性表

…2.1線性表的類型定義4.抽象數(shù)據(jù)類型線性表的定義（P19）

…ClearList(&L)

初始條件：線性表L已存在操作結(jié)果：將線性表L重置為空表

ListEmpty(L)

初始條件：線性表L已存在操作結(jié)果：若L為空表，則返回TRUE，否則返回FALSE

ListLength(L)

初始條件：線性表L已存在操作結(jié)果：返回L中數(shù)據(jù)元素個數(shù)

2.1線性表的類型定義4.抽象數(shù)據(jù)類型線性表的定義（P19）

GetElem(L,i,&e)

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

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

LocateElem(L,e,compare())

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

PriorElem(L,cur_e,&pre_e)

初始條件：線性表L已存在操作結(jié)果：若cur_e是L的元素，但不是第一個，則

用pre_e返回它的前驅(qū)，否則操作失敗，pre_e無定義2.1線性表的類型定義4.抽象數(shù)據(jù)類型線性表的定義（P19）

NextElem(L,cur_e,&next_e)

初始條件：線性表L已存在操作結(jié)果：若cur_e是L的元素，但不是最后一個，則用next_e返回它的后繼，否則操作失敗，next_e無定義

ListTraverse(L,visit())

初始條件：線性表L已存在操作結(jié)果：依次對L的每個元素調(diào)用函數(shù)visit()。一旦visit()失敗，則操作失敗2.1線性表的類型定義4.抽象數(shù)據(jù)類型線性表的定義（P19）

ListInsert(&L,i,e)

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

操作結(jié)果：在L的第i個元素之前插入新的元素e，L

的長度增1

ListDelete(&L,i,&e)

初始條件：線性表L已存在且非空，

1≤i≤LengthList(L)

操作結(jié)果：刪除L的第i個元素，并用e返回其值，L

的長度減1}ADTList2.1線性表的類型定義算法2-1

假設(shè)利用兩個線性表LA和LB分別表示兩個集合A和B（即：線性表中的數(shù)據(jù)元素即為集合中的成員），現(xiàn)要求一個新的集合A＝A∪B。上述問題等價于：要求對線性表作如下操作：擴(kuò)大線性表LA，將存在于線性表LB中而不存在于線性表LA中的數(shù)據(jù)元素插入到線性表LA中去。

分下列三步進(jìn)行：

1）從線性表LB中依次取得每個數(shù)據(jù)元素;

2）依值在線性表LA中進(jìn)行查訪;

3）若不存在，則插入之。2.1線性表的類型定義算法2.1：用C語言描述如下算法：voidunion(List&La,ListLb){

//將所有在線性表Lb中但不在La中的數(shù)據(jù)元素插入到La中

La_len=ListLength(La);Lb_len=ListLength(Lb);//求線性表的長度

for(i=1;i<=Lb_len;i++){GetElem(Lb,i,e);//取Lb中第i個數(shù)據(jù)元素賦給e

if(!LocateElem(La,e,equal))

ListInsert(La,++La_len,e);

//La中不存在和e相同的數(shù)據(jù)元素，則插入之

}}//union2.1線性表的類型定義例2-2

已知一個非空集合B，試構(gòu)造集合A，要求集合A中只包含集合B中所有值不相同的數(shù)據(jù)元素。

解法一：同上，分別以線性表LA和LB表示集合A和B，則首先初始化線性表LA為空表，之后的操作和例2-1完全相同。

解法二：仍以線性表表示集合。只是求解之前先對線性表LB中的數(shù)據(jù)元素進(jìn)行排序，即線性表LB中的數(shù)據(jù)元素依其值從小到大有序排列，則值相同的數(shù)據(jù)元素必相鄰。則上述操作中的第二步就不需要進(jìn)行從頭至尾的查詢。2.1線性表的類型定義算法2.2：用C語言描述得如下算法（針對解法一）voidpurge(List&La,ListLb){

InitList（La）；//初始化La為空表

La_len=ListLength(La);Lb_len=ListLength(Lb);//求線性表的長度

for(i=1;i<=Lb_len;i++){GetElem(Lb,i,e);//取Lb中第i個數(shù)據(jù)元素賦給e

if(ListEmpty(La)||!LocateElem(La,e,equal))

ListInsert(La,++La_len,e);//La中不存在和e相同的數(shù)據(jù)元素，則插入之

}//for}//purge思考題：請針對例子2-2C語言描述，寫出解法二對應(yīng)算法。2.1線性表的類型定義例2-3

P20例子2-2。歸并兩個“其數(shù)據(jù)元素按值非遞減有序排列的”線性表LA和LB，求得線性表LC也具有同樣特性。算法2.3：C語言描述如下：voidMergeList(ListLa,ListLb,List&Lc){//已知線性表La和Lb中的元素按值非遞減排列。歸并La和Lb得到新的線性表Lc，Lc的元素也按值非遞減排列。

InitList(Lc);i=j=1;k=0;La_len=ListLength(La);Lb_len=ListLength(Lb);//求線性表的長度

while((i<=La_len)&&(j<=Lb_len)){//La和Lb均非空

GetElem(La,i,ai);GetElem(Lb,j,bj);2.1線性表的類型定義

if(ai<=bj){ListInsert(Lc,++k,ai);++i;}else{ListInsert(Lc,++k,bj);++j;}}//將較小的元素優(yōu)先插入Lc

while(i<=La_len){GetElem(La,i++,ai);ListInsert(Lc,++k,ai);}//La的剩余元素插入Lc

while(j<=Lb_len){GetElem(Lb,j++,bj);ListInsert(Lc,++k,bj);}//Lb的剩余元素插入Lc}//merge_list算法結(jié)果演示：思考題：為什么上述兩個while循環(huán)體只會執(zhí)行其中的一個？2.1線性表的類型定義●

算法時間復(fù)雜度分析:

假設(shè):

GetElem和ListInsert這兩個操作的執(zhí)行時間和表長無關(guān)，LocateElem的執(zhí)行時間和表長成正比，則算法2.1的時間復(fù)雜度為

O(ListLength(LA)×ListLength(LB))；

例2-2(解法一)的時間復(fù)雜度為

O(ListLength2(LB))；算法2.2的時間復(fù)雜度為

O(ListLength(LB))；

可見，不同的算法策略所得不同算法的時間復(fù)雜度不同。算法2.3的時間復(fù)雜度為

O(ListLength(LA)＋ListLength(LB))2.1線性表的類型定義線性表的順序表示：

以元素在計算機(jī)內(nèi)存中的“物理位置相鄰”來表示線性表中數(shù)據(jù)元素之間的邏輯關(guān)系，如下所示：

Locate(ai+1)=Locate(ai)+sizeof(DataType) Locate(ai)=Locate(a0)+sizeof(DataType)*i稱第一個數(shù)據(jù)元素的存儲地址為線性表的起始地址，稱作線性表的基地址。只要確定了基地址，線性表中任意數(shù)據(jù)元素都可以隨機(jī)存取。因此線性表的順序存儲結(jié)構(gòu)為一種隨機(jī)存取的存儲結(jié)構(gòu)。2.2線性表的順序表示和實現(xiàn)邏輯地址數(shù)據(jù)元素存儲地址數(shù)據(jù)元素0k0Loc(k0)k01k1Loc(k0)+ck1…………ikiLoc(k0)+i*cki……n-1kn-1Loc(k0)+(n-1)*ckn-1●線性表的順序存儲結(jié)構(gòu)示意圖2.2線性表的順序表示和實現(xiàn)2.2線性表的順序表示和實現(xiàn)線性表順序存儲（順序表）結(jié)構(gòu)定義：在C語言中可以用一維數(shù)組表示。

constLIST_INIT_SIZE=100;//表初始空間分配量

constLISTINCREMENT=10;//空間分配增量

typedefstruct{ElemType*elem;//存儲空間基址

intlength;//順序表的當(dāng)前長度

intlistsize;//順序表當(dāng)前存儲容量

}SqList;2.2線性表的順序表示和實現(xiàn)●根據(jù)順序表的存儲特點，順序表的基本操作：1、構(gòu)造空表：

StatusInitList_Sq(SqList&L)

{//構(gòu)造空表L

L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!L.elem)exit(OVERFLOW);L.length=0;//表當(dāng)前長度

L.listsize=LIST_INIT_SIZE;//表容量

L.incrementsize=LISTINCREMENT;returnOK;}//InitList_Sq2.2線性表的順序表示和實現(xiàn)2.

intinsert_sq(SqListpalist,DataTypex,intp)

在palist所指順序表中下標(biāo)為p的位置上插入一個值為x的元素，并返回插入成功與否的標(biāo)志。此運算在0≤p≤n時有意義3.

intdelete_sq(SqListpalist,intp)

在palist所指順序表中刪除下標(biāo)為p的元素，并返回刪除成功與否的標(biāo)志。此運算在0≤p＜n時有意義2.2線性表的順序表示和實現(xiàn)3.

intfirst_sq(SqListpalist)

求palist所指順序表中第一個元素的下標(biāo)。當(dāng)palist為空表時返回一個特殊的下標(biāo)值-14.intlocate_sq(SqListpalist,DataTypex)

在palist所指順序表中尋找值為x的元素的下標(biāo)，若palist中不存在值為x的元素，則返回一個特殊的下標(biāo)值-12.2線性表的順序表示和實現(xiàn)5.DataTyperetrieve_sq(SqListpalist,intp)

在palist所指順序表中，尋找下標(biāo)為p(0≤p＜n)的元素，并將該元素的值作為函數(shù)值返回，若palist中無下標(biāo)為ｐ的元素，則返回一個特殊的值6.intnext_sq(SqListpalist,intp)

求palist所指順序表中下標(biāo)為p的元素的后繼元素下標(biāo)，當(dāng)不存在下標(biāo)為p的元素或雖有該元素但無后繼時，返回一個特殊的下標(biāo)值-12.2線性表的順序表示和實現(xiàn)7.intprevious_sq(SqListpalist,intp)

求palist所指順序表中下標(biāo)為p的元素的前驅(qū)元素下標(biāo)，當(dāng)不存在下標(biāo)為p的元素，或雖有該元素但無前驅(qū)時，本函數(shù)返回一個特殊的下標(biāo)值-18.voidcreateNullList_sq(SqListpalist)

置palist所指順序表為空表9.intisNullList_sq(SqListpalist)

判別palist所指順序表是否為空表。若為空則返回1,否則返回02.2線性表的順序表示和實現(xiàn)●

順序表的插入和刪除操作及算法描述：

1）線性表的插入操作示意圖。P23圖2.3

..\數(shù)據(jù)結(jié)構(gòu)C語言版.pdf。插入算法C語言描述如下：

StatusListInsert_Sq(SqList&L,inti,ElemTypee){//在順序表L中第i個位置之前插入新元素e

if(i<1||i>L.length+1)returnERROR;//非法的位置

if(L.length>=L.listsize){//當(dāng)前空間已滿

newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));

2.2線性表的順序表示和實現(xiàn)if(!newbase)exit(OVERFLOW);L.elem=newbase;L.listsize=L.listsize+INCREMENT;}

q=&(L.elem[i-1]);//定位位置i，對應(yīng)數(shù)組下標(biāo)為i-1

for(p=&(L.elem[L.length-1]),p>=q;--p){*(p+1)=*p;}//插入位置及之后的元素后移一個單元*q=e;//e插入位置iL.length++;//表長增1

returnOK;

}//ListInsert_Sq2.2線性表的順序表示和實現(xiàn)2）線性表的刪除操作示意圖。P23圖2.4

..\數(shù)據(jù)結(jié)構(gòu)C語言版.pdf。刪除算法C語言描述如下：StatusListDelete_Sq(SqList&L,intI,ElemType&e){//刪除L中第i個元素，后面的元素前移

if(i<1||i>L.length)returnERROR;//i值不合法p=&(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_Sq2.2線性表的順序表示和實現(xiàn)插入元素時的時間效率：

設(shè)pi是在第i個元素之前插入一個元素的概率，則在長度為n的線性表中插入一個元素時所需移動元素的次數(shù)的期望值（平均次數(shù)）為：設(shè)則有2.2線性表的順序表示和實現(xiàn)刪除元素時的時間效率：

設(shè)qi是刪除第i個元素的概率，則在長度為n的線性表中刪除一個元素時所需移動元素的次數(shù)的期望值（平均次數(shù)）為：設(shè)則有2.2線性表的順序表示和實現(xiàn)算法2.7：兩個順序表的合并P26voidMergeList_Sq(SqListla,SqListlb,SqList&lc){//已知順序表La和Lb的元素按值非遞減排列。與P21算法2.2類似

//歸并La和Lb得到新的順序線性表Lc，Lc的元素也按值非遞減排列。

ElemType*pa,*pb,*pc,*pa_last,*pb_last; pa=la.elem;pb=lb.elem; lc.listsize=la.length+lb.length; pc=lc.elem=(ElemType*)malloc(sizeof(ElemType)*lc.listsize); if(!lc.elem)exit(OVERFLOW); pa_last=pa+la.length-1; pb_last=pb+lb.length-1;2.2線性表的順序表示和實現(xiàn)

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的剩余元素

}//EndofMergeList_Sq()算法結(jié)果演示：..\數(shù)據(jù)結(jié)構(gòu)-光盤\DS-Algo-VC2.2線性表的順序表示和實現(xiàn)例：設(shè)計一個算法，用盡可能少的輔助空間將順序表中前m個元素和后n個元素進(jìn)行整體互換。即將線性表(a1,a2,…,am,b1,b2,…,bn)改變成

(b1,b2,…,bn,a1,a2,…,am)

分析1：取一臨時空間，將b1放入臨時空間，a1-am全部后移一個位置，如此b2,直到bn。

特點：犧牲時間節(jié)省空間。

分析2：另外申請空間m+n個元素單元，將b,a分別寫入。時間復(fù)雜度將為O（n+m）。2.2線性表的順序表示和實現(xiàn)算法一實現(xiàn)：voidexchange1(SqList&L,intm,intn){//線性表分成兩個部分后，兩部分倒置

for(i=1;i<=n;i++){w=L.Elem[i+m];//臨時空間w

for(j=m;j>=1;j--)

L.Elem[i+j]=L.Elem[i+j-1];L.Elem[i]=w;//依次轉(zhuǎn)移w，

}

}//exchange12.3線性表的鏈?zhǔn)奖硎炯皩崿F(xiàn)順序表的缺陷：插入/刪除耗費大量時間。因此，引入線性鏈表：用一組任意單元表示數(shù)據(jù)元素和數(shù)據(jù)元素之間的關(guān)系（這些單元可以是連續(xù)的，也可以是不連續(xù)的）。其結(jié)點由兩部分信息組成：

（1）數(shù)據(jù)域：存儲數(shù)據(jù)元素信息；（2）指針域：存儲直接后繼的存儲位置（地址）?！矜湵眍^指針指示鏈表中的第一個結(jié)點的存儲位置，整個鏈表的存取必須從頭指針開始。最后一個結(jié)點沒有直接后繼，其指針域為“空”（NULL）。2.3線性表的鏈?zhǔn)奖硎炯皩崿F(xiàn)2.3.1單鏈表：

數(shù)據(jù)域指針域存儲地址數(shù)據(jù)域指針域

1 Li 437 Qian 1313 Sun 1 19 Wang NULL25 Wu 3731 Zhao 737 Zheng1943 Zhou 2531頭指針H2.3線性表的鏈?zhǔn)奖硎炯皩崿F(xiàn)單鏈表：單鏈表的邏輯結(jié)構(gòu)LiZhaoQianSunZhouWuZhengWang^H2.3線性表的鏈?zhǔn)奖硎炯皩崿F(xiàn)單鏈表：一般附加一個頭結(jié)點，其數(shù)據(jù)域不存儲信息，指針域存儲指向第一個結(jié)點的指針。

a1an^a2...頭指針H頭結(jié)點H^非空表空表單鏈表結(jié)構(gòu)：注意頭指針，頭結(jié)點等概念的不同含義。

2.3線性表的鏈?zhǔn)奖硎炯皩崿F(xiàn)2.3線性表的鏈?zhǔn)奖硎炯皩崿F(xiàn)為什么要加頭結(jié)點？

頭結(jié)點是鏈表的開始結(jié)點之前的一個附加結(jié)點。

使用頭結(jié)點的好處在于：（1）由于開始結(jié)點(第一個數(shù)據(jù)節(jié)點)位置被存放在頭結(jié)點的指針域中，所以在鏈表的第一個位置上的操作就和在表的其它位置上的操作一致，無須進(jìn)行特殊處理。（2）無論鏈表是否為空，其頭指針是指向結(jié)點的非空指針（空表中頭結(jié)點的指針域為空），因此空表和非空表的處理也就統(tǒng)一了。線性鏈表的定義typedefintElemType;/*定義元素類型為整型，也可定義為其他類型*/structLNode; /*單鏈表結(jié)點類型*/typedefstructLNode*PNode;/*結(jié)點指針類型*/=======================================structLNode /*單鏈表結(jié)點存儲結(jié)構(gòu)*/{

ElemTypedata；//數(shù)據(jù)域

structLNode *next;//指針域}Lnode,*LinkList;2.3線性表的鏈?zhǔn)奖硎炯皩崿F(xiàn)單鏈表基本操作：

1、StatusInitList_L(LinkList&L){

//建立頭結(jié)點，其Next為空。初始化為空表

L=(LinkList)malloc(sizeof(LNode));L->next=NULL;returnOK;}2.3線性表的鏈?zhǔn)奖硎炯皩崿F(xiàn)2、VoidCreateList_L(LinkList&L,intn){/*創(chuàng)建一個帶頭結(jié)點的鏈表*/

L=(LinkList)malloc(sizeof(LNode));L->next=NULL;//創(chuàng)建頭結(jié)點

for(i=n;i>0;--i){//按數(shù)組倒序建立鏈表

p=(LinkList)malloc(sizeof(LNode));//生成一個節(jié)點

scanf(&p->data);//讀取一個數(shù)據(jù)

p->next=L->next;//P指針域賦值

L->next=p;

}

}//CreateList_L

算法結(jié)果演示：..\數(shù)據(jù)結(jié)構(gòu)-光盤\DSDemoW2.3線性表的鏈?zhǔn)奖硎炯皩崿F(xiàn)3、算法2.8單鏈表的元素讀?。ǚ请S機(jī)存?。㏒tatusGetElem_L(LinkList&L,inti,ElemType&e){//L為帶//帶頭結(jié)點的單鏈表的頭指針。當(dāng)?shù)趇個元素存在時，其值賦給e并返回//OK，否則返回ERROR

LinkListp;//鏈表指針變量pp=L->next;intj=1;//初始化，p指向第一個結(jié)點，j為計數(shù)器

while(p&&j<i){//順指針向后查找，直到p指向第i個元素或p為空

p=p->next;++j;}if(!p||j>i)returnERROR;//位置合法性檢查，第i個元素不存在？

e=p->data;//取第i個元素

returnOK;}//GetElem_L2.3線性表的鏈?zhǔn)奖硎炯皩崿F(xiàn)單鏈表結(jié)點插入和刪除P29圖2.8、2.9..\數(shù)據(jù)結(jié)構(gòu)C語言版.pdf2.3線性表的鏈?zhǔn)奖硎炯皩崿F(xiàn)abpabpcs->next=p->next;

注：順序不能反單鏈表插入結(jié)點

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

單鏈表刪除結(jié)點abxsp2.p->next=s;●單鏈表結(jié)點插入算法描述：

StatusListInsert_L(LinkList&L,inti,ElemTypee){//算法2.9

//在帶頭結(jié)點的單鏈線性表L的第i個元素之前插入元素e

LinkListp,s;p=L;//p指向L頭結(jié)點

intj=0;while(p&&j<i-1){//尋找第i-1個結(jié)點

p=p->next;++j;}if(!p||j>i-1)returnERROR;//插入位置合法性檢查，

i小于1或者大于表長？

s=(LinkList)malloc(sizeof(LNode));//生成新結(jié)點

s->data=e;s->next=p->next;//插入L中

p->next=s;returnOK;}//LinstInsert_L算法結(jié)果演示：..\數(shù)據(jù)結(jié)構(gòu)-光盤\DSDemoW2.3線性表的鏈?zhǔn)奖硎炯皩崿F(xiàn)●單鏈表結(jié)點刪除算法描述：StatusListDelete_L(LinkList&L,inti,ElemType&e){//算法//2.10。在帶頭結(jié)點的單鏈線性表L中，刪除第i個元素，并由e返回其值

LinkListp,q;p=L;intj=0;while(p->next&&j<i-1){//尋找第i個結(jié)點

p=p->next;++j;}if(!(p->next)||j>i-1)returnERROR;//刪除位置合法性檢查，是否合理？

q=p->next;//預(yù)刪除的結(jié)點ip->next=q->next;//刪除并釋放結(jié)點

e=q->data;free(q);returnOK;}//ListDelete_L算法結(jié)果演示：..\數(shù)據(jù)結(jié)構(gòu)-光盤\DSDemoW2.3線性表的鏈?zhǔn)奖硎炯皩崿F(xiàn)●單鏈表查找算法描述：算法2.12LNode*LocateElem_L(LinkListL,ElemTypee){//在L中找到第一個值和e相同的結(jié)點，返回其

//地址，若不存在，返回空值。

if(!L)returnNULL;p=L;

while(p&&p->data!=e)p=p->next;returnp;}算法結(jié)果演示：..\數(shù)據(jù)結(jié)構(gòu)-光盤\DS-Algo-VC該算法時間復(fù)雜度：O(n)2.3線性表的鏈?zhǔn)奖硎炯皩崿F(xiàn)算法2.13：將兩個有序鏈表歸并為一個新的有序鏈表。分析：有兩個非遞減有序鏈表La,Lb.現(xiàn)歸并La,Lb得到Lc。其條件Lc非遞減有序，即當(dāng)前節(jié)點，大于前者，小于后者。VoidMergeList_L(LinkList&Lc,LinkListLa,LinkListLb){

//已知兩個非遞減單鏈表為La,Lb

//歸并單鏈表La,Lb,形成新的有序鏈表Lc

pa=La->next;pb=Lb->next;

Lc=pc=La;//用La的頭結(jié)點作為Lc的頭結(jié)點2.3線性表的鏈?zhǔn)奖硎炯皩崿F(xiàn)

while(pa&&pb){//La,Lb非空

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;

//插入剩余段，思考題:如何實現(xiàn)？

free(Lb);//釋放Lb的頭結(jié)點，為啥不釋放La？}//MergeList_L算法結(jié)果演示：..\數(shù)據(jù)結(jié)構(gòu)-光盤\DSDemoW時間復(fù)雜度分析：O(n)

2.3線性表的鏈?zhǔn)奖硎炯皩崿F(xiàn)單鏈表與順序表的比較：單鏈表的存儲密度比順序表低，它多占用了存儲空間。但在許多情況下，鏈?zhǔn)降姆峙浔软樞蚍峙溆行?，順序表必須分配足夠大的連續(xù)的存儲空間，而鏈表可以利用零星的存儲單元在單鏈表里進(jìn)行插入、刪除運算比在順序表里容易得多對于順序表，可隨機(jī)訪問任一個元素，而在單鏈表中，需要順著鏈逐個進(jìn)行查找，因此單鏈表適合于在成批地、順序地處理線性表中的元素時采用。（單鏈表不是隨機(jī)存?。?.3線性表的鏈?zhǔn)奖硎炯皩崿F(xiàn)2.3.2循環(huán)鏈表最后一個結(jié)點的指針域的指針又指回第一個結(jié)點操作與線性鏈表基本一致循環(huán)條件：p->next==p->head表空條件：p->head->next==p->head2.3線性表的鏈?zhǔn)奖硎炯皩崿F(xiàn)HH空循環(huán)鏈表非空循環(huán)鏈表2.3.3雙向鏈表可以在單鏈表的每一個結(jié)點里再增加一個指向其前趨和后繼的指針域。這樣鏈表中有兩條不同方向的鏈。優(yōu)點：既可以找前驅(qū)，也可以找后繼。2.3線性表的鏈?zhǔn)奖硎炯皩崿F(xiàn)H

^^H^^空雙向鏈表非空雙向鏈表雙向鏈表存儲結(jié)構(gòu)：

typedefstructDuLNode{

ElemTypedata;

structDuLNode*prior;

structDuLNode*next;

}DuLNode,*DuLinkList;2.3線性表的鏈?zhǔn)奖硎炯皩崿F(xiàn)雙向循環(huán)鏈表2.3線性表的鏈?zhǔn)奖硎炯皩崿F(xiàn)H

H空雙向循環(huán)鏈表非空雙向循環(huán)鏈表2.3線性表的鏈?zhǔn)奖硎炯皩崿F(xiàn)雙向(循環(huán))鏈表的插入和刪除刪除雙向鏈表的結(jié)點1.p->prior->next=p->next;2.p->next->prior=p->prior;往雙向鏈表中插入結(jié)點s->prior=p->prior;p->prior->next=s;//先左s->next=p;p->prior=s;//后右順序不可顛倒ABCpABCsp①②③④①②③④雙向循環(huán)鏈表的插入算法：StatusListInsert_Dul(DuLinkList&L,inti,ElemTypee){//在帶頭結(jié)點的雙向循環(huán)鏈表第i個位置插入元素e

if(!(p=GetElemP_Dul(L,i)))returnERROR；//表的長度未達(dá)i，定位is=(DuLinkList)malloc(sizeof(ElemType));//生成結(jié)點

if(!s)exit(OVERFLOW)//空間不夠，溢出

s->data=e;s->prior=p->prior;p->prior->next=s;s->next=p;p->prior=s;returnOK;//更改指針域，插入結(jié)點e

}//ListInsert_Dul2.3線性表的鏈?zhǔn)奖硎炯皩崿F(xiàn)雙向循環(huán)鏈表的刪除算法：StatusListDelete_Dul(DuLinkList&L,inti,ElemType&e){//在帶頭結(jié)點的雙向循環(huán)鏈表中刪除第i個位置元素，并將結(jié)果存入e

if(!(p=GetElemP_Dul(L,i)))returnERROR；//表的長度未達(dá)i，定位i

e=p->data;p->prior->next=p->next;p->next->prior=p->prior;free(p);//更改指針域，釋放第i個結(jié)點

returnOK;

}//ListDelete_Dul2.3線性表的鏈?zhǔn)奖硎炯皩崿F(xiàn)線性鏈表與順序表的比較：線性鏈表

優(yōu)點：空間的合理利用；插入和刪除時不需要移動缺點：實現(xiàn)基本操作（如求表長）不如順序表數(shù)據(jù)元素的“位序”概念被淡化很多場合下，線性鏈表是線性表的首選存儲結(jié)構(gòu)2.3線性表的鏈?zhǔn)奖硎炯皩崿F(xiàn)一個帶頭結(jié)點的線性鏈表類型定義：P37~38..\數(shù)據(jù)結(jié)構(gòu)C語言版.pdf2.3線性表的鏈?zhǔn)奖硎炯皩崿F(xiàn)多項式運算的問題，幾乎成為表處理的一個經(jīng)典問題。用單鏈表結(jié)構(gòu)來表示多項式，研究兩個多項式的相加運算一元多項式

Pn(x)=p0+p1x+p2x2++pnxnQm(x)=q0+q1x+q2x2++qmxm在計算機(jī)中可以用一個線性表P,Q（順序存儲）來表示：P=(p0,p1,p2,,pn)Q=(q0,q1,q2,,qm)

每一項的指數(shù)都隱含在系數(shù)pi,qj的序號里2.4一元多項式的表示及相加多項式相加：Rn(x)=Pn(x)+Qm(x)(m<n)在計算機(jī)中可以用一個線性表R（順序存儲）來表示：R=(p0+q0,p1+q1,p2+q2,pm+qm,pm+1,,pn)采用順序結(jié)構(gòu)使的多項式相加的算法非常簡潔這種表示方法對于所有項都比較全的時候是很好的，但是如果指數(shù)很高并且變化很大時，不合適，順序表的最大長度難以確定。2.4一元多項式的表示及相加例如：一個稀疏多項式

:

S(x)=1+3x109-5x231+6x354把每一項的系數(shù)和指數(shù)都存儲下來，也就是對于每一項都用兩個數(shù)據(jù)項來存儲。即為如下的形式：P=((p1,e1),(p2,e2),(pm,em))可用線性表((1,0),(3,109),(-5,231),(6,354))表示對于這種表示方法，采用鏈?zhǔn)酱鎯?。利用單鏈表表示多項式時，每個結(jié)點設(shè)有三個域：系數(shù)域coef，指數(shù)域exp和鏈域next。

2.4一元多項式的表示及相加coefexpnext抽象數(shù)據(jù)類型一元多項式的定義ADTPolynomial{

數(shù)據(jù)對象：D＝{ai|ai∈TermSet,i=1,2,...,m,m≥0

TermSet中的每個元素包含一個表示系數(shù)的實數(shù)和表示指數(shù)的整數(shù)

}

數(shù)據(jù)關(guān)系：R1＝{<ai-1,ai>|ai-1,ai∈D,且ai-1中的指數(shù)值＜ai中的指數(shù)值，i=2,...,n}

基本操作：

CreatPolyn(&P,m)

操作結(jié)果：輸入m項的系數(shù)和指數(shù)，建立一元多項式P。

DestroyPolyn(&P)

初始條件：一元多項式P已存在。2.4一元多項式的表示及相加

操作結(jié)果：銷毀一元多項式P。

PrintPolyn(&P)

初始條件：一元多項式P已存在。操作結(jié)果：打印輸出一元多項式P。

AddPolyn(&Pa,&Pb)

初始條件：一元多項式Pa和Pb已存在。操作結(jié)果：完成多項式相加運算，即：Pa=Pa＋Pb，并銷毀一元多項式Pb。

SubtractPolyn(&Pa,&Pb)

初始條件：一元多項式Pa和Pb已存在。操作結(jié)果：完成多項式相減運算，即：Pa=Pa－Pb，并銷毀一元多項式Pb。2.4一元多項式的表示及相加

MultiplyPolyn(&Pa,&Pb)

初始條件：一元多項式Pa和Pb已存在。操作結(jié)果：完成多項式相乘運算，即：Pa=Pa×Pb，并銷毀一元多項式Pb。

PolynLength(P)

初始條件：一元多項式P已存在。操作結(jié)果：返回一元多項式P中的項數(shù)。

}ADTPolynomial2.4一元多項式的表示及相加例AH=1-10x6+2x8+7x14BH=-x4+10x6-3x10+8x14+4x18CH(x)=AH(x)+BH(x)它的單鏈表表示如圖2.4一元多項式的表示及相加多項式的加法運算規(guī)則:(1)若指數(shù)相等，系數(shù)相加，得C(x)的一項（若和為0，此項不存在）；(2)若A(x)當(dāng)前項指數(shù)小于B(x)，復(fù)抄A(x)的這一項到C(x)上；(3)若A(x)當(dāng)前項指數(shù)大于B(x)，復(fù)抄B(x)的這一項到C(x)上；(4)若一個多項式每項都加到C(x)上了，就把另一多項式的剩余部分復(fù)抄到C(x)上。2.4一元多項式的表示及相加C(x)是動態(tài)建立的，需要從表頭指針?biāo)傅慕Y(jié)點開始檢測，為此我們設(shè)兩個指針pa和pb分別指向兩個多項式中當(dāng)前被檢測的結(jié)點；同時還需要記清C(x)建在什么地方，又設(shè)指針pc指向C(x)當(dāng)前的最后一個結(jié)點。2.4一元多項式的表示及相加根據(jù)運算規(guī)則，考慮以下三種情況：（1）exp(pa)>exp(pb)：把pb指的結(jié)點復(fù)抄到C表的后面。所以調(diào)用過程——鏈接在C(x)上(coef(pb),exp(pb),pc)，并移動指針pb，繼續(xù)往下檢測；（2）exp(pa)=exp(pb)：將它們的系數(shù)相加，為此用一個x單元存放coef(pa)+coef(pb)的和。若x≠0，就調(diào)用過程——鏈接在C(x)上(x,exp(pb),pc)，并移動指針pa，pb；（3）exp(pa)<exp(pb)：把pa所指的結(jié)點復(fù)抄到C表的后面。所以調(diào)用過程——鏈接在C(x)上(coef(pa),exp(pa),pc),并移動指針pa。2.4一元多項式的表示及相加一元多項式抽象數(shù)據(jù)類型的實現(xiàn)：typedefstruct_ElemType//元素類型{ float coef; /*多項式系數(shù)*/

int expn; /*多項式指數(shù)*/}ElemType;/*NodeType單個結(jié)點類型--存儲結(jié)構(gòu)*/typedefstruct_Polyn{

ElemType data; /*數(shù)據(jù)域*/

struct_Polyn*next; /*指針域*/}Node,*Link; /*Nodetype&NodePointer2.4一元多項式的表示及相加typedefstruct{ Link head,tail; /*用作鏈表的頭節(jié)點和尾指針*/

int len; /*可以用來記錄鏈表的長度*/}LinkList,*PLinkList;typedefLinkListpolynomial;/*Initializealinklist–操作*/voidInitPolyn(polynomial&P);/*所用到的函數(shù)的原型化聲明*//*把兩個一元多項式相加*/voidAddPolyn(polynomial&pa,polynomial&pb);/*創(chuàng)建一個一元多項式*/voidCreatePolyn(polynomial&P,intm);2.4一元多項式的表示及相加/*實現(xiàn)兩個一元多項式的相乘*/voidMultiplyPolyn(polynomial&pa,polynomial&pb);/*打印該鏈表的結(jié)果*/voidPrintPolyn(polynomialP);/*比較兩個節(jié)點的指數(shù)的大小*/Intcmp(ElemTypea,ElemTypeb);/*刪除一個鏈表*/voidFreeList(polynomialP);/*Multiplyapolynomialwithanelement*/voidMultiItem(polynomialpResultList,polynomialP,LinkItem);/*Multiplytwolinklist*/PLinkListMultiLinkList(polynomialP1,polynomialP2);2.4一元多項式的表示及相加算法2-23多項式的加法:算法思路P41圖2-17、18..\數(shù)據(jù)結(jié)構(gòu)C語言版.pdfvoidAddPolyn(polynomial&Pa,polynomial&Pb){ ha=GetHead(Pa);hb=GetHead(Pb);//頭結(jié)點位置

qa=NextPos(ha); qb=NextPos(hb)；//開始結(jié)點位置

while(!Empty(Pa)&&!Empty(Pb)) { a=GetCurElem(qa);b=GetCurElem(qb); switch(*cmp(a,b)){ case-1:/*第一個鏈表中當(dāng)前結(jié)點的指數(shù)值小*/

ha=qa;qa=NextPos(Pa,qa);break;//同時移動指針

case0: /*指數(shù)值相等*/

sum=a.coef+b.coef;

if(sum!=0.0){SetCurElem(qa,sum);ha=qa; }2.4一元多項式的表示及相加 else{ /*若為零，則釋放qa所指向的結(jié)點空間*/

DelFirst(ha,qa);FreeNode(qa);}

DelFirst(hb,qb);FreeNode(qb);

qb=NextPos(Pb,hb);qa=NextPos(Pa,qa);break;

case1:/*第一個鏈表中當(dāng)前結(jié)點的指數(shù)值大*/

DelFirst(hb,qb);InsFirst(ha,qb);//從Lb中刪除qb，將qb插入La

qb=NextPos(Pb,hb);ha=NextPos(Pa,ha);break;

} /*EndofSwitch*/

} /*Endofwhile*/

if(!Empty(Pb))Append(Pa,qb);//鏈接Pb中剩余結(jié)點

FreeNode(hb);