1. 数据结构+算法=程序设计
程序设计：为计算机处理问题编制一组指令集
算法：处理问题的策略
数据结构：问题的数学模型
2.基本概念
- 数据结构包括：逻辑结构和物理结构
- 逻辑结构：(1). 集合 (2)线性结构 (3)树形结构 (4)网状结构
++集合++：结构中除了“同属于一个集合”外没有别的关系
++线性结构++：数据元素之间存在一对一的关系
++树形结构++：数据元素存在一对多的关系
++网状结构++：数据元素一对多的关系
- 物理结构：数据结构在计算机中的储存方式
(1)顺序储存结构(2)链式储存结构
++顺序储存结构++
++链式储存结构++
数据类型：体格值的集合和定义在这个值集上的一组操作
抽象数据类型(ADT)：指一个数学模型以及定义在该模型上的一组操作
ADT的定义格式
**ADT抽象数据类型名**{
**数据对象**：<数据对象的定义>
**数据关系**：<数据关系的定义>
**基本操作**：<数据对象的定义>
}
基本操作名（参数表）{
初始条件（初始条件的描述）
操作结果（操作结果的描述）
}
3.算法和算法分析
-
算法的5个特性
（1）有穷性：有穷步结束而且每一步时间合理
（2）确定性：指令要有确切的含义，只有唯一的一条执行路径
（3）可行性：足够基本
（4）输入：有0个或者多个输入
（5）输出：有一个或者多个输出
-
算法的4个设计要求
（1）正确性
四个层次：a.程序不含语法错误b.程序对于几组输入数据能得到满足规格的结果c.程序对于一些刁难苛刻的输入能得出满足规格结果d.程序对于一切合法输入都能得到满足规格的结果（2）可读性
（3）健壮性
（4）效率与低存储性
-
算法效率的度量--------- ==++时间复杂度++==
（1）事后统计方法
（2）事前统计方法
a.依据算法选用何种策略
b.问题规模 -
算法储存空间需求-------- ==++空间复杂度++==
（1）输入数据所需空间
（2）程序本身所占空间
（3）辅助变量所占空间
