数据结构
四种：集合结构，线性结构，树形结构，图形结构
- 集合结构：数据元素同属于一个结合，他们之间没有其他的关系。它们的共同属性是：同属于一个集合
- 线性结构：最典型的数据关系是一对一。线性结构是一种有序数据的集合。
- 数组：就是一个线性结构，栈，队列，FILO
- 树形结构：数据元素是一对多，例如dom树
-
图形结构：数据元素是多对多
1.png
2.png
3.png
4.png
物理结构：数据元素存储到计算中的存储器，针对内存而言的
数据的存储结构应该正确的反应数据元素之间的逻辑关系
顺序存储，链式存储
5.png
6.png
7.png
数组
js的数组不是真正意义上的数组；
数组：再内存中用一串连续的区域来存放一些值。
数组是相同类型数据元素的集合(js的数组可以存储不同类型)；
而且一般数组的容量是不会自动变化的
数组内存地址是连续的，但是js中的内存地址是不连续，原因是数据类型可以是任意类型导致的
数组的优点：
- 按照索引查询元素的时候速度很快
- 存储大两的数据
- 按照索引去遍历数组
- 定义方便，访问灵活
数组的缺点：
- 根据内容查找会很慢
- 数组的大小一经确定是不能改变的，不适合动态存储
- 数组只能存储相同类型数据
- 增加删除元素效率慢，因为内存地址是连续的
栈
内存区域：栈区
单片机：压栈
数据结构中有一个同名的数据结构，栈
内存中的堆栈和数据结构中的堆栈不是一个概念，内存中的堆栈是真实存在的物理区，数据结构中的堆栈是抽象数据存储结构
栈：是一种受限制的线性表，LIFO
其限制是仅允许再表的一端进行插入和删除运算，这一端被称为栈顶，相对的，把另一端称为栈底
向一个栈插入新元素被称为进栈，入栈，压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素
从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素
栈的应用：十进制转二进制
8.png
当时js中有内置api实现，但是此处只是说明一个应用场景
class Stack {
constructor() {
this.items = [];
}
push(ele) {
this.items.push(ele);
}
pop() {
return this.items.pop();
}
//返回栈顶元素
peek() {
return this.items[this.items.length - 1];
}
//判断栈中元素是否为空
isEmpty(){
return this.items.length==0;
}
size() {
return this.items.length;
}
clear() {
this.items=[];
}
}
const binary = number => {
let stack = new Stack();
let remainder = 0;
let top = '';
while (number > 0) {
//除以2取余数
remainder = number % 2;
stack.push(remainder);
//向下取整
number=Math.floor(number/2);
}
//不为空的时候
while (!stack.isEmpty()) {
//栈顶元素
top+=stack.top();
}
return top;
}
JS 调用栈：
前置说明：
1 JavaScript 是一门单线程的语言，这意味着它只有一个调用栈，因此，它同一时间只能做一件事。
2 内存堆：这是内存分配发生的地方.
3 调用栈：这是你的代码执行时的地方
定义：调用栈是解释器（就像浏览器中的javascript解释器）追踪函数执行流的一种机制。当执行环境中调用了多个函数时，通过这种机制，我们能够追踪到哪个函数正在执行，执行的函数体中又调用了哪个函数。
1. 每调用一个函数，解释器就会把该函数添加进调用栈并开始执行。
2 正在调用栈中执行的函数还调用了其它函数，那么新函数也将会被添加进调用栈，一旦这个函数被调用，便会立即执行。
3 当前函数执行完毕后，解释器将其清出调用栈，继续执行当前执行环境下的剩余的代码。
4 当分配的调用栈空间被占满时，会引发“堆栈溢出”
函数的调用本质："压栈和出栈操作"，但是函数在调用栈里面有一个特例，叫做递归
递归：自己调用自己，先进栈，如果不出栈，就会导致：栈溢出
斐波那契数列：从第三项开始，每一项都等于前两项的和1 1 2 3 5 8 13
当数值很大的时候，计算斐波那契数列会出现计算慢(因为有重复计算，函数多同时也会导致调用栈过多)调用栈溢出，解决方案是尾递归优化
- 尾调用
尾调用自身就是尾递归
//函数b的尾部调用a函数，被称为尾调用
function a(x) {}
function b(x){
return a(x);
}
b(x);
实际上就是调用a(x);
可以看成没有外部调用帧
如果a就是b本身的话，即使有很多层调用，因为尾递归优化，实际上不会像常规调用一样，帧一层套一层；
总共只有一个调用帧，避免了调用栈溢出
const factor=(n,total)=>{
if (n==1) {
return total;
}
return factor(n-1,n*total);
}
优化斐波那契数列
//原始案例
const Fibonacci = (n) => {
if (n <= 1) {
return 1;
}
return Fibonacci(n - 1)+Fibonacci(n-2);
}
//优化案例
//把前面两位数当作参数传递进来
//此处没有利用常规缓存函数计算结果，而是直接缓存上次总体计算结果；实际上也是利用了缓存
//递归需要同时保存成百上千个调用帧，很容易发生栈溢出，而且因为尾递归优化，只有一个调用栈，永远不会栈溢出
const Fibonacci = (n, ac1 = 1, ac2 = 2) => {
if (n <= 1) {
return ac2;
}
return Fibonacci(n - 1, ac2, ac1 + ac2);
}
console.log(Fibonacci(50,1,1));
队列
- 是一种受限的线性表，FIFO
-
受限之处：它只允许表的前端进行删除操作，在表的后端进行增加操作
9.png
class Quenue{
constructor(){
this.items= [];
}
//入队
enqueue(item){
this.items.push(item);
}
//出队操作
dequeue(){
return this.items.shift();
}
//查看队首元素
front() {
return this.items[0];
}
//查看对尾
rear() {
return this.items[this.items.length-1];
}
//是否为空
isEmpty(){
return this.items.length===0;
}
size(){
return this.items.length;
}
clear(){
this.items=[];
}
}
- JS的异步队列
js为什么是单线程：完成与用户交互以及dom操作；一个线程添加dom一个删除dom，浏览器听谁的，避免复杂性所以直接单线程 - 主线程执行完毕之后，从事件队列中读取任务队列的过程，称之为事件循环(EventLoop)
- Promise是同步的，then和catch是异步的
Promise补充：必须查看 https://segmentfault.com/a/1190000020980101
new Promise((resolve, reject) =>{
resolve();
}).then(() =>{
})
Promise.resolve()
https://segmentfault.com/a/1190000020980101
任务队列：存在着两个队列，一个宏任务一个微任务队列
主线程：同步任务->微任务->宏任务
promise.then catch finally process.nexttick是微任务，
I/O,定时器，ajax,事件绑定是宏任务
链表
例如原型链
10.png
链表就可以解决这样的问题
11.png
- 插入删除：链表的性能好
链表没有大小限制，支持动态扩容，因为链表的每个节点都需要存储前驱/后驱节点的指针，内存消耗会翻倍 - 查询修改：数组性能好
class Node {
constructor(element){
this.element = element;
this.next=null;
}
}
//链表
class LinkedList{
constructor(){
//链表头
this.head=null;
//链表长度
this.length=0;
}
//1.链表的尾部追加元素
append(element){
let node=new Node(element);
//如果链表空的
if (this.length===0){
this.head=node;
}else{
//通过head找到后面的节点
let current=this.head;
//遍历,是否是最后一个节点,next为空就是最后一个
while (current.next){
current=current.next;
}
//while执行完毕之后，current就已经是最后一个节点了
}
current.next=node;
this.length+=1;
}
getHead(){
return this.head;
}
toString(){
let current=this.head;
let linkString='';
while(current){
linkString+=','+current.element;
current=current.next;
}
return linkString.slice(1);
}
//任意位置插入元素
insert(element,positon){
//位置不能实负数
if (positon<0||position>this.length) {
return false;
}
let index=0;
let current=this.head;
let previous=null;
let node=new Node(element);
//判断插入的是不是第一个
if (position===0) {
node.text=this.head;
this.head=node;
}else{
while (index<positon) {
previous=current;
current=current.next;
index++;
}
node.next=current;
previous.next=node;
}
this.length+=1;
return true;
}
get(positon){
if (positon<0||positon>this.length) {
return null
}
let current=this.head;
let index=0;
while (index<positon) {
current=current.next;
index++;
}
return current.element;
}
// ......实际上还有代码，此处省略
}
prototype和proto
- 所有的引用类型(数组，函数，对象)可以自由的扩展属性(null除外)
- 所有的引用类型都有一个proto属性(隐式原型，它其实就是一个普通的对象)
- 所有的函数都有一个prototype属性(显式原型，也是一个普通对)
- 所有的引用类型的proto属性都指向它的构造函数的prototype属性
- 当试图得到一个对象的属性时，如果这个对象的本身不存在这个属性，那么就会去它的proto属性中找(去它的构造函数的prototype属性中去寻找)
- 当调用这个对象本身并不存在的属性或者方法时，它会一层层的往上找，一直找到null为止，null表示空的对象{}
案例
- 案例一
//构造函数
function Teacher(name, habby) {
this.name = name;
this.habby = habby;
this.show = function () {
console.log(1111);
}
}
var t1 = new Teacher('t1', '哈哈哈哈');
var t2 = new Teacher('t2', '呵呵呵呵');
/**
* Teacher它就是一个普通函数但是这个函数的作用：构造对象
* 这种构造对象的方式：工厂方式
*/
//这样new多少次show就有多少个
console.log(t1.show === t2.show);//false
- 案例二
//构造函数
function Teacher(name, habby) {
this.name = name;
this.habby = habby;
this.show = fun
}
function fun() {
console.log(1111);
}
var t1 = new Teacher('t1', '哈哈哈哈');
var t2 = new Teacher('t2', '呵呵呵呵');
console.log(t1.show === t2.show);//true
// 这样存在问题，容易导致全局作用域的污染，并且数据是不安全的容易被覆盖，例如后面还有一个同名的fun函数
- 案例三
//如下
function Teacher(name, habby) {
this.name = name;
this.habby = habby;
}
//Teacher就是构造函数，其内部有prototype属性，而__proto__又会指向构造函数的prototype属性
//Teacher.prototype是一个普通对象，这个对象的构造函数是Object
Teacher.prototype.show = function(){
console.log(1111);
}
console.log(Teacher.prototype.__proto__===Object.prototype);//true
12.png
- 原型链继承
function Teacher(name, habby) {
this.name = name;
this.habby = habby;
this.show = function () {
console.log(1111);
}
}
//构造方法是空的
function Tt() {}
Tt.prototype = new Teacher('t1', '哈哈哈哈');
var t=new Tt();
t.show();
哈希表
MD5是目前应用最广泛的Hash算法，但是并不是唯一的算法
13.png
14.png
15.png
16.png
class HashTable {
constructor() {
this.table = [];//哈希表
}
//哈希函数:这只是一个很简化版的
loseloseHashCode(key) {
let hash = 0;
for (let i = 0; i < key.length; i++) {
hash += key[i].charCodeAt();//计算key unicode码
}
//取模
return hash % 37;//37是质数，可以很大程度上避免碰撞
}
//新增元素
put(key, value) {
//获取key
const position = this.loseloseHashCode(key);
this.table[position] = value;
}
//移除元素
remove(key) {
this.table[this.loseloseHashCode(key)]=undefined;
}
//获取元素
get(key) {
return this.table[this.loseloseHashCode(key)];
}
}
const a=new HashTable();
a.put('zq',"zq@qq.com");
console.log(a);//HashTable { table: [ <13 empty items>, 'zq@qq.com' ] }
//由上面输出可知，有很多空项，是因为此时索引不是数字的，所以前面可能存在空项
console.log(a.get('zq'));
- 碰撞
数组里面，如果数组的下标相同，后边添加的就会覆盖前面的，这个叫覆盖；
哈希表：冲突，碰撞，对于不同的要存储的数据经过哈希函数得到的索引有可能相同
const arr = [];
arr[1] = 'zq';
arr[1] = 'zq1';
//数组会覆盖
console.log(arr); //[ <1 empty item>, 'zq1' ]
const loseloseHashCode = (key) => {
let hash = 0;
for (let i = 0; i < key.length; i++) {
hash += key[i].charCodeAt();
}
return hash % 37;
}
console.log(loseloseHashCode('money'));//34
console.log(loseloseHashCode('oxgbx'));//34
class HashTable {
constructor() {
this.table = [];//哈希表
}
//哈希函数:这只是一个很简化版的
loseloseHashCode(key) {
let hash = 0;
for (let i = 0; i < key.length; i++) {
hash += key[i].charCodeAt();//计算key unicode码
}
//取模
return hash % 37;//37是质数，可以很大程度上避免碰撞
}
//新增元素
put(key, value) {
//获取key
const position = this.loseloseHashCode(key);
this.table[position] = value;
}
//移除元素
remove(key) {
this.table[this.loseloseHashCode(key)]=undefined;
}
//获取元素
get(key) {
return this.table[this.loseloseHashCode(key)];
}
}
const a=new HashTable();
a.put('money',"money@qq.com");
a.put('oxgbx',"oxgbx@qq.com");
console.log(a.get('money')); //oxgbx@qq.com
解决冲突
开放地址法
-
线性探测法
17.png
35%10结果是5，发现5上面有数据，就会向后找，发现6没有放数据就会放在6里面;
线性探测法在数据聚集的时候会影响hash表的性能，无论是插入/删除/查询
- 二次探测法(平方探测法)：步长以平方的方式进行优化
- 再哈希法
链地址法
18.png
因为链表是元素本身和指向下一个元素的指针；所以首先哈希运算取得对应索引(例如：1，2，3这种)；然后后面是链表而且是多个，可以再利用元素本身和链表中元素进行比较
树
例如：dom树，linux系统的层级结构
19.png
20.png
21.png
树的术语
- 结点的度：结点所拥有的子树的个数
- 树的度：树中节点度的最大值
- 叶子(终端结点): 度为0的结点
- 分支结点(非终端结点)：度不为0的结点。除根节点之外的分支结点统称为：内部结点。根节点我们又称为：开始结点
- 结点的层：根节点层：1；其余结点的层数等于父结点的层数+1
- 树的深度：树中所有节点层数的最大值
- 森林：拥有N颗树，就被称为森林
树的存储结构
- 计算机只能是顺序存储或者链式存储，所以树这样的结构是不能够直接存储的，要将其转换为顺序或者链式存储
- 双亲表示法：采用数组存储普通的树，其核心思想：顺序存储每个结点的同时，给各个结点附加一个记录其父结点位置的变量，存储父结点的下标。
实际操作的时候，就是从上到下，顺序去遍历一棵树，并为相应的域赋值。
优点：可以快速的获取任意结点的父结点位置。
缺点：如果要获取某个结点的子结点就要遍历了
22.png
- 孩子表示法:建立多个指针域，指向它的子结点的地址；也就是说任何一个结点，都掌握它所有子结点的信息。数组+链表的形式来实现
顺序表=》数组，从树的根节点开始，使用数组依次存储树的各个结点，需要注意的是，孩子表示法会被各个结点配备一个链表，用于存储各结点的孩子结点位于数组中的位置，如果说，结点没有子结点(叶子结点)，则该结点的链表为空链表。
23.png
- 孩子兄弟表示法：把普通的树转换成了二叉树：从树的根结点开始，依次用链表存储各个结点的孩子结点和兄弟结点
25.png
24.png
二叉树：其实所有的树的本质都是可以使用二叉树进行模拟出来的，所以二叉树很重要；二叉树的存储方式有数组和链表，最合适的方式是链表；从上到下从左至右
26.png
满二叉树：在一颗二叉树中，如果所有的分支结点都存在于左子树和右子树，并且所有的叶子都在同一层，这样的二叉树就是满二叉树；叶子只能出现在最下一层，出现在其他层，不可能达成平衡；非叶子结点的度一定是2
27.png
完全二叉树：满二叉树一定是完全二叉树，反之则不是；设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数(其实就是2，因为完全二叉树就是满二叉树分支最多两个)，
第 h 层所有的结点都连续集中在最左边
28.png
左斜树
29.png
右斜树
30.png
二叉搜索树(BST)
二叉搜索树其实就是普通二叉树加上了一些限制
- 非空左子树的所有键值都小于其根节点的键值
- 非空右子树的所有键值都大于其根节点的键值
- 左右子树本身也都是二叉搜索树
总结：相对较小的值总保存在左子结点上，相对较大的值总是保存在右子结点上
class Node {
constructor(key) {
this.key = key;
this.left = null;
this.right = null;
}
}
class BinaryTree {
constructor() {
this.root = null;
}
insert(key) { // 插入数据
var newNode = new Node(key);
if (this.root == null) {
this.root = newNode;
} else {
var current = this.root;
while (true) {
if (key < current.key) {
if (current.left) {
current = current.left;
} else {
current.left = newNode;
break;
}
} else if (key > current.key) {
if (current.right) {
current = current.right;
} else {
current.right = newNode;
break;
}
}
}
}
}
centerSort(node, arr = []) { // 中序排列
if (node) {
this.centerSort(node.left, arr);
arr.push(node.key);
this.centerSort(node.right, arr);
}
return arr;
}
prevSort(node, arr = []) { // 前序排列
if (node) {
arr.push(node.key);
this.prevSort(node.left, arr);
this.prevSort(node.right, arr);
}
return arr;
}
nextSort(node, arr = []) { // 后续排列
if (node) {
this.nextSort(node.left, arr);
this.nextSort(node.right, arr);
arr.push(node.key);
}
return arr;
}
getMin(node) { // 获取二叉树的最小值
node = node || this.root;
while (node.left != null) {
node = node.left;
}
return node.key;
}
getMax(node) { //获取二叉树最大值
node = node || this.root;
while (node.right != null) {
node = node.right;
}
return node.key;
}
find(key) { // 查找 给定的值
var node = this.root;
while (node != null) {
if (key < node.key) {
node = node.left;
} else if (key > node.key) {
node = node.right;
} else {
return node;
}
}
return null;
}
remove(key) { // 删除给定的值
this.root = this.removeNode(this.root, key);
}
removeNode(node, key) { // 真正删除的函数
if (node == null) {
return null;
}
if (key < node.key) {
node.left = this.removeNode(node.left, key);
return node;
} else if (key > node.key) {
node.right = this.removeNode(node.right, key);
return node;
} else {
if (node.left == null && node.right == null) {
node = null;
return node;
} else if (node.left == null) {
return node.right;
} else if (node.right == null) {
return node.left;
} else {
var minNode = this.getMin(node.right);
node.key = minNode.key;
node.count = minNode.count;
node.right = this.removeNode(node.right, minNode.key);
return node;
}
}
}
}
先序遍历，中序遍历，后序遍历(用的少,也叫层次遍历)
- 先序遍历: 访问根结点，先序遍历其左子树，然后先序遍历其右子树
31.png
- 中序遍历：先递归遍历其左子树，从最后一个左子树开始存入数组，然后回溯遍历双亲结点，再是右子树，递归循环
32.png
- 后序遍历：后序遍历其左子树，然后后序遍历其右子树，最后访问根节点
33.png
删除：
- 没有子树
34.png
- 有一颗子树
35.png
- 有两颗子树：保持中序遍历顺序不变
36.png
37.png
二叉搜索树的优点：作为数据存储的结构有重要的意义，可以快速的找到给定的关键字的数据项，并且可以快速的插入和删除数据
二叉搜索树的缺点：具有局限性，同样的数据(但是顺序不同的情况下)，可以对应不同的二叉搜索树，主要就是因为左大右小的规则
38.png
如上图：二叉搜索树可能退化成一个链表的，二叉搜索树的操作速度和高度是相关的，如果出现这种右斜树类型的链表，则效率高也就成了一句空话
好的二叉搜索树的结构：左右分布均匀，但是我们插入连续的数据的时候，会导致数据分布不均匀，就把分布不均匀的树称为非平衡树(如上图右边)
平衡树：AVL(不常用，整体效率低于红黑树)，红黑树
二叉平衡树
39.png
下图只是说明平衡因子计算规则，而不是平衡二叉树
39-1.png
40.png
41.png
42.png
43.png
红黑树(R-B tree)
AVL树相对于红黑树，它的插入/删除操作效率不高。
红黑树是一种自平衡的二叉搜索树，以前叫做平衡二叉B树;红黑树之所以效率高就是因为平衡，平衡则层级少，则性能高
红黑树增加的一些特性
- 结点是红色或者黑色(结点上有一个color属性)
- 根节点是黑色
- 叶子结点都是黑色，且为null
- 链接红色结点的两个子结点都是黑色，红色结点的父结点都是黑色，红色结点的子结点都是黑色
- 从任意的结点出发，到其每个叶子结点的路径中包含相同数据的黑色结点
这几条规定：保证从根节点到叶子结点的最长路径不大于最短路径的2倍
红黑树插入数据的时候，会先去遍历数据应该插入到哪个位置，插入的数据一定是红色的，因为插入黑色会破坏平衡
通过旋转(左旋转，右旋转)变色等满足上述五条性质；
44.png
const RED = true;
const BLACK = false;
class Node {
constructor(key, value) {
this.key = key;
this.value = value;
this.left = null;
this.right = null;
this.color = RED;
}
}
class RBT {
constructor() {
this.root = null;
this.size = 0;
}
isRed(node) {
if (!node) return BLACK;
return node.color;
}
// 左旋 右红左黑
leftRotate(node) {
let tmp = node.right;
node.right = tmp.left;
tmp.left = node;
tmp.color = node.color;
node.color = RED;
return tmp;
}
// 右旋转 左红左子红
rightRoate(node) {
let tmp = node.left;
node.left = tmp.right;
tmp.right = node;
tmp.color = node.color;
node.color = RED;
return tmp;
}
// 颜色翻转
flipColors(node) {
node.color = RED;
node.left.color = BLACK;
node.right.color = BLACK;
}
add(key, value) {
this.root = this.addRoot(this.root, key, value);
this.root.color = BLACK; // 根节点始终是黑色
}
addRoot(node, key, value) {
if (!node) {
this.size++;
return new Node(key, value);
}
if (key < node.key) {
node.left = this.addRoot(node.left, key, value);
} else if (key > node.key) {
node.right = this.addRoot(node.right, key, value);
} else {
node.value = value;
}
if (this.isRed(node.right) && !this.isRed((node.left))) {
node = this.leftRotate(node);
}
if (this.isRed(node.left) && this.isRed((node.left.left))) {
node = this.rightRoate(node);
}
if (this.isRed(node.left) && this.isRed(node.right)) {
this.flipColors(node);
}
return node;
}
isEmpty() {
return this.size == 0 ? true : false;
}
getSize() {
return this.size;
}
contains(key) {
let ans = '';
!(function getNode(node, key) {
if (!node || key == node.key) {
ans = node;
return node;
} else if (key > node.key) {
return getNode(node.right, key);
} else {
return getNode(node.right, key);
}
})(this.root, key);
return !!ans;
}
// bst前序遍历(递归版本)
preOrder(node = this.root) {
if (node == null) return;
console.log(node.key);
this.preOrder(node.left);
this.preOrder(node.right);
}
preOrderNR() {
if (this.root == null) return;
let stack = [];
stack.push(this.root);
while (stack.length > 0) {
let curNode = stack.pop();
console.log(curNode.key);
if (curNode.right != null) stack.push(curNode.right);
if (curNode.left != null) curNode.push(curNode.left);
}
}
// bst中序遍历
inOrder(node = this.root) {
if (node == null) return;
this.inOrder(node.left);
console.log(node.key);
this.inOrder(node.right);
}
// bst后续遍历
postOrder(node = this.root) {
if (node == null) return;
this.postOrder(node.left);
this.postOrder(node.right);
console.log(node.key);
}
// bsf + 队列的方式实现层次遍历
generateDepthString1() {
let queue = [];
queue.unshift(this.root);
while (queue.length > 0) {
let tmpqueue = []; let ans = [];
queue.forEach(item => {
ans.push(item.key);
item.left ? tmpqueue.push(item.left) : '';
item.right ? tmpqueue.push(item.right) : '';
});
console.log(...ans);
queue = tmpqueue;
}
}
minmun(node = this.root) {
if (node.left == null) return node;
return this.minmun(node.left);
}
maximum(node = this.root) {
if (node.right == null) return node;
return this.maximum(node.right);
}
}
let btins = new RBT();
let ary = [5, 3, 6, 8, 4, 2];
ary.forEach(value => btins.add(value));
btins.generateDepthString1();
// ///////////////
// 5 //
// / \ //
// 3 8 //
// / \ / //
// 2 4 6 //
// ///////////////
console.log(btins.minmun()); // 2
console.log(btins.maximum()); // 8
树的应用
- 组织索引，mysql中用的B+树
- JDK1.8的hashmap在单链表冲突之后会使用红黑树
树的深度：从根结点开始，自顶向下逐层累加
树的高度：自底向上逐层累加
图(image)
- 集合只有同属于一个集合的关系
- 线性结构存在一对一的关系
- 树形结构一对多的关系
- 图形结构，多对多的关系
例如微信中，许多的用户组成了一个多对多的朋友关系网，这个关系网就是数据结构当中的图(Graph)
还有导航的最优路径：耗时最短的路径等
45.png
自环：即一条链接一个顶点和自身的边
平行边：连接同一对顶点的两条边
52.png
图的分类
- 无向图: 边没有方向的图称为无向图，边的作用仅仅是连接两个顶点，没有其他含义
- 有向图: 边不仅连接两个顶点，并且具有方向性，可能单向/双向
- 带权图: 边可以带权重
46.png
47.png
图的术语
- 相邻顶点：当两个顶点通过一条边相连时候，我们称这两个顶点是相连的，并且是依附于这两个顶点的
- 度：某个顶点的度：是依附于这个顶点的边的个数
- 子图:一幅图中，所有边的子集组成的图，包含这些边的依附的顶点
- 路径：是由边顺序链接的一系列的顶点组成
- 环：至少含有一条边，且终点和起来相同的路径
- 连通图：如果图中任意一个顶点都存在一条路径到达另外一个顶点，那么这幅图就称为连通图
- 连通子图：组成连通图的非连通图
48.png
欧拉七桥
欧拉开创了新的学科：图论
49.png
图的存储结构
图是由顶点和边构成的，所以在图里边，要存储的图形结构的信息，无非就是存储图的顶点和图的边；
顶点可以直接用数组去存储
1，2，3，4=》[1,2,3,4]
边存储起来就麻烦一些
存储结构：
- 邻接矩阵
- 矩阵是一个按照长方阵列的负数或者实数集合
- N*M数据的集合(类似九宫格)；可以用1表示顶点与顶点有直接的关系，用0表示没有连接
- 优点：表示明确，例如有向图A->D:1 D->A:0
- 缺点：消耗内存大，存储了太多的0；但是删除会很麻烦，需要一个个置为0；下面的邻接表就可以解决这个问题
50.png
- 邻接表
- 由图中的每个顶点以及和顶点相邻的顶点列表组成。数组/链表/字典
51.png
图的遍历
- 遍历：从某个结点出发，按照一定的搜索路线，依次访问数据结构中的全部结点，而且每个结点访问一次
- 广度优先遍历(BFS)
优先横向遍历图，广度优先的思想，从图中的某个顶点V出发，在访问V之后，依次去访问V的各个未曾访问过的邻结点，然后分别从这些邻结点出发，依次访问他们的邻结点。
注意：图没有横向和纵向的概念
53.png
- 深度优先遍历(LFS)
深度优先有递归的概念
54.png
图遍历的思路
- 每个顶点有三种状态
- 未发现
- 已经发现
- 已经探索
55.png
- 记录顶点是否被访问过，使用三种颜色来反应它们的状态
- 白色，未发现
- 灰色，以发现
- 黑色，已经探索
- 广度优先的遍历过程
- 发现未发现顶点后，存放队列中，等待查找，并且将这些顶点标记为以发现
- 在队列中拿出已经发现的顶点，开始探索全部顶点，并且要跳过已经探索的顶点
- 遍历完这个顶点以后，将这个顶点标志为已经探索
- 循环在队列中探索下一个顶点
- 深度优先的遍历过程
- 广度优先使用的是队列，深度优先的原理：使用递归
- 从某一个顶点开始查找，并且将这个顶点标记为已经发现(灰色)
- 从这个顶点开始探索其他的全部的顶点，并且跳过已经发现的顶点
- 递归返回，继续探索下一个路径的最深顶点
代码案例
- 利用邻接矩阵（边数组）创建图
let scanf = require('scanf');
//定义邻接矩阵
let Arr2 = [
[0, 1, 0, 0, 0, 1, 0, 0, 0],
[1, 0, 1, 0, 0, 0, 1, 0, 1],
[0, 1, 0, 1, 0, 0, 0, 0, 1],
[0, 0, 1, 0, 1, 0, 1, 1, 1],
[0, 0, 0, 1, 0, 1, 0, 1, 0],
[1, 0, 0, 0, 0, 0, 1, 0, 0],
[0, 1, 0, 1, 0, 1, 0, 1, 0],
[0, 0, 0, 1, 1, 0, 1, 0, 0],
[0, 1, 1, 1, 0, 0, 0, 0, 0],
]
let numVertexes = 9, //定义顶点数
numEdges = 14; //定义边数
// 定义图结构
function MGraph() {
this.vexs = []; //顶点表
this.arc = []; // 邻接矩阵，可看作边表
this.numVertexes = null; //图中当前的顶点数
this.numEdges = null; //图中当前的边数
}
let G = new MGraph(); //创建图使用
//创建图
function createMGraph() {
G.numVertexes = numVertexes; //设置顶点数
G.numEdges = numEdges; //设置边数
//录入顶点信息
for (let i = 0; i < G.numVertexes; i++) {
G.vexs[i] = scanf('%s'); //String.fromCharCode(i + 65); ascii码转字符
}
console.log(G.vexs) //打印顶点
//邻接矩阵初始化
for (let i = 0; i < G.numVertexes; i++) {
G.arc[i] = [];
for (j = 0; j < G.numVertexes; j++) {
G.arc[i][j] = Arr2[i][j]; //INFINITY;
}
}
/**以下是手动录入的方式 */
// for (let k = 0; k < G.numEdges; k++) {
// console.log('输入边（vi,vj）上的下标i,下标j和权w:');
// let rlt = scanf('%d,%d,%d');
// let i = rlt[0], j = rlt[1], w = rlt[2];
// G.arc[i][j] = w;
// G.arc[j][i] = G.arc[i][j]; //无向图，矩阵对称
// }
console.log(G.arc); //打印邻接矩阵
}
- 深度优先遍历
let visited = []; //访问标志数组，遍历时使用
//邻接矩阵的深度优先递归算法
function DFS(i) {
visited[i] = true;
console.log('打印顶点:', G.vexs[i]) //打印顶点 ,也可以其他操作
for (let j = 0; j < G.numVertexes; j++) {
if (G.arc[i][j] == 1 && !visited[j]) {
console.log(G.vexs[i], '->', G.vexs[j])
DFS(j) //对未访问的顶点进行递归
}
}
}
//邻接矩阵的深度遍历操作
function DFSTraverse() {
for (let i = 0; i < G.numVertexes; i++) {
visited[i] = false;
}
for (let i = 0; i < G.numVertexes; i++) {
if (!visited[i])
DFS(i)
}
}
- 广度优先遍历
//邻接矩阵的广度遍历算法
function BFSTraverse() {
let queue = []; //初始化队列
for (let i = 0; i < G.numVertexes; i++) {
visited[i] = false;
}
for (let i = 0; i < G.numVertexes; i++) { //对每一个顶点做循环
if (!visited[i]) { //如果没有访问过就处理
visited[i] = true;
console.log('打印顶点：', G.vexs[i]) //也可以是其他操作
queue.push(i); //将此顶点入队列
while (queue.length != 0) { //当前队列不为空
queue.shift();
for (let j = 0; j < G.numVertexes; j++) {
//判断其他顶点若与当前顶点存在边且未访问过
if (G.arc[i][j] == 1 && !visited[j]) {
visited[j] = true;
console.log(G.vexs[i], '->', G.vexs[j])
console.log('打印顶点：', G.vexs[j])
queue.push(j) //将此顶点放入队列
}
}
}
}
}
}
最短路径
-
路径：由边顺序连接的顶点组成的
- 寻找最短路径，所谓路径指的是：如果从图中的某一个顶点(起点，圆点)到达另外一个顶点(终点)路径步可能只有一条，如何找到一条路径使得沿这个路径边上的权值总和(路径长度)达到最小
-
回溯点
- 回溯点是离上一个顶点
最近的顶点。A的回溯电是null,B的回溯点是：A，E的回溯点是B
回溯路径(所有回溯点组成)
通过回溯点可以查找到最短路径
- 回溯点是离上一个顶点
56.png
const prev={
'A':null,
'B':'A',
'E':'B'
}
- 常见得求最短路径得算法
有了回溯点，但是实际上通过回溯点计算最短路径的算法有多种
- 迪杰斯拉特算法，是贪心算法的一个应用，用来解决单元点到其余顶点的最短路径的问题
- Floyd算法，经典的动态规划算法
作者:强某某
原文链接:https://www.jianshu.com/p/31c8d28417b1