第一章概论
基本概念和术语
数据是信息的载体能被计算机识别存储和加工处理
数据元素是数据的基本单位可由若干个数据项组成数据项是具有独立含义的最小标识单位
数据结构包括)数据的逻辑结构从逻辑关系上描述数据与数据存储无关独立于计算机;
)数据的存储结构是逻辑结构用计算机语言的实现依赖于计算机语言
)数据的运算定义在逻辑结构上每种逻辑结构都有一个运算集合常用的检索/插入/删除/更新/排序
数据类型是一个值的集合及在值上定义的一组操作的总称分为原子类型和结构类型
抽象数据类型是抽象数据的组织和与之相关的操作其优点是将数据和操作封装在一起实现了信息隐藏
ADT是在概念层上描述问题;类是在实现层上描述问题;在应用层上操作对象(类的实例)解决问题
数据的逻辑结构有)线性结构若结构是非空集则仅有一个开始和终端结点并且所有结点最多只有一个直接前趋和后继
)非线性结构一个结点可能有多个直接前趋和后继
数据的存储结构有)顺序存储把逻辑相邻的结点存储在物理上相邻的存储单元内
)链接存储结点间的逻辑关系由附加指针字段表示
)索引存储存储结点信息的同时建立附加索引表有稠密索引和稀疏索引
)散列存储按结点的关键字直接计算出存储地址
学习数据结构的意义
程序设计的实质是选择一个好的数据结构设计一个好的算法算法取决于描述实际问题的数据结构
算法的描述和分析
算法是任意一个良定义的计算过程以一个或多个值输入并产生一个或多个值输出是用来解决一个计算问题的工具
问题的输入实例是满足问题陈述中所给出的限制为计算该问题的解所需要的所有输入构成
评价算法的好坏是)算法是正确的;)要考虑算法所耗的时间存储空间(辅助存储)易于理解编码调试
算法所耗时间是每条语句执行时间之和每条语句的执行时间是该语句执行次数与执行时间的乘积
算法求解问题的输入量称问题的规模算法的时间复杂度T(n)是该算法的时间耗费是求解问题规模n的函数当问题规模趋向无穷大时把T(n)的数量阶称算法的渐进时间复杂度记为O(n)
常见的时间复杂度排列为常数阶对数阶线性阶线性对数阶平方阶立方阶K次方阶指数阶
算法的空间复杂度S(n)是该算法的空间耗费是求解问题规模n的函数算法的渐进空间复杂度简称空间复杂度
算法的时间复杂度和空间复杂度合称算法的复杂度
附结二:
第一章 概 论
*************************************************************************************
数据就是指能够被计算机识别存储和加工处理的信息的载体
数据元素是数据的基本单位可以由若干个数据项组成数据项是具有独立含义的最小标识单位
*************************************************************************************
数据结构的定义·逻辑结构从逻辑结构上描述数据独立于计算机·线性结构一对一关系
·线性结构多对多关系
·存储结构是逻辑结构用计算机语言的实现·顺序存储结构如数组
·链式存储结构如链表
·索引存储结构·稠密索引每个结点都有索引项
·稀疏索引每组结点都有索引项
·散列存储结构如散列表
·数据运算·对数据的操作定义在逻辑结构上每种逻辑结构都有一个运算集合
·常用的有检索插入删除更新排序
*************************************************************************************
数据类型是一个值的集合以及在这些值上定义的一组操作的总称·原子类型由语言提供
·结构类型由用户借助于描述机制定义是导出类型
抽象数据类型ADT·是抽象数据的组织和与之的操作相当于在概念层上描述问题
·优点是将数据和操作封装在一起实现了信息隐藏
*************************************************************************************
程序设计的实质是对实际问题选择一种好的数据结构设计一个好的算法算法取决于数据结构
*************************************************************************************
算法是一个良定义的计算过程以一个或多个值输入并以一个或多个值输出
评价算法的好坏的因素·算法是正确的;
·执行算法的时间;
·执行算法的存储空间(主要是辅助存储空间);
·算法易于理解编码调试
*************************************************************************************
时间复杂度是某个算法的时间耗费它是该算法所求解问题规模n的函数
渐近时间复杂度是指当问题规模趋向无穷大时该算法时间复杂度的数量级
评价一个算法的时间性能时主要标准就是算法的渐近时间复杂度
算法中语句的频度不仅与问题规模有关还与输入实例中各元素的取值相关
时间复杂度按数量级递增排列依次为常数阶O()对数阶O(logn)线性阶O(n)线性对数阶O(nlogn)平方阶O(n^)立方阶O(n^)……k次方阶O(n^k)指数阶O(^n)
空间复杂度是某个算法的空间耗费它是该算法所求解问题规模n的函数
算法的时间复杂度和空间复杂度合称算法复杂度
