《大话数据结构》笔记

1.数据结构绪论

1.1 基本概念及术语

1.1.1 数据

是指描述客观事物的符号，是计算机可以操作的对象，是能被计算机识别，并输入给计算机处理的符号集合。数据除了整型、实型等数据类型之外，还包括字符、声音、图像、视频等其他非数值类型。

1.1.2 数据元素

即组成数据，有一定意义的基本单位。在计算机中通常作为整体处理。比如人类的数据元素就是人。禽类的数据元素是牛，羊，鸡这些。

1.1.3 数据项

数据不可分割的最小单位，一个数据元素可由若干个数据项组成。例如人是数据元素，其数据项可以包括性别，年龄等等。虽然其是最小单位，但数据元素才是数据结构中建立数据模型的基本点。

1.1.4 数据对象

性质相同的数据元素的集合，是数据的子集。

1.1.5 数据结构

简单来说，结构就是不同数据元素之间存在的特定关系，而数据结构就是相互之间存在一种或多种特定关系的数据元素的集合。计算机中，数据元素并不是孤立，杂乱无序的，而是一种具有内在联系的数据集合。一个好的程序，必须分析待处理对象的特性以及各处理对象之间存在的关系。

1.2 逻辑结构与物理结构（存储结构）

按照角度的不同，数据结构可以分为逻辑结构与物理结构

1.2.1 逻辑结构

逻辑结构是指数据对象中数据元素之间的相互关系，可分为以下四种：

1. 集合结构
   集合结构中的数据元素除了同属于一个集合外，他们之间没有其他关系。各个数据元素是“平等”的，共同属性就是同属于一个集合。与数学中的集合概念类似。

2. 线性结构
   线性结构中的数据元素之间是一对一的关系。

3. 树形结构
   树形结构中的数据元素是一对多的层次关系，如同一棵树一样。

4. 图形结构
   图形结构的数据元素是多对多的关系

1.2.2 物理结构

是指数据的逻辑结构在计算机中的存储形式。实质就是**如何把数据元素存储到计算机的存储器中，**存储器主要是针对内存而言，外部存储器的数据组织通常用文件结构来描述。

数据的存储结构应正确反映数据元素之间的逻辑关系，数据元素的存储结构形式有两种：顺序存储和链式存储。

1. 顺序存储
   顺序存储结构：把数据元素存放在地址连续的存储单元里，其数据间的逻辑关系和物理关系是一致的。

这种存储结构跟排队一样（没有插队这种情况），数组就是这样的存储结构。当你建立一个有9个整型数据的数组时，计算机就在内存中安排了一块内存，按照一个整型所占位置带下乘以9，开辟一段连续的空间。

2. 链式存储结构
   实际上，就像排队一样，并不是一定这么简单、有规律。实际上总会有人插队，或者因为各种各样的事情离开队伍。也就是这个队中可能会有新成员，也有可能老成员会离开。像这样的情况，顺序存储就是不科学的，不满足实际情况的。由此就有了链式存储结构。

链式存储结构：是把数据元素存放在任意的存储单元里，这组存储单元可以是连续的，，也可以是不连续的。这个结构的存储关系并不能反映其逻辑关系，因此需要用一个指针来存放数据元素的地址，通过地址来找到相关联数据元素的位置。相对于顺序存储，链式存储会灵活许多。

1.3 抽象数据类型

1.3.1 数据类型

数据类型是指一组性质相同的值的集合以及定义在此集合上的一些操作的总称。
数据类型是按照值的不同进行划分的。在高级语言中，每个变量、常量和表达式都有各自的取值范围。类型就是用来说明变量或表达式的取值范围和所能进行的操作。

数据类型的出现时因为计算机的内存并不是无限大的，像一些简单的计算比如1+1=2，显然并不需要开辟很大的内存空间，所以用数据类型来区分不同的需求。

C语言中，按照取值的不同，数据类型可以分为两类：

1. 原子类型：不可再分解的基本类型，包括整型，实型，字符型等。
2. 结构类型：由若干个类型组合而成，是可以再分解的。例如整型数组，是由若干整型数据组成的。

1.3.2 抽象数据类型

抽象：指抽取出事物具有的普遍性的本质。是抽出问题的特征而忽略非本质的细节，是对具体事物的一个概括。抽象是一种思考问题的方式，它隐藏了繁杂的细节，只保留实现目标所必需的信息。

我们对已有的数据类型进行抽象，就有了抽象数据类型。**抽象数据类型（Abstract Data Type）**是指一个数学模型及定义在该模型上的一组操作。抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表现与实现无关。

比如“整数”类型，各种计算机–pc、平板电脑、等等都拥有整数类型，它在不同计算机的实现方法可能不一样，但最后表现出来的数学特性相同，在编程者看来，并没有什么不同。这其实就表明了“整型”其实就是一个抽象数据类型。抽象的意义在于数据类型的数学抽象特性。

除了已经定义并实现的数据类型，编程者自己定义的数据类型其实也可以是抽象数据类型。就好像游戏中的前进、跑、跳等等操作，都是对一个数据对象进行操作，将这些操作进行分解，抽象成一个个容易处理的问题，隐藏了具体的实现过程。

2.算法

2.1 数据结构与算法的关系

数据结构与算法经常被放在一起，只有数据结构，简单地认识了一下概念之后，并不能了解具体的使用，而有了算法，就可以将抽象的概念具体化，让我们有一个清晰的认识。

2.2 算法定义

什么是算法？算法就是描述解决问题的方法。一个被普遍认可的定义是：算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作

2.3 算法的特性

算法具有五个基本特性：输入、输出、有穷性、确定性和可行性

2.3.1 输入输出

**算法具有零个或多个输入，**大多数算法都会有输入参数，但一些个别情况例如打印“hello world”这样的代码，就不需要任何的输入参数。因此算法的输入可以是零个。**算法至少有一个或多个输出，**算法是一定需要输出的。输出的形式可以是打印输出，也可以是返回一个或多个值等。

2.3.2 有穷性

**指算法在执行有限的步骤之后，自动结束而不会出现无限循环，并且每个步骤在可接受的时间内完成。**当然，有穷的概念并不是纯数学意义的，而是在实际应用当中合理的，可以接受的“有边界”。

2.3.3 确定性

算法的每一步骤都有确定的含义，不会出现二义性，算法在一定条件下，只有一条执行路径，相同的输入只能有唯一的输出结果。

2.3.4 可行性

**算法的每一步都必须是可行的，也就是说每一步都能够通过执行有限次数完成。**可行性意味着算法可以转换为程序上机执行，并得到正确的结果。

2.4 算法设计的要求

2.4.1 正确性

算法的正确性是指算法至少应该具有输入、输出和加工处理无歧义性、能正确反映问题的需求，能够得到问题的正确答案。

2.4.2 可读性

算法设计的另一目的是为了便于阅读、理解和交流。

2.4.3 健壮性

一个好的算法还应该能对输入数据不合法的情况做合适的处理。比如输入的时间或者距离不应该为负数。
当输入数据不合法时，算法也能做出相关处理，而不是产生异常或莫名其妙的结果。

2.4.4 时间效率高和存储量低

时间效率指的是算法的执行时间，存储量需求指的是算法在执行过程中需要的最大存储空间，主要指算法程序运行时所占用的内存或外部硬盘存储空间。设计算法应尽量满足时间效率高和存储量低的需求。

2.5 算法时间复杂度

2.5.1 算法时间复杂度定义

在进行算法分析时，语句总的执行次数T(n)是关于问题规模n的函数，进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度，也就是算法的时间量度，记作：T(n)=O(f(n))。它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐进时间复杂度，简称为时间复杂度。其中f(n)树问题规模n的某个函数。

这样用大写O()来体现算法时间复杂度的记法，我们称为大O记法。一般情况下，随着n的增大，T(n)增长最慢的算法为最优算法。

2.5.2 推导大O阶方法

1.用常数1取代运行时间中的所有加法常数。

2.在修改后的运行次数函数中，只保留最高阶。

3.如果最高阶存在且不是1，则去除与这个项相乘的常数

得到的就是大O阶。

2.5.3 常数阶

如下面这个算法，它的时间复杂度是O(1)

int sum = 0, n = 100;
sum = (1+n)*n/2;     //执行一次
printf("%d", sum);

这个算法的运行次数函数是f(n) = 3,根据上面提到的推导大O阶的方法，用1代替常数，且不存在最高阶项，所以它的时间复杂度为O(1)。

如果算法中的sum = (1+n)*n/2执行了3次

int sum = 0, n = 100;
sum = (1+n)*n/2;     //执行第1次
sum = (1+n)*n/2;     //执行第2次
sum = (1+n)*n/2;     //执行第3次
printf("%d", sum);

无论n是多少，上面的两段代码就是执行了3次和5次的区别，这与问题的大小无关（n的大小），执行时间恒定的算法，我们称之具有O(1)的时间复杂度，又叫常数阶。

不管常数是多少，我们都记作O(1)，而不是O(3)、O(5)等

对于分支结构而言，无论真假，执行的次数都是恒定的，不会随着n的变大而变化，所以单纯的分支结构（if这种，不包括在循环结构中），其时间复杂度也是O(1)。

2.5.4 线性阶

线性阶的循环结构会复杂很多，要确定某个算法的阶次，我们常常需要确定某个特定语句或某个语句集运行的次数。因此，我们要分析算法的时间复杂度，关键就是要分析循环结构的运行情况。

如下面的这段代码，他的循环的时间复杂度为O(n)，因为循环中的代码要执行n次

int i;
for(i=0; i<n; i++)
{
    /*若里面是时间复杂度为O(1)的代码段*/
}

2.5.5 对数阶

再看下面这段代码：

int count = 1;
while(count < n)
{
    count = count * 2;
    /*下面是时间复杂度为O(1)的代码段*/
}

由于每次count乘以2之后，就离n更近一些。也就是说，x个2相乘后大于n，就会推出循环。由2^x = n 得 x = log2(n)。所以这个循环的时间复杂度为O(log2(n))。

2.5.6 平方阶

如下面的代码

int i, j;
for(i=0; i<n; i++)
{
    for(j=0; j<n; j++)
    {
        /*时间复杂度为O(1)的代码段*/
    }
}

这是一个循环嵌套，如同在线性阶分析的一样，是一个时间复杂度为O(n)的语句，再循环n次。所以这段代码的时间复杂度为O(n^2)。

如果外循环的循环次数改为了m，时间复杂度就变为O(m x n)。

int i, j;
for(i=0; i<n; i++)
{
    for(j=0; j<n; j++)
    {
        /*时间复杂度为O(1)的代码段*/
    }
}

由此可以总结得出循环的时间复杂度等于循环体的复杂度乘以该循环运行的次数

那么下面这个循环嵌套的时间复杂度是多少：

int i, j;
for(i=0; i<n; i++)
{
    for(j=i; j<n; j++)
    {
        /*时间复杂度为O(1)的代码段*/
    }
}

当i=0的时候，内循环执行了n次，当i=1时，内循环执行了n-1次，……当i=n-1时，执行了1次，所以总的执行次数为：n+(n-1)+(n-2)+⋯+1= n(n+1)/2 =n^2/2 + n/2， 然后只保留最高次项，即n^{2/2，去除常数，最后是n}2,最终得出这段代码的时间复杂度为O(n^2)。

对方法调用的时间复杂度

void function (int count)
{
    int i;
    for(i=count; i<n; i++)
    {
        /*若里面是时间复杂度为O(1)的代码段*/
    }
}

其实就是把循环放到了函数中，函数的时间复杂度为O(n)

如果是比较复杂的语句，例如把上面的代码都放在一起，那么计算时间复杂度的时候就是把执行次数都加在一起，最后根据大O的推导方法计算出时间复杂度。

2.6 常见的时间复杂度

常用的时间复杂度所耗费时间从小到大依次是：

O(1)< O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)

后四个时间复杂度，过大的n都会让结果变得不现实，如同噩梦般的运行时间，所以一般不作讨论。

2.7 最坏情况与平均情况

最坏情况运行时间是一种保证，就是运行时间不会再坏了。在应用中，这是一种最重要的需求，通常，除非特别指定，我们提到的运行时间都是最坏情况的运行时间。

平均运行时间是所有情况中最有意义的，因为它是期望的运行时间。现实中。平均运行时间很难通过分析得到，一般都是通过运行一定数量的实验数据后估算出来的。

对算法的分析，一种方法是计算所有情况的平均值，这种时间复杂度的计算方法称为平均时间复杂度。另一种方法是计算最坏情况下的时间复杂度，这种方法称为最坏时间复杂度。一般在没有特殊说明的情况下，都是指最坏时间复杂度。

2.8 算法空间复杂度

写代码时可以通过空间换时间，比如判断某一年是不是闰年，可以通过一个算法来实现，但是也可以建立一个数组，是闰年的，数组项置1，不是则为0；这样就只需要按照数组的索引来查找。由此运算的步骤算最小化了，但是就需要开辟这么大的内存来存储数组。

算法的空间复杂度通过计算算法所需的存储空间实现，算法空间复杂度的计算公式记作：S(n) = O(f(n)),其中n是问题的规模，f(n)为语句关于n所占存储空间的函数。

未完待续