《数据结构课件吴伟民编著.ppt

数据结构 1.1 什么是数据结构 1.2 基本概念和术语 1.3 抽象数据类型的表示和实现 1.4 算法和算法分析 1.1 什么是数据结构 什么是程序、软件？ N.沃思（Niklaus Wirth)教授提出： 程序=算法+数据结构 程序设计:为计算机处理问题编制一组指令集 算法:处理问题的策略 数据结构:问题的数学模型 软件=程序+文档（软件工程的观点） 电子计算机的主要用途： ?早期： 主要用于数值计算。 ?后来： 处理逐渐扩大到非数值计算领域（能处理多种复杂的具有一定结构关系的数据）。 数值计算解决问题的一般步骤： 数学模型→选择计算机语言→编出程序→测试→最终解答。 数值计算的关键是：如何得出数学模型（方程）？ 程序设计人员比较关注程序设计的技巧。 非数值计算问题： 数据元素之间的相互关系一般无法用数学方程加以描述 求解非数值计算的问题： 主要考虑的是设计出合适的数据结构及相应的算法。 即：首先要考虑对相关的各种信息如何表示、组织和存储？ 因此，可以认为：数据结构是一门讨论“描述现实世界实体的数学模型(非数值计算)及其上的操作在计算机中如何表示和实现”的学科。 数据结构课程的形成和发展： 形成阶段： 60年代初期，“数据结构”有关的内容散见于操作系统、编译原理和表处理语言等课程。1968年，“数据结构”被列入美国一些大学计算机科学系的教学计划。 发展阶段： 数据结构的概念不断扩充，包括了网络、集合代数论、关系等“离散数学结构”的内容。 70年代后期，我国高校陆续开设该课程。 《数据结构课程》所处的地位： 1.2 基本概念和术语 数据(Data):是对信息的一种符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素(Data Element):是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。 三者之间的关系：数据 数据元素 数据项 例：班级通讯录 个人记录 姓名、年龄…… 数据对象(Data Object)：是性质相同的数据元素的集合。是数据的一个子集。 数据的逻辑结构 逻辑结构是从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。 数据的逻辑结构 数据结构从逻辑上分为四类： ⑴ 集合：数据元素之间就是 “属于同一个集合” ； 数据的逻辑结构 数据结构从逻辑上分为四类： ⑴ 集合：数据元素之间就是 “属于同一个集合” ； ⑵ 线性结构：数据元素之间 存在着一对一的线性关系； 数据的逻辑结构 数据结构从逻辑上分为四类： ⑴ 集合：数据元素之间就是 “属于同一个集合” ； ⑵ 线性结构：数据元素之间存在着一对一的线性关系； ⑶ 树结构：数据元素之间存在着一对多的层次关系； 数据的逻辑结构 数据结构从逻辑上分为四类： ⑴ 集合：数据元素之间就是 “属于同一个集合” ； ⑵ 线性结构：数据元素之间存在着一对一的线性关系； ⑶ 树结构：数据元素之间存在 着一对多的层次关系； ⑷ 图结构：数据元素之间存在 着多对多的任意关系。 例：用图形表示下列数据结构，并指出它 们是属于线性结构还是非线性结构。 （1） S=(D, R) D={ a, b, c, d, e, f } R={a,e, b,c, c,a, e,f, f,d} （2） S=(D, R) D={di | 1≤i≤5} R={di , dj , ij} d1 d5 d2 d4 d3 数据的物理结构 物理结构亦称存储结构，是数据的逻辑结构在计算机存储器内的表示（或映像）。它依赖于计算机。 逻辑结构和存储结构之间的关系 数据的逻辑结构属于用户视图，是面向问题的，反映了数据内部的构成方式；数据的存储结构属于具体实现的视图，是面向计算机的。 一种数据的逻辑结构可以用多种存储结构来存储，而采用不同的存储结构，其数据处理的效率往往是不同的。 数据的运算(算法) 在数据的逻辑结构上定义的操作算法。 它在数据的存储结构上实现。 1.3 抽象数据类型的表示和实现 抽象数据类型可以通过固有的数据类型（如整型、实型、字符型等）来表示和实现。