数据结构-课件-胡学钢

1、2021/8/61数据结构数据结构(C(C语言版语言版) )2021/8/62目目 录录概概 论论第第 1 章章线线 性性 表表第第 2 章章栈、队列和数组栈、队列和数组第第 3 章章树树第第 4 章章图图第第 5 章章查查 找找第第 6 章章排排 序序第第 7 章章文文 件件第第 8 章章2021/8/63第第 1 章章 概概 论论数据结构的研究内容数据结构的研究内容1.1基基 本本 术术 语语1.2算算 法法 描描 述述 及及 分分 析析1.32021/8/641.1 数据结构的研究内容1.1.1 用计算机解决实际问题的过程用计算机解决实际问题的过程建立建立 模型模型构造求构造求解算法解算

2、法选择存储选择存储结构型结构型编写编写程序程序测试测试思考思考：你认为数据结构课程会涉及到上述哪些步骤呢？2021/8/65数据结构课程在问题求解过程中的作用： 与建立模型的关系 与算法设计的关系 与选择存储结构的关系 与编程之间的关系2021/8/661.1.2 学习数据结构的意义 在计算机科学中，数据结构不仅是一般程序设计的基础，而且是设计和实现编译程序、操作系统、数据库系统及其它系统程序和大型应用程序的重要基础。 目前在我国，数据结构不仅是计算机专业的核心课程之一，而且是一些非计算机专业的主要选修课程之一。 瑞士计算机科学家沃斯（N.Wirth）曾以“算法算法 + + 数据结构数据结构

3、程序程序”作为他的一本著作的名称。可见，程序设计的实质是对实际问题选择一种好的数据结构，并设计一个好的算法。因此，若仅仅掌握几种计算机语言和程序设计方法，而缺乏数据结构知识，则难以应付众多复杂的课题，且不能有效地利用计算机。 2021/8/67 数据结构 是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。是介于数学、计算机软件、计算机硬件的 一门核心课程。2021/8/681.2 基本术语数数 据据数据元素数据元素 字段字段( (域域) ) 数据结构数据结构数据结构的逻辑结构数据结构的逻辑结构数据结构的物理结构数据结构的物理结构数据结构运算的实现数据结构运算

4、的实现2021/8/691.2 基本术语数数 据据数据元素数据元素 字段字段( (域域) ) 数据结构数据结构数据结构的逻辑结构数据结构的逻辑结构数据结构的物理结构数据结构的物理结构数据结构运算的实现数据结构运算的实现数据是指信息的载体，是能够输入到计算机中，并被计算机识别、存储和处理的符号的集合。数据的形式较多，例如我们前面所述的工资报表、学生成绩表，一个家族关系的表示形式，表示一个群体中个体之间关系的图形描述等。 2021/8/6101.2 基本术语数数 据据数据元素数据元素 字段字段( (域域) ) 数据结构数据结构数据结构的逻辑结构数据结构的逻辑结构数据结构的物理结构数据结构的物理结构

5、数据结构运算的实现数据结构运算的实现数据中具有独立意义的个体。例如工资表中的个人工资信息，成绩表中的学生成绩信息，家族关系中的个人等。在有些场合下，也称之为元素元素、记录记录、结点结点、顶点顶点等。 2021/8/6111.2 基本术语数数 据据数据元素数据元素 字段字段( (域域) ) 数据结构数据结构数据结构的逻辑结构数据结构的逻辑结构数据结构的物理结构数据结构的物理结构数据结构运算的实现数据结构运算的实现虽然将具有独立意义的个体用元素来表示，但在许多情况下还需要特定个体的具体信息，因而涉及到了元素的字段信息。字段是对元素的详细描述，通常情况下，元素可能包含多个字段。 2021/8/612

6、1.2 基本术语数数 据据数据元素数据元素 字段字段( (域域) ) 数据结构数据结构数据结构的逻辑结构数据结构的逻辑结构数据结构的物理结构数据结构的物理结构数据结构运算的实现数据结构运算的实现数据结构是指组成数据的元素之间的结构关系。线性结构、树型结构和图结构是数据结构中的几类常见的数据结构形式。如果数据中的元素之间没有关系，则构成集合集合，这也是一种结构。 2021/8/6131.2 基本术语数数 据据数据元素数据元素 字段字段( (域域) ) 数据结构数据结构数据结构的逻辑结构数据结构的逻辑结构数据结构的物理结构数据结构的物理结构数据结构运算的实现数据结构运算的实现我们将线性结构、树型结

7、构和图结构这几类结构称为逻辑结构逻辑结构，它包括数据元素的表示和关系的表示。因为仅考虑了元素之间的逻辑关系，而没有考虑到其在计算机中的具体实现。2021/8/6141.2 基本术语数数 据据数据元素数据元素 字段字段( (域域) ) 数据结构数据结构数据结构的逻辑结构数据结构的逻辑结构数据结构的物理结构数据结构的物理结构数据结构运算的实现数据结构运算的实现为所涉及的数据结构选择一种存储形式，并将其存储到计算机中，这样就得到了数据结构在内存中的物理结构物理结构（有时也称为存储结构存储结构）。一种逻辑结构可能会有多种存储结构。例如，可以采用顺序存储，也可采用连接形式的存储。不同存储结构上所实现的运

8、算的性能可能有一定的差异。 2021/8/6151.2 基本术语数数 据据数据元素数据元素 字段字段( (域域) ) 数据结构数据结构数据结构的逻辑结构数据结构的逻辑结构数据结构的物理结构数据结构的物理结构数据结构运算的实现数据结构运算的实现数据的逻辑结构与存储结构密切相关。一个算法的设计取决于选定的逻辑结构，而算法的实现依赖于采用的存储结构。在选择了数据结构的存储结构之后，就可以实现所给出的运算了。 2021/8/6161.2 小 结数数 据据数据元素数据元素 字段字段( (域域) ) 数据结构数据结构数据结构的数据结构的逻辑结构逻辑结构数据结构的数据结构的物理结构物理结构数据结构运算的数据

9、结构运算的实现实现所以，由于不同的存储形式对算法的时间性能、空间性能等有较大影响，即使是相同的存储结构也可能会存在不同的算法实现，为此，需要解决这样的问题：究竟何种存储结构更为合适？什么算法更有效？为此，需要对算法进行分析，有关算法分析部分将在本章的后面部分讨论。通过分析，可以知道所实现的算法的性能及所选择的存储结构是否符合要求。 2021/8/6171.3 算法描述及分析1.3.1 算法描述语言概述算法描述语言概述描述：描述：算法可采用多种描述语言来描述，如自然语言、计算机语言或某些伪语言。各种描述语言在对问题的描述能力方面存在一定的差异：自然语言较为灵活，但不够严谨；而计算机语言虽然严格，

10、但由于语法方面的限制，使得灵活性不足。因此，许多教材中采用的是以一种计算机语言为基础，适当添加某些功能或放宽某些限制而得到的一种类语言，如类PASCAL语言、C语言等，这些类语言既具有计算机语言的严格性，又具有某些灵活性，同时也容易上机实现，因而被广泛接受。 定义定义:是对特定问题求解步骤的一种描述,是指令的有限序列,其中每一条指令表示一个或多个 操作。特性特性: 有穷性 确定性 可行性 输入 输出2021/8/618算法设计的要求：算法设计的要求：u 正确性：算法是否正确,是否符合具体问题的需求。u 可读性：有利于人机交流，机器执行。u 健壮性：对错误能适当的做出反应或进行处理。u 效率与低

11、存储量的要求。2021/8/6191.3 算法描述及分析1.3.2 算法分析算法分析 衡量算法的主要性能指标包括时间性能、空间性能等，其中时间性能是指运行算法所需的时间的度量，而空间性能则是指运行算法所需要的辅助空间的规模。 度量运行时间的方法：事后统计，事前分析估算（常用后一种）。2021/8/620 时间的复杂度时间的复杂度是指算法中包含简单操作重复执行的次数，而某个语句重复执行的次数就是该语句的频度。 可以记做：T(n)=O( f(n) ) 其中f(n）是问题规模n的某个函数，一般是算法中频度最大的语句频度。 例如： s:=0; for (k=1 ; k=n;k+) for( j=0;j

12、= n;j+) s:=s+2; 语句的频度是n*(n+1) * 存在循环嵌套语句时，算法的时间复杂度是由嵌套最深层的语句频度决定。 评价一个算法的时间性能主要标准是时间复杂度的数量级。这个程序段的时间复杂度为：T(n)=O(n2+n)=O(n2)所谓数量级是这样定义的：如果变量如果变量n的函数的函数f(n)和和g(n)满足：满足：lim =常数常数k(k0)，则称，则称f(n)和和g(n)是同一数量级的，并用是同一数量级的，并用f(n)=O(g(n)的形式来表示。的形式来表示。)()(ngnf2021/8/621 按数量级递增的顺序排列，常见的时间复杂度为： 常数阶O（1） 对数阶 O（2n）

13、 线性阶O（n） 线性对数阶O（n 2n ） 平方阶O（n2） 立方阶O（n3） K次方阶O（nk） 指数阶O（2n）2021/8/622例：程序段 语句频度 时间复杂度1. x=x+1; FOR( i=0; i= n;i+) x:=x+1; 3. FOR( i=1; in;i+) FOR(j=0; jn;j+) x:=x+1; 1 O(1) 常数阶 n+1 O(n) 线性阶(n-1)*nO(n2) 平方阶2021/8/623 算法与程序的区别算法是解决问题的一种方法或一个过程，考虑如何将输入转换成输出，一个问题可以有多种算法。程序是用某种程序设计语言对算法的具体实现。主要区别在：有穷性和描述方法 程序可以是无穷的，例如OS，算法是有穷的； 程序是用程序设计语言描述，在机器上可以执行； 算法还可以用框图、自然语言等方式描述。2021/8/624思考题 下面程序段的时间复杂度为（）(a) x=x+1;(b) FOR( i=0; i=n;i+) x=x+1;(c) FOR( i=1; i n;i+) FOR( j