一、基本概念

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）辅助变量所占空间