概念
数据结构-逻辑结构：分为 线性结构和非线性结构
算法特性
1.有穷性:执行有穷步之后结束，且每一步都可在有穷时间内完成。
2.确定性:算法中每一条指令都必须有确切的含义，不能含糊不清。
3.输入(>=0)
4.输出(>=1)
5.有效性(可行性):算法的每个步骤都能有效执行并能在执行有限次后得到确定的结果。例如a=0，b/a就无效
线性结构（线性表）
存储结构
顺序存储（顺序表）
优点：通过索引（下标）快速地访问表中元素
缺点：插入和删除操作，会使得表中的大量元素进行移动，效率较低；面对扩容问题的时候，比较繁琐；
链式存储（链表）
优点：链表的插入和删除操作的效率较高，不需要考虑扩容问题。
缺点：链表在查找元素的时候，执行效率较低，需要从头开始，依次往后找。
image.png
链表的操作
例1
队列与栈
image.png
例1
广义表
有广义表LS1= ( a , (b, c), (d , e))，其长度为3，深度为2
串
又叫字符串，是一种特殊的线性数据结构，它的数据元素是字符，是取值范围受限的线性表
image.png
串的模式匹配
-
朴素模式匹配算法
image.png
- KMP模式匹配算法
KMP匹配过程
https://www.bilibili.com/video/BV1AY4y157yL/?spm_id_from=333.337.search-card.all.click&vd_source=f7f94f7f3c9bbe49ae72b304286148f3
Next数组计算方法
例1
数组
数组元素地址计算方法
例1
树
是一种重要的非线性结构，该结构中一个数据元素可以有两个或两个以上的直接后续元素，来描述客观世界中广泛存在的层次关系
二叉树
二叉树特性
二叉树遍历方式
二叉查找树（二叉排序树）
image.png
二叉平衡树
image.png
例1
哈夫曼树（最优二叉树）
定义
给定N个权值作为N个叶子节点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树。哈夫曼树是带权路径长度最短的树，权值较大的节点离根较近。
构建步骤:
1，将所有左、右子树都为空的作为根节点。
2，在森林中选取两棵根节点的权值最小的树作为一棵新树的左、右子树，且置新树的附加根节点的权值为其左、右子树上根节点的权值之和。
3，从森林中删除这两棵树，同时把新树加入到森林中。
4，重复2，3步骤，直到森林中只有一棵树为止，此树便是哈夫曼树。
应用场景:
对字符集中的字符进行编码和译码
构建过程1
构建过程2
例1
B树
image.png
image.png
B+树
B+树
B+树
图
图的存储
邻接矩阵
邻接链表
例1
其邻接矩阵为：
[ 0 1 1 0]
[ 0 0 0 0]
[ 0 0 0 1]
[ 1 0 0 0]
图的遍历
遍历方法
查找算法
顺序查找
image.png
平均查找长度：(n+1)/2
缺点：平均查找长度较大，查找效率低
优点：简单，对查找表的结构无要求，无论记录是否有序均可
折半查找（二分查找）
image.png
前提：记录必须有序
适用于 表不易变动，经常进行查找的情况。
例1
索引顺序查找（分块查找）
索引顺序查找又叫分块查找，它是介于顺序查找和折半查找之间。如果既要保持查找效率，又要能够满足表元素动态变化的需求，则可采用索引顺序查找的方法
在此查找方法中，除查找表外还需要为查找表建立一个“索引表”，索引表是分段有序的。将查找表分为若干个子表，为每一个子表建立一个索引项存储在索引表中，索引项包括两项内容：关键字项和指针项
索引顺序查找
哈希查找
哈希查找
hash冲突的解决办法
例1
排序算法
排序算法
稳定排序算法记忆：两只鸡鸡（
计基）用木棍去插桶里冒泡的乌龟（归）
图的算法
最小生成树
image.png
最小生成树算法有很多，其中最经典的克鲁斯卡尔（Kruskal）算法和 普里姆（Prim）算法
- 克鲁斯卡尔（Kruskal）
在所有线中，找图中最小的边，并且不形成环形
image.png
总长：2+3+3+4+5+6 = 23
最短路径
- 例子1
image.png
解法：
从S点触发，计算到每个节点的最短路径，一直结算到T，然后根据T的最小值反推出路径的走法。
image.png
- 例子2:
image.png
解法：
image.png
调度算法
image.png
网友评论