第1章绪论(数据结构教程PPT课件)

1、 开设本课程的背景开设本课程的背景 数据结构数据结构是计算机相关专业的一门重要的专业是计算机相关专业的一门重要的专业基础课。它主要研究计算机加工对象的逻辑结构、在基础课。它主要研究计算机加工对象的逻辑结构、在计算机中的表示形式以及实现各种基本操作的算法。计算机中的表示形式以及实现各种基本操作的算法。学好这门课，可以加深对程序设计的理解，有助于进学好这门课，可以加深对程序设计的理解，有助于进一步提高程序设计能力，为进行软件开发打下良好的一步提高程序设计能力，为进行软件开发打下良好的基础，并为计算机专业后续课程，如数据库操作系统基础，并为计算机专业后续课程，如数据库操作系统编译原理，软件工程等课程

2、奠定良好的基础。编译原理，软件工程等课程奠定良好的基础。 本课程讲述的主要内容本课程讲述的主要内容 本课程将分别讲述数据结构的基本概念、线性表、栈本课程将分别讲述数据结构的基本概念、线性表、栈和队列、串和数组、树形结构、图结构、查找、排序等和队列、串和数组、树形结构、图结构、查找、排序等内容。内容。 学习本课程的基本方法学习本课程的基本方法l上课认真听讲；上课认真听讲；l 仔细阅读教材中的大量例题，从而体会并最终掌握仔细阅读教材中的大量例题，从而体会并最终掌握数据结构中的基本概念；数据结构中的基本概念；l 认真上机实习，独立完成每个章节后面的练习题。认真上机实习，独立完成每个章节后面的练习题。

3、v教学目的教学目的1.了解数据结构基本概念的含义了解数据结构基本概念的含义2.了解数据结构研究的主要内容了解数据结构研究的主要内容3.理解数据逻辑结构及存储结构的定义及分类理解数据逻辑结构及存储结构的定义及分类4.理解算法的概念、描述方法以及评价标准理解算法的概念、描述方法以及评价标准5.掌握时间复杂度与空间复杂度的计算掌握时间复杂度与空间复杂度的计算 1.1 数据结构的概念数据结构的概念 1.2 算法描述算法描述 1.3 算法分析算法分析 当今计算机应用的特点：当今计算机应用的特点： l l所处理的数据量大且具有一定的关系；所处理的数据量大且具有一定的关系； l l对其操作不再是单纯的数值计

4、算，而更多地是需对其操作不再是单纯的数值计算，而更多地是需要对其进行组织、管理和检索。要对其进行组织、管理和检索。 应用举例应用举例1 1学籍档案管理学籍档案管理 假设一个学籍档案管理系统应包含如下表假设一个学籍档案管理系统应包含如下表1-1所示所示的学生信息。的学生信息。 学 生 基本 情 况学 号姓 名性 别出 生 年 月.99070101李 军男80 12.99070102王 颜 霞女81 2.99070103孙 涛男80 9.99070104单 晓 宏男81 3. 特点：特点： l l每个学生的信息占据一行，所有学生的信息按学每个学生的信息占据一行，所有学生的信息按学号顺序依次排列构成

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

6、12321231213211 特点：特点： l l在求解过程中，所处理的数据之间具有层在求解过程中，所处理的数据之间具有层次关系，这是我们所说的树形结构；次关系，这是我们所说的树形结构； l l对它的操作有：建立树形结构，输出最低对它的操作有：建立树形结构，输出最低层结点内容等等。层结点内容等等。 应用举例应用举例3制定教学计划制定教学计划 在制定教学计划时，需要考虑各门课程的开设顺在制定教学计划时，需要考虑各门课程的开设顺序。有些课程需要先导课程，有些课程则不需要，而序。有些课程需要先导课程，有些课程则不需要，而有些课程又是其他课程的先导课程。比如，计算机专有些课程又是其他课程的先导课程。比

7、如，计算机专业课程的开设情况如下表业课程的开设情况如下表1-2所示：所示： 计 算 机 专 业 学 生 的 必 修 课 程课 程 编 号课 程 名 称需 要 的 先 导 课 程编 号c 1程 序 设 计 基 础无c 2离 散 数 学c 1c 3数 据 结 构c 1 ， c 2c 4汇 编 语 言c 1c 5算 法 分 析 与 设 计c 3 ， c 4c 6计 算 机 组 成 原 理c 1 1c 7编 译 原 理c 5 ， c 3c 8操 作 系 统c 3 ， c 6c 9高 等 数 学无c 1 0线 性 代 数c 9c 1 1普 通 物 理c 9c 1 2数 值 分 析c 9 ， c 1 0

8、， c 1课程先后关系的图形描形式：课程先后关系的图形描形式：c1c9c4c2c12c10c11c5c3c6c7c8 特点特点 l l课程之间的先后关系用图结构描述；课程之间的先后关系用图结构描述； l l通过实施创建图结构，按要求将图结构中的顶点通过实施创建图结构，按要求将图结构中的顶点进行线性排序。进行线性排序。 结论结论 计算机的操作对象的关系更加复杂，操作形式不计算机的操作对象的关系更加复杂，操作形式不再是单纯的数值计算，而更多地是对这些具有一定关再是单纯的数值计算，而更多地是对这些具有一定关系的数据进行组织管理，我们将此称为非数值性处理。系的数据进行组织管理，我们将此称为非数值性处理

9、。要使计算机能够更有效地进行这些非数值性处理，就要使计算机能够更有效地进行这些非数值性处理，就必须弄清楚这些操作对象的特点，在计算机中的表示必须弄清楚这些操作对象的特点，在计算机中的表示方式以及各个操作的具体实现手段。这些就是方式以及各个操作的具体实现手段。这些就是数据数据结构结构这门课程研究的主要内容。这门课程研究的主要内容。 数据数据 是对客观事物的符号表示。在计算机科学中其含是对客观事物的符号表示。在计算机科学中其含义是指所有能够输入到计算机中并被计算机程序处理义是指所有能够输入到计算机中并被计算机程序处理的符号集合。的符号集合。 数据元素（数据元素（data element） 数据元素

10、是组成数据的基本单位数据元素是组成数据的基本单位, 是数据集合的个体，在计是数据集合的个体，在计算机中通常作为一个整体进行考算机中通常作为一个整体进行考虑和处理。虑和处理。 学学 籍籍 表表 学号姓名性别籍贯出生年月住址101赵红玲女河北1983.11北京 数据项数据项记录记录数据项：具有独立含义的最小数据标识单位。数据项：具有独立含义的最小数据标识单位。 数据结构数据结构 数据结构的内容可归纳为三个部分：逻辑结构、存数据结构的内容可归纳为三个部分：逻辑结构、存储结构和运算集合。按某种逻辑关系组织起来的一批数储结构和运算集合。按某种逻辑关系组织起来的一批数据，按一定的映象方式把它存放在计算机的

11、存储器中，据，按一定的映象方式把它存放在计算机的存储器中，并在这些数据上定义了一个运算的集合，并在这些数据上定义了一个运算的集合， 就叫做数据就叫做数据结构。结构。 逻辑结构逻辑结构 数据结构中所说的数据结构中所说的“关系关系”实际上是指数据元素之实际上是指数据元素之间的逻辑关系，又称此为逻辑结构。常见的逻辑结构有：间的逻辑关系，又称此为逻辑结构。常见的逻辑结构有：线性结构、树形结构和图形结构，集合。线性结构、树形结构和图形结构，集合。四个基本逻辑结构四个基本逻辑结构集合集合线性结构线性结构树形结构树形结构 图图逻辑结构可看作是从逻辑结构可看作是从具体问题抽象出来的具体问题抽象出来的数学模型。

12、数学模型。 存储结构（物理结构）存储结构（物理结构） 是指数据结构在计算机存储器中的具体实现。与是指数据结构在计算机存储器中的具体实现。与孤立的数据元素表示形式不同，数据结构中的数据元孤立的数据元素表示形式不同，数据结构中的数据元素不但要表示其本身的实际内容，还要表示清楚数据素不但要表示其本身的实际内容，还要表示清楚数据元素之间的逻辑结构。元素之间的逻辑结构。 常见的存储结构常见的存储结构 顺序存储结构：逻辑上相邻的元素存储在物理位顺序存储结构：逻辑上相邻的元素存储在物理位置相邻的存储单元中置相邻的存储单元中.通常借助于程序设计语言中的数通常借助于程序设计语言中的数组来实现组来实现. 链式存储

13、结构：逻辑上相邻的元素不要求其物理位链式存储结构：逻辑上相邻的元素不要求其物理位置相邻置相邻,元素间的相邻关系借助于指示数据元素地址的元素间的相邻关系借助于指示数据元素地址的指针来实现。指针来实现。数据结构数据结构逻辑结构逻辑结构存储结构存储结构数据运算数据运算 （算法）（算法）（线性结构、树、图、集合）（线性结构、树、图、集合）链式存储结构链式存储结构顺序存储结构顺序存储结构 1.2.1 算法的概念算法的概念 算法是解决某个特定问题的一种方法或一个过程。算法是解决某个特定问题的一种方法或一个过程。 计算机对数据的操作可以分为数值性和非数值性计算机对数据的操作可以分为数值性和非数值性两种类型。

14、在数值性操作中主要进行的是算术运算；两种类型。在数值性操作中主要进行的是算术运算；而在非数值性操作中主要进行的是检索、排序、插入、而在非数值性操作中主要进行的是检索、排序、插入、删除等等。删除等等。 编写程序的基本过程编写程序的基本过程 l l通过对问题进行详细地分析，抽象出相应的数学通过对问题进行详细地分析，抽象出相应的数学模型；模型； l l确定使用的数据结构，并在此基础上设计对此数确定使用的数据结构，并在此基础上设计对此数据结构实施各种操作的算法；据结构实施各种操作的算法； l l选用某种语言将算法转换成程序；选用某种语言将算法转换成程序； l l调试并运行这些程序。调试并运行这些程序。

15、 算法应该具有下列五个特性算法应该具有下列五个特性 （1）有穷性：一个算法必须在执行有穷步之后结）有穷性：一个算法必须在执行有穷步之后结束。束。 （2）确定性：算法中的每一步，必须有确切的含）确定性：算法中的每一步，必须有确切的含义，在他人理解时不会产生二义性。义，在他人理解时不会产生二义性。 （3）可行性：算法中描述的每一步操作都可以通）可行性：算法中描述的每一步操作都可以通过已有的基本操作执行有限次实现。过已有的基本操作执行有限次实现。 （4）输入：一个算法应该有零个或多个输入。）输入：一个算法应该有零个或多个输入。 （5）输出：一个算法应该有一个或多个输出。这）输出：一个算法应该有一个或

16、多个输出。这里所说的输出是指与输入有某种特定关系的量。里所说的输出是指与输入有某种特定关系的量。 举例举例 问题：按从小到大的顺序重新排列问题：按从小到大的顺序重新排列x，y，z三个数三个数值的内容。值的内容。 算法：算法： （1）输入）输入x，y，z三个数值；三个数值； （2）从三个数值中挑选出最小者并换到）从三个数值中挑选出最小者并换到x中；中； （3）从）从y，z中挑选出较小者并换到中挑选出较小者并换到y中；中； （4）输出排序后的结果。）输出排序后的结果。 1.2.2 算法的描述算法的描述 算法描述分为以下算法描述分为以下4种种: （1）框图算法描述）框图算法描述(程序流程图程序流程图

17、,n-s流程图流程图) （2）非形式算法描述）非形式算法描述 （3）伪语言算法描述）伪语言算法描述 （4）高级语言编写的程序或函数）高级语言编写的程序或函数 算法的评价标准算法的评价标准 (1) 正确性：要求算法能够正确地执行预先规定的正确性：要求算法能够正确地执行预先规定的功能，并达到所期望的性能要求。功能，并达到所期望的性能要求。 (2) 可读性：为了便于理解、测试和修改算法，算可读性：为了便于理解、测试和修改算法，算法应该具有良好的可读性。法应该具有良好的可读性。 (3) 健壮性：算法中拥有对输入数据、打开文件、健壮性：算法中拥有对输入数据、打开文件、读取文件记录、分配内存空间等操作的结

18、果检测，并读取文件记录、分配内存空间等操作的结果检测，并通过与用户对话的形式做出相应的处理选择。通过与用户对话的形式做出相应的处理选择。 (4) 时间与空间效率：算法的时间与空间效率是时间与空间效率：算法的时间与空间效率是指将算法变换为程序后，该程序在计算机上运行时所指将算法变换为程序后，该程序在计算机上运行时所花费的时间及所占据空间的度量。花费的时间及所占据空间的度量。 算法的时间效率算法的时间效率 算法的时间效率主要由两个因素决定：算法的时间效率主要由两个因素决定： l l所需处理问题的数据量大小，数据量大，所需处理问题的数据量大小，数据量大，所花费的时间就多；所花费的时间就多； l l在

19、解决问题的过程中，基本操作的执行次在解决问题的过程中，基本操作的执行次数。数。时间特性的分析时间特性的分析 如果我们将一个算法所花费的时间设计成一个以如果我们将一个算法所花费的时间设计成一个以数据量数据量n为自变量的函数为自变量的函数t(n)，这个函数在正整数定义，这个函数在正整数定义域范围内一定是单调递增的。好的算法应该能够在数域范围内一定是单调递增的。好的算法应该能够在数据量据量n增长的同时，函数增长的同时，函数t(n)的增长速度比较缓慢。的增长速度比较缓慢。一般情况下，算法中基本操作重复执行的次数是问题规一般情况下，算法中基本操作重复执行的次数是问题规模模n的某个函数，算法的时间量度记作

20、的某个函数，算法的时间量度记作 t(n)=o(f(n)称作算法的渐近时间复杂度。称作算法的渐近时间复杂度。例例1 +x;s=0;将将x自增看成是基本操作，自增看成是基本操作， s=0也看成是基本操作也看成是基本操作, 则时间复杂度为则时间复杂度为(2)，即常量阶。，即常量阶。例例2、for(i=1;i=n;+i) +x;s+=x;基本操作基本操作 出现的次数（频度）为：出现的次数（频度）为：2n其时间复杂度为：其时间复杂度为：o(n) 即时间复杂度为线性阶。即时间复杂度为线性阶。例例3、for(i=1;i=n;+i)for(j=1;j=n;+j) +x;s+=x; 基本操作执行的次数（语句频度

21、）为：基本操作执行的次数（语句频度）为：2n2其时间复杂度为：其时间复杂度为：o(n2) 即时间复杂度为平方阶。即时间复杂度为平方阶。例例4、for(i=2;i=n;+i)for(j=1;j=i-1;+j) +x;aij=x;语句频度为：语句频度为： 2*( 1+2+3+n-1)=2*(1+n-1) (n-1)/2 =2*n(n-1)/2 =n2 -n 时间复杂度为时间复杂度为o(n2) 即此算法的时间复杂度为平方阶即此算法的时间复杂度为平方阶. 总之，算法时间复杂度计算：算法中基本操作的重总之，算法时间复杂度计算：算法中基本操作的重复执行的次数，它是问题规模复执行的次数，它是问题规模n的某个函数的某个函数f(