計(jì)算機(jī)軟件技術(shù)基礎(chǔ)

DepartmentofComputerQinghaiUniversityofChina

2010年3月

o第二章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

2.1數(shù)據(jù)結(jié)構(gòu)的基本概念

2.2線性表及其順序存儲(chǔ)結(jié)構(gòu)

2.3線性鏈表及其運(yùn)算

2.4樹(shù)與二叉樹(shù)

O2.1數(shù)據(jù)結(jié)構(gòu)的基本概念

L數(shù)據(jù)結(jié)構(gòu)研究的三個(gè)方面的問(wèn)題：

(1)數(shù)據(jù)集合中數(shù)據(jù)元素間固有的邏輯結(jié)構(gòu)；

(2)對(duì)數(shù)據(jù)處理時(shí)，各數(shù)據(jù)元素在計(jì)算機(jī)中的存儲(chǔ)關(guān)系

(3)對(duì)各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算；

2.目的：

(1)提高數(shù)據(jù)處理的效率

(2)提高數(shù)據(jù)處理的速度

(3)盡量節(jié)省計(jì)算機(jī)存儲(chǔ)空間

o2.1.1兩個(gè)例子

2.1.1兩個(gè)例子

【例】

■無(wú)序表的順序查找46

35167885432933215446

■有序表的對(duì)分查找46

16212933354346547885

【結(jié)論】

數(shù)據(jù)元素在表中的排列順序?qū)Σ檎倚适怯泻艽笥绊憽?/p>

【例】學(xué)生情況登記表以學(xué)號(hào)為順序排列

學(xué)生情況登■

學(xué)號(hào)姓名性別年齡成績(jī)

970156張小明男2086

970157李小W女1983

970158趙凱男1970

970159李啟明男2191

970160劉華寮1878

970161曾小波女1990

970162張軍男1880

9T0163王偉里2065

970164胡濤男1995

970165周敏女2087

970166楊雪輝男2289

970167呂永華男1861

970168梅玲女1793

970169劉健男2075

o2.1.1兩個(gè)例子

成績(jī)?cè)?0分以上的學(xué)生情況登記表

學(xué)號(hào)姓名性別年齡成績(jī)

970159李啟明男2191

970161曾小波女.1990

970164胡濤男1995

970168誨玲女1793

成績(jī)?cè)?0?89分之間的學(xué)生情況登記表

學(xué)號(hào)姓名性別年齡成績(jī)

970156張小明男2086

970157李小W女1983

970162張軍男1880

970165周敏女2087

970166楊雪輝男2289

O2.1.1兩個(gè)例子

成繳在70~79分之間的學(xué)生，痔況登記表

學(xué)號(hào)姓名性別年齡成績(jī)

970158趙凱男1970

970160劉華女1878

970169劉健男2075

成繳在60~69分之間的學(xué)生，皆況登記表

學(xué)號(hào)姓名性別年齡成績(jī)

970163王偉男2065

970167呂永華男1861

【結(jié)論】在對(duì)數(shù)據(jù)進(jìn)行處理時(shí)，可以根據(jù)所做的運(yùn)算不

同，將數(shù)據(jù)組織成不同的形式，以便于做該種運(yùn)算，

從而提高數(shù)據(jù)處理的效率。

*數(shù)據(jù)結(jié)構(gòu)：是指相互有關(guān)聯(lián)的數(shù)據(jù)元素集合。

*數(shù)據(jù)元素：現(xiàn)實(shí)世界中客觀存在的一切個(gè)體；

*數(shù)據(jù)元素之間的任何關(guān)系都可以用前后件關(guān)系來(lái)描述;

?前后件關(guān)系：是數(shù)據(jù)元素之間的一個(gè)基本關(guān)系；

描述一年四季的季節(jié)名：

春，夏，秋，冬可以作為季節(jié)的數(shù)據(jù)元素；

表示數(shù)值的各個(gè)數(shù)：

18,11,35,23,16,…可以作為數(shù)值的數(shù)據(jù)元素;

O2.1.2什么是數(shù)據(jù)結(jié)構(gòu)

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

(1)定義：指反映數(shù)據(jù)元素之間邏輯關(guān)系的數(shù)據(jù)

結(jié)構(gòu)。

①表示數(shù)據(jù)元素的信息;

②表示各數(shù)據(jù)元素之間的前后件關(guān)系。

(2)兩個(gè)要素：

①數(shù)據(jù)元素的集合D；

②反映D中各數(shù)據(jù)元素之間的前后件關(guān)系R。

D二元關(guān)系來(lái)表示

B=（D,R）其中：B表示數(shù)據(jù)結(jié)構(gòu)。

【例】B=（D,R）

D—｛春，夏，秋，冬｝

R=｛（春，夏），（夏，秋），（秋，冬）｝

說(shuō)明：設(shè)a與b是D中的兩個(gè)數(shù)據(jù)，則二元組（a,b）表示a是b

的前件，b是a的后件。

B=(D,R)

D={父親，兒子，女兒}

R={(父親，兒子)，(父親，女兒)}

n維向量X=(xpx2,???,xn)也是一種數(shù)據(jù)結(jié)構(gòu)。即

X=(D,R)

D—{xpx2,xj

R={(xjx2),x/}

O2.1.2什么是數(shù)據(jù)結(jié)構(gòu)

②數(shù)據(jù)結(jié)構(gòu)的圖形表示

?數(shù)據(jù)集合D中的每一個(gè)數(shù)據(jù)元素：

用中間標(biāo)有元素值的方框表示（數(shù)據(jù)結(jié)點(diǎn)，結(jié)點(diǎn)）

*用一條有向線段從前件結(jié)點(diǎn)指向后件結(jié)點(diǎn)。

【例】一年四季數(shù)據(jù)結(jié)構(gòu)的圖形表示

O2.1.2什么是數(shù)據(jù)結(jié)構(gòu)

▼r初】家庭成員間輩份關(guān)系

O2.1.2什么是數(shù)據(jù)結(jié)構(gòu)

【例】用圖形表示數(shù)據(jù)結(jié)構(gòu)B=(D,R),其中:

D=|l<i<7}={dpd2,d3,d4,d5,d6,d7}

R={(dPd3),(d1,d7),(d2,d4),(d3,d6)

O2.1.3什么是數(shù)據(jù)結(jié)構(gòu)

2.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)（數(shù)據(jù)的物理結(jié)構(gòu)）

?數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的存放形式。

?常用的存儲(chǔ)結(jié)構(gòu)有：

■順序、鏈接、索引等存儲(chǔ)結(jié)構(gòu)。

采用不同的存儲(chǔ)結(jié)構(gòu)，其數(shù)據(jù)處理的效率是不同的。

順序存儲(chǔ)結(jié)構(gòu)

鏈接存儲(chǔ)結(jié)構(gòu)

0-2.1.-4線性數(shù)據(jù)結(jié)構(gòu)與非線性數(shù)據(jù)結(jié)構(gòu)一一」

線性結(jié)構(gòu)又稱線性表：

(1)有且只有一個(gè)根結(jié)點(diǎn)；

(2)每一個(gè)結(jié)點(diǎn)最多有一個(gè)前件，也最多有一個(gè)后件

非線性結(jié)構(gòu)：

如果一個(gè)數(shù)據(jù)結(jié)構(gòu)不是線性結(jié)構(gòu)

不是線性結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)特例

2.2.1線性表及其運(yùn)算

2.2.2棧及其應(yīng)用

2.2.3隊(duì)列及其應(yīng)用

1.什么是線性表(LinearList)

?n維向量(xjx2,…，x)是一個(gè)長(zhǎng)度為n的線性表；

?英文小寫字母表(a,b,c,…，z)是一個(gè)長(zhǎng)度為26的

線性表；

?：.一年中的四個(gè)季節(jié)(春，夏，秋，冬)是一個(gè)長(zhǎng)度為4

的線性表；

矩陣是一個(gè)比較復(fù)雜的線性表；

學(xué)生情況登記表是一個(gè)復(fù)雜的線性表

由若干數(shù)據(jù)項(xiàng)組成的數(shù)據(jù)元素稱為記錄(record)

由多個(gè)記錄構(gòu)成的線性表又稱為文件(file)

學(xué)生情況登記表

姓名學(xué)號(hào)性別年齡健康狀況

王強(qiáng)80035619良好

劉建平80035720

趙軍80036119良好

葛文華800367；21較差

?■?*.*

O2.2線性表及其順序存儲(chǔ)結(jié)構(gòu)

尸11)線性表的定義:

是由n(n》0)個(gè)數(shù)據(jù)元素a：a2,???,組成的一

個(gè)

有限序列，表中的每一個(gè)數(shù)據(jù)元素，除了第一個(gè)外，

有且只有一個(gè)前件，除了最后一個(gè)外，有且只有一個(gè)

后件。即線性表或是一個(gè)空表，或可以表示為：

(a］，a?’%，???,a/

?其中：％(i=l,2,…，n)是屬于數(shù)據(jù)對(duì)象的元

素，通常也稱其為線性表中的一個(gè)結(jié)點(diǎn)。

O2.2線性表及其順序存儲(chǔ)結(jié)構(gòu)

(2)非空線性表結(jié)構(gòu)特征：

①有且只有一個(gè)根結(jié)點(diǎn)a1，它無(wú)前件；

②有且只有一個(gè)終端結(jié)點(diǎn)a”，它無(wú)后件；

③除根結(jié)點(diǎn)與終端結(jié)點(diǎn)外，其它所有結(jié)點(diǎn)有且

只有一個(gè)前件，也有且只有一個(gè)后件。

?線性表中結(jié)點(diǎn)的個(gè)數(shù)n稱為線性表的長(zhǎng)度。當(dāng)n

=0時(shí),稱為空表。

O2.2線性表及其順序存儲(chǔ)結(jié)構(gòu)

12.線性表的順序存儲(chǔ)結(jié)構(gòu)

(1)線性表的順序存儲(chǔ)結(jié)構(gòu)基本特點(diǎn)：

①所有元素所占的存儲(chǔ)空間是連續(xù)的；

②各數(shù)據(jù)元素在存儲(chǔ)空間中是按邏輯順序依次存

放的。

?線性表中第i個(gè)元素aj在計(jì)算機(jī)存儲(chǔ)空間中的存儲(chǔ)

地址為：ADR(a)=ADR(at)+(i—1)k

?K表示每個(gè)數(shù)據(jù)元素占K個(gè)字節(jié)

O2.2線性表及其順序存儲(chǔ)結(jié)構(gòu)

長(zhǎng)度為n的線性表整型一維數(shù)組

(a1，@2，a,a/存放長(zhǎng)度為8

?一，?一，V(1：12)

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

218

?(29,18,56,63,3

存儲(chǔ)地址*

■356

4635,24,31,47)

ADR(ajai占k個(gè)字節(jié)

535

ADR(ax)+k%

占k個(gè)字節(jié)624

■?

??

?■731

847

ADR(aJ?11-l)kax占k個(gè)字力

■■9

*■

■?

10

一

ADR(aJ*6l)ka.占k個(gè)字拈11

■

*

■12

o2.2線性表及其順序存儲(chǔ)結(jié)構(gòu)

2)建立空線性表的順序存儲(chǔ)空間(即初始化線

性表的順序存儲(chǔ)空間)

#includenstdlib.hn

voidinitsl(v,m,n)

ET*v；intm,*n；

{v=malloc(m*sizeof(ET))；

*n=0；

return；

}

釋放線性表的順序存儲(chǔ)空間free(v)；

O2.2線性表及其順序存儲(chǔ)結(jié)構(gòu)

(3)線性表順序存儲(chǔ)結(jié)構(gòu)下的主要運(yùn)算:

①插入②刪除③查找④排序

⑤分解⑥合并⑦復(fù)制⑧逆轉(zhuǎn)

O2.2線性表及其順序存儲(chǔ)結(jié)構(gòu)

V（1：10）V（1：10）V（1：10）

1291.29129

國(guó)一2182;87287

356318318

463456456

535563563

624635635

131724724

847831831

9回f9147914

10101047

(a)長(zhǎng)度為8的線t線(b)插入元素87后(c)又插入元素14后

)2.2線性表及其順序存儲(chǔ)結(jié)構(gòu)

輸入：線性表的存儲(chǔ)空---------------------------

PROCEDUREINSL(V,m,n,i,b)

間V(Lm)；線性表的

IF(n=m)THEN

長(zhǎng)度n(nCm)；插入{OVERFLOW；RETURN}

的位置i(i表示在第iIF(i>n)THENi=n+l

個(gè)元素之前插入)；IF(i<l)THENi=l

FORj=nTOiBY-1DOV(j+l)=V(j)

插入的新元素b。

V(i)=b

輸出：插入后的線性表n=n+1

存儲(chǔ)空間V(Lm)及線RETURN

性表的長(zhǎng)度n。

O2.2線性表及其順序存儲(chǔ)結(jié)構(gòu)

voidinsl(v,m,n,i,b)

ETv[],b；intm,*n,i；

{if(*n==m)

{printf(noverflow\nn)；return；}

if(i〉*n—1)i=*n+l；

if(i<l)i=l；

for(j=*n；j<=i；j—)v[j]=v[j-l]；

v[i—l]=b；

*n=*n+l；

return；

}

O2.2線性表及其順序存儲(chǔ)結(jié)構(gòu)

4.線性表在順序存儲(chǔ)下的刪除運(yùn)算

V（1：10）V（1：10）V（1：10）

129118118

218256256

356；363363

463435435

535524524

624631647

7317477

84788

999

101010

Q)長(zhǎng)度為8的線嫁(b)刪除元素29后⑹又刪除元素31后

O2.2線性表及其順序存儲(chǔ)結(jié)構(gòu)

輸入：線性表的存儲(chǔ)空間V(l：m)；線性表的長(zhǎng)度n(nWm)；

刪除的位置i(表示刪除第i個(gè)元素)。

輸出：刪除后的線性表存儲(chǔ)空間V(Lm)及線性表的長(zhǎng)度n。

PROCEDUREDESL(V,m,n,i)

l.IF(n=0)THEN{UNDERFLOW；RETURN}

2.IF(i<l)or(i>n)THEN

{“Notthiselementinthelist"；RETURN)

3.FORj=iTOn-1DOV(j尸V(j+1)

4.n=n—1

5.RETURN

2.2線性表及其順序存儲(chǔ)結(jié)構(gòu)

voiddesl(v,m,n,i)

ETv[]；intm,*n,i；

{if(*n==0){printf(nunderflow\n'')；return；}

if((i<l)11(i>*n))

{printf(nNotthiselementinthelist\nn)；return；}

for(j=i；j<=*n-l；j++)v[j-l]=v[j]；

*n=*nT；

return；

2.2.2棧及其應(yīng)用

1.什么是棧(stack)

主程序與子程序之間的調(diào)用關(guān)系

MAINSUB1SUB2SUB3SUB4

CALLSUB1CALLSUB2CALLSUB3CALLSUB4...

A：11,111B：……C：……D：…………

ENDRETURNRETURNRETURNRETURN

棧與遞歸.swf

2.2.2棧及其應(yīng)用

棧：限定在一端進(jìn)行插入與刪除的線性表；棧也

被稱為先進(jìn)后出表或后進(jìn)先出表。

棧頂:允許插入與刪除的一端稱為；

棧底：不允許插入與刪除的另一端稱為；

指針top：指示棧頂位置；

指針bottom：指示棧底位置；

2.2.2棧及其應(yīng)用

入棧退棧

1t1

1順序棧（4個(gè)存儲(chǔ)空間）.swf

極頂topT

,1

棧底bottomT順序棧（8個(gè)存儲(chǔ)空間）.swf

)2.2.2棧及其應(yīng)用

top=0表示?？眨籺op=m表示棧滿；

建立空棧的順序存儲(chǔ)空間(即初始化棧的順序

存儲(chǔ)空間)；

釋放棧的順序存儲(chǔ)空間時(shí)free(s)；

#includenstdlib.hn

voidinit_stack(s,m,top)

ET*s；intm,*top；

{s=malloc(m*sizeof(ET))；*top=0；

return；

}

o2.2.2棧及其應(yīng)用

2.棧的順序存儲(chǔ)及其運(yùn)算

S（1：10）S（1：10）S（1：10）

101010

99'9

8topf8Y汨

77Xtopf7X

topf6F6F6F

5E5E5E

4D4D；4D

3C3CC

2B2B<2B

bottomflAbottomflAbottom->1A

Q）有6個(gè)元素的棧G）插入X與丫后的棧（c）退出一個(gè)元素后的棧

PROCEDUREPUSH(S,m,top,x)

IF(top=m)THEN{Stack-OVERFLOW；RETURN}

top=top+1

S(top)=x

RETURN

voidpush(s,m,top,x)

ETs[],x；intm,*top；

{if(*top==m){printf(nStack—overflow\nn)；return；}

*top=*top+l；s[*top—l]=x；return；

PROCEDUREPOP(S,m,top,y)

IF(top=0)THEN{Stack-UNDERFLOW；RETURN}

y=S(top)

top=top—1

RETURN

voidpop(s,m,top,y)

ETs[],*y；intm,*top；

{if(*top==0){printf(nStack—underflow\nn)；

return；}

*y=s[*top—1]；*top=*top—1；return；

}

PROCEDURETOP(S,m,top,y)

IF(top=0)THEN{“Stackempty”；RETURN}

y=S(top)

RETURN

voidtop(s,m,top,y)

ETs[],*y；intm,*top；

{if(*top==0)

{printf(nStackempty\nn)；return；}

*y=s[*top—1]；return；

)

2.2.3隊(duì)列及其應(yīng)用

“Or什么是隊(duì)列（equeue）

但是指允許在隊(duì)尾進(jìn)行插入、在隊(duì)頭進(jìn)行刪除的線性表;

隊(duì)列又稱為“先進(jìn)先出”（FIFO）或“后進(jìn)后出”

（LILO）的線性表;

front_>

退隊(duì)運(yùn)算（a）Afront_>■front_*-

BBB

CCC

入隊(duì)運(yùn)算（b）rear-0■Drear->DD

—rear_>E

（a）一個(gè)隊(duì)列（b）刪除一個(gè)元素后Q）插入元素E后

⑨隊(duì)列的順序循環(huán)結(jié)構(gòu)采用循

rear-*

環(huán)隊(duì)列形式；

◎■循環(huán)隊(duì)列的初始狀態(tài)為空，

即rear=front=m;

八

O2.2.3隊(duì)列及其應(yīng)用

舊1^環(huán)隊(duì)列及其運(yùn)算

QQ：8)QU：8)Q（1：8）

88X8X

rear_*7FTF7F

6E6E6E

5D5D5D

4C4C4C

3B3B3B

2A2Afront-*-2

front-*-1￡ront-*■1Yrear—1Y

rear-*

[a)具有6個(gè)元素的循環(huán)隊(duì)列(b)加入X、Y后(Q退出一個(gè)元素后

o2.2.3隊(duì)列及其應(yīng)用

①當(dāng)front=rear時(shí)，兩種情況:

循環(huán)隊(duì)列滿或循環(huán)隊(duì)列空

增加一個(gè)標(biāo)識(shí)S區(qū)別隊(duì)列滿或空

,隊(duì)列空的條件為s=0

隊(duì)列滿的條件為(s=1)且front=rear

o2.2.3隊(duì)列及其應(yīng)用

②建立(初始化)循環(huán)隊(duì)列順序存儲(chǔ)空間

#includenstdlib.hn

voidinit_queue(q,m,front,rear,s)

ET*q；intm,"front,*rear,*s；

{q=malloc(m*sizeof(ET))；

*front=m；*rear=m；*s=0；

return；

釋放循環(huán)隊(duì)列的順序存儲(chǔ)空間free(q)；

PROCEDUREADDCQ(Q,m,rear,front,s,x)

1.IF(s=l)and(rear=front)THEN

{Queue-OVERFLOW；RETURN}

2.rear=rear+1

3.IF(rear=m+l)THENrear=l

4.Q(rear)=x

5.s=l

6.RETURN

o2.2.3隊(duì)列及其應(yīng)用

voidaddcq(q,m,rear,front,s,x)

ETq[],x；intm,*rear,*front,*s；

(

if((*s==1)&&(*rear==^front))

{printf(^Queue-OVERFLOW\n")；return；}

*rear=*rear+1；

if("rear==m+1)^rear=1；

q[^rear-1]=x；*s=1；return；

}

PROCEDUREDELCQ(Q,m,rear,front,s,y)

l.IF(s=0)THEN

{Queue-UNDERFLOW；RETURN)

2.front=front+1

3.IF(front=m+1)THENfront=1

4.y=Q(front)

5.IF(front=rear)THENs=0

6.RETURN

o2.2.3隊(duì)列及其應(yīng)用

voiddelcq(q,m,rear,front,s,y)

ETq[],*y；intm,*rear,"front,*s；

{if(*s==0)

{printf(nQueue-UNDERFLOW\nu)；return；}

*front="front+1；

if(*front==m+1)/front=1；

*y=q[*front-1]；

if("front==^rear)*s=0；

return；

}

2.2線性表及其順序存儲(chǔ)結(jié)構(gòu)

0一―一―

線性表順序存儲(chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)：

＞簡(jiǎn)單、運(yùn)算方便，尤其適合小線性表或長(zhǎng)度固定的線

性表；

線性表順序存儲(chǔ)結(jié)構(gòu)的缺點(diǎn)：

＞插入或刪除一個(gè)元素時(shí)，需要移動(dòng)大量的數(shù)據(jù)元素；

＞線性表的存儲(chǔ)空間不便于擴(kuò)充；

＞不便于隊(duì)存儲(chǔ)空間動(dòng)態(tài)分配；

2.3.1線性鏈表的基本概念

2.3.2線性鏈表的基本運(yùn)算

2.3.3循環(huán)鏈表

存儲(chǔ)序號(hào)數(shù)據(jù)域指針域

2

1V(i)NEXT(i)

線性捱表的一個(gè)存儲(chǔ)結(jié)點(diǎn)

線性鏈表的存儲(chǔ)空間

例如

structnode

{charname[10]；/*數(shù)據(jù)域*/

charsex；/*數(shù)據(jù)域*/

structnode*next；/*指針域*/

}

線性捱表的邏輯結(jié)構(gòu)

HEAD_^W1?數(shù)據(jù)2>???_?數(shù)據(jù)n皿

當(dāng)HEAD=NULL（或0）時(shí)為空表

線性捱表的物理狀態(tài)

線性鏈表的邏輯岫

o2.3.1線性鏈表的基本概念

【算法】依次輸出線性鏈表中的各結(jié)點(diǎn)值

輸入：線性鏈表的存儲(chǔ)空間V(Lm)、NEXT(1：m)；

線性鏈表的頭指針HEAD。

輸出：依次輸出線性鏈表中各結(jié)點(diǎn)的值。

PROCEDUREPRTLL(HEAD)

j=HEAD

WHILE(j#0)DO

{OUTPUTV(j)；j=NEXT(j)}

RETURN

o2.3.1線性鏈表的基本概念

#include"stdlib.h"/*malloc函數(shù)需要*/

structnode/*定義結(jié)點(diǎn)類型列

intd；/*數(shù)據(jù)域*/

structnode/next；/*指針域*/

main()

{structnode*p；/*定義該類型的指針變量P*/

p=(structnode*)malloc(sizeof(structnode))；

free(p)；

2.3.1線性鏈表的基本概念

#includenstdlib.hnif(head==NULL)head=p

#includenstdio.hnelseq->next=p；q=p；

structnodescanf(n%dn,&x)；

{intd；structnode*next；

main()p=head；

{structnode*p,*head,*q;while(p!=NULL)

intx;head=NULL；q=NULL；{printf(i6%5d5\p->d)；

scanf(“％d”，&x)；q=p；p=p->next；

while(x>0)free(q)；

p=(structnode*)malloc

(sizeof(structnode))；printf(“\n”)；

p->d=x；p->next=NULL；)

(3)單鏈表的缺點(diǎn)：每個(gè)結(jié)點(diǎn)只有一個(gè)指向后件的

指針，如果需要找到它的前件必須從指針開(kāi)始重新

尋找；

2.雙向鏈表

O2.3.1線

3.帶鏈的棧

topa。

可利用棧及其運(yùn)算

TOP

t

在從可利用棧取得一個(gè)結(jié)點(diǎn)p

>輸入：可利用棧棧頂指針TOP（默認(rèn)）；送回可

利用棧的結(jié)點(diǎn)序號(hào)P。

>輸出：結(jié)點(diǎn)P入棧后的可利用棧棧頂指針TOP（默

認(rèn)）。

PROCEDUREDISPOSE(p)

NEXT(p)=TOP；TOP=p

RETURN

＞輸入：可利用棧的棧頂指針TOP（默認(rèn)）。

＞輸出：退棧后的可利用棧棧頂指針TOP（默認(rèn)）；

存放取得結(jié)點(diǎn)序號(hào)的變量P。

PROCEDURENEW(p)

p=TOP；TOP=NEXT(TOP)

RETURN

o2.3.1線性鏈表的基本概念

⑶帶鏈棧的入棧運(yùn)算

輸入：帶鏈棧的棧頂指針top；入棧的元素值X。

輸出：元素X入棧后的帶鏈棧棧頂指針top。

PROCEDUREPUSHLL(top,x)

NEW(p)［從可利用棧取得一個(gè)新結(jié)點(diǎn)］

V(p)=x［置新結(jié)點(diǎn)數(shù)據(jù)域］

NEXT(p)=top［置新結(jié)點(diǎn)指針域］

top=p［改變棧頂指針］

RETURN

o2.3.1線性鏈表的基本概念

#include''stdlib.h''

structnode

{ETd；structnode*next；}；

pushll(top,x)

ETx；structnode**top；

{structnode*p；

p=(structnode*)malloc(sizeof(structnode))；

p->d=x；p->next=*top；

*top=p;/*改變棧頂指針*/

return；

o2.3.1線性鏈表的基本概念

⑷帶鏈棧的退棧運(yùn)算

＞輸入：帶鏈棧的棧頂指針top。

＞輸出：退棧后的帶鏈棧棧頂指針top；存放退

出結(jié)點(diǎn)元素值的變量y。

PROCEDUREPOPLL(top,y)

y=V(top)［取出標(biāo)頂元未值］

p=top

top=NEXT(p)［改變棧頂指針］

DISPOSE(p)［被刪除結(jié)點(diǎn)送回可利用棧］

RETURN

2.3.1

#includenstdlib.hn

structnode

{ETd；structnode*next；

popll(top,y)

ETy；structnode**top；

{structnode*p；

y=*top->d；/*取出棧頂元素值刃

p=*top；

*top=p->next；/*改變棧頂指針*/

free(p)；return；/*釋放被刪除結(jié)點(diǎn)后返回*/

a2

(b)在帶鏈的隊(duì)列中插入一個(gè)新結(jié)點(diǎn)

aI—aZ

八

rear

front

(c)在帶鏈的隊(duì)列中冊(cè)賒一個(gè)結(jié)點(diǎn)

o2.3.1線性鏈表的基本概念

(1)帶鏈隊(duì)列的入隊(duì)運(yùn)算

?輸入：帶鏈隊(duì)列的隊(duì)尾指針rear；入隊(duì)的新元素x。

A輸出：元素x入隊(duì)后的帶鏈隊(duì)列隊(duì)尾指針rear。

PROCEDUREADDLL(rear,x)

NEW(p)［從可利用棧取得一個(gè)新結(jié)點(diǎn)p］

V(p)=x［置新結(jié)點(diǎn)的數(shù)據(jù)域］

NEXT(p)=0［置新結(jié)點(diǎn)的指針為空］

NEXT(rear)=p［最后一個(gè)結(jié)點(diǎn)的指針指向新結(jié)點(diǎn)］

rear=p［改變隊(duì)尾指針］

RETURN

o2.3.1線性鏈表的基本概念

#include''stdlib.h''

structnode

{ETd；structnode*next；

addll(rear,x)

ETx；structnode**rear；

{structnode*p；

p=(structnode^)malloc(sizeof(structnode))；

p->d=x；p->next=NULL；/*置新結(jié)點(diǎn)的數(shù)據(jù)域與指針域*/

^rear->next=p；/*置最后一個(gè)結(jié)點(diǎn)的指針指向新結(jié)點(diǎn)*/

*rear=p；/*改變隊(duì)尾指針*/

return；

o2.3.1線性鏈表的基本概念

⑵帶鏈隊(duì)列的退隊(duì)運(yùn)算

輸入：帶鏈隊(duì)列的排頭指針fronto

?輸出：退隊(duì)后的帶鏈隊(duì)列排頭指針丘ont；存放

退出結(jié)點(diǎn)值的變量y。

PROCEDUREDELLL(front,y)

y=V(front)［取出排頭元素值］

p=front

front=NEXT(front)［改變排頭指針］

DISPOSE(p)［釋放刪除的結(jié)點(diǎn)］

RETURN

。

2.3.1線性鏈表的基本概念

#includenstdlib.hn

structnode

{ETd；structnode*next；}；

delll(front,y)

ETy；structnode**front；

{structnode*p；

y=^front->d；/*取出排頭元素值*/

p=*front；

"front=p—>next；/*改變排頭指針*/

free(p)；/*釋放被刪除結(jié)點(diǎn)*/

return；

O2.3.2線性鏈表的基本運(yùn)算

⑴在線性鏈表中包含指定元素的結(jié)點(diǎn)之前插入

一個(gè)新元素。

⑵在線性鏈表中刪除包含指定元素的結(jié)點(diǎn)。

(3)將兩個(gè)線性鏈表按要求合并成一個(gè)線性鏈表。

(4)將一個(gè)線性鏈表按要求進(jìn)行分解。

(5)逆轉(zhuǎn)線性鏈表。

(6)復(fù)制線性鏈表。

⑺線性鏈表的排序。

⑻線性鏈表的查找。

o2.3.2線性鏈表的基本運(yùn)算

i.在線性鏈表中查找指定元素

在非空線性鏈表中尋找包含元素X的前一個(gè)結(jié)點(diǎn)p

輸入：非空線性鏈表頭指針HEAD；被尋找元素X。

輸出：非空線性鏈表中包含元素x的前一個(gè)結(jié)點(diǎn)p。

PROCEDURELOOKST(HEAD,x,p)

p=HEAD

WHILE(NEXT(p)^O)and(V(NEXT(p))#)DO

p=NEXT(p)

RETURN

o2.3.2線性鏈表的基本運(yùn)算

structnode

{ETd；structnode*next；}；

structnode^lookst(head,x)

ETx；structnode*head；

{structnode*p；

p=head；

while((p—>next!=NULL)&&(((p->next)—>d)!=x))

p=p—>next；

return(p)；

}

O2.3.2線性健表的基本運(yùn)算

2.線性鏈表的插入

在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)下的線性表中

插入一個(gè)新元素。

O2.3.2線性健表的基本運(yùn)算

可利用棧與線性鏈表

HEAD0

(a)原來(lái)的可利用棧與線性鏈表

o2.3.2線性鏈表的基本運(yùn)算

(1)從可利用棧取得一個(gè)結(jié)點(diǎn)，設(shè)該結(jié)點(diǎn)號(hào)為P。

并置結(jié)點(diǎn)P的數(shù)據(jù)域?yàn)椴迦氲脑刂礲,即V(p)=b。

⑵在線性鏈表中尋找包含元素x的前一個(gè)結(jié)點(diǎn)q。

(b)從可利用棧取得結(jié)點(diǎn)p,在線性瞰中找到包含元素X的前一個(gè)結(jié)點(diǎn)q

o2.3.2線性鏈表的基本運(yùn)算

(3)將結(jié)點(diǎn)p插入到結(jié)點(diǎn)q之后:

①使結(jié)點(diǎn)P指向包含元素x的結(jié)點(diǎn)，即

NEXT(p)=NEXT(q)

②使結(jié)點(diǎn)q的指針域內(nèi)容改為指向結(jié)點(diǎn)P，即

NEXT(q)=p

(c)p插入到q之后

2.3.2線性鏈表的基本運(yùn)算

線性鏈表的插入

輸入：線性鏈表的頭指針HEAD；插入位置處的前

一個(gè)結(jié)點(diǎn)值x；插入的新元素b。

輸出：插入后的線性鏈表。

o2.3.2線性鏈表的基本運(yùn)算

PROCEDUREINSLST(HEAD,x,b)

1.NEW(p)

2.V(p)=b

3.IF(HEAD=0)THEN{HEAD=p；NEXT(p)=0；

RETURN}

4.IF(V(HEAD)=x)THEN

{NEXT(p)=HEAD；HEAD=p；RETURN}

5.LOOKST(HEAD,x,q)

6.NEXT(p)=NEXT(q)；NEXT(q)=p

7.RETURN

#includenstdlib.hn

structnode

(

ETd；

structnode*next；

｝；

o2.3.2線性鏈表的基本運(yùn)算

inslst(head,x,b)

ETx,b；structnode**head；

{structnode*p,*q；

p=(structnode^)malloc(sizeof(structnode))；

p—>d=b；

if(^head==NULL)

{*head=p；p->next=NULL；return；}

if((^head—>d)==x)

{p->next=*head；*head=p；return；}

q=lookst(^head,x)；

p->next=q->next；q->next=p；return；

O2.3.2線性鏈表的基本運(yùn)算

3.線性鏈表的刪除

在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)下的線性表中

刪除包含指定元素的結(jié)點(diǎn)。

O2.3.2線性健表的基本運(yùn)算

可利用棧與線性鏈表

Q）原來(lái)的可利用棧與線性鏈表

O2.3.2線性鏈表的基本運(yùn)笄

(1)尋找包含元素X的前一個(gè)結(jié)點(diǎn)q。

則包含元素x的結(jié)點(diǎn)序號(hào)p=NEXT(q)o

(2)將結(jié)點(diǎn)q后的結(jié)點(diǎn)P刪除,即NEXT(q)=NEXT(p)o

(b)從線性鏈表中刪除包含元素x的結(jié)點(diǎn)p后

O2.3.2線性鏈表的基本運(yùn)算

(3)將包含元素x的結(jié)點(diǎn)p送回可利用棧。

(C)將被刪除的結(jié)點(diǎn)P送回可利用棧后

O2.3.2線性鏈表的基本運(yùn)算

線性鏈表的刪除

A輸入：線性鏈表的頭指針HEAD；需刪除的

7E素X?

?輸出：刪除后的線性鏈表。

。

2.3.2線性鏈表的基本運(yùn)算

PROCEDUREDELST(HEAD,x)

l.IF(HEAD=0)THEN

{“Thisisaemptylist!”；RETURN}

2.IF(V(HEAD)=x)THEN

{p=NEXT(HEAD)；DISPOSE(HEAD)；HEAD=p；

RETURN}

3.LOOKST(HEAD,x,q)

4.IF(NEXT(q)=0)THEN

{uNothisnodeinthelist!99；RETURN}

5.p=NEXT(q)；NEXT(q)=NEXT(p)

6.DISPOSE(p)

7.RETURN

2.3.2線性鏈表的基本運(yùn)算

Qude"stdlib.h''

structnode

{ETd；structnode*next；}；

delst(head，x)

ETx；structnode**head；

{structnode*p,*q；

if(*head==NULL){printf(nThisisaemptylist!\nn)；return；

if((*head->d)==x)

{p=*head->next；free(*head)；*head=p；return；}

q=lookst(*head,x)；

if(q->next==NULL)

{printf(nNothisnodeinthelist!\nn)；return；}

p=q—>next；q—>next=p—>next；/*刪除結(jié)點(diǎn)p*/

free(p)；/*釋版結(jié)點(diǎn)p*/return；

⑴在循環(huán)鏈表中增加