一、基础常识：

1、数据结构-基础数据单元

数据：是描述客观事物的符号，是计算机中可以操作的对象，是能被计算机识别，并输入给计算机处理的符号集合。数据不仅仅包括整型、实型等数值类型，还包括字符及声音、图像、视频等非数值类型；可以输入到计算机中；能被计算机程序处理；

数据对象: 性质相同的数据元素的集合<数据的子集>

数据元素: 数据的基本单位，且有一定意义的基本单位,在计算机中通常作为整体处理<一个数据元素可以由若干数据项组成>

数据项: 组成数据元素的最小单位

数据结构: 指的数据对象中的数据元素之间的关系.

数据类型：是指一组性质相同值的集合以及定义在此集合的一些操作的总称。

image

2、数据结构

image

逻辑结构是指在数据中数据元素之间的相互关系。数据元素之间存在不同的逻辑关系构成了以下4种结构类型

1）集合结构：集合的数据元素没有其他关系，仅仅是因为他们挤在一个被称作“集合”的盒子里。

2）线性结构：线性的数据元素结构关系是一对一的，并且是一种先后的次序。

3）树形结构：树形的数据元素结构关系是一对多的。

4）图结构：图的数据元素结构关系是多对多的。如一个城市的电线网

存储结构，也称为物理结构，指的是数据的逻辑结构在计算机中的存储形式。数据的存储结构一般可以反映数据元素之间的逻辑关系。<u style="box-sizing: border-box;">分为顺序存储结构和链式存储结构。</u>

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

2）链式存储结构：是把数据元素存放在任意的存储单元里，这组存储单元可以是连续的，也可以是不连续的，数据元素的存储关系并不能反映其逻辑关系，因此需要借助指针来表示数据元素之间的逻辑关系。

3、算法

算法 是解决特定问题求解步骤的描述，在计算机中表现为有限的操作序列。在数据类型建立起来之后，就要对这些数据类型进行操作，建立起运算的集合即程序。

程序=算法+数据结构

算法的五大特性

1）有穷性，是指算法在执行有限的步骤之后，自动结束而不是出现无限循环，并且每一个步骤在可接受的时间内完成。

2）确定性，是指算法执行的每一步骤在一定条件下只有一条执行路径，也就是相同输入只能有一个唯一的输出结果。

3）可行性，是指算法每一步骤都必须可行，能够通过有限的执行次数完成。

4）输入，是指算法具有零个或多个输入。

5）输出，是指算法至少有一个或多个输出。

算法的设计要求

正确性 可读性 健壮性 时间效率高和存储量低

时间复杂度

常见时间复杂度从小到大依次排列：O(1) < O(log2n) < O(n) < O(n²）<O(n³) ····<O(n!)

在计算后的运行次数函数中，只保留最高阶项

空间复杂度

int n = 5;
 int a[10] = {1,2,3,4,5,6,7,8,9,10};    //算法实现(1)
 int temp;
 for(int i = 0; i < n/2 ; i++){
        temp = a[i];
        a[i] = a[n-i-1];
        a[n-i-1] = temp;
 }
以上例子只需要用到辅助空间temp，所以空间复杂度为O(1)

int b[10] = {0};
for(int i = 0; i < n;i++){
    b[i] = a[n-i-1];
 }
for(int i = 0; i < n; i++){
        a[i] = b[i];
}
这个例子中需要用到b(n）的辅助空间，所以空间复杂度为O(n)