数据结构-第1次课第一章基本概念(更改的).ppt

为什么要学习数据结构？ 1、电子计算机的主要用途： 计算机是一门研究利用计算机进行信息表示和处理的科学。涉及：信息的表示和信息的处理。 ?早期： 主要用于数值计算。 ?后来： 处理逐渐扩大到非数值计算领域（能处理多种复杂的具有一定结构关系的数据）。 提高程序的效率、编写出一个“好”的程序。必须分析待处理的对象的特征及各对象之间存在的关系，这就是数据结构这门课所要研究的问题。 用计算机解决问题的过程 数据结构课程的形成和发展 形成阶段 60年代初期，“数据结构”有关的内容散见于操作系统、编译原理和表处理语言等课程。 1968年，美唐纳德·克努特(Donald Ervin Knuth)教授开创了数据结构的最初体系，《计算机程序设计技巧》第一卷《基本算法》 ，“数据结构”被列入美国一些大学计算机科学系的教学计划。 发展阶段： 数据结构的概念不断扩充，包括了网络、集合代数论、关系等“离散数学结构”的内容。 70年代后期，80年代初，我国高校陆续开设该课程。 《数据结构课程》所处的地位： 学习提要 掌握本课程所涉及到的基本名词、术语和概念，特别是数据的逻辑结构和存储结构之间的关系及性质。 了解抽象数据类型的定义、表示和实现方法。 理解算法设计的五个要素和基本要求；掌握算法效率的度量方法，着重学习算法的时间复杂度分析。 教学重点 ⑴数据、数据元素、数据项； ⑵逻辑结构和存储结构在概念上的联系与区别； ⑶数据结构及其三个组成部分； ⑷抽象数据类型和数据抽象； ⑸评价算法优劣的标准及方法。 在不同的编程环境中 存储结构可有不同的描述方法。 当用高级程序设计语言进行编程时，通常可用高级编程语言中提供的数据类型描述之。 例如：以三个带有次序关系的整数表示一个长整数时，可利用C++语言中提供的整数数组类型，定义长整数为： int long_int[3]; 抽象数据类型的表示和实现 抽象数据类型需要通过固有数据类型（高级编程语言中已实现的数据类型）来实现。 本章学习要点 熟悉各名词、术语的含义，掌握基本概念； 理解算法五个要素的确切含义； 掌握计算语句频度和估算算法时间复杂度的方法。 练习 1. 下面程序的时间复杂度为_________。 练习 2. 下面程序的时间复杂度为_________。 和算法执行时间相关的因素： 1．算法选用的策略 2．问题的规模 3．编写程序的语言 4．编译程序产生的机器代码的质量 5．计算机执行指令的速度 事先分析 但同一个算法用不同的语言实现，或者用不同的编译程序进行编译， 或者在不同的计算机上运行时，效率均不相同。因此，使用绝对的时间 单位衡量算法的效率是不合适的。应撇开这些与计算机硬件、软件有关的因素， 可以认为一个特定算法“运行工作量”的大小，只依赖于问题的规模（通常用整数n 表示），或者说，它是问题规模的函数。 一个特定算法的“运行工作量” 的大小，只依赖于问题的规模（通常用整数量n表示），或者说，它是问题规模的函数。 例１、for(i=1;i=n;++i) for(j=1;j=n;++j) { c[i][j]=0; for(k=1;k=n;++k) c[i][j]+=a[i][k]*b[k][j]; } 一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数f(n)，算法的时间量度记作 T(n)=O(f(n)) 它表示随问题规模n的增大，算法执行时间的增长率和 f(n)的增长率相同，称作算法的渐近时间复杂度，简称时 间复杂度。 由于是一个三重循环，每个循环从1到n，则总次数为: n×n×n=n3，时间复杂度为T(n)=O(n3) 为了便于比较同一问题的不同算法，通常的做法是，从算法中选取一种对于所研究的问题（或算法类型）来说是基本操作的原操作，以该操作重复执行的次数作为算法的时间量度。 语句重复执行的次数也称为语句的频度： 例２ {++x;s=0;} 将x自增看成是基本操作，则语句频度为１，即时间复杂度为Ｏ(1) 如果将s=0也看成是基本操作，则语句频度为1，其时间复杂度仍为Ｏ(1)，即常量阶。 例３ for(i=1;i=n;++i) {++x;s+=x;} 语句频度