CHAP2線性表(數(shù)據(jù)結(jié)構(gòu))

1線性表是一種最簡(jiǎn)單的線性結(jié)構(gòu)第二章線性表2.1 線性表及其基本運(yùn)算2.2 線性表的順序存儲(chǔ)結(jié)構(gòu)2.3 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)線性表的邏輯結(jié)構(gòu)、物理結(jié)構(gòu)，以及它們之間的相互關(guān)系；定義與之相適應(yīng)的運(yùn)算；設(shè)計(jì)相應(yīng)的算法；分析算法的效率。32.1線性表的邏輯結(jié)構(gòu)2.3線性表類型的實(shí)現(xiàn)

鏈?zhǔn)接诚?.4一元多項(xiàng)式的表示2.2線性表類型的實(shí)現(xiàn)

順序映象42.1線性表及其基本運(yùn)算

一、線性表（linear_list）線性表是n個(gè)數(shù)據(jù)元素的有限序列，記為：

L=（a1,a2,…,an）

數(shù)據(jù)元素之間的關(guān)系是：

ai-1領(lǐng)先于ai，ai領(lǐng)先于ai+1。稱ai-1是ai的直接前驅(qū)元素；ai+1是ai的直接后繼元素。除a1外，每個(gè)元素有且僅有一個(gè)直接前驅(qū)元素，除an外，每個(gè)元素有且僅有一個(gè)直接后繼元素。線性表中數(shù)據(jù)元素的個(gè)數(shù)n(n>=0)稱為線性表的長(zhǎng)度，當(dāng)n=0時(shí)，稱為空表。6（a1,a2,…ai-1，ai,ai＋1

，…,an）數(shù)據(jù)元素線性起點(diǎn)ai的直接前趨ai的直接后繼下標(biāo)，是元素的序號(hào)，表示元素在表中的位置n為元素總個(gè)數(shù)，即表長(zhǎng)線性終點(diǎn)7【例1】26個(gè)英文字母組成的字母表

（A，B，C、…、Z）【例2】某校從2000年到2005年各種型號(hào)的計(jì)算機(jī)擁有量的變化情況()。

（150，236，321，400，500，600）數(shù)據(jù)元素ai（1≤i≤n）只是個(gè)抽象符號(hào)，其具體含義在不同情況下可以不同。8【例3】學(xué)生健康情況登記表。姓名學(xué)號(hào)性別年齡

健康情況王小林790631

男18

健康陳紅790632

女20

一般劉建平790633

男21

健康張立立790634

男17

神經(jīng)衰弱……..……..…….…….…….92.線性表邏輯結(jié)構(gòu)特征(非空有限集)(1)集合中必存在唯一的一個(gè)“第一元素”；(2)集合中必存在唯一的一個(gè)“最后元素”(3)除最后元素在外，均有唯一的后繼；(4)除第一元素之外，均有唯一的前驅(qū)。線性結(jié)構(gòu)是一個(gè)數(shù)據(jù)元素的有序（次序）集103.抽象數(shù)據(jù)類型線性表的定義ADTList{

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

為線性表的表長(zhǎng);

稱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在線性表中的位序。}11

基本操作：

結(jié)構(gòu)初始化操作結(jié)構(gòu)銷毀操作

引用型操作

加工型操作

}ADTList12

InitList(&L)操作結(jié)果：構(gòu)造一個(gè)空的線性表L。初始化操作13

結(jié)構(gòu)銷毀操作DestroyList(&L)初始條件：線性表L已存在。銷毀線性表L。操作結(jié)果：14ListEmpty(L)ListLength(L)PriorElem(L,cur_e,&pre_e)NextElem(L,cur_e,&next_e)

GetElem(L,i,&e)LocateElem(L,e,compare())ListTraverse(L,visit())引用型操作15加工型操作

ClearList(&L)PutElem(&L,i,&e)ListInsert(&L,i,e)ListDelete(&L,i,&e)

INITIATE（L）

初始化操作 設(shè)定一個(gè)空的線性表LLENGTH（L）

求長(zhǎng)度函數(shù)值為L(zhǎng)中數(shù)據(jù)元素的個(gè)數(shù)GET（L，i）

取元素函數(shù)1<=i<=LENGTH(L)時(shí)返回L中第i個(gè)數(shù)據(jù)元素，否則為空元素NULL。i稱為該數(shù)據(jù)元素在L中的位序PRIOR（L，elm）

求前驅(qū)函數(shù)

elm為L(zhǎng)中的一個(gè)數(shù)據(jù)元素，若它的位序大于1，則函數(shù)值為elm前驅(qū)，否則為NULLNEXT（L，elm）

求后繼函數(shù) 若elm的位序小于表長(zhǎng)，則函數(shù)值為elm的后繼，否則為NULLLOCATE（L，x）

定位函數(shù)給定值x，若x不在表中，則返回0，否則，返回x在表中第一次出現(xiàn)時(shí)的位序INSERTE（L,i,b）前插操作在第i個(gè)元素之前插入新元素b，i的取值范圍為：1<=i<=n+1；i=n+1表示在表尾插入，n為表長(zhǎng)DELETE（L，i）

刪除操作刪除線性表L中的第i個(gè)元素，1<=i<=nEMPTY(L)

判空表函數(shù) 若L為空表，則返回布爾值“true”，否則返回布爾值“false”CLEAR（L）

表置空操作 將L置為空表183.組合基本運(yùn)算，實(shí)現(xiàn)復(fù)雜運(yùn)算

例

2-2(構(gòu)造A)例

2-3(歸并A.B)例

2-1(A＝A∪B)19

假設(shè):有兩個(gè)集合A和B分別用兩個(gè)線性表LA和LB表示，即：線性表中的數(shù)據(jù)元素即為集合中的成員?，F(xiàn)要求一個(gè)新的集合A＝A∪B。【例2-1】

20

要求對(duì)線性表作如下操作：擴(kuò)大線性表LA，將存在于線性表LB中而不存在于線性表LA中的數(shù)據(jù)元素插入到線性表LA中去。上述問(wèn)題可演繹為：211．從線性表LB中依次察看每個(gè)數(shù)據(jù)元素;2．依值在線性表LA中進(jìn)行查訪;3．若不存在，則插入之。GetElem(LB,i)→e

LocateElem(LA,e,equal())

ListInsert(LA,n+1,e)操作步驟：22

GetElem(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);//求線性表的長(zhǎng)度

Lb_len=ListLength(Lb);for(i=1;i<=Lb_len;i++){}}//union23

已知一個(gè)非純集合B，試構(gòu)造一個(gè)純集合A，使A中只包含B中所有值各不相同的數(shù)據(jù)元素。仍選用線性表表示集合【例

2-2】24集合B集合A從集合B

取出物件放入集合A要求集合A中同樣物件不能有兩件以上因此，算法的策略應(yīng)該和例2-1相同25voidpurge(List&La,ListLb){

La_len=ListLength(La);Lb_len=ListLength(Lb);}//purge

GetElem(Lb,i,e);//取Lb中第i個(gè)數(shù)據(jù)元素賦給eif(!LocateElem(La,e,equal()))

ListInsert(La,++La_len,e);

//La中不存在和e相同的數(shù)據(jù)元素，則插入之for(i=1;i<=Lb_len;i++){}InitList(La);//構(gòu)造(空的)線性表LA26若線性表中的數(shù)據(jù)元素相互之間可以比較，并且數(shù)據(jù)元素在線性表中依值非遞減或非遞增有序排列，即ai≥ai-1

或ai≤ai-1(i=2,3,…,n)，則稱該線性表為有序表(OrderedList)。試改變結(jié)構(gòu)，以有序表表示集合。27例如：（2，3，3，5，6，6，6，8，12）對(duì)集合B而言，

值相同的數(shù)據(jù)元素必定相鄰對(duì)集合A而言，

數(shù)據(jù)元素依值從小至大的順序插入因此，數(shù)據(jù)結(jié)構(gòu)改變了，解決問(wèn)題的策略也相應(yīng)要改變。28voidpurge_order(List&La,ListLb)

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

for(i=1;i<=Lb_len;i++){

}}//purge_order

GetElem(Lb,i,e);//取Lb中第i個(gè)數(shù)據(jù)元素賦給eif(ListEmpty(La)||!equal(en,e))

{

ListInsert(La,++La_len,e);en=e;}

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

歸并兩個(gè)“其數(shù)據(jù)元素按值非遞減有序排列”的有序表LA和LB，求得有序表LC也具有同樣特性。設(shè)

La=(a1,…,ai,…,an)

Lb=(b1,…,bj,…,bm)

Lc=(c1,…,ck,…,cm+n)【例

2-3】k=1,2,…,m+n301．初始化LC為空表；基本操作：2．分別從LA和LB中取得當(dāng)前元素ai

和bj；3．若ai≤bj，則將ai

插入到LC中，否則將

bj插入到LC中；4．重復(fù)2和3兩步，直至LA或LB中元素被取完為止；5．將LA表或LB表中剩余元素復(fù)制插入到

LC表中。31

//La和Lb均非空，i=j=1,k=0GetElem(La,i,ai);GetElem(Lb,j,bj);

if(ai<=bj){//將ai插入到Lc中

ListInsert(Lc,++k,ai);++i;}else{//將bj插入到Lc中

ListInsert(Lc,++k,bj);++j;}32voidMergeList(ListLa,ListLb,List&Lc){

InitList(Lc);//構(gòu)造空的線性表Lci=j=1;k=0;La_len=ListLength(La);Lb_len=ListLength(Lb);}//merge_listwhile((i<=La_len)&&(j<=Lb_len))

{//La和Lb均不空}while(i<=La_len)

//若La不空while(j<=Lb_len)//若Lb不空33

while(i<=La_len){GetElem(La,i++,ai);ListInsert(Lc,++k,ai);

}

//插入La表中剩余元素

while(j<=Lb_len){GetElem(Lb,j++,bj);ListInsert(Lc,++k,bj);

}

//插入Lb表中剩余元素342.2線性表的順序表示和實(shí)現(xiàn)351.定義：用一組地址連續(xù)的存儲(chǔ)單元

依次存放線性表中的數(shù)據(jù)元素。

a1a2

…ai-1ai

…an線性表的起始地址，稱作線性表的基地址2.2.1線性表的順序存儲(chǔ)結(jié)構(gòu)362.實(shí)現(xiàn)：可用C/C++的一維數(shù)組實(shí)現(xiàn)a1a2an01n-112n內(nèi)存單元數(shù)組下標(biāo)元素序號(hào)m-1373．結(jié)點(diǎn)ai

的存儲(chǔ)地址

以“存儲(chǔ)位置相鄰”表示有序?qū)?lt;ai-1，ai>

即：LOC(ai)=LOC(ai-1)+C

一個(gè)數(shù)據(jù)元素所占存儲(chǔ)量↑所有數(shù)據(jù)元素的存儲(chǔ)位置均取決于第一個(gè)數(shù)據(jù)元素的存儲(chǔ)位置。

LOC(ai)=LOC(a1)+(i-1)×C

↑基地址38【例1】一個(gè)大小為10的一維數(shù)組A，每個(gè)數(shù)組元素用相鄰的8個(gè)字節(jié)存儲(chǔ)。假設(shè)存儲(chǔ)數(shù)組元素A[０]的第一個(gè)字節(jié)的地址是1020，則A[6]的第一個(gè)字節(jié)的地址是

1068LOC(a6)=LOC(a1)+8*(6-0)=1020+8×(6-0)=1068解：地址計(jì)算通式為：LOC(ai)=LOC(a1)+L*（i-1）39#defineMAXNUM

<順序表最大元素個(gè)數(shù)>typedefstruct{

}Sqlist；4.順序存儲(chǔ)結(jié)構(gòu)（1）靜態(tài)分配的順序存儲(chǔ)結(jié)構(gòu)Elemtypeelem[MAXNUM];intlength;40靜態(tài)順序表：lengthelem[MAXNUM]3265896例如：MAXNUM=1241（2）動(dòng)態(tài)分配的順序存儲(chǔ)結(jié)構(gòu)※typedefstruct{

}SqList;//俗稱順序表const

intLIST_INIT_SIZE=80;//線性表存儲(chǔ)空間的初始分配量ElemType*elem;//存儲(chǔ)空間基址int

listsize;//當(dāng)前分配的存儲(chǔ)容量intlength;

//當(dāng)前長(zhǎng)度42動(dòng)態(tài)順序表*elemlengthlistsize例如：742000H2000H472000H3578432.2.2順序表的基本操作InitList(&L)//結(jié)構(gòu)初始化LocateElem(L,e,compare())//查找ListInsert(&L,i,e)//插入元素ListDelete(&L,i,&e)//刪除元素//(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType))//free(T)StatusListCreate_Sq(SqList&L,intn)44預(yù)定義常量和類型：//函數(shù)結(jié)果狀態(tài)代碼#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineOVERFLOW-2//Status是函數(shù)的類型，其值是函數(shù)結(jié)果狀態(tài)代碼typedefintStatus;45StatusInitList_Sq(SqList&L){//構(gòu)造一個(gè)空的線性表

}//InitList_Sq算法時(shí)間復(fù)雜度：O(1)L.elem=new

ElemType[LIST_INIT_SIZE];if(!L.elem)exit(OVERFLOW);L.length=0;L.listsize=LIST_INIT_SIZEreturnOK;1.初始化動(dòng)態(tài)分配內(nèi)存設(shè)置順序表的大小46例如：在順序表中查找元素23754138546217L.elemL.lengthL.listsizee=38pppppi12341850p2.查找元素47

int

LocateElem_Sq(SqListL,ElemTypee){

//

在順序表中查詢第一個(gè)滿足判定條件的數(shù)據(jù)元素，

//若存在，則返回它的位序，否則返回0}//LocateElem_Sq

O(ListLength(L))算法的時(shí)間復(fù)雜度為：i=1;

//i的初值為第1元素的位序p=L.elem;

//p的初值為第1元素的存儲(chǔ)位置while(i<=L.length&&(*p++!=e))++i;if(i<=L.length)returni;elsereturn0;48線性表操作

ListInsert(&L,i,e)的實(shí)現(xiàn)：首先分析:插入元素時(shí)，線性表的邏輯結(jié)構(gòu)發(fā)生什么變化？3.插入元素49

(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>表的長(zhǎng)度增加1502118307542568721183075例如：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;p*q=e;實(shí)現(xiàn)步驟：移動(dòng)元素插入元素51L.length>=L.listsize//當(dāng)前存儲(chǔ)空間已滿，不能插入i<1||i>L.length+1//

插入位置不合法

事先應(yīng)判斷:插入位置i是否合法?表是否已滿?注意：52算法思想：1、進(jìn)行合法性檢查：

1<=i<=L.length+12、檢查線性表是否已滿

3、將第n個(gè)至第i個(gè)元素逐一后移一個(gè)單元4、在第i個(gè)位置處插入新元素5、將表的長(zhǎng)度加1.53

StatusListInsert_Sq(SqList&L,inti,ElemTypee){

//

在順序表L的第i個(gè)元素之前插入新的元素e,}//ListInsert_Sq

算法時(shí)間復(fù)雜度為:O(ListLength(L))q=&(L.elem[i-1]);//q指示插入位置for(p=&(L.elem[L.length-1]);p>=q;--p)*(p+1)=*p;

//插入位置及之后的元素右移*q=e;//插入e++L.length;//表長(zhǎng)增1returnOK;if(i<1||i>L.length+1)returnERROR;元素右移if(L.length>=L.listsize

)returnOVERFLOW;54考慮移動(dòng)元素的平均情況:

假設(shè)在第

i個(gè)元素之前插入的概率為，

則在長(zhǎng)度為n的線性表中插入一個(gè)元素所需移動(dòng)元素次數(shù)的期望值為：

若假定在線性表中任何一個(gè)位置上進(jìn)行插入的概率都是相等的，則移動(dòng)元素的期望值為：55線性表操作

ListDelete(&L,i,&e)的實(shí)現(xiàn)：首先分析：刪除元素時(shí)，線性表的邏輯結(jié)構(gòu)發(fā)生什么變化？4.刪除元素56

(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>表的長(zhǎng)度減少1a1a2

…ai-1ai

ai+1

…ana1a2

…ai-1

572118307542568721183075L.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)p實(shí)現(xiàn)步驟：移動(dòng)元素58(L.length=0)//當(dāng)前存儲(chǔ)空間為空，不能刪除(i<1)||(i>L.length)//

刪除位置不合法

事先應(yīng)判斷:刪除位置i是否合法?表是否為空?注意：59算法思想：1、進(jìn)行合法性檢查：

1<=i<=L.length2、檢查線性表是否為空

3、將第i+1個(gè)至第n個(gè)元素逐一前移一個(gè)單元4、將表的長(zhǎng)度減1.60StatusListDelete_Sq(SqList&L,inti,ElemType&e){}//ListDelete_Sqfor(++p;p<=q;++p)*(p-1)=*p;//

刪除元素--L.length;//表長(zhǎng)減1returnOK;算法時(shí)間復(fù)雜度為:

O(ListLength(L))p=&(L.elem[i-1]);//p為被刪除元素的位置e=*p;//被刪除元素的值賦給eq=L.elem+L.length-1;//表尾元素的位置if((i<1)||(i>L.length))returnERROR;元素左移if(L.length==0)returnERROR;61考慮移動(dòng)元素的平均情況:

假設(shè)刪除第

i個(gè)元素的概率為

,則在長(zhǎng)度為n的線性表中刪除一個(gè)元素所需移動(dòng)元素次數(shù)的期望值為：若假定在線性表中任何一個(gè)位置上進(jìn)行刪除的概率都是相等的，則移動(dòng)元素的期望值為：62typedefintElemType;

StatusListCreate_Sq(SqList&L,intn){//創(chuàng)建順序表}//ListCreate_SqreturnOK;for(inti=1;i<=n;++i){ cin>>x; L.elem[i-1]=x; ++L.length; }5.創(chuàng)建順序表632.2.3利用上述定義的順序結(jié)構(gòu)可以實(shí)現(xiàn)其它更復(fù)雜的操作例

2-5(逆置順序表)例

2-6(調(diào)整順序)例

2-4(歸并A、B)64則

歸并兩個(gè)“其數(shù)據(jù)元素按值非遞減有序排列”的有序表LA和LB，求得有序表LC也具有同樣特性。（用順序表實(shí)現(xiàn)）設(shè)

La=(a1,…,ai,…,an)

Lb=(b1,…,bj,…,bm)

Lc=(c1,…,ck,…,cm+n)【例

2-4】k=1,2,…,m+n65LA＝（1，3，4，9，10）LB＝（2，5，6，7，8）LC＝(1，2，3，4，5，6，7，8，9，10)Legth=5

Legth=5

Legth=10例如：6613942567PaPa_lastPb_lastPbLaLb8LcPc1234567810910算法思路ElemType*pa,*pb,*pc,*pa_last,*pb_last;pa=La->elem;pa_last=La->elem+La->length-1;pb=Lb->elem;pb_last=Lb->elem+Lb->length-1;Lc->listsize=Lc->length=La->length+Lb->length;if(*pa<=*pb)*pc++=*pa++;else*pc++=*pb++;pa<=pa_last&&pb<=pb_last

第二步歸并（將剩余元素插入到Lc末尾）第一步歸并結(jié)束第二步歸并結(jié)束67

while((i<LA.length)&&(j<LB.length)) if(LA.elem[i]<=LB.elem[j]){

LC.elem[k]=LA.elem[i]; i++;k++; } else{

LC.elem[k]=LB.elem[j]; j++;k++;}

voidMerge_sq(SqList&LC,SqListLA,SqListLB){

i=0,j=0,k=0;

LC.length=LA.length+LB.length;68

while(j<LB.length){ LC.elem[k]=LB.elem[j]; j++;k++;

}

while(i<LA.length){ LC.elem[k]=LA.elem[i]; i++;k++;

}

}//Merge_sq69設(shè)有一個(gè)順序表A，包含n個(gè)數(shù)據(jù)元素。編寫一個(gè)算法，將順序表A逆置，只允許在原表的存儲(chǔ)空間外再增加一個(gè)附加的工作單元?！纠?-5】70LA＝（21，62，8，9，11，25，20）

LA＝（20，25，11，9，8，62，21）逆置后：

i逆置前：

j附加單元tempLA＝（20，62，8，9，11，25，21）

temp＝LA(i);LA(i)=LA(j);LA(j)=temp

i

j71

temp=L.elem[i];L.elem[i]=L.elem[n-i-1];L.elem[n-i-1]=temp;

for(i=0;i<m;++i){}voidinvert_sq(SqList&L)

{

n=L.length;i=0,m=n/2;}//invert_sq72設(shè)有一個(gè)順序表A，包含n個(gè)數(shù)據(jù)元素。調(diào)整順序表A，使其左邊的所有元素均小于0，使其右邊的所有元素均大于0?！纠?-6】73LA＝（-62，-8，-25，20，9，8，21）調(diào)整前：LA＝（21，-62，8，9，-8，-25，20）

iLB＝（）xy調(diào)整后：LB＝（21）yxLA＝（21，-62，8，9，-8，-25，20）

iLB＝（-6221）yxLA＝（21，-62，8，9，-8，-25，20）

i與0比較74

if(LA.elem[i]<0){ LB.elem[x]=LA.elem[i];x++;}//前置

else{LB.elem[y]=LA.elem[i]; y--; }for(i=0;i<n;i++)voidadjust_sq(SqList&LA)

{

InitList_Sq(LB);

n=LA.length;x=0;y=n-1;}//adjust_sqfor(i=0;i<n;++i)LA.elem[i]=LB.elem[i];DestroyList(LB);75優(yōu)點(diǎn)：邏輯相鄰，物理相鄰可隨機(jī)存取任一元素存儲(chǔ)空間使用緊湊缺點(diǎn)：插入、刪除操作需要移動(dòng)大量的元素預(yù)先分配空間需按最大空間分配，利用不充分表容量難以擴(kuò)充順序存儲(chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)762.3.1單鏈表2.3.2單向循環(huán)鏈表2.3.3雙鏈表2.3.4雙向循環(huán)鏈表2.3線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)771.概述用一組地址任意的存儲(chǔ)單元存放線性表中的數(shù)據(jù)元素。2.3.1單鏈表以元素(數(shù)據(jù)元素的映象)

+指針(指示后繼元素存儲(chǔ)位置)=結(jié)點(diǎn)數(shù)據(jù)域指針域結(jié)點(diǎn)結(jié)構(gòu)數(shù)據(jù)域：元素本身信息指針域：指示直接后繼的存儲(chǔ)位置78ZHAOQIANSUNLIZHOUWUZHENGWANG^H例線性表(ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)43131NULL3771925數(shù)據(jù)域指針域LIQIANSUNWANGWUZHAOZHENGZHOU存儲(chǔ)地址1713192531374331H頭指針79

以線性表中第一個(gè)數(shù)據(jù)元素

的存儲(chǔ)地址作為線性表的地址，稱作線性表的頭指針。頭結(jié)點(diǎn)

a1a2…...an^頭指針頭指針

有時(shí)為了操作方便，在第一個(gè)結(jié)點(diǎn)之前虛加一個(gè)“頭結(jié)點(diǎn)”，以指向頭結(jié)點(diǎn)的指針為鏈表的頭指針。空指針以“結(jié)點(diǎn)的序列”表示線性表

稱作鏈表h空表^單鏈表的一般圖示法80上例鏈表的邏輯結(jié)構(gòu)示意圖有以下兩種形式：①ZHAOQIANLISUNZHOUWUZHENG/\WANGH②ZHAOQIANLISUNZHOUWUZHENG/\WANGH區(qū)別：①無(wú)頭結(jié)點(diǎn)②有頭結(jié)點(diǎn)81

typedefstructLNode{ElemTypedata;//數(shù)據(jù)域

structLnode*next;//指針域

}LNode,*LinkList;

2.結(jié)點(diǎn)和單鏈表的C語(yǔ)言描述LinkListL；//L為單鏈表的頭指針數(shù)據(jù)域指針域結(jié)點(diǎn)結(jié)構(gòu)823.單鏈表的運(yùn)算GetElem(L,i,e)//取第i個(gè)數(shù)據(jù)元素ListInsert(&L,i,e)//插入數(shù)據(jù)元素ListDelete(&L,i,e)//刪除數(shù)據(jù)元素ClearList(&L)//重置線性表為空表CreateList(&L,n)

//生成含n個(gè)數(shù)據(jù)元素的鏈表83(1)單鏈表元素的讀取GetElem(L,i,&e)L1p5^j=1假設(shè)i=2j<ij=j+1=2j=i找到！?。?4L1p5^j=1j<ij=j+1=2j<i假設(shè)i=4j=j+1=3j<i=∧沒(méi)找到?。?！非法位置85L1p5^j=1j>i假設(shè)i=0沒(méi)找到?。?！非法位置86

StatusGetElem_L(LinkListL,inti,ElemType&e){//L是帶頭結(jié)點(diǎn)的鏈表的頭指針，以e返回第i個(gè)元素}//GetElem_L算法時(shí)間復(fù)雜度為:O(ListLength(L))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;循環(huán)條件分析：

p=L->next;j=1；while(p&&j<i){p=p->next;++j;}兩個(gè)條件有６種組合：1．P=NULLANDj<i空表且i>1或i>表長(zhǎng)+1，異常，返回NULL2．P=NULLANDj=i空表且i=1或i=表長(zhǎng)+1，異常，返回NULL3．P=NULLANDj>i空表且i<1，異常，返回NULL4．P!=NULLANDj<i繼續(xù)循環(huán)5．P!=NULLANDj=i確定第i個(gè)結(jié)點(diǎn)，正常出循環(huán)6．P!=NULLANDj>ii<1，異常，返回NULL88

(2)插入操作

ListInsert(&L,i,e)xsbapabps->next=p->next;p->next=s;插入前插入后89

因此，在單鏈表中第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)的指針。90StatusListInsert_L(LinkList&L,inti,ElemTypee){

//L為帶頭結(jié)點(diǎn)的單鏈表的頭指針，

//在鏈表中第i個(gè)結(jié)點(diǎn)之前插入新的元素e

}//LinstInsert_L算法的時(shí)間復(fù)雜度為:O(ListLength(L))……p=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大于表長(zhǎng)或者小于191s=new

LNode;

//生成新結(jié)點(diǎn)s->data=e;s->next=p->next;p->next=s;//插入returnOK;92(3)刪除操作ListDelete(&L,i,&e)cabpq=p->next;qp->next=q->next;deleteq;93

在單鏈表中刪除第

i個(gè)結(jié)點(diǎn)的基本操作為:找到線性表中第i-1個(gè)結(jié)點(diǎn)，修改其指向后繼的指針。算法思路：94StatusListDelete_L(LinkList&L,inti,ElemType&e){

//刪除以L為頭指針(帶頭結(jié)點(diǎn))的單鏈表中第i個(gè)結(jié)點(diǎn)

}//ListDelete_L算法的時(shí)間復(fù)雜度為:O(ListLength(L))p=L;j=0;while(p->next&&j<i-1){p=p->next;++j;}

//尋找第i個(gè)結(jié)點(diǎn)，并令p指向其前趨if(!(p->next)||j>i-1)

returnERROR;//刪除位置不合理q=p->next;p->next=q->next;

//刪除并釋放結(jié)點(diǎn)e=q->data;deleteq;returnOK;95(4)清空操作ClearList(&L)voidClearList(&L){//將單鏈表重新置為一個(gè)空表

while(L->next){

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

}}//ClearListDeletep;算法時(shí)間復(fù)雜度：O(ListLength(L))96（5）如何從線性表得到單鏈表？鏈表是一個(gè)動(dòng)態(tài)的結(jié)構(gòu)，它不需要預(yù)分配空間，因此生成鏈表的過(guò)程是一個(gè)結(jié)點(diǎn)“逐個(gè)插入”的過(guò)程。97頭插法思路：^Ldatanextpdatanextpp->next=L->nextL->next=p(1)建立一個(gè)“空表”；(2)輸入數(shù)據(jù)元素an，建立結(jié)點(diǎn)并插入；(3)輸入數(shù)據(jù)元素an-1，建立結(jié)點(diǎn)并插入；(4)依次類推，直至輸入a1為止。逆位序輸入該方法生成鏈表的結(jié)點(diǎn)次序與輸入順序相反。98voidCreateList_L(LinkList&L,intn){//逆序輸入n個(gè)數(shù)據(jù)元素，建立帶頭結(jié)點(diǎn)的單鏈表}//CreateList_L算法的時(shí)間復(fù)雜度為:O(Listlength(L))L=newLNode;L->next=NULL;

//先建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表for(i=n;i>0;--i){p=newLNode;

cin>>

p->data;//輸入元素值

p->next=L->next;L->next=p;//插入}99尾插法思路（正位序輸入）：^Ldatanextppdatanextp->next=L->nextL->next=pp->next=L->next->nextL->next->next=pL->next->next->.......->next???100尾插法思路：^Ldatanextpspdatanextp->next=s->nexts->next=p注意：

⒈采用尾插法建表，生成的鏈表中結(jié)點(diǎn)的次序和輸入順序一致。

⒉必須增加一個(gè)尾指針s,使其始終指向當(dāng)前鏈表的尾結(jié)點(diǎn)。101voidCreateList_L(LinkList&L,intn){//正序輸入n個(gè)數(shù)據(jù)元素，建立帶頭結(jié)點(diǎn)的單鏈表}//CreateList_L算法的時(shí)間復(fù)雜度為:O(Listlength(L))L=newLNode;L->next=NULL;S=L;//

建立帶頭結(jié)點(diǎn)/尾指針的單鏈表for(i=1;i<=n;++i){p=newLNode;

cin>>

p->data;//輸入元素值

p->next=S->next;S->next=p;S=p;//插入}102則

歸并兩個(gè)“其數(shù)據(jù)元素按值非遞減有序排列”的有序表LA和LB，求得有序表LC也具有同樣特性。（用單鏈表實(shí)現(xiàn)）設(shè)

La=(a1,…,ai,…,an)

Lb=(b1,…,bj,…,bm)

Lc=(c1,…,ck,…,cm+n)【例

2-7】鏈表的應(yīng)用。k=1,2,…,m+n103算法分析：搜索：需要兩個(gè)指針?biāo)阉鲀蓚€(gè)鏈表；比較：比較結(jié)點(diǎn)數(shù)據(jù)域中數(shù)據(jù)的大小；插入：將兩個(gè)結(jié)點(diǎn)中數(shù)據(jù)小的結(jié)點(diǎn)插入新鏈表。1043

5

8

11^

2

6

7

12^9

Pa、Pb用于搜索La和Lb，Pc指向新鏈表當(dāng)前結(jié)點(diǎn)LaLbPbPaLcPc=∧不需要重建結(jié)點(diǎn)空間，只要修改指針即可105voidMergeList_L(LinkListLa,LinkListLb,LinkList&Lc){//合并兩個(gè)有序表

}//MergeList_Lpa=La->next;pb=Lb->next;//p指向第一個(gè)結(jié)點(diǎn)

Lc=pc=La;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;}

106假如x=3y=6算法思路：138459L^Pqqq【例2-8】設(shè)計(jì)一個(gè)算法，要求刪除線性表中介于x和y之間的數(shù)據(jù)。107voiddel_LQ(LinkListL,intx,inty){}//del_LQp=L;while(p->next){if(p->next->data>=x&&p->next->data<=y) {

q=p->next; p->next=q->next; delete(q); } else p=p->next;}線性表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)：(1).

邏輯上相鄰的元素，其物理位置不一定相鄰；元素之間的鄰接關(guān)系由指針域指示。(2).鏈表是非隨機(jī)存取存儲(chǔ)結(jié)構(gòu)；對(duì)鏈表的存取必須從頭指針開始。(3).鏈表是一種動(dòng)態(tài)存儲(chǔ)結(jié)構(gòu)；鏈表的結(jié)點(diǎn)可調(diào)用new()申請(qǐng)和delete()釋放。(4).插入刪除運(yùn)算非常方便；只需修改相應(yīng)指針值。109單鏈表的特點(diǎn)：1．它是一種動(dòng)態(tài)結(jié)構(gòu)，整個(gè)存儲(chǔ)空間為多個(gè)鏈表共用。2．指針占用額外存儲(chǔ)空間。3．在鏈表中，元素的“位序”概念淡化，結(jié)點(diǎn)的“位置”概念加強(qiáng)。4．不能隨機(jī)存取，查找速度慢,但是插入、刪除操作很方便。1101.定義：最后一個(gè)結(jié)點(diǎn)的指針域的指針又指回第一個(gè)結(jié)點(diǎn)的鏈表，使鏈表構(gòu)成環(huán)狀。a1a2…...an

帶頭結(jié)點(diǎn)的單循環(huán)鏈表h空表2.3.2單向循環(huán)鏈表111特點(diǎn)：從表中任一結(jié)點(diǎn)出發(fā)均可找到表中其他結(jié)點(diǎn)，提高查找效率。單循環(huán)鏈表a1a2…...an

帶頭結(jié)點(diǎn)的單循環(huán)鏈表112typedefstructLNode{

ElemTypedata; structLNode*next;}LNode,*CircleLinkList;2.存儲(chǔ)結(jié)構(gòu)（和單鏈表相同）113與單鏈表基本一致,它們僅在循環(huán)終止條件上有所不同。3.基本操作單鏈表：p==NULL或p->next==NULL循環(huán)鏈表：p==L或p->next==L114頭插法LdatanextpdatanextpL->next=p;（1）單向循環(huán)鏈表創(chuàng)建p->next=L->next;115頭插法voidCreatListF(CircleLinkList&L){

}//CreatListFcharch;

L=newLNode;//頭指針

L->next=L;

//鏈表開始為空

ch=getchar();//讀入第1個(gè)字符

while(ch!='\n'){

p=newLNode;//生成新結(jié)點(diǎn)

p->data=ch;

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

ch=getchar();

//讀入下一字符

}

116尾插法Ldatanextprpdatanextp->next=Lr->next=p;117尾插法voidCreatListR(CircleLinkList&L){

}//CreatListR

L=newLNode;//頭指針

L->next=L;

//鏈表開始為空

r=L;//設(shè)置尾指針初值

ch=getchar();//讀入第1個(gè)字符

while(ch!='\n'){

p=newLNode;

p->data=ch;

p->next=L;//將新結(jié)點(diǎn)插到r之后

r->next=p;

r=p;//尾指針指向新表尾

ch=getchar();

//讀入下一字符

}//endwhile118（2）單向循環(huán)鏈表元素的讀取L1p5j=1假設(shè)i=2j<ij=j+1=2j=i找到?。。?19L1p5j=1j<ij=j+1=2j<i假設(shè)i=4j=j+1=3j<i=L沒(méi)找到?。。?20L1p5j=1j>i假設(shè)i=0沒(méi)找到?。?！121xsbapabps->next=p->next;p->next=s;插入前插入后（3）單向循環(huán)鏈表的插入（同單鏈表）122cabpq=p->next;qp->next=q->next;deleteq;（4）單向循環(huán)鏈表的刪除（同單鏈表）1232.3.3雙向鏈表∧∧L空雙向鏈表：非空雙向鏈表：∧L∧ABbcapp->prior->next=p=p->next->prior;priordatanext124結(jié)構(gòu)定義typedefstructDBLNode{ElemTypedata;

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

structDBLNode*prior;

//指向前驅(qū)的指針域

structDBLNode*next;

//

指向后繼的指針域}DBLNode,*DBLinkList;priordatanext1252.3.4雙向循環(huán)鏈表L空雙向循環(huán)鏈表：非空雙向循環(huán)鏈表：LABbcapp->prior->next=p=p->next->proir;1261.結(jié)構(gòu)定義typedefstructDBLNode{ElemTypedata;

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

structDBLNode*prior;

//指向前驅(qū)的指針域

structDBLNode*next;

//

指向后繼的指針域}DBLNode,*DBLinkList;priordatanext1272.雙向循環(huán)鏈表的操作InitDBList(&DL)LocateDBList(DL,i)LocateDBNode(DL,key)InsertDBNode(&DL,i,x)DeleteDBNode(&DL,inti)CreateDBList(&DL)128voidInitDblList(DBLinkList&DL)

{//初始化雙向循環(huán)鏈表

}//InitDblListDL=newDBLNode;if(DL==NULL){cout<<"存儲(chǔ)分配錯(cuò)!\n";exit(1); }DL->prior=DL->next=DL;

//表頭結(jié)點(diǎn)的鏈指針指向自己(1)初始化雙向循環(huán)鏈表129DBLNode*LocateDBList(DBLinkListDL,inti)

{//按位查找

}//LocateDBListp=DL->next;

j=1;while(p!=DL&&j<i){ p=p->next;j++; } if(p==DL||j>i)returnNULL; elsereturnp;(2)在雙向循環(huán)鏈表中按位查找130DBLNode*LocateDBNode(DBLinkListDL,ElemTypekey)

{//按值查找

}//LocateDBNodep=DL->next;

while(p!=DL&&key!=p->data) p=p->next; if(p==DL)returnNULL; elsereturnp;(3)在雙向循環(huán)鏈表中按值查找131(4)雙向循環(huán)鏈表的前插操作算法voiddinsertbefor(DBLNode*p，ElemTypex){

q=newDBLNode;q—>data=x;

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

q—>prior=p—>prior;

q—>next=p;

p—>prior—>next=q;

p—>prior=q;}算法時(shí)間復(fù)雜度為:

O(1)xqbaP132intInsertDblNode(DBLinkList&DL,inti,ElemTypex)

{//前插法

}//InsertDblNodep=LocateDBList(DL,i);//指針定位于插入位置if(!p)returnERROR;q=newDBLNode;//分配結(jié)點(diǎn)q->data=x;q->prior=p->prior;q->next=p;//插入結(jié)點(diǎn)p->prior->next=q; p->prior=q;133(5)雙向鏈表的后插操作算法voi