文档介绍：第一章数据结构基本概念
1、基本概念:理解什么是数据、数据对象、数据元素、数据结构、数据的逻辑结构与物理结构、逻辑结构与物理结构间的关系。
2、面向对象概念:理解什么是数据类型、抽象数据类型、数据抽象和信息隐蔽原则。了解什么是面向对象。由于目前关于这个问题有许多说法,我们采用了一种最流行的说法,即Coad与Yourdon 给出的定义:面向对象= 对象+ 类+ 继承+ 通信。
要点:
·抽象数据类型的封装性
·面向对象系统结构的稳定性
·面向对象方法着眼点在于应用问题所涉及的对象
3、数据结构的抽象层次:理解用对象类表示的各种数据结构
4、算法与算法分析:理解算法的定义、算法的特性、算法的时间代价、算法的空间代价。
要点:·算法与程序的不同之处需要从算法的特性来解释
·算法的正确性是最主要的要求
·算法的可读性是必须考虑的
·程序的程序步数的计算与算法的事前估计
·程序的时间代价是指算法的渐进时间复杂性度量
什么是数据结构
计算机解决问题的步骤
实际问题------数据模型------算法------程序------结果
工程师数学家程序员
计算机的用途
科学计算(数值运算):解方程(组),函数求值,概率统计等
非数值运算:字符,表格,图像,声音等
计算机的用途——数值运算
水库大坝的应力计算
预报人口增长
天气预报
数据结构的定义
描述非数值计算问题的模型是——
如表、树、图之类的数据结构
数据结构是——
研究计算机的操作对象(数据)以及它们之间的关系和操作等的学科
基本概念和术语
数据:计算机程序处理的符号的总称。
数据元素:数据的基本单位。
通常作为一个整体进行处理。
数据项:数据的不可分割的最小单位。
一个数据元素可以由若干个数据项构成。
数据对象:性质相同的数据元素的集合。
数据结构:相互间存在一种或多种关系的数据元素的集合。
数据结构的数学定义
数据结构是一个二元组
Data_Structure=(D,S)
D—数据元素的有限集合
S—定义在D上得关系的有限集合
例如
Complex=(C,R)
C={(c1,c2)|c1,c2是实数}
R={P|P是定义在C上的关系,<c1,c2>表示c1是实部,c2是虚部}
逻辑结构和物理结构
逻辑结构:数据元素之间的逻辑关系
物理结构:数据结构在计算机中的表示,又称存储结构
算法的设计取决于选定的逻辑结构
算法的事先依赖于采用的存储结构
数据类型与抽象的数据类型
数据类型(Data Type):
值的集合以及定义在这个集合上打的一组操作。
例如:C语言中的整数类型
抽象数据类型(ADT)
数学模型以及定义在该模型上的一组操作。
与其在计算机中的表示和实现无关。
ADT可用三元组表示:(D,S,P)
D—数据对象; S—D上的关系; P—对D的基本操作集
抽象数据类型三元组的定义
ADT Triplet{
数据对象:D={e1,e2,e3|e1,e2,e3属于Elemset(定义了关系的某个集合)}
数据关系:R1={<e1,e2>|<e2,e3>}
基本操作:
—InitTriplet(&T,v1,v2,v3)
—