1、2022年7月28日1 1.1 为什么学习数据结构为什么学习数据结构 1.2 数据结构的有关概念和术语数据结构的有关概念和术语 1.3 算法和算法描述算法和算法描述 1.4 算法的时空效率分析方法算法的时空效率分析方法 1.5 小结与习题小结与习题2022年7月28日2主要介绍课程中常用术语、常用数据结构及用类主要介绍课程中常用术语、常用数据结构及用类C C语语言实现算法描述的一般规则，算法的时间复杂度和言实现算法描述的一般规则，算法的时间复杂度和空间复杂度分析与评价。空间复杂度分析与评价。本章主要内容本章主要内容 通过本章学习，应掌握如下内容：通过本章学习，应掌握如下内容：数据结构中的基本概
2、念及常用术语。数据结构中的基本概念及常用术语。线性结构、树型结构和图型结构等的逻辑特点。线性结构、树型结构和图型结构等的逻辑特点。算法的定义、特性及用类算法的定义、特性及用类C C语言描述算法的规则。语言描述算法的规则。评价算法优劣的标准：时间复杂度、空间复杂度评价算法优劣的标准：时间复杂度、空间复杂度的定义及表示。的定义及表示。2022年7月28日31.1 1.1 为什么要学习数据结构为什么要学习数据结构 研究数据的特性、研究数据的特性、数据间的相互关系及其对应数据间的相互关系及其对应的存储表示，并利用这些特性、关系和存储表示设的存储表示，并利用这些特性、关系和存储表示设计出相应的算法和程序
3、。计出相应的算法和程序。为什么要学习数据结构？为什么要学习数据结构？计算机处理的数据量越来越大；计算机处理的数据量越来越大；数据的类型越来越多；数据的类型越来越多；数据的结构越来越复杂。数据的结构越来越复杂。解决一个问题时几个步骤：抽象出一个适当的数学解决一个问题时几个步骤：抽象出一个适当的数学模型，设计或选择一个解决此类数学模型的算法，模型，设计或选择一个解决此类数学模型的算法，编写程序进行调试、测试，直至得到最终的解答。编写程序进行调试、测试，直至得到最终的解答。2022年7月28日4【例例1-11-1】学生信息检索问题。学生信息包括学号、姓名、性别和成绩等，一行学生信息检索问题。学生信息
4、包括学号、姓名、性别和成绩等，一行为为一个记录一个记录，表示一个学生的信息（也称为一个，表示一个学生的信息（也称为一个数据元素数据元素），一列为一个），一列为一个属性属性。学学 号号姓姓 名名性性 别别成成 绩绩2005060120050601张张 三三男男5185182005060220050602李一宁李一宁女女4964962005060320050603吴吴 磊磊女女581.5581.52005063620050636梁梁 磊磊男男529529线性关系线性关系:对线性表的主要操作有查找、修改、插入和删除等。对线性表的主要操作有查找、修改、插入和删除等。2022年7月28日5【例例1-21
5、-2】某大学专业设置问题。显然这种关系用某大学专业设置问题。显然这种关系用“树树”型结构来表示更形象。通型结构来表示更形象。通常用来表示结点的分层组织，结点之间是常用来表示结点的分层组织，结点之间是一对多的关系一对多的关系。对树型结构主要操作有查。对树型结构主要操作有查找、修改、插入和删除等。找、修改、插入和删除等。*大学大学机械工程系机械工程系电子工程系电子工程系计算机与信息工程计算机与信息工程系系机械机械制造制造材料材料科学科学电子电子应用应用电气自电气自动化动化计算机应计算机应用与维护用与维护计算机应计算机应用与维护用与维护2022年7月28日6【例例1-31-3】通信网络问题。带圆圈的
6、顶点表示城市，通信网络问题。带圆圈的顶点表示城市，顶点和顶点之间的连线和数据表示城市之间的通信线顶点和顶点之间的连线和数据表示城市之间的通信线路及其长度。，各顶点之间是多对多的关系，是路及其长度。，各顶点之间是多对多的关系，是网网状状结构，也称为结构，也称为图型图型结构，操作有：求从一个顶点到另结构，操作有：求从一个顶点到另一个顶点的最短路径等。一个顶点的最短路径等。由以上三个例子可见，由以上三个例子可见，描述这类非数值计算问描述这类非数值计算问题的数学模型有题的数学模型有线性表、线性表、树、图树、图等。所有的计算等。所有的计算机系统软件和应用软件机系统软件和应用软件都要用到各种类型的数都要用
7、到各种类型的数据结构。据结构。B CDFEA604540423040806532262022年7月28日71.2 1.2 数据结构的有关概念和术语数据结构的有关概念和术语 1.2.1 基本概念和术语基本概念和术语1数据（数据（Data）是描述客观事物的数值、字符以及所有能被输入到计算机并能被是描述客观事物的数值、字符以及所有能被输入到计算机并能被计算机识别、存储和处理的符号的集合。客观事物包括数值数据和非数值数据。计算机识别、存储和处理的符号的集合。客观事物包括数值数据和非数值数据。数值数据：整数、实数或复数；非数值数据：字符、文字、图形、图像和声音等。数值数据：整数、实数或复数；非数值数据：
8、字符、文字、图形、图像和声音等。2数据元素（数据元素（Data Element）是数据的基本单位。在不同的条件下，数据元素又是数据的基本单位。在不同的条件下，数据元素又可称为可称为元素、结点、顶点、记录元素、结点、顶点、记录等。等。数据项：数据项：数据结构中讨论的最小单位。一个数据元素可由若干个数据项（数据结构中讨论的最小单位。一个数据元素可由若干个数据项（Data Item）组成。例如，学生信息表的每一个数据元素就是一个学生记录，它包括学）组成。例如，学生信息表的每一个数据元素就是一个学生记录，它包括学生的学号、姓名、性别、成绩等数据项。生的学号、姓名、性别、成绩等数据项。2022年7月28
9、日83数据对象（数据对象（Data Object）是具有是具有相同性质数据元素相同性质数据元素的集合。的集合。4数据类型数据类型(Data Type)在用高级语言编写的程序中，每个变量、常量或表达在用高级语言编写的程序中，每个变量、常量或表达式都有一个它所属的确定的数据类型。式都有一个它所属的确定的数据类型。5抽象数据类型抽象数据类型（Abstract Data Type，简称，简称ADT）是指基于逻辑关系的数据类）是指基于逻辑关系的数据类型以及定义在该类型之上的一组操作。型以及定义在该类型之上的一组操作。ADT 抽象数据类型名抽象数据类型名 数据对象：（数据对象的定义）数据对象：（数据对象的
10、定义）数据关系：（数据关系的定义）数据关系：（数据关系的定义）基本操作：（基本操作的定义）基本操作：（基本操作的定义）2022年7月28日9【例例1-4】线性表的抽象数据类型可描述如下：线性表的抽象数据类型可描述如下：ADT Linear_list 数据元素数据元素 所有所有ai属于同一数据对象，属于同一数据对象，i=1，2，n （n1）逻辑结构逻辑结构 所有数据元素所有数据元素ai存在次序关系（存在次序关系（ai，ai+1），），a1无前驱，无前驱，an无后继。无后继。操作操作 /*设设L为为Linear_list类型的线性表类型的线性表*/InitList（L）；）；/*建立一个空的线性表
11、建立一个空的线性表L*/Length（L）；）；/*求线性表求线性表L的长度的长度*/GetElement（L，i）；）；/*取线性表取线性表L中的第中的第i个元素个元素*/Locate（L，x）；）；/*确定元素确定元素x在线性表在线性表L中的位置中的位置*/Insert（L，i，x）；）；/*在线性表在线性表L中的第中的第i个位置处插入数据元素个位置处插入数据元素x*/Delete（L，i）；）；/*删除表删除表L中第中第i个位置的元素个位置的元素*/；/*ADT Linear_list */2022年7月28日101.2.2 数据结构定义数据结构定义数据结构数据结构（Data Struc
12、ture）是指互相之间存在着一种或多种关系的数据元素的）是指互相之间存在着一种或多种关系的数据元素的集合。数据元素之间的关系称为结构。数据的结构包括逻辑结构和物理结构。集合。数据元素之间的关系称为结构。数据的结构包括逻辑结构和物理结构。（1）逻辑结构：）逻辑结构：是数据元素之间的相互逻辑关系，它与数据的存储无关，是独是数据元素之间的相互逻辑关系，它与数据的存储无关，是独立于计算机而存在。立于计算机而存在。数据结构是由两个集合构成的一个二元组：数据结构是由两个集合构成的一个二元组：Data_Structure(D，R)Data_Structure是一种数据结构，它由同属一个数据对象的数据元素的有
13、限集合是一种数据结构，它由同属一个数据对象的数据元素的有限集合D和和D上二元关系的有限集合上二元关系的有限集合R组成。其中：组成。其中：D=di|1in,n1R=rj|1jm,m12022年7月28日11di表示第表示第i个数据元素，个数据元素，rj表示第表示第j个关系。个关系。D上二元关系上二元关系R是序偶的集合。对于是序偶的集合。对于R中的任一序偶中的任一序偶(x,yD)，x称为序偶的称为序偶的第一元素，第一元素，y称为序偶的第二元素，又称序偶的第一元素是第二元素的直接前驱；称为序偶的第二元素，又称序偶的第一元素是第二元素的直接前驱；第二元素为第一个元素的直接后继。第二元素为第一个元素的直
14、接后继。【例例1-5】树型结构中的圆圈代表数据元素，树型结构中的圆圈代表数据元素，带箭头的连线表示元素之间的关系，试用二带箭头的连线表示元素之间的关系，试用二元组表示法表示其逻辑结构。元组表示法表示其逻辑结构。解：二元组为解：二元组为(D,R)其中，其中，D=A,B,C,E,F,G,H,I,J;R=,ABCEFGHIJ2022年7月28日12通常有下列四种基本的结构：通常有下列四种基本的结构：a.a.集合结构集合结构。集合是元素关系极为松散的一种结构。集合是元素关系极为松散的一种结构。b.b.线性结构线性结构。线性结构的逻辑特征是：若结构是非空集，则有且仅有一个开始结。线性结构的逻辑特征是：若
15、结构是非空集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前驱和一个直接后继。点和一个终端结点，并且所有结点都最多只有一个直接前驱和一个直接后继。c.c.树型结构树型结构。该结构的数据元素之间存在着一对多的关系。该结构的数据元素之间存在着一对多的关系。d.d.图型结构图型结构。该结构的数据元素之间存在着多对多的关系，图型结构也称作网状。该结构的数据元素之间存在着多对多的关系，图型结构也称作网状结构。结构。（2 2）物理结构（或存储结构）物理结构（或存储结构）是数据结构在计算机中的表示（又称映像），它是数据结构在计算机中的表示（又称映像），它包括数据元素的机内表示和关系的
16、机内表示。具体实现的方法有顺序、链接、索包括数据元素的机内表示和关系的机内表示。具体实现的方法有顺序、链接、索引、散列等多种，数据的具体操作与存储结构有很密切的联系。引、散列等多种，数据的具体操作与存储结构有很密切的联系。数据结构作为一门学科主要研究数据的各种数据结构作为一门学科主要研究数据的各种逻辑结构逻辑结构和和存储结构存储结构，以及对数据，以及对数据的的各种操作各种操作。同时还要考虑执行算法时的。同时还要考虑执行算法时的时间和空间效率时间和空间效率。2022年7月28日131.3 1.3 算法和算法描述算法和算法描述 有穷性有穷性。一个算法必须在有穷步之后结束，即必须在有限时间内完成。一
17、个算法必须在有穷步之后结束，即必须在有限时间内完成。确定性确定性。算法的每一步必须有确切的定义，无二义性。算法的每一步必须有确切的定义，无二义性。可行性可行性。算法中的每一步都可以通过已经实现的基本运算的有限次执行得以实。算法中的每一步都可以通过已经实现的基本运算的有限次执行得以实现。现。输入输入。一个算法具有零个或多个输入，这些输入取自特定的数据对象集合。一个算法具有零个或多个输入，这些输入取自特定的数据对象集合。输出输出。一个算法具有一个或多个输出，这些输出同输入之间存在某种特定的关。一个算法具有一个或多个输出，这些输出同输入之间存在某种特定的关系。系。1.3.1 算法与算法特性算法与算法
18、特性算法算法（Algorithm）是对特定问题求解步骤的一种描述，是指令的有限序列。一个）是对特定问题求解步骤的一种描述，是指令的有限序列。一个算法应该具有下列特性：算法应该具有下列特性：2022年7月28日14一个好的算法通常要达到以下的要求：一个好的算法通常要达到以下的要求：v正确正确。执行结果应当满足预先规定的功能和性能要求。执行结果应当满足预先规定的功能和性能要求。v可读可读。应当思路清晰、层次分明、简单明了、易读易懂。应当思路清晰、层次分明、简单明了、易读易懂。v健壮健壮。当输入不合法数据时，应能作适当处理，不至引起严重后果。当输入不合法数据时，应能作适当处理，不至引起严重后果。v高
19、效高效。有效使用存储空间和有较高的时间效率。有效使用存储空间和有较高的时间效率。1.3.2 算法描述最简单的方法是使用自然语言，其优点是简单且便于人们对算法的阅读；缺点是转最简单的方法是使用自然语言，其优点是简单且便于人们对算法的阅读；缺点是转换成高级语言困难。换成高级语言困难。类类C C语言语言忽略高级程序设计语言中一些严格的语法规则与描述细节，因此它比程序忽略高级程序设计语言中一些严格的语法规则与描述细节，因此它比程序设计语言更容易描述和被人理解，比自然语言更接近程序设计语言，很容易被转换设计语言更容易描述和被人理解，比自然语言更接近程序设计语言，很容易被转换成高级语言。成高级语言。202
20、2年7月28日15本书对所用类本书对所用类C语言作如下约定：语言作如下约定：1问题的规模用问题的规模用MAXSIZE#define MAXSIZE 602预定义常量和类型：预定义常量和类型：#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW -1typedef int Status;3数据结构（存储结构）的表示用类型定义（数据结构（存储结构）的表示用类型定义（typedef）描述。数据元素类型约定）描述。数据元素类型约定为为 ElemType，由用户在使用该数据类型时自行定义。，由用户在使用该数据类型
21、时自行定义。例例1.学生信息检索系统中，用一维数组作存学生信息检索系统中，用一维数组作存储储 n 个学生的信息，数组中的数据元素有个学生的信息，数组中的数据元素有4个域：学号、姓名、性别和成绩：个域：学号、姓名、性别和成绩：typedef struct std_info long int Num;/*学号域学号域*/char Name8;/*姓名域姓名域*/char Sex;/*性别域性别域*/float Score;/*成绩域成绩域*/ElemType;2022年7月28日164基本操作的算法都用以下形式的函数描述基本操作的算法都用以下形式的函数描述函数类型函数类型 函数名函数名(函数参数表
22、函数参数表)/*算法说明算法说明*/语句序列；语句序列；/*函数名函数名*/5C语言中的常用语句语言中的常用语句赋值（赋值（=）、选择（）、选择（if、if else、switch case default）、循环（）、循环（for、while、do while）、结束（）、结束（return、break、continue、exit）、输入和输出等语句。）、输入和输出等语句。6基本运算和基本函数基本运算和基本函数基本运算有基本运算有+、-、*、/、%、-、&和和|等。等。基本函数有基本函数有max、min、abs、fabs、eof 等。等。2022年7月28日17 例设某班级有例设某班级有n个
23、学生，编写算法，查找班级中成绩最高的学生，并输出该学个学生，编写算法，查找班级中成绩最高的学生，并输出该学生的所有信息。生的所有信息。分析：，算法依次查看数组中的元素，并保存当前最高成绩及其下标。使用类分析：，算法依次查看数组中的元素，并保存当前最高成绩及其下标。使用类C语语言编写：言编写：int largest（ElemType SMAXSIZE，int n）float currlarge=0.0;int i,j=0;/*赋初值赋初值*/for（i=0;i currlarge)j=i;currlarge=Si.Score;printf(“%10ld%10s%10c%10fn”,Sj.Num,
24、Sj.name,Sj.Sex,Sj.Score);/*largest*/typedef struct std_info long int Num;char Name8;char Sex;float Score;ElemType;2022年7月28日181.4 1.4 算法时空效率分析方法算法时空效率分析方法评价算法的性能用时间复杂度与空间复杂度来度量。评价算法的性能用时间复杂度与空间复杂度来度量。1、算法的时间复杂度、算法的时间复杂度算法的时间复杂度（算法的时间复杂度（Time complexity）是指算法转换为程序后）是指算法转换为程序后(这里仍称为算法这里仍称为算法)在计算机上从开始运行
25、到结束所需要的时间。运行所需要的时间取决于下列因素：在计算机上从开始运行到结束所需要的时间。运行所需要的时间取决于下列因素：硬件的速度。硬件的速度。与硬件的配置高低有关。与硬件的配置高低有关。书写程序的语言。书写程序的语言。语言的级别越高，其执行效率就越低。语言的级别越高，其执行效率就越低。编译程序所生成目标代码的质量编译程序所生成目标代码的质量。依据依据算法所选用的策略算法所选用的策略。问题的规模问题的规模。一般情况下，处理的数据量越大，执行的时间相对也越长。一般情况下，处理的数据量越大，执行的时间相对也越长。2022年7月28日19通常的做法是：不考虑不确定的情况，而以算法中简单操作重复执
26、行的次数作为算通常的做法是：不考虑不确定的情况，而以算法中简单操作重复执行的次数作为算法的时间度量。为此，一个特定算法的运行时间长短就只依赖于法的时间度量。为此，一个特定算法的运行时间长短就只依赖于问题的规模问题的规模n，或或者说它是问题规模者说它是问题规模n的函数的函数f(n)。【例例1-7】求累加求和求累加求和int sum(int b，int n）int sum=0;/*第第1条定义并赋初值语句执行条定义并赋初值语句执行1次次*/for（int i=0；in；i+）/*3n+2 次次*/sum+=bi;/*n次次 */return sum;/*返回语句执行返回语句执行1次次 */2022
27、年7月28日20要精确地计算要精确地计算f(n)是困难的，引入渐进时间复杂度在数量上估计一个算法的执行时是困难的，引入渐进时间复杂度在数量上估计一个算法的执行时间。算法时间的度量记作间。算法时间的度量记作T(n)=(f(n)它表示随问题的规模它表示随问题的规模n的增大，算法执行时间的增长率和的增大，算法执行时间的增长率和f(n)相同。使用大相同。使用大记号，记号，(f(n)称为算法的渐进时间复杂度（称为算法的渐进时间复杂度（Asymptotic Time Complexity），简称时间复），简称时间复杂度。杂度。例如，一个程序的实际执行时间为例如，一个程序的实际执行时间为 T(n)2.7n3
28、+3.8n2+5.3。则。则T(n)(n3)。2022年7月28日21【例例1-8】求下面程序段的时间复杂度。求下面程序段的时间复杂度。s=0;for(j=1;j=n;j+)for(x=1,k=1;k=n;k+)x=x*k;s+=x;解：该算法中解：该算法中“s=0;”的频度为的频度为1，后面由两个，后面由两个“for”语句构成了一个二重循环结语句构成了一个二重循环结构，其内循环体执行的频度为构，其内循环体执行的频度为n2，用最高数量级，用最高数量级n2的表示，则该程序段的时间复的表示，则该程序段的时间复杂度为杂度为O(n2)。通常将称通常将称(1)为为常数阶常数阶，(n)为为线性阶线性阶，O
29、(n2)为为平方阶平方阶。算法还可能呈现的复。算法还可能呈现的复杂度有：对数阶杂度有：对数阶(log2n)，指数阶，指数阶(2n)等，不同数量级时间复杂度的关系有：等，不同数量级时间复杂度的关系有：(1)(log2n)(n)(nlog2n)(n2)(n3)(2n)2022年7月28日220 1 2 4 8 16 32 64 128 256 nT(n)102451225612864321684210 1 2 4 8 16 32 64 128 256 512 1024 nnlog2n2nn2n3nlog2n图图1-7 常见函数的增长率常见函数的增长率2022年7月28日232、算法的空间复杂度、算
30、法的空间复杂度一个程序的空间复杂度（一个程序的空间复杂度（Space complexity）是指程序运行从开始到结束所需的）是指程序运行从开始到结束所需的最大存储空间。最大存储空间。包括以下三部分：包括以下三部分：（1）输入数据所占空间；）输入数据所占空间；（2）程序本身所占空间；）程序本身所占空间；（3）辅助变量所占空间辅助变量所占空间。只需要分析辅助变量所占空间即可。通常以算法的空间复杂度作为算法所占用存只需要分析辅助变量所占空间即可。通常以算法的空间复杂度作为算法所占用存储空间的量度。定义：储空间的量度。定义：S(n)=O(g(n)2022年7月28日24小小 结结术语：术语：数据（数据
31、（Data）、数据元素（数据元素（Data Element）、）、数据项、数据项、数据对象、数数据对象、数据类型等据类型等 线性结构、树型结构和图型结构等的逻辑特点。线性结构、树型结构和图型结构等的逻辑特点。算法的定义、特性及用类算法的定义、特性及用类C C语言描述算法的规则。语言描述算法的规则。评价算法优劣的标准：时间复杂度、空间复杂度评价算法优劣的标准：时间复杂度、空间复杂度的定义及表示。的定义及表示。2022年7月28日星期四第25页 2.1 2.2 2.3 2.4 2022年7月28日星期四第26页本章学习目标 线性表线性表是最简单、最基本、最常用的一种数据结构是最简单、最基本、最常用
32、的一种数据结构 通过本章学习，应掌握如下内容：通过本章学习，应掌握如下内容：线性表的概念及表示方法线性表的概念及表示方法 线性表的线性表的两种两种存储方式：存储方式：顺序存储顺序存储和和链式存储链式存储 线性表的基本运算及其实现算法线性表的基本运算及其实现算法 线性表的典型应用线性表的典型应用2022年7月28日星期四第27页 例例2 2:奇数序列奇数序列 (1,3,5,7,9,11)(1,3,5,7,9,11)例例1 1:字母序列字母序列 (A,B,C,D,E,F)A,B,C,D,E,F)例例3 3：随机的学生成绩序列：随机的学生成绩序列2.1 线性表的逻辑结构 2.1.1 线性表的定义线性
33、表的定义 问题的引入学学 号号姓姓 名名性性 别别成成 绩绩20050601张张 三三男男51820050602李一宁李一宁女女49620050603吴吴 磊磊女女581.520050636梁梁 磊磊男男5292022年7月28日星期四第28页3.3.举例：举例：A=(,)该线性表的长度为该线性表的长度为 5 5B=(a1,a2,a3,，am)该线性表的长度为该线性表的长度为 m mC=(b1,b2,b3,，bn)该线性表的长度为该线性表的长度为 n n1.1.定义：具有定义：具有相同类型相同类型的的 n n 个个数据元素组成的数据元素组成的有限序列有限序列。记为记为 (a1，a2，ai-1，
34、ai，ai+1，an)其中其中n n为表长，当为表长，当n=0 n=0 时称为空表。时称为空表。关键点关键点:(1)(1)相同类型相同类型(2)(2)线性表的长度线性表的长度 n (n0)n (n0)(3)(3)有限序列有限序列2022年7月28日星期四第29页1.1.线性表的长度线性表的长度线性表中所包含的元素个数线性表中所包含的元素个数 n(n0)n(n0)；2.2.空线性表空线性表线性表的长度线性表的长度 n=0 n=0；3.3.（直接）前驱和后继直接）前驱和后继在相邻元素中，在相邻元素中，a ai i 是是a ai+1i+1的前驱（第一个元素的前驱（第一个元素 a a1 1无前驱）无前
35、驱）在相邻元素中，在相邻元素中，a ai+1i+1是是a ai i的后继（最后一个元素的后继（最后一个元素a an n无后继）无后继）4.4.举例：举例：长度为长度为1010的奇数序列的奇数序列 (1,3,5,7,9,11,13,15,17,19)线性表可以看作是除线性表可以看作是除第一个元素第一个元素无前驱，无前驱，最后一个元素最后一个元素无后继外，其余元素都有无后继外，其余元素都有唯一的直接前驱和直接后继的一组元素构成的有序集合。唯一的直接前驱和直接后继的一组元素构成的有序集合。2022年7月28日星期四第30页 通常将通常将 ai的数据类型抽象为的数据类型抽象为ElemType。例如，学
36、生信息表例如，学生信息表中数据元素可以定义为一个结构类型：中数据元素可以定义为一个结构类型：typedef struct std_info long int Num;/*学号域学号域 */char Name8;/*姓名域姓名域*/char Sex;/*性别域性别域*/float Score;/*成绩域成绩域*/ElemType;学学 号号姓姓 名名性性 别别成成 绩绩20050601张张 三三男男51820050602李一宁李一宁女女49620050603吴吴 磊磊女女581.520050636梁梁 磊磊男男5292022年7月28日星期四第31页2.1.2 线性表的基本操作 线性表初始化线性
37、表初始化：Init_List(L)；建立一个空的线性表；建立一个空的线性表；求线性表的长度求线性表的长度：Length_List(L)；返回线性表中数据元素的个数。返回线性表中数据元素的个数。取表中元素取表中元素：Get_Elem(L,i)；返回线性表返回线性表L中第个数据元素的值或地址。中第个数据元素的值或地址。按值查找按值查找：Locate_List(L,x)；在表在表L中查找值为的数据元素的位置。中查找值为的数据元素的位置。插入操作插入操作：Insert_List(L,i,x)；在线性表在线性表L的第的第i个位置上个位置上插入一个值为插入一个值为x的数据元素。的数据元素。删除操作删除操作
38、：Delete_List(L,i)；在线性表在线性表L中删除序号为中删除序号为 i 的数据元素的数据元素。2022年7月28日星期四第32页ADT List ADT List 数据对象数据对象：D=ai|ai ELEMTP i=1,2,n ,n 0 数据关系数据关系：R=|ai,ai+1 D i=1,2,n-1 ,n 0 基本操作基本操作：InitList（&L）：）：线性表的初始化；线性表的初始化；ListLength（L）：求线性表的长度；求线性表的长度；ListInsert（&L,i,e）：）：在第在第 i i 个位置插入元素个位置插入元素 e e；ListDelete（&L,i,e）：
39、）：在线性表第在线性表第 i i 个位置删除元素个位置删除元素 e；2022年7月28日星期四第33页2.2 线性表的顺序存储结构及运算实现2.2.1 顺序表顺序表 是指在内存中用一块地址连续的是指在内存中用一块地址连续的存储空间按顺序存储线性表存储空间按顺序存储线性表的各个数据元素。的各个数据元素。特点特点：采用连续的空间来存储线：采用连续的空间来存储线性表性表顺序表顺序表。顺序存储结构可描述如下：顺序存储结构可描述如下：typedef struct ElemType elemMAXSIZE;int length;/*线性表长度线性表长度 */SeqList;data数组下标数组下标a1a2
40、ai-1aiai+1an12i-1ii+1length.MAXSIZE-1bb+db+(i-1)db+(length-1)d存储地址存储地址2022年7月28日星期四第34页线性表的线性表的长度长度及元素在线性表中的及元素在线性表中的位置位置 已知该线性表的首地址已知该线性表的首地址(a a1 1)为，那么任意一个元素的地址为为，那么任意一个元素的地址为:ai(i-1)d （其中其中d d为该类型元素所占空间）为该类型元素所占空间）定义一个顺序表：定义一个顺序表：SeqList SeqList *L L；顺序表的长度为顺序表的长度为L-length;L-length;数据元素是数据元素是L-d
41、ata1L-data1L-dataL-L-dataL-lengthlength。因为在因为在 C C语言中数组的下标是从语言中数组的下标是从0 0开始的，开始的，为了与线性表中元素的序号保持一致，不使为了与线性表中元素的序号保持一致，不使用数组下标为用数组下标为“0 0”的单元，下标的取值范的单元，下标的取值范围围11iMAXSIZE-1iMAXSIZE-1。data数组下标数组下标a1a2ai-1aiai+1an12i-1ii+1length.MAXSIZE-1bb+db+(i-1)db+(length-1)d存储地址存储地址2022年7月28日星期四第35页 (1)将将anai 按从后向前
42、的顺序向下按从后向前的顺序向下移动，为新元素让出位置；移动，为新元素让出位置；(2)将将x置入空出的第置入空出的第i个位置；个位置；(3)修改修改length值。值。Length+1 8560785590782.2.2 顺序表上基本运算的实现 1顺序表的初始化顺序表的初始化-构造一个空表构造一个空表 void init_SeqList(SeqList*L)L-length=0;L-length=0;2.2.插入运算插入运算 a1a2 ai-1aiai+1ana1aai-1 x aiai+1an 1 2 i-1 i i+1 nn+12022年7月28日星期四第36页【算法【算法2.2】在顺序表的
43、第】在顺序表的第i个位置上插入一个值为个位置上插入一个值为x的新元素。的新元素。int Insert_SeqList(SeqList*L，int i，ElemType x)int j;if(L-length=MAXSIZE-1)printf(表满表满);return OVERFLOW;if(iL-length+1)/*检查插位置的正确性检查插位置的正确性*/printf(位置错位置错);return ERROR ;for(j=L-length;j=i;j-)L-elemj+1=L-elemj;L-elemi=x;L-length+;return OK;/*插入成功，返回插入成功，返回*/202
44、2年7月28日星期四第37页8660787555909055786086例如：插入元素75，插入位置为4，则90和55两个元素应向后移。算法说明算法说明：在线性表中，按照某顺序查找与其：在线性表中，按照某顺序查找与其给定一致的元素是否存在，如果存在返回其位给定一致的元素是否存在，如果存在返回其位置，否则给出相关信息。置，否则给出相关信息。i的取值范围为的取值范围为：1in+1即有即有n1个位置可以插入。个位置可以插入。2022年7月28日星期四第38页11)1(Eniiininp插入算法的时间性能分析：插入算法的时间性能分析：在第在第i个位置上插入个位置上插入 x，从从 ai 到到 an 都要
45、向下移动一个位置，共需要移动都要向下移动一个位置，共需要移动 ni1个个元素，而元素，而 i 的取值范围为的取值范围为：1=i=n+1，即有即有 n1个位置可以插入。设在第个位置可以插入。设在第i个位置上作插入的概率为个位置上作插入的概率为Pi，则则平均移动数据元素的次数：平均移动数据元素的次数：设：设：Pi=1/(n+1)，即为等概率情况，则：即为等概率情况，则：11112)1(11)1(Eniniiinninninp这说明：在顺序表上做插入操作需移动表中一半的数据元素。显然时间复杂度为这说明：在顺序表上做插入操作需移动表中一半的数据元素。显然时间复杂度为(n)。2022年7月28日星期四第
46、39页3.删除运算 删除第删除第i i个元素，个元素，i i 的取值范围为：的取值范围为：11inin。运算的步运算的步骤为：先将骤为：先将a ai+1i+1a an n 依次向上移动，然后将依次向上移动，然后将length length 值减值减1 1。a1a2 ai-1aiai+1ana1aai-1ai+1an 1 2 i-1 i i+1n-1 nn+1删除算法删除算法int Delete_SeqList(SeqList*L,int i)int j;if(iL-length)printf(不存在第不存在第i个元素个元素);return ERROR ;for(j=i;jlength-1;j+
47、)L-elemj=L-elemj+1;L-length-;return OK;2022年7月28日星期四第40页9055786086例如：删除元素75，则90和55两个元素应向前移。86605590删除第删除第i个元素时，其后面的元素个元素时，其后面的元素 ai+1an 都要向上移动一个位置，共移动了都要向上移动一个位置，共移动了 n-i 个个元素，所以平均移动数据元素的次数：元素，所以平均移动数据元素的次数：niideinp1)(E在等概率情况下，在等概率情况下，pi=1/n，则：则：11121)(1)(Eniniideninninp这说明顺序表上作删除运算时大约需要这说明顺序表上作删除运算
48、时大约需要移动表中一半的元素，显然该算法的时移动表中一半的元素，显然该算法的时间复杂度为间复杂度为 (n)。2022年7月28日星期四第41页4按值查找【算法【算法2.42.4】在线性表中查找与给定值】在线性表中查找与给定值x x相等的数据元素。相等的数据元素。int Location_SeqList(SeqList*L,ElemType x)int i=1;while(ilength&L-elemi!=x)i+;if(iL-length)return-1;/*查找失败查找失败*/else return i;/*返回返回x的存储位置的存储位置*/时间复杂度分析：当时间复杂度分析：当 a a1
49、1=x x 时，只比较一次；当时，只比较一次；当 a an n=x x 时需时需要比较要比较 n n 次；平均比较次数为（次；平均比较次数为（n+1n+1）/2/2，所以时间复杂度为所以时间复杂度为O(n)O(n)，即时间复杂度与表长有关。即时间复杂度与表长有关。2022年7月28日星期四第42页【例2-3】有两个顺序表 A 和 B，其元素均按从小到大的升序排列，编写一个算法将它们合并成一个顺序表 C，要求 C 的元素也是从小到大排列。算法的时间复杂度是O(m+n)，void merge(SeqList*A,SeqList*B,SeqList*C)int i,j,k;i=1;j=1;k=1;w
50、hile(ilength&jlength)if(A-elemielemj)C-elemk+=A-elemi+;else C-elemk+=B-elemj+;while(ilength)C-elemk+=A-lengthi+;while(jlength)C-elemk+=B-elemj+;C-length=A-length+B-length;2022年7月28日星期四第43页2.3 线性表的链式存储和运算实现 问题的引入：问题的引入：1.1.顺序存储结构必须在程序编译前就顺序存储结构必须在程序编译前就规定规定好数组元素的多少好数组元素的多少(即数组长度即数组长度)，事先难估计，多了造成浪费存储空
