数据结构第1次课基本概念课件

1、第一章第一章 绪论绪论 计算机是一门研究利用计算机进行信计算机是一门研究利用计算机进行信息表示和处理的科学。息表示和处理的科学。 涉及：涉及： 信息的表示信息的表示 信息的处理信息的处理用计算机解决问题的过程用计算机解决问题的过程建立模型建立模型构造求解算法构造求解算法选择存储结构选择存储结构编写程序编写程序测试测试描述问题的共描述问题的共性性描述问题的求描述问题的求解方法解方法将问题涉及的数据将问题涉及的数据存储到计算机中存储到计算机中 早期：早期： 主要用于数值计算。主要用于数值计算。后来：后来： 处理逐渐扩大到非数值计算领域（能处理逐渐扩大到非数值计算领域（能处理多种复杂的具有一定结构关

2、系的数处理多种复杂的具有一定结构关系的数据）。据）。 早期：早期： 主要用于数值计算。主要用于数值计算。后来：后来： 处理逐渐扩大到非数值计算领域（能处理逐渐扩大到非数值计算领域（能处理多种复杂的具有一定结构关系的数处理多种复杂的具有一定结构关系的数据）。据）。登录号：书名：作者名：分类号：出版单位：出版时间：价格：书目卡片001高等数学樊映川S01002理论力学罗远祥L01003高等数学华罗庚S01004线性代数栾汝书S02书目文件按书名按作者名按分类号高等数学001，003理论力学002，.线性代数004，.樊映川001,华罗庚002,.栾汝书004,.L002,S001,003,索引表.

3、CEDABABACADBABCBDDADBDCEAEBECED用计算机解决问题的过程用计算机解决问题的过程建立模型建立模型构造求解算法构造求解算法选择存储结构选择存储结构编写程序编写程序测试测试描述问题的共描述问题的共性性描述问题的求描述问题的求解方法解方法将问题涉及的数据将问题涉及的数据存储到计算机中存储到计算机中面临的问题面临的问题复杂算法设计复杂算法设计?复杂存储结构？复杂存储结构？编程效率提高？编程效率提高？ 主要考虑的是设计出合适的数据结构及相主要考虑的是设计出合适的数据结构及相应的算法。应的算法。 即：首先要考虑对相关的各种信息如何表即：首先要考虑对相关的各种信息如何表示、组织和存

4、储？示、组织和存储？ 因此，简单说来，因此，简单说来，数据结构是一门研究非数据结构是一门研究非数值计算的程序设计问题中计算机的操作数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作的学科。对象以及它们之间的关系和操作的学科。数据结构课程的形成和发展数据结构课程的形成和发展 形成阶段形成阶段l6060年代初期，年代初期，“数据结构数据结构”有关的内容散见于操作系有关的内容散见于操作系统、编译原理和表处理语言等课程。统、编译原理和表处理语言等课程。l19681968年，美唐纳德年，美唐纳德克努特克努特(Donald Ervin Knuth)(Donald Ervin Knuth)教教

5、授开创了数据结构的最初体系，授开创了数据结构的最初体系，计算机程序设计技计算机程序设计技巧巧第一卷第一卷基本算法基本算法 ，“数据结构数据结构”被列入美国被列入美国一些大学计算机科学系的教学计划。一些大学计算机科学系的教学计划。 发展阶段：发展阶段：l数据结构的概念不断扩充，包括了网络、集合代数论数据结构的概念不断扩充，包括了网络、集合代数论、关系等、关系等“离散数学结构离散数学结构”的内容。的内容。l7070年代后期，年代后期，8080年代初，我国高校陆续开设该课程。年代初，我国高校陆续开设该课程。 计算机程序设计技巧计算机程序设计技巧,【作者作者】（美）克努特（美）克努特（D.E. Knu

6、th）著；）著；管纪文，苏运霖译管纪文，苏运霖译 1968年，年，计算机程序设计艺术计算机程序设计艺术(TAOCP)的第一卷正式出版了。的第一卷正式出版了。这一卷的标题叫这一卷的标题叫基本算法基本算法，但，但难度却并不低。据说比尔难度却并不低。据说比尔盖茨曾盖茨曾经花了几个月的时间读完这一卷，经花了几个月的时间读完这一卷，并且做了大量的练习，然后他说，并且做了大量的练习，然后他说，如果你想成为一个优秀的程序员，如果你想成为一个优秀的程序员，那就去读这个那就去读这个基本算法基本算法吧。高吧。高德纳本人的说法更犀利：要是看不德纳本人的说法更犀利：要是看不懂，就别当程序员。懂，就别当程序员。 将数据

7、的逻辑结构、存储结构以及将数据的逻辑结构、存储结构以及对每种结构所定义的操作组成了对每种结构所定义的操作组成了“数据结构数据结构”的主要内容。此后，各的主要内容。此后，各大学纷纷开设大学纷纷开设“数据结构数据结构”课程。课程。1.2 基本概念和术语基本概念和术语C C在不同的编程环境中在不同的编程环境中 存储结构可有不同的描述方法。存储结构可有不同的描述方法。 当用高级程序设计语言进行编程时，通当用高级程序设计语言进行编程时，通常可用高级编程语言中提供的数据类型常可用高级编程语言中提供的数据类型描述之。描述之。 例如：以三个带有次序关系的整数表示例如：以三个带有次序关系的整数表示一个长整数时，

8、可利用一个长整数时，可利用C+语言中提供语言中提供的整数数组类型，定义长整数为：的整数数组类型，定义长整数为： int long_int3;实现细节。如复数定义实现细节。如复数定义抽象数据类型的表示和实现抽象数据类型的表示和实现1.4 算法和算法分析算法和算法分析算法算法：是对特定问题求解步骤的一种描述，是指令的有限序列，：是对特定问题求解步骤的一种描述，是指令的有限序列，其中每一条指令表示一个或多个操作。其中每一条指令表示一个或多个操作。 算法具有以下五个特性：算法具有以下五个特性：（1）有穷性有穷性 一个算法必须总是在执行有穷步之后结束，且每一个算法必须总是在执行有穷步之后结束，且每一步都

9、在有穷时间内完成。一步都在有穷时间内完成。（2）确定性确定性 算法中每一条指令必须有确切的含义。不存在二义算法中每一条指令必须有确切的含义。不存在二义性。性。（3）可行性可行性 一个算法是可行的。即算法描述的操作都是可以通一个算法是可行的。即算法描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。过已经实现的基本运算执行有限次来实现的。（4）输入输入 一个算法有零个或多个输入，这些输入取自于某个特一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。定的对象集合。（5）输出输出 一个算法有一个或多个输出，这些输出是同输入有着一个算法有一个或多个输出，这些输出是同输入有着某些特定关

10、系的量。某些特定关系的量。1.4.2 1.4.2 算法设计的要求算法设计的要求评价一个好的算法有以下几个标准评价一个好的算法有以下几个标准: :(1)(1)正确性正确性: :算法应满足具体问题的需求。算法应满足具体问题的需求。(2)(2)可读性可读性: :算法应该好读。以有利于阅读者对程序的理解。算法应该好读。以有利于阅读者对程序的理解。(3)(3)健状性健状性: :算法应具有容错处理。当输入非法数据时，算法应算法应具有容错处理。当输入非法数据时，算法应对其作出反应，而不是产生莫名其妙的输出结果。对其作出反应，而不是产生莫名其妙的输出结果。(4)(4)效率与存储量需求效率与存储量需求 效率指的

11、是算法执行的时间；存储量效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般，这两者需求指算法执行过程中所需要的最大存储空间。一般，这两者与问题的规模有关。执行时间少，存储空间小。与问题的规模有关。执行时间少，存储空间小。1.4.3 算法效率的度量算法效率的度量 对一个算法要作出全面的分析可分成两种方法：对一个算法要作出全面的分析可分成两种方法：事先分析事先分析 求出该算法的一个时间界限函数求出该算法的一个时间界限函数事后统计事后统计 收集此算法的执行时间和实际占用空间的收集此算法的执行时间和实际占用空间的统计资料。缺陷：一是必须先运行依据算法编制的程统计资料。缺陷：

12、一是必须先运行依据算法编制的程序；二是所得时间的统计量依赖于计算机的硬件、软序；二是所得时间的统计量依赖于计算机的硬件、软件等环境因素，有时容易掩盖算法本身的优劣。件等环境因素，有时容易掩盖算法本身的优劣。例、例、for(i=1;i=n;+i) for(j=1;j=n;+j) cij=0; for(k=1;k=n;+k) cij+=aik*bkj; 一般情况下，算法中基本操作一般情况下，算法中基本操作重复执行的次数重复执行的次数是问是问题规模题规模n的某个函数的某个函数f(n)，算法的时间量度记作，算法的时间量度记作 T(n)=O(f(n) 它表示随问题规模它表示随问题规模n的增大，算法执行时

13、间的增长率和的增大，算法执行时间的增长率和 f(n)的增长率相同，称作算法的渐近时间复杂度，简称时的增长率相同，称作算法的渐近时间复杂度，简称时间复杂度。间复杂度。 由于是一个三重循环，每个循环从由于是一个三重循环，每个循环从1到到n，则总次数为则总次数为: nnn=n3，时间复杂度为时间复杂度为T(n)=O(n3) 为了便于比较同一问题的不同算法，通常的做法是为了便于比较同一问题的不同算法，通常的做法是，从算法中选取一种对于所研究的问题（或算法类型），从算法中选取一种对于所研究的问题（或算法类型）来说是来说是基本操作基本操作的原操作，以该操作重复执行的次数作的原操作，以该操作重复执行的次数作

14、为算法的时间量度。为算法的时间量度。语句重复执行的次数也称为语句的语句重复执行的次数也称为语句的频度频度：例例 +x;s=0; 将将x自增看成是基本操作，则语句频度为，即时间复杂度为自增看成是基本操作，则语句频度为，即时间复杂度为(1) 如果将如果将s=0也看成是基本操作，则语句频度为也看成是基本操作，则语句频度为1，其时间复杂度，其时间复杂度仍为仍为(1)，即常量阶。，即常量阶。例例 for(i=1;i=n;+i) +x;s+=x; 语句频度为：语句频度为：n其时间复杂度为：其时间复杂度为：O(n) 即时间复杂度为线性阶。即时间复杂度为线性阶。i=0: 赋值次赋值次i=1: 赋值赋值 2 次

15、次i=2: 赋值赋值3次次i=n-1:赋值赋值n次次.+1+2+3+n=(1+n)n/2=n2/2+n/2例例 for(i=1;i=n;+i)for(j=1;j=n;+j) +x;s+=x; 语句频度为：语句频度为：n2其时间复杂度为：其时间复杂度为：O(n2) 即时间复杂度为平方阶。即时间复杂度为平方阶。例例 for(i=0;i=n-1;+i) for(j=0;j=i;+j)aij=0; 其时间复杂度为：其时间复杂度为：O(n2) 即时间复杂度为平方阶。即时间复杂度为平方阶。 取语句频度增长最快的项。取语句频度增长最快的项。 以下几种计算算法时间的多项式是最常用的。其以下几种计算算法时间的多

16、项式是最常用的。其关系为：关系为： 指数时间的关系为：指数时间的关系为： O(2n)O(n!)0 ;i-) for(j=0;jaj+1) aj aj+1; 最好情况：最好情况：0次次 最坏情况：每次都换，最坏情况：每次都换， (n2) 由小到大排列由小到大排列i=n-1: j从从0到到n-2 交换交换n-1次次.+(n-1)+(n-2)+(n-3)+1=(n-1)n/2=n2/2-n/2i=n-2: j从从0到到n-3 交换交换n-2次次i=n-3: j从从0到到n-4 交换交换n-3次次i=1: j从从0到到0 交换交换1次次注意：时间与空间往往是对矛盾，要综合考虑。注意：时间与空间往往是对矛盾，要综合考虑。1.4.4算法的存储空间需求算法的存储空间需求空间复杂度空间复杂度:算法所需存储空间的度量，记作算法所需存储空间的度量，记作: S(n)=O(f(n) 其中其中n为问题的规模为问题的规模(或大小或大小)本章学习要点本