全套电子课件：数据结构(C语言版).ppt

1、第第1 1章章 绪论绪论教学要求 建议学时：2学时 总体要求 了解数据结构的意义，数据结构在计算机领域的地位和作用；掌握数据结构各名词、术语的含义和有关的基本概念；数据的逻辑结构和存储结构之间的关系；了解使用C语言对数据结构进行抽象数据类型的表示和实现的方法；了解算法的五要素；掌握计算语句频度估算算法时间复杂度的方法。教学要求 相关知识点 相关术语：数据、数据元素、数据项、数据对象、数据结构 数据逻辑结构：集合、线性结构、树和图 数据的物理结构：顺序和非顺序结构 算法的五要素和时间复杂度及空间复杂度 学习重点 数据的逻辑结构和存储结构及其之间的关系 算法时间复杂度及空间复杂度及其计算 目录目录

2、常用术语和基本概念常用术语和基本概念数据类型数据类型 算法和算法分析算法和算法分析 3 3数据结构概述数据结构概述1 12 24 4本章小结本章小结 5 51.1 1.1 数据结构数据结构概述概述数据结构概述 数据结构与算法 数据结构(Data Structure)+算法(Algorithm)=程序(Program)计算机算法与数据结构密切相关，算法都依附于具体的数据结构，数据结构直接关系到算法的选择和效率。一般来说，用计算机来解决一个具体问题时，大致需要经过以下几个步骤：首先，要从具体问题中抽象出一个适当的数学模型，然后设计一个解此数学模型的算法(Algorithm)，最后编写程序、进行测试

3、，调试和运行直到得到最终解答。讲授常用的算法，程序员也可以直接拿来或经过少许的修改就可以使用，并且可以通过算法训练来提高程序设计水平。数据结构概述 数据结构的意义 寻求数学模型的实质是分析问题，从中提取操作的对象，并找出这些操作对象之间含有的关系，然后用数学的语言加以描述。当人们用计算机处理数值计算问题时，所用的数学模型是用数学方程描述的。因此程序设计者的主要精力集中于程序设计技巧上，而不是数据的存储和组织上。然而，计算机应用的更多领域是“非数值型计算问题”，它们的数学模型无法用数学方程描述，而是用数据结构描述，解决此类问题的关键是设计出合适的数据结构，非数值型问题的数学模型是用线性表、树、图

4、等结构来描述的。数据结构概述 数据结构的意义 数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系的操作的学科。数据结构是一门介于数学、计算机硬件和计算机软件三者之间的计算机专业核心课程。在计算机科学中，数据结构不仅是一般程序设计的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序和大型应用程序的重要基础。数据结构概述 【例1.1】学生信息登记表 每年新生入学都会用如下类似的二维表进行信息登记，以便完成各种数据的统计，比如，统计男生和女生的比例、生源籍贯等。二维表(即线性表)是经常用到的数学模型。学号学号姓名姓名性别性别民族民族籍贯籍贯出生日期出生日期

5、20170108001苏宏苏宏男男汉族汉族南宁市南宁市1999012120170108002梁琪梁琪女女汉族汉族贵港市贵港市1999091320170108003韦华韦华男男壮族壮族崇左市崇左市1998081520170108004覃婷覃婷女女汉族汉族南宁市南宁市19981203数据结构概述 【例1.2】酒店管理系统中的客房分配问题。在酒店的客房分配管理中，希望同类房中各间客房的入住机会均等，以保证维持一个平均的磨损率。为此，分配客房的算法应该是“先退的客房先被启用”。相应地，所有“空”的同类客房的管理模型应该是一个“队列”，即酒店前台每次接待客人入住时，从“队头”分配客房；当客人结账离开时，

6、应将退掉的空客房排在“队尾”，如图1.1所示。队列是经常用到的一种数学模型。数据结构概述 【例1.3】人机对弈问题。计算机操作对象是可能出现的格局，而格局之间的关系是由比赛规则决定的。从对弈开始到结束的过程中所有可能出现的格局会构成一棵倒立生长的“树”。数据结构概述 综合以上3个例子可见，描述这类非数值计算问题的数学模型不再是数学方程，而是诸如二维表、队列和树之类的数据结构。因此，简单来说，在非数值计算的程序设计问题中，数据结构是一门研究计算机的操作对象及其相互之间的关系和运算等的学科。1.2 1.2 常用术语常用术语和基本概念和基本概念常用术语和基本概念 数据(Data)计算机程序处理各种各

7、样的数据，可以是数值数据，如整数、实数或复数；也可以是非数值数据，如字符、文字、图形、图像、声音等。数据元素(Data Element)和数据项(Data Item)数据元素是数据的基本单位，在计算机程序中通常被作为一个整体进行考虑和处理。数据元素有时也被称为元素、结点、顶点、记录等。一个数据元素可由若干个数据项(Data Item)组成。数据项是不可分割的、含有独立意义的最小数据单位，数据项有时也称为字段(Field)或域(Domain)。数据对象(Data Object)数据对象是性质相同的数据元素的集合，是数据的一个子集。例如，整数数据对象是0,1,2,3,，字符数据对象是a,b,c,。

8、常用术语和基本概念 数据结构(Data Structure)数据结构是相互之间存在一种或多种特定关系的数据元素的集合。数据结构由相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成。数据结构的形式化定义记为：Data_Structure=(D,R)。其中，D是数据元素的有限集合，R是数据集合D中所有元素之间的关系的有限集合。常用术语和基本概念 数据的逻辑结构(Logic Structure)数据的逻辑结构是从具体问题抽象出来的数学模型，与数据在计算机中的具体存储没有关系。数据的逻辑结构独立于计算机，是数据本身所固有的特性。从逻辑上可以把数据结构分为线性结构和非线性结构，

9、主要包括：集合、线性、树和图形结构，其中集合、树和图形结构都属于非线性结构。常用术语和基本概念 数据的逻辑结构(Logic Structure)根据数据元素之间关系的不同特性，通常有4类基本数据结构：(1)集合(Set)：该结构中的数据元素除了存在“同属于一个集合”的关系外，不存在任何其它关系。(2)线性结构(Linear Structure)：该结构中的数据元素存在着一对一的关系。(3)树形结构(Tree Structure)：该结构中的数据元素存在着一对多的关系。(4)图状结构(Graphic Structure)：该结构中的数据元素存在着多对多的关系。常用术语和基本概念 数据结构(Dat

10、a Structure)常用术语和基本概念 数据结构(Data Structure)【例1.4】定义集合D=3,6,9,18,27的数据结构。DS1=(D,R1)，其中R1定义为D上的“”(大于)关系，则数据结构DS1为线性结构。DS2=(D,R2)，其中R2定义为D上的“整除”关系，则R2=(3,6),(3,9),(3,18),(3,27),(6,18),(9,18),(9,27)，数据结构DS2为图状结构。常用术语和基本概念 数据的物理结构(Physical Structure)。数据的物理结构又称为存储结构(Storage Structure)，是数据在计算机中的表示（又叫映像）和存储，

11、包括数据元素的表示和存储以及数据元素之间关系的表示和存储。存储结构是逻辑结构在计算机存贮器中的映像，必须依赖于计算机。数据元素之间的关系在计算机中的表示方法主要有两种：顺序映像和非顺序映像。分别对应两种数据的存储结构包括顺序存储结构和链式存储结构两种。常用术语和基本概念 数据的物理结构(Physical Structure)。顺序存储结构(Sequence Storage Structure)是通过数据元素在计算机存储器中的相对位置来表示出数据元素的逻辑关系，一般把逻辑上相邻的数据元素存储在物理位置相邻的存储单元中。链式存储结构(Linked Storage Structure)对逻辑上相邻的

12、数据元素不要求其存储位置必须相邻。链式存储结构中的数据元素称为结点(Node)，在结点中附设地址域(Address Domain)来存储与该结点相邻的结点的地址来实现结点间的逻辑关系。常用术语和基本概念 数据的运算 算法的设计取决于数据的逻辑结构，而算法的实现依赖于数据采用的存储结构。数据的存储结构实质上是它的逻辑结构在计算机存储器中的实现，为了全面地反映一个数据的逻辑结构，它在存储器中的映象包括两方面的内容，即数据元素之间的信息和数据元素之间的关系。不同的数据结构有其相应的若干运算。数据的运算是在数据的逻辑结构上定义的操作算法，如检索、插入、删除、更新和排序等。1.3 1.3 数据类型数据类

13、型数据类型 数据类型 数据类型(Data Type)是高级程序设计语言中的概念，是数据的取值范围和对数据进行操作的总和。数据类型规定了程序中对象的特性。程序中的每个变量、常量或表达式的结果都应该属于某种确定的数据类型。数据类型就是一个值的集合和定义在这个值集上的一组操作的总称。例如，C语言中的基本整数类型(signed int)，它的值集是-3276832767，在这个值集上能进行的操作有加、减、乘、除和取余数等，而在实数类型(float)上就不能进行取余数操作。按值的不同特性，数据类型又可分为不可分解的原子类型及可分解的结构类型。数据类型 抽象数据类型 1.抽象的数据类型 抽象的数据类型(A

14、bstract Data Type，ADT)是指基于一类逻辑关系的数据类型以及定义在这个类型上的一组操作。在软件设计中，抽象数据类型通常包含元素、关系和操作三部分。所以，一般而言，抽象数据类型可用以下三元组表示：ADT_Type=(D,R,P)其中，D是数据元素有限集，即数据对象，R是D上的关系集，P是对D的基本操作集。数据类型 抽象数据类型 2.抽象数据类型定义的一般形式ADT抽象数据类型名数据对象：数据关系：基本操作：ADT抽象数据类型名数据类型 抽象数据类型 3.本书在用C语言描述时的约定(1)C语言的数组元素的下标从“0”开始，为此，在表示数据结构时，数据元素的序号也从0开始。(2)数

15、据元素的类型约定为ElemType。具体的类型可以由用户在使用时定义：typedef int ElemType /*定义数据类型为int*/(3)数据存储结构用类型定义(typedef)描述，如：typedef structElemType*elem;int length;int listsize;SqList;/*定义名为SqList的线性表采用顺序存储结构的类型定义*/数据类型 抽象数据类型 3.本书在用C语言描述时的约定(4)算法以函数形式描述：类型标识符 函数名(形参表)/*算法说明*/语句通过以上定义可以看出，抽象数据类型只是数学的抽象，在ADT的定义中根本没有涉及如何实现操作的集合

16、。对于每个ADT并不存在什么法则来说明必须要有哪些操作，这只是一个设计决策。数据类型 抽象数据类型 4.抽象数据类型可以细分为3种类型(1)原子类型：其值是不可分的。(2)固定聚合类型：其值由确定数目的成分按某种结构组成。(3)可变聚合类型：其值由不确定数目的成分构成。一个抽象数据类型的软件模块通常包含定义、存储和实现这3个部分。1.4 1.4 算法和算算法和算法复杂度法复杂度 算法和算法复杂度 概念 算法（Algorithm）是指在有限的时间范围内，为解决某一问题而采取的方法和步骤的准确完整的描述，它是一个有穷的规则序列，这些规则决定了解决某一特定问题的一系列运算。算法是程序设计的精髓，算法

17、的设计取决于数据的逻辑结构，算法的实现取决于数据的物理结构。算法数据结构程序 算法应该具备以下特征：1有穷性2确定性3可行性4有输入5有输出算法和算法复杂度 算法效率的度量1.正确性(Correctness)：满足预先规定的功能和性能的要求2.可读性(Readability)：一个算法应当思路清晰、层次分明、简单明了、易读易懂。3.健壮性(Robustness)：一个算法应该具有很强的容错能力，当输入不合法的数据时，算法应当能做适当的处理，使得不至于引起严重的后果。4.高效率：运行时间(Running Time)是指算法在计算机上运行所花费的时间，它等于算法中每条语句执行时间的总和。一般来说，

18、执行时间越短，性能越好。5.低存储：占用空间(Storage Space)是指算法在计算机上存储所占用的存储空间，包括存储算法本身所占用的存储空间、算法的输入及输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间。算法和算法复杂度 时间复杂度（Time Complexity）1.时间复杂度的定义 一个程序的运行时间是指程序从开始到结束所需要的时间。通常，用n 作为表示问题规模的量。我们把规模为n 的算法的执行时间，称为时间复杂度T(n)。通常把算法中基本操作重复执行的次数（频度）作为算法的时间复杂度:T(n)=f(n)“渐进时间复杂度”，即当n 逐渐增大时 的极限情况。一般把这种算法的

19、渐进复杂度简称为时间复杂度。为了便于分析，时间复杂性常用数量级的形式来表示，T(n)=O(f(n).其中大写字母 为Order（数量级）的第一个字母，为f(n)函数形式，如:T(n)=O(n2)。一般用数量级的形式表示T(n)，当T(n)为多项式时，可只取其最高次幂，且其系数也可省略。算法和算法复杂度 时间复杂度（Time Complexity）2.度量一个程序执行时间的两种方法(1)事后统计法这种统计方法依据算法所编写的程序在计算机上运行时所消耗的时间。但是，同一个程序在不同类型的机器上运行所需的时间不一定相同，所以这种统计是片面的。(2)事先估计法根据每条指令的执行时间来估算依据算法编写的

20、程序在计算机上运行时所消耗的时间。但是，因为每种类型机器的指令集不同，执行的时间也不尽相同，所以这种方法也离不开具体的机器软硬件环境和设备。算法和算法复杂度 时间复杂度（Time Complexity）3.时间复杂度的计算方法【例1.5】分析下列语句的时间复杂度时间复杂度s=0;for(i=1;i=n;i+)s=s+i;分析：s=0;执行1次i=1;执行1次i=n;执行n+1次s=s+i;执行n次i+;执行n次总的执行次数为3(n+1)次，因此，该算法的时间复杂度为T(n)=O(3(n+1)=O(n)。算法和算法复杂度 时间复杂度（Time Complexity）4.时间复杂度的时间量级 O(

21、1)：常数阶。基本操作执行次数为常数。O(n)：线性阶 O(n2)：平方阶 O(nk)：K方阶 O(en)：指数阶 O(log2n)：对数阶 O(nlog2n)：线性对数阶（复合阶）算法和算法复杂度 常见函数的时间复杂度增长率 一般地，对于足够大的 n，常用的时间复杂性存在如下顺序：)!(.)3()2(.)()()log()()(log)1(32nOOOnOnOnnOnOnOOnn算法和算法复杂度 空间复杂度（Space Complexity）1.空间复杂的定义 空间是指执行算法所需要的存储空间 算法所对应程序运行所需存储空间包括固定部分和可变部分。固定部分所占空间与所处数据结构外理数据的大小

22、和数量无关，或者称与该问题的实例的特征无关。主要包括程序代码、常量、简单变量等所占的空间；可变部分所占空间与该算法在某次执行中处理的特定数据的大小和规模有关。例如100 个数据元素的排序算法与1000 个数据元素的排序算法所需的存储空间显然是不同的。与算法的时间复杂度类似，可以空间复杂度作为算法所需存储空间的量度，记为：S(n)=O(f(n).算法和算法复杂度 空间复杂度（Space Complexity）2.空间复杂的计算方法 依据算法所编写的程序除了需要存储空间来寄存程序本身所用的指令、常数、变量和输入数据外，也需要一些对数据进行操作的工作单元和存储一些为实现计算所需信息的辅助空间。通常，

23、程序所占空间变化不大，所以在此主要考虑算法的辅助空间需求。【例1.6】分析下面程序的时间复杂度和空间复杂度。RevArray(int a,int n)int i,j,*b;b=(int*)malloc(sizeof(int)*n);for(i=0,j=n-1;in;i+,j-)bj=ai;for(i=j=0;in;i+,j+)ai=bi;free(b);算法和算法复杂度 空间复杂度（Space Complexity）2.空间复杂的计算方法【例1.6】分析下面程序的时间复杂度和空间复杂度。算法空间复杂度的分析：因为基本语句就是循环内的赋值语句，共执行了2n次，所以T(n)=2n=O(n)。而算法

24、的辅助空间是一个与问题规模同量级的一维数组空间，另再加上两个控制变量i和j，共n+2个，所以S(n)=n+2=O(n)。1.5 1.5 本章小结本章小结本章小结 数据结构的基本概念和术语 数据、数据元素、数据项、数据结构等基本概念 数据结构的逻辑结构、存储结构及数据运算的含义及其相互关系 数据结构的两大逻辑结构和两种常用的存储表示方法 算法的描述和分析 算法、算法的时间复杂度和空间复杂度的概念 算法描述和算法分析的方法，对于一般算法能分析出时间复杂度第第2 2章章 线性表线性表教学要求 建议学时：8学时 总体要求 掌握线性表的逻辑结构及两种不同的存储结构；掌握线性表两类存储结构（顺序和链式存储

25、结构）的存储方法；掌握线性表在顺序存储结构及链式存储结构上实现基本操作（查找、插入、删除等）的算法及分析；对于链式存储结构，掌握单链表、循环链表、双向链表的区别及联系；能够针对具体应用问题的要求和性质，选择合适的存储结构设计出有效算法，解决与线性表相关的实际问题。教学要求 相关知识点 相关概念：线性表、顺序表、链表（单链表、循环链表、双向链表）、头指针、头结点 顺序表的存储及基本操作 链表的存储及基本操作 学习重点 线性表的逻辑结构及两种不同的存储结构 顺序表的存储和实现 链表的存储和实现 目录目录线性表的顺序存储及运算的实现线性表的顺序存储及运算的实现线性表的链式存储及运算的实现线性表的链式

26、存储及运算的实现 3 3线性表概述线性表概述1 12 2本章小结本章小结4 42.1 线性表概述线性表概述 线性表的定义及特点 1.线性表的定义 线性表(Linear_List)简称为表，是n(n0)个数据元素(也叫节点或表元素)组成的有限序列，其特点是各数据元素之间存在着线性关系，即都是一个接一个地按一定顺序排列的，并且线性表要求同一个表中的各数据元素的结构类型必须完全一致。通常将线性表记作：(a0，a1，a2，a3，ai-1，ai，ai+1，an-1)即表中ai-1领先于ai，称ai-1是ai的直接前驱元素，ai+1是ai的直接后续元素。当i=0，1，2，3，n-2时，ai有且仅有一个直接

27、后继；当i=1，2，3，4，n-1时，ai有且仅有一个直接前驱。线性表概述 线性表的定义及特点 1.线性表的定义 线性表中元素的个数n(n0)定义为线性表的长度，特别地，当n=0时称该线性表为空表。非空线性表中的每一个数据元素都有一个确定的位置，如a0是最前面一个数据元素，an-1是最后面一个数据元素，ai是第i(0in-1)个数据元素，称i为数据元素在线性表中的位序。线性表概述 线性表的定义及特点 2.线性表的特点 通过定义可以得到线性表有如下特点：(1)唯一首元素；(2)唯一尾元素；(3)除首元素外，任何元素都有一个前驱；(4)除尾元素外，任何元素都有一个后继；(5)每个元素有一个位序。线

28、性表概述 线性表的抽象数据类型 ADT List数据对象：D=ai|aiElemSet，i=0，1，2，n-1，n0数据关系：R=|ai-1，aiD，i=0，1，2，n-1基本操作：(1)线性表初始化：InitList(*L)需要条件：线性表L没有被创建过。操作结果：创建一个空的线性表L。(2)求线性表的长度：ListLength(L)需要条件：表L已经被创建。操作结果：返回线性表L所含数据元素的个数。线性表概述 线性表的抽象数据类型(3)取表中的某一个元素：GetElem(L,i,*e)需要条件：线性表L已经被创建，且0iLength(L)-1。操作结果：返回线性表L中的第i个元素的值。(4

29、)按值查找：LocateElem(L,e,compare()需要条件：线性表L已经被创建。操作结果：在线性表L中查找值为e的数据元素，返回在L中首次出现值为e的数据元素的位置编号；如果线性表L中不存在值等于e的数据元素，则存储查找失败，返回-1。线性表概述 线性表的抽象数据类型(5)插入操作：Insert(*L,i,e)需要条件：线性表L已经被创建，插入位置i满(0in，其中n=Length(L)。操作结果：在线性表L的第i个位置插入一个值为e的新元素，同时原来序号为i，i+1，n-1的数据元素向后移动，其序号变为i+1，i+2，n，新线性表的表长度为原表长+1。线性表概述 线性表的抽象数据类

30、型(6)删除操作：ListDelete(*L,i,*e)需要条件：线性表L已经被创建，且0in-1，其中n=Length(L)。操作结果：在线性表L中删除序号为i的数据元素，同时原来序号为i+1，i+2，n-1的数据元素向前移动，其序号变为i，i+1，n-2，新线性表的表长度为原表长-1。线性表概述 线性表的抽象数据类型(7)求直接前驱操作：PriorElem(L,cur_e,*pre_e)需要条件：线性表L已经被创建，cur_e,*pre_e与线性表数据元素同结构。操作结果：若cur_e不是最前面的一个元素，则用*pre_e返回它的直接前驱，否则返回-1，存储操作失败。线性表概述 线性表的抽

31、象数据类型(8)求直接后继操作：NextElem(L,cur_e,*next_e)需要条件：线性表L已经被创建，cur_e,*next_e与线性表数据元素同结构。操作结果：若cur_e不是最后面的一个元素，则用*next_e返回它的直接后继，否则返回-1，存储操作失败。2.2 线性表的顺序存储及运算的实现线性表的顺序存储及运算的实现 线性表的顺序存储 1.线性表的顺序存储原理 线性表的顺序存储(Sequential Mapping，简称顺序表)，是指用一组地址连续的存储单元按线性表元素之间的逻辑顺序，依次存储线性表的数据元素。数据元素的逻辑顺序和物理上的存储顺序是完全一致的，物理上存放在位置i

32、的元素，就是按照逻辑顺序存储时的第i个元素。因此在顺序存储结构下不需要另外建立空间来记录各个元素之间的关系。顺序存储的线性表是一种随机存取结构，因为只要确定了存储线性表的起始位置，就可以随机存取表中的任何一个数据元素。由于C语言的一维数组在内存中所占的正是一个地址连续的存储区域，因此可以用C语言的一维数组来作为线性表的顺序存储结构。线性表的顺序存储及运算的实现 线性表的顺序存储 2.顺序存储的线性表抽象数据类型的定义#define INIT_SIZE 100 /*线性表存储空间的初始分配量*/#define INCREMENT 10 /*线性表存储空间的分配增量*/typedef int El

33、emType;/*定义元素类型为int*/typedef struct ElemType*elem;/*存储空间的基地址*/int length;/*当前长度*/int listsize;/*当前分配的存储容量(以sizeof(ElemType)为单位)*/SqList;线性表的顺序存储及运算的实现 线性表的顺序存储 2.顺序存储的线性表抽象数据类型的定义 元素元素位序位序0in-1listsize-1存储存储地址地址LOC(a0)LOC(a0)+i*LLOC(a0)+(n-1)*LLOC(a0)+(listsize-1)*L元素元素表示表示L.elem0L.elemiL.elemL.leng

34、th-1L.elemL.listsize-1内存内存状态状态a0aian-1线性表的顺序存储及运算的实现 线性表的顺序存储 2.顺序存储的线性表抽象数据类型的定义 其中，设LOC(a0)为线性表的首地址，L为数据元素长度，L.leni的值即为线性表中的第i个数据元素；该顺序表最多可容纳listsize个数据元素；ElemType为线性表中数据元素的所属类型。由上可知，在顺序表中，任一数据元素的存放位置是从起始位置开始的、与该数据元素的位序成正比的对应存储位置，可以借助上述存储地址计算公式确定。因此，可以根据顺序表中数据元素的位序，随机访问表中的任一元素，也就是说，顺序表是一种随机存取的存储结构

35、。线性表的顺序存储及运算的实现 顺序表的基本操作 1.顺序表的初始化 算法2.1 顺序表的初始化int InitList_Sq(SqList*L)/*初始化顺序表，成功返回1，失败返回0*/L-elem=(ElemType*)malloc(INIT_SIZE*sizeof(ElemType);if(!L-elem)return 0;/*初始化失败*/L-length=0;L-listsize=INIT_SIZE;return 1;/*初始化成功*/线性表的顺序存储及运算的实现 顺序表的基本操作 2.顺序表的插入 线性表的插入操作是指在表的第i-1个元素和第i个元素之间插入一个新的元素e，插入新

36、元素后原表长为n的表a0，a1，a2，a3，ai-1，ai，ai+1，an-1变为表长为n+1的新表a0，a1，a2，a3，ai-1，e，ai，ai+1，an-1。其中需要注意的是i的取值范围0in，即当i=n时，表示在整个顺序表的末尾插入一个元素e。线性表的顺序存储及运算的实现 顺序表的基本操作 2.顺序表的插入(1)插入操作需要注意的问题 顺序表中数据区域分配有listsize个存储单元，在进行插入操作时需要先检查表空间是否已满，表满的情况下不能再进行插入操作，否则会产生内存溢出错误。要检查插入位置的有效性，这里i的有效范围是0in，其中n为原表长度。注意数据移动的方向为向大的下标移动（从

37、后开始向后移动）线性表的顺序存储及运算的实现 顺序表的基本操作 2.顺序表的插入(2)算法思路一般情况下，在第i(1in)个元素之前插入一个元素时，需将第n-1至第i(共n-i)个元素向后移动一个位置。从后开始向后移动：将an-1ai顺序向后移动一个位置，即an-1移动到an的位置，an-2移动到an-1的位置，ai移动到ai+1的位置，为待插入的新数据元素让出位置i。将e放到空出的第i个位置上。修改length指针，使之恒指向顺序表中的最后一个元素。线性表的顺序存储及运算的实现 顺序表的基本操作 2.顺序表的插入(3)算法2.2 顺序表的插入int ListInsert_Sq(SqList*

38、L,int i,ElemType e)/*在顺序表L的第i个位置之前插入新的元素e，若插入成功则返回1，否则返回0*/int j;ElemType*newbase;if(iL-length)return 0;/*插入位置不合法，插入失败*/if(L-length=L-listsize)/*当前存储空间已满，增加分配*/线性表的顺序存储及运算的实现 顺序表的基本操作 2.顺序表的插入(3)算法2.2 顺序表的插入 newbase=(ElemType*)realloc(L-elem,(L-listsize+INCREMENT)*sizeof(ElemType);if(!newbase)return

39、 0;/*存储分配失败，插入失败*/L-elem=newbase;L-listsize+=INCREMENT;线性表的顺序存储及运算的实现 顺序表的基本操作 2.顺序表的插入(3)算法2.2 顺序表的插入for(j=L-length-1;j=i;j-)L-elemj+1=L-elemj;/*插入位置及之后的元素从后开始向后移动*/L-elemi=e;/*插入e*/+L-length;/*表长增1*/return 1;/*插入成功*/线性表的顺序存储及运算的实现 顺序表的基本操作 2.顺序表的插入 (4)插入操作的时间复杂度在顺序表上进行插入操作时，其时间主要消耗在插入位置之后的若干数据元素的移

40、动上。要在第i个位置插入元素e，则从ai到an都要向后移动一个位置，共需要移动(n-i)个元素。可见在顺序表中插入一个数据元素平均需要移动表中一半的数据元素，其时间复杂度为O(n)。n0iiini)(nPE2n21)n(n*1n1i)(n1n1i)(nPEn0in0iiin线性表的顺序存储及运算的实现 顺序表的基本操作 3.顺序表的删除 线性表的删除操作是指将表中的第i个元素从线性表中删除的过程，删除第i个元素后原表长为n的线性表(a0，a1，a2，a3，ai-1，ai，ai+1，an-1)变为表长为n-1的新表(a0，a1，a2，a3，ai-1，ai+1，an-1)。其中需要注意的是i的有效

41、范围为0in-1。(1)删除操作需要注意的问题 删除第i个元素时，要删除的元素必须真实存在，所以需要检查i的取值是否有效，i的有效取值范围为0in-1，否则操作失败。表为空表时不能执行删除操作。注意数据移动的方向为向小的下标移动（从前开始向前移动）线性表的顺序存储及运算的实现 顺序表的基本操作 3.顺序表的删除(2)算法思路 从前开始向前移动：将ai+1an-1顺序向前移动一个位置。修改length指针，使之仍指向当前表中的最后一个元素。线性表的顺序存储及运算的实现 顺序表的基本操作 3.顺序表的删除(3)算法2.3 顺序表的删除int ListDelete_Sq(SqList*L,int i

42、,ElemType*e)int j;if(iL-length-1)return 0 *e=L-elemi;/*将被删除元素的值赋给e*/for(j=i+1;jlength-1;j+)L-elemj-1=L-elemj;-L-length;return 1;/*删除成功*/线性表的顺序存储及运算的实现 顺序表的基本操作 3.顺序表的删除(4)删除操作的时间复杂度在顺序表上进行删除操作时，其时间也同样主要消耗在删除元素之后的其他数据元素的移位上，要删除第i个元素，其后面的元素ai+1an-1都要向前移动一个位置，共移动了(n-i-1)个元素，平均移动数据元素的次数为由此可见，在顺序表上删除一个数据

43、元素平均需要移动表中一半的数据元素，故该算法的时间复杂度为O(n)。1n0iide1)i(nPE21n21)n(n*n11)i(nn11)i(nPE1n0i1n0iide线性表的顺序存储及运算的实现 顺序表的基本操作 4.顺序表的按值查找 顺序表的按值查找是指在顺序表L中查找是否存在与给定值e相等的数据元素。可将e和L中的数据元素逐个比较。(1)算法思路从最前面一个元素a0开始向后依次将顺序表中的元素ai与e相比较，直到找到一个与e相等的数据元素，返回这个数据元素在表中的位置；若顺序表中的所有元素都与e不相等，即查找不到与e相等的数据元素，则返回-1，表示查找失败，如算法2.4所示。也可以从最

44、后一个元素an-1开始向前依次将顺序表中的元素ai与e相比较，直到找到一个与e相等的数据元素，返回这个数据元素在表中的位置；若顺序表中的所有元素都与e不相等，即查找不到与e相等的数据元素，则返回-1，表示查找失败。线性表的顺序存储及运算的实现 顺序表的基本操作 4.顺序表的按值查找(2)算法2.4 顺序表的按值查找int LocateElem_Sq(SqList L,ElemType e)/*在顺序线性表L中查找第1个值与e相等的元素的位序，若找到，则返回其在L中的位序，否则返回-1*/int i=0;/*i的初值为最前面一个元素的位序*/while(iL.length&L.elemi!=e)

45、i+;/*从前向后逐一比较*/if(L.elemi=e)return i;/*查找成功，i为与e相等的第一个元素的位序*/else return-1;/*查找失败*/线性表的顺序存储及运算的实现 顺序表的基本操作 4.顺序表的按值查找(3)顺序表按值查找的时间复杂度算法2.4的时间主要耗费在e与ai的比较上，而比较的次数既与e在表中的位置有关，也与表长有关。设查找成功的最好情况是当a0=e时，比较一次就成功；最坏的情况是当an-1=e时，需要比较n次才成功。平均比较次数为(n+1)/2，故该算法的时间复杂度为O(n)。线性表的顺序存储及运算的实现 顺序表的基本操作 5.取顺序表中的元素 取表中

46、元素是指根据所给的序号i在顺序表中查找相应数据元素的过程。(1)算法思路首先确认所查找的数据元素序号是否合法，若合法则直接返回对应的元素值，否则操作失败。线性表的顺序存储及运算的实现 顺序表的基本操作 5.取顺序表中的元素(2)算法2.5 取顺序表中元素int Get_SqList(SqList L,int i,ElemType*e)/*在顺序线性表L中取第i个元素存入e中，若成功，则返回1，否则返回0*/if(iL.length-1)return 0；/*没有第i个元素,读取失败*/*e=L.elemi;return 1;/*读取成功*/线性表的顺序存储及运算的实现 顺序表的基本操作 5.取

47、顺序表中的元素(3)取顺序表中元素的时间复杂度顺序表是随机存储结构，具有按数据元素的序号随机存取的特点，所以计算任意元素的存储地址的时间是相等的，与数据元素所在位置无关，因此算法2.5的时间复杂度为O(1)。线性表的顺序存储及运算的实现 顺序表的基本操作 6.顺序表的应用 【例2-1】有顺序表LA和LB，其元素均按从小到大的升序排列，编写一个算法将它们合并成一个顺序表LC，要求LC的元素也是从小到大的升序排列。算法思路：依次扫描LA和LB的元素，比较线性表LA和LB当前元素的值，将较小值的元素赋给LC，如此直到一个线性表扫描完毕，然后将未完的那个顺序表中余下部分赋给LC即可。因此线性表LC的容

48、量应不小于线性表LA和LB长度之和。算法描述如下：线性表的顺序存储及运算的实现int MergeList_Sq(SqList LA,SqList LB,SqList*LC)/*已知顺序线性表LA和LB的元素按值非递减排列，归并LA和LB得到新的顺序线性表LC，LC的元素也按值非递减排列，成功返回1，失败返回0*/int i=0,j=0,k=0;LC-listsize=LA.length+LB.length;LC-elem=(ElemType*)malloc(LC-listsize*sizeof(ElemType);if(!LC-elem)return 0;while(iLA.length&jL

49、B.length)if(LA.elemielemk+=LA.elemi+;else LC-elemk+=LB.elemj+;while(ielemk+=LA.elemi+;while(jelemk+=LB.elemj+;LC-length=k;return 1;线性表的顺序存储及运算的实现 顺序表的基本操作 6.顺序表的应用 本算法的基本操作为“元素赋值”，算法的时间复杂度为 。).(lengthLBlengthLAO2.3 线性表的链式存储及运算的实现线性表的链式存储及运算的实现 单链表 1.单链表存储原理 线性表的链式存储结构是用一组任意的存储单元来存放线性表的数据元素，这组存储单元可以是

50、连续的，也可以是不连续的。那么，对于某一元素，如何找到它的下一个元素的存放位置呢？因此，对每个数据元素ai，除了存储其本身的信息之外，还需存储一个指示其直接后继存放位置的指针。这两部分信息组成数据元素ai的存储映像，称为结点（node）。如图2.4所示，它包括两个域：其中存储数据元素信息的域称为数据域data；存储直接后继存放位置的域称为指针域next。图图2.4 单链表结点结构单链表结点结构 线性表的链式存储及运算的实现 单链表 1.单链表存储原理 这样n个元素的线性表通过每个结点的指针域链接成一个链表。又由于此链表的每个结点中只有一个指向后继的指针，所以称其为单链表或线性链表。其中，头指针