PPT《*》

1 6

60 行:结点(对象、记录、元组等);

列:数据项(属性、域、字段等) 逻辑结构:开始结点?终端结点?内部结点? 结点之间的逻辑关系:有且仅有1个开始结点和1个终端结点,表中任1结点最多只有1个直接前驱和1个直接后继-----线性关系存储结构:用数组实现,还是用指针实现?运算:创建、插入、删除、查找等 * §1.1 基本概念和术语 逻辑结构线性结构:任一结点最多只有1个直接前驱和1个直接后继非线性结构:一结点可有多个直接前驱和多个直接后继集合结构:元素间无关系,只有元素是否属于集合的关系存储结构 (1)顺序存储方法 逻辑上相邻的结点存储在物理位置上相邻的存储单元里 结点间的逻辑关系由存储单元的邻接关系来体现 借助于数组描述 应用于线性的数据结构,非线性的数据结构的线性化 * §1.1 基本概念和术语 存储结构 (2)链接存储方法 该方法不要求逻辑上相邻的结点在物理位置上亦相邻 借助于指针来表示结点间的逻辑关系 (3)索引存储方法 在存储结点信息的同时,建立附加的索引表.表中每项称为索引项 (关键字,地址)稠密索引:每个结点对应1个索引项 稀疏索引:一组结点对应1个索引项 (4)散列存储方法 根据结点的Key直接计算出该结点的存储地址. * 数据结构的主要运算⑴ 建立(Create)一个数据结构;

⑵ 消除(Destroy)一个数据结构;

⑶ 从一个数据结构中删除(Delete)一个数据元素;

⑷ 把一个数据元素插入(Insert)到一个数据结构中;

⑸ 对一个数据结构进行访问(Access);

⑹ 对一个数据结构(中的数据元素)进行修改(Modify);

⑺ 对一个数据结构进行排序(Sort);

⑻ 对一个数据结构进行查找(Search). §1.1 基本概念和术语 * §1.1 基本概念和术语 数据结构3方面之联系同一逻辑结构的不同存储结构,则用不同名称称谓 例如, 线性表?顺序表,链表,散列表运算不同,称谓也不同 线性表?栈、队列? 顺序栈、顺序队列数据的逻辑结构和物理结构是密不可分的两个方面,一个算法的设计取决于所选定的逻辑结构,而算法的实现依赖于所采用的存储结构.在C语言中,用一维数组表示顺序存储结构;

用结构体类型表示链式存储结构. * 数据的逻辑结构 非线性结构 集合 图状结构 有向图 无向图 树形结构 一般树 二叉树 线性结构 一般线性表 线性表推广 广义表 数组 串 受限线性表 栈和队列 数据逻辑结构层次关系图 逻辑结构与所采用的存储结构 线性表 树图顺序存储结构 链式存储结构 复合存储结构 逻辑结构 物理结构 * §1.1 基本概念和术语 数据类型:是一个值的集合以及定义在这些值上的一组操作的总称,可看作是高级语言提供的数据结构原子类型:值不可分,一般是基本的预定义类型 int,char等,定义了 + , - 等结构类型:可供用户定义的新类型,构造类型、导出类型、派生类型等 由基本类型组织而成,如数组、struct等*§1.1 基本概念和术语 抽象数据类型(Abstract Data Type) 抽象数据的组织和与之相关的操作,可看作是数据的逻辑结构及其在逻辑结构上定义的抽象操作特点①封装与隐藏:将数据和操作封装在一起,内部结构和实现细节对外屏蔽,实现信息隐藏②抽象:用户只能通过ADT里定义的接口和说明来访问和操作数据.ADT和类的概念反映了程序设计的两层抽象:?概念层(抽象)---ADT、类说明?实现层---类实现,相当于普通类型?应用层----如main(){…},通过操作对象解决实际问题 * §1.1 基本概念和术语 抽象数据类型(Abstract Data Type) ADT ADT_Name{ Data: 数据结构(数据对象和数据关系)说明 Operations:Constructor://构造函数,创建对象实例 Operation1://用C++或C函数原型描述 input:Preconditions://初始条件,执行本操作前系统 //需满足的状态 process://对数据执行的操作 output://对返回数据的说明 Postconditions://执行本操作后系统的状态 Operation2: } * 例:抽象数据类型复数的定义ADT Complex {数据对象:D={e1,e2|e1,e2∈RealSet }数据关系:R1={ | e1是复数的实数部分,e2 是复数的虚数部分}基本操作:InitComplex( &