JS数据结构与算法1
需积分: 0 46 浏览量
2022-08-03
18:13:19
上传
评论
收藏 84KB PDF 举报
JS Data Structures
and Algorithms
顺序数据结构
数组
栈Stack 后进先出（LIFO）
队Queue 先进先出（FIFO）
链表LinkedList
存储有序的元素集合
元素本身
指针（链接）：指向下个元素的引
特点
添加或者删除元素时需要移动其他元素
访问元素时，需要从表头开始迭代直到找到所需元素
双向链表DoublyLinkedList
链接是双向的，元素组成有三个
优点
提供两种迭代表的法，顺序或者逆序
单向表：如果迭代表错过要找的元
素，就需要回到表起点，重新开始迭代
序性数据结构
集合 组序且唯的项组成的集合 [值，值]
字典与散表
字典 [键，值]
散表（顺序数据结构） 尽可能快的在数据结构中找到个值
树
叉树
节点最多只能有两个节点
叉搜索树BST（BinarySearchTree） 只允许在左侧节点存储（节点）的值，在右侧存储的值
树的遍历
中序
上式，从到 应：对树进排序
左侧节点 => 节点本身 => 右侧节点
先序
优先于后代节点的顺序访问每个节点 应：打印结构化档
节点本身 => 左侧节点 => 右侧节点
后序
访问后代节点 => 访问节点本身 应：计算个录和它的录中所有件所占空间的
左侧节点 => 右侧节点 => 节点本身
搜索树中的值
搜索最值 如果节点本身和其左侧节点为空，则继续递归搜索它的左侧节点
搜索最值 如果节点本身和其右侧节点为空，则继续递归搜索它的右侧节点
搜索特定值
图（线性数据结构）
定义
径
简单径包含重复的顶点
环：第个和最后个顶点是同个顶点
有向图/向图
强连通：每个顶点间在双向上都存在径
加权/未加权：赋予权值
图的表示
邻接矩阵 每个节点都和个整数相关联，该整数将作为数组的索引
邻接表
动态数据结构（对于多数问题来说是好的选择）
邻接表由图中每个顶点的相邻顶点表所组成
可以表（数组）、链表，甚是散表或是字
典来表示相邻顶点表
关联矩阵
矩阵的表示顶点，表示边
通常于边的数顶点多的情况下，以节省空间和内存
图的遍历
核思想
必须追踪每个第次访问的节点，并且追踪哪些节点还没有被完全探索
都需要明确指出第个被访问的顶点
为保证效率：每个顶点最多只能被访问两次
两种算法的同 待访问顶点表的数据结构
两种
度优先搜索（BFS）-
Breadth-First Search Page117
数据结构：队
先宽后深地访问顶点
深度优先搜索（DFS）-Depth-
First Search Page122
数据结构：栈
先深度后度的访问顶点
需要个源顶点
基础算法
排序
冒泡排序O(n2)
较任何两个相邻的项，如果第个第个，则交换它们。
改进后的冒泡排序 从内循环减去外循环中已跑过的轮数，避免内循环中所有必要的较
选择排序O(n2) 找到数据结构中的最值并将其放置在第位
插排序
每次只排序个数组项，确定它应该插到哪个位置
排序型数组时，此算法选择排序和冒泡排序性能要好。
归并排序(分治)O(nlogn)
将数组拆分成较的数组，直到每个数组的度为1
合并和排序数组，直到回到原始数组的度
快速排序(分治)O(nlogn) 将原始数组分为较的数组（但它没有像归并排序那样将它们分割开）。
搜索
顺序搜索O(n)
将每个数据结构中的元素和我们要找的元素做较
最低效的种搜索算法
分搜索O(log(n))
选择数组的中间值
如果选中值是待搜索值，那么算法执完毕（值找到）。
如果待搜索值选中值要，则返回步骤1并在选中值左边的数组中寻找
如果待搜索值选中值要，则返回步骤1并在选种值右边的数组中寻找
算法基础补充
递归
直接或者间接调身的法或者函数
每个递归函数都必须要有边界条
件，即个再递归调的条件
（停点），以防限递归
如果没有加上边界条件，递归会永远执，会抛出“栈溢出错误”
ES6有尾调优化，会“跳转指令”，故可以执下去
其实递归普通版本慢，但容解，代码少，ES6却会慢（尾调优化的缘故）
优化技术
贪算法
遵循种近似解决问题的技术，期盼通过每个阶段的局部最优
选择（当前最好的解），从达到全局的最优（全局最优解）
像动态规划那样计算的格局
分治算法 把问题分解成相互独的问题，然后组合它们的答案
动态规划DP
将复杂问题分解成的问题来解决
步骤
定义问题
实现要反复执解决问题的部分（这步要参考前节讨论的递归的步骤）
识别并求解出边界条件。
实际应
最少硬笔找零
背包问题
最公共序
矩阵链相乘
图的全源最短径
O表示法 描述算法的性能和复杂程度
般考虑的是CPU（时间）占
CPU（时间）占、内存占、
硬盘占和络占
评论0