作者：舒后
出版社：电子工业出版社
格式: AZW3, DOCX, EPUB, MOBI, PDF, TXT
数据结构试读：
前言
数字媒体技术是近年来各高校兴办的新专业，是交叉型、复合型的专业。“数据结构”课程是计算机程序设计的重要理论基础，它是计算机、数字媒体技术等相关专业重要的专业基础课程与核心课程，同时也是其他理工专业的热门选修课。本书是为“数据结构”课程编写的教材，其内容选取符合教学大纲要求，并兼顾不同学科的广度和深度，适用面广。
本书在编写中结合了编著者多年讲授这门课程的教学经验，合理地组织教材内容，做到内容紧凑、叙述深入浅出、图文并茂，并提供了大量的案例介绍。全书共8章：第1章绪论，以非数值计算的程序设计解决实际问题为例，说明什么是数据结构，数据结构的研究内容及相关概念，讨论了如何描述算法及对应的性能分析；第2～4章，主要讨论线性结构，如线性表、栈、队列、串、数组等，研究了各自的逻辑结构、存储结构及相关的数据操作；第5～6章讨论非线性结构，包括树、二叉树和图以及它们的应用；第7、8章讨论程序设计中常见的查找和排序问题，并就典型方法进行了详尽的算法分析和描述，不仅介绍了各种算法的实现，而且着重从时间上进行了定性或定量的分析和比较。
本书内容阐述详尽，文字通俗，简明易懂，算法分析循序渐进富有逻辑性，算法描述清晰准确，理论知识剖析清楚，且注重对难点的阐述，易于学生理解和自学。书中的算法均采用C语言实现，可直接在任何C环境下调试运行。每章后均配有相应的习题并提供参考答案，方便学生自主学习；同时，本书免费提供以教材为基本内容并符合课堂讲授方式的电子课件，这也是编著者在教学中一直使用的教学课件。通过教材的学习，希望达到理解数据结构理论并能运用常用算法解决实际问题的目的。
本书可作为高等院校相关课程的本科或专科教材，是适合应用型人才培养的教材，也可作为科技工作者的参考书，讲授48～80学时。教师根据学时、专业和学生的实际情况，选讲或不讲教材中的某些章节，如第4章的多维数组部分。
本书由舒后编著，参加编写的还有杨潮、何薇、陈如琪、程明智、葛雪姣、熊一帆、简琼、张雅倩、刘华群、齐红心、舒岳、陈红斌、李旸。在编写过程中得到了北京印刷学院数字媒体技术专业同仁的热情帮助，在此表示一并感谢！
本教材配套有教学资源PPT课件，如有需要，请登录电子工业出版社华信教育资源网（www.hxedu.com.cn），注册后免费下载。
由于作者水平所限，加之时间仓促，本书难免有错误和不足之处，希望读者给予指正。编著者2017年5月第1章绪论教学要求
①了解：数据结构这门学科的发展历史，以及在计算机科学中所处的地位。
②掌握：与数据结构有关的概念和术语。
③了解：算法的概念及特征。
④掌握：如何描述算法，以及算法和程序的关系。
⑤掌握：如何评价一个算法的好坏。1.1 引言
在20世纪40年代第一台ENIAC产生的时候，电子计算机的应用范围几乎仅局限于科学和工程的计算，其处理的对象是纯数值性的信息，通常，人们把这类问题称为数值计算。
电子计算机的发展异常迅猛，这不仅表现在计算机本身运算速度不断提高、信息存储量日益扩大、价格逐步下降，更重要的是计算机广泛地应用于情报检索、企业管理、系统工程等方面，已远远超出了科技计算的范围，而渗透到人类社会活动的一切领域。与此相应，计算机的处理对象也从简单的纯数值性信息发展到非数值性的和具有一定结构的信息（或数据），而非数值性数据是具有一定的结构的，数据与数据之间的关系也较为复杂。如何选择合适的数据表示（即结构），如何有效地组织计算机存储，如何在此基础上有效地实现对象之间的“运算”关系？传统的解决数值计算的许多理论、方法和技术已不能满足解决非数值计算问题的需要，必须进行新的探索。数据结构就是研究和解决这些问题的重要基础理论。1.2 数据结构的发展简史及其在计算机科学中所处的地位
1.发展史“数据结构”作为一门独立的课程在国外是从1968年开始设立的。在这之前，它涉及的内容分布在其他课程中。1968年在美国一些大学的计算机系的教学中，将“数据结构”规定为一门课程，美国人唐·欧·克努特教授开创了数据结构的最初体系，他所著的《计算机程序设计技巧》第一卷《基本算法》是第一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。
2.地位（1）“数据结构”在计算机科学中是一门综合性的专业基础课。（2）数据结构是介于数学、计算机硬件（特别是编码理论、存储装置和存取方法等）和计算机软件三者之间的一门核心课程。（3）数据结构这门课的内容不仅是一般程序设计（特别是非数值性程序设计）的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序的重要基础。1.3 什么是数据结构
一般来说，用计算机解决一个实际问题时，通常要经过以下几个步骤：首先从具体问题抽象出一个适当的数据模型（或数学公式）；然后设计一个用来描述此模型的算法；最后编写程序并上机调试，直到最终解决实际问题。若计算机处理的是数值计数问题，求解模型可用数学方程描述，涉及的运算对象一般是整型、实型或字符型等一些简单类型的数据。此时，程序设计者主要关注程序设计的技巧，而对数据的组织和存储就不那么关心。随着计算机应用领域的不断扩大，计算机处理的对象更多是非数值计算问题，如资料的查询、组织机构的管理、交通道路的规划等问题，它们的数学模型无法用数学方程进行描述，此时就必须建立相应的数据结构进行描述，分析问题中所用的数据是如何组织的，研究数据之间的关系，进而为解决这些问题设计出合适的数据结构。
下面从简单的案例入手，先直观地了解数据结构研究的是什么，然后给出具体的定义。
1.线性表示例
例1-1 一个具有8条记录的反映学生信息的数据文件如图1-1所示。图1-1 学生数据表
该学生数据表（即花名册）中记录之间的逻辑关系是一个线性关系（因此也称该数据文件为一个线性表）。整个花名册就是一个数据结构。针对该学生数据表，研究的问题主要有以下三方面。
①元素之间的关系：具体表现为表中有且仅有一条起始记录和终止记录；除了起始记录外，表中其他记录有且仅有一条记录是与之相邻的，且位于它前面的记录（称为直接前驱）；除了终止记录外，表中其他记录有且仅有一条记录是与之相邻的，且位于它后面的记录（称为直接后继）。这就是该花名册表的逻辑结构。
②存储：主要描述表中的记录如何存放在计算机中，这是存储结构。
③操作：对表中涉及的数据如何进行操作，如查找、插入、删除、修改和排序等，这就涉及数据的运算问题。
只有弄清以上三个方面的问题，才能有效地使用花名册这个数据结构，有效地解决这些学生基本信息的计算机管理问题。
2.树形结构示例
例1-2 一个单位的组织结构（或表示人类血缘关系的祖谱图）通常如图1-2所示。最顶层的结点代表某个机构的最高权力部分，它下面有若干分支，分别代表不同的机构或部门。图1-2 树形结构示意图
从图1-2中可看出呈现这种结构的记录与记录之间的关系（即逻辑结构）不同于例1-1的线性表，它像一棵倒立的树，具体表现如下：除起始记录（也称树根结点）外，其他记录有且仅有一个直接前驱记录，但直接后继记录可以有多个。这也是一个数据结构。
3.图状（形）结构示例
例1-3 城市之间的交通联系如图1-3所示，图中的顶点（结点）代表各城市，图中的边表示城市之间的道路。这幅交通网络图也表示一个数据结构，图中记录与记录之间的关系不同于以上两种：在这个数据结构中，结点之间的关系可以是任意的，任意两个结点之间都可以相关。即图中任意一个结点的直接前驱和直接后续都可以有多个。图1-3 图形结构示意图1.4 基本概念和术语
下面介绍数据结构的相关术语。
1.数据（Data）
数据是指能够输入计算机中，并被计算机识别和处理的符号的集合。例如，数字、字母、汉字、图形、图像、声音都可以称为数据。
2.数据元素（Data Element）
数据的基本单位是数据元素。在计算机中通常作为一个整体进行考虑和处理，例如，图1-1中学号为01的学生记录如下：
一个数据元素可由若干个数据项（域或称字段）组成，如上图中学号为01的这个数据元素，是由学号、姓名等6个数据项组成的。数据项是数据的最小单位。数据元素也称为结点、元素、记录等。
3.数据类型（Data Type）
数据类型是一组性质相同的值的集合，以及定义于这个值集合上的一组操作的总称。数据类型是指程序设计语言中各变量可取的数据种类。数据类型是高级程序设计语言中的一个基本概念，它和数据结构的概念密切相关，主要体现在以下两方面：
①在程序设计语言中，每一个数据都属于某种数据类型。数据类型显式或隐含地规定了数据的取值范围、存储方式及允许进行的运算。可以认为，数据类型是在程序设计中已经实现的数据结构。例如，C语言中用到的基本整数类型（int），它的取值范围是-32 767～+32 768，可进行的运算有加、减、乘、除、取模（即+、-、*、/、％）。
②在程序设计过程中，当需要引入某种新的数据结构时，总是借助编程语言所提供的数据类型来描述数据的存储结构。
4.抽象数据类型（Abstract Data Type，ADT）
ADT是指一个数学模型及定义在该数学模型上的一组操作，用户进行软件系统设计时，从问题的数学模型中抽象出来的逻辑数据结构和逻辑数据结构上的运算，而不考虑计算机的具体存储结构和运算的具体实现算法。
ADT并不是全新的概念，是大家熟悉的基本数据类型概念的引伸和发展。具体关系如下。
①与数据类型本质相同：基本数据类型已隐含着数据模型和定义在该模型上的运算。如各计算机均有的“整数”类型是一个抽象数据类型，不同处理器上实现的方法不同，但其定义的数学特征相同，在用户看来都是相同的。故“抽象”的意义在于数据类型的数学抽象特性。
②不同在于抽象数据类型的范畴更广（即引申和发展）：数据类型指的是高级语言支持的基本数据类型；抽象数据类型指的是在基本数据类型支持下用户新设计的数据类型。比如本书主要讨论的表、堆栈、队列、串、树、图等典型的常用数据结构。这些数据结构就是一个个不同的抽象数据类型。
抽象数据类型的特征是使用与实现相分离，实行封装和信息隐蔽。也就是说，在抽象数据类型设计时，把类型的定义与其实现分离开来。
通常软件设计采用模块化方法，抽象数据类型是构造大型软件的最基本模块。
描述抽象数据类型通常采用如下书写格式：
5.数据结构（Data Structure）
数据结构是一门研究数据是如何组织、存储、数据之间的相互关系及运算操作的学科。
具体来讲，数据结构主要包含3个方面的内容，即数据的逻辑结构、数据的存储结构和对数据所施加的运算（或操作）。
①元素之间的相互关系又称为数据的逻辑结构。数据的逻辑结构独立于计算机，是数据本身所固有的。
②数据元素在计算机内存中的表示，称为数据的物理结构（存储结构），必须依赖于计算机。
③对数据需要施加的操作主要包括查找、插入、删除、修改和排序等。运算的定义直接依赖于逻辑结构，但运算的实现必依赖于存储结构。
6.数据结构的分类（1）从逻辑结构的角度出发划分数据结构
①线性结构：主要特点如下。
·有且仅有一个开始结点（表头结点）a1。
·有且仅有一个终端结点（表尾结点）an。
·除表头结点外，其余的结点有且仅有一个直接前驱结点。
·除表尾结点外，其余的结点有且仅有一个直接后继结点。
总之，元素之间为一对一的线性关系。
②非线性结构：元素之间为一对多或多对多的非线性关系，即每个元素有多个直接前驱或多个直接后继。其中，元素之间为一对多关系的是树形结构，呈现多对多关系的是图状（形）结构。（2）从存储结构角度出发划分数据结构
①顺序存储（向量存储）：所有元素存放在一片连续的存储单元中，逻辑上相邻的元素存放到计算机内存仍然相邻。
②链式存储：所有元素存放在可以不连续的存储单元中，但元素之间的关系可以通过地址确定，逻辑上相邻的元素存放到计算机内存后不一定是相邻的。
③索引存储：使用该方法存放元素的同时，还建立附加的索引表，索引表中的每一项称为索引项，索引项的一般形式是（关键字，地址），其中的关键字是能唯一标识一个结点的某个数据项，如例1-4所示。
例1-4 用索引存储方法来表示各城市的基本信息，具体包括城市名、区号及简单说明。索引存储结构如表1-1（a）、（b）所示。表1-1（a） 索引表表1-1（b） 结点表
④散列存储：散列存储结构是根据结点的值确定结点的存储地址。通过构造散列函数，以结点中某个字段的值为自变量，通过散列函数计算对应的函数值，用该函数值来确定结点（即元素）存放的地址。详细可见第7章。
一般来说，这4种基本存储方法既可单独使用，也可组合起来，同一种逻辑结构可采用不同的存储方法，得到不同的存储结构，选择何种结构要视具体问题的要求而定。1.5 算法1.5.1 算法的概念
软件的最终成果都是以程序的形式表现的，数据结构的各种操作都是以算法的形式描述的。数据结构、算法和程序是密不可分的。三者的关系正如瑞士苏黎世联邦工业大学著名计算机科学家沃思（Wirth）提出的一个公式：数据结构+算法=程序。
其中，算法是灵魂，它解决“做什么”和“怎么做”的问题。
在给出算法的概念之前，先举两个例子来说明什么是算法。
例1-5 求1+2+3+4+…+100=？
方法1：直接相加，得出结果。
方法2：=100+（1+99）+（2+98）+…+（49+51）+50
=50*100+50
=5050
例1-6 求1*2*3*4*5=？
最原始的方法：S1：先求1*2，得2。
S2：将2*3，得6。
S3：将6*4，得24。
S4：将24*5=120，便得到最后的结果。
若求1*2*3*…*1000=？，再用此方法就不可行。因为需要999个步骤，故要找一种通用的方法。可设两个变量，一个变量代表被乘数（p），一个变量代表乘数（i）。
S1：使p=1。
S2：使i=2。
S3：使p*i，将p*i=＞p。
S4：i+1=＞i。
S5：若i不大于5，返回重新执行S3、S4和S5；否则，算法结束。
可见，算法（Algorithm）是对特定问题求解步骤的一种描述，是指令的有限序列。其中每一条指令表示一个或多个操作。1.5.2 算法的特征
一个算法应该具有下列特性。
①有穷性：一个算法应包含有限的操作步骤，而不能是无限的。
②确定性：每一步应是确定的，而不应是含糊的、模棱两可的，即无二义性。
③有输入：有零个或多个输入。
④有输出：有一个或多个输出，算法的目的是为了“解”，求结果。所以，没有输出的算法是没有意义的。
⑤有效性（可行性）。算法中的每一步都应能有效地执行，并得到确定的结果，如b=0，则表达式a/b是不能有效执行的。1.5.3 算法和程序
算法的含义与程序十分相似，但二者是有区别的。一个程序不一定满足有穷性（如操作系统这个系统软件，只要整个系统不遭破坏，它将永远不会停止，即使没有作业需要处理，它仍处于动态等待中。因此，操作系统不是一个算法）。另外，程序中的指令必须是机器可执行的，而算法中的指令则无此限制。算法代表了对问题的解，而程序则是算法在计算机上的特定的实现。一个算法若用计算机语言来书写，则它就是一个程序。
算法与数据结构是相辅相成的。解决某一特定类型问题的算法可以选定不同的数据结构，而且选择恰当与否直接影响算法的效率。反之，一种数据结构的优劣由各种算法的执行来体现。设计一个好的算法应考虑以下4条准则。
①正确性：算法应当满足具体问题的需求。
②可读性：算法主要为了人的阅读与交流，其次才是机器执行。可读性好有助于人对算法的理解，这样程序易于调试和修改。
③健壮性（坚固性）：当输入数据非法时，算法也能适当地做出反应或进行处理，而不会产生莫明其妙的输出结果。
④效率与低存储量需求：即高时间效率和高空间效率，其中效率指的是算法执行时间。1.5.4 算法的描述
算法可以使用各种不同的方法来描述，主要有以下几种。
1.自然语言
自然语言是人们日常使用的语言，如汉语、英文或其他语言。用自然语言来描述算法的优点是简单且便于人们对算法的阅读；缺点是不够严谨。
2.流程图表示算法
流程图表示算法是一种用图形表示算法的方法。ANSI规定了一些常用的流程图符号，如表1-2所示。表1-2 常用的流程图符号
例1-7 用流程图表示例1-6的算法，如图1-4所示。图1-4 算法的流程图表示
当算法比较复杂时，画流程图既费时又不方便，因为对流程线的使用没有严格限制，使用者可以不受限制地使流程随意地转来转去，使流程图变得毫无规律。这种乱麻一样的算法称为BS算法（a Bowl of Spaghetti）。
为了限制这种无规律的任意转向，人们规定了3种基本结构：顺序结构、选择机构和循环结构。由这些基本结构像建房子一样搭成各种算法结构，这样就能保证算法的质量。
①顺序结构如图1-5所示。
②选择结构如图1-6所示。图1-5 顺序结构图1-6 选择结构
③循环结构根据不同的执行情况，分为当型循环和直到型循环两种，如图1-7和图1-8所示。图1-7 当型循环图1-8 直到型循环
由这些基本结构构成的算法属于“结构化”算法。其实，基本结构不一定只限于上面3种，只要具备下面4个特点都可作为基本结构：
·只有一个入口；
·只有一个出口；
·结构内的每一部分都有机会被执行到（即对每一个框来说，有一条从入口到出口的路径通过它）；
·结构内不存在“死循环”（无终止的循环）。
3.用N-S图表示算法
1973年美国学者提出一种新的用图形表示算法的形式，即N-S图（盒图）。N-S图完全去掉了带箭头的流程线。这种流程图适用于结构化程序设计。同样有三种结构：顺序结构、选择结构和循环结构。N-S图的每种基本结构都是一个矩形框，整个算法可像堆积木一样堆成。
①顺序结构如图1-9所示。
②选择结构如图1-10所示。图1-9 顺序结构图1-10 选择结构
③循环结构如图1-11所示。
例1-8 用流程图表示例1-6的算法，如图1-12所示。图1-11 循环结构的当两种形式图1-12 算法的N-S图表示
无论是流程图还是N-S图，均是算法的图形表示方法，优点是直观形象，易于理解；缺点是不能直接在计算机上执行，若要将它转换成可执行的程序，还有一个编程的问题。
4.伪代码表示算法
为解决理解与执行这两者之间的矛盾，人们常常使用一种称为伪码语言的描述方法来进行算法描述。伪码语言介于高级程序设计语言和自然语言之间，它忽略高级程序设计语言中一些严格的语法规则与描述细节，因此，它比程序设计语言更容易描述和被人理解，而比自然语言更接近程序设计语言。伪码语言虽然不能直接执行，但很容易被转换成高级语言，所以，伪代码表示具有结构清晰、代码简单、可读性好的特点。
例1-9 用伪代码表示任意3个数中求最大数的算法。代码如下：
5.高级语言表示
直接用某种高级编程语言来表示算法，要求按照严格的语法规则来描述，该方法描述的算法可直接用于程序之中。
注：本书的算法全部用C语言来描述。1.5.5 算法分析
衡量算法优劣最重要的一点是效率与低存储量要求。算法效率（算法运行的时间）由时间复杂度来度量。一般，鉴于空间（内存）较为充足，故把算法的时间复杂度作为分析的重点。在求时间复杂度之前，先介绍频度统计法。
频度：一条语句的频度是指该语句被执行的次数。而整个算法的频度是指算法中所有基本语句的频度之和。
例1-10 求下列算法段的语句频度。
分析：该算法为一个二重循环，执行次数为内、外循环次数相乘，因此频度=n2。
1.时间复杂度
在刚才提到的算法频度中，n称为问题的规模（通常用正整数n表示）。当n不断变化时，语句频度也会不断变化。但有时我们想知道它变化时呈现什么规律。为此，我们引入时间复杂度概念。或者说时间复杂度是问题规模的函数。但算法的时间复杂度考虑的只是对问题规模n的增长率，难以精确计算出语句频度，只需求出它关于n的增长率或阶（数量级）即可。
一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数f（n），记作T（n）=O（f（n））。
其中，T（n）表示时间复杂度，大写字母O为英文Order（即数量级）单词的第一个字母。
例如，
语句x=x+1执行次数关于n的增长率为n2，故它的时间复杂度T（n）=O（n2）。
例1-11 求出下列算法段的时间复杂度。
分析可知：（1）T（n）=O（1）（2）T（n）=O（n），第3段代码，语句①的频度是n-1，语句②的频度是（n-1）（2n+1）=2n2-n-1，则该程序段的时间复杂度T（n）=n-1+2n2-n-1=O（n2），第4段代码是三层for循环，故时间复杂度为O（n3）。第5段代码中的语句①的频度是1，语句②的频度设为f（n），则有2 f（n）≤n，即f（n）≤log2n，取最大值f（n）=log2n。故该程序段的时间复杂度T（n）=1+log2n=O（log2n）。
思考：以下代码段的时间复杂度是多少？
总结：在各种不同算法中，若程序的运行时间不随着问题规模n的增加而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数，此类算法的时间复杂度仍是O（1）。另外，在频度不相同时，时间复杂度有可能相同，如T（n）=n2+3n+4与T（n）=4n2+2n+1的频度不同，但时间复杂度相同，都为O（n2）。
按数量级递增排列，常见的时间复杂度有常数阶O（1）、对数阶O（log2n）、线性阶O（n）、线性对数阶O（nlog2n）、平方阶O（n2）、立方阶O（n3）…k次方阶O（nk）、指数阶O（2n）。
随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率降低。
2.空间复杂度
一个程序需要的空间即存储量，包括输入数据所占空间、程序本身所占空间和辅助变量所占空间。我们一般是讨论算法占用的辅助存储空间，即空间复杂度是对一个算法在运行过程中临时占用的存储空间大小的量度。一般也作为问题规模n的函数，以数量级形式给出，记作：
S（n）=O（g（n））
讨论方法与时间复杂度类似，在此不再赘述。习题1
一、填空题
①数据的逻辑结构包括（ ）和（ ）两种类型，后者主要包括（ ）和（ ）两种结构。
②数据的存储结构包括（ ）、（ ）、（ ）和（ ）四种基本类型。
③数据的最小单位是（ ）。
二、按要求完成以下各题
①数据结构的研究内容是什么？
②求下面程序段的时间复杂度。第2章线性表教学要求
①了解：线性表的定义及其运算。
②掌握：线性表的顺序存储结构和链式存储结构。
③掌握：顺序表、单链表、循环链表、双向链表的定义及操作。
④掌握：线性表的各种典型应用。
线性表（Linear List）是最简单且最常用的一种数据结构。这种结构具有下列特点：存在一个唯一的没有前驱的（头）数据元素；存在一个唯一的没有后继的（尾）数据元素；此外，每一个数据元素均有一个直接前驱和一个直接后继数据元素。2.1 线性表的定义及其运算2.1.1 线性表的逻辑结构
1.线性表的定义
线性表是n（n≥0）个数据元素a1，a2，…，an组成的有限序列。其中，n称为数据元素的个数或线性表的长度，当n=0时称为空表，n＞0时称为非空表。通常将非空的线性表记为
L=（a1，a2，…，an）
其中，数据元素ai（1≤i≤n）是一个抽象的符号，其具体含义在不同情况下是不同的，即它的数据类型可以根据具体情况而定。
2.线性表的特征
从线性表的定义可以看出线性表的逻辑特征如下：
①有且仅有一个开始结点（表头结点）a1，它没有直接前驱，只有一个直接后继。
②有且仅有一个终端结点（表尾结点）an，它没有直接后继，只有一个直接前驱。
③其他结点有且仅有一个直接前驱和直接后继结点。
④元素（结点）之间为一对一的线性关系。2.1.2 线性表的抽象数据类型定义
下面给出线性表的抽象数据类型定义：2.1.3 线性表的运算
常见线性表的运算有如下几种。
①置空表（初始化）SETNULL（＆L）：将线性表L置成空表。
②求长度LENGTH（L）：求给定线性表L的长度。
③取元素GET（L，i）：若1≤i≤length（L），则取第i个位置上的元素，否则取得的元素为NULL。
④定位函数LOCATE（L，X）：在线性表L中查找值为X的元素位置，若有多个值为X，则以第一个为准；若没有，位置为0。
⑤插入INSERT（＆L，X，i）：在线性表L中第i个数据元素之前插入一个值为X的新元素。
⑥删除DELETE（＆L，i）：删除线性表L中第i个元素，当1≤i≤len时，删除成功，返回被删元素的值，否则返回NULL。
对线性表的操作还有很多，如取前驱、取后继及排序等。2.2 线性表的顺序存储结构
线性表的顺序存储结构也称为顺序表。其存储方式如下：在内存中开辟一片连续存储空间，该连续存储空间的大小要大于或等于顺序表的长度，然后让线性表中第一个元素存放在连续存储空间第一个位置，第二个元素紧跟着第一个之后，其余以此类推。
可见，在线性表上，逻辑关系相邻的两个元素在物理位置上也相邻，这就是线性表顺序存储的特点。
在顺序表中很容易确定每个数据元素在存储单元中与起始地址的相对位置：假设线性表中的元素为（a1，a2，…，an），设第一个元素a1的内存地址为ADR（a1），而每个元素在计算机内占K个存储单元，则第i个元素ai的首地址如图2-1所示。
ADR（ai）=ADR（a1）+（i-1）×K（其中1≤i≤n）图2-1 长度为n的线性表在计算机中的顺序存储结构
显然，顺序表便于进行随机访问，故线性表的顺序存储结构是一种随机存储的结构。而一维数组具有占用一片连续的存储区、可随机存取数组内元素的特点，故在程序设计语言中，通常定义一个一维数组来表示线性表的顺序存储空间。2.2.1 顺序表的结构
下面用C语言给出顺序表的定义：
说明：编程中使用此定义时，maxlen及elemtype要根据实际问题的需要来进行设定。
有了线性表的顺序存储结构后，下面就可以讨论如何在该结构上实现有关数据元素的运算问题。重点讨论线性表元素的插入和删除。2.2.2 顺序表的基本运算
1.插入运算
线性表的插入是指在表的第i个位置插入一个值为x的新元素，通常在第i个元素（1≤i≤n+1）插入一个新元素时，需要有n-i+1个元素进行移动。通过以下步骤完成顺序表的插入运算：
①将an～ai共n-i+1个元素依次向下移动，为新元素空出位置。
②将x置入空出的第i个位置。
③修改len值（即修改表长），使之加1。
插入前：L=（a1，…，ai-1，ai，…，an）
插入后：L=（a1，…，ai-1，x，ai，…，an）
若i=3，则顺序表L=（10，12，25，8，16，20）在插入x（值为15）前后的状态对比如图2-2所示。图2-2 顺序表插入前后状态的对比
注意：此处的i是表示顺序表中元素的位置，称为位序，与数组的下标概念不同。
算法描述如下：
算法中需注意以下问题：
①顺序表中数据区域有MAXSIZE个存储单元，所以，在向顺序表中插入时先检查表空间是否已满，在表满的情况下不能再做插入，否则会产生溢出错误。
②要检验插入位置的有效性，这里i的有效范围是1≤i≤n+1，其中n为原表长，用（*L）.len表示。
③注意数据的移动方向。
性能分析：
插入算法花费的时间，主要在于循环中元素的后移（其他语句花费的时间可以省去），即从插入位置到最后位置的所有元素都要后移一位，使空出的位置插入元素值x。但是，插入的位置是不固定的，当插入位置i=1时，全部元素都得移动，需n次移动，当i=2时，移动n-1个元素，以此类推，当i=n时，仅需移动元素一次。设pi为在第i个数据元素之前插入一个元素的概率，假设在顺序表的任何位置插入元素都是等概率的，即pi=1/（n+1），则在长度为n的顺序表中插入一个元素时所需的平均移动次数为
可见，在顺序表上做插入操作需移动表中一半的数据元素，显然时间复杂度为O（n）。
2.删除运算
线性表的删除运算是指将表中第i个元素从线性表中去掉，i的取值范围为1≤i≤n。
通过以下步骤完成顺序表的删除运算：
①将ai+1～an顺序向前（向上）移动。
②修改len值（即修改表长），使之减1。
删除前：L=（a1，…，ai-1，ai，…，an）
删除后：L=（a1，…，ai-1，ai+1，…，an）
若i=3，则顺序表L=（10，12，25，8，16，20，45）在删除ai（值为25）前后的状态对比如图2-3所示。图2-3 顺序表删除前后状态的对比
算法描述如下：
算法需注意以下问题：
①删除第i个元素，i的取值为1≤i≤n，否则第i个元素不存在，因此，要检查删除位置的有效性。
②当表为空时不能进行删除，而条件（i＜1||i＞L→len）也包括了对表空的检查。
③删除ai之后，该数据已不存在，如果需要，可先取出ai，再进行删除。
性能分析：
与插入运算相同，删除第i个元素时，后面的元素ai+1～an都要向上移动一个位置，共移动了n-i个元素，故平均移动次数为
说明在顺序表上进行删除运算大约需要移动表中一半的元素，显然该算法的时间复杂度为O（n）。2.3 线性表的链式存储结构
线性表的链式存储结构，也称为链表。链式存储是用一些任意的存储单元来存储线性表中的元素，这些单元在物理上既可以是连续的，也可以是不连续的。为了能正确地描述元素之间的逻辑关系，除存储元素本身的信息外，还需存储指示元素之间逻辑关系的信息。这
试读结束[说明：试读内容隐藏了图片]