6. 数据结构与算法基础

书写与190311

数据结构的定义

数据结构的概念

数据结构是计算机存储和组织数据的方式，之所以研究它，是选择不同的数据结构或对数据结构进行调整后效率会有很大的改变

数据逻辑结构

数组与矩阵

数组

稀疏矩阵

在一些矩阵中，可能有很多值都为零或者为空，所以有时候不用存储那么多的数据，可以用数组来存储

线性表⭐

线性表常见的存储结构

顺序存储结构——顺序表
链式存储结构——链表

链表的基本操作

顺序存储与链式存储对比

存储密度：由于链表还要有的记录下一个数据的指针，所以存储密度要小点
查找和读运算，查找是找到叫什么的数据，读是找到第几位的数据

队列与栈

环形队列

一般来说，为了避免队满时队头等于队尾与队空的情况相同，所以会不存最后一个元素，所以队满时的条件就变成了上图中的情况，

广义表

树与二叉树⭐

基本概念

节点的度

1号有两个孩子，所以度为2
树的度

所有节点中度最高的为树的度，如图，树的度为2
深度

为树有几层
叶子节点

最末支的为树的叶，如图为4，5，7，8
分支节点

图中的分支节点为2，3，6
内部节点

非叶子节点，和非头节点
父节点

4的父节点是2
子节点

2的子节点是4，5
兄弟节点

2的兄弟节点为3

满二叉树和完全二叉树

满二叉树

所有除叶子节点外的度都为2
完全二叉树

除叶子节点外为为满二叉树，而叶子节点要从左到右排

二叉树的重要特性

二叉树的遍历

反向构造二叉树

树转二叉树

查找二叉树

基本性质
插入结点
删除结点

有两个子结点的情况，如89，找到89中最大的元素(用中序遍历取最后一个元素)，把89换成56，删掉原来的56，56被删掉，把51连到48中

最优二叉树–哈夫曼树

实现无损压缩

基本概念
- 树的路径长度——2的路径长度为2
- 权——2的权为2
- 带权路径长度——权*路径长度
- 树的带权路径长度为——所有叶子结点的带权路径长度
构造哈夫曼树的效果是树的带权路径长度最小
例题

线索二叉树

树中有些结点没有满(左右结点未满),所以有一些指针没有用, 线索二叉树把这些指针利用起来

左边的指针指向之前遍历的元素, 右边的指针指向后面遍历的元素

平衡二叉树

任意结点的左右子树深度相差不超过1,每节带点的平衡度(左子树深度-右子树深度)只能为-1,0,1,那么就是一个平衡二叉树,它提出的意义可能是对于查找二叉树,平衡二叉树查找效率更高

图

图的基本概念

无向图
有向图
完全图

所有图该连的线都连了

图的存储

邻接矩阵

邻接表

3. 图的遍历

拓扑排序

图的最小生成树

找出路径最短的遍历方式

1) 普里姆算法

从A出发,找其他未遍历的点的最小路径–100,构成A,B集合
从A,B出发,找其他未遍历的点的最小路径–200,构成A,B,E集合
…

2) 克鲁斯卡尔算法

找出最短的边,100,连接AB
再找其次短的边,200,连接A,E,连接D,F
不能形成环路

算法基础及常见的算法⭐

算法的复杂度

时间复杂度
- 时间复杂度找最大的
- log2n是在查询二叉树的时候要到，n为结点的数量
- 常用的对算法执行所需时间的时间复杂度
空间复杂度

查找⭐

顺序查找

顺序查找的概念

平均查找长度——1/1+n
时间复杂度——O(n)

二分查找法

二分查找的概念
时间复杂度为 \(\log_2n\)

散列表

基本思想
例题

排序⭐

排序的一些概念

稳定排序和不稳定排序

例如21 32 13 45 27 38 76 21，稳定排序在排相同数字21和21时，前后顺序和之前的没有改变，不稳定则不一定
内排序与外排序

在内存里的排序为内排序，涉及外存的排序为外排序

排序方法分类

直接插入排序

希尔排序

比如一次分出来的d1为5，就是间隔5个是一组，57，28一组，68,96一组，59,33一组52,24一组，组内进行直接插入排序，这样子在数据量大的时候效率高

直接选择排序

堆排序

1) 堆的概念

类似于二叉树，最顶的树最小，最底的树最大，就叫做小顶堆，反之大顶堆

2) 堆排序的做法

思想就是比如一个大顶堆，那么我拿掉根结点最大后，再形成新大顶堆，再拿掉根结点，形成从大到小的排序，好处在于可以排出前多少大的结点而不用全部排序出来

初建堆

如果是大顶堆，从最后一个非叶子结点起，和底下的子节点对比，取最大的放在该结点上，如果子节点下还有其他结点，还要进行再次对比，最后到根结点来形成初建堆
再次建堆

再次建堆取最后一个结点放在根结点上，根结点与自己的子节点对比，和初建堆的对此操作一致

冒泡排序

快速排序

快速排序是定一个基准，比基准大的放在左/右边，比基准小的放在右/左边，然后再对新的左右两堆进行同样的排序