DepartmentofComputerQinghaiUniversityofChina

2010年3月

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

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

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

2.3線性鏈表及其運算

2.4樹與二叉樹

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

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

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

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

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

2.目的：

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

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

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

o2.1.1兩個例子

2.1.1兩個例子

【例】

■無序表的順序查找46

35167885432933215446

■有序表的對分查找46

16212933354346547885

【結(jié)論】

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

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

學生情況登■

學號姓名性別年齡成績

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兩個例子

成績在90分以上的學生情況登記表

學號姓名性別年齡成績

970159李啟明男2191

970161曾小波女.1990

970164胡濤男1995

970168誨玲女1793

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

學號姓名性別年齡成績

970156張小明男2086

970157李小W女1983

970162張軍男1880

970165周敏女2087

970166楊雪輝男2289

O2.1.1兩個例子

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

學號姓名性別年齡成績

970158趙凱男1970

970160劉華女1878

970169劉健男2075

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

學號姓名性別年齡成績

970163王偉男2065

970167呂永華男1861

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

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

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

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

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

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

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

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

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

表示數(shù)值的各個數(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)兩個要素：

①數(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中的兩個數(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中的每一個數(shù)據(jù)元素：

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

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

【例】一年四季數(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)在計算機存儲空間中的存放形式。

?常用的存儲結(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)有且只有一個根結(jié)點；

(2)每一個結(jié)點最多有一個前件，也最多有一個后件

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

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

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

2.2.1線性表及其運算

2.2.2棧及其應(yīng)用

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

1.什么是線性表(LinearList)

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

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

線性表；

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

的線性表；

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

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

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

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

學生情況登記表

姓名學號性別年齡健康狀況

王強80035619良好

劉建平80035720

趙軍80036119良好

葛文華800367；21較差

?■?*.*

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

尸11)線性表的定義:

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

個

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

有且只有一個前件，除了最后一個外，有且只有一個

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

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

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

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

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

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

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

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

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

只有一個前件，也有且只有一個后件。

?線性表中結(jié)點的個數(shù)n稱為線性表的長度。當n

=0時,稱為空表。

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

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

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

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

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

放的。

?線性表中第i個元素aj在計算機存儲空間中的存儲

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

?K表示每個數(shù)據(jù)元素占K個字節(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個字節(jié)

535

ADR(ax)+k%

占k個字節(jié)624

■?

??

?■731

847

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

■■9

*■

■?

10

一

ADR(aJ*6l)ka.占k個字拈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)下的主要運算:

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

⑤分解⑥合并⑦復(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

個元素之前插入)；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.線性表在順序存儲下的刪除運算

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個元素)。

輸出：刪除后的線性表存儲空間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)用

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

被稱為先進后出表或后進先出表。

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

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

指針top：指示棧頂位置；

指針bottom：指示棧底位置；

2.2.2棧及其應(yīng)用

入棧退棧

1t1

1順序棧（4個存儲空間）.swf

極頂topT

,1

棧底bottomT順序棧（8個存儲空間）.swf

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

top=0表示?？?；top=m表示棧滿；

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

存儲空間)；

釋放棧的順序存儲空間時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.棧的順序存儲及其運算

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）插入X與丫后的棧（c）退出一個元素后的棧

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隊列及其應(yīng)用

“Or什么是隊列（equeue）

但是指允許在隊尾進行插入、在隊頭進行刪除的線性表;

隊列又稱為“先進先出”（FIFO）或“后進后出”

（LILO）的線性表;

front_>

退隊運算（a）Afront_>■front_*-

BBB

CCC

入隊運算（b）rear-0■Drear->DD

—rear_>E

（a）一個隊列（b）刪除一個元素后Q）插入元素E后

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

rear-*

環(huán)隊列形式；

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

即rear=front=m;

八

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

舊1^環(huá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個元素的循環(huán)隊列(b)加入X、Y后(Q退出一個元素后

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

①當front=rear時，兩種情況:

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

增加一個標識S區(qū)別隊列滿或空

,隊列空的條件為s=0

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

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

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

#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)隊列的順序存儲空間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隊列及其應(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隊列及其應(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)點：

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

性表；

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

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

＞線性表的存儲空間不便于擴充；

＞不便于隊存儲空間動態(tài)分配；

2.3.1線性鏈表的基本概念

2.3.2線性鏈表的基本運算

2.3.3循環(huán)鏈表

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

2

1V(i)NEXT(i)

線性捱表的一個存儲結(jié)點

線性鏈表的存儲空間

例如

structnode

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

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

structnode*next；/*指針域*/

}

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

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

當HEAD=NULL（或0）時為空表

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

線性鏈表的邏輯岫

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

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

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

線性鏈表的頭指針HEAD。

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

PROCEDUREPRTLL(HEAD)

j=HEAD

WHILE(j#0)DO

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

RETURN

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

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

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

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)單鏈表的缺點：每個結(jié)點只有一個指向后件的

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

尋找；

2.雙向鏈表

O2.3.1線

3.帶鏈的棧

topa。

可利用棧及其運算

TOP

t

在從可利用棧取得一個結(jié)點p

>輸入：可利用棧棧頂指針TOP（默認）；送回可

利用棧的結(jié)點序號P。

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

認）。

PROCEDUREDISPOSE(p)

NEXT(p)=TOP；TOP=p

RETURN

＞輸入：可利用棧的棧頂指針TOP（默認）。

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

存放取得結(jié)點序號的變量P。

PROCEDURENEW(p)

p=TOP；TOP=NEXT(TOP)

RETURN

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

⑶帶鏈棧的入棧運算

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

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

PROCEDUREPUSHLL(top,x)

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

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

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

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線性鏈表的基本概念

⑷帶鏈棧的退棧運算

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

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

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

PROCEDUREPOPLL(top,y)

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

p=top

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

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

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é)點后返回*/

a2

(b)在帶鏈的隊列中插入一個新結(jié)點

aI—aZ

八

rear

front

(c)在帶鏈的隊列中冊賒一個結(jié)點

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

(1)帶鏈隊列的入隊運算

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

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

PROCEDUREADDLL(rear,x)

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

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

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

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

rear=p［改變隊尾指針］

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é)點的數(shù)據(jù)域與指針域*/

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

*rear=p；/*改變隊尾指針*/

return；

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

⑵帶鏈隊列的退隊運算

輸入：帶鏈隊列的排頭指針fronto

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

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

PROCEDUREDELLL(front,y)

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

p=front

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

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

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é)點*/

return；

O2.3.2線性鏈表的基本運算

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

一個新元素。

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

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

(4)將一個線性鏈表按要求進行分解。

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

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

⑺線性鏈表的排序。

⑻線性鏈表的查找。

o2.3.2線性鏈表的基本運算

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

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

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

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

PROCEDURELOOKST(HEAD,x,p)

p=HEAD

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

p=NEXT(p)

RETURN

o2.3.2線性鏈表的基本運算

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線性健表的基本運算

2.線性鏈表的插入

在鏈式存儲結(jié)構(gòu)下的線性表中

插入一個新元素。

O2.3.2線性健表的基本運算

可利用棧與線性鏈表

HEAD0

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

o2.3.2線性鏈表的基本運算

(1)從可利用棧取得一個結(jié)點，設(shè)該結(jié)點號為P。

并置結(jié)點P的數(shù)據(jù)域為插入的元素值b,即V(p)=b。

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

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

o2.3.2線性鏈表的基本運算

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

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

NEXT(p)=NEXT(q)

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

NEXT(q)=p

(c)p插入到q之后

2.3.2線性鏈表的基本運算

線性鏈表的插入

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

一個結(jié)點值x；插入的新元素b。

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

o2.3.2線性鏈表的基本運算

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線性鏈表的基本運算

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線性鏈表的基本運算

3.線性鏈表的刪除

在鏈式存儲結(jié)構(gòu)下的線性表中

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

O2.3.2線性健表的基本運算

可利用棧與線性鏈表

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

O2.3.2線性鏈表的基本運笄

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

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

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

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

O2.3.2線性鏈表的基本運算

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

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

O2.3.2線性鏈表的基本運算

線性鏈表的刪除

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

7E素X?

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

。

2.3.2線性鏈表的基本運算

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線性鏈表的基本運算

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é)點p*/

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

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