零、启航，新的目标！

1、问题

为什么要学习数据结构这门课程？

2、常见问题

• 语言学习结束之后是否有能力进行项目开发？
• 当面对一个问题的时候如何思考解决方案？
• 如何评判代码效率的高低好坏？
• 怎样才能提高自己的编程能力？
• 。。。

3、数据结构课程的意义

• 培养专业的程序设计思维
• 训练使用程序语言描述解决方案的能力
• 计算机专业的基础课程
• 算法分析专业课的先修课程

4、数据结构==算法设计 ? ? ?

5、另一个值得思考的问题

        现代的程序设计语言开发包中都有数据结构和常用算法的完整实现，是不是掌握如何使用就可以了？

6、知其然，知其所以然！

• 排序的时候，如何选择排序算法？
• 单链表就够用了，为什么还要双向链表？
• 最短路径的算法很有名，为什么很少在项目中使用？
• 递归就是函数自己调用自己，这样诡异的做法有什么用？

7、不下降序列问题

        

8、专业程序员的培养路线

        

9、数据结构的基础功底在职场竞争中的作用

• 对于职场新人
  • 大型软件企业招聘必考数据结构
• 对于职场老鸟
  • 提出并实现解决问题的关键方案是价值的体现

10、启航，新的目标！

• 课程目标
  • 创建可复用的数据结构软件库
  • 分析并优化C++课程中创建的实用类

• 使用的技术
  • C++面向对象技术
  • C++模板技术
  • C++异常处理技术

一、理解程序的本质

1、问题

为什么会有各种各样的程序存在？程序的本质是什么？

2、理解程序的本质

• 程序是为了解决实际问题而存在的从本质上而言，程序是解决问题的步骤描述

        

• 一小步的进阶：理解实际问题！
  • 确认问题类型
    • 如：数值计算，求最小值个数
  • 确认求解步骤
    • 如：打开文件，读数据，关闭文件，计算和

3、问题

如何判断问题求解步骤的好坏？

4、实例分析：判断求解步骤的好坏

/*
    问题：给定一个整数 n，编程求解 1 + 2 + 3 + ... + n 的和。
*/
#include <iostream>
 
using namespace std;
 
long sum1(int n)
{
    long ret = 0;
    int* array = new int[n];
    
    for(int i=0; i<n; i++)
    {
        array[i] = i + 1;
    }
    
    for(int i=0; i<n; i++)
    {
        ret += array[i];
    }
    
    delete[] array;
    
    return ret;
}
 
long sum2(int n)
{
    long ret = 0;
    
    for(int i=1; i<=n; i++)
    {
        ret += i;
    }
    
    return ret;
}
 
long sum3(int n)
{
    long ret = 0;
    
    if( n > 0 )
    {
        ret = (1 + n) * n / 2;
    }
    
    return ret;
}
 
int main()
{
    cout << "sum1(100) = " << sum1(100) << endl;
    cout << "sum2(100) = " << sum2(100) << endl;
    cout << "sum3(100) = " << sum3(100) << endl;
    
    return 0;
}

5、程序评鉴初探

• 用尽量少的时间解决问题
• 用尽量少的步骤解决问题
• 用尽量少的内存解决问题

优秀的开发者追求高质量的代码！

6、数据结构课程的历史起源

1968年，由高纳德教授(Donald E.Knuth )开创一同年，在计算机科学的学位课程中出现（必修）

        

7、数据结构课程的研究范围

• 非数值计算类型的程序问题
• 数据间的组织和操作方式
• 数据的逻辑结构和存储结构

8、历史上的经典公式

程序 = 数据结构＋算法

对于数据结构和算法的研究，语言不重要，重要的是思想。

9、小结

• 程序是为了解决实际问题而存在的
• 针对同一个问题可以有多种解决方案
• 专业程序员应该尽量追求高质量的程序
• 数据结构课程主要研究非数值计算问题

二、数据的艺术

1、程序设计的挑战

• 利用计算机解决现实生活中的问题
• 生活中的不同个体间存在联系
• 用计算机程序描述生活中个体间的联系

2、问题

        如何用程序描述生活中的个体？

3、数据的艺术

• 数据的概念
  • 程序的操作对象，用于描述客观事物
• 数据的特点
  • 可以输入到计算机
  • 可以被计算机程序处理

4、数据中的新概念

• 数据元素
  • 组成数据的基本单位
• 数据项
  • 一个数据元素由若干数据项组成
• 数据对象
  • 性质相同的数据元素的集合

5、数据实例分析

        

6、数据结构指数据对象中数据元素之间的关系

• 数据元素之间不是独立的
  • 存在特定的关系，这些关系即结构
• 如：
  • 数组中各个元素之间存在固定的线性关系

编写一个“好”的程序之前，必须分析待处理问题中各个对象的特性，以及对象之间的关系。

7、逻辑结构

• 集合结构
  • 数据元素之间没有特别的关系，仅同属相同集合
• 线性结构
  • 数据元素之间是一对一的关系
• 树形结构
  • 数据元素之间存在一对多的层次关系
• 图形结构
  • 数据元素之间是多对多的关系

        

8、物理结构

• 逻辑结构在计算机中的存储形式
  • 顺序存储结构
    • 将数据存储在地址连续的存储单元里
  • 链式存储结构
    • 将数据存储在任意的存储单元里
    • 通过保存地址的方式找到相关联的数据元素

        

9、数据的艺术

• 数据结构是相互之间存在特定关系的数据元素的集合
• 数据结构可以分为逻辑结构和物理结构

        

三、初识程序的灵魂

1、初识程序的灵魂

• 数据结构静态的描述了数据元素之间的关系
• 高效的程序需要在数据结构的基础上设计和选择算法

        

• 算法是特定问题求解步骤的描述
• 在计算机中表现为指令的有限序列

        

2、算法的特性

• 输入：算法具有0个或多个输入
• 输出：算法至少有1个或多个输出
• 有穷性：算法在有限的步骤之后会自动结束而不会无限循环
• 确定性︰算法中的每一步都有确定的含义，不会出现二义性
• 可行性：算法的每一步都是可行的

• 正确性
  • 算法对于合法数据能够得到满足要求的结果
  • 算法能够处理非法输入，并得到合理的结果
  • 算法对于边界数据和压力数据都能得到满足要求的结果
  • 注意：正确性是算法最需要满足的基本的准则，但是作为计算机程序，不可能无限制的满足这条准则。

• 可读性
  • 算法要方便阅读，理解和交流

注意：算法可读性是最容易被忽视的，然而，程序是写给人看的，而不是计算机。

• 健壮性
  • 算法不应该产生莫名其妙的结果
• 性价比
  • 利用最少的资源得到满足要求的结果

3、小结

• 算法为了解决实际问题而存在
• 数据结构是算法处理问题的载体
• 数据结构与算法相辅相成，共同解决问题

 

四、程序灵魂的审判

1、木暮的思考。。。

如果两个算法都满足功能性需求，那工程中最关心的其它特性是什么？如何比较评判呢？

注意：

性价比（效率）是工程中最关注的算法附加特性！

2、算法效率的度量

• 事后统计法
  • 比较不同算法对同一组输入数据的运行处理时间
  • 缺陷
    • 为了获得不同算法的运行时间必须编写相应程序
    • 运行时间严重依赖硬件以及运行时的环境因素
    • 算法的测试数据的选取相当困难
• 事前分析估算
  • 依据统计的方法对算法效率进行估算
  • 影响算法效率的主要因素

1. 算法采用的策略和方法

2. 问题的输入规模

3. 编译器所产生的代码

4. 计算机执行速度

• 算法效率的简单估算一

        

• 算法效率的简单估算二

        

• 算法效率的简单估算三

        

3、实例分析：程序效率估算

#include <iostream>
 
using namespace std;
 
int func(int a[], int len)       // ==> (n*n + 2)
{
    int ret = 0;      // 1
    
    for(int i=0; i<len; i++)     
    {
        for(int j=0; j<len; j++) 
        {
            ret += a[i] * a[j];  // n * n
        }
    }
    
    return ret;      // 1
}
 
int main()
{
    int array[] = {1, 2, 3, 4, 5};
    
    cout << func(array, 5) << endl;
    
    return 0;
}
 

4、程序灵魂的审判

• 启示
  • 程序效率估算练习中的关键部分的操作数量为n*n
  • 三种求和算法中关键部分的操作数量分别为2n, n和1
• 随着问题规模n的增大，它们操作数量的差异会越来越大，因此实际算法在效率上的差异也会变得非常明显！

        

• 算法操作数量的对比一

        

• 算法操作数量的对比二

        

• 算法操作数量的对比三

        

5、小结

• 算法的度量有事后统计法和事前分析估算法
• 事后统计法不容易准确度量算法的效率
• 事前分析估算法通过操作数量度量算法效率
• 判断一个算法效率时只需要关注最高阶项就能得出结论
• 某个算法，随着问题规模n的增大，它会越来越优于另一算法，或者越来越差于另一算法。

五、算法的时间复杂度

1、结论

        判断一个算法的效率时，操作数量中的常数项和其他次要项常常可以忽略，只需要关注最高阶项就能得出结论。

2、问题

如何用符号定性的判断算法的效率？

3、算法的复杂度

• 时间复杂度
  • 算法运行后对时间需求量的定性描述
• 空间复杂度
  • 算法运行后对空间需求量的定性描述

注意！！！

        数据结构课程重点关注的是算法的效率问题，因此，整个课程会集中于讨论算法的时间复杂度；

        但其使用的方法完全可以用于空间复杂度的判断！

4、大O表示法

• 算法效率严重依赖于操作(Operation）数量
• 操作数量的估算可以作为时间复杂度的估算
• 在判断时首先关注操作数量的最高次项

        

5、常见时间复杂度

• 线性阶时间复杂度：O(n)

        

• 对数阶时间复杂度：O(logn)

        

• 平方阶时间复杂度：O(n2)

        

6、时间复杂度计算练习

• 时间复杂度计算练习一

        

===> O(n^2)

• 时间复杂度计算练习二

        

此处子函数少个i++。

===> O(n^2)

• 时间复杂度计算练习三

        

===> O(n^3)

7、小结

• 时间复杂度是算法运行时对于时间的需求量
• 大O表示法用于描述算法的时间复杂度
• 大O表示法只关注操作数量的最高次项
• 常见的时间复杂度为：线性阶，平方阶和对数阶

六、算法效率的度量

1、常见时间复杂度

        

2、常见时间复杂度的比较

        

3、算法分析示例

        

4、算法的最好与最坏情况

意义：

        当算法在最坏情况下仍然能满足需求时，可以推断，算法的最好情况和平均情况都满足需求。

注意：

        数据结构课程中，在没有特殊说明时，所分析算法的时间复杂度都是指最坏时间复杂度。

5、算法的空间复杂度（Space Complexity )

• 定义：S(n) = S(f(n))
  • n为算法的问题规模
  • f(n)为空间使用函数，与n相关

• 推导时间复杂度的方法同样适用于空间复杂度

• 例如：
  • 当算法所需要的空间是常数时，空间复杂度为S(1)

6、空间复杂度计算练习

7、空间与时间的策略

• 多数情况下，算法的时间复杂度更令人关注
• 如果有必要，可以通过增加额外空间降低时间复杂度
• 同理，也可以通过增加算法的耗时降低空间复杂度

8、实例分析：空间换时间

/*
    问题： 
    在一个由自然数1-1000中某些数字所组成的数组中，每个数字可能出现零次或者多次。
    设计一个算法，找出出现次数最多的数字。
*/
 
#include <iostream>
 
using namespace std;
 
void search(int a[], int len)     // O(n)
{
    int sp[1000] = {0};
    int max = 0;
    
    for(int i=0; i<len; i++)
    {
        sp[a[i] - 1]++;
    }
    
    for(int i=0; i<1000; i++)
    {
        if( max < sp[i] )
        {
            max = sp[i];
        }
    }
    
    for(int i=0; i<1000; i++)
    {
        if( max == sp[i] )
        {
            cout << i + 1 << endl;
        }
    }
}
 
int main(int argc, char* argv[])
{
    int a[] = {1, 1, 3, 4, 5, 6, 6, 6, 3, 3};
    
    search(a, sizeof(a)/sizeof(*a));
 
    return 0;
}

9、面试题

当两个算法的大O表示法相同时，是否意味着两个算法的效率完全相同？

算法时间复杂度相同，意味着两个算法效率是一个级别的，不意味着效率完全相同。

10、小结

• 一般而言，工程中使用的算法，时间复杂度不超过O(n3)
• 算法分析与设计时，重点考虑最坏情况下的时间复杂度
• 数据结构课程中重点关注算法的时间复杂度
• 大O表示法同样适用于算法的空间复杂度
• 空间换时间是工程开发中常用的策略

七、课程学习小问答

1、数据结构课程该如何学习？

        1. 先从概念上形象的理解数据元素之间的关系

        2. 思考这种关系能够解决什么问题

        3. 考虑基于这种关系能够产生哪些算法

        4. 理解和熟悉最终的算法

        5. 选择一种熟悉的语言，编码实战

2、如果只想进行嵌入式开发，需要学习数据结构吗？

• 以后工作中会用到数据结构的知识吗？

数据结构是计算机领域的基础课程，在学习过程中养成的思维方式将影响整个职业生涯。

3、学习大数据分析需要用到数据结构的知识吗？

        

4、学习人工智能需要用到数据结构的知识吗？

• 人工智能研究的课题
  • 知识的模型化和表示方法
  • 启发式搜索理论
  • 各种推理，规划，演绎和归纳的方法
  • 。。。

5、学习操作系统内核需要用到数据结构吗？

• 内存管理
  • 需要设计页映射表相关的数据结构和访问算法
• 进程管理
  • 需要设计表示进程的数据结构（PCB）和资源分配算法
• 线程管理
  • 需要设计表示线程的数据结构（TCB）和调度算法

• 。。。

6、数据结构课程中会涉及算法设计吗？

• 数据结构以数据元素的结构设计为住，相关算法学习为辅。

7、数据结构课程的内容学完，是不是就可以放下这门课了？

• 数据结构和算法的训练应该贯穿整个软件开发的职业生涯！！！