数据结构(严蔚敏)读书笔记 (1): 绪论
行文逻辑:数据概念 — 加入数据间的关系(数据结构) — 加入数据间的操作(数据类型) — 算法概念
数据的基本概念和术语
数据,数据元素,数据项,数据对象
数据:
数据元素:数据元素用于完整的描述一个对象,也称为元素,记录。(描述型数据的集合)
数据项:数据项是组成数据元素的最小单位,表示数据元素中的属性(学生生日,成绩,班级) 。 (数据在特征上的集合)
数据对象:数据对象是性质相同的数据元素的集合,只要集合内元素的性质均相同,都可称之为一个数据对象。(数据元素的集合)
关系:数据对象思各数据元素的集合,数据元素是各数据项的集合。类比:(无成员函数)类 - (无成员函数)对象 - 成员变量
数据结构
数据类型
|| 类型暗含了数据的 “取值范围,储存方式” 和 “允许的操作”
|| 数据类型就是 值的集合(数据项的集合 / 数据元素 ) 和 这些值上的一组操作 的总称
带操作的数据对象 = 数据类型 (成员函数 + 成员变量 = 类)
算法
算法的定义和特性
|| 算法的定义:是解决某个问题的有限长的操作序列
|| 五个特性:有穷性,确定性,可行性,输入,输出
—> 算法判定:先有: 正确性,高效性 / 后有: 可读性,健壮性
算法的时间复杂度
|| 影响时间的因素:问题规模,语句频率,最好最坏情况
|| 取问题规模n的代表执行次数的函数f(n) 的 同阶无穷大函数 大O 来表示 算法的时间复杂度
tip: 与问题规模n无关的for循环,仅代表次数,不影响大O复杂度