JS数据结构与算法总结 （第一篇）

一.数据结构简介（序）：

程序设计 = 数据结构 + 算法。

数据 = 符号

(1). 其可以输入到计算机中。

(2). 能够被计算机识别和处理。

数据分为：

(1).数据元素：数据的基本单位，也称为结点或者记录。

(2).数据对象: 相同特性的数据元素的集合，是数据的一个子集。

(3).数据项: 独立含义的数据的最小单位。

数据的目的是存储，存储的目的是后期的再利用。

数据结构的主要作用是:阐述关系。

如何存储具有复杂关系的数据更有助于后期对数据的再利用。

结构:

简单的理解就是关系，不同的数据元素之间不是独立的。而是存在特定的关系。

(1). 逻辑结构:

数据对象中数据元素之间的互相关系。

四种:

集合结构、线性结构、树形结构、图形结构.

集合结构: 数据元素同属于个集合， 他们之间没有其他的关系。他们的共同属性是:“同属于一个集合”。

线性结构: 最典型的数据关系是一对一。线性结构是种有序数据的集合。除了第一个和最后一个数据元素之外，其他数据元素都是首尾相接的。

1.必存在一个第一个元素。

2.必存在最后的一个元素。

3.除最后一个元素外，其他的数据元素均有一个唯一的后续”。

4.除第一个元素之外，其他数据元素均有一个唯一的前驱。

比如：数组， 栈，队列，等都是一个线性结构。

树形结构：数据元素一对多的关系。如 Dom Tree。

图形结构：多对多的关系。如 地图。

（2）.物理结构： 数据元素存储到计算中的存储器（内存）。数据的存储结构应该正确的反应数据元素之间的逻辑关系。包括顺序存储和链式存储。

顺序存储： 该结构是把逻辑上相邻的结点存储在物理位置上相邻的存储单元中，结点之间的逻辑关系由存储单元的邻接关系来体现。

链式存储： 在计算机中用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以是不连续的)。它不要求逻辑上相邻的元素在物理位置上也相邻.因此它没有顺序存储结构所具有的弱点,但也同时失去了顺序表可随机存取的优点。

二.算法简介（序）：

算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。简单来说，算法是解决问题的方法和步骤。数据结构的实现离不开算法。

声明： JS数组不是真正意义上的数组。

传统数组是在内存中用一串连续的区域存放具有相同类型的元素。

但是，如一个js数组如下：

const arr = [123,'a',"啦啦"];

可以看出 JS 数组元素是可以任意类型的，内存地址是不连续的。所以它不是真正意义上的数组。但是它好用呀。

数组的优点：

（1）按照索引查询元素速度快；

（2）能存储大量数据；

（3）按照索引遍历数组方便；

（4）定义简单，而且访问灵活；

数组的缺点：

（1）根据内容查找元素速度很慢；

（2）数组的大小一经确定不能改变，不适合动态存储；

（3）数组只能存储一种类型的数据；

（4）增加、删除元素效率慢；

（5）未封装任何方法，所有操作都需要用户自己定义；

三.栈与队列：

（1）内存中的堆栈和数据结构中的堆栈不是一个概念， 内存中的堆栈是真实存在的物理区,数据结构中的堆栈是抽象数据存储结构。

（2）栈又名堆栈，它是一种运算受限的线性表。它遵循后进先出（LIFO）原则。

（3）受限制意思就是在新增数据、删除数据、查找等操作时，不能随心所欲，必须遵循一定的限制(规则)。

（4）向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素。

（5）从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为

新的栈顶元素

//定义一个类，相当函数 class Stack{ // 构造方法 constructor(){ this.items = []; } //添加方法，入栈顶 push(ele){ this.items.push(ele); } //出栈 pop(){ //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 = []; } }

let arr = [1,2,3];

arr.length = 0;

arr = [];

arr.splice(0,arr.length);

执行上下文： 就是当前JavaScript代码被解析和执行是所在环境的抽象概念，JavaScript中运行任何的代码都是在执行上下文中运行。（执行环境）。分为以下三种：

（1） 全局执行上下文： 默认的，最基础的执行上下文。共两个过程：1.创建全局对象，在浏览器中这个全局对象就是window对象。2.将this指针指向这个全局对象。

（2）函数执行上下文： 每次调用函数时，都会为该函数创建一个新的执行上下文。每个函数都拥有自己的执行上下文，但是只有在函数被调用的时候才会被创建。

（3）Eval函数执行上下文： eval() 函数可计算某个字符串，并执行其中的的 JavaScript 代码。运行在eval函数中的代码也获得了自己的执行上下文。

执行栈： 执行栈，也叫调用栈，遵循LIFO原则。用于存储在代码执行期间创建的所有执行上下文。如下代码：

const one = ()=>{ two(); console.log('I am one'); } const two = () =>{ console.log('I am two'); } one();

结果：

·当上述代码在浏览器中加载时，JavaScript 引擎会创建一个全局执行上下文并且将它推入到当前的执行栈。

· 当调用 one函数时，JavaScript 引擎会为该函数创建了一个新的执行上下文并将其push推到当前执行栈的栈顶。

· 当在 one() 函数中调用 two() 函数时，Javascript 引擎为该函数创建了一个新的执行上下文并将其推到当前执行栈的栈顶。

· 当two() 函数执行完成后，它的执行上下文从当前执行栈中弹出。上下文控制权将移到当前执行栈的下一个执行上下文，即 one() 函数。

从上可以知道，函数的调用的本质为压栈与出栈操作。

函数在调用栈里边有一个特例，叫做递归。

递归，就是在运行的过程中调用自己。会产生一个叫递归栈。

先进栈，到条件后就出栈。如果不出栈，由于递归调用次数过多，堆栈溢出。因为堆栈的大小是系统控制的，无法改变。

递归例子，算阶乘：

const factorial = (n) =>{ //判断出口 if(n===1){ return 1; } //递归 return n*factorial(n-1); } //输出3阶乘 console.log(factorial(3));

结果：

递归例子，斐波那契数列：

斐波那契数列指的是这样一个数列：

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,…

第3项开始，每一项都等于前两项之和。

现在求输入第几项后输出数列对应的数字：

const Fibonaqi = n=>{ if(n<2){ return n; } return Fibonaqi(n-1)+Fibonaqi(n-2); } console.log(Fibonaqi(5));

这代码有个问题，会进行非常多重复的计算，需要同时保存多个调用帧，可能导致消耗内存，爆栈。假如 n 为 5 执行过程如下：

Fib(5)=Fib(4)+Fib(3) =5 Fib(4)=Fib(3)+Fib(2) =3 Fib(3)=Fib(2)+Fib(1) =2 Fib(2)=Fib(1)+Fib(0) =1 Fib(1)= 1 Fib(0)= 0

可采用尾递归方式解决。首先理解概念：

尾调用： 尾调是在函数的执行过程中最后一个动作是一个函数的调用，即这个调用的返回值被当前函数直接返回。如下：

function g(x) { } function f(x) { return g(x) }

尾递归： 而尾递归指最后的尾调用位置上是这个函数本身。首先执行计算出一次的结果，然后执行递归调用，将当前步骤的结果值传递给下一个递归步骤。每次递归都不会增加调用栈的长度，只是更新当前的堆栈帧，只存在一个调用帧，避免了内存的消耗。

尾递归实现斐波那契数列：

int Fibonaqi(int n, int ret1, int ret2) { if (n ==0 ) { //结果 return ret1; } else { return Fib(n - 1, ret2, ret1 +ret2); } }

执行过程：

Fib (5, 0,1)=Fib (4, 1, 1) =1 Fib (4,1,1)=Fib (3, 1,2) =1 Fib (3, 1,2)=Fib (2,2, 3) =2 Fib (2,2,3)=Fib (1,3, 5) =3 Fib(1,3,5)=Fib (0,5, 8) =5

尾递归的阶乘，这个好理解点：

int facttail(int n, int a) { if (n < 0) return 0; else if (n == 0) return 1; else if (n == 1) return a; else return facttail(n - 1, n * a); }

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。遵循 FIFO，先进先出。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。

//定义一个类，实质也是一个函数 class Queue{ //定义一个构造方法 constructor(){ //实例对象 this.items = []; } //入队方法 enqueue(ele){ this.items.push(ele); } //出队方法 dequeue(){ //shift()方法可用于把数组的第一个元素从其中删除，并返回第一个元素的值。 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 = []; } }

使用看：

const queue = new Queue(); queue.enqueue(2); queue.enqueue(5); queue.enqueue(5); console.log(queue); console.log(queue.size());

运行结果正确：

首先JavaScript是单线程的，同一个时间只能做一件事。

为什么 JavaScript 是单线程 ？这主要和js的用途有关，js是作为浏览器的脚本语言，主要是实现用户与浏览器的交互，以及操作dom；这决定了它只能是单线程，否则会带来很复杂的同步问题。比如，假定JavaScript同时有两个线程，一个线程在某个 DOM 节点上添加内容，另一个线程删除了这个节点，这时浏览器就不知道以哪个线程为准。

为了利用多核 CPU 的计算能力，HTML5 提出 Web Worker 标准，允许 JavaScript

脚本创建多个线程，但是子线程完全受主线程控制，且不得操作 DOM。所以，这个新标准并没有改变 JavaScript 单线程的本质。

单线程就意味着，所有任务需要排队，前一个任务结束，才会执行后一个任务。 如果前一个任务耗时很长，如发起一个请求， 网络很慢，那后面的那个任务是不是就要一直等着。这样就很不好，那肯定不可以呀，所以js这样解决。

如在I0的时候，(输入输出的时候) ,主线程不去管IO，挂起处于等待中的任务，先运行排在后面的任务，等待I0设备返回了结果，再回过头，把挂起等待的任务继续执行下去。

于是所有的任务可以分为: 同步任务，异步任务。

同步任务: 在主线程上排队执行的任务，只有前一个任务执行完毕以后，才能够去执行下一个任务。

异步任务: 不进入主线程，而是进入任务队列，（任务队列就是主线程维护的一个任务队列，保存着异步代码），只有任务队列通知主线程，某个异步任务可以执行了，这个任务才会进入主线程执行。

有下面的代码，说出输出顺序：

console.log(1); setTimeout(()=>{ console.log(2); },60) setTimeout(()=>{ console.log(3); },0) console.log(4);

答案如下：1,4,3,2

最先执行的是同步代码，执行完毕以后，立即出栈，让出主线程。

同步代码执行完毕，立即出栈，此时主线程是处于空闲状态了。

则此时主线程去读取任务队列，队列遵循的原则是先进先出。但是，有个条件，触发条件相等既优先级一样，会遵循先进先出。就是谁先进队列谁先出去主线程运行。但是如果触发条件不相同，则优先执行到达触发条件的代码先出去。明显等待0秒的优先级更高，主线程有空就立即执行。

主线程执行完毕以后，从事件队列中去读取任务队列的过程，我们称之为事件循环。(Event Loop)

判断以下代码输出：

// 宏任务 setTimeout(()=>{ console.log('1'); },0) // 同步任务 const promise = new Promise((resolve,reject)=>{ console.log('2'); resolve(); //微任务 }).then(()=>{ console.log('3'); })

结果：

任务队列里又存在着宏任务队列和微任务队列，执行完同步任务后，先执行微任务再执行宏任务。

常见宏任务队列：lO、定时器、事件绑定、ajax …等

常见微任务队列：Promise.then catch、 finally、 process.nextTick…等

四.链表：

官方解释是：

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。

使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。链表最明显的好处就是，常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序，数据的存取往往要在不同的排列顺序中转换。链表允许插入和移除表上任意位置上的节点，但是不允许随机存取。链表有很多种不同的类型：单向链表，双向链表以及循环链表。链表可以在多种编程语言中实现。

简单来说就是：

链表： 内存地址可以是连续的，也可以是不连续的。把数据元素存放在任意的存储单元里，指针来存放数据元素的地址。

数组： 大小是固定的，一经声明就要占用整块的连续的内存空间。如果说，声明的数组过大，系统可能没有足够的连续的内存空间用于分配，(out of memory)内存不足。如果声明的数组过小，当不够用时，又需要去重新一块更大的内存，还要数据拷贝。但是数组查找元素很快。

单向链表结构图：

链表的每个元素由一个存储元素本身的节点和一个指向下一个元素的引用(有些语言称为指针或者链接)组成。

总而言之：

插入和删除： 链表性能更好。

查询和修改： 数组性能更好。

// 结点的类 class Node { constructor(element){ this.element = element; this.next = null; } } // 链表类 class LinkedList { constructor(){ //有个链表头 this.head = null; //链表长度 this.length = 0; } // 实现在链表尾部追加元素 append(element){ //新建一个结点 let node = new Node(element); //先看链表是不是空 if(this.length===0){ //为空这个结点就为表头 this.head = node; }else{ //变量,当前结点，通过从head开始遍历找到最后的结点 let current = this.head; while(current.next){ current = current.next; } //循环结束，则current为最后一个结点 //添加新结点 current.next = node; } // 长度加1 this.length+=1; } //获取链表头 getHead(){ return this.head; } //toString方法,就是输出链表内容 toString(){ let current = this.head; let linkString = ''; //遍历链表，把每个结点内容用linkString拼接起来 while(current.next){ linkString+= ','+current.element; current = current.next; } //添加最后一个结点内容 linkString+= ','+current.element; //返回内容 return linkString.slice(1); } //插入在任意位置插入元素，element是内容，position是位置 insert(element,position){ //先判断位置是有效值 if(position<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.next=this.head; this.head=node; }else{ while(indexthis.length){ return false; } //当前结点从头开始 let current = this.head; let index = 0; //老样子遍历 while(indexthis.length){ return false; } // 以下是位置有效 // 记录索引 let index = 0; //当前结点 let current = this.head; //上一个结点 let previous = null; //判断插入是不是第一个 if(position===0){ //头结点变为第二个 this.head = this.head.next; }else{ while(index

测试下：

const linkedList = new LinkedList(); //添加1,2,3,4, linkedList.append(1); linkedList.append(2); linkedList.append(3); linkedList.append(4); //删除第二个 linkedList.removeAt(2); //输出长度 console.log(linkedList.length); //输出内容 console.log(linkedList.toString()); console.log(linkedList);

结果没问题：

首先知道，JS是基于对象设计和开发出来的语言。而面向对象有三大特点: (封装、 继承于多态)。但是基于对象是使用对象，我们无法利用现有的对象模板去产生新的对象类型，继而去产生一个新的对象，也就是说基于对象是没有继承的特点。但是面向对象对象实现了继承和多态，基于现象是没有实现这些的。

oop面向对象的支持两种继承方式:接口继承、实现继承。

ECMAscript是无法去实现去接口继承的，JS只支持实现继承。实现继承主要依靠原型链去实现。

接下来简单介绍 prototype 和 _ _ proto _ _ 。

所有的引用类型(数组、函数、对象)可以自由的扩展属性(nul除外）。

所有的引用类型都有一个_ _ proto _ _属性(隐式原型，其实就是一个普通的对象。

所有的函数都有一个prototype 属性，(显式原型，它也是一个普通的对象)。

所有的引用类型，它的_ _ proto _ _属性指向它的构造函数的prototype属性。

当你试图得到一个对象的属性时，如果这个对象的本身不存在这个属性，那么就会去它的_ _ proto _ _属性中去寻找(去它的构造函数的protorype属性)中去寻找。

当调用这个对象本身并不存在的属性或者是方法时，它会一层层地往上找，一直找到null为止，null表示空的对象{ }。

//有一个构造函数 function People(name,age){ this.name = name; this.age = age; //它有一个say函数方法 this.say = function(){ console.log('哈哈哈，你也能用我啦~'); } } // 空的构造方法 function Xiaoming(){} // 我想让Xiaoming也有People里面的say方法。 // 利用原型链机制，让一个引用类型继承另一个引用类型的属性和方法 Xiaoming.prototype = new People('小明',18); var xiaoming = new Xiaoming(); xiaoming.say(); //它会像链子一样一层一层往上找，直到找到null，找到null则无路可走了证明找到了

运行结果：

五.哈希表：

哈希：

hash，一般可以称为散列。其是把任意长度的输入通过散列算法变换成固定长度的输出，那么输出的值就是散列值。这种转换是一种压缩映射。 映射表达是一 一对应的关系， 也就是说，散列值的空间通常会小于输入的空间。而且注意的是，哈希算法不能从结果去推算出输入，也就是说哈希算法是不可逆的。既然哈希特性是不可逆，那么哈希算法是可以当作一种加密算法存在的。哈希算法可以运用在加密算法上。

众所周知，数组的查询效率很高，但是，有个前提，那就是按照索引进行查找效率才高，如果是按照内容查找的话效率还是比较低的。

如下：

//有一个数组 const arr = [ {name:'xiaoming',age:18}, {name:'xiaobai',age:20} ] //直接从索引找xiaoming，速度快 console.log(arr[0]); //按照内容找xiaoming，速度慢 for(let i=0;i

那有没有一种方法，能将名字name作为索引，来提高查找速度呢？就是将字符串作为数组的索引。当然，肯定有呀，那就是----哈希表。

哈希表通常是基于数组实现的，但是相对于数组，它有很多的优势。那就是它可以提供非常非常快速的插入、删除、查找等操作。其实哈希表的结构就是数组，但是它和数组的也有不一样的地方就是哈希表对于索引的一种转换。这种转换我们通常称之为哈希函数。

一个单词如何转换为数字索引呢？

我们可以通过ASCLL码转换，每个字母都有一个对应的ASCLL码，我们可以通过把每个码相加的和作为其的数字索引。

如，有一个 name：xiao，那么xiao的ASCLL码和如下：

xiao = x + i + a + o = 120+105+97+111 = 433

那么，我们可以这样存：

arr[433] = {name:'xiao',age:20} ;

这样就可以通过索引快速查找。可以更好理解以下哈希表概念：

哈希表：

哈希表(Hash table) ，也叫散列表，是根据关键码值(Key value) 而直接进行访问的数据结构。

它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。

这个起到映射作用的叫做散列函数(Hash Function) ,存放记录的数组叫做哈希表(或者散列表)。

给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址。

发现一个问题，上面每个码相加的和作为其的数字索引的这个哈希函数得的结果会出现重复，比如 xiao 和 xioa 得到的关键码是一样的。总而来说就是对不同的关键字可能得到同一散列地址，即k1≠k2，而f(k1)=f(k2)，这种现象称为冲突，这个后面可能讲。

class HashTable{ constructor(){ // 用数组表示哈希表 this.table = []; } // 哈希函数 loseloseHashCode(key){ let hash = 0; for(let i=0;i

测试测试：

onst hashtable = new HashTable(); //添加两个元素 hashtable.put('小明','age:18'); hashtable.put('小红','age:20'); // 找小明的年纪 console.log(hashtable.get('小明'));

结果：

通过哈希函数得的重复的结果会产生覆盖问题，就是后面添加的覆盖前面添加的。这样一来前面的数据不就丢失了？那咋办呢？如下：

线性探测法：

假如如下图，我们要存一个35，哈希函数就是对其除10取余，经过哈希化得到的是index = 5,但是在插入的时候，发现这个5位置已经有了值78,那怎么办呢，那我们可以去index+1的位置，看看有没有空的位置，不空的话继续往下一点点的查找合适的位置来放置35。总结就是寻找空白的位置来放置冲突的数据项。

这样的话查找的时候也是一样，看看对应的关键码位置的值是不是自己想要的，如果不是就往下一点一点查找对比是不是自己想要的，如果一直查到空的位置都没有，那就停下查找了。因为既然有的话它会放在这个空位置的。当然，这个方法缺点也很明显，那就是万一很多连续的数据一起的，那就要找很久，耗性能。 需要注意的是对于利用开放地址法处理冲突所产生的哈希表中删除一个元素时不能直接地删除，因为这样将会截断其他具有相同哈希地址的元素的查找地址，通常可以采用设定一个特殊的标志以示该元素已被删除。

链地址法：

链地址法前面也是一样的，通过哈希函数计算关键码然后插入数值，不同的是它是插入是链表。就是说如果有关键码一样的，就插在这个关键码地址对应的链表上。

就是下面这种感觉：

六.树：请看第二篇~

数据结构

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。