课件第二章数据结构顺序表

1、NO：1常用数据结构常用数据结构第二章第二章NO：2第二章第二章 常用数据结构及其运算常用数据结构及其运算2 21 1 数据结构数据结构2 22 2 线性表线性表2 23 3 栈与队栈与队2 25 5 数组数组2 26 6 树与二叉树树与二叉树2 27 7 图图2 28 8 查查 找和排找和排 序序NO：3第二章第二章 常用数据结构及其运算常用数据结构及其运算2.1 2.1 数据结构数据结构当今计算机应用的特点：当今计算机应用的特点： a) 所处理的数据量大且具有一定的关系；所处理的数据量大且具有一定的关系； b) 对其操作不再是单纯的数值计算，而更多地是对其操作不再是单纯的数值计算，而更多地

2、是需要对其进行组织、管理和检索。需要对其进行组织、管理和检索。应用举例应用举例1学籍档案管理学籍档案管理 假设一个学籍档案管理系统应包含如下表所示的学假设一个学籍档案管理系统应包含如下表所示的学生信息。生信息。 学 号姓 名性 别出生年月.99070101李 军男8012.99070102王颜霞女812.99070103孙 涛男809.99070104单晓宏男813.NO：4第二章第二章 常用数据结构及其运算常用数据结构及其运算2.1 2.1 数据结构数据结构特点：特点：i ) 每个学生的信息占据一行，所有学生的信息按每个学生的信息占据一行，所有学生的信息按学号顺序依次排列构成一张表格；学号顺

3、序依次排列构成一张表格；ii ) 表中每个学生的信息依据学号的大小存在着一表中每个学生的信息依据学号的大小存在着一种前后关系，这就是我们所说的线性结构；种前后关系，这就是我们所说的线性结构；iii ) 对它的操作通常是插入某个学生的信息，删除对它的操作通常是插入某个学生的信息，删除某个学生的信息，更新某个学生的信息，按条件某个学生的信息，更新某个学生的信息，按条件检索某个学生的信息等等。检索某个学生的信息等等。应用举例应用举例2输出输出n个对象的全排列个对象的全排列 输出输出n个对象的全排列可以使用下图所示的形式描个对象的全排列可以使用下图所示的形式描述。述。NO：53121321231232

4、1231213211特点：特点：i ) 在求解过程中，所处理的数据之间具有层次关系，这在求解过程中，所处理的数据之间具有层次关系，这是我们所说的树形结构；是我们所说的树形结构；ii ) 对它的操作有：建立树形结构，输出最低层结点内容对它的操作有：建立树形结构，输出最低层结点内容等等。等等。NO：6第二章第二章 常用数据结构及其运算常用数据结构及其运算2.1 2.1 数据结构数据结构应用举例应用举例3制定教学计划制定教学计划 在制定教学计划时，需要考虑各门课程的开在制定教学计划时，需要考虑各门课程的开设顺序。有些课程需要先导课程，有些课程则不设顺序。有些课程需要先导课程，有些课程则不需要，而有些

5、课程又是其他课程的先导课程。比需要，而有些课程又是其他课程的先导课程。比如，计算机专业课程的开设情况如下表所示：如，计算机专业课程的开设情况如下表所示：课程编号课程名称需要的先导课程编号C1程序设计基础无C2离散数学C1C3数据结构C1 ， C2C4汇编语言C1C5算法分析与设计C3 ， C4C6计算机组成原理C11C7编译原理C5 ， C3C8操作系统C3 ， C6C9高等数学无C 10线性代数C9C11普通物理C9C12数值分析C9 ， C10， C1课程编号课程名称需要的先导课程编号C1程序设计基础无C2离散数学C1C3数据结构C1 ， C2C4课程编号课程名称需要的先导课程编号C1程序

6、设计基础无C2离散数学C1C3数据结构C1 ， C2C4汇编语言C1C5算法分析与设计C3 ， C4C6计算机组成原理C11C7编译原理C5 ， C3C8操作系统C3 ， C6汇编语言C1C5算法分析与设计C3 ， C4C6计算机组成原理C11C7编译原理C5 ， C3C8操作系统C3 ， C6C9高等数学无C 10线性代数C9C11普通物理C9C12数值分析C9 ， C10， C1C9高等数学无C 10线性代数C9C11普通物理C9C12数值分析C9 ， C10， C1NO：7第二章第二章 常用数据结构及其运算常用数据结构及其运算2.1 2.1 数据结构数据结构特点特点: i ) 课程之间的

7、先后关系用图结构描述；课程之间的先后关系用图结构描述； ii ) 通过实施创建图结构，然后对该有向图结构中的通过实施创建图结构，然后对该有向图结构中的顶点进行拓扑排序。顶点进行拓扑排序。课程先后关系的图形描形式：课程先后关系的图形描形式：c1c9c4c2c12c10c11c5c3c6c7c8NO：8第二章第二章 常用数据结构及其运算常用数据结构及其运算2.1 2.1 数据结构数据结构结论结论 计算机的操作对象的关系更加复杂，操计算机的操作对象的关系更加复杂，操作形式不再是单纯的数值计算，而更多地是作形式不再是单纯的数值计算，而更多地是对这些具有一定关系的数据进行组织管理，对这些具有一定关系的数

8、据进行组织管理，我们将此称为非数值性处理。要使计算机能我们将此称为非数值性处理。要使计算机能够更有效地进行这些非数值性处理，就必须够更有效地进行这些非数值性处理，就必须弄清楚这些操作对象的特点，在计算机中的弄清楚这些操作对象的特点，在计算机中的表示方式以及各个操作的具体实现手段。这表示方式以及各个操作的具体实现手段。这些就是数据结构个章节研究的主要内容。些就是数据结构个章节研究的主要内容。NO：9第二章第二章 常用数据结构及其运算常用数据结构及其运算2.1 2.1 数据结构数据结构一、什么是数据结构一、什么是数据结构1. 数值型与非数值型数据数值型与非数值型数据2. 数据结构数据结构3.简单来

9、说，就是相互之间存在一种或多简单来说，就是相互之间存在一种或多种特定关系的数据元素的集合。种特定关系的数据元素的集合。4.如线性关系、层次关系、网状关系等。如线性关系、层次关系、网状关系等。NO：10第二章第二章 常用数据结构及其运算常用数据结构及其运算2.1 2.1 概概 述述二、有关数据结构的基本概念和术语二、有关数据结构的基本概念和术语1.1. 数据数据(data)(data)：是信息的载体，它可以用计算机：是信息的载体，它可以用计算机表示并加工，如数、字符、符号等的集合。分表示并加工，如数、字符、符号等的集合。分为数值型数据和非数值型数据两类。为数值型数据和非数值型数据两类。2.2.

10、数据元素数据元素(data element)(data element)：是数据集合中的：是数据集合中的一个个体，是数据的基本单位。如数据集合一个个体，是数据的基本单位。如数据集合N=1N=1，2 2，3 3，4 4，55中整数中整数1 1至至5 5均为数据元素。均为数据元素。3.3. 数据元素不一定是单个的数字或字符，数据元素不一定是单个的数字或字符，也可能是若干个数据项的组合，如学生信息。也可能是若干个数据项的组合，如学生信息。学生（学号，姓名，性别，成绩）学生（学号，姓名，性别，成绩）4.4. 数据元素有时也称结点或记录。数据元素有时也称结点或记录。NO：11第二章第二章 常用数据结构及

11、其运算常用数据结构及其运算2.1 2.1 概概 述述3.3. 数据对象数据对象(data object)(data object)：是具有相同性质的：是具有相同性质的数据元素的集合。如大写字母字符的数据对象数据元素的集合。如大写字母字符的数据对象是集合：是集合：C= AC= A，BB，.，Z Z 。4.4. 数据结构数据结构(data structure)(data structure)：是指同一数据：是指同一数据对象中各数据元素间存在的关系。用集合论方对象中各数据元素间存在的关系。用集合论方法定义数据结构为：法定义数据结构为：S =S =（D D，R R）5.5. 数据结构数据结构S S是一

12、个二元组，是一个二元组，D D是一个数据是一个数据元素的非空有限集合，元素的非空有限集合，R R是定义在是定义在D D上的关系的上的关系的非空有限集合。非空有限集合。6.6.例如一个向量例如一个向量x=(x1,x2,xn)x=(x1,x2,xn)，D=x1,x2,xnD=x1,x2,xnR=,R=,。NO：12第二章第二章 常用数据结构及其运算常用数据结构及其运算2.1 2.1 概概 述述逻辑结构：是对数据元素之间逻辑关系（抛开具体逻辑结构：是对数据元素之间逻辑关系（抛开具体的关系含义以及存储方式等）的描述，它可以用一的关系含义以及存储方式等）的描述，它可以用一个数据元素的集合和定义在此集合上

13、的几个关系来个数据元素的集合和定义在此集合上的几个关系来表示。通常可用图形表示，圆圈表示数据元素，箭表示。通常可用图形表示，圆圈表示数据元素，箭头表示关系：头表示关系：物理结构：数据结构在计算机中的具体表示和实现，物理结构：数据结构在计算机中的具体表示和实现，又称存储结构又称存储结构E i+1数据元素数据元素数据元素数据元素关系关系E iNO：13按逻辑结构分类：按逻辑结构分类： 纯集合型结构纯集合型结构: :数据元素之间除了数据元素之间除了“同属同属于一个集合于一个集合”这一这一 关系外，别无其他关系外，别无其他关系关系 线性结构：数据元素之间存在线性结构：数据元素之间存在“一个跟一个跟着一

14、个着一个”的序列关系的序列关系 树型结构：数据元素之间存在树型结构：数据元素之间存在“每个元每个元素只能跟着一个元素素只能跟着一个元素 但可以有多个元素跟着它但可以有多个元素跟着它”的层次关系的层次关系 图状结构：任意两个数据元素之间都可图状结构：任意两个数据元素之间都可能存在关系能存在关系按存储结构分类：按存储结构分类： 顺序存储结构顺序存储结构 链式存储结构链式存储结构 索引存贮结构索引存贮结构2.1 2.1 概概 述述第二章第二章 常用数据结构及其运算常用数据结构及其运算NO：14第二章第二章 常用数据结构及其运算常用数据结构及其运算2.1 2.1 概概 述述7.7. 数据结构与算法数据

15、结构与算法8.8. 算法是解决某一特定类型问题的有限运算法是解决某一特定类型问题的有限运算序算序 列。列。9.9. 算法的实现必须借助于程序设计语言中算法的实现必须借助于程序设计语言中提供提供 的数据类型及其运算。的数据类型及其运算。10.10. 数据结构的选择对数据处理的效率起着数据结构的选择对数据处理的效率起着至关至关 重要的作用。重要的作用。11.11. 程序算法数据结构程序算法数据结构12.12. 数据结构分线性和非线性两种。数据结构分线性和非线性两种。NO：15第二章第二章 常用数据结构及其运算常用数据结构及其运算2.1 2.1 概概 述述三、算法描述语言三、算法描述语言 算法是由一

16、套计算规则组成的一个过程；算法是由一套计算规则组成的一个过程； 组成算法的规则是确定的、可执行的；组成算法的规则是确定的、可执行的； 算法必须有确定的结果，有一个或多个输出；算法必须有确定的结果，有一个或多个输出； 每个算法必须有每个算法必须有0 0个或多个输入；个或多个输入； 解答必须在有限步内得到解答必须在有限步内得到, ,不能出现不能出现“死循环死循环”。我们可以得出如下的结论：算法是一个过程，我们可以得出如下的结论：算法是一个过程，这个过程由一套明确的规则组成，这些规则指这个过程由一套明确的规则组成，这些规则指定了一个操作的顺序，以便用有限的步骤提供定了一个操作的顺序，以便用有限的步骤

17、提供特定类型问题的解答。特定类型问题的解答。NO：16第二章第二章 常用数据结构及其运算常用数据结构及其运算2.1 2.1 概概 述述举例举例 问题：按从小到大的顺序重新排列问题：按从小到大的顺序重新排列x，y，z三个三个数值的内容。数值的内容。算法：算法： （1）输入）输入x，y，z三个数值；三个数值； （2）从三个数值中挑选出最小者并换到）从三个数值中挑选出最小者并换到x中；中； （3）从）从y，z中挑选出较小者并换到中挑选出较小者并换到y中；中； （4）输出排序后的结果。）输出排序后的结果。NO：17第二章第二章 常用数据结构及其运算常用数据结构及其运算2.1 2.1 概概 述述四、算法

18、分析技术初步四、算法分析技术初步 一个可执行的算法不一定是一个好算法，算法一个可执行的算法不一定是一个好算法，算法的分析是一个复杂的问题，通常用计算机执行时的分析是一个复杂的问题，通常用计算机执行时在时间和空间两方面的消耗多少作为评价该算法在时间和空间两方面的消耗多少作为评价该算法优劣的标准。优劣的标准。 这两个标准分别称为时间复杂度和空间复杂度。这两个标准分别称为时间复杂度和空间复杂度。一般时间复杂度考虑的较多。一般时间复杂度考虑的较多。 度量一个程序的执行时间通常有两种方法：度量一个程序的执行时间通常有两种方法： 事后统计和事前分析估算事后统计和事前分析估算NO：18第二章第二章 常用数据

19、结构及其运算常用数据结构及其运算2.1 2.1 概概 述述 事后统计方法：利用计算机内部的定时器事后统计方法：利用计算机内部的定时器( (如调用如调用QueryPerformanceCounter() ApiQueryPerformanceCounter() Api函数函数 ）对函数运行）对函数运行时间进行计数时间进行计数 缺点：缺点：1. 1. 必须执行程序必须执行程序 2. 2. 其它因素掩盖算法本质其它因素掩盖算法本质 事前分析估算：运行时间取决于下列因素事前分析估算：运行时间取决于下列因素 a) a) 选择何种算法；选择何种算法； b) b) 问题的规模，例如求问题的规模，例如求100

20、100以内还是以内还是10001000以内的素以内的素数数 c) c) 书写程序的语言：语言级别越高，执行效率越书写程序的语言：语言级别越高，执行效率越低低 d) d) 编译程序所产生机器代码的质量；编译程序所产生机器代码的质量； e) e) 机器执行指令的速度机器执行指令的速度NO：19第二章第二章 常用数据结构及其运算常用数据结构及其运算2.1 2.1 概概 述述1.1. 时间复杂度时间复杂度2.2. 频度：指一条语句重复执行的次数。频度：指一条语句重复执行的次数。 记作：记作：F(n)F(n)3.3. 时间复杂度：时间复杂度：T(n)=O(F(n)T(n)=O(F(n)4.4. 下面举例

21、说明如何求时间复杂度？下面举例说明如何求时间复杂度？ NO：20第二章第二章 常用数据结构及其运算常用数据结构及其运算2.1 2.1 概概 述述1. for (i=0; in; i+)1. for (i=0; in; i+)2. for (j=0; jn; j+)2. for (j=0; jn; j+)3. cij=0;3. cij=0;4. for (k=0; kn; k+)4. for (k=0; kn; k+)5. cij=cij+aik5. cij=cij+aik* *bkj;bkj;6. 6. 我们以执行次数最多的语句（第我们以执行次数最多的语句（第5 5句）进行计算：句）进行计算：

22、 语句频度为：语句频度为：F(n)=n3F(n)=n3 时间复杂度：时间复杂度：T(n)=O(F(n)=O(n3)T(n)=O(F(n)=O(n3)两个两个n阶方阵的乘积阶方阵的乘积C = A x BNO：21第二章第二章 常用数据结构及其运算常用数据结构及其运算2.1 2.1 概概 述述 4 4）思考下列程序段的时间复杂度）思考下列程序段的时间复杂度 1 1、x=x+1;x=x+1;T(n)=O(1)T(n)=O(1)T(n)=O(n)T(n)=O(n)T(n)=O(n2)T(n)=O(n2)T(n)=O(n2)T(n)=O(n2)4 4、for (j=2; j=n; j+)for (j=2

23、; j=n; j+) for (k=2; k=j-1; k+) for (k=2; k=j-1; k+) x=x+1; x=x+1; 3 3、for (j=0; jn; j+)for (j=0; jn; j+) for (k=0; kn; k+) for (k=0; kn; k+) x=x+1; x=x+1; 2 2、for (j=0; jn; j+) x=x+1;for (j=0; jn; j+) x=x+1;计算方法：对于外层循环中计算方法：对于外层循环中的的j j，从，从2 2到到n n循环，计算出循环，计算出j j每取一个值时，内层循环执每取一个值时，内层循环执行的次数行的次数0 0、

24、1 1、2 2、.、n-2n-2，然后累加起来，得到一个然后累加起来，得到一个n n的的多项式多项式(n-1)(n-2)/2(n-1)(n-2)/2，取出，取出次数最高的项即可。次数最高的项即可。NO：22第二章第二章 常用数据结构及其运算常用数据结构及其运算2.1 2.1 概概 述述 常见的时间复杂度常见的时间复杂度 1 1）O(1)O(1)：常量型：常量型 2 2）O(n)O(n)、O(n2)O(n2)、.、O(nk)O(nk)：多项式型：多项式型 3 3）O(log2n)O(log2n)、O(2log2n)O(2log2n)：对数型：对数型 4 4）O(2n)O(2n)、O(en)O(e

25、n)：指数型：指数型log2n n nlog2n n2 n3 2n 3n 时，时，f(n)=(n-1)(n-2)/2 与与n2成正比，即程成正比，即程序运行时间的量度与序运行时间的量度与n2为同一数量级，因此即为为同一数量级，因此即为O(n2).NO：25第二章第二章 常用数据结构及其运算常用数据结构及其运算2.2 2.2 线线 性性 表表常用的时间复杂度常用的时间复杂度:O(1) 常数时间，即算法时间用量和输入数据量无关常数时间，即算法时间用量和输入数据量无关O(logn) 对数时间，对数阶通常不写底数，在计算对数时间，对数阶通常不写底数，在计算 机科学中，一般以机科学中，一般以2为底为底O

26、(n) 线性时间，即算法时间用量与线性时间，即算法时间用量与n成正比成正比O(nlogn)O(n2)O(n3)。以上都属于多项式阶，在算法理论中，如果某算以上都属于多项式阶，在算法理论中，如果某算法的时间用量的阶超过多项式阶，达到指数时间法的时间用量的阶超过多项式阶，达到指数时间O(2n)，或阶乘时间，或阶乘时间O(n!)，那么这个算法就是一，那么这个算法就是一个无效算法，因为只要数据量个无效算法，因为只要数据量n稍大，算法就不稍大，算法就不可能在可能在“有限步有限步”内完成。相应地，多项式时间内完成。相应地，多项式时间阶的算法属于有效算法。阶的算法属于有效算法。NO：26第二章第二章 常用数

27、据结构及其运算常用数据结构及其运算2.1 2.1 概概 述述2.2. 空间复杂度空间复杂度3.3. 空间复杂度是指在算法中所需的辅助空空间复杂度是指在算法中所需的辅助空间单元而不包括问题的原始数据占用的空间间单元而不包括问题的原始数据占用的空间（因为这些单元与算法无关），记作：（因为这些单元与算法无关），记作：S(n)S(n)4.4. 时间与空间是一对矛盾。要节约空间往时间与空间是一对矛盾。要节约空间往往就要消耗较多时间，反之亦然，而目前由于往就要消耗较多时间，反之亦然，而目前由于计算机硬件的发展，一般都有足够的内存空间，计算机硬件的发展，一般都有足够的内存空间，因此在分析中着重考虑时间的因素

28、。因此在分析中着重考虑时间的因素。NO：27第二章第二章 常用数据结构及其运算常用数据结构及其运算2.2 2.2 线线 性性 表表一、线性表的定义和运算一、线性表的定义和运算1.1. 线性表的概念线性表的概念2.2. 由相同种类的数据元素组成的一个有穷由相同种类的数据元素组成的一个有穷序列称为一个线性表。序列称为一个线性表。“一个跟着一个一个跟着一个” ” a2ana1NO：282. 线性表的结构特点线性表的结构特点数据元素之间是线性关系，即在线性表中必存在数据元素之间是线性关系，即在线性表中必存在唯一的一个称为唯一的一个称为“第一个第一个”的元素；必存在唯一的元素；必存在唯一的一个称为的一个

29、称为“最后一个最后一个”的元素；的元素；NO：29第二章第二章 常用数据结构及其运算常用数据结构及其运算2.2 2.2 线线 性性 表表 除第一个元素外，每个元素都有且只有一个前除第一个元素外，每个元素都有且只有一个前驱元素；除最后一个元素外，每个元素都有且驱元素；除最后一个元素外，每个元素都有且只有一个后继元素。所有数据元素只有一个后继元素。所有数据元素aiai在同一个在同一个线性表中必须是相同的数据类型。线性表中必须是相同的数据类型。线性表的定义线性表的定义 L= L=（D D，R R）2 ,11niDaaaaRiiii,.,21naaaD 有序对有序对NO：30第二章第二章 常用数据结构

30、及其运算常用数据结构及其运算2.2 2.2 线线 性性 表表4.4. 有序表与无序表的概念有序表与无序表的概念5.5. 若线性表中的数据元素相互之间可以比较，若线性表中的数据元素相互之间可以比较，且且aiai-1 aiai-1 ，i=2i=2，3 3，.，n n 则称该线性表则称该线性表为有序表，否则称为无序表。为有序表，否则称为无序表。6.6. 线性表的基本运算线性表的基本运算7.7. 插入、删除、查找、排序等。插入、删除、查找、排序等。NO：31第二章第二章 常用数据结构及其运算常用数据结构及其运算2.2 2.2 线线 性性 表表二、顺序存储线性表二、顺序存储线性表1. 顺序存储结构（顺序

31、表）顺序存储结构（顺序表）2. 要实现在计算机内表示一个数据结构，要解决要实现在计算机内表示一个数据结构，要解决两种信息的存贮问题：两种信息的存贮问题：3. 数据元素本身的存贮数据元素本身的存贮4. 数据元素之间关系的存贮数据元素之间关系的存贮5. 定义：利用内存物理结构上的邻接特点，实现定义：利用内存物理结构上的邻接特点，实现线性表的线性表的“一个跟着一个一个跟着一个”这一序列关系的存这一序列关系的存贮方式，称为线性表的顺序存贮结构，其上的贮方式，称为线性表的顺序存贮结构，其上的线性表称为顺序表。线性表称为顺序表。NO：32第二章第二章 常用数据结构及其运算常用数据结构及其运算2.2 2.2

32、 线线 性性 表表 地址计算：设每个元素占地址计算：设每个元素占k k个单元，线性表个单元，线性表在内存中的首地址为：在内存中的首地址为：addr(a1)addr(a1)，则线性表中，则线性表中第第i i个元素的存储地址为：个元素的存储地址为： addr(ai)=addr(a1)+(i-1) addr(ai)=addr(a1)+(i-1)* *k k 特点：这种存储结构只要知道元素的序号，特点：这种存储结构只要知道元素的序号，就很容易找到第就很容易找到第i i个数据元素，且无论序号个数据元素，且无论序号i i为为何值，找到第何值，找到第i i个元素所需时间相同。所以，个元素所需时间相同。所以，

33、这种存储结构亦称为随机存储结构。这种存储结构亦称为随机存储结构。NO：33 在顺序存储结构中，逻辑上相邻的数据元素在计在顺序存储结构中，逻辑上相邻的数据元素在计算机存储空间中的位置也是相邻的，因此，数据元算机存储空间中的位置也是相邻的，因此，数据元素之间的前后件关系可以由它们在存储结构中前后素之间的前后件关系可以由它们在存储结构中前后位置的邻接关系唯一确定。位置的邻接关系唯一确定。 顺序存储主要用于线性结构，不能用于非线性结顺序存储主要用于线性结构，不能用于非线性结构构2.2 2.2 线线 性性 表表第二章第二章 常用数据结构及其运算常用数据结构及其运算NO：34顺序表之整体概念：顺序表之整体

34、概念： datadata0 01 1n nMaxsizeMaxsizen n数组下标数组下标 数组数组变量变量操作算法操作算法Maxsize-1Maxsize-1初始化操作初始化操作插入操作插入操作删除操作删除操作查找操作查找操作排序操作排序操作 . . . . . . . . . . . . . . . . . . . . . . . . . .NO：35第二章第二章 常用数据结构及其运算常用数据结构及其运算2.2 2.2 线线 性性 表表2.2. 顺序存储结构的插入、删除运算顺序存储结构的插入、删除运算3.3. 插入插入4.4.1 1）问题描述：有线性表）问题描述：有线性表(a1,a2 ,

35、.(a1,a2 ,.，an)an)，长度为长度为n n，要在第，要在第i-1i-1与第与第i i个元素之间插入一个元素之间插入一个新元素。个新元素。5.5.2 2）插入过程：先将第）插入过程：先将第i i至第至第n n个元素依次向个元素依次向后移动一个位置，然后将新元素插入在第后移动一个位置，然后将新元素插入在第i i个个位置上，线性表的长度变为位置上，线性表的长度变为n+1n+1。NO：36NO：37第二章第二章 常用数据结构及其运算常用数据结构及其运算2.2 2.2 线线 性性 表表3 3）算法描述（顺序表插入）算法描述（顺序表插入）int InsertSList(int L,int n,

36、int i,int x)int InsertSList(int L,int n,int i,int x) /n: /n:表长度表长度 i: i:在位置在位置i i处插入处插入 x: x:插入元素插入元素x x int j; int j; if (in)/ if (in)/插入位置非法插入位置非法 printf(nCant insert!n);printf(nCant insert!n); else else for (j=n-1;j=i;j-) Lj+1=Lj;/for (j=n-1;j=i;j-) Lj+1=Lj;/后移后移Li=x;/Li=x;/插入插入n+;/n+;/表长加表长加1 1

37、return(n);/ return(n);/返回表长返回表长 NO：38第二章第二章 常用数据结构及其运算常用数据结构及其运算2.2 2.2 线线 性性 表表 删除删除1 1）问题描述：有线性表）问题描述：有线性表(a1,a2 ,.(a1,a2 ,.，an)an)，长度为长度为n n，要将第，要将第i i个元素删除。个元素删除。2 2）删除过程：将第）删除过程：将第i+1i+1至第至第n n个元素依次向个元素依次向前移动一个位置，线性表的长度变为前移动一个位置，线性表的长度变为n-1n-1。12. . .0i-1ii+1n-1n1. . . . . . . . . . .NO：39第二章第二

38、章 常用数据结构及其运算常用数据结构及其运算2.2 2.2 线线 性性 表表3 3）算法描述（顺序表删除）算法描述（顺序表删除）int DeleteSList(int L,int n,int i)int DeleteSList(int L,int n,int i) int j; int j; if (in-1) / if (in-1) /删除位置非法删除位置非法printf(nCant delete!n);printf(nCant delete!n); else else for (j=i;j=n-2;j+)for (j=i;jnextq=p-next；pppspsheadpsheadqpsp

39、psq2 2）指针移动：）指针移动：p=p-nextp=p-next；3 3）后插：）后插：s-next=p-nexts-next=p-next；p-next=sp-next=s；4 4）前插：）前插：q=headq=head；while(q-next!=p) q=q-next;while(q-next!=p) q=q-next;q-next=sq-next=s；s-next=ps-next=p；NO：47第二章第二章 常用数据结构及其运算常用数据结构及其运算2.2 2.2 线线 性性 表表 插入运算插入运算1 1）问题描述：在头指针为）问题描述：在头指针为headhead的链表中，的链表中，

40、在值为在值为a a的结点前面插入一个值为的结点前面插入一个值为x x的结点。的结点。若链表为空，则若链表为空，则x x成为其头结点；若表中无成为其头结点；若表中无a a元素，则将元素，则将x x插入链表末尾。插入链表末尾。x xsaHeadHead qq-next=s;q-next=s;s-next=q-next; s-next=q-next; 2 2）算法描述）算法描述NO：48第二章第二章 常用数据结构及其运算常用数据结构及其运算2.2 2.2 线线 性性 表表NODE NODE * *InsertList(NODE InsertList(NODE * *head,int a,int x)

41、head,int a,int x) NODE NODE * *s,s,* *q;q;s=GetListNode(x); if (!s) return(head);s=GetListNode(x); if (!s) return(head);if (head=NULL)/if (head=NULL)/表为空时表为空时 head=s; return(head); head=s; return(head); if (head-data=a)/if (head-data=a)/第一个结点满足第一个结点满足 s-next=head; head=s; return(head); s-next=head;

42、head=s; return(head); q=head;/q=head;/其它情况，进行查找其它情况，进行查找 while (q-next!=NULL & q-next-while (q-next!=NULL & q-next-data!=a)data!=a)q=q-next;q=q-next;s-next=q-next; /s-next=q-next; /插入插入q-next=s;q-next=s;return(head); /return(head); /返回头指针返回头指针 NODE NODE * *GetListNode(int x)GetListNode(int x

43、) NODE NODE * *s;s;s=(NODE s=(NODE * *)malloc(NODESIZE);)malloc(NODESIZE);if (s)if (s) s-data=x; s-next=NULL; s-data=x; s-next=NULL; return(s);return(s); NO：49第二章第二章 常用数据结构及其运算常用数据结构及其运算2.2 2.2 线线 性性 表表 删除运算删除运算1 1）问题描述：在头指针为）问题描述：在头指针为headhead的链表中，的链表中， 将值为将值为a a的结点删除。的结点删除。pp=q-next;p=q-next;q-nex

44、t=p-next;q-next=p-next;free(p);free(p);qheadhead a2 2）算法描述）算法描述NO：50第二章第二章 常用数据结构及其运算常用数据结构及其运算2.2 2.2 线线 性性 表表NODE NODE * *DeleteList(NODE DeleteList(NODE * *head,int a)head,int a) NODE NODE * *p,p,* *q;q;if (head=NULL) return(NULL);if (head=NULL) return(NULL);if (head-data=a) /if (head-data=a) /第一

45、个结点满足第一个结点满足 p=head; head=head-next; free(p); p=head; head=head-next; free(p); return(head); return(head); q=head; /q=head; /其它情况，进行查找其它情况，进行查找 while (q-next!=NULL & q-next-data!=a)while (q-next!=NULL & q-next-data!=a)q=q-next;q=q-next;if (q-next!=NULL);/if (q-next!=NULL);/找到，删除找到，删除 p=q-nex

46、t; q-next=p-next; free(p); p=q-next; q-next=p-next; free(p);return(head); /return(head); /返回头指针返回头指针 NO：51第二章第二章 常用数据结构及其运算常用数据结构及其运算2.2 2.2 线线 性性 表表 具有头结点的线性链表具有头结点的线性链表1 1）如果在链表的第一个结点之前附加一个）如果在链表的第一个结点之前附加一个头结点，该结点的结构和链表中其它结点头结点，该结点的结构和链表中其它结点相同，只是它的数据域中不存放线性表的相同，只是它的数据域中不存放线性表的元素，它的指针域指向线性表的第一个元元

47、素，它的指针域指向线性表的第一个元素。当表空时只有一个头结点，它的指针素。当表空时只有一个头结点，它的指针域为空，如下图：域为空，如下图：headhead（空表）（空表）NO：52第二章第二章 常用数据结构及其运算常用数据结构及其运算2.2 2.2 线线 性性 表表2 2）在线性链表中附加一个头结点后便可以使）在线性链表中附加一个头结点后便可以使算法在形式上得以简化，例如在以上的插入运算法在形式上得以简化，例如在以上的插入运算中，当表空时尚有头结点存在，因此头指针算中，当表空时尚有头结点存在，因此头指针非空，这与表中不存在非空，这与表中不存在a a元素的算法相同，当元素的算法相同，当a a为表

48、中第一个元素时，因有头结点存在，则在为表中第一个元素时，因有头结点存在，则在a a结点之前插入一元素时不必修改头指针。结点之前插入一元素时不必修改头指针。算法可仿照无头结点链表的操作自行写出。算法可仿照无头结点链表的操作自行写出。NO：53第二章第二章 常用数据结构及其运算常用数据结构及其运算2.2 2.2 线线 性性 表表3.3. 线性链表的其它形式线性链表的其它形式4.4. 循环链表循环链表5.5.特点：表中最后一个结点的指针域不为空，特点：表中最后一个结点的指针域不为空，而是指向表头，整个链表形成一个环。与一般而是指向表头，整个链表形成一个环。与一般链表不同之处在于只要给定循环链表中任一

49、结链表不同之处在于只要给定循环链表中任一结点的地址，就可以查遍表中所有的结点，而不点的地址，就可以查遍表中所有的结点，而不必从头指针开始。如下图：必从头指针开始。如下图：结点1结点2结点nNO：54第二章第二章 常用数据结构及其运算常用数据结构及其运算2.2 2.2 线线 性性 表表 双向链表双向链表特点：表中每个结点有两个指针域：一个特点：表中每个结点有两个指针域：一个指向直接后继，一个指向直接前驱，那么指向直接后继，一个指向直接前驱，那么从表中任一结点都可以随意向前或向后查从表中任一结点都可以随意向前或向后查找。但在作插入、删除运算时，需同时修找。但在作插入、删除运算时，需同时修改两个方向

50、上的指针。如下图：改两个方向上的指针。如下图： headNO：55第二章第二章 常用数据结构及其运算常用数据结构及其运算2.2 2.2 线线 性性 表表4.4. 应用实例应用实例一元多项式相加一元多项式相加5.5. 问题描述问题描述6.6.一个一元多项式可以表示为：一个一元多项式可以表示为：nniinxPxPxPPxP.)(10其中每一项由系数其中每一项由系数PiPi及及x x的指数的指数i i组成。若多项组成。若多项式按升幂排列，则它由式按升幂排列，则它由n+1n+1个系数唯一确定，个系数唯一确定，因此可以用一个线性表因此可以用一个线性表P P表示：表示：),.,.,(10niPPPPP其指

51、数其指数i i隐藏在系数隐藏在系数PiPi的序号内。的序号内。NO：56第二章第二章 常用数据结构及其运算常用数据结构及其运算2.2 2.2 线线 性性 表表 问题分析问题分析1 1）存储结构：多项式相加时，常要合并同）存储结构：多项式相加时，常要合并同类项，由此就要改变多项式的系数和指数，类项，由此就要改变多项式的系数和指数，而且在实际问题中，时常会出现多项式的而且在实际问题中，时常会出现多项式的次数很高但又存在大量零系数的项，因此次数很高但又存在大量零系数的项，因此宜采用链式存储结构。宜采用链式存储结构。2 2）结点结构：每一个非零项构成链表中的）结点结构：每一个非零项构成链表中的一个结点

52、，结点由两个数据域和一个指针一个结点，结点由两个数据域和一个指针域构成，如下图：域构成，如下图：coef exp nextpiNO：57第二章第二章 常用数据结构及其运算常用数据结构及其运算2.2 2.2 线线 性性 表表3 3）链表结构：采用带头结点的线性链表表示）链表结构：采用带头结点的线性链表表示多项式多项式A(x)A(x)、B(x)B(x)，相加后结果在线性链表，相加后结果在线性链表C(x)C(x)中。中。4 4）运算过程：设指针）运算过程：设指针haha、hbhb分别为多项式链分别为多项式链表表A(x)A(x)、B(x)B(x)的头指针，指针的头指针，指针p p、q q的初始位置的初

53、始位置分别指向分别指向A(x)A(x)、B(x)B(x)中的第一项。过程为：比中的第一项。过程为：比较较p p、q q所指结点中的指数项。所指结点中的指数项。若：若：p-expexpp-expexp，那么，那么p p所指的结点为所指的结点为C(x)C(x)中的一项，令中的一项，令p p指针后移一个结点；指针后移一个结点；NO：58第二章第二章 常用数据结构及其运算常用数据结构及其运算2.2 2.2 线线 性性 表表若：若：p-expq-expp-expq-exp，则，则q q所指的结点为所指的结点为C(x)C(x)中的一项，将中的一项，将q q结点插入结点插入p p结点之前，并令结点之前，并令

54、q q指指针后移一个结点；针后移一个结点；若若p-exp=q-expp-exp=q-exp，则将两个结点中的系数相，则将两个结点中的系数相加，当和不为零时，修改加，当和不为零时，修改p p结点中的系数，释结点中的系数，释放放q q结点；否则，删去结点；否则，删去p p结点，同时释放结点，同时释放p p、q q结结点。点。这种方法实际上是将这种方法实际上是将B(x)B(x)加到加到A(x)A(x)中，最后形中，最后形成成C(x)C(x)，因此，因此C(x)C(x)中的结点不需要重新生成。中的结点不需要重新生成。 算法描述（一元多项式加法）算法描述（一元多项式加法）NO：59第二章第二章 常用数据

55、结构及其运算常用数据结构及其运算2.2 2.2 线线 性性 表表EXPNODE EXPNODE * *AddPoly(EXPNODE AddPoly(EXPNODE * *ha,EXPNODE ha,EXPNODE * *hb)hb) p=ha-next; q=hb-next; pre=ha; hc=ha; p=ha-next; q=hb-next; pre=ha; hc=ha; while (p!=NULL & q!=NULL) while (p!=NULL & q!=NULL) if (p-expexp) pre=p; p=p-next; if (p-expexp) pre

56、=p; p=p-next; if (p-expq-exp)if (p-expq-exp) u=q-next; q-next=p; pre-next=q; u=q-next; q-next=p; pre-next=q; pre=q; q=u; pre=q; q=u; if (p-exp=q-exp)if (p-exp=q-exp) int x=p-coef+q-coef; int x=p-coef+q-coef; if (x!=0) p-coef=x; pre=p; if (x!=0) p-coef=x; pre=p; else pre-next=p-next; free(p); else pr

57、e-next=p-next; free(p); p=pre-next; u=q; q=q-next; free(u); p=pre-next; u=q; q=q-next; free(u); if (q!=NULL) pre-next=q; if (q!=NULL) pre-next=q; free(hb); return(hc); free(hb); return(hc); NO：60第二章第二章 常用数据结构及其运算常用数据结构及其运算2.2 2.2 线线 性性 表表四、顺序表和链表的比较四、顺序表和链表的比较 顺序表 插入、删除运算时间代价O(n) 预先申请固定长度的数组 如果整个数组元

58、素很满，则没有结构性存储开销 链表 插入、删除运算时间代价O(1) 但找到第i个删除元素运算时间代价O(n) 存储利用指针，动态地按照需要为表中新的元素分配存储 空间 每个元素都有结构性存储开销NO：61第二章第二章 常用数据结构及其运算常用数据结构及其运算2.2 2.2 线线 性性 表表 线性表的长度是否固定线性表的长度是否固定向量的存储空间是静态分配的，执行期间向量的存储空间是静态分配的，执行期间上下界固定，适用于表长固定的场合；链上下界固定，适用于表长固定的场合；链表的存储空间是在执行过程中动态分配的，表的存储空间是在执行过程中动态分配的，适用于表长不固定的场合。适用于表长不固定的场合。

59、 线性表的主要操作是什么线性表的主要操作是什么 向量是连续存放的，适用于频繁查找操作向量是连续存放的，适用于频繁查找操作的表。链表适用于经常进行插入和删除的的表。链表适用于经常进行插入和删除的表。表。 采用的算法语言：链表要求指针类型变量。采用的算法语言：链表要求指针类型变量。NO：62第二章第二章 常用数据结构及其运算常用数据结构及其运算2.2 2.2 线线 性性 表表NO：63第二章第二章 常用数据结构及其运算常用数据结构及其运算2.2 2.2 线线 性性 表表3. 线性表的查找线性表的查找1) 顺序查找法：最简单直观的一种方法，从表的一顺序查找法：最简单直观的一种方法，从表的一端（表头或

60、表尾作为查找起点），向另一个端点端（表头或表尾作为查找起点），向另一个端点（查找终点），逐一检测是否是要查找的结点。（查找终点），逐一检测是否是要查找的结点。 for (i=0; i=0; i-) if( ai = x) return(i);return(-1); 从右到左查找从右到左查找NO：64第二章第二章 常用数据结构及其运算常用数据结构及其运算2.2 2.2 线线 性性 表表 分析：用查找长度（查找时需要检测的结点数目）分析：用查找长度（查找时需要检测的结点数目）描述查找算法的效率。描述查找算法的效率。最大查找长度是表长最大查找长度是表长n，在等概率条件下，平均查，在等概率条件下，平均查找长度是表长的一半，即找长度是表长的一半，即n/2