数据结构与算法基础概述
概述
数据结构概述
什么是数据结构
数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成。
数据的存储结构
顺序存储结构
顺序存储结构：是把数据元素存放在地址连续的存储单元里，其数据间的逻辑关系和物理关系是一致的。数组就是顺序存储结构的典型代表。
链式存储结构
链式存储结构：是把数据元素存放在内存中的任意存储单元里，也就是可以把数据存放在内存的各个位置。这些数据在内存中的地址可以是连续的，也可以是不连续的。
两种方式的区别
数据的逻辑结构
集合结构
集合结构中的数据元素同属于一个集合，他们之间是并列的关系，除此之外没有其他关系。
线性结构
线性结构中的元素存在一对一的相互关系。
树形结构
树形结构中的元素存在一对多的相互关系。
图形结构
图形结构中的元素存在多对多的相互关系。
算法概述
算法的定义
是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。
算法的特性
- 输入
- 输出
- 有穷性
- 确定性
- 可行性
算法的基本要求
- 正确性
- 可读性
- 健壮性
- 时间复杂度
- 空间复杂度
线性结构
数组
数组的基本使用
面向对象的数组
查找算法
- 线性查找
- 二分法查找
栈
队列
单链表
- 节点的删除
- 节点的插入
循环链表
双链表
递归
递归：在一个方法（函数）的内部调用该方法（函数）本身的编程方式
- 斐波那契数列
- 汉诺塔问题
排序算法
时间复杂度和空间复杂度概述
八种常用排序算法
交换排序
- 冒泡排序
- 快速排序
插入排序
- 直接插入排序
- 希尔排序
选择排序
- 简单选择排序
- 堆排序
归并排序
基数排序
八种排序算法的对比
树结构
树结构概述
什么是树结构
为什么使用树结构
树的基本概念
- 根节点
- 双亲节点
- 子节点
- 路径
- 节点的度
- 节点的权
- 叶子节点
- 子树
- 层
- 树的高度
- 森林
二叉树
什么是二叉树
- 满二叉树
- 完全二叉树
链式存储的二叉树
创建二叉树
添加节点
树的遍历
- 前序遍历
- 中序遍历
- 后序遍历
查找节点
删除子树
顺序存储的二叉树
- 顺序存储的二叉树的性质
- 遍历
线索二叉树
- 线索二叉树的概述
- 线索二叉树的代码实现
赫夫曼树
赫夫曼树概述
最优二叉树
它是n个带权叶子结点构成的所有二叉树中，带权路径长度最小的二叉树。
叶结点的带权路径
树的带权路径长度WPL
树的带权路径长度WPL(weighted path length)：树中所有叶子结点的带权路径长度之和。
（a）WPL=9x2+4x2+5x2+2x2=18+8+10+4=40
（b）WPL=9x1+5x2+4x3+2x3=9+10+12+6=37
（c）WPL=4x1+2x2+5x3+9x3=4+4+15+27=50
权值越大的结点离根结点越近的二叉树才是最优二叉树。
赫夫曼树的代码实现
赫夫曼编码概述
- 赫夫曼编码.pptx
赫夫曼编码代码实现
- 统计字符数并排序
- 创建赫夫曼树
- 创建赫夫曼编码表
- 编码
使用赫夫曼编码进行解码
文件的压缩与解压
二叉排序树
二叉查找树概述
添加节点
查找节点
删除节点
- 删除叶子节点
- 删除只有一个子节点的节点
- 删除有两个子节点的节点
AVL树
AVL树概述
单旋转
- 左左
- 右右
双旋转
- 左右
- 右左
多路查找树
- 计算机的存储
- 2-3树和2-3-4树
- B树和B+树
哈希表
哈希表概述
散列函数
- 直接定址法
- 数字分析法
- 平方取中法
- 取余法
- 随机数法
散列冲突的解决方案
开放地址法
- 线性探测法
- 二次探测法
- 再哈希法
链地址法
图结构
图的基本概念
- 图结构
- 邻接
- 路径
- 有向图和无向图
- 带权图
图的代码实现
图的遍历
- 深度优先搜索算法
- 广度优先搜索算法
