数据结构与算法

1 数据结构

1.1 动态数组

① 数组特点

存储特点： 连续存储
优点：查找块，访问元素快
缺点：插入、删除元素效率低

② 实现思路

1. 初始化： malloc() 动态分配内存区域
2. 扩展长度： realloc() 重新调整内存区域大小
3. 插入元素： 插入位置，后面所有元素后移
4. 删除元素： 删除位置，后面所有元素前移

1.2 链表

① 链表分类

单向链表
双向链表
循环单向链表
循环双向链表

② 链表特点

存储特点： 分散存储
优点：添加删除节点效率高，链表扩展方便
缺点：查找效率低，需要额外开销（每个节点要存储下一个节点的地址）

③ 实现思路

1. 每个节点需要单独的内存空间， 每个节点存储数据和下一个节点的地址
2. 查找节点：从头结点开始一个一个的数
3. 添加新节点： 上一个节点指向新节点，新节点指向下一个节点
4. 删除节点：直接上上一个节点指向下下个节点（把要删除的节点跳过）
5. 释放内存：遍历挨个释放每个节点的内存

1.3 栈

① 特点

先进后出，后进先出

② 专业名词

栈顶（Stack Top）：	   允许插入、删除元素的一端
栈底（Stack Bottom）：  不允许插入、删除元素的一端
空栈： 没有元素的栈

进栈（入栈、压栈、Push）： 添加新元素
出栈（弹栈、Pop）：		  删除（最上面的）栈顶的元素

1.4 队列

① 特点

先进先出，后进后出

② 专业名词

队首（front）： 删除元素的一端
队尾（rear）：  添加元素的一端
空队列：没有元素的队列

入队（进队、unshift）： 从队尾添加元素
出队（离队、shift）： 从队首删除元素

2 算法

2.1 算法评价标准

① 时间复杂度

描述程序的执行效率

n值     O(n)执行次数    O(logn)执行次数
1		  1                0
2         2                1
3         3                
4         4                2
5         5
6         6
7         7
8         8                3

O(1) < O(logn) < O(n) < O(n * logn) O(n^2)

② 空间复杂度

描述程序的内存占用情况

2.1 查找算法

1. 顺序查找 (线性查找)
   时间复杂度： O(n)

2. 二分查找
   必须是有序的数组
   时间复杂度：O(logn)

2.2 排序算法

1. 冒泡排序
2. 快速排序