数据结构与算法（笔记）_算法t(n)

数据结构与算法

1 基础知识点

（1）空间复杂度和时间复杂度

空间复杂度S(n):程序执行时占用存储单元的长度。
时间复杂度T(n):程序执行时耗费时间的长度。

• 在分析一般算法的效率时，常关注以下两种复杂度

  1）最坏情况复杂度 $$Tworse（n）$$
  2）平均复杂度 $$Tavg（n）$$

（2）线性表及其实现

1）什么是线性表
1

由同类型数据元素构成有序序列的线性结构

• 表中元素个数成为线性表的长度

• 线性表没有元素时，称为空表

• 表起始位置称为表头，结束位置称为表尾
  2）什么是广义线性表

• 广义表是线性表的推广

• 对于线性表而言，n个元素都是基本的单元

• 广义表中，这些元素不仅可以是单元素也可以是另一个广义表
  3） 什么是多重链表
  多重链表：链表中的节点可能同时隶属于多个链

（3） 数组和链表的区别

一、什么是数组、链表

数组和链表是两种不同的基本数据结构，它们在内存存储上的表现不一样，所以也有各自的特点。

1、数组

数组是一组具有相同数据类型的变量的集合，这些变量称之为集合的元素；

每个元素都有一个编号，称之为下标，可以通过下标来区别并访问数组元素，数组元素的个数叫做数据的长度；

2、链表

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的

链表的特性是在中间任意位置插入和删除元素都非常快，不需要移动其它元素

对于单向链表而言，链表中的每一个元素都要保存一个指向下一个元素的指针

对于双向链表而言，链表中的每个元素既要保存指向下一个元素的指针，又要保存指向上一个元素的指针

对于双向循环链表而言，链表中的最后一个元素保存一个指向第一个元素的指针

二、数组、链表的优缺点

1、数组的优点和缺点

优点：

随机访问性强
查找速度快，数组在内存中顺序存储，可通过下标访问，访问效率高
数组从栈上分配内存，使用方便
缺点：

插入和删除效率低，需要移动其他元素
数组元素减少时，可能浪费内存
内存空间要求高，必须有足够的连续内存空间
使用数组之前，必须事先固定数组长度，不支持动态改变数组大小；
数组的大小是固定的，所以存在访问越界的风险
2、链表的优点和缺点

优点：

插入删除速度快
内存利用率高，不会浪费内存
大小没有固定，拓展很灵活，链表从堆上分配内存，自由度大
缺点：

不能随机查找，必须从第一个开始遍历，查找效率低（数组的大小是固定的，所以存在访问越界的风险）

（4）什么是堆栈

堆栈（Stack）:具有一定操作约束的线性表
只在一端（栈顶，Top）做插入、删除

• 插入数据：入栈（Push)
• 删除数据：出栈（Pop）
• 后入先出：Last in First Out（LIFO）
  堆栈可以由数组或链式存储实现。

（5）什么是队列

队列（Quene）：具有一定操作约束的线性表

• 插入和删除操作，只能在一端插入，而在另一端删除。
• 数据插入：入队列（AddQ）
• 数据删除：出队列（DeleteQ）
• 先来先服务
• 先进先出：FIFO

（6）什么是树

1）二叉树

二叉树T：一个有穷的结点集合
这个集合可以为空
若不为空，则它是由根节点和称为其左子树Tl和右子树Tr的两个不相交的二叉树构成。
（1）完全二叉树，层序遍历不存在空的树。
公式：

• n:总结点 n0:度为0的结点
• n1:度为1的结点
• n2:度为2的结点

1.树的必记公式：n = n0+n1+n2+…
2.二叉树必记公式:n0=n2+1
3.完全二叉树必记公式:n1 = 0或者n1 = 1

1.二叉树的遍历

（1）先序遍历
遍历过程为：

• 访问根节点
• 先序遍历其左子树
• 先序遍历其右子树
  （2）中序遍历
• 中序遍历其左子树
• 访问根节点
• 中序遍历其右子树
  （3）后序遍历
• 后序遍历其左子树
• 后序遍历其右子树
• 访问根节点

(7)什么是二叉搜索树

查找问题：
- 静态查找和动态查找
二叉搜索树（BST）也称二叉排序树或二叉查找树。

（8）什么是平衡二叉树

平衡因子（BF），BF(T)=Hl-Hr，其中Hl和Hr分别为T的左右子树的高度。
平衡二叉树（AVL树）：空树或者任一节点左右子树高度差的绝对值不超过1.

• 给定节点数为n的AVL树的最大高度为O(LOG2N)

平衡二叉树的调整

RR右旋
LL旋转
LR旋转
RL旋转

（7）什么是抽象的链表

• 有地方存数据
• 有地方存指针-下一个结点的地址

(8) 什么是堆（heap）

优先队列：特殊的队列，取出元素的顺序是按照元素的优先权大小，而不是进入队列的先后顺序。
堆的两个特性：

• 结构性：用数组表示的完全二叉树
• 有序性：任一节点的关键字是其子树所有节点的最大值（最小值）
  – 最大堆，也称大顶堆，最大值
  –最小堆，也称小顶堆，最小值
  堆中路径

（9）什么是哈夫曼树

带权路径长度（WPL）：设二叉树有n个叶子节点，每个叶子结点带有权值Wk，从根结点到每个叶子结点的长度为Ik，则每个叶子结点的带权路径长度之和就是：WPL=（WkIk）之和。
最优二叉树或哈夫曼树：WPL最小的二叉树。
哈夫曼树的构造：
每次把权值最小的两颗二叉树合并
哈夫曼树的特点：

• 没有度为1的结点
• n个叶子结点的哈夫曼树公有2n-1个结点
  哈夫曼编码
• 用二叉树进行编码：
• （1）左右分支：0，1
• （2）字符只在叶结点上
  哈夫曼编码的特点：
• 1最优编码–总长度（WPL）最小
• 2 无歧义解码–前缀码：数据仅存于叶子结点
• 3 没有度为1的结点–满足1、2则必然有3

（10）集合的表示

• 集合运算：交、并、补、差，判定一个元素是否属于某一集合。

（10）什么是图

无向图：图中边没有方向
有向图：图中边单向或双向
网络：带权重的图
1 图的遍历
（1）深度优先搜索（DFS）
（2）广度优先搜索（BFS）（类似于树的层序遍历）

三 算法

(1)二分查找（Binary Search）

有序，在数组中。

（2）有权图的单源最短路算法