数据结构ppt课件完整版.pptx

《数据结构ppt课件完整版.pptx》由会员分享，可在线阅读，更多相关《数据结构ppt课件完整版.pptx（304页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构数据结构&什么是数据结构什么是数据结构&重要性及学习意义重要性及学习意义&课程特点及学习方法课程特点及学习方法&参考资料参考资料序：课程介绍序：课程介绍1、数据结构数据结构是程序设计的重要组成部分是程序设计的重要组成部分用计算机解决问题的步骤：用计算机解决问题的步骤：用计算机解决问题的步骤：用计算机解决问题的步骤：从具体问题中抽象出一个适当的从具体问题中抽象出一个适当的从具体问题中抽象出一个适当的从具体问题中抽象出一个适当的数学模型数学模型数学模型数学模型。设计一个适合该数学模型的算法。设计一个适合该数学模型的算法。设计一个适合该数学模型的算法。设计一个适合该数学模型的算法。编写程序。

2、编写程序。编写程序。编写程序。进行测试、调整、修改，直至解决问题进行测试、调整、修改，直至解决问题进行测试、调整、修改，直至解决问题进行测试、调整、修改，直至解决问题。瑞士计算机科学家瑞士计算机科学家瑞士计算机科学家瑞士计算机科学家N.writhN.writh提出：提出：提出：提出：程序设计程序设计程序设计程序设计=算法算法算法算法+数据结构数据结构数据结构数据结构&什么是数据结构什么是数据结构2 2、数据结构的主要内容、数据结构的主要内容、数据结构的主要内容、数据结构的主要内容计算机科学发展的早期主要用来做科学计算，处理一计算机科学发展的早期主要用来做科学计算，处理一计算机科学发展的早期主要

3、用来做科学计算，处理一计算机科学发展的早期主要用来做科学计算，处理一些些些些数值计算数值计算数值计算数值计算问题，这类问题的数学模型为问题，这类问题的数学模型为问题，这类问题的数学模型为问题，这类问题的数学模型为数学方程，数学方程，数学方程，数学方程，但是但是但是但是随其发展，已经不局限于此。随其发展，已经不局限于此。随其发展，已经不局限于此。随其发展，已经不局限于此。例例例例11电话号码簿的查询问题电话号码簿的查询问题电话号码簿的查询问题电话号码簿的查询问题李李李李王王王王&什么是数据结构什么是数据结构例例例例2 2 学生信息检索学生信息检索学生信息检索学生信息检索河南商专河南商专河南商专河

4、南商专计算机系计算机系计算机系计算机系软件软件软件软件20102010级级级级20092009级级级级计算机应用计算机应用计算机应用计算机应用会计系会计系会计系会计系&什么是数据结构什么是数据结构例例例例3 3 交通图的查找交通图的查找交通图的查找交通图的查找3 3、数据结构的定义、数据结构的定义、数据结构的定义、数据结构的定义数据结构数据结构数据结构数据结构是一门研究非数值计算的程序设计问题中计是一门研究非数值计算的程序设计问题中计是一门研究非数值计算的程序设计问题中计是一门研究非数值计算的程序设计问题中计算机的操作对象以及他们之间的关系和操作的学科。是数算机的操作对象以及他们之间的关系和操

5、作的学科。是数算机的操作对象以及他们之间的关系和操作的学科。是数算机的操作对象以及他们之间的关系和操作的学科。是数据的据的据的据的组织组织组织组织、存储存储存储存储和和和和运算运算运算运算的总和。的总和。的总和。的总和。逻辑结构：逻辑结构：逻辑结构：逻辑结构：指数据元素之间的逻辑关系，是从具体问指数据元素之间的逻辑关系，是从具体问指数据元素之间的逻辑关系，是从具体问指数据元素之间的逻辑关系，是从具体问题中抽象出来的数学模型，独立于计算机。题中抽象出来的数学模型，独立于计算机。题中抽象出来的数学模型，独立于计算机。题中抽象出来的数学模型，独立于计算机。存储结构：存储结构：存储结构：存储结构：指数

6、据元素之间的逻辑关系在计算机中的指数据元素之间的逻辑关系在计算机中的指数据元素之间的逻辑关系在计算机中的指数据元素之间的逻辑关系在计算机中的表示，又称物理结构。表示，又称物理结构。表示，又称物理结构。表示，又称物理结构。运算操作：运算操作：运算操作：运算操作：查询，插入，删除查询，插入，删除查询，插入，删除查询，插入，删除&什么是数据结构什么是数据结构FF计算机专业的计算机专业的计算机专业的计算机专业的核心课程之一核心课程之一核心课程之一核心课程之一FF是程序设计及软件开发的重要基础是程序设计及软件开发的重要基础是程序设计及软件开发的重要基础是程序设计及软件开发的重要基础FF各类计算机考试、专

7、升本各类计算机考试、专升本各类计算机考试、专升本各类计算机考试、专升本的主要内容的主要内容的主要内容的主要内容FF学习它，有助于形成计算机处理问题的意识：存储、学习它，有助于形成计算机处理问题的意识：存储、学习它，有助于形成计算机处理问题的意识：存储、学习它，有助于形成计算机处理问题的意识：存储、输入、处理、输出输入、处理、输出输入、处理、输出输入、处理、输出FF具有复杂问题的解决能力具有复杂问题的解决能力具有复杂问题的解决能力具有复杂问题的解决能力&重要性及学习意义重要性及学习意义课程特点：课程特点：课程特点：课程特点：理论性强，难度较大理论性强，难度较大理论性强，难度较大理论性强，难度较大

8、学习方法：学习方法：学习方法：学习方法：FF理解课堂内容理解课堂内容理解课堂内容理解课堂内容：认真听、做笔记：认真听、做笔记：认真听、做笔记：认真听、做笔记FF勤于习题演练勤于习题演练勤于习题演练勤于习题演练：强调代码要独立写：强调代码要独立写：强调代码要独立写：强调代码要独立写FF加强上机实践加强上机实践加强上机实践加强上机实践：阶段性调试算法：阶段性调试算法：阶段性调试算法：阶段性调试算法FF养成独立思考问题、解决问题的习惯养成独立思考问题、解决问题的习惯养成独立思考问题、解决问题的习惯养成独立思考问题、解决问题的习惯&课程特点及学习方法课程特点及学习方法FF严尉敏、吴伟民：严尉敏、吴伟民

9、：严尉敏、吴伟民：严尉敏、吴伟民：数据结构数据结构数据结构数据结构，清华大学出版社，清华大学出版社，清华大学出版社，清华大学出版社FF严尉敏、吴伟民：严尉敏、吴伟民：严尉敏、吴伟民：严尉敏、吴伟民：数据结构习题集数据结构习题集数据结构习题集数据结构习题集，清华大学出，清华大学出，清华大学出，清华大学出版社版社版社版社FF徐士良：徐士良：徐士良：徐士良：实用数据实用数据实用数据实用数据，清华大学出版社，清华大学出版社，清华大学出版社，清华大学出版社FF李春葆：李春葆：李春葆：李春葆：数据结构习题与解析数据结构习题与解析数据结构习题与解析数据结构习题与解析，清华大学出版社，清华大学出版社，清华大学

10、出版社，清华大学出版社&参考资料参考资料主要内容主要内容 1.1.数据结构课程的性质和地位数据结构课程的性质和地位 2.2.基本概念和术语基本概念和术语 3.3.算法及算法分析算法及算法分析 重点、难点重点、难点 基本概念及术语，算法评价的方法基本概念及术语，算法评价的方法第第1章章数据结构概述数据结构概述数据数据数据数据(Data):(Data):(Data):(Data):是对信息的一种符号表示。在计算机科学是对信息的一种符号表示。在计算机科学是对信息的一种符号表示。在计算机科学是对信息的一种符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的中是指所有能输入到计算机中并被

11、计算机程序处理的中是指所有能输入到计算机中并被计算机程序处理的中是指所有能输入到计算机中并被计算机程序处理的符号的总称。符号的总称。符号的总称。符号的总称。数据元素数据元素数据元素数据元素(Data Element(Data Element(Data Element(Data Element):):):):是数据的基本单位，在计算是数据的基本单位，在计算是数据的基本单位，在计算是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。机程序中通常作为一个整体进行考虑和处理。机程序中通常作为一个整体进行考虑和处理。机程序中通常作为一个整体进行考虑和处理。一个数据元素可由若干个数据项组成。数

12、据项是一个数据元素可由若干个数据项组成。数据项是一个数据元素可由若干个数据项组成。数据项是一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。数据的不可分割的最小单位。数据的不可分割的最小单位。数据的不可分割的最小单位。数据对象数据对象数据对象数据对象(Data Object)(Data Object)(Data Object)(Data Object)：是性质相同的数据元素的集是性质相同的数据元素的集是性质相同的数据元素的集是性质相同的数据元素的集合。是数据的一个子集。合。是数据的一个子集。合。是数据的一个子集。合。是数据的一个子集。如：自然数集如：自然数集如：自然数集如：自

13、然数集N N N N0000，1 1 1 1，2 2 2 2，3 3 3 3，字母集字母集字母集字母集C C C CAAAA，BBBB，CCCC&1.1基本概念和术语基本概念和术语数据结构数据结构数据结构数据结构(Data Structure)(Data Structure)(Data Structure)(Data Structure)：是相互之间存在一种或是相互之间存在一种或是相互之间存在一种或是相互之间存在一种或多种特定关系的数据元素的集合。多种特定关系的数据元素的集合。多种特定关系的数据元素的集合。多种特定关系的数据元素的集合。&1.1基本概念和术语基本概念和术语形式化定义形式化定义形

14、式化定义形式化定义:D Data_ata_S Structures=tructures=（D D,S S）其中其中其中其中:D D是数据元素的有限集，是数据元素的有限集，是数据元素的有限集，是数据元素的有限集，S S是是是是D D上关系的有限集。上关系的有限集。上关系的有限集。上关系的有限集。包括三个方面：包括三个方面：包括三个方面：包括三个方面：逻辑结构、存储结构、存储及实现逻辑结构、存储结构、存储及实现逻辑结构、存储结构、存储及实现逻辑结构、存储结构、存储及实现逻辑结构：逻辑结构：逻辑结构：逻辑结构：描述其逻辑关系。可归结为以下四类描述其逻辑关系。可归结为以下四类描述其逻辑关系。可归结为以

15、下四类描述其逻辑关系。可归结为以下四类:集合结构集合结构&1.1基本概念和术语基本概念和术语线性结构线性结构（一对一）（一对一）树形结构树形结构（一对多）（一对多）图状结构图状结构（多对多）（多对多）线性结构的形式化描述：线性结构的形式化描述：Line=(D,R)D=a,b,c,dR=,存储结构存储结构存储结构存储结构：逻辑结构在计算机中的表示。分为两类：逻辑结构在计算机中的表示。分为两类：逻辑结构在计算机中的表示。分为两类：逻辑结构在计算机中的表示。分为两类：顺序顺序顺序顺序存储结构存储结构存储结构存储结构:逻辑关系由存储单元的邻接关系体现逻辑关系由存储单元的邻接关系体现逻辑关系由存储单元的

16、邻接关系体现逻辑关系由存储单元的邻接关系体现 即：逻辑上相邻的物理上也相邻。即：逻辑上相邻的物理上也相邻。即：逻辑上相邻的物理上也相邻。即：逻辑上相邻的物理上也相邻。通常用一维数组来描述。通常用一维数组来描述。通常用一维数组来描述。通常用一维数组来描述。可延伸为：索引和散列可延伸为：索引和散列可延伸为：索引和散列可延伸为：索引和散列链式存储结构链式存储结构链式存储结构链式存储结构:元素可以任意存储，不要求逻辑上相邻元素可以任意存储，不要求逻辑上相邻元素可以任意存储，不要求逻辑上相邻元素可以任意存储，不要求逻辑上相邻的物理上也相邻，其逻辑关系一般用指针来实现。的物理上也相邻，其逻辑关系一般用指针

17、来实现。的物理上也相邻，其逻辑关系一般用指针来实现。的物理上也相邻，其逻辑关系一般用指针来实现。注意：任一算法，设计在逻辑结构，但实现在存储注意：任一算法，设计在逻辑结构，但实现在存储注意：任一算法，设计在逻辑结构，但实现在存储注意：任一算法，设计在逻辑结构，但实现在存储结构上。结构上。结构上。结构上。&1.1基本概念和术语基本概念和术语数据类型：数据类型：数据类型：数据类型：具有相同性质的操作对象及其运算方法的集具有相同性质的操作对象及其运算方法的集具有相同性质的操作对象及其运算方法的集具有相同性质的操作对象及其运算方法的集合。即：一个合。即：一个合。即：一个合。即：一个值的集合值的集合值的

18、集合值的集合和定义在这个值集上的和定义在这个值集上的和定义在这个值集上的和定义在这个值集上的一组操作一组操作一组操作一组操作的总称。的总称。的总称。的总称。如：如：如：如：intint：32768327673276832767；+、*、抽象数据类型抽象数据类型抽象数据类型抽象数据类型(Abstract Data Type(Abstract Data Type(Abstract Data Type(Abstract Data Type 简称简称简称简称ADT)ADT)ADT)ADT)是指一个是指一个是指一个是指一个数学模型数学模型数学模型数学模型以及定义在此数学模型上的一以及定义在此数学模型上的

19、一以及定义在此数学模型上的一以及定义在此数学模型上的一组组组组操作操作操作操作它与数据类型实质上是一个概念，但其特征是它与数据类型实质上是一个概念，但其特征是它与数据类型实质上是一个概念，但其特征是它与数据类型实质上是一个概念，但其特征是使用使用使用使用与与与与实现实现实现实现分离，实行封装和信息隐蔽（独立于计算机）分离，实行封装和信息隐蔽（独立于计算机）分离，实行封装和信息隐蔽（独立于计算机）分离，实行封装和信息隐蔽（独立于计算机）&1.1基本概念和术语基本概念和术语 讨论每一种数据结构时讨论每一种数据结构时讨论每一种数据结构时讨论每一种数据结构时,均要介绍其上的运算。均要介绍其上的运算。均

20、要介绍其上的运算。均要介绍其上的运算。一般的，运算可分为下列两种基本类型：一般的，运算可分为下列两种基本类型：一般的，运算可分为下列两种基本类型：一般的，运算可分为下列两种基本类型：（1 1 1 1）加工型运算加工型运算加工型运算加工型运算：运算后改变了原结构中数据元素的个数：运算后改变了原结构中数据元素的个数：运算后改变了原结构中数据元素的个数：运算后改变了原结构中数据元素的个数或数据元素的内容。或数据元素的内容。或数据元素的内容。或数据元素的内容。（2 2 2 2）引用型运算引用型运算引用型运算引用型运算：运算不改变结构中数据元素的个数和元：运算不改变结构中数据元素的个数和元：运算不改变结

21、构中数据元素的个数和元：运算不改变结构中数据元素的个数和元素的内容，只从结构中提取某些信息作为运算的结果。素的内容，只从结构中提取某些信息作为运算的结果。素的内容，只从结构中提取某些信息作为运算的结果。素的内容，只从结构中提取某些信息作为运算的结果。&1.2运算运算 常用的基本运算主要包括：常用的基本运算主要包括：常用的基本运算主要包括：常用的基本运算主要包括：插入插入插入插入(加工型加工型加工型加工型):):):):在原结构的指定位置上增添新的数据元素。在原结构的指定位置上增添新的数据元素。在原结构的指定位置上增添新的数据元素。在原结构的指定位置上增添新的数据元素。删除删除删除删除(加工型加

22、工型加工型加工型):):):):将原结构中的某个指定的数据元素删除。将原结构中的某个指定的数据元素删除。将原结构中的某个指定的数据元素删除。将原结构中的某个指定的数据元素删除。查找查找查找查找(引用型引用型引用型引用型):):):):从结构中找出满足条件的数据元素的位置。从结构中找出满足条件的数据元素的位置。从结构中找出满足条件的数据元素的位置。从结构中找出满足条件的数据元素的位置。读取读取读取读取(引用型引用型引用型引用型):):):):使用结构中满足条件的数据元素的内容。使用结构中满足条件的数据元素的内容。使用结构中满足条件的数据元素的内容。使用结构中满足条件的数据元素的内容。更新更新更新

23、更新(加工型加工型加工型加工型):):):):更换结构中某个数据元素的内容。更换结构中某个数据元素的内容。更换结构中某个数据元素的内容。更换结构中某个数据元素的内容。使用这些基本运算，可以构成其他的复杂运算使用这些基本运算，可以构成其他的复杂运算使用这些基本运算，可以构成其他的复杂运算使用这些基本运算，可以构成其他的复杂运算&1.2运算运算一、算法的概念一、算法的概念一、算法的概念一、算法的概念 是为了解决某类问题而定义的一个有限长的操作序列。是为了解决某类问题而定义的一个有限长的操作序列。是为了解决某类问题而定义的一个有限长的操作序列。是为了解决某类问题而定义的一个有限长的操作序列。一个算法

24、必须满足一个算法必须满足一个算法必须满足一个算法必须满足五个重要特性五个重要特性五个重要特性五个重要特性：1 1 1 1、有穷性：有穷性：有穷性：有穷性：有限的指令，每个指令在有限的时间内完成有限的指令，每个指令在有限的时间内完成有限的指令，每个指令在有限的时间内完成有限的指令，每个指令在有限的时间内完成 2 2 2 2、确定性确定性确定性确定性：每一条指令都有明确的含义，相同的条件下：每一条指令都有明确的含义，相同的条件下：每一条指令都有明确的含义，相同的条件下：每一条指令都有明确的含义，相同的条件下执行线路是确定的执行线路是确定的执行线路是确定的执行线路是确定的 3 3 3 3、可行性可行

25、性可行性可行性：每个步骤都是切实可行，足够基本每个步骤都是切实可行，足够基本每个步骤都是切实可行，足够基本每个步骤都是切实可行，足够基本 4 4 4 4、输入：输入：输入：输入：一个算法可以有一个或多个输入，也可以没有一个算法可以有一个或多个输入，也可以没有一个算法可以有一个或多个输入，也可以没有一个算法可以有一个或多个输入，也可以没有输入（隐含输入）输入（隐含输入）输入（隐含输入）输入（隐含输入）5 5 5 5、输出输出输出输出：一个算法可以有一个或多个输出：一个算法可以有一个或多个输出：一个算法可以有一个或多个输出：一个算法可以有一个或多个输出&1.3算法及算法分析算法及算法分析1 1、正

26、确性，首先要满足算法需求，其次对算法的、正确性，首先要满足算法需求，其次对算法的、正确性，首先要满足算法需求，其次对算法的、正确性，首先要满足算法需求，其次对算法的“正确正确正确正确性性性性”的理解有以下四个层次：的理解有以下四个层次：的理解有以下四个层次：的理解有以下四个层次：2 2、易读性，一个好的算法主要是与他人交流共享，晦涩、易读性，一个好的算法主要是与他人交流共享，晦涩、易读性，一个好的算法主要是与他人交流共享，晦涩、易读性，一个好的算法主要是与他人交流共享，晦涩难懂的算法不利于交流、调试、维护。难懂的算法不利于交流、调试、维护。难懂的算法不利于交流、调试、维护。难懂的算法不利于交流

27、、调试、维护。3 3、健壮性，对于非法数据能够给出合理反应、健壮性，对于非法数据能够给出合理反应、健壮性，对于非法数据能够给出合理反应、健壮性，对于非法数据能够给出合理反应4 4、高效性，主要有两方面，运行时间和占用空间，即时、高效性，主要有两方面，运行时间和占用空间，即时、高效性，主要有两方面，运行时间和占用空间，即时、高效性，主要有两方面，运行时间和占用空间，即时间复杂度和空间复杂度间复杂度和空间复杂度间复杂度和空间复杂度间复杂度和空间复杂度此外，还要考虑算法的可维护性。此外，还要考虑算法的可维护性。此外，还要考虑算法的可维护性。此外，还要考虑算法的可维护性。二、算法的设计要求二、算法的设

28、计要求二、算法的设计要求二、算法的设计要求程序不含语法错误程序不含语法错误程序不含语法错误程序不含语法错误对于随意的几组合法数据输入对于随意的几组合法数据输入对于随意的几组合法数据输入对于随意的几组合法数据输入能够得出符合要求的结构能够得出符合要求的结构能够得出符合要求的结构能够得出符合要求的结构对于精心设计的典型、有刁难对于精心设计的典型、有刁难对于精心设计的典型、有刁难对于精心设计的典型、有刁难性的合法数据能够得出符合要求性的合法数据能够得出符合要求性的合法数据能够得出符合要求性的合法数据能够得出符合要求的结果的结果的结果的结果程序对所有的合法的输入数据程序对所有的合法的输入数据程序对所有

29、的合法的输入数据程序对所有的合法的输入数据都能得出符合要求的结果都能得出符合要求的结果都能得出符合要求的结果都能得出符合要求的结果&1.3算法及算法分析算法及算法分析1 1、算法的时间复杂度、算法的时间复杂度、算法的时间复杂度、算法的时间复杂度算法在整个运行过程中消耗的时间。算法在整个运行过程中消耗的时间。算法在整个运行过程中消耗的时间。算法在整个运行过程中消耗的时间。影响运行时间的因素：影响运行时间的因素：影响运行时间的因素：影响运行时间的因素：算法选用的策略算法选用的策略算法选用的策略算法选用的策略问题的规模问题的规模问题的规模问题的规模编程语言编程语言编程语言编程语言编译程序编译程序编译

30、程序编译程序产生的目标代码的质量产生的目标代码的质量产生的目标代码的质量产生的目标代码的质量机器运行指令的速度机器运行指令的速度机器运行指令的速度机器运行指令的速度衡量算法运行时间的方法衡量算法运行时间的方法衡量算法运行时间的方法衡量算法运行时间的方法事后统计事后统计事后统计事后统计缺点：必须执行程序；容易受其他硬件、软件因素影响缺点：必须执行程序；容易受其他硬件、软件因素影响缺点：必须执行程序；容易受其他硬件、软件因素影响缺点：必须执行程序；容易受其他硬件、软件因素影响事前估计事前估计事前估计事前估计&1.3算法及算法分析算法及算法分析二、算法分析二、算法分析二、算法分析二、算法分析(时间、

31、空间时间、空间时间、空间时间、空间)讨论算法主要讨论随着问题规模的增长，算法执行讨论算法主要讨论随着问题规模的增长，算法执行讨论算法主要讨论随着问题规模的增长，算法执行讨论算法主要讨论随着问题规模的增长，算法执行时间的增长率，通常用一个函数来表示：时间的增长率，通常用一个函数来表示：时间的增长率，通常用一个函数来表示：时间的增长率，通常用一个函数来表示：它表示随着问题规模它表示随着问题规模它表示随着问题规模它表示随着问题规模n n的增大，算法的执行时间的的增大，算法的执行时间的的增大，算法的执行时间的的增大，算法的执行时间的增长率和增长率和增长率和增长率和f f（n n）的增长率相同，称为算法

32、的渐进时间）的增长率相同，称为算法的渐进时间）的增长率相同，称为算法的渐进时间）的增长率相同，称为算法的渐进时间复杂度，简称复杂度，简称复杂度，简称复杂度，简称时间复杂度。时间复杂度。时间复杂度。时间复杂度。&1.3算法及算法分析算法及算法分析算法的时间复杂度算法的时间复杂度怎么分析算法的时间复杂度呢？怎么分析算法的时间复杂度呢？怎么分析算法的时间复杂度呢？怎么分析算法的时间复杂度呢？运行时间运行时间运行时间运行时间 =算法中每条语句执行时间之和。算法中每条语句执行时间之和。算法中每条语句执行时间之和。算法中每条语句执行时间之和。每条语句执行时间每条语句执行时间每条语句执行时间每条语句执行时间

33、 =该语句的执行次数（频度）该语句的执行次数（频度）该语句的执行次数（频度）该语句的执行次数（频度）*语语语语句执行一次所需时间。句执行一次所需时间。句执行一次所需时间。句执行一次所需时间。语句执行一次所需时间取决于机器的指令性能和速度和语句执行一次所需时间取决于机器的指令性能和速度和语句执行一次所需时间取决于机器的指令性能和速度和语句执行一次所需时间取决于机器的指令性能和速度和编译所产生的代码质量，很难确定。编译所产生的代码质量，很难确定。编译所产生的代码质量，很难确定。编译所产生的代码质量，很难确定。设每条语句执行一次所需时间为单位时间，则一个算法设每条语句执行一次所需时间为单位时间，则一

34、个算法设每条语句执行一次所需时间为单位时间，则一个算法设每条语句执行一次所需时间为单位时间，则一个算法的运行时间就是该算法中所有语句的频度之和。的运行时间就是该算法中所有语句的频度之和。的运行时间就是该算法中所有语句的频度之和。的运行时间就是该算法中所有语句的频度之和。例例例例:for(i=0;in;i+)for(i=0;in;i+)n+1n+1for(j=0;jn;j+)for(j=0;jy)x=5;(2)if(xy)x=5;elsex=10;elsex=10;T(n)=O(1)T(n)=O(1)算法的时间复杂度算法的时间复杂度(3)for(i=1;i=n;i+)(3)for(i=1;i=n

35、;i+)ai=i;ai=i;T(n)=O(n)T(n)=O(n)(4)n=100;(4)n=100;for(i=1;i=n;i+)for(i=1;i=n;i+)ai=i;ai=i;T(n)=O(1)T(n)=O(1)(5)x=0;(5)x=0;for(i=1;i=n;i+)for(i=1;i=n;i+)for(j=1;j=i;j+)for(j=1;j=i;j+)for(k=1;k=j;k+)for(k=1;k=j;k+)x+;x+;=O(n=O(n3 3)T(n)=T(n)=(6)i=s=0;(6)i=s=0;while(sn)while(s 1 b,i=1 第二章第二章线性表线性表顺序表的顺

36、序表的C语言实现语言实现#definemaxlen1000typedefintelemtype;elemtypeelemmaxlen;intlen;typedefstructSqList;SqList*L,*p;顺序表的运算顺序表的运算1.1.顺序表的查找顺序表的查找 对于给定的数据元素，找出其在线性表中的位置对于给定的数据元素，找出其在线性表中的位置intSqSearch(SqList*L,elemtypex)/在顺序表在顺序表L中查找数据元素中查找数据元素x在表中第一次在表中第一次出现的位置出现的位置intj;for(j=0;jlen;j+)if(L-elemj=x)return(j+1)

37、;return(0);x=38x=39L-Len=723075141238354462517678第二章第二章线性表线性表时间复杂度：时间复杂度：O O（n n）如按序号查找：如按序号查找：O O（1 1）顺序表的运算顺序表的运算2.2.顺序表的插入序表的插入 在在线性表（性表（n n个元素）的第个元素）的第i i个位置前插入一个元素个位置前插入一个元素 int SqInsert(int SqInsert(SqListSqList*L,elemtype x,int i)*L,elemtype x,int i)初始条件：初始条件：线性表性表L L已存在，已存在，1in+11in+1 操作操作结果

38、：果：在在L L的第的第i i个元素之前插入新的元素个元素之前插入新的元素x x，L L的的长度增度增1 1。实现步骤：实现步骤：将第将第n至第至第i位的元素向后移动一个位置；位的元素向后移动一个位置；将要插入的元素写到第将要插入的元素写到第i个位置；个位置；表长加表长加1。注意：注意：注意：注意：事先应判断事先应判断:插入位置插入位置i是否合法是否合法?表是否已满表是否已满?第二章第二章线性表线性表第二章第二章线性表线性表顺序表的运算顺序表的运算intSqInsert(SqList*L,elemtypex,inti)/在顺序表在顺序表L的第的第i个数据元素之前插入一个数据元素个数据元素之前插

39、入一个数据元素xintj,n;n=L-len;if(in+1)printf(Error!);return(0);if(n=maxlen)printf(Overflow!);return(0);for(j=n;j=i;j-)L-elemj=L-elemj-1;L-elemi-1=x;L-len+;return(1);23075141238354462517678L-len=7SqInsert(L,66,5)第二章第二章线性表线性表顺序表的运算顺序表的运算线性表的插入算法的时间复杂度线性表的插入算法的时间复杂度插入算法中，其时间主要消耗在移动数据元素上，插入算法中，其时间主要消耗在移动数据元素上，

40、数据的移动次数与插入元素的位置有关数据的移动次数与插入元素的位置有关(讨论等概率讨论等概率)。所有可能的元素移动次数合计：所有可能的元素移动次数合计：0+1+n=n(n+1)/20+1+n=n(n+1)/2共有多少种插入形式共有多少种插入形式?连头带尾有连头带尾有n+1n+1种种!故插入时的平均移动次数为：故插入时的平均移动次数为：n(n+1)/2n(n+1)/2（n+1n+1）n/2 n/2 O(n)O(n)O(n)O(n)第二章第二章线性表线性表顺序表的运算顺序表的运算3.3.顺序表的序表的删除：除：将将线性表（性表（n n个元素）的第个元素）的第i i个数据元素个数据元素删除除 int

41、SqDelete(SqList*L,int i,elemtype*p)int SqDelete(SqList*L,int i,elemtype*p)初始条件：初始条件：线性表性表L L已存在且非空，已存在且非空，1i1iListLengthListLength(L)(L)操作操作结果：果：删除除L L的第的第i i个元素，并用个元素，并用*p p返回其返回其值，L L的的长度度减减1 1。实现步骤：实现步骤：将第将第i+1至第至第n位的元素向前移动一个位置；位的元素向前移动一个位置；表长减表长减1。注意：事先需要判断，注意：事先需要判断，删除位置删除位置i是否合法是否合法?第二章第二章线性表线

42、性表顺序表的运算顺序表的运算intSqDelete(SqList*L,inti,elemtype*p)/在顺序表在顺序表L中删除第中删除第i个数据元素，个数据元素，*p返回其值返回其值intj,n;n=L-len;if(in)printf(Error!);return(0);*p=L-elemi-1;for(j=i-1;jelemj=L-elemj+1;L-len-;return(1);230751412383544625176L-len=7SqDelete(L,4,p)第二章第二章线性表线性表顺序表的运算顺序表的运算线性表的删除算法的时间复杂度线性表的删除算法的时间复杂度删除算法中，其时间主

43、要消耗在移动数据元素上，删除算法中，其时间主要消耗在移动数据元素上，数据的移动次数与删除元素的位置有关数据的移动次数与删除元素的位置有关所有可能的元素移动次数合计所有可能的元素移动次数合计 0+1+n-1=n(n-1)/20+1+n-1=n(n-1)/2共有多少种共有多少种删除删除形式形式?有有n n种种!删除删除时的平均移动次数为：时的平均移动次数为：n(n-1)/2n n(n-1)/2n（n-1n-1）/2/2 O(n)O(n)O(n)O(n)第二章第二章线性表线性表顺序存储结构的优缺点顺序存储结构的优缺点优点优点逻辑相邻，物理相邻逻辑相邻，物理相邻可随机存取任一元素可随机存取任一元素存储

44、空间使用紧凑存储空间使用紧凑缺点缺点插入、删除操作需要移动大量的元素插入、删除操作需要移动大量的元素预先分配空间需按最大空间分配，利用不充分预先分配空间需按最大空间分配，利用不充分表容量难以扩充表容量难以扩充顺序表顺序表第二章第二章线性表线性表2.3线性表的链式存储结构线性表的链式存储结构1.1.1.1.单链表单链表单链表单链表线性表的链式存储结构简称线性表的链式存储结构简称链表链表，其特点为：，其特点为：用一组任意的存储单元存储线性表的数据元素用一组任意的存储单元存储线性表的数据元素利用指针实现了用不相邻的存储单元存放逻辑上相邻的利用指针实现了用不相邻的存储单元存放逻辑上相邻的元素元素数据域

45、数据域 指针域指针域结点结点每个数据元素，除存储本身信息外，每个数据元素，除存储本身信息外，还需存储其直接后继的信息还需存储其直接后继的信息结点结点数据域：元素本身信息数据域：元素本身信息指针域：指示直接后继的存储位置指针域：指示直接后继的存储位置第二章第二章线性表线性表例例 线性表线性表 (ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)(ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)19WANGNULL数据域数据域指针域指针域1LI43存储地址存储地址31h头指针头指针7QIAN1313SUN125WU3731ZHAO737ZHENG194

46、3ZHOU25WUZHENGhZHAOQIANSUNLIZHOUWANG2.3线性表的链式存储结构线性表的链式存储结构第二章第二章线性表线性表结点：结点：数据元素的存储映像。由数据域和指针域两部分组成；数据元素的存储映像。由数据域和指针域两部分组成；链表：链表：n个结点由指针链组成一个链表。它是线性表的链式存储映像，称个结点由指针链组成一个链表。它是线性表的链式存储映像，称为线性表的链式存储结构为线性表的链式存储结构,结点只有一个指针域的链表，称为结点只有一个指针域的链表，称为单链表单链表或或线性链线性链表表。头指针：头指针：指向链表中第一个结点的指针。指向链表中第一个结点的指针。头结点：头结

47、点：有时候为了操作方便在单链表的第一个结点之前添加一个结点，有时候为了操作方便在单链表的第一个结点之前添加一个结点，该结点和表中的其他结点结构相同，只是数据域不存放数据，或闲置不用，该结点和表中的其他结点结构相同，只是数据域不存放数据，或闲置不用，或存放其他信息。或存放其他信息。HZHAOQIANSUNLIZHOUWUZHENGWANG2.3线性表的链式存储结构线性表的链式存储结构第二章 线性表类型定义类型定义typedefstructNodeelemtypedata;structNode*next;LinkList;LinkList*h,*p;生成一个生成一个LinkListLinkList

48、型新结点：型新结点：p=(LinkList*)malloc(sizeof(LinkList);p=(LinkList*)malloc(sizeof(LinkList);系统回收系统回收p p结点：结点：free(p)free(p)a1a2an h空单链表：空单链表：hp2.3线性表的链式存储结构线性表的链式存储结构第二章第二章线性表线性表单链表的算法单链表的算法(1)(1)查找查找查找单链表中是否存在结点查找单链表中是否存在结点x，若有则返回指向，若有则返回指向x结点的指针；否则返结点的指针；否则返回回NULLLinkList*LinkSearch(LinkList*h,elemtypex)/

49、在单链表中查找数据元素值为在单链表中查找数据元素值为x的节点的节点LinkList*p;p=h-next;while(p!=NULL&p-data!=x)p=p-next;return(p);时间复杂度时间复杂度O（n）a1a2Xan hppp(2)(2)取指定位置（第取指定位置（第i i个）的元素个）的元素intGetElem(LinkList*h,inti,elemtype*e)/把链表把链表h中第中第i个元素的值存入在指针个元素的值存入在指针e的目标变量中的目标变量中LinkListp;intj;p=h-next;j=1;while(p!=NULL&jnext;j+;if(p=NULL)

50、return0;*e=p-data;return1;单链表的算法单链表的算法第二章第二章线性表线性表a1a2a3a4 hpj=1pj=2pj=3(3)(3)插入插入在链表（在链表（n个元素）的第个元素）的第i(1in+1)个位置前插入个位置前插入一个元素一个元素,成功返回成功返回1，否则返回，否则返回0。ai-1aisxpai-1aisxp单链表的算法单链表的算法第二章第二章线性表线性表s=(LinkList*)malloc(sizeof(LinkList);s-data=x;s-next=p-next;p-next=s;intLinkInsert(LinkList*h,inti,elemty