概述：数据结构是计算机存储、组织数据的方式。数据结构分为逻辑结构、（存储）物理结构和数据的运算三个部分。常见的数据结构有：队列，树，堆，数组，栈，链表，图，散列表等。
1. 数据结构基本术语
数据：可以被计算机读取和处理的一些符号。
数据对象：性质相同的数据元素的集合，是数据的子集。
数据元素：数据组成的基本单位。
数据项：数据元素组成的最小单位。
他们直接的关系如下图：
2. 数据的逻辑结构与物理结构
2.1 逻辑结构：是指数据中数据元素之间的相互关系。分为线性结构与非线性结构。
2.1.1 线性结构：结构关系是一对一的，并且是一种先后的次序。
• 表现形式为：线性表、栈、队列、字符串等。
• 主要特征存在唯一的被叫做第一个和最后一个数据；
• 除第一个元素之外每个数据元素均有⼀个前驱；
• 除最后一个元素之外每个数据元素均有一个后继。
2.1.2 非线性结构：结构关系是一对多或者多对多或者没有对应关系只是同属于一个集合。
• 表现形式为: 树形结构、图形结构、集合结构。
• 树形结构: 元素结构关系是一对多。
• 图形结构: 结构关系是多对多的。
• 集合结构: 元素之间没有特殊的关系，只是属于一个集合。
2.2 物理结构：指的是数据的逻辑结构在计算机中的存储形式。分为顺序存储结构和链式存储结构。
2.2.1 顺序存储结构：是指把数据元素存放在一组地址连续的存储单元中。
2.2.2 链式存储结构：是把数据元素存放在任意的存储单元里，这组存储单元可以是连续的，也可以是不连续的，数据元素的存储关系并不能反映其逻辑关系，因此需要借助指针来表示数据元素之间的逻辑关系。
3. 算法
定义：算法就是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列， 并且每个指令表示一个或多个操作。算法的好坏直接决定计算机运行效率的高低。
3.1 算法与数据结构的关系
两者既有联系又有区别。联系是程序 = 算法 + 数据结构。数据结构是算法实现的基础，算法总是要依赖某种数据结构来实现的，算法的操作对象是数据结构。区别是数据结构关注的是数据的逻辑结构、存储结构等一些基本操作，而算法更多的是关注如何在数据结构的基本上解决实际问题。算法是编程思想，数据结构则是这些思想的基础。
3.2 算法的特性
• 有穷性，是指算法在执行有限的步骤之后，自动结束而不是出现无限循环，并且每一个步骤在可接受的时间内完成。
• 确定性，是指算法执行的每一步骤在一定条件下只有一条执行路径，也就是相同输入只能有唯一的输出结果。
• 可行性，是指算法每一步骤都必须可行，能够通过有限的执行次数完成。
• 输入，是指算法具有零个或多个输入。
• 输出，是指算法至少有一个或多个输出。
3.3 算法的设计要求
• 正确性，是指算法在执行结束后得到的结果是正确的。
• 可读性，是指算法的设计便于让人看懂。
• 健壮性，是指算法在任何输入情况下不出现崩溃的特性。
• 时间效率⾼和储存量低，是指算法运行花费的时间少和运行时所占用的内存的低。
3.4 算法的衡量标准
3.4.1 时间复杂度
算法的时间复杂度通常用大O符号表述，在进行算法分析时，语句执行次数 T(n) 是关于问题规模 n 的函数。进而分析次数 T(n) 随规模 n 的变化情况并确定 T(n) 的数量级。算法的时间复杂度就是算法的时间度量，记作T(n) = O(f (n) )。它表示随问题规模 n 的增大，算法的执行时间的增长率和 f(n) 的增长率相同，称作算法的渐进时间复杂度，简称为时间复杂度。其中，f(n) 是问题规模 n 的某个函数。
大O表示法规则：
• 用常数1取代运行时间中所有常数。如： 3->1 O(1)
• 在修改运行次数函数中，只保留最高阶项。如：n^3 + 2n^2+5 -> O(n^3)
• 如果最高阶存在且不等于1的常数，则去除这个项目相乘的常数。 如：2n^3 -> n^3
常见时间复杂度术语：
• 常数阶
//1+1+1+1+1+1+1 = 7 O(1)
void testSum2(int n) {
int sum = 0; //执行1次
sum = (1+n)*n/2; //执行1次
sum = (1+n)*n/2; //执行1次
sum = (1+n)*n/2; //执行1次
sum = (1+n)*n/2; //执行1次
sum = (1+n)*n/2; //执行1次
printf("testSum2:%d\n",sum); //执行1次
}
• 线性阶
//x=x+1; 执行n次 O(n)
void add2(int x,int n) {
for (int i = 0; i < n; i++) {
x = x+1;
}
}
• 对数阶
//2的x次方等于n x = log2n ->O(logn)
void testA(int n) {
int count = 1; //执行1次
//n = 10
while (count < n) {
count = count * 2;
}
}
• 平方阶
//1+(n+1)+n(n+1)+n^2+n^2 = 2+3n^2+2n -> O(n^2)
void testSum5(int n) {
int i,j,x=0,sum = 0; //执行1次
for (i = 1; i <= n; i++) { //执行n+1次
for (j = 1; j <= n; j++) { //执行n(n+1)
x++; //执行n*n次
sum = sum + x; //执行n*n次
}
}
printf("testSum5:%d\n",sum);
}
• 立方阶
//1+n+n^2+n^3+n^3 = 1+n+n^2+2n^3 -> O(n^3)
void testB(int n) {
int sum = 1; //执行1次
for (int i = 0; i < n; i++) { //执行n次
for (int j = 0 ; j < n; j++) { //执行n*n次
for (int k = 0; k < n; k++) { //执行n*n*n次
sum = sum * 2; //执行n*n*n次
}
}
}
}
• nlog阶
void testN(int n) {
int k,j,count = 0;
for (k = 1; k <= n; k *= 2) {
for (j = 1; j < n; j++) {
count ++;
}
}
}
• 指数阶(不考虑)
O(2^n)或者O(n!) 除非是非常小的 n，否则会造成噩梦般的时间消耗，这是一种不切实际的算法时间复杂度。一般不考虑！
3.4.2 空间复杂度
空间复杂度作为算法所需存储空间的量度，记做S(n) = O (f(n))。其中，n 为问题的规模；f(n) 为语句关于 n 的所占存储空间的函数。在考量算法的空间复杂度，主要考虑算法执行时所需要的辅助空间。
一般情况下，一个程序在机器上运行时，除了需要存储程序本身的指令、常数、变量和输入数据外，还需要存储对数据操作的存储单位。若输入数据所占空间只取决于问题本身，和算法无关，这样只需要分析该算法在实现时所需的辅助单元即可。若算法执行时所需的辅助空间相对于输入数据量而言是个常量，则称此算法为原地工作，空间复杂度为O(1)。
int n = 5;
int a[10] = {1,2,3,4,5,6,7,8,9,10};
//算法实现
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)
