第1章数据结构绪论

1、第1页第2页 数据结构是计算机及相关专业中一门重要的专业基础课程。本课程的任务： 在基础方面，要求学生掌握常用数据结构的基本概念及其不同的实现方法；在技能方面，通过系统学习能够在不同存储结构上实现不同的运算，并对算法设计的方式和技巧有所体会。学业基础： 本课程的先修课程为离散数学和高级语言程序设计。学习本课程必须具备高级语言程序设计(C语言)的基础知识与基本技能。它的后续课程有操作系统和数据库原理等。第3页2022年5月5日教学内容： (1)数据结构的概念 (2)抽象数据类型 (3)算法和算法分析 (4)递归 教学目的： (1)领会数据、数据元素和数据项的概念及其相互间关系 (2)清楚数据结构

2、的逻辑结构、存储结构的联系与区别 (3)理解抽象数据类型的概念 (4)掌握进行简单算法分析的方法 (5)理解递归的特点，会分析什么样的问题适合用递归解决；领会递归调用的执行过程； 了解递归的优缺点第1章 数据结构与算法第4页2022年5月5日教学重点： 数据、数据项、数据元素、数据结构的概念 逻辑结构和数据结构在概念上的联系与区别 抽象数据类型和数据抽象 评价算法优劣的标准及方法 (5) 什么样的问题可以用递归解决、递归实现的方法 、递归方法的时空效率教学难点： 区别算法与程序 逻辑结构、存储结构的联系与区别 抽象数据类型与数据抽象 算法的时间复杂度分析 (5)递归的执行过程；递归转换为非递归

3、第5页2022年5月5日1.1.1 为什么要学习数据结构随着计算机应用领域的扩大和软、硬件的发展，非数值计算问题越来越显得重要。这类问题涉及到的数据结构更为复杂，数据元素之间的相互关系一般无法用数学方程式加以描述。解决这类问题的关键是要设计出合适的数据结构，才能有效地解决问题。1.1 引言第6页2022年5月5日 【例1-1】成绩检索系统。要求成绩检索系统提供自动查询的功能，如查找某个学生的单科成绩或平均成绩，查询某门课程的最高分等等。学号姓名 考 试 成 绩 平均成绩高等数学C语言英语20071801吴承志9095859020071802李淑芳8876918520071803刘 丽92788

4、28420071804张会友8178727720071805石宝国7682797920071806何文颖8690918920071807赵胜利7678807820071808崔文靖8293868720071809刘 丽80858182图 1-1 学生成绩表第7页 【例1-2】棋盘布局问题。要求将4个棋子布在4行4列的棋盘上，使得任两个棋子既不在同一行或同一列，也不在同一对角线上。第8页2022年5月5日 【例1-3】教学计划编排问题第9页2022年5月5日1、数据结构课程的发展 数据结构作为一门独立的课程在国外是从1968年才开始的，但在此之前其有关内容已散见于编译原理及操作系统之中。 从20

5、世纪60年代末到70年代初，出现了大型程序，软件也相对独立，结构程序设计成为程序设计方法学的主要内容，人们越来越重视数据结构。 从70年代中期到80年代，各版本的数据结构著作相继出现。 1.1.2 数据结构课程的内容第10页2022年5月5日数据结构的内容包括三个层次的五个“要素”。2、数据结构课程的内容第11页2022年5月5日1.2.1 有关概念和术语1、数据2、数据项3、数据元素4、数据对象 1.2 数据结构的概念第12页2022年5月5日 （a）集合结构 （b）线性结构 （c）树结构 （d）图结构 四类基本结构的示意图5、数据结构 集合结构。线性结构。树结构。图结构。 第13页2022

6、年5月5日(1)逻辑层次的数据结构有两个要素。 一个是数据元素的集合，另一个是关系的集合。 形式上，数据结构可以采用一个二元组来表示： Data_Structure （D，R）其中，D是数据元素的有限集，R是D上关系的有限集。(2) 应用层次的数据结构包括数据的逻辑结构和数据的物理结构。 数据的逻辑结构可以看作是从具体问题抽象出来的数学模型，它与数据的存储无关。 数据结构在计算机中的标识称为数据的物理结构，或称存储结构。第14页2022年5月5日1.2.2 抽象数据类型1、数据类型 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。2、抽象数据类型 抽象数据类型（Abstruct Da

7、ta Type，简称ADT）是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型的定义取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部的使用。第15页2022年5月5日1.3.1 算法及其特性 算法（算法（AlgorithmAlgorithm）是对特定问题求解步骤的一种描述，）是对特定问题求解步骤的一种描述，是指令的有限序列。其中每一条指令表示一个或多个操作。是指令的有限序列。其中每一条指令表示一个或多个操作。 一个算法应该具有下列特性： 有穷性。有穷性。 确定性。确定性。 可行性。可行性。 输入。输入。 输出。

8、输出。1.3 算法 第16页2022年5月5日要设计一个好的算法通常要考虑以下的要求。 正确。正确。 可读。可读。 健壮。健壮。 高效。高效。第17页2022年5月5日1.3.2 算法描述算法可以使用各种不同的方法来描述。l自然语言自然语言: :l程序流程图、程序流程图、N-SN-S图图等算法描述工具：l直接使用某种程序设计语言某种程序设计语言：l用伪码语言伪码语言的描述方法：第18页2022年5月5日1.3.3 算法的性能分析与度量时间复杂度 将一个算法转换成程序并在计算机上执行时，其运行所需要的时间取决于下列因素： 硬件的速度。 书写程序的语言。 编译程序所生成目标代码的质量。 问题的规模

9、。第19页2022年5月5日 时间复杂度时间复杂度 ：算法的时间复杂度T(n)表示为：其中ti表示语句i执行一次的时间，ci表示语句i的频度。 假设每条语句执行一次的时间均为一个单位时间，那么算法的时间耗费可简单表示为各语句的频度之和： ii( )tciT n 语句（）i( )ciT n 语句第20页2022年5月5日【例1-5】下面的程序段用来求两个n阶方阵A和B的乘积C。for(i=0;in;i+) /* n+1*/ for(j=0;jn;j+) /* n(n+1) */ Cij=0; /* n2*/ for(k=0;kn;k+) /* n2(n+1) */Cij+=Aik*Bkj; /*

10、 n3*/右边列出了各语句的频度，因而算法的时间复杂度T(n)为： T (n) (n+1)n(n+1)+ n2+ n2(n+1) + n3 =2n3+3n2+2n+1可见，T(n)是矩阵阶数n的函数。第21页2022年5月5日 而许多时候要精确地计算T(n)是困难的，很多算法的时间复杂度难以给出解析形式，或者非常复杂。 因此在实际应用中，往往放弃复杂的函数来表示确切的时间复杂度，而采用一些简单的函数来近似表示时间性能，这就是时间渐进复杂度。 定义（大记号）：设T(n)是问题规模n的函数f(n)，若存在两个正常数c和n0，使得对所有的n，nn0，有： T(n) cf(n)，则记为：T(n) (f

11、(n) 例 如 ， 一 个 程 序 的 实 际 执 行 时 间 为 T ( n ) 20n3+25n2+9，则T(n)(n3)。 使用大记号表示的算法的时间复杂度，称为算法的渐进时间复杂度（Asymptotic Complexity），简称时间复杂度。第22页2022年5月5日 通常用(1)表示常数计算时间。常见的渐进时间复杂度按数量级递增排列为： (1)(log2n)(n)(nlog2n) (n2)(n3)(2n) 第23页2022年5月5日【例1-6】冒泡排序。void BublleSort(int a , int n) for (i=0; in-1&swap; i+) swap=0; f

12、or(j=0; jaj+1) ajaj+1; swap=1; 选择交换相邻的两个元素“ajaj+1;”作为基本操作。 而n个元素组成的输入集可能有n!中排列情况，若各种情况等概率，则冒泡排序的平均时间复杂度T(n)=(n2)。 第24页2022年5月5日l 空间复杂度： 一个算法的空间复杂度（Space complexity）是指算法运行从开始到结束所需的存储量。 第25页2022年5月5日 算法运行所需的存储空间包括以下两部分： v固定部分 这部分空间与所处理数据的大小和个数无关，或者称与问题的实例的特征无关。主要包括程序代码、常量、简单变量、定长成分的结构变量所占的空间。v可变部分 这部分

13、空间大小与算法在某次执行中处理的特定数据的大小和规模有关。例如100个数据元素的排序算法与1000个数据元素的排序算法所需的存储空间显然是不同的。 第26页 例1：一个人要搬走10块石头，怎么搬呢？ 例2：计算从1到100的累加和。 例3：计算2n。 这些定义方式体现了一种逻辑思想，同时又是一种解决问题的方案。递归定义的问题，可以用递归的算法来求解。1.4 递归1.问题的提出第27页n ! =1 n=0 n*(n-1)! n0 Fib( n ) =n n=0,1 Fib(n-1)+ Fib(n-2) n=2 递归是一个过程或函数直接或间接调用自身的一种方法，它可以把一个大型的问题层层转化为一个

14、与原问题相似、但规模较小的问题来求解。 数学中阶乘的定义，n的阶乘可以如下表示： 再如，斐波那契（Fibonacci）数列指的是这样一个数列： 直接或间接调用自身的程序称为递归程序。 递归是一种特殊的嵌套调用，是某个函数调用自己，而不是另外一个函数。这是一种函数直接或者间接调用自身编程技术。1.4.1 递归的概念第28页1.4.2 递归调用的实现原理1.递归算法的构成能够用递归解决的问题应该满足以下三个条件：需要解决的问题可以化为一个或多个子问题来求解，而这些子问题的求解方法与原来的问题完全相同，只是在数量规模上不同；递归调用的次数必须是有限的；必须有结束递归的条件（边界条件）来终止递归。第2

15、9页递归算法的设计一般分为两步:第一步，将规模较大的原问题分解为一个或多个规模较小的而又类似于原问题特性的子问题，既将较大的问题递归地用较小的子问题来描述，解原问题的方法同样可以用来解决子问题；第二步，是确定一个或多个不需要分解、可直接求解的最小子问题。 第30页【算法2-1】计算n！的递归方法 public static int fact1 (int n) int temp； if (n= =0|) /递归的终结条件 return 1 ; else temp= n* fact (n-1)； /递归调用 return temp; 【算法2-2】计算斐波那契（Fibonacci）数列第n项的递归

16、方法 public static int fibonacci1 (int n) if (n= =0|n= =1) /递归的终结条件 return n ; else return(fibonacci (n-2)+ fibonacci (n-1)；/递归调用 第31页 2.递归调用的内部过程 【算法2-1】中求阶乘的问题，假设程序运行时，n4，那么程序的执行过程。第32页 从上面可以看出，递归调用的过程分为两个阶段： 1）递归过程：将原始问题不断转化为规模小了一级的新问题，从求4！变成求3！，变成求2！，最终达到递归终结条件，求1！； 2）回溯过程：从已知条件出发，沿递归的逆过程，逐一求值返回，直

17、至递归初始处，完成递归调用。 第33页2.递归调用的内部过程 在这两个阶段中，系统会分别完成一系列的操作。在递归调用之前，系统需完成三件事：为被调用过程的局部变量分配存储区；将所有的实参、返回地址等信息传递给被调用过程保存；将控制转移到被调过程的入口。 从被调用过程返回调用过程之前，系统也应完成三件工作：保存被调过程的计算结果；释放被调过程的数据区；依照被调过程保存的返回地址将控制转移到调用过程。 在计算机中，是通过使用系统栈（后面的章节会介绍“栈”）来完成上述操作的。第34页1.4.3 递归转换为非递归1.1.递归转化为递推递归转化为递推 当递归算法所涉及的数据定义形式是递归的情况下，通常可

18、以将递归算法转化为递推算法，用递归的边界条件作为递推的边界条件。比如求阶乘、斐波那契数列等。 递推也是一种从已知条件出发，用一种具体的算法，一步一步接近未知，一般采用循环结构，经常和枚举配合使用。递推算法在求解的过程中，每一个中间量都是已知，而且没有重复计算，运算简洁，但是书写代码和理解代码比较难。第35页【例1-8】 阶乘的递推算法 public static int fact2 (int n) int s=1; for( i=1; i=n; i+) s=s*i; return s; 【例1-9】斐波那契数列的递推算法 public static int fibo 2(int n) int f0=1, f1=1, f;