为什么学习数据结构

1. 计算机是什么

计算机是一种处理数据的机器

输入=〉存储 =〉输出
        ||
       处理

2. 计算机处理数据的分类

数值数据：整数、浮点数等数值类型。与这类数据相关的问题有：线性方程的求解，矩阵求逆，微分方程求解等。在计算机发展初期，人们使用计算机主要是解决这类问题。现在主要是在解决工程学、经济学的问题中使用。

处理这类数据的知识叫做：数值计算。

3. 计算机处理数据的分类

非数值数据：这类数据的类型多样，比如：文字，图像，声音，视频等等。这类数据的数据量巨大。随着计算机应用领域的扩大和软、硬件的发展，这类数据所占的比例越来越多，也越来越重要。（据统计，当今处理非数值性问题占用了90%以上的机器时间。）数据元素之间的相互关系一般无法用数学方程加以描述。

如何描述此类数据，并对此类数据进行有效的处理，成为了严峻的问题。解决此类问题的知识，被称为：数据结构。

4. 非数值问题求解

著名的瑞士计算机科学家沃思（N.Wirth）教授曾提出：

算法+数据结构=程序

• 数据结构：是指数据的逻辑结构和存储结构
• 算法：是对数据运算的描述

解决非数值问题的关键不再是分析数学和计算方法，而是要设计出适当的数据结构来存储数据，并在此基础上设计出有效的算法，来对数据进行需要的处理。

5. 例子：电话号码查询问题

设计一个查询某个城市的私人电话号码的程序。要求对任意给出的一个姓名，若该人有电话号码，则迅速找到其电话号码；否则指出该人没有电话号码。

要解此问题首先构造一张电话号码登记表。表中每个结点存放两个数据项： 姓名和电话号码。要写出好的查找算法，取决于这张表的结构及存储方式。最简单的方式是将表中结点顺序地存储在计算机中。查找时从头开始依次查对姓名，直到找出正确的姓名或是找遍整个表均没有找到为止。

这种查找算法对于一个不大的单位或许是可行的，但对一个有成千上万私人电话的城市就不实用了。

6. 例子：田径赛的时间安排问题

假设某校的田径选拔赛共设六个项目的比赛，即跳高、跳远、标枪、铅球、100米和200米短跑，规定每个选手至多参加三个项目的比赛。现有五名选手报名比赛，选手所选择的项目如参赛选手比赛项目表所示。现在要求设计一个竞赛日程安排表，使得在尽可以短的时间内安排完比赛。

7. 关于数据结构课程

这门课程是计算机相关专业的核心课程，在众多的计算机系统软件和应用软件中都要用到各种数据结构。仅掌握计算机语言是难以应付众多复杂的课题的，要想有效地使用计算机语言，必须学好数据结构的有关知识。 学习内容：

• 数据结构的基础知识与运用
• 算法的简单分析与设计

后继课程：数据库，操作系统等都要数据结构知识

8. 如何学习数据结构

数据结构课程理论结合实践，难度比较大

9. 参考资源

• 《数据结构》严蔚敏，吴伟民
• 《Fundamentals of Data Structures in C》Ellis Horowitz
• 数据结构自考网http://student.zjzk.cn/course_ware/data_structure/web/main.htm

10. C语言基础

使用C语言进行课堂讲授

C语言中的重点：

• 结构体
• 指针
• 数组
• 内存动态分配与释放

参考资料：

• 《C程序设计语言》第二版，K&R

11. 离散数学基础

这是数据结构的理论基础

主要相关知识：

• 图论（图、树）

参考资料

数据结构中的基本概念

1. 数据结构的基本概念

• 数据（Data）：是信息的载体。它能够被计算机识别、存储和加工处理，是计算机程序加工的“原料”。数据的范畴包括：整数、实数、字符串、图像和声音等。
• 数据元素（Data Element）是数据的基本单位。数据元素也称元素、结点、顶点、记录。一个数据元素可以由若干个数据项（也可称为字段、域、属性）组成。

2. 数据的逻辑结构

数据元素之间的逻辑关系，也称数据的逻辑结构（Logical Structure）

数据的逻辑结构是从逻辑关系上描述数据，与数据的存储无关，是独立于计算机的。数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。

3. 逻辑结构的表示

B = (K, R)

K：数据元素的集合，比如：{a, b, c, d,e}

R：数据元素之间的关系的集合，比如：{<a,b>, <b,c>,<c,d>,<d,e>}

<a,b>：a是b的前驱节点，b是a的后继节点

4. 逻辑数据结构分类

• 线性结构：若结构是非空集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。线性表是一个典型的线性结构。栈、队列、字符串等都是线性结构。
  

• 非线性结构：一个结点可能有多个直接前趋和直接后继。树和图等数据结构都是非线性结构。

  • 树：只有一个前驱，可能有多个后继
    

  • 图：有多个前驱和多个后继
    

5. 数据的存储结构

数据元素及其逻辑关系在计算机存储器内的表示，称为数据的存储结构（Storage Structure）

数据的存储结构是逻辑结构用计算机语言的实现（亦称为映象），它依赖于计算机语言。对机器语言而言，存储结构是具体的。一般，只在高级语言的层次上讨论存储结构。

6. 数据的基本存储结构

• 顺序存储结构（Sequential Storage Structure）：该方法把逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。通常借助程序语言的数组描述。该方法主要应用于线性的数据结构。非线性的数据结构也可通过某种线性化的方法实现顺序存储。
• 链式存储结构（Linked Storage Structure）：该方法不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系由附加的指针字段表示。通常借助于程序语言的指针类型描述。
• 索引存储结构：该方法通常在储存结点信息的同时，还建立附加的索引表。索引表由若干索引项组成。索引项的一般形式是：(关键字、地址)。关键字是能唯一标识一个结点的那些数据项，地址指示结点所在的存储位置。
• 散列存储结构：根据结点的关键字直接计算出该结点的存储地址。

四种基本存储结构，既可单独使用，也可组合起来对数据结构进行存储映像。

同一逻辑结构可以采用不同的存储结构来表示。选择何种存储结构来表示相应的逻辑结构，视具体要求而定，主要考虑运算方便及算法的时空要求。

存储密度：数据所占空间与数据结构所占空间的比。一定≤1

7. 数据的运算

数据的运算，即对数据施加的操作。

数据的运算定义在数据的逻辑结构上，每种逻辑结构都有一个运算的集合。

最常用的检索、插入、删除、更新、排序等运算实际上只是在抽象的数据上所施加的一系列抽象的操作。所谓抽象的操作，是指我们只知道这些操作是"做什么"，而无须考虑"如何做"。只有确定了存储结构之后，才考虑如何具体实现这些运算。

8. 数据结构

数据结构就是指按一定的逻辑结构组成的一批数据，使用某种存储结构将这批数据存储于计算机中，并在这些数据上定义了一个运算集合。

数据的逻辑结构、数据的存储结构及数据的运算这三方面是一个整体。

存储结构是数据结构不可缺少的一个方面：同一逻辑结构的不同存储结构可冠以不同的数据结构名称来标识。【例】线性表是一种逻辑结构，若采用顺序方法的存储表示，可称其为顺序表；若采用链式存储方法，则可称其为链表；若采用散列存储方法，则可称为散列表。

数据的运算也是数据结构不可分割的一个方面：在给定了数据的逻辑结构和存储结构之后，按定义的运算集合及其运算的性质不同，也可能导致完全不同的数据结构。

【例】若对线性表上的插入、删除运算限制在表的一端进行，则该线性表称之为栈；若对插入限制在表的一端进行，而删除限制在表的另一端进行，则该线性表称之为队列。 更进一步，若线性表采用顺序表或链表作为存储结构，则对插入和删除运算做了上述限制之后，可分别得到顺序栈或链栈，顺序队列或链队列。

9. 抽象数据类型（Abstract Data Type）

ADT是指抽象数据的组织和与之相关的操作。可以看作是数据的逻辑结构及其在逻辑结构上定义的操作。

一个ADT可描述为：

ADT ADT-Name{
    数据对象：
       ……
    数据元素之间逻辑关系：
       ……
    操作：
        Operation1://操作1
        Operation2://操作2
        ……
  }

算法和算法的度量

1. 算法

为了求解某问题，必须给出一系列的运算规则，这一系列的运算规则是有限的，表达了求解问题方法和步骤，这就是一个算法。 一个算法可以用自然语言描述，也可以用高级程序设计语言描述，也可以用伪代码描述。本课程采用C语言对算法进行描述。实验中采用C/C++都可以。

2. 例子

写一个算法，计算n!

让i=1, s=1
如果i>n则转第6步
s = s * i
i = i +1
转第2步
计算结束，s为n!的值

还有其他算法吗？

3. 五个重要特性

• 有穷性：算法的执行必须在有限步内结束。
• 确定性：算法的每一个步骤必须是确定的无二义性的。
• 输入：算法可以有0个或多个输入。
• 输出：算法一定有输出结果
• 可行性：算法中的运算都必须是可以实现的。

4. 算法的正确性

• 正确的算法：若一个算法对于每个输入实例均能终止并给出正确的结果，则称该算法是正确的。正确的算法解决了给定的计算问题。
• 不正确的算法：一个不正确的算法是指对某些输入实例不终止，或者虽然终止但给出的结果不是所渴望得到的答案。

5. 评价算法的好坏

求解同一计算问题可能有许多不同的算法，究竟如何来评价这些算法的好坏以便从中选出较好的算法呢？选用的算法首先应该是“正确”的。

主要考虑如下三点：

• 执行算法所耗费的时间；
• 执行算法所耗费的存储空间，其中主要考虑辅助存储空间；
• 算法应易于理解，易于编码，易于调试等等。

6. 算法的选择

一个占存储空间小、运行时间短、其它性能也好的算法是很难做到的。原因是上述要求有时相互抵触：要节约算法的执行时间往往要以牺牲更多的空间为代价；而为了节省空间可能要耗费更多的计算时间。

因此我们只能根据具体情况有所侧重：

• 若该程序使用次数较少，则力求算法简明易懂；
• 对于反复多次使用的程序，应尽可能选用快速的算法；
• 若待解决的问题数据量极大，机器的存储空间较小，则相应算法主要考虑如何节省空间。

7. 算法执行时间的分析

一个算法所耗费的时间=算法中每条语句的执行时间之和

每条语句的执行时间=语句的执行次数（频度）×语句执行一次所需时间

算法转换为程序后，每条语句执行一次所需的时间取决于机器的指令性能、速度以及编译所产生的代码质量等难以确定的因素。

若要独立于机器的软、硬件系统来分析算法的时间耗费，则设每条语句执行一次所需的时间均是单位时间，一个算法的时间耗费就是该算法中所有语句的频度之和。

8. 例子：求矩阵乘积

   1 void mult(int a[n][n], int b[n][n], int c[n][n]) 
   2 {
   3     int i, j, k;
   4     for (i=0; i<n; ++i) {  /* n+1 */
   5         for (j=0; j<n; ++j) { /* n(n+1)*/
   6             c[i][j] = 0;  /*n2*/
   7             for (k=0; k<n; ++k) /*n2(n+1)*/
   8                 c[i][j] += a[i][k]*b[k][j];  /* n3 */
   9         }
  10     }
  11 }

所有语句的频度之和 T(n)=(n+1)+n(n+1)+n²+n²(n+1) +n³

9. 问题规模和算法的时间复杂度

算法求解问题的输入量称为问题的规模，一般用一个整数表示。比如：矩阵乘积问题的规模是矩阵的阶数。

一个算法的时间复杂度T(n)是该算法的时间耗费，是该算法所求解问题规模n的函数。当问题的规模n趋向无穷大时，时间复杂度T(n)的数量级(阶)称为算法的渐进时间复杂度。

比如：矩阵乘积算法的时间复杂度T(n) ，当n趋向无穷大时，显然有

这表明，当n充分大时，T(n)和n³之比是一个不等于零的常数。即T(n)和n³是同阶的，或者说T(n)和n³的数量级相同。记作T(n)=O(n³)是矩阵乘积算法的渐近时间复杂度。

10. 大O表示法

若T(n)和f(n)是定义在正整数集合上的两个函数，则T(n)=O(f(n))表示存在正的常数C和n0，使得当n≥n0时都满足0≤T(n)≤C·f(n)。

常见的时间复杂度按数量级递增排列依次为：常数0(1)、对数阶0(log₂n)、线形阶0(n)、线形对数阶0(nlog₂n)、平方阶0(n²)立方阶0(n³)、…、k次方阶0(n^k)、指数阶0(2ⁿ)。显然，时间复杂度为指数阶0(2ⁿ)的算法效率极低，当n值稍大时就无法应用。

11. 例子

有两个算法A1和A2求解同一问题，时间复杂度分别是T₁(n)=100n²，T₂(n)=5n³。

那么，当输入量n＜20时，有T₁(n)＞T₂(n)，后者花费的时间较少。

随着问题规模n的增大，两个算法的时间开销之比5n³/100n²=n/20亦随着增大。即当问题规模较大时，算法A1比算法A2要有效地多。

渐近时间复杂度O(n²)和O(n³)评价了这两个算法在n较大时的时间性能

12. 例子

    Temp=i;
    i=j;
    j=temp; 

T(n)=O(1)

13. 例子

x=0; 
y=0;
for(k-1;k<=n;k++)
    x++;
for(i=1;i<=n;i++)
     for(j=1;j<=n;j++)
         y++; 

T(n)=O(n²)

14. 例子

 x=1;
 for(i=1;i<=n;i++)
     for(j=1;j<=i;j++)
         for(k=1;k<=j;k++)
             x++; 

T(n)=O(n³/6+低次项)=O(n³)

15. 数据初始状态影响执行时间

算法的时间复杂度不仅仅依赖于问题的规模，还与输入实例的初始状态有关。

在数值A[0..n-1]中查找给定值k的算法大致如下：

for(i=0;i<n && A[i]!=k; i++);
   return i;

冒泡排序

16. 各种情况下的算法性能

• 最坏情况下的时间复杂度称最坏时间复杂度，算法计算量达到最大值
• 最好情况下的时间复杂度称最好时间复杂度，算法计算量最小
• 算法在平均情况下的时间复杂度是指在所有可能的情况下的计算量经过加权平均后的平均值

17. 算法的空间复杂度

算法所需空间包括：

• 输入数据所占空间
• 辅助变量所占空间
• 程序所占空间

若输入数据所占空间只取决于问题本身，和算法无关，则只需要分析除输入和程序之外的辅助变量所占额外空间。

算法的时间复杂度和空间复杂度合称为算法的复杂度。

总结

数据结构（包括逻辑结构，存储结构，运算）

算法（时间复杂度，空间复杂度）