数据结构教学课件吴伟民编著.pptVIP

数据结构; 总学时：60 讲课学时：50 实验学时：10 教材： 《数据结构C语言版》严蔚敏、吴伟民 -----清华大学出版社 《数据结构C语言篇》习题与解析 李春葆 -----清华大学出版社;课程要求;上机安排 上机地点：机房 上机时间： 上机内容： 要求: 所有作业必须独立完成 算法作业必须经上机调试通过 上机考勤3次缺席，按不及格处理 发现上机时间上网，按缺席一次处理;课程重要性; 1.1 什么是数据结构 1.2 基本概念和术语 1.3 抽象数据类型的表示和实现 1.4 算法和算法分析;教学目的：（1）了解数据结构及算法的概念；（2）掌握计算语句频度和估算算法时间复杂度的方法。教学的重点和难点：估算算法时间复杂度。 ;1.1 什么是数据结构 什么是程序、软件？ N.沃思（Niklaus Wirth)教授提出： 程序=算法+数据结构 程序设计:为计算机处理问题编制一组指令集 算法:处理问题的策略 数据结构:问题的数学模型 软件=程序+文档（软件工程的观点）;电子计算机的主要用途： ?早期： 主要用于数值计算。 ?后来： 处理逐渐扩大到非数值计算领域（能处理多种复杂的具有一定结构关系的数据）。;数值计算解决问题的一般步骤： 数学模型→选择计算机语言→编出程序→测试→最终解答。 数值计算的关键是：如何得出数学模型（方程）？ 程序设计人员比较关注程序设计的技巧。 非数值计算问题： 数据元素之间的相互关系一般无法用数学方程加以描述;;;;求解非数值计算的问题： 主要考虑的是设计出合适的数据结构及相应的算法。 即：首先要考虑对相关的各种信息如何表示、组织和存储？ 因此，可以认为：数据结构是一门讨论“描述现实世界实体的数学模型(非数值计算)及其上的操作在计算机中如何表示和实现”的学科。;数据结构课程的形成和发展： 形成阶段： 60年代初期，“数据结构”有关的内容散见于操作系统、编译原理和表处理语言等课程。1968年，“数据结构”被列入美国一些大学计算机科学系的教学计划。 发展阶段： 数据结构的??念不断扩充，包括了网络、集合代数论、关系等“离散数学结构”的内容。 70年代后期，我国高校陆续开设该课程。 ;《数据结构课程》所处的地位： ;1.2 基本概念和术语 数据(Data):是对信息的一种符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素(Data Element):是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。 三者之间的关系：数据 数据元素 数据项 例：班级通讯录 个人记录 姓名、年龄…… 数据对象(Data Object)：是性质相同的数据元素的集合。是数据的一个子集。; 序偶：由两个具有给定次序的元素x和y所组成的序列,记为x,y。 关系：是指集合中元素之间的相互联系。 是集合中某些元素所构成的序偶的集合。 例如 D={A，B，C，D，E} R={A,D,D,C,D,E}和 R={A,C,B,D,A,D} 都是D上的一种关系。 ;数据结构：;又例，在2行3列的二维数组{a1, a2, a3, a4, a5, a6} 中六个元素之间 存在两个关系:;再例，在一维数组 {a1, a2, a3, a4, a5, a6} 的数据元素之间存在如下的次序关系:;数据的逻辑结构;数据的逻辑结构;数据的逻辑结构;数据的逻辑结构;数据的逻辑结构;数据结构的形式定义为:;例：用图形表示下列数据结构，并指出它 们是属于线性结构还是非线性结构。;（2） S=(D, R) D={di | 1≤i≤5} R={di , dj , ij};数据的物理结构;在不同的编程环境中，;逻辑结构和存储结构之间的关系;数据的运算(算法);;数据类型：是一个值的集合和定义在该值上 的一组操作的总称。;抽象数据类型可以用以下的三元组来表示： ADT = （D，S，P） 数据对象 D上的关系集 D上的操作集 ;例如，抽象数据类型复数的定义：;基本操作：; GetIm