数据结构 第1章.ppt

1、,2011年春季,数据结构和算法 Data Structure,青岛理工大学通信学院,芯片无所不在的时代,日本地震对中国汽车业影响： 主要存在问题的是微处理器芯片短缺(日立),芯片的广泛使用导致编程无所不在,普通机床,数控机床,您将来到社会做什么？如何生存呢？,您需要编程序吗？90%的可能性。您需要了解程序和相关的实现吗？100%的可能性。,课前的话-通信专业学生学习数据结构的意义,从实用的角度讲，通信无非是做硬件或做软件，两者都要用到数据结构。因为任何一个系统里都有数据，如何合理有效地组织数据，使系统速度更快，数据访问方式更灵活，这都严重依赖于是否选择了合适的数据结构。,从专业课程的角度讲，

2、数据结构的知识点在后继课程中会用到，例如计算机通信与网络、信息论与编码、现代通信与技术等等。,从就业的角度，从以往学生的情况来看，从事软件开发是一个比较容易找到工作的出口。,学时数：32（248） 学 分： 2 教 材：严蔚敏、吴伟民，数据结构（C语言版），清华大学出版社，1997年4月第1版 和2007年第二版都行 参考书： 1 严蔚敏、吴伟民、米宁，数据结构题集（C语言版），清华大学出版社，1999年7月,师生沟通渠道：,许小可 Email: 如何看待不同老师的作用：与时俱进,内 容 安 排,考试成绩,平时成绩（20%） （考勤、作业） 上机+综合程序设计（30%） 期末考试（50%）,课

3、程要求,第一层次：每种数据结构的适用性 第二层次： 每种数据结构和算法的白话实现 第三层次： 每种数据结构和算法的C语言编程实现 思考题： 数据结构的学习是否依赖于编程语言？ 这门课和C语言程序设计的关系是什么？,第1章 绪论 第2章 线性表 第3章 栈和队列 第4章 串 第5章 数组和广义表 第6章 树和二叉树 第7章 图 第9章 查找 第10章 排序,目 录,第一章 绪论,讨论5个问题：,1.1 什么是数据结构 1.2 学习数据结构的意义 1.3 数据结构涵盖的主要内容 1.4 什么是抽象数据类型 1.5 算法效率的度量,1.1什么是数据结构,例 某人骑自行车从A地先以每小时12千米的速度

4、下坡后，以每小时9千米的速度走平路到B地，共用55分钟.回来时，他以每小时8千米的速度通过平路后，以每小时4千米的速度上坡，从B地到A地共用1.5小时，求A、B两地相距多少千米？,答案：设坡路长为x千米，A、B两地相距为y千米，依题意列如下方程组：,求解步骤：审题 设未知元列方程解方程检验作结论,建立数学模型 设计算法 编程 测试调整,数值计算问题 操作对象：实型、整型、布尔型数据 数学模型：数学方程式（计算机的主要操作是解方程）,1.1.1非数值计算问题,例1 学生信息管理问题,人机对弈背景资料,卡斯帕罗夫与“深蓝”对弈(右为“深蓝”操作者),“人机对弈” 诸宸最终负于紫光之星,例2 人机对

5、奕问题,非数值计算问题,非数值计算问题,例3 田径赛时间安排问题,例3 田径赛时间安排问题,问题：设有六个比赛项目，规定每个选手至多可参加三个项目，有五人报名参加比赛（如表1所示）设计比赛日程表，使得在尽可能短的时间内完成比赛。,表1,（2）用顶点代表比赛项目 不能同时进行比赛的项目之间连上一条边,（3）某选手比赛的项目必定有边相连 （不能同时比赛）,表3,表2,解法：,（1）设用如下六个不同的代号代表不同的项目： 跳高 跳远 标枪 铅球 100米 200米 A B C D E F,1.1.2数据结构学科定义,数据结构是一门学科，它针对非数值计算的程序设计问题，研究计算机的操作对象以及它们之间

6、的关系（数学模型）和操作等等。,数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。,1.1.3术语简介:数据、数据元素、数据项,数据(data)对客观事物的符号表示，所有能被计算机识别、存储和处理的符号的集合（包括数字、字符、声音、图像等信息 ）。,数据元素(data element)是数据的基本单位，具有完整确定的实际意义(又称元素、结点，顶点、记录等）。,数据项(Data item)构成数据元素的项目，是具有独立含义的最小标识单位（又称字段、域、属性 等）。,三者之间的关系：数据 数据元素 数据项,1.1.4基本概念,数据结构是相互之间存在一种或多种特定关系的数据元素的 集

7、合，表示为：,Data_Structure=（D, R）,元素有限集,关系有限集,（数值或非数值）,数据对象(data object)-是性质相同的数据元素的集合，是数据的一个子集。 例如，字母字符对象是集合C=A,B,Z,结构是指同一数据元素类型中各元素之间存在的关系的集合。,数据结构是带结构的数据元素的集合.,思考：数据结构和算法之间的关系,例 在2行3列的二维数组a1, a2, a3, a4, a5, a6 中六个元素之间 存在两个关系:,行的次序关系: 列的次序关系:,row = ,col = ,a1 a3 a5 a2 a4 a6,a1 a2 a3 a4 a5 a6,数据结构示例,1.

8、2学习数据结构的意义,选择合适的数据结构解决应用问题,程序设计=好算法+好结构,例 学生信息查询问题,计算机内的数值运算依靠方程式，而非数值运算（如表、树、图等）则要依靠数据结构。,同样的数据对象，用不同的数据结构来表示，运算效率可能有明显的差异。,索引表,1.3 数据结构涵盖的内容,集合结构： 仅同属一个集合 线性结构: 一对一（1:1) 树 结 构: 一对多（1:n) 图 结 构: 多对多 (m:n),非线性,线 性,逻辑结构可细分为4类：,答：指数据元素之间的逻辑关系。即从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。,解释1： 什么叫数据的逻辑结构？,（1） S=(D, R

9、) D= a, b, c, d, e, f R=(a,e), (b,c), (c,a), (e,f), (f,d),解： 上述表达式可用图形表示为：,b c a e f d,此结构为线性的。,例：用图形表示下列数据结构，并指出它们是属于线性结构还是非线性结构。,课堂练习,课堂练习,（2） S=(D, R) D=di | 1i5 R=(di , dj ), ij,解：上述表达式可用图形表示为：,d1 d5 d2 d4 d3,该结构是非线性的。,解释2：什么叫数据的存储结构？,答：存储结构（亦称物理结构），是数据的逻辑结构在计算机存储器内的表示（或映像）。它依赖于计算机。,“数据元素”的映像 ？,

10、“关系”的映像 ？,用二进制位(bit)的位串表示数据元素,(321)10 = (501)8 = (101000001)2,A = (101)8 = (001000001)2,数据元素的映象方法：,数据元素的映象方法：从黑客帝国说起,隐喻,黑客帝国讲了个啥事呀？ 那盗梦空间呢？,存储结构可分为4大类：,顺序、链式、索引、散列,顺序存储结构借助元素在存储器中的相对位 置来表示数据元素间的逻辑关系 链式存储结构借助指示元素存储地址的指针表示数据元素间的逻辑关系,关系的映象方法：,（表示x, y的方法）,1536,元素2,1400,元素1,1346,元素3,元素4,1345,h,链式存储,答：在数据

11、的逻辑结构上定义的操作算法。 它在数据的存储结构上实现。,最常用的数据运算有 5 种：,插入、删除、修改、查找、排序,解释3：什么是数据的运算？,1.4 什么是抽象数据类型,1.4.1 数据类型与抽象数据类型的区别？ 1.4.2 抽象数据类型如何定义？ 1.4.3 抽象数据类型如何表示和实现？,讨论：,抽象数据类型和C伪码是学习数据结构的工具,数据类型高级语言中指数据变量的取值范围及其上可进行的操作的总称,例 C语言中，提供int, char, float, double等基本 数据类型，数组、结构体、共用体、枚举 等构造数据类型，还有指针、空(void)类 型等。用户也可用typedef 自

12、己定义数据类型,typedef struct int num; char name20; float score; STUDENT; STUDENT stu1,stu2, *p;,1.4.1 数据类型与抽象数据类型的区别,【例】从键盘输入两个整数，输出它们的和。 #include main() int a,b,c,d; /a,b,c,d是四个整型变量，分别对应于内存中一块16bit的区域，取值范围为-215 215-1 ； printf(输入两个整数：); scanf(%d%d, ,1.4.1 数据类型与抽象数据类型的区别,数据类型：是一个值的集合和定义在该值上的一组操作的总称。,抽象数据类型

13、：由用户定义，用以表示应用问题的数据模型。它由基本的数据类型构成，并包括一组相关的服务（或称操作）,它与数据类型实质上是一个概念，其特征是使用与实现分离，实行封装和信息隐蔽（独立于计算机）。但是范畴更广，包括用户在设计软件系统时自己定义的数据类型，可用于软件复用。,抽象的意义在于数据类型的数学抽象特性。,1.4.2 抽象数据类型如何定义,抽象数据类型可以用以下的三元组来表示： ADT = （D，R，P）,ADT抽象数据类型名 数据对象： 数据关系： 基本操作 ： ADT抽象数据类型名,ADT常用定义格式,数据对象,D上的关系集,D上的操作集,ADT 有两个重要特征:,数据抽象,用ADT描述程序

14、处理的实体时，强调的是其本质的特征、其所能完成的功能以及它和外部用户的接口（即外界使用它的方法）。,数据封装,将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节。,例如，抽象数据类型复数的定义：,数据对象： De1,e2e1,e2RealSet 数据关系： R1 | e1是复数的实数部分 | e2 是复数的虚数部分 ,ADT Complex ,基本操作：,AssignComplex( in;i+) y=y+1; for (j=0; j=(2*n); j+) x+; ,/* 1 * /,/* 2 * /,分析：语句的频度指的是该语句重复执行的次数。一个算法中所有语句的频度之和构成了该算法的运行时间。 语句1的频度是：n-1 语句2的频度是：,则该程序段的时间复杂度： T(n)=,空间复杂度,与时间复杂度类似，空间复杂度是指算法在计算机内执行时所需存储空间的度量。记作: S(n)=O(f(n) 我们一般所讨论的是除正常占用内存开销外的辅助存储单元规模。讨论方法与时间复杂度类似，不再赘述。,注意：算法的所有性能之间都存在着或多或少的相互影响，因此，当设计一个算法，特别是大型算法时，要综合考虑算法的各项性能、算法的使用频率、算法处理的数据量的