JavaScript数据结构和算法

梦里梦外; 2021-09-02 10:26 442阅读 0赞

## 01-线性数据结构之数组 ##

线性数据结构：也叫一维数据结构，线性的数据结构强调存储和顺序，常用的有数组和链表两种线性数据结构。

### 特性 ###

1.  存储在物理空间上是连续的；
2.  数组定长，底层的数组长度是不可变的；
3.  数组的变量，指向了数组第一个元素的位置；

### 优点 ###

1.  查询性能好

### 缺点 ###

1.  因为数组存储的空间必须得是连续的，所以如果数组比较大，当系统的空间碎片较多的时候，容易存不下；
2.  因为数组的长度是固定的，所以数组的内容难以被添加和删除；

### 补充 ###

1.  数组 a = \[1, 2, 3, 4, 5, 6\], a\[1\], a\[2\], a\[3\]中**方括号**表示存储地址的偏移。
2.  操作系统的小知识：通过偏移查询数据性能最好。

## 02-线性数据结构之链表 ##

### 使用javascript创建一个链表 ###

// 创建一个链表节点
    function ListNode (value, next = null) { 
      this.value = value;
      this.next = next;
    };
    
    const d = new Node(4);
    const c = new Node(3, d);
    const b = new Node(2, c);
    const a = new Node(1, b);

### 特性 ###

1.  空间上是不是连续的；
2.  每存放一个值，都要多开销一个引用空间；

### 优点 ###

1.  只有内存足够大，就能存的下，不用担心空间碎片的问题；
2.  链表的添加和删除非常容易；

### 缺点 ###

1.  查询速度慢（指查询某个位置）
2.  链表的每一个节点都需要创建一个指向next的引用，浪费了一些空间。解决方法：当节点内数据越多的时候，这部分多开销的内存响应越小。

### 补充 ###

1.  如果传递一个链表，必须传递链表的根节点。每一个节点，都认为自己是根节点。

03-线性数据结构的遍历

### 03-线性数据结构的遍历 ###

#### 数组 ####

##### 循环遍历 #####

const arr = [1, 2, 3, 4, 5, 6];
    
    function ArrTraverse(arr) { 
      if (arr == null) return; // 算法对严谨性要求非常高，算法绝对不能出现报错行为；
      for (let i = 0; i < arr.length; i++) { 
        console.log(arr[i]);
      }
    }
    ArrTraverse(arr);

##### 递归遍历（重要） #####

function ArrTraverse1(arr, i) {  // 数组 开始遍历位置的索引
      if (arr[i] == null) return;
      console.log(arr[i]);
      ArrTraverse1(arr, i + 1);
    }

注： **递归的思路是先找递归的出口**

#### 链表 ####

##### 循环遍历 #####

##### 递归遍历（重要） #####

function linkTraverse1 (root) { 
      if (root == null ) return;
      console.log(root.value);
      linkTraverse1(root.next);
    }

## 04-链表的逆置 ##

## 05-排序算法 ##

[https://blog.csdn.net/weixin\_42755677/article/details/91479533][https_blog.csdn.net_weixin_42755677_article_details_91479533]

## 06-栈和队列 ##

### 栈 ###

### 队列 ###

## 07-双向链表 ##

function listNode(value) { 
        this.value = value;
        this.next = null;
        this.pre = null;
    }

## 08-二维数据结构 ##

### 二维数据结构（二维数组） ###

### 二位拓补结构（图、树） ###

描述的是一种关系，只看关系，不看大小、距离；

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mjc1NTY3Nw_size_16_color_FFFFFF_t_70]

## 二叉树 ##

[https://blog.csdn.net/weixin\_42755677/article/details/108906617][https_blog.csdn.net_weixin_42755677_article_details_108906617]

[https_blog.csdn.net_weixin_42755677_article_details_91479533]: https://blog.csdn.net/weixin_42755677/article/details/91479533
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mjc1NTY3Nw_size_16_color_FFFFFF_t_70]: /images/20210813/7fc4953a2ea8423fabf9c337ac898ac0.png
[https_blog.csdn.net_weixin_42755677_article_details_108906617]: https://blog.csdn.net/weixin_42755677/article/details/108906617