高等教育自学考试 （自考）数据结构导论 全册讲义

第一章概论

一、学习目的与要求

理解数据、数据元素和数据项的概念及其相互关系；

理解数据结构的含义；

理解逻辑结构、基本运算和存储结构的概念，意义和分类；

理解存储结构与逻辑结构的关系；

理解算法的概念：

理解衡量一个算法效率的两个标准：时间复杂度和空间复杂度。

二、课程内容

1.1引言

计算机处理问题的-•般步骤：

（1）从具体的问题抽象出一个适当的数学模型；

（2）设计一个求解该数学模型的算法；

（3）用某种计算机语言编写实现该算法的程序，调试和运行程序直至最终得到问题的解答。

数据结构编程数据结构

原始数据（逻辑结构）（存错结构）

处理要求*,

--程序语句序列

实际问题数学模型计算机程序实现

算法+数据结构:程序

1.2基本概念和术语

1.2.1数据、数据元素和数据项

数据：所有被计算机存储、处理的对象。数值、布尔值等扩展到字符串、表格、图像甚至声音等。

数据元素（元素）：数据的基本单位，在程序中作为一个整体而加以考虑和处理。

数据项：一般情况下，数据元素由数据项组成。在数据库中数据项又称为字段或域。.它是数据的不可

分割的最小标识单位。

结合表1T,理解数据、数据元素、数据项三个概念及之间的联系

表1-1学生档案信息表

学号姓名性别年龄入学成绩

1001王韬男2()589

1002潘小欣女21580

1003张艳女19568

1004赵李军男185S0

1005刘勇男22585

1.2.2数据的逻辑结构

数据的逻辑结构是指数据元素之间的逻辑关系。所谓逻辑关系是指数据元素之间的关联方式或“邻接关

系”

四种基本的逻辑结构：

•集合：集合中任意两个结点之间都没有邻接关系，组织形式松散。

・线性结构：一对一

•树形结构：一对多

•图结构：多对多

a）集合b）线性结构C）树形结构d）图结构

1.2.3数据的存储结构

数据的逻辑结构在计算机中的实现称为数据的存储结构（或物理结构）。一般情况下，一个存储结构包

括以下两个部分：

（1）存储数据元素；

（2）数据元素之间的关联方式。

主要的存储方式：顺序存储、链式存储。顺序存储方式是指所有存储结点存放在一个连续的存储区里。

利用结点在存储器中的相对位置来表示数据元素之间的逻辑关系。链式存储方式是指每个存储结点除了含

有一个数据元素外，还包含指针，每个指针指向一个与本结点有逻辑关系的结点，用指针表示数据元素之

间的逻辑关系。

除了上述两种存储方式之外，还有索引存储方式和散列存储方式。

1.2.4运算

运算是指在某种逻辑结构上施加的操作，即对逻辑结构的加工。这种加工以数据的逻辑结构为对象。一

般来说，在每个逻辑结构上，都定义了一组基本运算，这些运算包括：建立、查找、读取、插入和删除等。

1.3算法及描述

一个算法给规定了求解给定问题所需的处理步骤及其执行顺序，使得给定问题能够在有限的时间内被求

解。本书采用类C语言来描述算法

1）函数描述形式.

函数类型函数名（函数参数表）〃算法说明

{

语句序列

）

2）输入、输出语句

输入语句：scanf（格式串，变量1,变量n）；

输出语句：printf（格式串，变量1,变量n）；

3）赋值语句变量名=表达式；

4）选择语句

1＞条件语句：

if（表达式）语句：

或

if（表达式）语句；

else语句；

2》分支语句：

switch

{case条件1：语句序列；break；

case条件2：语句序列;break；

case条件n：语句序列；break；

default：语句序列；}

其中“default：语句序列；”可以省略。

5）循环语句

for（赋初值表达式序列；条件；修改表达式序列）语句；

while（条件）语句；

do,

语句；

}while（条件）；

6）结束语句

1＞函数结束语句：return表达式；

2＞case结束语句break；

3》异常结束语句：exit（异常代码）；

7）出错语句：error（"错误描述"）

8）注释

单行注释：〃注释内容

多行注释：/*注释内容*/

1.4算法分析

通常评价算法好坏的因素包括以下几个方面：

1)正确性：能正确地实现预定的功能，满足具体问题的需要。

2)易读性：易于阅读、理解和交流，便于调试、修改和扩充。

3)健壮性：即使输入非法数据，算法也能适当地做出反应或进行处理，不会产生预料不到的运行结果。

4)时空性：一个算法的时空性是指该算法的时间性能(或时间效率)和空间性能(或空间效率)，前

者是算法包含的计算量，后者是算法需要的存储量。

1.4.1时间复杂度

【例1-4】编制函数求1!+制+...求!。

【分析】对于这个问题，可以写出两个算法，如图所示。

intfactl(intn)intfact2(intn)

{intirj,temp,s;{intirjrtemp,s;

s-0;s-0;temp-1:

fori++)for(i-1;i<-n;i+*)

{temp-1;{temp-temp*i;

for(j-1;j<-i；j++)s-s+temp;

temp-temp*j;).

s-s+temp;returns;

))

returns;

两个算法的计算量不同，如何估算算法的计算量?可在算法中合理地选择一种或几种操作作为“基本操

作”，对给定的输入，确定算法共执行了多少次基本操作，可将基本操作次数作为该算法的时间度量。

假如问题的输入规模为n,一般情况下，一个算法的计算量是问题规模n的函数。设函数factl中乘法、

加法司赋值的次数记为T(n),则

T(n)=n(n+1)/2+n+n(n+1)/2+2n-l=2(n2+n)/2+3n+l=n2+4n+l

当n充分大时，i?这一项对T(n)的值起着支配作用，采用数学记号0(n2)表示T(n)的近似值，写

为T(n)=0(n2),这种表示法称为大0表示法，它的含义是：当n充分大时，算法的执行时间与产成

正比,大。表示法的具体提法是：当且仅当存在正常数c和n。，使得：T(n)<=cf(n)。

对所有n>n。成立。其中，f(n)为问题的规模n的某个函数，大0表示法也称为渐进表示法，它不考虑

具体的运行时间，只给出算法在问题规模n下执行时间的上界。

T(n)=0(f(n))称为算法的渐进时间复杂度，简称时间复杂度。

3

常见的时间复杂度有：常数阶0(1),对数阶0(log2n),线性阶0(n),多项式阶0(M)、0(n),

指数阶0(20)

最坏时间复杂度、平均时间复杂度、最好时间复杂度

1.4.2空间复杂度

一个算法的空间复杂度定义为该算法所耗费的存储空间，它也是问题规模n的函数。通常可记为：S(n)

=0(g(n))其中，g(n)为问题规模n的某个函数。空间复杂度是对一个算法在运行过程中临时占用存

储空间大小的量度。

一个算法在执行期间所需要的存储空间量应包括以下三个部分：

(1)程序代码所占用的空间

(2)输入数据所占用的空间

(3)辅助变量所占用的空间

三、考核的知识点与考核要求

1.数据结构、数据、数据元素和数据项的概念

识记：数据结构；数据；数据元素；数据项。

领会：数据结构的作用；数据、数据元素、数据项三者关系。

2.数据逻辑结构和数据存储结构

识记：数据逻辑结构、数据存储结构。

领会：四类基本逻辑结构的特点；顺序存储结构；链式存储结构；逻辑结沟与存储结构的关系。

3.运算、算法和算法分析

识记：运算；基本运算；算法分析；时间复杂度；空间复杂度。

领会：运算与数据结构的关系；算法的描述方法；算法的评价因素；时间复杂度分析方法；空间复杂度

分析方法。

简单应用：运用类C语言描述算法；简单算法时间复杂度分析：简单算法的空间复杂度分析。

四、本章重点、难点

本章重点：数据结构、数据逻辑结构、数据存储结构以及运算等概念。

本章难点：算法时间复杂度分析。

五、练习

【例题•单选题】与数据元素本身的形式、内容、相对位置、个数无关的是数据的()。

A.存储结构

B.逻辑结构

C.类型

D.运算实现

I1正确答案JB

『答案解析』数据的物理存储、数据类型、运算实现与数据元素本身的形式、内容、相对位置，个数都

密切相关，而逻辑结构反映的是数据元素之间的邻接方式。参见教材P25。

【例题・单选题】算法时间复杂度指的是()。

A.一个算法的确切执行时间

B.一个程序的确切执行时间

C.算法在给定输入下的计算量

D.算法在给定时间下的计算量

『正确答案」C

『答案解析』首先算法的时间复杂度是对计算量的估算，其含义是对给定的输入，确定算法共执行了多

少次基本操作。参见教材P29。

【例题•单选题】下面几种算法时间复杂度阶数中()最小。

A.0(logn)

B.O(n)

C.O(n2)

D.O(2n)

『正确答案』A

I1答案解析』对于常见的几种算法时间复杂度而言：0(1)<0(logn)<0(n)<0(nlogn)<0(n2)<0

(n3)<0(2n)<0(n!)<0(nn)«参见教材P30。

【例题•单选题】下面几种算法时间复杂度阶数中()最大。

A.0(logn)

B.O(n)

C.O(n2)

D.0(nlogn)

I1正确答案』C

I1答案解析』对于常见的儿种算法时间复杂度而言：0(D<0(logn)<0(n)<0(nlogn)<0(n2)<0

(n3)<0(2n)<0(n!)<0(nn)o参见教材P30。

【例题•单选题】算法的空间复杂度指的是()。

A.算法本身所占用的存储空间的大小

B.算法中输入数据所占用的存储空间的大小

C.算法中所占用的所有存储空间的大小

D.算法中除输入数据占用的存储空间之外所需的附加存储空间的大小

『正确答案』D

f答案解析」算法的空间复杂度定义为该算法所耗费的存储空间。参见教材P31。

【例题・填空题】从数据结构的观点看，通常所说的“数据”应分成三个不同的层次，即、

___________和___________

『正确答案』数据、数据元素、数据项

I1答案解析J这道题考察关于数据的桂关概念。参见教材P24。

【例题•填空题】数据项又称为—或,它是数据的不可分割的最小标识单位。

『正确答案』字段、域

I1答案解析』这道题考察关于数据的相关概念。参见教材P24。

【例题•填空题】根据数据元素之间关系的不同特性，通常有______、_______、________和

四类基本逻辑结构，它们反映了四种基本的数据组织形式。

『正确答案』集合、线性结构、树形结构、图结构

I1答案解析』这道题考察关于数据的匹种逻辑结构。参见教材P25。

【例题•填空题】一般情况下，一个算法的时间复杂度是的函数

r正确答案J算法输入规模

『答案解析』这道题考察时间复杂度的概念"参见教材P29。

【例题•填空题】常见算法时间复杂度的阶数有常数阶0()、对数阶0()、线性

阶0(_________)、平方阶0()和指数阶0()。通常认为，具有指数阶量级的算

法是的，而量级低于平方阶的算法是。

［正确答案［1、logn.n、n\2\实原不可计算、高效

I■答案解析』这道题对考察时间复杂度的理解，应该掌握常见的几种时间复杂度的大小关系及其含义。

参见教材P30。

【例题•填空题】下述算法的时间复杂度T(n)=

for(i=l；i<=n；i++)

(

k++；

for(j=l；j<=n；j++)

m+=k；

)

『正确答案』0(n2)

［答案解析］这道题考察算法时间复杂度的计算。参见教材P30。

第二章线性表

一、学习目的与要求

顺序表和单链表分别是简单、基本的顺序存储结构和链式存储结构。顺序表和单链表上实现基本运算的

算法是数据结构中简单和基本的算法。这些内容构成以下各章的重要基础，因此本章是本课程的重点之一。

本章要求：理解线性表的概念；熟练掌握顺序表和链表的组织方法及实现基本运算的算法；掌握在顺序

表和链表上进行算法设计的基本技能；了解顺序表与链表的优缺点。

二、课程内容

2.1线性表的基本概念

线性表中结点具有一对一的关系，如果结点数不为零，则除起始结点没有直接前驱外，其他每个结点有

且仅有一个直接前驱；除终端结点没有直接后继外，其他每个结点有且仅有一个直接后继。

线性表基本运算有：初始化、求表长、读表元素、定位、插入、删除。

2.2线性表的顺序存储

2.2.1线性表的顺序存储

线性表的顺序存储：逻辑结构相邻的结点其存储位置也相邻。用顺序存储实现的线性表称为顺序表，一

般用数组来表示顺序表，如图2-1所示

空闲

---------------人--------------

3•••

致俄下标：0IMaxsizc-I

图2T顺序表不意图

【例2-1】学生档案信息表的顺序存储实现。

【分析】根据学生档案信息，给出顺序表具体的类型定义。

constintMaxsize-7;〃颈先定义数组大小

typedefstruct

{intnum;〃学号

charname[8];〃姓名

charsex[2];〃性别

intage;〃年龄

intscore;〃入学成绩

}DataType;〃定义结点的类型

typedefstruct

(DataTypedata[Maxsize];〃存放数据的数组

intlength;〃线性表的实际长度

)SeqList;〃取序表的类型

SeqListstudent;//student为顺序表的名称

2.2.2线性表的基本运算在顺序表上的实现

插入

顺序表的插入运算InsertSeqlist(SeqListL,DataTypex,inii)是指在顺序表的第i(l<=i<=n+l)

个元素之前，插入一个新元素x。使长度为n的线性表(a】，a2,,a-,a”...，a„)变为长度为n+1

的线性表(ai,a2>...»a(-i,x,ai,...»a,.)。

始入位H

空闱

ttiflF幄0i-2i-lin-lnMaxsize-1

空位空闲

敏倒下标:MAXsize-1

ftflF标:MJUMZC-I

图2-2a)插入前b)插入前，移出空位之后c)插入x后

具体算法描述如下：

voidInsertSeqlist(SeqListL,DataTypex,int幼

(〃将元素x插入到履序表L的第i个数据元素之前

if(L.length-"Maxsize)exit('表己H;

if(1<1||i>L.len9th*l)•xitC位置榜・“〃检杳插入位置是否合法

for(j»L.length〃初始i-L.length

L.data[j]"L.data[j-l];〃依次后移

L.data(i-l]ax;〃元素x置入到下标为1T的位置

L.length”；〃表长度加1

}

2)删除

删除运算DeleteSeqlist(SeqListL,inti)是指将线性表的第i(l<=i<=n)个数据元素删去，使

长度为n的线性表(ai,a2»...,a1,at,at*t>...»an)变为长度为nT的线性表(ai,a2,...,al,

ai+l,•..,Hn)©

胸下*:

a)

蝴

的下标:

b)

图2-3顺序表删除元素前、后的状况示意图

a)删除前b)删除后

具体算法描述如下:

voidDeleteSeqList(SeqListL,inc

(〃副除线性表L中的第i个数据结点

if(1<1|I1>L.length)〃检香位置是否合法

exit(•非法位置・)；

for(j-i;j<L.length;j++)〃第i个元素的下标为i-1

L.data[j-l]»L.data[j];〃依次左移

L.length一;〃表长度充1

3)定位

定位运算LocateSeqlist(SeqListL,DataTypex)的功能是查找出线性表L中值等于x的结点序号的

最小值，当找不到值为x的结点时，返回结果0。下列算法从左往右扫描顺序表中的元素，考察元素的值

是否等于X,描述算法如下：

intLocateSeqlist(SeqListL,DataTypex)

(

inti-0;

while((i<L.length)u(，&8[1]!”))〃在顺序表中查找值为乂的结点

if(i<L.length)return-i+1;〃若找到值为x的元素，运回元索的序号

elsereturn0;〃未查找到值为x的元素，返回0

2.2.3顺序表实现算法的分析

插入：0(n)

删除：0(n)

定位：0(n)

2.3线性表的链接存储

2.3.1单链表的类型定义

线性表的链接存储是指它的存储结构是链式的。线性表常见的链式存储结构有单链表、循环链表和双向

循环徒表，其中最简单的是单链表。

下面举个例子说明单链表的结构：

00000000

图2-4

单链表的一个结点由两部分组成：数据元素和指针，相当于火车的车厢和车钩。各个结点在内存中的存

储位置并不一定连续。链表的结点可以重新连接，相当于火车的编组。

图2-5

如图所示，data部分称为数据域，用于存储线性表的一个数据元素，next部分称为指针域或链域，用

于存放一个指针，该指针指向本结点所含数据元素的直接后继结点。

非空的单链表和空单链表，如图所示

■站点尾绐点

｛』［NULL

NULL

图2-6单捱表示例

a）非空的单链表b）空单链表

我们通常用结构体类型来定义单链表的结点数据类型:

单锌表的类型定义如下：

Typedefstructnode

（

DataTypedata；//数据域

structnode*next；〃指针域

}Node,*LinkList；

【例2-2】学生档案信息链表的类型完整描述

typedefstruct

{intnum;〃学号

charname[8];〃姓名

charsex[2j;〃性别

intage;〃年龄

intscore;〃入学成绩

)DataType;〃定义结点的类型

typedefstructnode

(DataType.data;〃数据城

structnode•next;〃指针城

}Node,*LinkList;//Node是箧表结点的类型

LinkListhead;

则学生档案信息链式存储实现，如图2-7所示

head-।

图2-7

为了便于运算实现，在单链表的第一个结点之前增设一个类型相同的结点，称之为头结点，其他结点称

为表结点。

b)

图2-8带头结点的单捱表

a）带头结点的非空单链表b）带头结点的空单链表

2.3.2线性表的基本运算在单链表上的实现

我们首先来讨论单链表的一些基本运算，这是使用单链表的开始。

初始化

初始化的工作是建立一个空表，空表由一个头指针和一个头结点组成。

算法描述如下：

LinkListInitiateLinkList()

〃建立一个空的单健表

(

LinkListhead;〃头指针

head«malloc(sizeof(Node));〃动态构建一结点,它是头结点

head->next-NULL;

returnhead;

}

2.求表长

在单链表存储结构中，线性表的表长等于单链表中数据元素的结点个数，即除了头结点以外的结点的个

数。图2-9所示为数据域为整数的单链表，其表长为4。

图2-9

通过结点的指针域来从头至尾访问每一个结点求表长，让工作指针P通过指针域逐个结点向尾结点移动,

工作指针每向尾部移动一个结点，让计数器加1。这样，直到工作指针p-〉next为NULL。

算法描述如下：

intLengthLinklist(LinkListhead)

〃求单储表表head的长度

{Node■p-head;〃p是工作指计,初始时p指向头结点

intcnt-0;〃计数器段初值

while(p->next!-NULL)〃判断是否为尾结点

(p»p->next;〃指针移动到F一个站点

ent+f;

returnent;〃返回表长

3.读表元素

通常给定一个序号i,查找线性表的第i个元素。从头指针出发，一直往后移动，直到第i个结点。

单徒表的读表元素算法描述如下：

Node*GetLinklist(LinkListhead,int1)

〃在单处表head中查找第i个元素结点,若找到,则返回指向该结点的指针;否则返回NULL

Node*p;〃p是工作指针

p-head->next;〃初始时,P指向首结点

intc-1;

while((c<i)&&(p!-NULL))〃当未到第i结点且未到尾结点时维埃后移

(p-p->next;C++;}

if(i—c)returnp;〃找到第i个站点

elsereturnNULL;〃i<l或i>n,i值不合法,1E我失效

}

4.定位

线性表的定位运算，就是对给定表元素的值，找出这个元素的位置。从头至尾访问链表，直至找到需要

的结点，返回其序号。若未找到，返回0。

定位运算算法描述如下：

intLocateLinklist(LinkListhead,DataTypex)

〃糕head中第一个值等于x的球的序号，若不存在研轴,诋醐果为0

Node*p»head;//pftim

PT>->next;〃初始时p指向首献

inti-0;〃i快献的*%这星物值为0

while(p!-NULLUp-xiata!-x)〃访问隹表

(i**;

p«p->next;

if(p!・NULL)returni+1;

elsereturn0;

)

5.插入

单性表的插入运算是将给定值为x的元素插入到链表head的第i个结点之前。插入结点的指针变化如

图2-10所示。

lead

•'・:41J(JI**1>T4|NULL

帆/©

pQ—•x

图2-10

插入算法描述如下:

插入算渊遨吓：

voidInsertLinklist(LinkListhead>DataTypex*inti)

〃在表head的第i个数据元素结点之前插入一个以x为值的新站点

{Node*pr*q;

if(i«l)q-head;

elseq-GetLinklist(head,i-1);〃找第i-1个数碧元素结点

if(q-NULL)〃第个结点不存在

exit(哦不期I入的位加);

else

{p-malloc(sizeof(Node));p->data-x;〃生成新结点

p->next=q->next;〃新结点镂域指向*q的后继结点

q->next*p;〃修改*q的鞋城

注意：p>next=q>next和q>next=p两条语句的执行顺序不能颠倒。

6.删除

删除运算是给定一个值i,将链表中第i个结点从链表中移出，并修改相关结点的指针域，以维持剩余

结点的链接关系。删除结点的指针变化如图2-11所示。

图2-11

单铢表的删除运算算法描述如下:

voidDeleteLinklist(LinkListhead,int1)

〃剧除表head的第1个结点

(Node*q;

if(i・・l)q*head;

elseq-GetLinkli8t(head,i-l);〃先找持翻结点的宜族前驱

if(q!-NOLL&&q->next1-NULL)〃若直接前驱存在且待删结点存在

(

p-q->next;〃p指向待加结点

q->next-p->next;〃移出符M结点

free(p);〃释放已移出结点P的空间

)

elseexit「找不到要!!除的结点”)；〃结点不存在

注意，free(p)是必不可少的，无用结点需要释放它的空间。

2.4其他运算在单链表上的实现

2.21建表

我们讨论建立含头结点的单链表。

方法一：尾插法，这个过程分为三部，首先建立带头结点的空表；其次建立一个新结点，然后将结点连

接到头结点之后；重复后面两个步骤，直到线性表中所有元素链接到单链表中。

代玛描述如下：

LlnkLiatCreatLinkliitl<)

调用InitiateLinkllstmIns^rtllnkllst实现龙发算法・假定0是输入结束标志

(Llnklltthead;

intx,i;

head»Initl«t«Llnklist();〃建立空哀

1-1;〃置Ml入位置初值

■c・nf《"Qd".&x);//读入第一个敛据元素，X为整型

while(x!"0);〃必人的不是靖束标志时逑就插入

(f

InaertLinkliat(head,x,l);〃将珀入插入到h•2农足

〃修改循入位置

scant4x);//读下一元素

returnhead;

\

方法二：上面的算法由于每次插入都从表头开始查找，比较浪费时间。因为每次都是把新的结点链接到

表尾，我们可以用一个指针指向尾结点，这样就为下一个新结点指明了插入位置。

代码描述如下：

LinkListCreateLinklist2()

//q是一个LinkU4类型的变量,用耒揩示e入位IE

{Linklisthead;

Node

intx;

heaXalloc(sizeof(Node));〃生成头结点

q«head;〃尾指竹I初值

scanf("Id",&x);〃读入第一个元素

while(x!-0)〃■入的不是结束标志时维她人

(

t«^aalloc(sizeof(Node));t->data-x;〃生成一个新结点

q->next-t;〃新结点t修入

q-t;〃修改足指计q,指向新的尾结点

scanf〃读入下一个元素

)

q->next-NULL;returnhead;〃q折角尾鳍点,置尾结点标志

方法中的链接操作如图2-12,它的时间与元素个数成正比，故其时间复杂度为0(n)。

图2-12建表算法中的表尾链入操作

方法三：头插法，始终将新增加的结点插入到头结点之后，第一个数据之前。如图2T3所示。

图2T3建表算法中的在表头键入操作

代玛描述如下：

LinkListCreateLinklist3()

(Linkllsthead;

Node*p;

intx;

head-malloc(sizeof(Node));〃生成头站点

hcad->next-NULL;

scandf("%d"/&x);

while(x)//x-0时结束输入

(

p-raalloc(sizeof(Node));

p-xlata-x;

p->next*head->next;//Itflt插入刎愈表的第一个18点处

head->next-p;

scandf("Id",&x);

)

returnhead;

2.4.2删除重复结点

在线性表中，可能有多个结点的元素值是相同的，它们是重复结点。可以设计算法删除重复结点，只保

留结点序号最小的那个结点。例如，线性表(4,7,2,5,2,4),删除重复结点后结果为(4,7,2,5)。

用他表作为存储结构，细化上述算法得到最后的算法描述：

voidPurgeLinkllst(LinkListh««d)

//»»«head中多余的重复结点

(Node•p,*q,*r;

q-head->next)//q指示当就检套站点的位置，量其切值指向苜站点

while(q!-NULL)

//当前检行特点・q不是用姑点时，寻找弁■除它的・复州点

(

p・q；〃工作指计P指向*q

while(p->next!-NULL)

//S-p的后震鳍点存在时，将其敷**与*q故招域比较

if(p->next-xiata-q->data)//若・(p->next)的质夏站点

(

r-p->next//r指向特刷结点

p->n«xt-r—>ncxt;

〃移出结点•(p->next),p->next指向原来，(p->n«xtj的后罐饰点

fre«(r)i

)

•ls«p^>->next;〃否则，让p指向下一个结点

q-q->next;//更新依蛋结点

单徒表上删除结点时的指针变化如图2-14所示:

।W句•pfr_*।।+->l«rNULL

图2-14

2.5其他链表

2.5.1循环链表

在单链表中，如果让最后一个结点的指针域指向第一个结点可以构成循环链表。在循环链表中，从任一

结点出发能够扫描整个链表。

图2-15给出常见的循环链表，图2-15a、b分别表示带头结点的非空循环链表和空循环链表，头指针

是head。在这种结构下，要找到尾结点可以从头指针head出发扫描所有的结点。在图2-15c、d中，链

表没有设头指针，只设尾指针rear。这样，首结点表示为：rear->next->next,首尾结点都能方便地访问。

rear

图2-15

a）带头结点的非空循环链表

b）带头结点的空循环链表

c）设立尾指针的非空循环链表

d）设立尾指针的空循环链表

2.5.2双向循环链表

双向循环链表的结点结构如图2-16所示:

priordatanext

图2-16双向循环链表结点结构

双向循环链表示意图如图2-17所示，prior与next类型相同，它指向直接前驱结点。头结点的prior

指向最后一个结点，最后一个结点的next指向头结点。

图2-17双向循环链表示意图

a）空表b）非空表

双向循环链表与单链表类似，用C语言描述如下:

structdbnode

{Datatypedata;

structdbnode*prior,*next;

)

typedefstructdbnode*dbpolnter;

typedefdbpointerDLinkList;

双向循环链表是一种对称结构，可以用下列等式表示：

p=p->prior->next=p->next->prior

在单链表中，找直接后继结点的时间复杂度是0(1)。在双向循环链表中，找直接后继结点和前驱结点

的时间复杂度都是0(1)。

双向循环链表的求表长、定位、按序查找等运算的实现和单链表基本相同，这里我们讨论它的插入和删

除操作。

1.删除

在单链表中删除结点时，需要用一个指针指向待删结点的前驱结点，在双循环链表中，设p指向待删结

点，删除*P可通过下述语句完成，执行效果如图2T8所示。

(1)p->prior->next=p->next；

//p前驱结点的后链指向p的后继结点

(2)p->next->prior=p->prior；

//P后继结点的前链指向P的前驱结点

(3)free(p)；//释放*p的空间

(1)、(2)这两个语句的执行顺序可以颠倒。

■)b)

图2-18双向循环链表上结点的删除

a)删除结点*p之前b)删除结点*p后

2.插入

在P所指结点的后面插入一个新结点*t,需要修改四个指针：

(1)t->prior-p；

(2)t->next=p->next；

(3)p->next->prior=t；

(4)p->next=t；

插入操作过程如图2-19所示，注意这些语句之间的顺序。

图2-19双向循环链表上结点的插入

a)插入前b)插入后

2.6顺序实现与连接实现的比较

查找：对于按位置查找运算，顺序表是随机存取，时间复杂度为0(1)。单链表需要对表元素进行扫描,

它时间为复杂度为0(n)。

定位：基本操作是比较，顺序表和单链表上的实现算法的时间复:杂度是相同的，均为0(n)

插入和删除：在顺序表和链表中，都需要进行定位。在顺序表中，其基本操作是元素的比较和结点的移

动，平均时间复杂度为0(n)。在单链表中，由于需要定位，基本操作是元素的比较，尽管不需要移动结

点，其平均时间复杂度仍然为0(n)。

单铢表的每个结点包括数据域与指针域，指针域需要占用额外空间。从整体考虑，顺序表要预分配存储

空间，如果预先分配得过大，将造成浪费，若分配得过小，又将发生上溢；单链表不需要预先分配空间，

只要内存空间没有耗尽，单链表中的结点个数就没有限制。

三、考核的知识点与考核要求

1.线性表概念

识记：线性表概念；线性表的基本特征。

领会：线性表表长；线性表初始化、求表长、读表元素、定位、插入、删除等基本运算的功能。

2.线性表的顺序存储结构一顺序表

识记：顺序表表示法、特点和类C语言描述。

领会：顺序表的容量；顺序表表长；插入、删除和定位运算实现的关键步骤。

简单应用：顺序表插入、删除和定位运算的实现算法。

综合应用：顺序表上的简单算法；顺序表实现算法的分析。

3.线性表的链式存储结构一单链表

识记：结点的结构；单链表的类C语言描述。领会：头指针；头结点；首结点；尾结点；空链表；单链

表插入、删除和定位运算的关键步骤。

简单应用：单链表插入、删除和定位等基本运算的实现算法。

综合应用：用单链表设计解决应用问题的算法。

4.循环链表和双向循环链表

识记：循环链表的结点结构；双向循环链表结点结构；循环链表和双向循环链表类C语言描述。

领会：循环链表插入和删除运算的关键步骤：双向循环链表插入和删除运算的关键步骤。

四、本章重点、难点

本章重点线性表概念和基本特征；线性表的基本运算;顺序表和单链表的组织方法和算法设计。

难点：单链表上的算法设计。

五、练习

【例题：单选题】若某线性表最常用的操作是在最后一个结点之后插入一个新结点或删除最后一个结点,

要使操作时间最少，应选择()存储结构。

A.无头结点的单向链表

B.带头结点的单向链表

C.带头结点的双循环链表

D.带头结点的单循环链表

I1正确答案』C

『答案解析』双循环链表的找直接前驱和直接后继结点的时间复杂度都是0(1)o参见教材P53。

【例题：单选题】在表长为n的顺序表上做删除运算，其平均时间复杂度为()。

A.0(1)

B.O(n)

C.0(nlog2n)

D.O（n2）

『正确答案』B

I1答案解析」在顺序表上做删除运算，需要后续结点向前移动一个位置以保证顺序表的连续。参见教材

P39。

【例题：单选题】在表长为n的顺序表上做插入运算，平均要移动的点数为（）。

A.n/4

B.n/3

C.n/2

D.n

r正确答案』c

『答案解析J如果在顺序表的尾部插入，则移动。个结点，如果在顺序表的头部插入，则移动n个结点。

参见教材P39。

【例题：单选题】若线性表最常用的操作是存取第i个元素及其前驱的值，那么最节省操作时间的存储

方式是（）。

A.单链表

B.双向循环链表

C.单循环链表

D.顺序表

『正确答案』D

I1答案解析」顺序表的特点是逻辑上相邻的在物理存储上也相邻。参见教材P40。

【例题：单选题】设顺序表有9个元素，则在第3个元素前插入一个元素所需移动元素的个数为（）。

A.5

B.6

C.7

D.9

I1正确答案』C

『答案解析』第三个元素前插入一个元素，即第3到9个元素都要移动，故答案是7。参见教材P39。

【例题：单选题】从一个长度为n的顺序表中删除第i个元素（l<=i<=n）时，需向前移动的元素个数

为（）。

A.n-i

B.n-i+1

C.n-i-1

D.i

I1正确答案JA

［答案解析』删除第i个元素，则后面n-i个元素都要前移。参见教材P39。

【例题：单选题】对于长度为n的顺序表执行删除操作，则其结点的移动次数（）。

A.最少为0,最多为n

B.最少为1,最多为n

C.最少为0,最多为n-1

D.最少为1,最多为联1

r正确答案JC

f答案解析』如果在顺序表尾部删除，移动次数为0,如果在顺序表头部删除，移动次数为n-屋参见

教材P40o

【例题：单选题】设单链表中指针p指向结点A,要删除A之后的结点（若存在），则修改指针的操作

为（）。

A.p->next=p->next->next

B.p=p->next

C.p=p->next—>next

D.p->next=p

『正确答案』A

I1答案解析』要删除A之后的结点，即将A的指针域指向A之后的结点的下一个结点。参见教材P47。

【例题：填空题】设r指向单链表的最后一个结点，要在最后一个结点之后插入S所指的结点，需执行

的语句序列是；r=s；r->next=NULLo

『正确答案』r->next=s

I1答案解析」在单链表中用尾插法插入一个结点，将尾结点的指针域指向待插结点，带插结点的指针域

指向NULL参见教材P46。

【例题：填空题】在单链表中，指针P所指的结点为最后一个结点的条件是（）。

『正确答案Jp>next==NULL

r答案解析』最后一个结点的指针域指向空。参见教材P42。

【例题：填空题】在带头结点的单链表L中，第一个数据元素结点的指针为（）。

『正确答案』L->next

f答案解析』本题考察对单链表结点结构的理解。参见教材P4L

【例题：填空题】在双向循环链表中，在指针P所指结点前插入指针s所指的结点，需执行下列语句：

s->next=p；s->prior=p->prior；p->prior=s；=s0

『正确答案』（s->prior）->next

I1答案解析』在双向循环链表中插入一个结点，需要做四件事情：待插结点后指针域指向P结点，P的

前指针域指向待插结点；带插结点的前指针域指向P的前驱结点；P的前驱结点的后指针域指向待插结

点。参见教材P53。

【例题；填空题】带头结点的双向循环链表L为空的条件是o