数据结构和算法（第二节课）

插入上一节课概念小节

抽象数据类型（ADT）

抽象数据类型{数据对象，数据关系，基本操作}

其中基本操作又包括：初始条件和操作结果

抽象数据类型的表述与实现

• 抽象数据类型可以通过固有的数据类型（整型、实型、字符型）来表示和实现

例如定义一个抽象数据类型“复数”的实现

构造复数数据类型

typedef struct{
    float realpart; //实部
    float imaqpart //虚部
}Complex // 定义复数抽象数据类型

构造复数

    void assign(Complex *A,float real,float imag){
        A->realpart = real; //实部赋值
        A->imagpart = imag; //虚部赋值
}

实现复数的加法

    void add(Complex *c,Complex A,Complex B){
        c->realpart = A.realpart +B.realpart; //实部相加
        c->imagpart = A.imagpar+B.imagpart;//虚部相加
}

算法的定义

• 对特定问题求解的方法和步骤的一种描述，它是指令的有限序列，其中每个指令表示一个或者多个操作

程序的定义

• 程序是某种程序设计语言对算法的具体实现
• 程序 = 数据结构 + 算法

算法的描述

• 自然语言：英语、中文
• 流程图：传统流程图、NS流程图
• 伪代码：类语言：类C语言
• 程序代码：c++等

算法的特性

1. 有穷性
2. 确定性
3. 可行性
4. 输入
5. 输出

算法的设计要求

1. 正确性
2. 可读性
3. 健壮性
4. 高效性

算法分析

• 除了需要具备算法的设计要求和特性之外，主要考虑算法的效率
• 算法的效率主要从两方面来考虑
  1. 时间效率
  2. 空间效率
• 时间效率和空间效率有时候是矛盾的

算法的时间效率度量

• 算法时间效率度量分为 事后统计和事前分析

• 比较时间效率的时候通常考虑时间复杂度（f(n)，当n趋向于无穷，即算法的渐进时间复杂度）