数据结构知识点归纳和习题解答

第1章绪论

一、数据结构的基本概念

1.基础概念和术语

(1)数据(Data)：数据是客观事物的符号表示。在计算机科学中指的是所有能输入到计算机中并被

计算机程序处理的符号的总称。

(2)数据元素(DataElement)：数据元素是数据的基本单位，在程序中通常作为一个整体来进行考虑

和处理。

(3)数据项(DataItem)：数据项是数据的不可分割的最小单位，数据项是对客观事物的某一方面的

数据描述。一个数据元素可由若干个数据项(DataItem)组成。

(4)数据对象(DataObject)：数据对象是性质相同的数据元素的集合，是数据的一个子集。如字符

集合C=rA7B：C,...)

(5)数据结构(DataStructure)：数据结构是指相互之间存在一定联系(关系)的数据元素的集合。

元素之间的相互联系(关系)称为逻辑结构。

2.数据结构的形式定义

数据结构的形式定义是一个二元组：

DataStructure=(D,S)

其中D是数据元素的有限集，S是D上关系的有限集。

数据元素之间的关系可以是元素之间本身代表的某种自然关系，也可以是为了处理问题方便而人为定义

的关系，这种自然或人为定义的关系称为数据元素之间的逻辑关系，相应的结构称为逻辑结构。

3.数据结构的组成

数据结构的三个组成部分：

(1)逻辑结构

数据元素之间的逻辑关系的描述。数据元素之间的逻辑结构有四种基本类型：

①集合：结构中的数据除了“同属于一个集合''外，没有其它关系。

②线性结构：结构中的数据元素之间存在一对一的关系。

③树形结构：结构中的数据元素之间存在一对多的关系。

④图形结构或网状结构：结构中的数据元素之间存在多对多的关系。

(2)存储结构

数据结构在计算机中的实际表达方式，它包括对数据元素的表示和对关系的表示。存储结构主要有：顺

序存储、链式存储、索引存储和散列存储。

①顺序存储结构：用数据元素在存储器中的相对位置来表示数据元素之间的逻辑结构。数据元素存放的

地址是连续的。其优点是可以实现随机存取，存储空间小；缺点是只能使用相邻的一整块存储单元，容

易产生碎片。

②链式存储结构：在每一个数据元素中增加一个存放另一个元素地址的指针，用该指针来表示数据元素

之间的逻辑结构。对数据元素存放的地址是否连续没有要求。其优点是能充分利用所有存储单元；缺点

是每个结点都需要额外的存储空间，且只能实现顺序存取。

③索引存储结构：在存储元素信息的同时.还建立附加的索引表。索引表中的每一项称为索引项，索引

项的一般形式是：（关键字.地址），关键字唯一标识一个元素，地址作为指向元素的指针。其优点是

检索速度快；缺点是需要额外的存储空间来存放索引表。

④散列（或哈希）存储结构：根据元素的关键字通过哈希函数直接计算出该元素的存储地址。其优点是

检索速度快，缺点是可能存在冲突，而解决冲突会增加时空开销。

（3）数据操作

对数据要进行的运算。

【例】下列有关数据存储结构的叙述中，正确的是（）。

A.顺序存储方式只能用于存储线性结构

B.顺序存储方式的优点是占用存储空间小，插入、删除等操作效率高

C.链表的每个结点中都恰好含有一个指针

D.Hash存储的基本思想是由关键词的值决定数据的存储地址

【答案】D

【解析】顺序存储方式除了用于存储线性结构外，还能存储数组或完全二叉树等非线

性结构，但在插入、删除操作时，由于要移动大量的数据，执行效率低。链表的形式有单链表、双链表

和多重链表，除了单链表外，其他链表中的结点需要两个以上的指针。

二、抽象数据类型

1.数据类型

数据类型（DataType）：数据类型是一个值的集合和定义在该集合上的一组操作的总称。

2.抽象数据类型

抽象数据类型（ADT）：是指一个数学模型以及定义在该数据模型上的一组操作。

ADT的定义仅是一组逻辑特性的描述，与其在计算机内的表示和实现无关。因此，不论ADT内部结构如

何变化，只要其数学特性不变，都不影响其外部使用。

ADT的形式化定义是三元组：ADT={D,S,P}。

其中：D是数据对象，S是D上的关系集，P是对D的基本操作集。

三、算法分析

1.算法

（1）概念

算法（Algorithm）：算法是对特定问题求解方法（步骤）的一种描述，是指令的有限序列，其中每一

条指令表示一个或多个操作。

（2）特性

算法由五个特性：

①有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。

②确定性：算法中每一条指令必须有确切的含义，不存在二义性，且算法只有一个入口和出口。

③可行性：算法描述的操作都可以通过已经实现的基本运算执行有限次来实现。

④输入：一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。

⑤输出：一个算法有一个或多个输出，这些输出同输入有着某些特定关系的量。

(3)评价标准

评价一个好的算法有以下几个标准：

①正确性：算法应满足具体问题的需求。

②可读性：算法应容易供人阅读和交流。可读性好的算法有助于对算法的理解和修改。

③健壮性：算法应具有容错处理。当输入非法或错误数据时，算法能适当地做出反应或进行处理。

④通用性：算法应具有一般性，处理结果对于一般数据集合都成立。

⑤效率和存储量需求：效率指的是算法执行的时间；存储量需求指的是执行过程中所需要的最大存储空

间。

2.效率的度量

(1)时间复杂度

算法中的基本操作重复执行的次数是问题规模n的某个函数，其时间度量记做T(n)=O(f(n))(其

中“O”是指T(n)的数量级)，称作算法的渐进时间复杂度，简称时间复杂度。

算法的时间复杂度一般用最深层循环内的语句中的原操作的执行频度(重复执行的次数)来表示。

常用的时间复杂度的关系：

0(1)<0(log2n)<0(n)<0(nlog2n)<0(n2)<O(n3)

指数时间复杂度关系为：O(2n)<O(n!)<O(nn)

有的情况下，算法中基本操作重复执行的次数会随问题的输入数据集的不同而不同

(2)空间复杂度

空间复杂度指的是算法编写成程序后，在计算机中运行时所需存储空间大小的度量。记做：S(n)

=0(f(n)),其中n为问题的规模。

空间复杂度一般包括三个方面：

①指令常数变量所占用的存储空间。

②输入数据所占用的存储空间。

③辅助存储空间。

【例】有以下算法，其时间复杂度为()。

voidfun(intn)

(

mtp=1,d=n,f=n；

while(d>0)

(

if(d%2==i)

p=p*f；

f=f*f:d=d2;

)

}

A.O(1)

B.O(log2n)

C.0(n)

D.(nlog2n)

【答案】Bo

【解析】基本运算语句为(1=皿2(或,设其执行时间为T(n),则有：

d=ii2：安士1,2T：0：＜n

则T(n)Slog2n=0(log2n)。

注意算法中while循环的if条件中包含的尸p*f语句可以不考虑.因为它执行的次数不超过d=d/2语句的执行

次数。

练习题一、单项选择题

1.下列程常段的时间复杂度是()。［2014年联考真题］

count=0:

fork*2)

for

count—;

A.0(log2n)

B.O(n)

C.O(nlog2n)

D.O(n2)

【答案】C

【解析】外部循环的退出条件是k>n,而对于k,每次循环都执行1<=1<*2,所以循环次数为log,n；内部循环

的退出条件是j>n,对于j,每次循环都执行)可+1,所以每次循环次数为n次。所以此程序段的时间复杂度

为O(nlog2n),即选C。

2.求整数n(n>0)阶乘的算法如下，其时间复杂度是()。［2012年联考真题］

intfact(intn)

(if(nV=1)return11

returnn•fact(n-1)»

A.O(log2n)

B.O(n)

C.O(nlog2n)

D.O(n2)

【答案】B

【解析】设fact(n)的运行时间函数是T(n).

intfact<intn){

if(nV=l)return11〃语句

returnn»fact(n-1)>//语句

该函数中语句①的运行时间是0(1),语句②的运行时间是T(n-1)+O(1),其中O(1)为乘法运算

的时间。

因此，当旺1时，T(n)-0(1)；当n>l时，T(n)=T(n-1)+0(1)。则，T(n)=0(1)+T(n-1)

=2x0(1)+T(n-2)=(n-1)xQ(1)+T(1)=nxO(1)

=0(n)

即fact(n)的时间复杂度为O(n)。

3.设n是描述问题规模的非负整数，下面程序片段的时间复杂度是()。［2011年联考真题］

while(x<n.2)

x=2Xx；

A.O(log2n)

B.O(n)

C.O(nlog2n)

D.O(n2)

【答案】A

【解析】其中，以基本的原操作重复执行的次数作为算法的时间度量。题目中的基本运算是语句

(n)

x=2xx,设其执行时间为T(n),则有2T<n/2即T(n)<log2(n/2)=O(log2n)«

4.算法的计算量的大小称为计算的()。［北京邮电大学2000研］

A.效率

B.复杂性

C.现实性

D.难度

【答案】B

【解析】算法复杂度通常分为时间复杂度和空间复杂度，算法的计算量的大小可以用时间复杂度衡量,

即可以称为计算的复杂度。

5.下列说法错误的是()。［南京理工大学2000研］

(1)算法原地工作的含义是指不需要任何额外的辅助空间

(2)在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2D的算法

(3)所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界

(4)同一个算法，实现语言的级别越高，执行效率就越低

A.(1)

B.(1),(2)

C.(1),(4)

D.(3)

【答案】A

【解析】算法原地工作的含义不是指不需要任何额外的辅助,而是算法所需要的辅助空间不随着问题的

规模而变化，是一个确定的值。

6.以下属于逻辑结构的是()。

A.顺序表

B.哈希表

C.有序表

D.单链表

【答案】C

【解析】数据结构分别为逻辑结构、存储结构（物理结构）和数据的运算。数据的逻辑结构是对数据之

间关系的描述，与数据元素本身的形式、内容、相对位置、所含结点个数都无关。顺序表、哈希表、单

链表都涉及到数据的存储结构，有序表是指表中数据有序，与逻辑结构无关。

7.在数据结构中，从逻辑上可以将其分为（）。［中南大学2005研］

A.动态结构和静态结构

B.紧凑结构和非紧凑结构

C.内部结构和外部结构

D.线性结构和非线性结构

【答案】D

【解析】数据结构从逻辑上可以分为线性结构和非线性结构。常见的线性结构为栈和队列，非线性结构

为树形结构和网状结构。

8.一个算法应该是（）。

A.程序

B.问题求解步骤的描述

C.要满足五个基本要求

D.A和C

【答案】B

【解析】程序不一定满足有穷性，如死循环，操作系统等，而算法必须有穷。算法代表了对问题求解步

骤的描述，而程序是算法在计算机上的特定实现。

9.数据结构中数据元素之间的逻辑关系被称为（）。［北京理工大学2005研］

A.数据的存储结构

B.数据的基本操作

C.程序的算法

D.数据的逻辑结构

【答案】D

10.下面程序段中，执行S语句的次数为（）。

for（inti=l；i<=n；D

for（mtj«lj<=i;jj）

S;

A.n2

B.n2/2C.n

（n+1）

D.n(n+1)/2

【答案】D

【解析】i的变化范围是从1到n,对于每个已确定值的i,j的变化范围是从1到i,相当于求一个公差为1的

等差数列1,2，…，n的前n项和，即：n(n+1)②

II.可以用()定义一个完整的数据结构。［中山大学2004研］

A.数据元素

B.数据对象

C.数据关系

D抽象数据类型

【答案】D

【解析】抽象数据类型可以定义一个完整的数据结构。包括数据元素，数据元素之间的关系，以及可以

进行的操作。

12.以下算法的时间复杂度()。

\bidfirn(intn)

(

inti-1;

While(ion)

}

A.0(n)

B.O(n2)

C.O(nlog2n)

D.O(logjn)

【答案】D

【解析】基本运算为i=i*2,设其执行时间为T(n),则2,⑴<=n,即T(n)<=log2n=D.O(log2n)

二、综合题

1,已知一个整数序列,其中OVQ,,若存a,”7且,

则称X为A的主元素。例如人(。-5.5),则称5为主元素；又如.—》；*,一则A中没有主元素。假设

A中的n个元素保存在一个一维数组中，请设计一个尽可能高效的算法，找出A的主元素。若存在主元

素，则输出该元素；否则输出-1。要求：

(1)给出算法的基本设计思想。

(2)根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。

(3)说明你所设计算法的时间复杂度和空间复杂度。［2013年联考真题〕

解：(1)算法的策略是从前向后扫描数组元素,标记出一个可能成为主元素的元素Num。然后重新计

数，确认Num是否是主元素。

算法可分为以下两步：

①选取候选的主元素；依次扫描所给数组中的每个整数，将第一个遇到的整数Num保存到c中，记录

Num的出现次数为1；若遇到的下一个整数仍等于Num,则计数加1否则计数减1；当计数减到0时，将遇

到的下一个整数保存到C中，计数重新记为1,开始新一轮计数，即从当前位置开始重复上述过程，直到

扫描完全部数组元素。

②判断c中元素是否是真正的主元素，再次扫描该数组，统计c中元素出现的次数，若大于n/2,则为主

元素；否则，序列中不存在主元素。

(2)算法实现如下：

mtM^ority(intA[],iiirn){

mti,c,count=l;c用来保存候选主元素，count用来计数

oA(0];设置A[。]为候选主元素

for>{查找候选壬元素

jfc)

count—;为A中的候选主元素计数

eles{

if(countX))处理不是候选壬元素的情况

count-;

elsM更换候选主元素

count=l;

)

)

)

if(count>0)

for(i-count-0,i<n,i­){统计候选王元素的实际出现次数

if(Ad)

count**;

)

if(counun2)确认候选王元素

returnc;

else

return1;不存在主元素

)

(3)时间复杂度为0(n)，空间复杂度为0(1).

2阅读下面的程序，指出过程pp完成的功能及结果数据结构的名称.并估计算法的时间复杂度

0(?),说明理由。设单链表长度为n。

C语言

Typedefcharelemtype；

Typedefstructnode

Elemtypekey：

Strcutnode*nextx

}node.•*link»

1inkla：

voidpp《linkp)；

if(p)

pp(p->next)sp-next=lanext：

la->next=p$la=p：

}returnj

main()

1inkqj

建立用la指出的带头结点的单链长:

q=lanext；lanext=la；pp<q)；

输出用la指出的总式结构的数据儿索；

return1：

答：(1)程序的功能是将单链表逆置;

(2)结果数据结构为存入一个带头结点、用尾指针表示的单向循环链表；

(3)算法时间复杂度为O(n)o理由：因为此程序通过递归方法达到单链表的逆置，递归深度与表的

节点数相当，回退时处理插入，每层复杂度为0(1),故总的复杂度为O(n)。

第2章线性表

一、线性表的定义和操作

1.线性表的定义

线性表(LinearList)：是由n(nSO)个数据元素(结点)a］，a2,…an组成的有限序列。该序列中的

所有结点具有相同的数据类型。其中数据元素的个数n称为线性表的长度。

当n=O时，称为空表。

当n>0时，将非空的线性表记作：L=(aPa2,...an),其中a1称为线性表的第一个(首)结点，an称为

线性表的最后一个(尾)结点。a,,a2,…a^i都是由(2WiWn)的前驱，其中a”是为的直接前驱：ai+P

aj+2，…an都是aj(1=i=n-l)的后继，其中西+L是aj的直接后继。

2.线性表的基本操作

一个数据结构的基本操作是指其最核心、最基本的操作。其它较为复杂的操作可以通过调用基本操作来

实现。线性表的主要操作如下：

InitList(&L)初始化线性表：构造一个空的线性表L。

DestroyList(&L)销毁线性表：释放线性表L占用的内存空间。

LislEmpty(L)判断线性表是否为空表：若L是空表，则返回真，否则返回假。

ListLength(L)求线性表长度：返回L中元素的个数。

DispList(L)输出线性表：当线性表L不为空时，顺序显示L的各结点的值域。

GetElem(L,i,&e)求线性表L中指定位置的某个元素：用e返回L中第i(1WiWListLength(L))个

元素的值。

LocateElem(L,e)定位查找：返回L中第1个值域与e相等的为序。不存在则返回0。

Listinsert(&L,i,e)插入数据元素：在L的第i(1SiSListLength(L)+1)个元素之前插入新的元素

e,L的长度增加1。

ListDelete(&L,i,&e)删除数据元素：删除L的第i(1二iWListLength(L))个元素，并用e返回其

值，L的长度减少1。

二、线性表的实现

1.顺序存储

(1)线性表的顺序存储结构

线性表的顺序存储结构就是把线性表的结点按逻辑顺序依次存放在一块地址连续的存储单元里。用这种

方法存储的线性表简称顺序表。

顺序存储的线性表的特点：

①线性表的逻辑顺序与物理顺序一致。

②数据元素之间的关系是以元素在计算机内“物理位置相邻''来体现。

假设线性表存储的起始位置是LOC(A),元素类型为ElemType,则每个元素所占用存储空间的大小

(即字节数)为sizeof(ElemType),整个线性表所占用存储空间的大小为n*sizeof(ElemType)，其

中，n表示线性表的长度。线性表的存储如图1-1所示。

下标位置线性表存储空间存储地址

0LOC(A)

LOC(A)+sizeofi(ElemType)

LOC(A)+<i-l)*sizeof(EfemType)

LOC(A)+(n-l)*sizeof(ElemType)

MaxSize-1LOC(A)+(MaxSize-1)*sizeof(IkmType)

图1-1线性表的顺序存储结构

为在逻辑序列中的位置称为逻辑位序，在顺序表中的位置称为物理位序。

在定义一个线性表的顺序存储类型时，需要定义一个数组来存储线性表中的所有元素和定义一个整型变

量来存储线性表的长度。

假定数组用data[MaxSize]表示，长度整型变量用length表示，并采用结构体类型表示，则元素类型为通用

类型标识符:ElemType的线性表的顺序存储类型可描述如下：

sdefineOK1

^defineERROR-1

defineMAX_SIZE100

n-pedefmtStatus;

typedefstructsqlist

(

ElemlXpeElem_anay(\IAX_SIZEJ;

intlength;

}SqList;

其中，Elem_array成员存放元素，length成员存放线性表的实际长度。

(2)顺序表的基本操作

由于顺序表的操作比较简单，在这里只给出建立、插入、删除和按值查找的操作的算法。

①建立顺序表

其方法是将给定的含有n个元素数组的每个元素依次放入到顺序表中，并将n赋给顺序表的长度成员。算

法如下：

voidCreateList(SqList*<S:L,ElemTypea[],mtn)

*建立顺序表.

(

inti;

L-(SqList•)malloc(sizeof(SqList));为顺序表分配存储空间

for—)

L->length=n;

}

②插入操作

该运算在顺序表L的第i个位置(iWiWListLength(L)+1)上插入新的元素e。

思路：如果i值不正确，则显示相应错误信息；否则将顺序表原来第i个元素及其后面元素均后移一个位

置，腾出一个空位置插入新元素，顺序表长度增1。

StatusInsert_SqList(Sqlist*L,inti,Eieml^pee)

(

inrj;

if(i<li>L->length)

returnERROR;

if(L->length>-MAX_SIZE)

(

printf(“线性表溢出!n”)；

returnERROR;

)

for(j=L->length-1:j>=i:-j)

L->Eiem_array[j-l]=L->Elem_array[j]：

*i位置以后的所有结点后移*

L->Elem_ana>li-1]-e,

*在1位*插入结点*

L->length—;

returnOK,

在线性表L中的第i个位置插入新结点，其时间主要耗费在表中结点的移动操作上，因此，可用结点的移

动来估计算法的时间复杂度。

设在线性表L中的第i个位置插入结点的概率为R,不失一般性，设各个位置插入是等概率，则Pi=l/

(n+1),而插入时移动结点的次数为n-i+10

总的平均移动次数：

即在顺序表上做插入运算，平均要移动表上一半结点。当表长n较大时，算法的效率相当低。因此算法

的平均时间复杂度为O(n)。

③删除操作

删除顺序表L中的第i(l<i<ListLength(L))个元素。

思路：如果i值不正确，则显示相应错误信息；否则将线性表第i个元素及其后面元素均向前移动一个位

置，这样覆盖了原来的第i个元素，达到删除该元素的目的，最后顺序表长度减1。

ElemTypeDel«e_SqList(Sqlist*L,inti)

(

mtk;

Elemiypex;

if(L->length«-0)

(

prrntf(“线性表L为空!n”),

returnERROR;

}

elseif(i<l；|i>L->length)

(

pnntf(“要删除的数据元素不存在!n”)；

returnERROR;

x=L->Elem_array-[i-l]:*保存结点的值*

for(k-i;k<L->length;k**)

L->E!em_array[k-1卜L->Elem_anay[k];

*।位重以后的所有结点前看*

L->length—;

return(x);

删除线性表L中的第i个元素，其时间主要耗费在表中结点的移动操作上，因此，可用结点的移动来估计

算法的时间复杂度。

设在线性表L中删除第i个元素的概率为B，不失一般性，设删除各个位置是等概率，则Pj=l/n,而删除

时移动结点的次数为n-i。

则总的平均移动次数：

v-1,1、1>：-1

Er=2P.5-1n)=_-(>3-1)=―；­=

>1>17~~

即在顺序表上做删除运算，平均要移动表上一半结点。当表长n较大时，算法的效率相当低。因此算法

的平均时间复杂度为O(n)。

④按值查找

该运算顺序查找第1个值与e相等的元素的位序。若这样的元素不存在，则返回值为0。

intLocateElem(SqList*L,Elemlypee)

(

inti-0;

while(i<L->length&&L->data[i]!-e)

if

if(i>-L->length)

return0:

else

returni-1;

}

假设Pi(Pi=l/n)是查找元素在第i个位置上的概率，则在长度为n的线性表中查找值为e的元素所需要比

较的平均次数为：

因此，线性表按值查找算法的平均时间复杂度为O(n)。

2.链式存储

(1)线性表的链式存储结构

线性表的链式存储结构是指用一组任意的存储单元来存储线性表中的数据元素。用这种方法存储的线性

表简称线性链表。

在链式存储中，每个存储结点不仅包含所存元素本身的信息(称之为数据域)，而且还需包含元素之间

逻辑关系的信息，比如前驱结点包含后继结点的地址信息，这称为指针域，这样可以通过前驱结点的指

针域很方便地找到后继结点的位置，提高数据查找速度。

一般地，每个结点都有一个或多个这样的指针域。若一个结点中的某个指针域不需要任何结点，则仅它

的值为空，用常量NULL表示。

为操作方便，总是在链表的第一个结点之前附设一个头结点(头指针)head指向第一个结点。头结点的

数据域可以不存储任何信息(或链表长度等信息)。

(2)单链表

由于顺序表中的每个元素至多只有一个前驱元素和一个后继元素，即数据元素之间是一对一的逻辑关

系，所以当进行链式存储时，一种最简单也最常用的方法是：

在每个结点中除包含有数据域外，只设置一个指针域，用以指向其后继结点，这样构成的链接表称为线

性单向链接表，简称单链表。带头结点的单链表如图1-2所示。

头结点开始结点终端结点

headT|a/-Ha?|->|ar|A|

图1-2带头结点的单链表单

链表中结点类型描述为：

typedefstructLnode

(

El«nT\pedata.啜据域，保存结点的值*

structLnode*next;*指针域*

}LNode;逐点的类型*/

单链表中基本操作为：

①建立单链表

假设线性表中结点的数据类型是整型，以32767作为结束标志。假设我们通过一个含有n个数据的数组来

建立单链表。建立单链表的常用方法有如下两种：

a.头插法建表

从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插

入到当前链表的表头上，直到读入结束标志为止。即每次插入的结点都作为链表的第一个结点。

LNode*creaie_LinkList(void)

*头插入法©建单道表,捱表的担点head作为返回值*

(

intdata;

LNode*head,*p;

head-(LNode*)malloc(sizeof(INode));

head->next-NULL;*创建i鳏的表头结点head*

while(1)

(

scanf("*•d",&dau).

if(data-32767)

break;

p-(LNode*)malloc(sizeof(LNode));

p->data-data;*数据i/值*

p->next-head->next;

head->next-p;

广构施，新创建幅点总是作为第一个结点*

)

return(head);

}

b.尾插法建表

头插入法建立链表虽然算法简单，但生成的链表中结点的次序和输入的顺序相反。若希望二者次序一

致，可采用尾插法建表。该方法是将新结点插入到当前链表的表尾，使其成为当前链表的尾结点。

LNode*create_L4nkList(void)

*尾插入法制0单涟表，道表的头结点head作为返回值*

(

intdata;

LNode*head,*p,*q;

head-p-(INode*)malloc(sizeof(LNode));

p->next-NULL;•创建单道表的表头结点head•

while(1)

{

scanf(,&data);

if(data=32767)

break,

q・(INode")malloc(sizeof(LNode〉)；

q->data=data;*数据域赋值*

q->next=p->next:

p->next=qT

p-q；

*构涟，新创建的结点总是作为最后一个结点*

}

return(head);

)

无论是哪种插入方法，如果要插入建立的单线性链表的结点是n个，算法的时间复杂度均为O(n)。

②单链表查找

a.按序号查找

即取单链表中的第i个元素。

对于单链表，不能像顺序表中那样直接按序号i访问结点，而只能从链表的头结点出发，沿链域next逐个

结点往下搜索，直到搜索到第i个结点为止。因此，链表不是随机存取结构。

设单链表的长度为n,要查找表中第i个结点，仅当IWiWn时，i的值是合法的。

Elemly-peGet_Elan(LNode*L,inri)

(

intj;

LNode*p;

p-L->next;

jT；产使P指向第一个结点.

while(p!-NULL&&j<i)

(

p-p->next;

)•移朝旨针p.j计数*

if(j!-i)

return(-32768);

else

return(p->data);

*p为NULL表示i太大;j>i表示i为0.

)

按序号查找单链表的时间复杂度为O(n)。

b.按值查找

按值查找是在链表中，查找是否有结点值等于给定值key的结点。若有，则返回首次找到的值为key的结

点的存储位置；否则返回NULL。查找时从开始结点出发，沿链表逐个将结点的值和给定值key作比较。

LNode*Locate_Node(LNode,L:mtkey)

•在以L为诵点的单道表中查找值为key•的第一个结点・

(

LNode*p=L->next;

while(p!«NULL±&p->data*-key)

p-p->nexi,

if(p-xlau-kejO

returnp;

else

(

pnntf("所要查找储点不存在!!；

return(NULL).

}

)

算法的执行与形参key有关，平均时间复杂度为O(n)。

③单链表的插入

插入运算是将值为e的新结点插入到表的第i个结点的位置上，即插入到ar与比之间。因此，必须首先找

到为」所在的结点p,然后生成一个数据域为e的新结点q,q结点作为p的直接后继结点。

voidInsert_LNode(LNode*L,mti,ElemI>pee)

*在以1为头结点的单薄表的第1个位置插入值为e储点*

(

intj-O;

LNode*p,*q;

p»L->next;

while(p!-MULL&&j<i-l)

(

p-p->next;

j**；

)

if(j!»i-l)

prmtfLi太大或访0!!n”；

else

(

q-(LNode*)malloc(sizeof(LNode));

q->data«e;

q->next««p->next;

p->next=q;

)

}

设链表的长度为n,合法的插入位置是IWiWn。算法的时间主要耗费移动指针p上，故时间复杂度亦为

0(n)。

④单链表的删除

a.按序号删除

删除单链表中的第i个结点。

为了删除第i个结点为，必须找到结点的存储地址。该存储地址是在其直接前趋结点牛」的next域中，因

此，必须首先找到ar的存储位置p,然后令p->next指向西的直接后继结点，即把可从链上摘下。最后释放

结点研的空间，将其归还给“存储池

设单链表长度为n,则删去第i个结点仅当lWi=n时是合法的。则当i=n+l时，虽然被删结点不存在，但

其前趋结点却存在，是终端结点。故判断条件之一是p->next!=NULL。

voidDelete_LinkList(LNodeeL,inti)

*删除为嵋点的单道表中的第i个结点*

(

intj-1;

LNode*p,*q;

P=L；

q=L->next;

while(p->next!=NVLL&4fcj<i)

(

p-q；

q*q->next;

)

if(j!-i)

printf(一太大或i为0!!W);

else

{

p->next=q->nexti

free(q);

}

)

b,按值删除

删除单链表中值为key的第一个结点。

与按值查找相类似，首先要查找值为key的结点是否存在？若存在，则删除；否则返回NULL。

voidDelete_LinkList(LNode*L,mtkey)

*删除以工为脂点的单绘表中值为key的第一个结点*

(

LNode*p»L,*q=L->next;

while(q!»NULL&&q->dara!=key)

(

L；

q-q->next;

)

if(q->data—ke>>)

(

p->next»q->next;

free<q);

}

else

prmtf("所要JU除留给点不存在!！n")；

}

单链表的删除结点时间都耗费在查找结点的操作上。时间复杂度为O(n)。

⑤求表长

返回单链表L中数据结点的个数。

intListLength(LmkList*L)

(

LmkList*p=L;inti=0;

while(p->next?-NULL)

(

i**；

p«p->nect;

}

return(i);

}

时间复杂度为0(n)。单链表的长度不包括头结点。

【例】已知指针P所指结点不是尾结点，若在*P之后插入结点*S,则应执行下列哪一个操作

()O

A.S->NEXT=P；P->NEXT=S；

B.S->NEXT=P->NEXT；P->NEXT=S；

C.S->NEXT=P->NEXT；P=S；

D.P->NEXT=S；S->NEXT=P；

【答案】B

【解析】插入结点S是的情况如下图所示：在断开P—>next之前必须先将S—>next指向P的直接后继，否则

由于是单链表结构，会无法找到P的后继结点，然后才能将P的直接后继修改为S。

(3)循环链表

循环链表就是一种头尾相接的链表。其特点是最后一个结点的指针域指向链表的头结点，整个链表的指

针域链接成一个环。图1-3是带头结点的单循环链表的示意图。

headhead____________

等空表

图L3单循环链表

从循环链表的任意一个结点出发都可以找到链表中的其它结点，使得表处理更加方便灵活。

对于单循环链表，基本操作都跟单链表差不多，仅仅需要在单线性链表操作算法基础上做以下修改：

①判断是否为空链表条件改为：head->next==head;

②判断是否为表尾结点条件改为：p->next==head«

(4)双向链表

双向链表指的是构成链表的每个结点中设立两个指针域：一个指向其直接前趋的指针域prior,一个指向

其直接后继的指针域next。这样形成的链表中有两个方向不同的链，故称为双向链表。其结点形式如图

1一4所示。和单链表类似，双向链表一般增加头指针也能使双链表上的某些运算变得方便。带头结点的

双向链表如图1-5所示。

|prior|data|next|

图1-4双向链表结点形式

hea<Jhead

空双向能妻非电双向链表

图1-5带头结点的双向链表

双链表中结点的类型定义描述如下：

typedefstructDuinode

(

ElemT>-pedata;

stmctDuinodeapnor「next:

JDulNode;

双向链表结构具有对称性，设p指向双向链表中的某一结点，则其对称性可用下式描述：

(p->prior)->next=p=(p->next)->prior;

点p的存储位置存放在其直接前趋结点p->prior的直接后继指针域中，同时也存放在其直接后继结点p-

>next的直接前趋指针域中。

双向链表的操作

①双向链表的插入

将值为e的结点插入双向链表中。插入前后链表的变化如图1-6所示。

,上~一r，，，，

|a,-=naT"lI加k

息

图1-6双向链表的插入

a.插入时仅仅指出直接前驱结点，钩链时必须注意先后次序是：“先右后左部分语句组如下：

S=(DulNode*)malloc(sizeof(DulNode));

S->data=e;

S->next-p->next;

p->next->pnor-S,

p->next»S;

Aprimp;尸翎联渊陶重要*

b.插入时同时指出直接前驱结点p和直接后继结点q,钩链时无须注意先后次序。部分语句组如下：

S=(DulNode•)malloc(sizeof(DulNode));

S->dat^e;

p->next»S;

S->next-q;

S->prior-p,

q->pnor3gS;

②双向链表的结点删除

设要删除的结点为p,删除时可以不引入新的辅助指针变量，可以直接先断链，再释放结点。部分语句

组如下：

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

p->next->prior-p->pnor;

笈ee(p)；

与单链表的插入和删除操作不同的是，在双向链表中插入和删除必须同时修改两个方向上的指针域的指

向。

(5)静态链表

静态链表借用一维数组来描述线性链表。数组中的一个分量表示一个结点，同时使用游标(指示器cur

即为伪指针)代替指针以指示结点在数组中的相对位置。数组中的第0个分量可以看成头结点，其指针

域指示静态链表的第一个结点。

这种存储结构仍然需要预先分配一个较大空间，但是在进行线性表的插入和删除操作时不需要移动元

素，仅需要修改“指针”，因此仍然具有链式存储结构的主要优点。

【例】如果对含有n(n>l)个元素的线性表的运算只有4种：删除第一个元素，删除最后一个元素，在

第一个元素前面插入新元素，在最后一个元素的后面插入新元素，则最好使用()。

A.只有尾结点指针没有头结点指针的循环单链表

B.只有尾结点指针没有头结点指针的非循环单链表

C.只有头结点指针没有尾结点指针的循环单链表

D.既有头结点指针也有尾结点指针的循环单链表

【答案】C

【解析】对于A项的链表，删除最后一个结点P时，需要找到P的前一个结点，其时间复杂度为O(n)；

对于B项的链表，删除第一个结点的P时，需找到头结点，这里没给出头结点指针，故无法实现这种操

作。

对于C项的链表，这4种操作的时间复杂度都为0(1)。

对于D项的链表，删除最后一个结点P时，需要找到P的前一个结点，其时间复杂度为O(n)。

3.线性表的应用

(1)一元多项式的表示

2n

一元多项式p(x)=p()+p|X+p2x+...+pnx,由n+1个系数唯一确定。则在计算机中可用线性表

(P0，Pl，P2,...,Pn)表示。既然是线性表，就可以用顺序表和链表来实现。两种不同实现方式的元素类型

定义如下：

①顺序存储表示的类型

typcdefstruct

(

floatcoef;♦系数部分•

mtexpo;嘴数部分・

}Elemiype;

②链式存储表示的类型

typedefstructploy

(

floatcoef,•系数部分"

intexpo;•指数部分•

structployenext,

}Ploy;

(2)一元多项式相加

①顺序存储的一元多项式相加

线性表的定义

typedefstruct

(

Elemiypea[MAX_SIZE];

intlength;

}Sqlist;

用顺序表表示则相加非常简单。访问第5项可直接访问：L.a[4].coef,L.a[4].expn

②链式存储表示的一元多项式相加

当采用链式存储表示时，根据结点类型定义，凡是系数为0的项不在链表中出现，从而可以大大减少链

表的长度。

一元多项式相加的实质是：指数不同时是链表的合并；指数相同时系数相加，和为0,去掉结点，和不

为0,修改结点的系数域。

现在提供一种算法，在原来两个多项式链表的基础上进行相加，相加后原来两个多项式链表就不再存

在。当然再要对原来两个多项式进行其它操作就不允许了。

Ploy*add_J)toy(ploy*La.ploy*Lb)

*将以La,Lb为头指针裘示的一元多项式相腑

(

ploy*Le.*pc,,p%*pb,*ptr.

finatx;

Lo=po=La;

pa-La->next:

pLb->next;

while(pal-NULL&&pb;-NULL)

(

if(pa->^pn<pb->expn)

(

pc->next=pa;

po=pa;

pa-pa->next;

}

，“将pa所指的结点合并，pa指向下一个结点火

if(pa->cxpn>pb->expn)

(

pc->n这可b;

pv=pb;

ppb->nexl;

else

(

x-pa->coef+pb->coef:

if(abs(x)<-1.0e-6)

*如果系韵和为0.删除两个结点*

{

PtP=pa-

pa"Ja->nexi:

free(ptr):p

扛可)b;

pbaapb->next;

free(ptr):

)

else*如果系防和不为O,修改其中一个结点的系数域，删除另一个芜点*

(

pc->next=pa;

pa->coef=x;

pc=pa;

pa41a->next:

ptr=pb:

pb=pl>->next;

fr(pb):

}*endofwhile*

if(pa=NULL)

pc->next=pb;

else

pc->nexl叩a:

return(Le)；

J

练习题一、单项选择题

1.已知两个长度分别为m和n的升序链表，若将它们合并为一个长度为m+n的降序链表，则最坏情况下

的时间复杂度是()。［2013年联考真题］

A.O(n)B.O

(m*n)C.O(min

(m,n))D.O

(max(m,n))

【答案】D

【解析】m