数据结构基础概念小结
数据结构
什么是数据结构？
数据结构包括逻辑结构和物理结构以及他们的联系。
- 逻辑结构
1.集合 —–同一类型
2.线性结构 —–一对一
3.树形结构 —–一对多
4.图状结构(网状结构) —–多对多 - 物理结构/存储结构
描述数据具体在内存中的存储方式，大体上有顺序结构，链式结构，索引结构，哈希结构。
- 时间复杂度
算法的执行时间与原操作执行次数之和成正比。
时间复杂度由小到大有：O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3)
幂次时间复杂度由小到大有：O(2^n) < O(n!) < O(n^n)
线性表 —– 线性结构
头节点，中间节点，尾结点组成。头节点无前驱，尾节点无后继。其中链表只能顺序查找。
2
3
4
5
6
7
|
|———— 静态链表 ： 用一维数组来实现线性链表。所谓静态指的是表的容量一定。(因为数组)
|
|———— 循环链表 ： 头尾相接的链表。
|
|———— 双向链表 ： 循环链表的基础上，每个节点增加前驱，每个节点可双向出发。
栈
栈也是一种线性表，但是它被限制在一端插入与输出，这端叫作栈顶(top)，另一端为栈底(bottom)。因此可以知道，栈的进栈出栈方式是先进后出。当top = 0时不是代表空栈，而是只有一个元素，空栈时top = -1。
栈也可以形成链式存储结构，称为链栈。操作仅限在栈顶，头指针也就是栈顶指针。
2
3
4
5
6
e <----- 栈顶
栈顶 ------> d 插入e d 删除 d <----- 栈顶
c ==> c ==> c
b ==> b ==> b
栈顶 ------> a a <----- 栈底 a <----- 栈底
队列
队列与栈有所相似，也是运算受限的线性表。对于队列，只能在一端删除，一段插入，删除端叫队头(front),插入一端叫队尾(rear)，进出栈方式为先进先出。