书名：数据结构：C语言（微课版）pdf/doc/txt格式电子书下载

推荐语：一本真正的数据结构立体化教材，重点难点全方位视频讲解

作者：王海艳编

出版社：人民邮电出版社

出版时间：2017-07-01

书籍编号：30489213

ISBN：9787115458254

正文语种：中文

字数：179393

版次：1

所属分类：教材教辅-大学

版权信息

书名：数据结构：C语言（微课版）

作者：王海艳

ISBN：9787115458254

版权所有 · 侵权必究

内容提要

本书将现代信息技术与教学紧密融合，突破了传统教学模式，通过微课的形式全面阐述数据结构课程中的重点、难点，涵盖线性表、树、图等内容，形成一套完整的包含知识点、习题、实验、微课视频等的立体化教学资源，帮助学生进行自主式和研究性学习，同时为教师的传统课堂教学提供辅助。

本书系统地讲解了数据结构的相关知识。全书共有10章，系统地讲述了线性表、堆栈、队列、数组、树、查找、图、排序等内容，还安排了习题和实验。本书重视算法及其实践性，书中算法都有完整的C语言程序，程序代码注释详细。为了让读者能够及时地检验学习效果、把握学习进度，每章都附有丰富的习题。

本书可作为计算机、电子信息、管理信息系统、电子商务、教育技术等相关专业数据结构课程的本科教材，也可以作为计算机软件及应用的工程技术人员参考资料。

前言

“数据结构”是设计系统软件及大型应用软件的重要基础，对于构建高效的算法起着决定性的作用。“数据结构”课程作为计算机专业的重要核心课程，对培养学生的计算思维和系统分析与设计、算法设计与分析、程序设计与实现等学科基本能力起着至关重要的作用。本书将现代信息技术与传统教育教学方法紧密融合，通过微课的形式阐述数据结构课程中的重点、难点，突破传统教学模式的束缚，建立立体化的教学资源，形成新的知识传授模式。本书在促进教学理念更新，推动高等教育教学方式方法和学习方式的创新方面做了重要尝试。本书旨在使教学与学习过程朝着教学方式混合化、教学资源开放化、学生学习个性化、学习过程社会化方向转变，对于帮助学生进行自主式和研究性学习具有重要意义。

本书以计算机类和信息类学科人才为培养目标，以教学认知规律为编写依据，以“理论、实践、理论与实践相结合”为编写原则。全书共分10章，第1章介绍数据结构课程的研究内容和关键问题；第2章至第4章介绍线性表、堆栈和队列、数组和字符串等线性结构的基本概念及常用算法；第5章至第9章介绍非线性结构的树、散列表、图等数据结构以及相关算法和应用；第10章主要讨论排序的各种实现方法及其综合分析比较。附录部分为上机实验内容，指导学生按软件工程的方法设计与编写程序。

本书条理清楚，内容翔实，用词达意，深入浅出，并且配有大量的实例和图示。本书把数据结构的基本概念和常用算法的设计、应用与程序紧密结合，书中算法都有完整的C语言程序，程序代码注释详细。本书提供了丰富的习题，并在各章中对重点难点内容配备了微课视频，使读者更具体、更深刻地理解各种常用的数据结构及它们与算法之间的关系，以达到学以致用的目的。

本书的参考学时为48~64学时，以56学时为例给出各章的参考教学课时，课时分配如下表。

本书可作为计算机类专业或信息类相关专业的本科教材，也可以作为报考相关专业硕士研究生入学考试的复习用书，还可以供从事计算机类工程与应用工作的科技工作者学习参考。

本书由王海艳主编，并编写第1、6章，骆健编写第2、9章，朱洁编写第4、10章，邹志强编写第7、8章，戴华编写第3章，徐鹤编写第5章，王甦编写附录综合实验。此外，本书的编写得到南京邮电大学教务处及计算机学院的支持和帮助，在此对学校的支持和同事特别是《数据结构》课程组的各位前辈、各位课程组成员的鼓励表示衷心的感谢。

由于编者水平和经验有限，书中难免有欠妥和错误之处，恳请读者批评指正。

编者

2017年7月

第1章　绪论

本章首先介绍数据结构的基本概念及相关术语；然后讨论数据结构、数据类型和抽象数据类型之间的关系，介绍数据结构描述方法；最后阐述算法分析的方法。

1.1　数据结构起源

“数据结构”的概念起源于1968年美国计算机科学家唐纳德·克努特（Donald Ervin Knuth）教授所著的《计算机程序设计艺术》（The Art of Computer Programming），如图1.1所示。在该书的第一卷《基本算法》中，他开创了数据结构的最初体系，较系统地阐述了数据的逻辑结构和存储结构及其操作。

图1.1　Donald Ervin Knuth及其著作《The Art of Computer Programming》

在计算机科学中，研究数据结构对设计出高性能的算法和高性能软件至关重要。“数据结构”课程不仅是程序设计的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他应用程序的重要基础。

1.2　基本概念和术语

1.2.1　基本概念

1．数据

数据是可被计算机识别并加工处理的对象。数据不仅包括整型、实型等数值数据，还包括声音、图像、视频等非数值数据。例如，MP3格式的文件是常见的音频声音数据，BMP格式的文件是典型的图像数据，RMVB格式的文件是视频数据。

2．数据元素

数据元素是由数据组成的具有一定意义的基本单位，在计算机中通常作为一个整体来处理。有些情况下，数据元素也称为元素、记录。

3．数据项

数据项是组成数据元素的、不可分割的最小单位。

表1.1为学生信息表，其中每个学生的信息可看作一个数据元素，它由学号、姓名、性别、籍贯等数据项组成。

表1.1　学生信息表

1.2.2　数据结构

数据结构（Data Structure）是由某一数据对象及该对象中所有数据元素之间的关系组成的。数据结构包括数据的逻辑结构、存储结构及数据的运算三方面的内容。接下来从这三方面分别阐述。

1．数据的逻辑结构

数据的逻辑结构是从逻辑关系上描述数据。数据的逻辑结构仅考虑数据之间的内在关系，是面向应用问题的，它是独立于计算机的。根据数据结构中数据元素之间关系的不同特征，可划分为四种基本逻辑结构，如图1.2所示。

（1）线性结构

线性结构中数据元素之间存在一对一的关系。例如，表1.1所示的学生信息表可看成一个线性结构，学生信息按照学号依次排列。

（2）树形结构

树形结构中数据元素之间存在一对多的关系。例如，一所学校有多个学院，一个学院有多个专业，构成树形结构。

（3）图结构

图结构中数据元素之间存在多对多的关系。例如，微信朋友圈中，“我”的朋友们彼此之间可能是相识关系，也可能是不相识关系，他们之间存在多对多的朋友关系，从而构成图结构。

图1.2　四种基本的逻辑结构示例

（4）集合结构

数据元素之间除了“属于同一个集合”的联系之外没有其他关系。例如，学生存在于某个班级中，若不考虑学生之间的其他关系，则可视班级为一个集合结构。

以上四种基本的逻辑结构还可进一步分成两类：线性结构和非线性结构。除了线性结构以外，树形、图和集合结构可统一归入非线性结构一类。

2．数据的存储结构

数据的存储结构是数据及数据之间的关系在计算机内的表示形式。它是面向计算机的，是数据的逻辑结构在计算机存储中的影像。数据的存储结构中，最常见的两种基本存储结构分别是顺序存储结构和链式存储结构。

（1）顺序存储结构

顺序存储结构是将逻辑上相关的数据元素依次存储在地址连续的存储空间中。这种存储结构是借助数据元素在存储空间中的相对位置来表示它们之间的逻辑关系。假定有一线性结构的数据（a₀,a₁,a₂），每个元素占2个存储单元，连续存储空间的起始地址是100，则其顺序存储表示如图1.3（a）所示。

顺序表示方法并不仅限于存储线性结构的数据。例如，树形结构的数据对象有时也可采用顺序存储的方法表示。这将在以后章节中详细阐述。

（2）链式存储结构

链式存储结构中，数据元素可以存储在任意的存储空间中，可以是连续的存储空间，也可以是不连续的存储空间。在这种情况下，数据元素的存储位置并不能体现它们之间的逻辑关系，需要用指针域存储逻辑上相关的数据元素的地址。因此，为了存储一个元素，需要存放数据元素本身和与该元素逻辑上相关的其他元素的地址，这两部分信息组成一个结点。

假定有一线性结构的数据（a₀,a₁,a₂），其链式存储表示如图1.3（b）所示。其中，每个结点存储了数据元素和该元素逻辑上的后继结点的地址。注意：一个结点的存储地址通常是指存放该结点的存储块的起始存储单元地址。

图1.3　两种基本的存储表示方法

在此约定，在不会引起混淆的场合，本书将不明确区分结点和元素这两个术语。但必要时，将包括数据元素和地址在内的整个存储块称为结点，而将其中的数据元素称为该结点的元素。

3．数据的运算

如果说数据的逻辑结构描述了数据的静态特性，那么在数据的逻辑结构上定义的一组运算给出了数据被使用的方式，即数据的动态特性。使用数据结构上定义的运算，用户可对数据结构的实例或组成实例的数据元素实施相应的操作。运算的结果可使数据改变状态。

数据结构最常见的运算有：

（1）搜索运算——在数据结构中搜索满足一定条件的元素；

（2）插入运算——在数据结构中插入新元素；

（3）删除运算——将数据结构中指定元素删除；

（4）更新运算——将数据结构中指定元素更新为新的元素。

1.3　抽象数据类型

1．数据类型

数据类型是指性质相同的值的集合以及定义在该值集上的运算集合。C语言常用的基本数据类型有整型、字符型、指针类型等。数据类型规定了数据的取值范围和允许执行的运算。例如，若在C语言中声明int a,b，则可以给变量a和b赋值0，但不可以赋值2.5，这超出了int型变量的取值范围。a和b之间可以执行加法运算，但不可以执行求交集运算，这也超出了int型变量所允许的运算范围。

2．抽象数据类型

了解一个数据类型的对象（变量、常量）在计算机内的表示是有一定用处的，但如果每个数据使用者都要考虑基本数据类型的实现细节，这将给数据使用者增加一项繁杂的工作，并且使用者一旦随意改变数据存储表示，也会滋生不可预知的错误。目前普遍认为对数据类型进行抽象，对使用者隐藏一个数据类型的实现是一个好的设计策略，由此产生了抽象数据类型。

抽象数据类型（Abstract Data Type，ADT）是一个数学模型以及在其上定义的运算集合。其最主要的两个特征是数据封装和信息隐蔽。数据封装是指把数据和操纵数据的运算组合在一起的机制。信息隐蔽是指数据的使用者只需知道这些运算的定义（也称规范）便可访问数据，而无须了解数据的存储以及运算算法的实现细节。通过实行数据封装和信息隐蔽，可使数据的使用和实现相分离。

本书中，抽象数据类型的定义格式如下：

3．数据结构与抽象数据类型

本书将一种数据结构视为一个抽象数据类型，从规范和实现两方面来讨论数据结构。规范是对数据结构中数据元素及其关系、运算给出定义，即逻辑结构和运算的定义组成了数据结构的规范。规范指明了一个数据结构可以“做什么”。数据结构的使用者通过规范中的说明使用一个数据结构，不必了解具体的实现细节。数据的存储表示和运算算法的描述构成数据结构的实现，它解决了“怎样做”的问题。

1.4　算法和算法分析

1.4.1　算法

算法是计算机科学中的基本概念，是对特定问题的求解步骤。算法须具有下列五个特征。

（1）输入：一个算法有0个或多个输入。

（2）输出：一个算法产生一个或多个输出，作为算法运算的结果。

（3）可行性：算法的每一个步骤都可以通过已经实现的基本运算来实现。

（4）确定性：算法的每一个步骤都必须有确切的含义，不会产生二义性。

（5）有穷性：算法必须能在执行有穷步之后终止。

算法的描述方式多种多样，可以用自然语言、流程图、程序设计语言或伪代码来描述。为了方便读者理解算法和上机验证算法，本书采用自然语言描述算法思想，并使用C语言描述算法的实现。

衡量一个算法的优劣，主要有以下几个基本标准。

（1）正确性

在合理的数据输入下，算法能够在有限的时间内产生满足预先规定的功能和性能要求。

（2）可读性

一个好的算法应当思路清晰、简单明了。可读性高的算法便于人们阅读、理解和交流；晦涩难懂的算法容易隐藏错误，不易被发现和调试。

（3）健壮性

一个好的算法应在输入不合法数据时，能做出适当处理，而不至于产生异常或是出现崩溃等严重后果。

（4）高效性

评价一个算法的效率主要包括时间和空间两方面。好的算法应具备执行效率高和占用存储空间少的特点。时间复杂度和空间复杂度是衡量算法效率的两个重要指标。

1.4.2　算法的时间复杂度

算法执行时间需通过依据该算法编制的程序在计算机上运行时所消耗的时间来度量。算法的时间复杂度一般是指程序运行从开始到结束所需的时间。而度量一个程序的执行时间通常有两种方法：事后统计法和事前估算法。事后统计法是将算法实现后计算其时间和空间开销，从而确定算法的效率。然而，时间和空间开销的计算与计算机软硬件环境相关，同一个算法在不同的机器上执行所花的时间也不一样，这种方法存在明显的缺陷，因此，不予采纳。本书采用事前估算法评估算法效率。

抛开与计算机软硬件相关的因素，影响算法时间效率最主要的因素是问题规模。问题规模通常是指算法的输入量，一般用整数n表示。例如，采用相同的排序算法对10个元素进行排序与对100 000个元素进行排序所需的时间显然是不同的。

一个算法时间花销与算法中语句的执行次数成正比例。算法中语句执行次数多，它的时间花销就多。一个算法中的语句执行次数称为语句频度。

一般情况下，算法中基本运算执行次数用T(n)表示，若有问题规模n的某个函数f(n)，使存在自然数n₀，正常数c，当n大于等于n₀时，T(n)≤cf(n)，则称f(n)是T(n)的渐近上界。记为

T(n)=O(f(n))

大O记号表示算法的一种渐近时间复杂度。渐近时间复杂度也常简称为时间复杂度。大O记号用以表达一个算法运行时间的上界，估计算法的执行时间的数量级。

下面举例说明算法的渐近时间复杂度的求解。

程序1.1　简单求和程序

程序1.1语句执行次数为5，算法的渐近时间复杂度为O(1)，属于常数级。

程序1.2　累加求和程序

程序1.2语句执行次数为2n+4，算法的渐近时间复杂度T(n)=O(n)。

程序1.3　矩阵求和程序

程序1.3语句执行次数为3+n+1+n(n+1)+n²=2n²+2n+4，算法的渐近时间复杂度T(n)=O(n²)。

一般情况下，可以通过考察一个程序中的关键操作的执行次数来计算算法的渐近时间复杂度。所谓关键操作是对算法执行时间贡献最大的操作。例如，程序1.2中，语句sum=sum+1可被认为是关键操作，其执行次数为n，由此计算可得算法的渐近时间复杂度也是O(n)。

常见的渐近时间复杂度从小到大依次是O(1)<O(log₂ n)<O(n)<O(nlog₂ n)<O(n²)<O(n³)。

1.4.3　最坏、最好和平均情况时间复杂度

算法的时间复杂度不仅与问题规模相关，如果输入数据不同，算法所需的时间开销也会不同。例如，在包含n个元素的数组中找给定元素x，设算法从左向右搜索，如果待搜索的元素x正好是第一个元素，则所需的查找时间最短，这就是算法的最好情况。如果待搜索的元素x是最后一个元素或是不在数组中，则是算法的最坏情况。如果需要多次在数组中查找元素，并且假定以相等的概率查找每个数组元素，则是算法时间代价的平均情况。

对于算法的时间复杂度分析，存在三种情况，对应三种时间复杂度，即最好情况、最坏情况和平均情况时间复杂度。相关示例将在后续章节中给出。

1.4.4　算法的空间复杂度

算法的空间复杂度往往是指对应的程序从运行开始到结束所需的存储量。

程序运行所需的存储空间包括两部分。

（1）固定部分。这部分空间与问题规模无关，主要包括程序代码、常量、简单变量等所占的空间。

（2）可变部分。这部分空间大小与问题规模有关。例如，长度为1 000的两个数组相加，与长度为10的两个数组相加，所需的存储空间是不同的。这部分存储空间除了包括数据元素所占的空间外，还包括算法执行所需的额外空间，如递归栈所用的空间。

算法的空间复杂度的讨论类似于时间复杂度，但空间复杂度一般按最坏情况来分析。

1.5　微课（一）

算法的时间复杂度是本章的重点和难点。这部分内容已制作成微课视频以供学习。

扫描以下二维码，可观看数据结构绪论的相关微课视频。

算法和算法分析

习题

一、基础题

1．对包含n个元素的数组进行顺序搜索时，若搜索每个元素的概率相同，则平均搜索长度为_____。

A．n/2

B．n

C．(n−1)/2

D．(n+1)/2

2．下面说法正确的是_____。

A．健壮的算法不会因非法的输入数据而出现莫名其妙的状态

B．算法的优劣与算法描述语言无关，但与所用计算机环境因素有关

C．数据的逻辑结构依赖于数据的存储结构

D．以上几个都是错误的

3．从逻辑上可以把数据结构分为_____两大类。

A．初等结构、构造型结构

B．顺序结构、链式结构

C．线性结构、非线性结构

D．动态结构、静态结构

4．数据采用链式存储时，存储单元的地址_____。

A．一定连续

B．一定不连续

C．不一定连续

D．部分连续，部分不连续

5．算法的时间复杂度取决于_____。

A．问题规模

B．计算机的软硬件配置

C．两者都是

D．两者都不是

6．下面的程序段的时间复杂度为_____。

A．O(2n)

B．O(n)

C．O(n²)

D．O(log₂n)

二、扩展题

1．简述下列概念：数据、数据元素、数据项。

2．什么是数据结构？

3．简述逻辑结构的四种基本关系。

4．最常见的存储结构有哪两种？

5．算法有哪些特征？

6．算法与程序的区别与联系是什么？

7．简述衡量算法优劣的基本标准。

8．对于下列程序段，分析带下划线语句的执行次数，并给出它们的时间复杂度。

第2章　线性表

线性表是最基础、最常用的一种线性数据结构。线性表被广泛应用于信息存储与管理、网络、通信等诸多领域。本章将给出线性表的定义和抽象数据类型描述，讨论线性表的逻辑结构、存储结构及相关运算，并以一元整系数多项式的算术运算为实例介绍线性表的简单应用。

2.1　线性表定义

线性表是零个或多个数据元素构成的线性序列，记为(a₀,a₁,…,a_n−1)。线性表中的数据元素个数n称为线性表的长度。当n=0时，此线性表为空表。

线性表(a₀,…,a_i−1,a_i,a_i+1,…,a_n−1)中，a_i表示下标为i的元素，a_i−1是a_i的直接前驱元素，a_i+1是a_i的直接后继元素。线性表除第一个数据元素a₀没有直接前驱元素，最后一个数据元素a_n−1没有直接后继元素之外，其他数据元素都有唯一一个直接前驱元素和直接后继元素。在不会引起混淆的情况下，我们简称直接前驱元素为“前驱”，直接后继元素为“后继”。线性表中数据元素之间存在着一对一关系，因此，线性表的逻辑结构为线性结构。

线性表是一种非常灵活的数据结构，可在线性表的任意位置执行插入、删除元素的运算，也可执行搜索、修改等运算。本章采用第1章给出的抽象数据类型格式对线性表进行描述，其中包括线性表最常见的运算，如ADT 2.1所示。

以上描述由抽象数据类型定义的线性表，暂不涉及具体的实现，因此所描述的参数和数据元素暂不必给出具体数据类型，可根据实际使用进行具体的表示和实现。

线性表有两种典型的存储结构：顺序存储结构和链式存储结构，以下分别介绍。

2.2　线性表的顺序存储结构和实现

2.2.1　线性表的顺序存储结构

线性表的顺序存储指使用连续的存储空间，按照数据元素在线性表中的序号依次存储数据元素。采用顺序存储结构的线性表称为顺序表。顺序表借助元素在存储空间中的位置来表示数据元素之间的逻辑关系：逻辑上相邻的数据元素，其物理存储地址也相邻。

设线性表中第一个元素a₀在内存中的存储地址是loc(a₀)，每个元素占用k个存储单元，则线性表中任意元素a_i在内存的存储地址为：

loc(a_i)=loc(a₀)+i×k　　（2-1）

由公式（2-1）可知，只要给定loc(a₀)和k的值，即可计算出任意元素在内存中的存储地址，从而进行数据元素的存取，所以线性表的顺序存储结构是一种随机存取结构。

C语言中，一维数组占用了内存中一组连续的存储单元，具备随机存取的特性，由此可使用一维数组描述线性表的顺序存储结构。线性表中的数据元素（a₀,…,a_i,…,a_n−1）在一维数组的存储形式如图2.1所示，图中maxLength是顺序表的最大允许长度。在处理实际问题时，所需线性表的长度会随具体问题的不同而不同，因此在实现顺序表时，使用动态分配的一维数组。

线性表的顺序表示定义如下。

图2.1　顺序表示例

在以上定义中，n是顺序表的长度，即顺序表中数据元素的个数。maxLength是顺序表的最大允许长度。ElemType是自定义类型，它是为了统一描述数据结构中数据元素的数据类型而设定的。在实际使用时，用户可以根据实际需要将ElemType具体定义为所需的数据类型，可以是int、float等基本数据类型，也可以是struct结构体类型等。例如typedef int ElemType，将ElemType定义为int型。指针element指示顺序表的存储空间的首地址。SeqList是类型名，可通过它定义相应变量，例如

SeqList L;

2.2.2　顺序表基本运算的实现

以下讨论顺序表中几个主要运算的具体实现。

1．初始化

顺序表的初始化运算是使用动态分配数组空间方式构造一个空的线性表。动态分配数组空间可以达到有效利用存储空间的目的。

【算法步骤】

（1）为顺序表L动态分配一维数组。

（2）若动态分配一维数组失败，则返回出错信息；否则返回OK。

程序2.1　顺序表的初始化

此处返回值类型Status为整型，返回OK代表1，返回ERROR代表0。之后在代码中出现将不再赘述。malloc是动态分配内存空间的函数。

2．查找

顺序表的查找运算是查找表中元素a_i的值。顺序表具有随机存取的特点，因此元素a_i的值可以直接通过数组下标定位取得。

【算法步骤】

（1）判断所要查找的元素下标i是否越界，若越界，返回ERROR。

（2）若下标i未越界，则取出element[i]的值通过参数x返回。

程序2.2　顺序表的查找

3．插入

顺序表的插入运算是在顺序表L的元素ai之后插入新元素x。若i=−1，则表示将新元素x插入顺序表的最前面。首先需要对i是否越界、顺序表存储空间是否已满进行判断。新元素x插入顺序表之前，将从n−1到i+1之间的所有元素依次向后移动一个位置。下面以实例进行说明，图2.2所示为新元素55插入前后线性表的变化。为了将新元素55插入下标为2的元素之后，需从下标为5的元素开始依次向后移动一个位置，直到下标为3的元素。

图2.2　顺序表中插入新元素55

【算法步骤】

（1）判断元素下标i是否越界，若已越界，返回ERROR。

（2）判断顺序表存储空间是否已满，若已满，返回ERROR。

（3）将元素（a_i+1,…,a_n−1）依次向后移动一个位置。

（4）将新元素x放入下标i+1的位置。

（5）表长加1。

程序2.3　顺序表的元素插入

【算法分析】

顺序表的元素插入运算过程中，时间主要消耗在移动元素上。对于长度为n的顺序表，在位置i（i=−1,0,1,…,n−1）后插入一个新元素，需要移动n−i−1个元素。设P_i是在位置i之后插入一个新元素的概率，并设在任意位置处插入元素的概率是相等的，则有P_i=1/(n+1)。设E_i是在长度为n的顺序表中插入一个新元素时所需移动元素的平均次数，则

由上述分析可知，顺序表插入算法的平均时间复杂度为O(n)。

4．删除

顺序表的删除运算的功能是将元素a_i删除。须先对i是否越界、顺序表是否为空进行判断。在顺序表中，逻辑上相邻的数据元素在物理位置上也需相邻，因此不能直接简单删除元素a_i，而需将从i+1到n−1之间的所有元素依次向前移动一个位置。下面以实例进行说明，图2.3所示为删除元素50前后线性表的变化。为了删除元素50，需从下标为3的元素开始依次向前移动一个位置，直到下标为5的元素。

图2.3　删除顺序表中的元素50

【算法步骤】

（1）判断元素下标i是否越界，若不越界，返回ERROR。

（2）判断顺序表是否为空，若为空，返回ERROR。

（3）将元素（a_i+1,…,a_n−1）依次向前移动一个位置。

（4）表长减1。

程序2.4　顺序表的元素删除

顺序表的元素删除运算过程中，时间主要消耗在移动元素上。对于长度为n的顺序表，删除位置i(i=0,1,…,n−1)上的一个元素，需要移动n−i−1个元素。设P_i是在位置i删除一个元素的概率，并设在任意位置处删除元素的概率是相等的，则有P_i=1/n。设E_d是在长度为n的顺序表中删除一个元素时所需移动元素的平均次数，则

由上述分析可知，顺序表删除算法的平均时间复杂度为O(n)。

5．输出

顺序表的输出运算是将顺序表的元素依次输出。

【算法步骤】

（1）判断顺序表是否为空，若为空，返回ERROR。

（2）将元素（a₀,…,a_n−1）依次输出。

程序2.5　顺序表的

....