数据结构学习笔记（王道考研）
一.线性表
1.定义
线性表是具有相同数据类型的n（n>=0)个数据元素的有限序列，其中n为表长，当n=0时线性表是一个空表。若用L命名线性表，其一般表示为
L = （a1,a2,…，ai，ai+1，…，an）
2.基本操作
什么时候要传入参数的引用“&”：
注意对比俩段代码的不同之处：
第一段是在test函数运行时候，又开辟了新的内存x存放值，对main函数中的x没有任何的影响；
第二段传入引用，俩者操作的是同一内存的值，能够实现“带回来”；
3.总结
二.顺序表
1.定义
用顺序存储的方式实现线性表。
顺序存储：把逻辑上相邻的元素存储在物理位置上也相邻的储存单元中，元素之间的关系由储存单元的邻接关系来体现。
可以使用sizeof（ElemType）来知道个数据元素的大小
2.实现
1）静态分配
静态分配内存，容易实现内存资源的浪费
1.简单定义：
2.对顺序表一个较为完整的实现
如果我们没有对开辟的元素内存进行赋初值：
注意刚开始一定要把初始长度设为0，使用基本操作访问数据元素；
2）动态分配
动态分配内存，合理分配内存，但时间开销是较大的
1.简单实现
注意使用malloc、free；new、delete来实现；理解它们的使用规则
2.较为完整的动态分配
这里涉及到了指针数组和数组指针的知识。
*data实际是指向分配首地址的指针，是一个数组指针，它指向数组的首地址，通过它可以访问整个数组的内容。可以发现最后开辟内存，先把L.data给到了p，是开辟新的数组指针，里面存下所有L.data原先的值，再对L.data开辟新的内存，然后用p把值给新的L.data最后释放p的内存。
3）特点
1.随机访问，即可以在O(1)时间内找到第i个元素
2.存储密度高，每个元素只存储数据元素
3.拓展容量不方便，时间复杂度高
4.插入、删除操作不方便，要移动大量元素
3.总结
4.插入删除操作
先对问题进行分析：
需要移位操作
1）插入
具体的代码实现：
注意实现插入前要判断能否进行插入操作
时间复杂度：
最好：移动一次O1
最坏：移动n次，On
平均：n/2次，也就是On
2）删除
就是把要删除的元素之后的元素往前移一位
具体的代码实现：
时间复杂度：
最好：移动0次O1
最坏：移动n-1次，On
平均：（n-1）/2次，也就是On
3）总结
5.查找
1）按位查找
1 | ElemType GetElem(SeqList L,int i){ |
时间复杂度：O1
2）按值查找
简单类型的查找：
复杂类型的查找：
对结构体进一步拆分进行“==”操作；或重载运算符；
时间复杂度：
最好：目标元素在表头，循环一次，O1
最坏：目标元素在表尾，循环n次，On
平均：（n+1）/2次，也就是On
3）总结
三.链表
1.单链表
什么是单链表？
逻辑结构是线性表。每个节点除了存放数据元素外，还要存储只想下一个节点的指针。
优点是改变容量方便，缺点是不可随机存曲，要耗费一定空间存放指针。
1）定义
首先是对节点的定义：
注意新加一个节点的方法：开辟新空间语法和用p指向
课本中使用了一个简洁的语法来实现重命名：
注意LNode和LinkList何时使用
强调是节点用前者，强调是链表用后者
2）初始化
1）不带头节点的单链表
2）带头结点
对带头节点和不带头节点的比较：
头节点是不存储数据的
3）总结
4）插入和删除
1.按位序插入
2.前插操作
3.按位序删除
4.指定结点删除
5）总结
6）查找
按位查找
按值查找
求表长
总结
7）链表建立
尾插法
这里设置一个尾指针，大大降低了插入的时间复杂度
头插法
通过头插法可以实现链表的逆序
2.双链表
1)初始化（带头节点）
2）插入
注意指针修改的顺序，1、4不可交换
3）删除
4）遍历
5）总结
3.循环链表
1）循环单链表
2）循环双链表
插入和删除
3）总结
4.静态链表
分配一整片连续的内存空间，各个结点集中安置。
代码定义：
容量固定不可变
5.顺序表和链表比较
都是线性表，都是线性结构
顺序表支持随机存取、储存密度高，但大片连续空间分配不方便，改变容量不方便；
链表离散的小空间分配方便，改变容量方便，但不可随机存取，储存密度低
基本操作
创销，增删改查
他们插入的时间复杂度都是On
顺序表按位查找O1，链表按位查找On
顺序表按值查找可达Olog n，链表按值On
四.栈和队列
1.栈
是只允许在一端进行插入或删除操作的线性表
这个top栈顶指针会浪费一个存储空间（没有数据）
先看对栈的基本操作（创销，增删改查）
栈常考出栈可能的顺序；有几种不同的出栈可能
栈的顺序存储实现
（书上有完整展示，与ppt略有不同，以书P46、P47为准）
1）初始化
2）进栈操作
3）出栈操作
4）读栈顶元素
要注意top指针是指向哪里
5）共享栈
俩个栈共享同一片空间
俩个指针一个指向底部，一个指向顶部
6）总结
2.队列（循环队列要理解）
只允许在一端插入，在另一端删除的线性表
先进先出
1）基本操作
2）队列的顺序实现
初始化
入队操作
循环队列出队
循环队列是将顺序队列臆造位一个环状的空间，称之为循环队列
如果不允许留下一个空位存放尾指针来判断队列为空（front == rear）；那么在初始化时候就需要定义一个size，借用size来判断（size == maxsize）
或者定义一个tag（初始化rear=front=tag=0），由于只有删除才能导致队空（tag置0），只有插入才会导致队满（tag置1），那么我们可以得知：
队满条件是front == rear && tag ==1;
队空条件是front == rear && tag ==0;
综上所述：
要么牺牲一个储存单元
要么增加辅助变量
3）总结
4）队列的链式实现
结合链表的知识
ps：后面还有双端队列以及栈和队列的应用，由于考试不涉及所以跳过了，有时间再补起来
3.特殊矩阵的压缩储存
数组元素a[i]的存放地址 = LOC+i*sizeof（ElemType）
LOC为起始地址
行优先和列优先
要会计算a[i,j]的一维数组的表示，是一维数组的第几个元素，先算到i–1行或j-1列
要注意是从a[0,0]开始还是从a[1,1]开始
稀疏矩阵的存储
3.考点总结
创销，增删改查
循环单链表，循环队列的相关操作，指针该如何移动
五.树和二叉树
1.基本概念
了解结点之间的关系
结点层次（深度）、结点高度、树的高度，结点的度（有几个分支），树的度（各结点度的最大值）
森林：m（m>0）颗互不相交的树的集合
2.常考的性质
结点数 = 总度数 + 1；
树的度–各结点的度的最大值；
m叉树–每个结点最多只能有m个孩子的树；
3.二叉树
是n个结点的有限集合，或者为空二叉树，或者由一个根结点和俩个互不相交的被称为根的左子树和右子树组成。左子树和右子树又分别是一颗二叉树。
特点：每个结点至多只有俩棵子树，左右子树不能颠倒（二叉树是有序树）
注意区别：度为2的有序树
特殊的二叉树
4.二叉树的性质
结点数等于总度数+1
具有n个结点的完全二叉树的高度是[log2(n+1)],2是底数
对于完全二叉树，可以由结点数n退出度为0、1、2的结点的个数
5.二叉树的存储结构
1）顺序存储
2）链式存储
链式存储的二叉树的构建
如果需要找父指针就要定义三叉链表，即二叉树定义中加入一个父结点的指针
n个结点的二叉链表共有n+1个空链域
6.二叉树的遍历
先序：根左右
中序：左根右
后序：左右根
这里贴一个习题（方法是对根展开，叫做分支结点逐层展开法）
对于遍历的代码：
是使用递归来实现的，中序则把第一句放到中间；后序则把第一句放到最后
层序遍历
7.由遍历序列构造二叉树
如果只给出一种遍历序列，不能唯一确定一颗二叉树
先确定根，再左右子树，以此类推
注意俩俩组合其中一个一定要是中序遍历，否则不能唯一确定二叉树
8.线索二叉树
1）概念
n个结点的二叉树，有n+1个空链域，可用于记录前驱和后继
左孩子指针充当前驱线索，指向前驱；右孩子指针充当后继线索，指向后继（前驱、后继指的是访问顺序的前一个和后一个）
2）二叉树的线索化
土方法找某个结点的前驱，就按照他的遍历顺序再进行一次遍历，同时再visit函数中定义俩个变量一个是当前访问值，一个是访问值的前驱，每当访问值改变时，访问前驱也跟着改变，直到访问值等于查找的结点时，此时记录的前驱即为查找的前驱
如何实现线索化：
3）找前驱后继
先定义找最左元素的函数，中序根结点的后继就是右子树的最左结点
同理：
找前驱即是左子树的最右结点
二叉链表先序找不到直接前驱，要么再遍历一遍，要么改为三叉链表
同理：后序也找不到直接后继
9.树的存储结构
树是n>=0个结点的有限集合，n=0时，称为空树。任意一个非空树应满足：
1.有且仅有一个根结点
2.n>1时，其余结点可以分为m>0个子树
1）双亲表示法
2）孩子表示法（顺序+链式存储）
找孩子方便，找双亲就没那么方便了
3）孩子兄弟表示法（链式）！！！
把兄弟连起来，然后只保留指向左边第一个孩子的指针，左边是孩子，右边是兄弟
对父结点来说，它子节点最左边的称为它的左孩子；对于子节点来说，他的兄弟会变成它的右孩子。
这里就引出了关于树和二叉树的转换问题
用孩子兄弟表示法存储的树在物理上呈现出“二叉树”的亚子。
10.树和森林的遍历
树先、中、后根遍历，层次遍历，和二叉树原理相同
注意访问森林时，等价于先转成二叉树再进行遍历：
1.先序遍历森林等同于依次对各个树先序遍历
2.中序遍历森林等同于依次对各个树进行后序遍历
11.哈夫曼树！！！
首先了解什么是权，带权路径长度，WPL
在含有n个带权叶结点的二叉树中，其中带权路径长度（WPL）最小的二叉树称为哈夫曼树，也成为最优二叉树
1）如何构造哈夫曼树！！！
2）哈夫曼编码
先按照频率构造哈夫曼树，然后左为0，右为1，用二进制数表示字符；
12.写完习题的总结考点
度和结点、深度的关系
哈夫曼树的构造
画线索二叉树
前序中序后序遍历，根据中序和另一序画二叉树；
层次遍历画二叉树
二叉树和森林的相互转化
六.图
1.定义和概念
有向图和无向图
简单图，多重图
有关度的一些概念
顶点与顶点之间的关系
连通图和强连通图
子图
连通分量和强连通分量
生成树和生成森林
与权相关的概念
考点总结
2.邻接矩阵法
二位数组<i,j>表示第i个元素和第j个元素有一条边，有边则置为1，反之为0；
当边有权值时在数组相应位置存下权值即可
对它的性能进行分析
对他的性质进行分析
考点总结
3.邻接表法
4.十字链表、邻接多重表
十字链表：由橙指针可以找到全部指向该结点的结点，由绿色指针可以找到该结点指向的全部结点；
5.图的基本操作
6.广度优先遍历和深度优先遍历
对于树来说，广度优先就是层次遍历；深度优先就是先中后序遍历。图和树的原理大致类似
需要利用辅助数组，标记结点是否被访问过
留下寻找的路径，就生成了树
1）广度优先
层次遍历的推广
2）深度优先
先根遍历的推广
7.最小生成树
8.最短路径问题
1）BFS
2）Dijkstra
先确定最小的边，选n-1条最小的构成连通图就形成了最短路径
3）Floyed
先确定俩点，再选这俩点的最短路径，最后得到一个图的完整最短路径
9.有向无环图描述表达式
DAG是有向无环图
10.拓扑排序
1）在有向图中选一个没有前驱的顶点且输出它
2）从图中删除该顶点和所有以它为尾的结点
重复以上俩个不走，直到所有几点都已输出，或者当前图中不存在无前驱的结点为止。后一种情况说明有向图中存在环。
11.关键路径！！！
缩短公共关键路径才能缩短工期
七.查找
1.顺序查找
基础：挨个遍历，找到元素
对效率的分析总结
2.折半查找
始终和中间元素作比较，查找失败是low>high
mid的值向下或者向上取整都会导致判定树不同
3.分块查找
4.二叉排序树
1）BST二叉排序树
查找
二叉树的构造就是小于在左，大于在右
删除
效率分析（ASL平均查找长度）
2）平衡二叉树AVL
定义：
树上任一结点左子树和右子树高度差不超过1
结点的平衡因子 = 左子树高 - 右子树高
对平衡二叉树的调整！！！
插入操作导致不平衡
1.左左形
右旋，中间结点作根
2.右右型
左旋，中间结点作根
3.左右型
先把<b，c>左旋形成左左型,此时c是a的左子树根结点，再根据左左型右旋实现平衡
4.右左型
先把<b，c>右旋形成右右型,此时c是a的右子树根结点，再根据右右型左旋实现平衡
总结
要先找是什么原因导致不平衡，分析是哪个类型
在旋转过程中相对关系不变，连接可能会改变
删除操作导致不平衡
3）哈希表（散列表）
定义
处理冲突
查找先用哈希函数求出目标元素的存储地址（对key对储存长度取余，得到存在哪个地方）
然后在该链表中查找
1）线性探测法
2）平方探测法
3）伪随机序列法
查找效率
ASL = 查找所有元素的总共次数/key的个数
冲突次数+1 = 查找次数
总结
八.排序
关注时间复杂度，稳定与否，算法思想
1.插入排序
带哨兵：
空间复杂度O（1）
时间复杂度O（n平方）
（稳定，最好O（n），最坏O（n平方），平均O（n平方））
仍然是O（n平方）
总结
2.希尔排序
不稳定
O（n的平方）
3.冒泡
稳定，
O（n的平方）
4.快速排序
不稳定
O（递归层数）
最好O（nlogn）
最坏O（n方）
平均是nlogn
有序或逆序时候效率最低
5.简单选择排序
O（n方）
不稳定
6.堆排序
注意区分建立大根堆和基于大根堆排序（递增序列）
大根堆是根>=左右
小根堆是根<=左右
由初始队列建立大根堆：
先画树，再从最后一个非叶子结点开始调整
如何得到排序，最后一个结点和根结点交换在进行调整；依次类推；
7.归并排序
一般是二路归并
稳定的
O（nlogn）
8.基数排序
从低位到高位依次收集、形成新的队列，再按新队列进位收集，形成新队列，以此类推；
补充（广义表）
Head、Tail取元素，从里向外；
Head是头，是头一个元素；
Tail是表，是除了头的表；
求长度（第二层对括号）和深度（最多几对括号）
本文链接： http://wusterlllry.xyz/2023/12/11/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/
版权声明： 本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。转载请注明出处！
