数据结构 第1章(精品·公开课件).ppt

An Introduction to Database Systenm 2011年春季 芯片无所不在的时代 日本地震对中国汽车业影响： 主要存在问题的是微处理器芯片短缺(日立) 芯片的广泛使用导致编程无所不在 普通机床 您将来到社会做什么？如何生存呢？ 您需要编程序吗？90%的可能性。您需要了解程序和相关的实现吗？100%的可能性。 课前的话---通信专业学生学习数据结构的意义 从实用的角度讲，通信无非是做硬件或做软件，两者都要用到数据结构。因为任何一个系统里都有数据，如何合理有效地组织数据，使系统速度更快，数据访问方式更灵活，这都严重依赖于是否选择了合适的数据结构。 考试成绩 平时成绩（20%） （考勤、作业） 上机+综合程序设计（30%） 期末考试（50%） 课程要求 第一层次：每种数据结构的适用性 第二层次： 每种数据结构和算法的白话实现 第三层次： 每种数据结构和算法的C语言编程实现 思考题： 数据结构的学习是否依赖于编程语言？ 这门课和C语言程序设计的关系是什么？ 第一章 绪论 1.1 什么是数据结构 1.2 学习数据结构的意义 1.3 数据结构涵盖的主要内容 1.4 什么是抽象数据类型 1.5 算法效率的度量 1.1什么是数据结构 例 某人骑自行车从A地先以每小时12千米的速度下坡后，以每小时9千米的速度走平路到B地，共用55分钟.回来时，他以每小时8千米的速度通过平路后，以每小时4千米的速度上坡，从B地到A地共用1.5小时，求A、B两地相距多少千米？ 1.1.1非数值计算问题 人机对弈背景资料 例2 人机对奕问题 非数值计算问题 1.1.2数据结构学科定义 1.1.4基本概念 数据对象(data object)---是性质相同的数据元素的集合，是数据的一个子集。 例如，字母字符对象是集合C={‘A’,’B’,…,’Z’} 1.2学习数据结构的意义 1.3 数据结构涵盖的内容 （1） S=(D, R) D={ a, b, c, d, e, f } R={(a,e), (b,c), (c,a), (e,f), (f,d)} 课堂练习 解释2：什么叫数据的存储结构？ 　　　答：存储结构（亦称物理结构），是数据的逻辑结构在计算机存储器内的表示（或映像）。它依赖于计算机。 数据元素的映象方法： 数据元素的映象方法：从黑客帝国说起 隐喻 关系的映象方法： 答：在数据的逻辑结构上定义的操作算法。 它在数据的存储结构上实现。 数据类型—高级语言中指数据变量的取值范围及其上可进行的操作的总称 【例】从键盘输入两个整数，输出它们的和。 #include stdio.h main() { int a,b,c,d; //a,b,c,d是四个整型变量，分别 对应于内存中一块16bit的区 域，取值范围为-215~ 215-1 ； printf(输入两个整数：); scanf(%d%d,a,b); c=a+b;//”+”和”-”是int型变量的操作； d=a-b; printf(和=%d\n, c); } 抽象数据类型可以通过固有的数据类型（如整型、实型、字符型等）来表示和实现。 提示： 1.5.1 什么是算法？如何评判算法的好坏？ 1.5.2 时间复杂度和空间复杂度如何表示？ 1.5.3 计算举例 例1.4 一个不是算法的例子 (1)begin (2)n=0 (3)n=n+1 (4)repeat (3) (5)end 用依据该算法编制的程序在计算机上执行所消耗的时间来度量。 1.5.2 时间复杂度和空间复杂度如何表示？ 设解决一个问题的规模为n（比如排序问题中，n表示待排序元素的个数；在矩阵运算中，n表示矩阵的阶数；在图的遍历中，n表示图中的顶点数），那么算法的时间量度可记为T (n).当n不断变化时,T(n)也会不断变化,但有时我们想知道它变化时呈什么规律. 3n+2=O(n) 因为 3n+2?4n for n?2 6*2n+n2=O(2n) 因为6*2n+n2 ?7* 2n for n?4 什么是同数量级函数？ 分析：语句的频度指的是该语句重复执行的次数。一个算法中所有语句的频度之和构成了该算法的运行时间。 语句1的频度是：n-1 语句2的频度是： 注意：算法的所有性能之间都存在着或多或少的相互影响，因此，当设计一个算法，特别是大型算法时，要综合考虑算法的各