【数据结构】数据结构前置知识

基本概念与术语

概念皆来自于《大话数据结构》。

数据

数据的概念：是描述客观事物的符号，是计算机中可以操作的对象，是能被计算机识别并输入给计算机处理的符号集合。
其实就是可以输入到计算机中，可以被计算机处理的字符。像文件，图像，声音，数字等等都是可以通过编码转换为字符来处理。

数据元素

数据元素的概念：是组成数据的，有一定意义的基本单位，在计算机中通常作为整体处理，也称为记录。

就像数学中由多个集合（子集合）构成的集合。子集就像数据元素一样

数据项

数据项概念：一个数据元素可以由若干个数据项组成。
数据项就像集合中的元素。

数据对象

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

关系：
用∈代替一下‘包含于’关系
数据项∈数据元素∈数据对象∈数据

数据结构

数据结构概念:是互相之间存在一种或多种特定关系的数据元素的集合。

逻辑结构和物理结构

这是根据视点来区分的数据结构。

物理结构

物理结构：是指数据的逻辑结构在计算机中的存储形式。

顺序存储结构

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

链式存储结构

是把数据元素存放在任意位置的存储单元里，这组存储单元可以是连续的，也可以是不连续的。

逻辑结构

是指数据对象中数据元素之间的相互关系。

集合结构

集合结构中的数据元素除了同属于一个集合外，他们之间没有其他关系。

线性结构

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

树形结构

树形结构中的数据元素之间存在一种一对多的层次关系。

图形结构

图形结构中的数据元素是多对多的关系。

算法

算法的定义：算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列。并且每条指令表示一个或多个操作。
算法五大特性：输入，输出，有穷性，确定性，可行性。

当多个算法都可以解决问题（在保证了正确性、可读性、健壮性），我们一般要考虑算法的时间效率，空间效率。我们就要用时间复杂度和空间复杂度来衡量。

时间复杂度和空间复杂度

其实我们要求时间复杂度就把语句执行次数给加起来表示为一个函数，空间复杂度开辟空间次数加起来表示为一个函数。然后将函数由大O的渐进表示法来表示。求得的就是复杂度。

我们通常使用大O的渐进表示法来表示时间复杂度和空间复杂度。

大O的渐进表示法

规则：
1.用常数1来取代运行时间中的所有加法常数；
2.在修改后的运行次数函数中，只保留最高阶项；
3.如果最高阶项存在且系数不为1，则将系数修改为1。

时间复杂度

常数阶

int n = 100;
int sum = (n+1)*n/2;

这个高斯公式求和就是函数为3，常数都表示为1，大O渐进法（时间复杂度）表示就是O(1)。

线性阶

int n = 100;
int sum = 0;
for(int i = 0; i < n; i++){sum += i; 
} 

这个求和就是函数为n+2，保留最高阶，大O渐进法（时间复杂度）表示就是O(n)。

对数阶

int count = 1;
while(count < n){count *= 2;
}

这个就是函数为logN+1，保留最高阶，大O渐进法（时间复杂度）表示就是O(logN)。

平方阶

for(int i = 0; i < n; i++){for(int j = 0; j < n; j++){System.out.print("0 ");}
}

这个的函数为nn + 1，保留最高阶，大O渐进法（时间复杂度）表示就是O(nn)。

常见时间复杂度

O(1) < O(logN) < O(N) < O(NlogN) < O(NN) < O(2^N) < O(N!) < O(N*N)

空间复杂度

空间复杂度和时间复杂度求法完全一样，只不过是将执行次数变为开辟空间次数。

int factorial(int N) {return N < 2 ? N : factorial(N-1)*N;
}

如上面代码每一次调用都要开辟一次，递归了N次。空间复杂度就是O(N)。

最好情况与平均情况于最坏情况

最好情况就是当前要解决的问题完全契合当前算法。像写一个冒泡排序，给的数组本身就是有序的，此时直接返回值时间复杂度就是O(1)。

平均情况就是所有情况中最有意义的，因为它是期望的运行时间。

最坏情况，一般不说明我们像上面将诉的方法求的复杂度一般是最坏情况。