📖【数据结构与算法】第一章：基本概念及术语
📝1️⃣为什么要学习数据结构与算法？
✨数据结构所处的地位

由图可以很直观的看出，数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。

✨数据结构的用处
编程基础
计算机及相关专业考研考博必修课程
计算机等级考试
程序员考试课程
✨数据结构在计算机学科中的地位

Web信息处理：队列、图、字符、矩阵、哈希表等；
人工智能：广义表、集合、有向图、搜索树等；
图形图像：队列、栈、图、矩阵、空间索引树等；
数据库：线性表、多链表、排序、B+树等；
操作系统：队列、存储管理、表、排序、目录树等；
编译原理：字符串、栈、哈希表、语法树等；
程序设计语言
概率论与数理统计
计算机概论
集合论与图论
📝2️⃣数据结构与算法研究的内容
沃思（Niklaus Wirth）教授提出一个经典的等式：程序 = 算法 + 数据结构。

✨电子计算机的主要用途
早期：数值计算。

后期：处理逐渐扩大到非数值计算领域，能处理多种复杂的具有一定结构关系的数据。

对求解非数值计算的问题，设计出合适的数据结构及相应的算法，即首先要考虑对相关的各种信息如何表示、组织和存储。

由此可见，数据结构的研究内容为：研究非数值计算的程序设计问题中计算机的操作对象以及他们之前的关系和操作。

📝3️⃣基本概念及术语
✨数据
所有能输入计算机中区的描述客观事物的符号。可分为：

数值性数据
非数值性数据（多媒体信息处理）
✨数据元素
数据的基本单位，也称为结点（node）或记录（record）

✨数据项
有独立含义的数据最小单位，也称域（field）

三者之间的关系：数据 > 数据元素 > 数据项

例如：学生表 > 个人记录 > 学号、姓名...

✨数据对象
相同特性数据元素的集合，是数据的一个子集

整数数据对象
N = {0, 1, 2, ...}
学生数据对象：学生记录的集合
✨数据结构
相互之间存在一种或多种特定关系的数据元素的集合

数据结构是带“结构”的数据元素的集合，“结构”指数据元素之间存在的关系。
📝4️⃣数据结构的两个层次
✨逻辑结构
数据元素间抽象化的相互关系，与数据的存储无关，独立于计算机，他是从具体问题抽象出来的数据模型。

✨存储结构（物理结构）
数据元素及其关系在计算机存储器中的存储方式。

✨存储结构两大类：顺序存储结构和链式存储结构
顺序存储结构：

借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。

链式存储结构：

借助指示元素存储地址的指针表示数据元素间的逻辑关系。

✨两种结构的划分方法
方法一：根据每个节点的前去后继

线性结构：

有且仅有一个开始和一个终端节点，并且所有节点都最多只有一个直接前驱和一个后继。

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

非线性结构：

一个节点可能有多个直接前驱或后继。

方法二：是否存在一对一或多对一的关系

集合：

数据元素间除“同属于一个集合”外，无其他关系。

线性结构:

一个对一个，如线性表、栈、队列。

树形结构：

一对多，如树。

图形结构：

多对多，如图。

📝5️⃣数据的运算
逻辑结构和存储结构都相同，但运算不同，则数据结构不同，例如，栈和队列。

对于一种数据结构，常见的运算：增、删、改、查、排序。

📝6️⃣数据类型
✨定义
在一种程序设计语言中，变量所具有的数据种类。

FORTRAN语言：整型、实型、复数型。
C语言：
基本数据类型：char int float double void 
构造数据类型：数组、结构体、共用体、文件

✨抽象数据类型
跟高层次的数据抽象。
由用户定义，用以表示应用问题的数据模型。
由基本的数据类型组成，并包括一组相关的操作。
抽象数据类型可以用以下的三元组来表示：

ADT  = （D ，S，P）

D 数据对象
S D上的关系集
P D上的操作集

ADT 抽象数据类型名{

数据对象：< 数据对象的定义 >

数据关系：< 数据关系的定义 >

基本操作：< 基本操作的定义 >

}ADT抽象数据类型名
使用抽象数据类型可以实现 信息隐蔽和数据封装，使用与实现相分离。

 ✨抽象数据类型的表示与实现
抽象数据类型可以通过固有的数据类型（如整型、实型、字符型等）来表示和实现。
它有些类似C语言中的结构（struct）类型,但增加了相关的操作。
文中的类C语言作为描述工具，上机时要用具体语言实现，如C或C++等。以下简单介绍一些表示语句。

1.预定义常量及类型。

//函数结果状态代码

define OK 1

define ERROR 0

define OVERFLOW -2

//Status 为函数返回值类型，其值是函数结果状态代码

typedef int Status;
2.数据元素被约定为 ElemType 类型，用户需要根据具体情况自行定义该数据类型。

3.算法描述为以下的函数形式：

函数类型 函数名 (函数参数表)
{

语句序列;

}
 4.内存的动态分配与释放

使用 new 和 delete 动态分配和释放内存空间;
分配空间 指针变量=new 数据类型;
释放空间 delete指针变量;
5.赋值、选择、循环语句基本和C语言保持一致。

6.结束语句形式

函数结束语句 return;
循环结束语句 break;
异常结束语句 exit(异常代码);
 7.输入输出语句形式

输入语句 cin(scanf());
输出语句 cout(printf());
 8.扩展函数有

求最大值 max
求最小值 min
📝7️⃣算法与算法分析
✨初始算法
定义：一个有穷的指令集，这些指令为解决某一特定任务，规定了一个运算序列。

描述：自然语言流程图，程序设计语言伪码。

特性：

输入：有0个或多个输入
输出：有一个或多个输出（处理结果）
确定性：每部定义都是确切、无歧义的
有穷性：算法应在执行有穷步后结束
有效性：每一步运算应足够基本
评价：如何评价一个算法可以从以下四个性质出发。

效率：用依据该算法编制的程序在计算机上执行所消耗的时间来度量。

事后统计：利用计算机内的计时功能，不同算法的程序可以用一组或多组相同的统计数据区分。
缺点：必须运行依据算法编制的程序，所得时间统计量依赖于硬件软件等环境因素，掩盖算法本身的优劣。
事前分析估计：一个高级语言程序在计算机上运行所消耗的时间取决于：
依据的算法选用那种策略
问题的规模
程序语言
比那依程序产生及其代码质量
机器执行指令速度
        同一个算法用不同的语言、不同的编译程序、在不同的计算机上运行，效率均不同，使用绝对时间单位衡量算法效率不合适。

✨算法时间复杂度的渐进表示法
算法中基本语句重复执行的次数是问题规模n的某个函数f(n)，算法的时间量度记作：T(n)=O(f(n))

 基本语句重复执行的次数：

算法中重复执行次数和算法的执行时间成正比的语句。
对算法运行时间的贡献最大。
问题规模n：n越大，算法执行时间越长。

场景 n
排序 记录数
矩阵 矩阵的阶数
多项式 多项式的项数
集合 元素个数
树 树的结点个数
图 图的定点数或边数
✨分析算法时间复杂度的基本方法
找出语句频度最大的那条语句作为基本语句
计算基本语句的频度，得到问题规模 n 的某个函数 f(n)
忽略掉低次幂和常数项，取最高次幂。
取其数量级用符号“o”表示
例如：

x=0;y=0;
for(int k = 0; k < n ; k++){

x++;//语句频度 n

}

for(int i = 0; i < n ; i++){
for(int j = 0; j < n ; j++){

   y++;//语句频度 n^2

}
}
由于 n^2 > n，因此 f(n) = n^2，时间复杂度 T(n) = o(n^2)。 

时间复杂度由嵌套最深层语句的频度所决定.

void exam ( float x[][], int m, int n){

float sun [];
for( int i = 0; i< m ; i ++){
    sum[i] = 0.0;//第一层嵌套，执行频度m
    for( int i = 0; i< n ; i ++){
        sum[i] += x[i][j];//第二层嵌套，执行频度m * n
    }
}

for( int i = 0; i< m ; i ++){
    cout << i << ": " << sum[i] << endl;           
}

}
 这时的 f(n) = nm，时间复杂度 T(n) = o(nm)。

有些情况下，算法的基本操作重复执行的次数还随问题的输入数据集不同而不同。

//顺序查找
for(int i = 0; i< n ; i++){

if(a[i] == e)
    return i+1；
return 0;

}
 最优情况：1        最坏情况：n       

此时的 o(n) 取平均时间复杂度：（n+1）/2。

时间复杂度按数量级递增顺序：

 ✨渐进空间复杂度
空间复杂度：算法所需存储空间的度量，记作 S(n) = O(f(n))，n为问题的规模。

for(int i=0;i<n/2;i++){

t=a[i];
a[i] = a[n-i-1];
a[n-i-1]=t;

}
 S(n) = O(1),相当于原地工作。

for(int i=0;i<n;i++)

b[i] = a[n-i+1];

for(int i=0;i<n;i++)

a[i] = b[i];

 S(n) = O(n)。

​