计算机软件技术基础

DepartmentofComputerQinghaiUniversityofChina

2010年3月

o第二章基本数据结构及其运算

2.1数据结构的基本概念

2.2线性表及其顺序存储结构

2.3线性链表及其运算

2.4树与二叉树

O2.1数据结构的基本概念

L数据结构研究的三个方面的问题：

(1)数据集合中数据元素间固有的逻辑结构；

(2)对数据处理时，各数据元素在计算机中的存储关系

(3)对各种数据结构进行的运算；

2.目的：

(1)提高数据处理的效率

(2)提高数据处理的速度

(3)尽量节省计算机存储空间

o2.1.1两个例子

2.1.1两个例子

【例】

■无序表的顺序查找46

35167885432933215446

■有序表的对分查找46

16212933354346547885

【结论】

数据元素在表中的排列顺序对查找效率是有很大影响。

【例】学生情况登记表以学号为顺序排列

学生情况登■

学号姓名性别年龄成绩

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

【结论】在对数据进行处理时，可以根据所做的运算不

同，将数据组织成不同的形式，以便于做该种运算，

从而提高数据处理的效率。

*数据结构：是指相互有关联的数据元素集合。

*数据元素：现实世界中客观存在的一切个体；

*数据元素之间的任何关系都可以用前后件关系来描述;

❖前后件关系：是数据元素之间的一个基本关系；

描述一年四季的季节名：

春，夏，秋，冬可以作为季节的数据元素；

表示数值的各个数：

18,11,35,23,16,…可以作为数值的数据元素;

O2.1.2什么是数据结构

1.数据的逻辑结构

(1)定义：指反映数据元素之间逻辑关系的数据

结构。

①表示数据元素的信息;

②表示各数据元素之间的前后件关系。

(2)两个要素：

①数据元素的集合D；

②反映D中各数据元素之间的前后件关系R。

D二元关系来表示

B=（D,R）其中：B表示数据结构。

【例】B=（D,R）

D—｛春，夏，秋，冬｝

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

说明：设a与b是D中的两个数据，则二元组（a,b）表示a是b

的前件，b是a的后件。

B=(D,R)

D={父亲，儿子，女儿}

R={(父亲，儿子)，(父亲，女儿)}

n维向量X=(xpx2,•••,xn)也是一种数据结构。即

X=(D,R)

D—{xpx2,xj

R={(xjx2),x/}

O2.1.2什么是数据结构

②数据结构的图形表示

♦数据集合D中的每一个数据元素：

用中间标有元素值的方框表示（数据结点，结点）

*用一条有向线段从前件结点指向后件结点。

【例】一年四季数据结构的图形表示

O2.1.2什么是数据结构

▼r初】家庭成员间辈份关系

O2.1.2什么是数据结构

【例】用图形表示数据结构B=(D,R),其中:

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

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

O2.1.3什么是数据结构

2.数据的存储结构（数据的物理结构）

♦数据的逻辑结构在计算机存储空间中的存放形式。

❖常用的存储结构有：

■顺序、链接、索引等存储结构。

采用不同的存储结构，其数据处理的效率是不同的。

顺序存储结构

链接存储结构

0-2.1.-4线性数据结构与非线性数据结构一一」

线性结构又称线性表：

(1)有且只有一个根结点；

(2)每一个结点最多有一个前件，也最多有一个后件

非线性结构：

如果一个数据结构不是线性结构

不是线性结构的数据结构特例

2.2.1线性表及其运算

2.2.2栈及其应用

2.2.3队列及其应用

1.什么是线性表(LinearList)

♦n维向量(xjx2,…，x)是一个长度为n的线性表；

♦英文小写字母表(a,b,c,…，z)是一个长度为26的

线性表；

♦：.一年中的四个季节(春，夏，秋，冬)是一个长度为4

的线性表；

矩阵是一个比较复杂的线性表；

学生情况登记表是一个复杂的线性表

由若干数据项组成的数据元素称为记录(record)

由多个记录构成的线性表又称为文件(file)

学生情况登记表

姓名学号性别年龄健康状况

王强80035619良好

刘建平80035720

赵军80036119良好

葛文华800367；21较差

•■•*.*

O2.2线性表及其顺序存储结构

尸11)线性表的定义:

是由n(n》0)个数据元素a：a2,•••,组成的一

个

有限序列，表中的每一个数据元素，除了第一个外，

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

后件。即线性表或是一个空表，或可以表示为：

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

♦其中：％(i=l,2,…，n)是属于数据对象的元

素，通常也称其为线性表中的一个结点。

O2.2线性表及其顺序存储结构

(2)非空线性表结构特征：

①有且只有一个根结点a1，它无前件；

②有且只有一个终端结点a”，它无后件；

③除根结点与终端结点外，其它所有结点有且

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

♦线性表中结点的个数n称为线性表的长度。当n

=0时,称为空表。

O2.2线性表及其顺序存储结构

12.线性表的顺序存储结构

(1)线性表的顺序存储结构基本特点：

①所有元素所占的存储空间是连续的；

②各数据元素在存储空间中是按逻辑顺序依次存

放的。

♦线性表中第i个元素aj在计算机存储空间中的存储

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

♦K表示每个数据元素占K个字节

O2.2线性表及其顺序存储结构

长度为n的线性表整型一维数组

(a1，@2，a,a/存放长度为8

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

顺序存储结构129的线性表

218

•(29,18,56,63,3

存储地址*

■356

4635,24,31,47)

ADR(ajai占k个字节

535

ADR(ax)+k%

占k个字节624

■•

••

•■731

847

ADR(aJ♦11-l)kax占k个字力

■■9

*■

■•

10

一

ADR(aJ*6l)ka.占k个字拈11

■

*

■12

o2.2线性表及其顺序存储结构

2)建立空线性表的顺序存储空间(即初始化线

性表的顺序存储空间)

#includenstdlib.hn

voidinitsl(v,m,n)

ET*v；intm,*n；

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

*n=0；

return；

}

释放线性表的顺序存储空间free(v)；

O2.2线性表及其顺序存储结构

(3)线性表顺序存储结构下的主要运算:

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

⑤分解⑥合并⑦复制⑧逆转

O2.2线性表及其顺序存储结构

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线性表及其顺序存储结构

输入：线性表的存储空---------------------------

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线性表及其顺序存储结构

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线性表及其顺序存储结构

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线性表及其顺序存储结构

输入：线性表的存储空间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线性表及其顺序存储结构

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栈及其应用

1.什么是栈(stack)

主程序与子程序之间的调用关系

MAINSUB1SUB2SUB3SUB4

CALLSUB1CALLSUB2CALLSUB3CALLSUB4...

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

ENDRETURNRETURNRETURNRETURN

栈与递归.swf

2.2.2栈及其应用

栈：限定在一端进行插入与删除的线性表；栈也

被称为先进后出表或后进先出表。

栈顶:允许插入与删除的一端称为；

栈底：不允许插入与删除的另一端称为；

指针top：指示栈顶位置；

指针bottom：指示栈底位置；

2.2.2栈及其应用

入栈退栈

1t1

1顺序栈（4个存储空间）.swf

极顶topT

,1

栈底bottomT顺序栈（8个存储空间）.swf

)2.2.2栈及其应用

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栈及其应用

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队列及其应用

“Or什么是队列（equeue）

但是指允许在队尾进行插入、在队头进行删除的线性表;

队列又称为“先进先出”（FIFO）或“后进后出”

（LILO）的线性表;

front_>

退队运算（a）Afront_>■front_*-

BBB

CCC

入队运算（b）rear-0■Drear->DD

—rear_>E

（a）一个队列（b）删除一个元素后Q）插入元素E后

⑨队列的顺序循环结构采用循

rear-*

环队列形式；

◎■循环队列的初始状态为空，

即rear=front=m;

八

O2.2.3队列及其应用

旧1^环队列及其运算

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

88X8X

rear_*7FTF7F

6E6E6E

5D5D5D

4C4C4C

3B3B3B

2A2Afront-*-2

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

rear-*

[a)具有6个元素的循环队列(b)加入X、Y后(Q退出一个元素后

o2.2.3队列及其应用

①当front=rear时，两种情况:

循环队列满或循环队列空

增加一个标识S区别队列满或空

,队列空的条件为s=0

队列满的条件为(s=1)且front=rear

o2.2.3队列及其应用

②建立(初始化)循环队列顺序存储空间

#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；

释放循环队列的顺序存储空间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队列及其应用

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队列及其应用

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线性表及其顺序存储结构

0一―一―

线性表顺序存储结构的优点：

＞简单、运算方便，尤其适合小线性表或长度固定的线

性表；

线性表顺序存储结构的缺点：

＞插入或删除一个元素时，需要移动大量的数据元素；

＞线性表的存储空间不便于扩充；

＞不便于队存储空间动态分配；

2.3.1线性链表的基本概念

2.3.2线性链表的基本运算

2.3.3循环链表

存储序号数据域指针域

2

1V(i)NEXT(i)

线性捱表的一个存储结点

线性链表的存储空间

例如

structnode

{charname[10]；/*数据域*/

charsex；/*数据域*/

structnode*next；/*指针域*/

}

线性捱表的逻辑结构

HEAD_^W1►数据2>・・・_►数据n皿

当HEAD=NULL（或0）时为空表

线性捱表的物理状态

线性链表的逻辑岫

o2.3.1线性链表的基本概念

【算法】依次输出线性链表中的各结点值

输入：线性链表的存储空间V(Lm)、NEXT(1：m)；

线性链表的头指针HEAD。

输出：依次输出线性链表中各结点的值。

PROCEDUREPRTLL(HEAD)

j=HEAD

WHILE(j#0)DO

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

RETURN

o2.3.1线性链表的基本概念

#include"stdlib.h"/*malloc函数需要*/

structnode/*定义结点类型列

intd；/*数据域*/

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)单链表的缺点：每个结点只有一个指向后件的

指针，如果需要找到它的前件必须从指针开始重新

寻找；

2.双向链表

O2.3.1线

3.带链的栈

topa。

可利用栈及其运算

TOP

t

在从可利用栈取得一个结点p

>输入：可利用栈栈顶指针TOP（默认）；送回可

利用栈的结点序号P。

>输出：结点P入栈后的可利用栈栈顶指针TOP（默

认）。

PROCEDUREDISPOSE(p)

NEXT(p)=TOP；TOP=p

RETURN

＞输入：可利用栈的栈顶指针TOP（默认）。

＞输出：退栈后的可利用栈栈顶指针TOP（默认）；

存放取得结点序号的变量P。

PROCEDURENEW(p)

p=TOP；TOP=NEXT(TOP)

RETURN

o2.3.1线性链表的基本概念

⑶带链栈的入栈运算

输入：带链栈的栈顶指针top；入栈的元素值X。

输出：元素X入栈后的带链栈栈顶指针top。

PROCEDUREPUSHLL(top,x)

NEW(p)［从可利用栈取得一个新结点］

V(p)=x［置新结点数据域］

NEXT(p)=top［置新结点指针域］

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；存放退

出结点元素值的变量y。

PROCEDUREPOPLL(top,y)

y=V(top)［取出标顶元未值］

p=top

top=NEXT(p)［改变栈顶指针］

DISPOSE(p)［被删除结点送回可利用栈］

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；/*释放被删除结点后返回*/

a2

(b)在带链的队列中插入一个新结点

aI—aZ

八

rear

front

(c)在带链的队列中册赊一个结点

o2.3.1线性链表的基本概念

(1)带链队列的入队运算

»输入：带链队列的队尾指针rear；入队的新元素x。

A输出：元素x入队后的带链队列队尾指针rear。

PROCEDUREADDLL(rear,x)

NEW(p)［从可利用栈取得一个新结点p］

V(p)=x［置新结点的数据域］

NEXT(p)=0［置新结点的指针为空］

NEXT(rear)=p［最后一个结点的指针指向新结点］

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；/*置新结点的数据域与指针域*/

^rear->next=p；/*置最后一个结点的指针指向新结点*/

*rear=p；/*改变队尾指针*/

return；

o2.3.1线性链表的基本概念

⑵带链队列的退队运算

输入：带链队列的排头指针fronto

»输出：退队后的带链队列排头指针丘ont；存放

退出结点值的变量y。

PROCEDUREDELLL(front,y)

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

p=front

front=NEXT(front)［改变排头指针］

DISPOSE(p)［释放删除的结点］

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)；/*释放被删除结点*/

return；

O2.3.2线性链表的基本运算

⑴在线性链表中包含指定元素的结点之前插入

一个新元素。

⑵在线性链表中删除包含指定元素的结点。

(3)将两个线性链表按要求合并成一个线性链表。

(4)将一个线性链表按要求进行分解。

(5)逆转线性链表。

(6)复制线性链表。

⑺线性链表的排序。

⑻线性链表的查找。

o2.3.2线性链表的基本运算

i.在线性链表中查找指定元素

在非空线性链表中寻找包含元素X的前一个结点p

输入：非空线性链表头指针HEAD；被寻找元素X。

输出：非空线性链表中包含元素x的前一个结点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.线性链表的插入

在链式存储结构下的线性表中

插入一个新元素。

O2.3.2线性健表的基本运算

可利用栈与线性链表

HEAD0

(a)原来的可利用栈与线性链表

o2.3.2线性链表的基本运算

(1)从可利用栈取得一个结点，设该结点号为P。

并置结点P的数据域为插入的元素值b,即V(p)=b。

⑵在线性链表中寻找包含元素x的前一个结点q。

(b)从可利用栈取得结点p,在线性瞰中找到包含元素X的前一个结点q

o2.3.2线性链表的基本运算

(3)将结点p插入到结点q之后:

①使结点P指向包含元素x的结点，即

NEXT(p)=NEXT(q)

②使结点q的指针域内容改为指向结点P，即

NEXT(q)=p

(c)p插入到q之后

2.3.2线性链表的基本运算

线性链表的插入

输入：线性链表的头指针HEAD；插入位置处的前

一个结点值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.线性链表的删除

在链式存储结构下的线性表中

删除包含指定元素的结点。

O2.3.2线性健表的基本运算

可利用栈与线性链表

Q）原来的可利用栈与线性链表

O2.3.2线性链表的基本运笄

(1)寻找包含元素X的前一个结点q。

则包含元素x的结点序号p=NEXT(q)o

(2)将结点q后的结点P删除,即NEXT(q)=NEXT(p)o

(b)从线性链表中删除包含元素x的结点p后

O2.3.2线性链表的基本运算

(3)将包含元素x的结点p送回可利用栈。

(C)将被删除的结点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；/*删除结点p*/

free(p)；/*释版结点p*/return；

⑴在循环链表中增加