第二章-線性表

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

2.3.1線性鏈表

2.3.2循環(huán)鏈表

2.3.3雙向鏈表2.4一元多項(xiàng)式的表示及相加第二章線性表重點(diǎn)：理解線性表的邏輯結(jié)構(gòu)特性熟練掌握線性表的順序存儲(chǔ)結(jié)構(gòu)的描述方法，以及在該存儲(chǔ)結(jié)構(gòu)下的基本操作熟練掌握線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的描述方法，靈活使用單鏈表、雙鏈表、循環(huán)鏈表，學(xué)會(huì)在相應(yīng)存儲(chǔ)結(jié)構(gòu)下實(shí)現(xiàn)其各種基本算法及相關(guān)的時(shí)間性能分析一元多項(xiàng)式的表示和相加第二章線性表難點(diǎn)：能夠從時(shí)間和空間復(fù)雜度的角度綜合比較線性表兩種存儲(chǔ)結(jié)構(gòu)的不同特點(diǎn)及其應(yīng)用場(chǎng)合使用本章所學(xué)的基本知識(shí)設(shè)計(jì)有效算法，解決與線性表相關(guān)的應(yīng)用問(wèn)題第二章線性表線性結(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è)后繼1.線性表：定義：簡(jiǎn)稱為表，是零個(gè)或多個(gè)元素的有窮序列，通?？梢员硎境?a1,a2,…,an)(n

0)表的長(zhǎng)度：表中所含元素的個(gè)數(shù)

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

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

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

數(shù)據(jù)對(duì)象：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)造一個(gè)空的線性表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ù)元素個(gè)數(shù)

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

GetElem(L,i,&e)

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

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

LocateElem(L,e,compare())

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

PriorElem(L,cur_e,&pre_e)

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

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

NextElem(L,cur_e,&next_e)

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

ListTraverse(L,visit())

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

ListInsert(&L,i,e)

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

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

的長(zhǎng)度增1

ListDelete(&L,i,&e)

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

1≤i≤LengthList(L)

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

的長(zhǎng)度減1}ADTList2.1線性表的類型定義算法2-1

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

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

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

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

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

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

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

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

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

ListInsert(La,++La_len,e);

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

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

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

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

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

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

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

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

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

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

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

P20例子2-2。歸并兩個(gè)“其數(shù)據(jù)元素按值非遞減有序排列的”線性表LA和LB，求得線性表LC也具有同樣特性。算法2.3：C語(yǔ)言描述如下：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);//求線性表的長(zhǎng)度

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é)果演示：思考題：為什么上述兩個(gè)while循環(huán)體只會(huì)執(zhí)行其中的一個(gè)？2.1線性表的類型定義●

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

假設(shè):

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

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

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

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

O(ListLength(LB))；

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

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

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

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

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

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

typedefstruct{ElemType*elem;//存儲(chǔ)空間基址

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

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

}SqList;2.2線性表的順序表示和實(shí)現(xiàn)●根據(jù)順序表的存儲(chǔ)特點(diǎn)，順序表的基本操作：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)前長(zhǎng)度

L.listsize=LIST_INIT_SIZE;//表容量

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

intinsert_sq(SqListpalist,DataTypex,intp)

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

intdelete_sq(SqListpalist,intp)

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

intfirst_sq(SqListpalist)

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

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

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

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

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

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

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

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

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

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

StatusListInsert_Sq(SqList&L,inti,ElemTypee){//在順序表L中第i個(gè)位置之前插入新元素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線性表的順序表示和實(shí)現(xiàn)if(!newbase)exit(OVERFLOW);L.elem=newbase;L.listsize=L.listsize+INCREMENT;}

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

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

returnOK;

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

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

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;//表長(zhǎng)減1returnOK;

}//ListDelete_Sq2.2線性表的順序表示和實(shí)現(xiàn)插入元素時(shí)的時(shí)間效率：

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

設(shè)qi是刪除第i個(gè)元素的概率，則在長(zhǎng)度為n的線性表中刪除一個(gè)元素時(shí)所需移動(dòng)元素的次數(shù)的期望值（平均次數(shù)）為：設(shè)則有2.2線性表的順序表示和實(shí)現(xiàn)算法2.7：兩個(gè)順序表的合并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線性表的順序表示和實(shí)現(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線性表的順序表示和實(shí)現(xiàn)例：設(shè)計(jì)一個(gè)算法，用盡可能少的輔助空間將順序表中前m個(gè)元素和后n個(gè)元素進(jìn)行整體互換。即將線性表(a1,a2,…,am,b1,b2,…,bn)改變成

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

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

特點(diǎn)：犧牲時(shí)間節(jié)省空間。

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

for(i=1;i<=n;i++){w=L.Elem[i+m];//臨時(shí)空間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)奖硎炯皩?shí)現(xiàn)順序表的缺陷：插入/刪除耗費(fèi)大量時(shí)間。因此，引入線性鏈表：用一組任意單元表示數(shù)據(jù)元素和數(shù)據(jù)元素之間的關(guān)系（這些單元可以是連續(xù)的，也可以是不連續(xù)的）。其結(jié)點(diǎn)由兩部分信息組成：

（1）數(shù)據(jù)域：存儲(chǔ)數(shù)據(jù)元素信息；（2）指針域：存儲(chǔ)直接后繼的存儲(chǔ)位置（地址）?！矜湵眍^指針指示鏈表中的第一個(gè)結(jié)點(diǎn)的存儲(chǔ)位置，整個(gè)鏈表的存取必須從頭指針開始。最后一個(gè)結(jié)點(diǎn)沒有直接后繼，其指針域?yàn)椤翱铡保∟ULL）。2.3線性表的鏈?zhǔn)奖硎炯皩?shí)現(xiàn)2.3.1單鏈表：

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

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

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

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

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

使用頭結(jié)點(diǎn)的好處在于：（1）由于開始結(jié)點(diǎn)(第一個(gè)數(shù)據(jù)節(jié)點(diǎn))位置被存放在頭結(jié)點(diǎn)的指針域中，所以在鏈表的第一個(gè)位置上的操作就和在表的其它位置上的操作一致，無(wú)須進(jìn)行特殊處理。（2）無(wú)論鏈表是否為空，其頭指針是指向結(jié)點(diǎn)的非空指針（空表中頭結(jié)點(diǎn)的指針域?yàn)榭眨虼丝毡砗头强毡淼奶幚硪簿徒y(tǒng)一了。線性鏈表的定義typedefintElemType;/*定義元素類型為整型，也可定義為其他類型*/structLNode; /*單鏈表結(jié)點(diǎn)類型*/typedefstructLNode*PNode;/*結(jié)點(diǎn)指針類型*/=======================================structLNode /*單鏈表結(jié)點(diǎn)存儲(chǔ)結(jié)構(gòu)*/{

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

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

1、StatusInitList_L(LinkList&L){

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

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

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

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

p=(LinkList)malloc(sizeof(LNode));//生成一個(gè)節(jié)點(diǎn)

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

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

L->next=p;

}

}//CreateList_L

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

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

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

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

e=p->data;//取第i個(gè)元素

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

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

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

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

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

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

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

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

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

i小于1或者大于表長(zhǎng)？

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

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

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

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

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

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

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

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

if(!L)returnNULL;p=L;

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

//已知兩個(gè)非遞減單鏈表為L(zhǎng)a,Lb

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

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

Lc=pc=La;//用La的頭結(jié)點(diǎn)作為L(zhǎng)c的頭結(jié)點(diǎn)2.3線性表的鏈?zhǔn)奖硎炯皩?shí)現(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;

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

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

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

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

typedefstructDuLNode{

ElemTypedata;

structDuLNode*prior;

structDuLNode*next;

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

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

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

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

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

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

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

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

returnOK;

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

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

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

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

:

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

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

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

TermSet中的每個(gè)元素包含一個(gè)表示系數(shù)的實(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項(xiàng)的系數(shù)和指數(shù)，建立一元多項(xiàng)式P。

DestroyPolyn(&P)

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

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

PrintPolyn(&P)

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

AddPolyn(&Pa,&Pb)

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

SubtractPolyn(&Pa,&Pb)

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

MultiplyPolyn(&Pa,&Pb)

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

PolynLength(P)

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

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

int expn; /*多項(xiàng)式指數(shù)*/}ElemType;/*NodeType單個(gè)結(jié)點(diǎn)類型--存儲(chǔ)結(jié)構(gòu)*/typedefstruct_Polyn{

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

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

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

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

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

ha=qa;qa=NextPos(Pa,qa);break;//同時(shí)移動(dòng)指針

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

sum=a.coef+b.coef;

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

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

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

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

case1:/*第一個(gè)鏈表中當(dāng)前結(jié)點(diǎn)的指數(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é)點(diǎn)

FreeNode(hb);