数据结构与算法 - 第一章：绪论 - 《计算机专业课笔记》

数据结构的概念
抽象数据类型
算法和算法分析
- 算法
💡关于大O记法（重点）

数据结构的概念

什么是数据结构

在计算机中解决问题的一般步骤：

数学模型→选择计算机语言→编出程序→测试→最终解答

其中最重要的部分，就是建立数学模型的部分。这一个过程包含了两部分：

分析出解决问题需要面对的操作对象
寻找出这些操作对象之间的关系，用数学的语言描述

以上就是构建数据结构的过程。

数据结构分类

数值计算类模型
非数值计算类模型

了解即可

基本概念和术语

数据相关概念

名称	描述
数据	对信息的一种符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。
数据元素	数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。
数据项	一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小标识单位。
数据结构	是相互之间存在一种或多种特定关系的数据元素的集合。数据结构主要指逻辑结构和物理结构。

举个例子：

在上图中，**数据**就是整张表格，**数据元素**就是一行的数据，**数据项**就是一行数据中的一个属性，而上图中的数据结构就是一张表。

数据结构概念

名称	描述
集合	结构中的数据元素除了同属于一种类型外，别无其它关系。
线性结构	结构中的数据元素之间存在一对一的关系，如线性表、栈、队列。
**	结构中的数据元素之间存在一对多的关系，如树。
图状结构或网状结构	结构中的数据元素之间存在多对多的关系。

四种基本结构如图所示：

两种结构类型

数据的结构有两种：

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

所谓的逻辑结构，也就是上一小节里面的数据结构，是一种逻辑上的模型。所谓的存储结构，指的是数据实际在计算机内存上的结构。
逻辑结构对应的是抽象的数据结构，存储结构对应实际的物理结构。
所谓内存就是实际存储数据的地方：

如图所示，就是一个内存的样子。其中左侧的1 - 1M-1表示的是内存地址，右侧方框内就用于存放实际的数据。

两种映像

映像指的是一种一一对应的关系，这里的映像指的就是数据在内存上的映射。有两种不同的映射：

**顺序存储结构**：数据在内存上的存储是连续的，计算机通过连续的内存地址进行访问
**链式存储结构**：数据在内存上的存储是非连续的，计算机通过数据携带的下一个内存地址进行访问

第一章：绪论 - 图4
顺序存储
第一章：绪论 - 图5
链式存储
从上面两张图中很容易发现，顺序存储方式获取数据方便，所需要的空间也小。链式存储就需要额外在数据内容存储下一条数据的地址。

这里只需要简单了解一下，后续内容会线性表一章继续讲解。

抽象数据类型

基本概念

数据结构总共包含三样东西：

数据对象
数据关系
基本操作

其中**数据对象**和**数据关系**合并称为数据结构的静态特征，**基本操作**则是动态特征。

数据类型

数据的类型大致可以分为两种：

原子类型（int, float,char,指针,枚举型等）
结构类型（数组，结构体，联合体）

所谓原子类型，就是基本的数据类型，能直接在编辑器里面被定义，而结构类型实际上就是多个原子类型构成的复合类型。

一般结构类型的数据，我们叫做抽象数据类型，指一个数学模型以及定义在该模型上的一组操作，例如数组，就是一种抽象数据类型。

表示方法

抽象数据类型可用以下三元组表示:(D,S,P)
格式：

ADT抽象数据类型名{ 数据对象D:<数据对象的定义> 数据关系S:<数据关系的定义> 基本操作P:<基本操作的定义> }ADT抽象数据类型名

基本操作的定义如下：

操作名<参数表> 初始条件：< 初始条件描述> 操作结果：< 操作结果描述>

说明: (1)赋值参数只为操作提供输入值，以&开头的是引用参数，不但提供输入值，还返回操作结果。 (2)初始条件描述了操作执行之前数据结构和参数应该满足的条件。 (3)操作结果说明了操作正常完成后，数据结构的变化状况和应返回的结果。这一部分后续会详细解释什么意思。

算法和算法分析

算法

算法的概念

概念：算法(Algorithm)是为了解决某类问题而规定的一个有限长的操作序列。
一个算法必须满足以下五个重要特性:

**有穷性**：算法可以再有限的步数内执行完毕
**确定性**：任何条件下，算法只有一条执行路径，对应每一种输入，输出都是唯一的
**可行性**：算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现之
**输入**：有零个或多个输入，取自特定的对象集合
**输出**：有一个或多个输出，是算法进行信息加工后得到的结果

算法设计的基本原则
**正确性**：
1. 算法中不含有语法错误
2. 输出的数据需要满足预期的结果
3. 算法输出的所有数据都需要保证正确，包括边界值特殊值等。
**可读性**：算法主要是为了人的阅读与交流，其次才是为计算机执行。因此算法应该易于人的理解。
**健壮性**：当输入的数据非法时，算法应当恰当地作出反映或进行相应处理，而不是产生莫名奇妙的输出结果。
**效率与低存储量需求**：通常，效率指的是算法执行时间；存储量指的是算法执行过程中所需要的最大存储空间。一般我们追求的算法，尽量需要满足执行时间短，存储空间小。

例题

说出下面两个代码不符合算法的什么特征和要求？

void suanfa1()
{
    int i,s=0;
    for (i=0;i>=0;i++)
        s++;
}

很明显，这个函数的for循环是停止不下来的，不满足算法的**有穷性**。

float suanfa2( )
{ 
    int x;  float y;
    scanf("%d", &x);
    y=sqrt(x);  
    return(y);
}

这里的问题在于如果输入了一个非法的数据，比如-1，这个函数会输出-nan，不满足**健壮性**。
算法2可以使用一下的代码实验一下：

#include <math.h>
#include <stdio.h>
float suanfa2( )
{ 
    int x;  float y;
    scanf("%d", &x);
    y=sqrt(x);  
    return(y);
}
int main(void) {
    printf("输入一个整数\n");
    float y =suanfa2();
    printf("%f",y);
    return 0;
}

结果如下：

💡关于大O记法（重点）

大O记法是一种衡量算法好坏的方式。
我们前面说过，衡量算法好坏的标准有两个：

算法执行的效率
算法执行所需要占用的空间

其中算法执行的效率最直观的感受，就是算法所需要执行的时间，以排序算法为例，如果需要把一个混乱的数组从大到小排序完毕，那么运行的时间就能很好的反应这个排序算法的效率。

但是这种事后比较的方法有很多因素影响：

数组原始大小不同会影响整体排序的速度
每个人计算机性能不一样，也会影响整体排序的速度
必须执行源程序才能知道效率
…

所以一般不采用这种事后排序的方法，而采用事前提前计算的方法，这就是大O记法。

大O记法

**大O记法**是一个不用具体的测试数据和测试环境，就可以粗略的估算执行效率的方法，这个方法我们称之为复杂度。其中包含了两个层次的复杂度：

**时间复杂度**：让程序运行时间更短的指标，对应的就是算法的执行效率。
**空间复杂度**：让程序运行所消耗的内存更少的指标，对应的就是算法执行所需要占用的空间。

一般情况下，我们只计算时间复杂度，所以说复杂度，如果没有特指，那么就是只指向时间复杂度。

时间复杂度

时间复杂度的基本单位被叫做**步数**：数组每次索引值的读取，就算作一步，也被称之为unit_time。
简单来说，就是计算机从内存中每读取一个数据，就算作一步。
下面通过两个例题感受一下：

例题一

int a[4] = {1,2,3,4};
printf("%d",a[0]);

上面的step1就是读取数组中第0个的值，把这个时间称作**一步**。
在计算机底层，可以通过任意一步跳到任意一个索引的位置进行数据的读取。
所以无论数组长度多少，获取数组中任意一个值的时间都是一步。
如果用大O记法就是常数时间—-O(1)

例题二

int factorial(int n) {
    int result = 1; //step1
    for (int i = 1; i <= n; i++) { //step2
        result *= i;  // step3
    }
    return result;
}

第一章：绪论 - 图7
大O记法是数据随着规模增长的变化趋势。
而这种情况下常量和系数部分并不会随着数据规模变化而变化，所以可以忽略。

所以上面的O(2N+2)也可以写成O(N)。

在看一个平方级别的例子：

void sum(int m,int n)  
{
    int i,j,s=0;        // 1次
    for(i=1；i<=m；i++)     // m次
    { 
        for(j=1；j<=n；j++)  // m*n次
            s++;              // m*n次
         printf(“%d”,s);     // m次
     } 
}

初始赋值s，计算机访存1次。（注意这里只是定义了i和j，并没有赋值，所以无需访存）
第一层循环，总共循环了m次，每次循环都需要给i赋值，就是访存了**m**次
第二层循环是在第一层循环下进行的，同理于上，每次一层循环都需要进行n次二层循环，所以需要访存**m*n**次
循环内部s++同样伴随循环进行m*n次，因为s++ 等同于 s = s+1，实际还是访存，所以访存**m*n**层
最后输出实际还是要访存（访问内存获取需要的数据s），总共进行**m**次

那么：

其中: f(m,n)=1+m+2mn+m=2mn+2m+1
当m=n时,f(n)=2n2+2n+1
T(n)=O(f(n))=O(2n2+2n+1)=O(n2) O(n2) 称成为平方阶/平方数量级

总结
大O记法：指数级别＞线性级别＞对数级别＞常数级别。

空间复杂度（可以忽略）

如何计算空间复杂度

一个基础的数据类型就是一个基础单位。

优先考虑时间复杂度

实际编程过程中是优先考虑时间复杂度的。

类C语言（了解即可）

预定义常量和类型

#define TRUE 1;  \\定义TRUE的值为1
#define FALSE 0;
#define OK 1;
typedef int Status;\\定义Status为int类型

类C语言的赋值

简单赋值：变量名=表达式;
串联赋值：变量名1=变量名2=…变量名k=表达式;
成组赋值：

（变量名1，…变量名k)=(表达式1，…,表达式k);
结构名=结构名;
结构名=(值1，…，值k) ;
变量名[起始下标..终止下标]=变量名[起始下标..终
止下标];

交换赋值:变量名<—>变量名;
条件赋值:变量名=条件表达式?表达式T:表达式F;

注意条件赋值里面，当条件表达式为真的时候，变量的值为T，反之则为F。

基本函数

求最大值：max(表达式1，…，表达式n)
求最小值：min(表达式1，…，表达式n)
求绝对值：abs(表达式)
求不足整数值：floor(表达式)
求进位整数值：ceil(表达式)
判定文件结束：eof(文件变量)或eof
判定行束：eoln(文件变量)或eoln

第一章：绪论