目录

1、数据结构的研究内容

2、基本概念和术语

2.1 思维导图

2.2 基本概念

2.3 数据结构的两个层次

2.3.1 逻辑结构

2.3.2 物理结构（存储结构）

3、抽象数据类型的表示与实现

3.1 数据类型的定义：

3.2 数据类型的作用：

3.3 抽象数据类型（ADT）

3.4 抽象数据类型的形式定义

4、算法和算法分析

4.1 算法的定义

4.2 算法的描述

4.3 算法的特性

4.4 “好”算法的特质

5、算法的效率

5.1 时间复杂度

5.2 空间复杂度

---

1、数据结构的研究内容

• 描述非数值计算问题的数学模型不是数学方程，而是诸多表、树和图之类的具有逻辑关系的数据；

• 数据结构是一门研究非数值计算的程序设计中计算机的操作对象以及他们之间的关系和操作的学科；

---

2、基本概念和术语

2.1 思维导图

2.2 基本概念

1）数据： 数据是信息的载体，是描述客观事物属性的数、字符及所有能输入到计算机中并被计算机程序识别、存储、加工的各种符号的集合。数据是计算机程序加工的原料。

包括：

• 数值型数据：整数、实数等；

• 非数值型数据：文字、图像、图形、声音等；

2）数据元素： 数据元素是数据的基本单位，通常作为一个整体进行考虑和处理。也简称为元素，或称为记录、结点或顶点；一个数据元素可由若干数据项组成；

3）数据项： 数据项是构成数据元素的不可分割的最小单位。

注意：数据、数据元素、数据项三者之间的关系： 数据 > 数据元素 > 数据项 例如：学生表 > 个人纪录 > 学号、姓名......

4）数据对象： 数据对象是具有相同性质的数据元素的集合，是数据的一个子集。

注意：4.1）数据元素——组成数据的基本单位 与数据的关系：是集合的个体；

4.2）数据对象——性质相同的数据元素的集合 与数据的关系：集合的子集；

5）数据结构：

• 数据元素不是孤立存在，他们之间存在着某种关系，数据元素相互之间的关系称为结构

• 是指相互之间存在一种或多种特定关系的数据元素集合；

• 数据结构是带结构的数据元素的集合

数据结构包括以下三个方面的内容： 1）数据元素之间的逻辑关系，也称逻辑结构； 2）数据元素及其关系在计算机内存中的表示（又被称为映像），称为数据的物理结构或数据的存储结构； 3）数据的运算和实现，即对数据元素可以施加的操作以及这些操作在相应的存储结构上的实现；

2.3 数据结构的两个层次

2.3.1 逻辑结构

• 描述数据元素之间的逻辑关系；

• 与数据的存储无关，独立于计算机；

• 是从具体问题抽象出来的数学模型；

1）线性结构

数据元素之间是一对一的关系。除了第一个元素，所有元素都有唯一前驱；除了最后一个元素，所有元素都有唯一后续；

例如：线性表、栈、队列、串

2）树形结构

数据元素之间是一对多的关系

3）图形结构（网状结构）

数据元素之间是多对多的关系

4）集合

各个元素同属一个集合，别无其他关系

                                         

2.3.2 物理结构（存储结构）

• 数据元素及其关系在计算器存储器中的结构（存储方式）；

• 是数据结构在计算机种的表示；

1）顺序存储结构：

用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系由元素的存储位置表示（C语言中用数组来表示顺序存储结构）

2）链接存储结构：

用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系用指针来表示（C语言中用指针来实现链式存储结构） 存储当前元素的同时，存储下一个元素的地址

                                

3）索引存储结构：

在存储结点信息的同时，还建立了索引表（Index目录）

4）散列存储结构：

根据结点的关键字直接计算出该结点的存储地址，又称哈希存储

2.3.3 逻辑结构和存储结构的关系：

• 存储结构是逻辑关系的映像与元素本身的映像；

• 逻辑结构是数据结构的抽象，存储结构是数据结构的实现；

• 两者综合起来就建立了数据元素之间的结构关系；

---

3、抽象数据类型的表示与实现

3.1 数据类型的定义：

数据类型是一组性质相同的值的集合以及定义于这个值集合上的一组操作的总称

数据类型 = 值的集合 + 值集合上的一组操作

3.2 数据类型的作用：

1）约束常量或变量的取值范围； 2）约束变量或常量的操作；

3.3 抽象数据类型（ADT）

• 由用户定义，从问题抽象出数据模型（逻辑结构）

• 还包括定义在数据模型上的一组抽象运算（相关操作）

• 不考虑计算机内的具体存储结构与运算的具体实现算法； 例如：Circle圆：到某一定点距离相等的点的集合

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

利用处理器中已存在的数据类型来说明新的结构，用已经实现的操作来组合新的操作；

3.4 抽象数据类型的形式定义

1）抽象数据类型可用（D、S、P）三元组表示。

其中：D是数据对象 S是D上的关系集 P是对D的基本操作集

2）数据类型的定义格式如下：

ADT 抽象数据类型名{ 数据对象：<数据对象的定义>//用伪代码描述 数据关系：<数据关系的定义>//用伪代码描述 基本操作：<基本操作的定义> } ADT 抽象数据类型名

3）基本操作的定义格式为：

基本操作名:（参数表） 初始条件：(初始条件描述) 操作结果：（操作结果描述）

注意：基本操作的定义格式说明：

3.1）参数表：赋值参数 只为操作提供输入值； 引用参数以&打头，除可提供输入值外，还将返回操作结果； 例如：图片的缩放操作 G‘ = scale（G，n）相当于 scale（&G，n）

3.2）初始条件： 描述操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。若初始条件为空，则省略之；

3.3）操作结果： 说明操作正常完成之后，数据结构的变化状况和应返回的结果；

4）举例说明以上内容（类C语言实现）：

ADT Circle{
    数据对象：D = {r，x，y|r，x，y均为参数}
    数据关系：R = {|r是半径，是圆心坐标} 
    基本操作：
    Circle(&C,r,x,y)
            操作结果：构造一个圆。
    double Area(C)
            初始条件：圆已存在。
            操作结果：计算面积。
    double Circumference(C)
            初始条件：圆已存在。
            操作结果：计算周长。
        ......
}ADT Circle

---

4、算法和算法分析

4.1 算法的定义

对特定问题求解方法和不步骤的一种描述，他是指令的有限序列，其中每个指定表示一个或多个操作（解决问题的方法和步骤）；

4.2 算法的描述

• 自然语言：英文、中文

• 流程图：传统流程图、NS流程图

 

• 伪代码：类语言：类C语言

• 程序代码：C语言程序、Java程序

算法与程序

• 算法是解决问题的一种方法或一个过程，考虑如何将输入转换成输出，一个问题可以有多种算法；

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

4.3 算法的特性

1）有穷性：一个算法必须总在执行有穷步之后结束，且每一步都可在有穷时间内完成 注： 算法必须是有穷的，而程序可以是无穷的。

2）确定性：算法中每条指令必须有确切的含义，对于相同的输入只能得出相同的输出。

3）可行性：算法中描述的操作都可以通过已经实现的基本运行执行有限次来实现。

4）输入：一个算法有零个或多个输入，这些输入取自于某个特定的对象的集合。

5）输出：一个算法有一个或多个输出，这些输出是与输入有着某种特定关系的量。

4.4 “好”算法的特质

1）正确性：算法应能正确地解决求解问题。

2）可读性：算法应具有良好的可读性，以帮助人们理解。

3）健壮性（鲁棒性）：输入非法数据时，算法能适当地做出反应或进行处理，而不会产生莫名其妙的输出结果。

4）高效性和低存储量需求。 高效性：执行速度快，时间复杂度低。 低存储量需求：不费内存，空间复杂度低。

5、算法的效率

5.1 时间复杂度

5.1.1 度量程序执行时间的方法

1）事后统计的方法：

这种方法有两种缺陷：

• 必须先运行依据算法编制的程序；

• 是所得时间的统计量依赖于计算机的硬件、软件等环境因素，有事容易掩盖算法本身的优劣。因此人们常常采用另一种事前分析估算的方法。

2）事前分析估算的方法：一个用高级程序语言编写的程序在计算机上运行时所消耗的时间取决于下列因素：

• 依据的算法选用何种策略；

• 问题的规模，例如求100以内还是求1000以内的素数;

• 书写程序的语言，对于同一个算法，实现语言的级别越高，执行效率就越低；

• 编译程序所产生的机器代码的质量；

• 机器执行指令的速度；

5.1.2 算法时间复杂度的渐进表示法

• 为了便于比较两个不同算法的时间效率，我们仅比较它们的数量级 例如：两个不同的算法，时间消耗分别是：

                  ​​​​​​​                ​​​​​​​        ​​​​​​​        

  那么数量级小的比较好

• 若有某个辅助函数f(n),使得当n趋近于无穷大的时候，T(n) / f(n)的极限值为不等于零的常数，则称 f(n) 是 T(n) 的同数量级函数。就做T(n) = O(f(n))；称为 O(f(n)) 为算法的渐进时间复杂度（O是数量级的符号），简称时间复杂度； T(n) = 2n^3 + 3n^2 + 2n + 1则 f(n) = n^3，可知 T(n) 与 n^3 是同阶的，T(n)可记作：T(n) = O(n^3)

5.1.3 分析算法时间复杂度的基本方法

1）找出语句频度最大的那条语句作为基本语句；（嵌套层次最深的） 2）计算基本语句的频度得到问题规模 n 的某个函数 f(n)； 3）取其数量级用符号"O"表示

5.1.4 算法有两条运算规则：

5.1.5 常见的渐进时间复杂度

5.1.6 算法案例

1）算法一：

void loveYou(){//n为问题规模
①    int i=1;
②    while(i<=n){
③        i++;
④        printf("I Love You %d\n",i);
    }
⑤    pritnf("I Love You Than %d\n",n);
}

语句频度：

① ——1次

② ——3001次

③④——3000次

⑤ ——1次 T(3000)=1+3001+2*300+1

时间开销与问题规模n的关系：T(n)=3n+3=O(n)

2）算法二：

void loveYou(){//n为问题规模
    int i=1;
    while(i<=n){
        i++;
        printf("I Love You %d\n",i);
        for(int j=1;j
            printf("I am Iron Man\n");
        }
    }
    pritnf("I Love You Than %d\n",n);
}

外层循环执行n次，内层循环共执行n^2次。 时间开销与问题规模n的关系：

结论：如果有多层嵌套循环，只需关注最深层循环循环了几次

3）算法三：

void loveYou(){//n为问题规模
    int i=1;
    while(i<=n){
        i=i*2;//每次翻倍
        printf("I Love You %d\n",i);
        for(int j=1;j
            printf("I am Iron Man\n");
        }
    }
    pritnf("I Love You Than %d\n",n);
}

计算上述算法的时间复杂度T(n): 设最深层循环的语句频度(总共循环的次数)为x，则由循环条件可

知，循环结束时刚好满足

4）算法四：

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

5.2 空间复杂度

算法的空间复杂度S(n)定义为该算法所消耗的存储空间，它是问题规模n的函数。记为S ( n ) = O ( g ( n ) )

一个程序在执行时除需要存储空间来存放本身所用的指令、常数、变量和输入数据外，还需要一些对数据进行操作的工作单元和存储一些为实现计算所需信息的辅助空间。若输入数据所占空间只取决于问题本身，和算法无关，则只需分析除输入和程序之外的额外空间。

实例：

算法一：

for(i=0;i
    t=a[i];
    a[i]=a[n-i-1];
    a[n-i-1]=t;
}

S(n) = O(1);原地工作

算法二：

for(i=0;i
    b[i]=a[n-i-1];
for(i=0;i
    a[i]=b[i];

S(n) = O(n);

可见算法一的空间效率高于算法二；