第二章 線性表

主講人：張新彩

phonenumber/p>

E-mail:zhangxincail2345@163.com

???

■集合°oo

■線性結(jié)構(gòu)OOOO

■樹型結(jié)構(gòu)

■圖型結(jié)構(gòu)

第二章線性表二f-5

■線性結(jié)構(gòu)的特點(diǎn)：在數(shù)據(jù)元素中的非空有限集中

■(1)存在唯一的一個被稱作“第一個”的數(shù)據(jù)元素；

■(2)存在唯一的一個被稱作“最后一個”的數(shù)據(jù)元

素；

■(3)除第一個外，集合中的每一個數(shù)據(jù)元素均只有

一個前驅(qū)；

■(4)除最后一個外，集合中的每一個數(shù)據(jù)元素均只

有一個后繼。

2.1線性表的類型定義W

1.線性表

■線性表(LinearList)：一個線性表是n個數(shù)據(jù)元素的有

限序列。例如：

■例1、26個英文字母組成的字母表

-(A,B,C,??.，Z)

■例2、某校從1999年到2003年各種型號的計算機(jī)擁有

量的變化情況。

-(6,17,28,50,92,188)

-在稍復(fù)雜的線性表中，一個數(shù)據(jù)元素可以由若干個數(shù)

據(jù)項(xiàng)組成。在這種情況下，常把數(shù)據(jù)元素稱為記錄，

含有大量記錄的線性表又稱為文件。

■例3、學(xué)生健康情況登記表如下:

姓名學(xué)號性別年齡健康情況

王小林790631男18健康

陳紅790632女20一般

劉建平790633男21健康

張立立790634男17神經(jīng)衰弱

?????????????????????????????????????

1.線性表

-可見，線性表中的數(shù)據(jù)元素可以是各種各樣的，但同

一線性表中的元素必定具有相同特征，即屬同一數(shù)據(jù)

對象，相鄰數(shù)據(jù)元素之間存在著序偶關(guān)系。若將線性

表記為：

■則表中為“領(lǐng)先于詼，為領(lǐng)先于aj+i,稱a.1是如的自接

前驅(qū)元素，如+i是藥的直接后繼元素。

■當(dāng)i=l,2,…時，如有且僅有一個直接后繼，當(dāng)

i=2,3,…聲時，語有且僅有一個直接前驅(qū)。

■線性表中的元素的個數(shù)n(n20)定義為線性表的長度,

n=0時稱為空表。

■線性表的特點(diǎn)可概括如下：

■同一性：線性表由同類數(shù)據(jù)元素組成，每一個如

必須屬于同一數(shù)據(jù)對象。

■有窮性：線性表由有限個數(shù)據(jù)元素組成，表長度

就是表中數(shù)據(jù)元素的個數(shù)。

■有序性：線性表中表中相鄰數(shù)據(jù)元素之間存在著

序偶關(guān)系va”ai+1>o

2.抽象數(shù)據(jù)類型線性表

■ADTList{

■數(shù)據(jù)對象：={ai|aiGElemSet,i=l,2,...,n,ii>0}

■數(shù)據(jù)關(guān)系：Rl={<ai.nai>|%.科，eD,i=2,…,n}

〃稱i為％在線性表中的位序。

■基本操作：

■InitList(&L)

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

2.抽象數(shù)據(jù)類型線性表

■DestroyList(&L)

初始條件：線性表L已經(jīng)存在。

操作結(jié)果：銷毀線性表L。

■ClearList(&L)

初始條件：線性表L已經(jīng)存在。

操作結(jié)果：將L置為空表。

■ListEmpty(L)

初始條件：線性表L已經(jīng)存在。

操作結(jié)果：若L為空表，貝I」返回TRUE,否則返回FALSE。

2.抽象數(shù)據(jù)類型線性表

■ListLength(L)

初始條件：線性表L已經(jīng)存在。

操作結(jié)果：返回L中數(shù)據(jù)元素個數(shù)。

■GetElem(L,i9&e)

初始條件：線性表L已經(jīng)存在，l?i?Listlength(L)。

操作結(jié)果：用e返回L中第i個數(shù)據(jù)元素的值。

■LocateElem(L,e,compare())

初始條件:線性表L已經(jīng)存在,compare是數(shù)據(jù)元素判定函數(shù)。

操作結(jié)果：返回L中第一個與e滿足關(guān)系compare。的數(shù)據(jù)

元素的位序。若這樣的元素不存在，則返回值為0。

2.抽象數(shù)據(jù)類型線性表

■ListInsert(&L,i,e)

■初始條件:線性表L已經(jīng)存在，且lWi〈Listlength(L)+l。

■操作結(jié)果：在L中第i個位置之前插入新的數(shù)據(jù)元素e,L的

長度加1。

■ListDelete(&L,i,&e)

■初始條件：線性表L已經(jīng)存在且非空，且ki?Listlength(L)。

■操作結(jié)果：刪除L中的第i個數(shù)據(jù)元素，并用e返回其值，L

的長度減1。

■}ADTList

3.例題

例2-1

■利用兩個線性表LA和LB分別表示兩個集合A和B,現(xiàn)

要求一個新的集合A=AUB。只要從線性表LB中依次

取得每個數(shù)據(jù)元素，并依值在線性表LA中進(jìn)行查訪，

若不存在，則插入。

3.例題

voidunion(List&La,ListLb)

La_len=Listlength(La);Lb」en=Listlength(Lb);〃線性表長

for(i=l;i<=Lb_len;i++)

GetElem(Lb,i,e);〃取Lb中的第個i元素賦給e

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

Listinsert(La,++La_len,e);

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

}//union

例2-2

-巳知線性表LA和線性表LB中的數(shù)據(jù)元素按值非遞減

有序排列，現(xiàn)要求將LA和LB歸并為一個新的線性表

LC且LC中的元素仍按值非遞減有序排列。

■例LA=(3,5,8,11)

LB=(2,6,8,9,11,15,20)

則LC=(2,3,5,6,8,8,9,11,11,15,20)

3.例題

-從上面的問題要求可知，LC中的數(shù)據(jù)元素或是LA中

的數(shù)據(jù)元素，或是LB中的數(shù)據(jù)元素，則只要先設(shè)LC

為空表，然后將LA或LB中的元素逐個插入到LC中即

可。

■設(shè)兩個指針i和j分別指向LA和LB中某個元素，設(shè)i當(dāng)

前所指的元素為a,j當(dāng)前所指的元素為b,則當(dāng)前應(yīng)

插入到LC中的元素c為

4,當(dāng)446時

c二4，

6,當(dāng)a>8時

3.例題

voidmergelist(listLa,listLb,list&Lc)

(

InitList(Lc)；i=j=l;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);

if(ai<=bj){ListInsert(Lc,++k,ai);++i;}

else{ListInsert(Lc,++k,bj);++j;}

)

3.例題

while(i<=La_len)

(

GetElem((La,i++,ai);ListInsert(Lc,++k,ai);

)

while(j<=Lb_len)

(

GetElem((Lb,j++,bj);ListInsert(Lc,++k,bj);

}//MergeList

3.例題

■上述兩個算法的時間復(fù)雜度取決于抽象數(shù)據(jù)類型list定

義中基本操作的執(zhí)行時間。假如GetElem和Listinsert

這兩個操作的執(zhí)行時間和表長無關(guān)，LocateElem的執(zhí)

行時間和表長成正比。

■則算法2?1的時間復(fù)雜度為

-O(ListLength(LA)xListLength(LB)

■算法2.2的時間復(fù)雜度則為

-O(ListLength(LA)+ListLength(LB)

2.2線性表的順序存儲結(jié)構(gòu)

一、線性表的順序表示

■線性表的順序表示指的是用一組地址連續(xù)的存儲單元

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

■假設(shè)線性表的每個元素需占用A個存儲單元，并以所

占的第一個單元的存儲地址作為數(shù)據(jù)元素的存儲位置。

則線性表中第i+1個數(shù)據(jù)元素的存儲位置LOC(aiQ和

第i個數(shù)據(jù)元素的存儲位置LOC(%)之間滿足下列關(guān)系:

LOC(a1+i)=LOC(a1)+左

一、線性表的順序表示

n

空閑

圖2.2順序表存儲示意圖

一、線性表的順序表示

-一般來說，線性表的第i個數(shù)據(jù)元素%的存儲位置為:

LOC(ai)=LOC(a1)+(i-1)*^

■線性表的這種機(jī)內(nèi)表示稱作線性表的順序存儲結(jié)構(gòu),

稱這種存儲結(jié)構(gòu)的線性表為順序表。

一、線性表的順序表示

■例：一個向量的第一個存儲地址是1000,每個元素的

長度為4,則第5個元素的地址是多少？

■解：Loc(5)=Loc(ax)+(i-1)*k

=1000+(5-1)*4

=1016

一、線性表的順序表示

-順序存儲的結(jié)構(gòu)特點(diǎn)：

■(1)以數(shù)據(jù)元素在計算機(jī)“物理位置相鄰”來表示

表中數(shù)據(jù)元素間的邏輯關(guān)系。

■(2)能隨機(jī)存取表中任一數(shù)據(jù)元素，換言之，數(shù)據(jù)

元素在順序表中的存儲位置取決于該數(shù)據(jù)元素在線性

表中的順序號。

■例如：一個班學(xué)生集體出游，按學(xué)號分配房間

一、線性表的順序表示

-由于C語言中的一維數(shù)組也是采用順序存儲表示，故

可以用數(shù)組類型來描述順序表。除了用數(shù)組來存儲線

性表的元素之外，順序表還應(yīng)該用一個變量來表示線

性表的長度屬性，所以我們用結(jié)構(gòu)類型來定義順序表

類型。

一、線性表的順序表示

■結(jié)構(gòu)體定義的語法形式如下：

struct結(jié)構(gòu)體標(biāo)識符

（

成員變量列表；

）；

在｛｝之間通過分號分割的變量列表稱為成員變量

（structuremember）,用于描述此類事物的某一方面特

性。

■成員變量可以為基本數(shù)據(jù)類型（如float）、數(shù)組和指針類

型，也可以為結(jié)構(gòu)體。

一、線性表的順序表示

structStudent

nunr付十lJ

{?

name-字節(jié)

intnum;?20

sexI1字節(jié)

charname[20];

age-,2子下

charsex;

intage;score(,4字節(jié)

floatscore;

charaddr[30];add「30字節(jié)

一、線性表的順序表示

-在完成一個結(jié)構(gòu)體定義之后，就可以像定義基本數(shù)據(jù)

類型變量一樣，定義結(jié)構(gòu)體類型的變量和數(shù)組。

■structStudentStul;/*定義structStudent類型變量*/

一、線性表的順序表示

■為了描述三維世界中的坐標(biāo)點(diǎn)，可以定義結(jié)構(gòu)體stnict

Point如下：

structPoint

doublex;/*x坐標(biāo)*/

doubley;/*y坐標(biāo)*/

doublez;/*z坐標(biāo)*/

｝；

一、線性表的順序表示

-引用規(guī)則：結(jié)構(gòu)體變量不能整體引用，只能引用變量

成員

■引用方式：結(jié)構(gòu)體變量名.成員名

其中，是成員訪問運(yùn)算符

■如：structPointoPl；

oPl.x=0.0,

oPl.y=0.2

oPl.z=0.3

一、線性表的順序表示

■指向結(jié)構(gòu)體的指針

■定義形式：struct結(jié)構(gòu)體名*結(jié)構(gòu)體指針名;

例structstudent*p;

structstudent

p

{intnum;

charname[20];

charsex;

intage;

}stu;

structstudent*p=&stu;

一、線性表的順序表示

-使用結(jié)構(gòu)體指針變量引用成員

結(jié)構(gòu)體指針變量名，成員名

其中，”為指向運(yùn)算符

一、線性表的順序表示

一、線性表的順序表示

#defineLISTINITSIZE100//線性表初始分配量

#defineLISTINCREMENT10〃線性表分配增量

typedefstruct

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

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

intListSize;

〃當(dāng)前分配的存儲容量(以sizeof(ElemType)為單位)

}SqList;

一、線性表的順序表示

■注意：C語言中的數(shù)組下標(biāo)從“0”開始，因此，若L

是SqList類型的順序表，則表中第i個元素是L.elem[i-

l]o

二、順序表上實(shí)現(xiàn)的基本操作不皿二

Y

■順序表上基本運(yùn)算：

令1.順序表的初始化

02.插入運(yùn)算

令3.刪除運(yùn)算

令4.按值查找

二、順序表上實(shí)現(xiàn)的基本操作

1.線性表的初始化

StatusInitList_Sq(SqList&L)

{〃構(gòu)造一個空的線性表L

L.elem=(ElemType*)

malloc(LIST_INIT_SIZE*sizeof(ElemType));

if(!L.elem)

exit(OVERFLOW);

L.length=0;

L.Listsize=LIST_INIT_SIZE;

returnok;

}//InitList_Sq

二、順序表上實(shí)現(xiàn)的基本操作

2.插入

-線性表的插入是指在表的第i個位置上插入一個值為x

的新元素，插入后使原表長為n的表：

ai.pai?ai+p…，an)

成為表長為n+1的表：

(a],a2,…，,x,分計],…，an)l<=i<=n+l

-順序表上完成這一運(yùn)算需要通過以下步驟進(jìn)行:

令(1)將詼an順序向下移動，為新元素讓出位置;

令(2)將x置入空出的第i個位置;

令⑶表長加1。

V數(shù)組下標(biāo)內(nèi)存元素序號V數(shù)組下標(biāo)內(nèi)存

二、順序表上實(shí)現(xiàn)的基本操作

2.插入

例如：已知線性表(4,%15,28,30,30,42,51,62),需在

第4個元素之前插入一個元素“21%則需要將第9個

二、順序表上實(shí)現(xiàn)的基本操作

2.插入

StatusListInsert_Sq(SqList&L,inti,ElemTypee)

{if(i<l||i>L.length+l)returnERROR〃i值不合法

if(L.length>=L.listSize){

〃當(dāng)前存儲空間已滿，增加分配

newbase=(ElemType*)realloc(L.elem,

(L.listsize+LISTINCREMENT)*sizeof(ElemType));

if(!newbase)exit(OVERFLOW);//存儲分配失敗

L.elem=newbase;//新地址

L.listsize+=LISTINCREMENT;〃增加存儲容量}

二、順序表上實(shí)現(xiàn)的基本操作"產(chǎn)Q

2.插入

q=&(L.elem[i-l]);〃q為插入位置

for(p=&(L.elem[L.length-l]);p>=q;-p)*(p+l)=*p;

〃插入位置及之后的元素后移

*q=e;〃插入e

++L.length;//表長增1

returnOK;

}//listlnsertSq

二、順序表上實(shí)現(xiàn)的基本操作心；［人s

2.插入.

■該算法的時間主要花費(fèi)在循環(huán)的結(jié)點(diǎn)后移語句上，由

此可看出，所需移動結(jié)點(diǎn)的次數(shù)不僅依賴于表的長度,

而且還與插入位置有關(guān)。

■在長度為n的線性表中第i個位置上插入一個結(jié)點(diǎn)，令

Eis(n)表示移動結(jié)點(diǎn)的期望值(即移動的平均次數(shù))，

則在第i個位置上插入一個結(jié)點(diǎn)的移動次數(shù)為n-i+L

故

n-l

Eis(n)=2pt(n-i+1)

i=l

二、順序表上實(shí)現(xiàn)的基本操作

2.插入

■不失一般性，假設(shè)在表中任何位置(IWiWn+l)上插入

====1/n+

結(jié)點(diǎn)的機(jī)會是均等的，則P1=P2P3--Pn+l(l)°

因此，在等概率插入的情況下：

1成+1n

E.=i+1)=

9

H+17=1

-也就是說，在順序表上做插入運(yùn)算，平均要移動表上

一半結(jié)點(diǎn)。當(dāng)表長n較大時，算法的效率相當(dāng)?shù)汀Ｒ?/p>

此算法的平均時間復(fù)雜度為O(n)o

二、順序表上實(shí)現(xiàn)的基本操作

3.刪除

-線性表的刪除運(yùn)算是指將表的第i(lWiWn)結(jié)點(diǎn)刪除,

使長度為n的線性表：

寸(為,…a'ftpaj+i…'a)

變成長度為n-1的線性表

(a1,…aj],2計1，…,an)

■順序表上完成這一運(yùn)算的步驟如下:

令(1)將ai+i?/順序向前移動。

令(2)表長減1。

V數(shù)組下標(biāo)內(nèi)存元素序號

i-1Hi+li

iai+2i+1

n-2a。n-1

nn+1n-1n

二、順序表上實(shí)現(xiàn)的基本操作

3.刪除?上一^

■例如：線性表(4,9,15,21,28,30,30,42,51,62)刪除第

5個元素，則需將第6個元素到第10個元素依次向前移

動一個位置，如圖2.4所示。

序號12345678910

491521283030425162

刪除28后4915213030425162

二、順序表上實(shí)現(xiàn)的基本操作

3.刪除

StatusListDelete_Sq(SqList&L,inti,ElemType&e)

if((i<l||i>L.length)returnERROR;〃i值不合法

p=&(L.elem[i-l]);〃p為被刪除元素位置

e=*p;〃被刪除元素值賦給e

q=L?elem+L?length-l;//表尾元素位置

二、順序表上實(shí)現(xiàn)的基本操作

3.刪除Y

for(++p;p<=q;++p)*(p-1)=*p;

〃被刪除元素之后的元素左移

—L.length;〃表長減1

returnOK;

}//listDeleteSq

二、順序表上實(shí)現(xiàn)的基本操作

3.刪除

■該算法的時間分析與插入算法相似，結(jié)點(diǎn)的移動次數(shù)

也是由表長11和位置i決定。

■假設(shè)％是刪除第i個元素的概率，則在長度為n的線性

表中刪除一個元素時所需移動元素次數(shù)的期望值（平

均次數(shù)）為：

E印〃一i)

二、順序表上實(shí)現(xiàn)的基本操作

3.刪除

-不失一般性，假設(shè)在表中任何位置上刪除結(jié)點(diǎn)的機(jī)會

是均等的，則5=1/11。因此，在等概率插入的情況下,

Z7-_--1Z"(〃-Z、)-_--"-一；-1

E①〃j=i2

?也就是說，在順序表上做刪除運(yùn)算，平均要移動表中

約一半的結(jié)點(diǎn)，平均時間復(fù)雜度也是O(n)。

二、順序表上實(shí)現(xiàn)的基本操作

4.按值查找

L.listsize

L.elem1

23754138546217

可見，基本操作是:

將順序表中的元素

逐個和給定值e

e=38〃成功

相比較。

50〃不成功

二、順序表上實(shí)現(xiàn)的基本操作

4.按值查找

intLocateElem_Sq(SqListL,ElemTypee,Status(*

compare)(ElemType,ElemType))

{

inti=l;

p=L.elem;

while(i<=L.length&&!(*compare)(*p++,e))

++i；

if(i<=L.length)

returni;

else

return0;

二、順序表上實(shí)現(xiàn)的基本操作

5.有序表的歸并

voidMergeList_Sq(SqListLa,SqListLb,SqList&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);

pa_last=La.elem+La.length-l;

pb_last=Lb.elem+Lb.length-l;

二、順序表上實(shí)現(xiàn)的基本操作

5.有序表的歸并

while(pa<=pa_last&&pb<=pb_last)

(

if(*pa<=*pb)

*pc++=*pa++;

else

*pc++=*pb++;

)

while(pa<=pa_last)

*pc++=*pa++;

while(pb<=pb_last)

*pc++=*pb++;

)

二、順序表上實(shí)現(xiàn)的基本操作

順序表小結(jié)

-由上面的討論可知，線性表順序表示的優(yōu)點(diǎn)是：

■(1)無需為表示結(jié)點(diǎn)間的邏輯關(guān)系而增加額外的存儲

空間(因?yàn)檫壿嬌舷噜彽脑仄浯鎯Φ奈锢砦恢靡彩?/p>

相鄰的)；

■(2)可方便地隨機(jī)存取表中的任一元素。

二、順序表上實(shí)現(xiàn)的基本操作

順序表小結(jié)：：

-其缺點(diǎn)是：(1)插入或刪除運(yùn)算不方便，除表尾的位

置外，在表的其它位置上進(jìn)行插入或刪除操作都必須

移動大量的結(jié)點(diǎn)，其效率較低；

■(2)由于順序表要求占用連續(xù)的存儲空間，存儲分配

只能預(yù)先進(jìn)行靜態(tài)分配，因此當(dāng)表長變化較大時，難

以確定合適的存儲規(guī)模。若按可能達(dá)到的最大長度預(yù)

先分配表空間，則可能造成一部分空間長期閑置而得

不到充分利用；若事先對表長估計不足，則插入操作

可能使表長超過預(yù)先分配的空間而造成溢出。

2.3線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)

-線性表的順序表示的特點(diǎn)是用物理位置上的鄰接關(guān)系

來表示結(jié)點(diǎn)間的邏輯關(guān)系，這一特點(diǎn)使我們可以隨機(jī)

存取表中的任意結(jié)點(diǎn)，但它也使得插入和刪除操作會

移動大量的數(shù)據(jù)元素。

■由于順序表需要一組地址連續(xù)的存儲單元，對于長度

可變的線性表就需要預(yù)分配足夠的空間，有可能使一

部分存儲空間長期閑置不能充分利用。

■也可能由于估計不足，當(dāng)表長超過預(yù)分配的空間而造

成溢出，在這種情況下，又難以擴(kuò)充連續(xù)的存儲空間。

2.3線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)

■為了克服上述缺點(diǎn)，我們將討論線性表的另一種存儲

方式-鏈?zhǔn)酱鎯Y(jié)構(gòu)，簡稱為鏈表(LinkedList)o

■線性表的鏈?zhǔn)酱鎯Φ奶攸c(diǎn)是指用一組任意的存儲單元

來依次存放線性表的結(jié)點(diǎn)，這組存儲單元既可以是連

續(xù)的，也可以是不連續(xù)的，甚至是零散分布在內(nèi)存中

的任意位置上的。因此，鏈表中結(jié)點(diǎn)的邏輯次序和物

理次序不一定相同。

2.3線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)

-為了能正確表示結(jié)點(diǎn)間的邏輯關(guān)系，在存儲每個結(jié)點(diǎn)

值的同時，還必須存儲指示其后繼結(jié)點(diǎn)的地址(或位

置)信息，這個信息稱為指針(pointer)或鏈

(next)o這兩部分信息組成了元素場的存儲映象，

稱為結(jié)點(diǎn)，它包括兩個域：

datanext

2.3.1線性鏈表.，■的收

Y

datanext

-其中：data域是數(shù)據(jù)域，用來存放結(jié)點(diǎn)的值。next是

指針域（亦稱鏈域），用來存放結(jié)點(diǎn)的直接后繼的地

址（或位置）。

■鏈表正是通過每個結(jié)點(diǎn)的鏈域?qū)⒕€性表的n個結(jié)點(diǎn)按

其邏輯次序鏈接在一起的。

2.3.1線性鏈表

-通常把線性鏈表畫成用箭頭相連接的結(jié)點(diǎn)序列，其中

箭頭表示鏈域中的指針。

■n個結(jié)點(diǎn)如(lv=iv=n)連接成一個鏈表，即為線性表

(aPa2,aj的鏈?zhǔn)酱鎯Y(jié)構(gòu)。由于上述鏈表的

每一個結(jié)點(diǎn)只有一個鏈域，故將這種鏈表稱為單鏈表

(SingleLinked)。

2.3.1線性鏈表

-鏈表中每個結(jié)點(diǎn)的存儲地址是存放在其前驅(qū)結(jié)點(diǎn)next

域中，而開始結(jié)點(diǎn)無前驅(qū)，故應(yīng)設(shè)頭指針head指向開

始結(jié)點(diǎn)。同時，由于終端結(jié)點(diǎn)無后繼，故終端結(jié)點(diǎn)的

指針域?yàn)榭?，即NULL（圖示中也可用人表示）

例:

2.3.1線性鏈表

?由上述可見，單鏈表可由頭指針唯一確定，在C語言

中可用結(jié)構(gòu)體指針來描述：

?線性表的單鏈表存儲結(jié)構(gòu)

typedefstructLNodeElemType為數(shù)據(jù)域的類型，可以

是任何類型。

(

ElemTypedata;Data為數(shù)據(jù)域，存放該結(jié)點(diǎn)的數(shù)

據(jù)；

structLNode*next;

next為指針域，指向該結(jié)點(diǎn)的直

}LNode/LinkList;

接后繼結(jié)點(diǎn)。

2.3.1線性鏈表

-假設(shè)L為LinkList型的變量，則L為單鏈表的頭指針,

它指向表中第一個結(jié)點(diǎn)。

LA

■若L為“空"（L=NULL）,則所表示的線性表為

“空”表，其長度n為“零”。

2.3.1線?性鏈表

-有時，我們在單鏈表的第一個結(jié)點(diǎn)之前附設(shè)一個結(jié)點(diǎn),

稱之為頭結(jié)點(diǎn)。頭結(jié)點(diǎn)的數(shù)據(jù)域可以不存儲任何信息,

也可以存儲如線性表的長度等類的附加信息，頭結(jié)點(diǎn)

的指針域存儲指向第一個元素的存儲位置。

頭結(jié)點(diǎn)

anA

a2

■帶頭結(jié)點(diǎn)的空表表示為：L->next=NULLo

LA空表

2.3.1線?性鏈表

頭指針頭結(jié)點(diǎn)首元結(jié)點(diǎn)

-----r

ai

■頭指針是指向鏈表中第一個結(jié)點(diǎn)（或?yàn)轭^結(jié)點(diǎn)或?yàn)槭?/p>

元結(jié)點(diǎn)）的指針。

■頭結(jié)點(diǎn)是在鏈表的首元結(jié)點(diǎn)之前附設(shè)的一個結(jié)點(diǎn)；數(shù)

據(jù)域內(nèi)只放空表標(biāo)志和表長等信息；

■首元結(jié)點(diǎn)是指鏈表中存儲線性表第一個數(shù)據(jù)元素%的

結(jié)點(diǎn)O

■假設(shè)p是指向線性表中第i個數(shù)據(jù)元素（結(jié)點(diǎn)a）的指針，

■貝i」p->next是指向第i+1個數(shù)據(jù)元素（結(jié)點(diǎn)ai+i）的指針。

■換句話說，若p->data=aj,

貝I」p->next->data=ai+1

■由此，在單鏈表中，取得第i個數(shù)據(jù)元素必須從頭指針

出發(fā)尋找，因此，單鏈表是非隨機(jī)存取的存儲結(jié)構(gòu)。

2.3.1線?性鏈表

1012*1145

■h->data=1012

■(h->next)->data=l145

1.查找運(yùn)算

-在鏈表中，即使知道被訪問結(jié)點(diǎn)的序號3也不能象順

序表中那樣直接按序號i訪問結(jié)點(diǎn)，而只能從鏈表的頭

指針出發(fā)，順鏈域next逐個結(jié)點(diǎn)往下搜索，直到搜索

到第i個結(jié)點(diǎn)為止。因此，鏈表不是隨機(jī)存取結(jié)構(gòu)。

■顯然，查找第i個數(shù)據(jù)元素的基本操作為：移動指針,

比較j和i。j為計數(shù)器。令指針p始終指向線性表中

第j個數(shù)據(jù)元素。

1.查找運(yùn)算

在單鏈表中的實(shí)現(xiàn):

L

2130-75-42-56A

P

p=p->next

i=3

1.查找運(yùn)算

StatusGetElem_L(LinkListL,inti,ElemType&e)

{〃L為帶頭結(jié)點(diǎn)的單鏈表的頭指針。

〃當(dāng)?shù)趇個元素存在時，則將第i個數(shù)據(jù)元素的值賦給e并返

回OK,否則返回ERROR

p=L->next;j=l;〃初始化,p指向第一個結(jié)點(diǎn)，j為計數(shù)

器

while(p&&j<i)

{〃順指針向后查找，直到p指向第i個元素或p為空

p=p->next;++j;

1.查找運(yùn)算

if(!p||j>i)

returnERROR;//第i個元素不存在

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

returnOK;

}//GetElem_L

2.插入運(yùn)算

-在線性表的兩個數(shù)據(jù)元素距“和冬之間插入一個數(shù)據(jù)元

素e,已知p為其單鏈表存儲結(jié)構(gòu)中指向結(jié)點(diǎn)為“的指針。

■在單鏈表中的實(shí)現(xiàn)：

有序?qū)Γ紴椤?a＞

改變?yōu)椤丛?e＞和ve,

2.插入運(yùn)算

■可見，在鏈表中插入結(jié)點(diǎn)只需要修改指針。若

要在第i個結(jié)點(diǎn)之前插入元素，修改的是第i?l

個結(jié)點(diǎn)的指針，但需要先找到第i-1個結(jié)點(diǎn)。

-因此，在單鏈表中第i個結(jié)點(diǎn)之前進(jìn)行插入的基

本步驟為：

令⑴找到線性表中第i-1個結(jié)點(diǎn)，

令(2)修改其指向后繼的指針，插入新結(jié)點(diǎn)。

2.插入運(yùn)算

j=0

2.插入運(yùn)算

2.插入運(yùn)算

2.插入運(yùn)算

2.插入運(yùn)算

datanext

P

步驟1：生成一個數(shù)據(jù)域?yàn)閑的結(jié)點(diǎn)。

用C語句描述為:

s=(LNode*)malloc(sizeof(LNode));

s->data=e;

步驟2：將數(shù)據(jù)元素e插在a,i和由元素之間。

用C語言描述為：

s->next=p->next;

p->next=s;

2.插入運(yùn)算

■注意語句的順序。如改為以下順序，什么情況會發(fā)生?

datanextb結(jié)點(diǎn)的地址？

b

P

關(guān)鍵語句：

s=(LNode*)malloc(sizeof(LNode));

s->data=e;

s->next=p->next;

p->next=s;-

StatusListInsert_L(LinkList&L,inti,ElemTypee){

〃在帶頭結(jié)點(diǎn)的單鏈表L中第i個數(shù)據(jù)元素之前插入數(shù)據(jù)元素e

p=L;j=0;

while(p&&j<i-1)

{p=p->next;++j；}//尋找第i-1個結(jié)點(diǎn)

returnERROR;//i小于1或者大于表長

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

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

p->next=s;

returnOK;

}//LinstlnsertL

3.刪除運(yùn)算?一*,

■刪除線性表中的第i個元素。

■在鏈表中的實(shí)現(xiàn)：

有序?qū)a^,a>和<ai9ai+1>

改變?yōu)椤碼.ai+1>

ai+lA

3.刪除運(yùn)算

-刪除元素如：

data

P

datanext

用c語言語句描述為：

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

3.刪除運(yùn)算

-刪除元素如并釋放之:

datanext

P

步驟1：將距的地址記錄下來

即：q=p->next;

3.刪除運(yùn)算

-刪除元素如并釋放之:

datanext

P

步驟2：讓p?>next指向由后第一個結(jié)點(diǎn)

即：p->next=q->next;

3.刪除運(yùn)算

-刪除元素如并釋放之:

datanext

b

P

步驟3：釋放b結(jié)點(diǎn)

即：free(q);

3.刪除運(yùn)算一，*一

StatusListDelete_L(LinkList&L,inti,ElemType&e){

〃在帶頭結(jié)點(diǎn)的單鏈表L中，刪除第i個元素，并由e返回其值

p=L;j=0;

while(p->next&&j<i-1)

{〃尋找第i個結(jié)點(diǎn)，并令p指向其前趨

p=p->next;++j;}

if(!(p->next)||j>i-1)

returnERROR;〃冊lj除位置不合理

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

e=q->data;free(q);

returnOK;

}//ListDeleteL

4.建立單鏈表

-鏈表是一個動態(tài)的結(jié)構(gòu)，它不需要預(yù)分配空間，因此

生成鏈表的過程是一個結(jié)點(diǎn)“逐個插入”的過程。

）

■例如：逆位序輸入11個數(shù)據(jù)元素的值值11聲11_1..?用2件1,

建立帶頭結(jié)點(diǎn)的單鏈表（ai，a2^.”an）。

4.建立單鏈表

操作步驟：

■L建立一個“空表

-2.輸入數(shù)據(jù)元素an

■3.輸入數(shù)據(jù)元素an.p建立結(jié)點(diǎn)并插入;

■4.依次類推，直至輸入小為止。

Sin-1

4.建立單鏈表

(d)插入第i個元收

頭插法建立單鏈表圖示

4.建立單鏈表

LinkListCreateListL(LinkList&L,intn)

{〃逆序輸入n個數(shù)據(jù)元素，建立帶頭結(jié)點(diǎn)的單鏈表

L=(LinkList)malloc(sizeof(LNode));

L->next=NULL;〃先建立一個帶頭結(jié)點(diǎn)的單鏈表

for(i=n;i>0;—i)

{p=(LinkList)malloc(sizeof(LNode));〃生成新結(jié)點(diǎn)

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

p->next=L->next;//把L的后繼作為p的后繼

L->next=p;//把p插入至［|L后

)

}//Cjrg?teUstJ,一一..

5.單鏈表的合并

令pa:指向La中當(dāng)前節(jié)點(diǎn)的指針;

令pb:指向Lb中當(dāng)前節(jié)點(diǎn)的指針;

Ope:指向Lc中當(dāng)前節(jié)點(diǎn)的指針;

-算法步驟：

令第一步：比較pa->data和pa->data的大?。?/p>

?(1)若pa->data<=pb->data,則將pa所指的節(jié)點(diǎn)插

入到Lc尾部，pa指針后移

?(2)^pa->data>pb->data,貝U將pb所指的節(jié)點(diǎn)插入

至！jLc尾部，pb指針后移

令第二步：將所有剩余的元素插入到Lc尾部。

5.單鏈表的合并

■voidMergeList_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)

5.單鏈表的合并

while(pa&&pb)

if(pa->data<=pb->data)

{pc->next=pa;pc=pa;pa=pa->next;}

else

{〃pc指向Lc中當(dāng)前最后一個結(jié)點(diǎn)

pc->next=pb;pc=pb;pb=pb->next;}

}

pc->next=pa?pa:pb;//插入乘!1余段

free(Lb);//釋放Lb的頭結(jié)點(diǎn)

}//MergeListL

單鏈表小結(jié)

1H1H1HHi1Hll?

■1.在單鏈表上插入、刪除一個結(jié)點(diǎn)，必須知道其前驅(qū)

結(jié)點(diǎn)O

-2.單鏈表不具有按序號隨機(jī)訪問的特點(diǎn)，只能從頭指

針開始一個個順序進(jìn)行。

■3.鏈?zhǔn)酱鎯Φ膬?yōu)點(diǎn)：插入刪除效率高

■4.鏈?zhǔn)酱鎯Φ娜秉c(diǎn)：訪問某個數(shù)據(jù)效率低

2.3.2循環(huán)鏈表

-循環(huán)鏈表是一種頭尾相接的鏈表。其特點(diǎn)是無需增加

存儲量，僅對表的鏈接方式稍作改變，即可使得表處

理更加方便靈活。

■單循環(huán)鏈表：在單鏈表中，將終端結(jié)點(diǎn)的指針域

NULL改為指向第一個結(jié)點(diǎn)，就得到了單鏈形式的循

環(huán)鏈表，并簡稱為單循環(huán)鏈表。

2.3.2循環(huán)鏈表

-循環(huán)鏈表中也可設(shè)置一個頭結(jié)點(diǎn)。

⑴非空表

■空循環(huán)鏈表僅有一個自成循環(huán)的頭結(jié)點(diǎn)表示。

⑵空表

2.3.2循環(huán)鏈表

-由于循環(huán)鏈表中沒有NULL指針，故涉及遍歷操作時,

其終止條件就不再像非循環(huán)鏈表那樣判斷p或p—

>next是否為空，而是判斷它們是否等于頭指針。

2.3.2循環(huán)鏈表

-在很多實(shí)際問題中，表的操作常常是在表的首尾位置

上進(jìn)行。如果改用尾指針rear來表示單循環(huán)鏈表，則

查找開始結(jié)點(diǎn)力和終端結(jié)點(diǎn)都很方便，它們的存儲

位置分別是(rear->next)—>next和rear,顯然，查找

時間都是0(1)。

(c)取用尾指針的循環(huán)a骯衣的假形式

-因此，實(shí)際中多采用尾指針表示單循環(huán)鏈表。

2?3.3雙向鏈表

■雙向鏈表：在單鏈表的每個結(jié)點(diǎn)里再增加一個指向其

直接前趨的指針域prior。這樣形成的鏈表中有兩個方

向不同的鏈，故稱為雙向鏈表。

■形式描述為：

typedefstructDulNode

ElemTypedata;數(shù)據(jù)域

structDulNode*prior;指向前驅(qū)元素的指針

structDulNode*next;指向后繼元素的指針

}DulNode,*DuLinkList;

2?3.3雙向鏈表

-設(shè)指針p指向某一結(jié)點(diǎn)，則有:

(p——>prior)—>next=p=(p—>next)—>prior

即結(jié)點(diǎn)*p的存儲位置既存放在其前趨結(jié)點(diǎn)*(p—>prior)

的直接后繼指針域中，也存放在它的后繼結(jié)點(diǎn)*(p—

>next)的直接前趨指針域中。

7七二Tia]|甘?…H|即|人I

head

2?3.3雙向鏈表

L雙向鏈表的前插操作

■算法描述：欲在雙向鏈表第i個結(jié)點(diǎn)之前插入一個新的

結(jié)點(diǎn)，則指針的變化情況如圖2.16所示。

s

圖2.16雙向鏈表插入操作

2?3.3雙向鏈表

L雙向鏈表的前插操作

^EM3===OIW

嚴(yán)

s=(DulNode*)malloc(sizeof(DulNode));

s—>data=x;

s—>prior=p—>prior;

p—>prior—>next=s;

s—>next=p;

p—>prior=s;

2?3.3雙向鏈表

L雙向鏈表的前插操作

StatusListInsert_Dul(DulLinkList&L,inti,inte){

〃在帶頭結(jié)點(diǎn)的雙鏈循環(huán)線性表L中第i個位置之前插入元素e

〃i合法值為大于等于1,小于等于表長加L

if(!(p=GetP_DUL(L,i))

returnERROR;〃在L中確定插入位置指針p,i等于表長

〃加1時，指向頭結(jié)點(diǎn)；i大于表長加1時，p=NULL；

if(!s=(DulLinkList)malloc(sizeof(DulNode))))

returnERROR;

s->data=e;

s->prior=p->prior;p->prior->next=s;

s->next=p;p->prior=s;