数据结构基本概念

数据 信息的载体 计算机识别和处理的符号的集合
数据元素 数据的基本单位 由数据项组成
数据对象  具有相同性质的数据元素的集合，数据的一个子集
数据类型  一个值得集合和定义在集合上的一组操作的总称 
原子类型（不可再分）  机构类型

抽象数据类型


在任何问题中，数据元素都不是孤立存在的，
而是在它们之间存在着某种关系，
这种数据元素相互之间的关系称为结构 Structure 

数据结构是相互之间存在一种或多种特定关系的数据元素的集合 

数据结构包括三方面的内容
逻辑结构 存储结构  数据的运算 

数据的逻辑结构和存储结构是密不可分的两个方面
一个算法的设计取决于所选定的逻辑结构
而算法的实现依赖于所采用的存储结构 

逻辑结构
逻辑结构是指数据元素之间的逻辑关系，即从逻辑关系上描述数据
它与数据的存储无关，独立于计算机

数据的逻辑结构分为 线性结构 和 非线性结构

集合 结构中的数据元素之间除了“同属于一个集合”的关系外，无其他关系 
线性结构 结构中的数据元素之间只存在一对一的关系。比如排队
树形结构 结构中的数据元素之间存在一对多的关系。比如家族族谱
图状结构或网状结构 结构中的数据元素之间存在多对多的关系 

物理结构
存储结构是指数据结构在计算机中的表示（又称映像），也称物理结构
它包括 数据元素的表示 和 关系的表示
数据的存储结构是逻辑结构用计算机语言的实现，它依赖于计算机语言
数据的存储结构主要有：顺序存储 链式存储 索引存储  散列存储
顺序存储 存储的物理位置相邻 
链接存储 存储的物理位置未必相邻，通过记录相邻元素的物理位置来找到相邻元素
索引存储 类似于目录 
散列存储 通过关键字直接计算出元素的物理地址 

算法的定义
对特定问题求解步骤的描述 指令的有限序列

算法的五个特征
有穷性  有限步之后结束
确定性  不存在二义性，即没有歧义
可行性  比如受限于计算机的计算能力，有些算法虽然理论上可行，但实际上无法完成
输入 
输出 

算法的复杂度

时间复杂度
衡量算法随着问题规模增大，算法执行时间增长的快慢
T(n)=O(f(n)) f(n)是算法中基本运算的频度 
一般考虑最坏情况下的时间复杂度

空间复杂度
衡量算法随着问题规模增大，算法所需空间的快慢
S(n)=O(g(n))  

复杂度量级
多项式阶  非多项式阶

O(1)（常数阶） —— 代码中没有循环等复杂结构
O(logN)（对数阶）
O(n)（线性阶） —— 代码中最高阶为单层循环
O(nlogN)（线性对数阶）
O(n^2)（平方阶）
O(n^3)（立方阶）
O(n^k)（k次方阶；k>3）

O(2^n)（指数阶）
O(n!)（阶乘阶）

正确性 可读性 健壮性 效率  空间需求