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

DepartmentofComputerQinghaiUniversityofChina

2010年3月

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

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

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

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

2.4樹與二叉樹

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

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

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

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

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

2.目的：

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

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

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

o2.1.1兩個(gè)例子

2.1.1兩個(gè)例子

【例】

■無序表的順序查找46

35167885432933215446

■有序表的對分查找46

16212933354346547885

【結(jié)論】

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

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

學(xué)生情況登■

學(xué)號姓名性別年齡成績

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è)例子

成績在90分以上的學(xué)生情況登記表

學(xué)號姓名性別年齡成績

970159李啟明男2191

970161曾小波女.1990

970164胡濤男1995

970168誨玲女1793

成績在80?89分之間的學(xué)生情況登記表

學(xué)號姓名性別年齡成績

970156張小明男2086

970157李小W女1983

970162張軍男1880

970165周敏女2087

970166楊雪輝男2289

O2.1.1兩個(gè)例子

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

學(xué)號姓名性別年齡成績

970158趙凱男1970

970160劉華女1878

970169劉健男2075

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

學(xué)號姓名性別年齡成績

970163王偉男2065

970167呂永華男1861

【結(jié)論】在對數(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)系來描述;

?前后件關(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)系來表示

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

【例】B=（D,R）

D—｛春，夏，秋，冬｝

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

說明：設(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ù)的存儲結(jié)構(gòu)（數(shù)據(jù)的物理結(jié)構(gòu)）

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

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

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

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

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

鏈接存儲結(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è)長度為n的線性表；

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

線性表；

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

的線性表；

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

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

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

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

學(xué)生情況登記表

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

王強(qiáng)80035619良好

劉建平80035720

趙軍80036119良好

葛文華800367；21較差

?■?*.*

O2.2線性表及其順序存儲結(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ù)對象的元

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

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

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

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

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

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

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

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

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

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

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

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

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

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

放的。

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

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

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

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

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

(a1，@2，a,a/存放長度為8

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

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

218

?(29,18,56,63,3

存儲地址*

■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線性表及其順序存儲結(jié)構(gòu)

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

性表的順序存儲空間)

#includenstdlib.hn

voidinitsl(v,m,n)

ET*v；intm,*n；

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

*n=0；

return；

}

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

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

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

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

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

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

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

1291.29129

國一2182;87287

356318318

463456456

535563563

624635635

131724724

847831831

9回f9147914

10101047

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

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

輸入：線性表的存儲空---------------------------

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

間V(Lm)；線性表的

IF(n=m)THEN

長度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

存儲空間V(Lm)及線RETURN

性表的長度n。

O2.2線性表及其順序存儲結(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線性表及其順序存儲結(jié)構(gòu)

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

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

129118118

218256256

356；363363

463435435

535524524

624631647

7317477

84788

999

101010

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

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

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

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

輸出：刪除后的線性表存儲空間V(Lm)及線性表的長度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線性表及其順序存儲結(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è)存儲空間）.swf

極頂topT

,1

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

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

top=0表示棧空；top=m表示棧滿；

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

存儲空間)；

釋放棧的順序存儲空間時(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.棧的順序存儲及其運(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)識S區(qū)別隊(duì)列滿或空

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

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

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

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

#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ì)列的順序存儲空間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線性表及其順序存儲結(jié)構(gòu)

0一―一―

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

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

性表；

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

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

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

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

2.3.1線性鏈表的基本概念

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

2.3.3循環(huán)鏈表

存儲序號數(shù)據(jù)域指針域

2

1V(i)NEXT(i)

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

線性鏈表的存儲空間

例如

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)值

輸入：線性鏈表的存儲空間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è)指向后件的

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

尋找；

2.雙向鏈表

O2.3.1線

3.帶鏈的棧

topa。

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

TOP

t

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

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

利用棧的結(jié)點(diǎn)序號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)序號的變量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ì)列中冊賒一個(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)酱鎯Y(jié)構(gòu)下的線性表中

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

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

可利用棧與線性鏈表

HEAD0

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

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

(1)從可利用棧取得一個(gè)結(jié)點(diǎn)，設(shè)該結(jié)點(diǎn)號為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)酱鎯Y(jié)構(gòu)下的線性表中

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

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

可利用棧與線性鏈表

Q）原來的可利用棧與線性鏈表

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

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

則包含元素x的結(jié)點(diǎn)序號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)鏈表中增加