tan-ln的博客

稳住，我们能赢

0%

数据结构

发表于 更新于

链表

链表和数组

数组的内存是连续分配的，在使用数组之前需要分配固定大小的空间
链表的内存是不连续的，链表通过一个指向下一个元素地址的引用将链表中的元素串起来

单链表

是一种递归的数据结构，每个节点拥有一个元素（data）和一个指向下一个节点的引用（next）

从链头指向链尾，链尾的 Next 指针设置为 NULL

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
//节点
function Node(element) {
    this.element = element;   //当前节点的元素
    this.next = null;         //下一个节点链接
}

//链表类
function LList () {
    this.head = new Node( 'head' );     //头节点
    this.find = find;                   //查找节点
    this.insert = insert;               //插入节点
    this.remove = remove;               //删除节点
    this.findPrev = findPrev;           //查找前一个节点
    this.display = display;             //显示链表
}

//查找给定节点
function find ( item ) {
    var currNode = this.head;
    while ( currNode.element != item ){
        currNode = currNode.next;
    }
    return currNode;
}

//插入节点
function insert ( newElement , item ) {
    var newNode = new Node( newElement );
    var currNode = this.find( item );
    newNode.next = currNode.next;
    currNode.next = newNode;
}

//显示链表元素
function display () {
    var currNode = this.head;
    while ( !(currNode.next == null) ){
        console.log( currNode.next.element );
        currNode = currNode.next;
    }
}

// 倒序
function reverse() {
  var revList = new LList()
  var currNode = this.head.next
  while(currNode) {
    this.head.next = currNode.next
    currNode.next = revList.head.next
    revList.head.next = currNode
    currNode = this.head.next
  }
  return revList
}

双向链表

由各个内存结构通过指针 Next 和指针 Prev 链接在一起组成

Data 数据 + Next 指针 + Prev 指针，组成一个双向链表的内存结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
//节点类
function Node(element) {
    this.element = element;   //当前节点的元素
    this.next = null;         //下一个节点链接
    this.previous = null;     //上一个节点链接
}

//链表类
function LList () {
    this.head = new Node( 'head' );
    this.find = find;
    this.findLast = findLast;
    this.insert = insert;
    this.remove = remove;
    this.display = display;
    this.dispReverse = dispReverse;
}

//查找元素
function find ( item ) {
    var currNode = this.head;
    while ( currNode.element != item ){
        currNode = currNode.next;
    }
    return currNode;
}

//插入节点
function insert ( newElement , item ) {
    var newNode = new Node( newElement );
    var currNode = this.find( item );
    newNode.next = currNode.next;
    newNode.previous = currNode;
    currNode.next = newNode;
}

//删除节点
function remove ( item ) {
    var currNode = this.find ( item );
    if( !( currNode.next == null ) ){
        currNode.previous.next = currNode.next;
        currNode.next.previous = currNode.previous;
        currNode.next = null;
        currNode.previous = null;
    }
}

栈和队列

栈：后进先出，只能在栈顶添加或删除，遵循 先入后出

方法： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
//定义栈
function Stack () {
    this.dataStore = [];    //初始化为空
    this.top = 0;           //记录栈顶位置
    this.pop = pop;         //出栈
    this.push = push;       //入栈
    this.peek = peek;       //查看栈顶元素
    this.length = length;   //查看栈内元素总数
    this.clear = clear;     //清空栈
}

// push 压入栈
    function push( element ){
    this.dataStore[this.top++] = element;
}
// pop 顶出
function pop(){
    if(this.top > 0) {
        var popItem = this.dataStore[--this.top]
        this.dataStore.splice(this.top-1,1)
        return popItem;
    } else {
        return 'Empty'
    }
}

栈的应用
判断一个字符串是不是回文：从左到右依次压入栈，再依次出栈

其他方法

1
return String(word).split('').reverse().join('') == word ? true : false

队列：先进先出

队列只能在队尾插入元素，在队首删除元素，就像我们平时排队买票一样~

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//定义队列
function Queue(){
    this.dataStore = [];
    this.enqueue = enqueue;     //入队
    this.dequeue = dequeue;     //出队
    this.front = front;         //查看队首元素
    this.back = back;           //查看队尾元素
    this.toString = toString;   //显示队列所有元素
    this.clear = clear;         //清空当前队列
    this.empty = empty;         //判断当前队列是否为空
}

//向队列末尾添加一个元素，直接调用 push 方法即可
function enqueue ( element ) {
    this.dataStore.push( element );
}

//删除队列首的元素，可以利用 JS 数组中的 shift 方法
function dequeue () {
    if( this.empty() ) return 'This queue is empty';
    else this.dataStore.shift();
}

排序

冒泡排序

比较相邻的元素。如果第一个比第二个大，就交换它们两个
对每一对相邻元素作同样的工作

1
2
3
4
5
6
7
8
9
10
function bubbleSort(arr) {
    for (let i = 0; i < arr.length; i++) {
        for (let j = 0; j < arr.length; j++) {
            if (arr[j] > arr[j + 1]) {
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
            }           
        }
    }
    return arr
}

改进的冒泡

1
2
3
4
5
6
7
8
9
10
11
12
13
function bubbleSort(arr) {
    var i = arr.length - 1; //初始时,最后位置保持不变
    while (i > 0) {
        var pos = 0; //每趟开始时,无记录交换
        for (var j = 0; j < i; j++)
            if (arr[j] > arr[j + 1]) {
                pos = j; //记录交换的位置
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
            }
        i = pos; //为下一趟排序作准备
    }
    return arr
}

选择排序

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function selectionSort (arr) {
    var len = arr.length
    var min, temp
    for (let i = 0; i < arr.length; i++) {
        min = i
        for (let j = i + 1; j < len; j++) {
            if (arr[j] < arr[min]) {    // //寻找最小的数
                min = j         //将最小数的索引保存
            }
        }
        [arr[i], arr[min]] = [arr[min], arr[i]]
    }
    return arr
}

插入排序

从第一个元素开始
取出下一个元素，在已经排序的元素序列中从后向前扫描
如果该元素（已排序）大于新元素，将该元素移到下一位置

1

树

二叉树

深度和高度

深度：从根节点往下数
高度：节点的高度从最低叶节点开始，到目标节点的个数
（类比：楼房的楼层，从下往上数）

二叉搜索树 BTS

一个二叉树
满足 left 节点< 中间节点 < right 节点

  • 二叉搜索树的插入
  1. 如果树中没有任何节点，那么就是根节点
  2. 如果插入节点的值 比树的根节点的值大，则放在右子树，否则放在左子树
  3. 递归 （2）直到找到空位插入新节点
1
2
3
4
5
function insertNode(node, newNode) {
    if () {

    }
}

堆

  • 是一种非连续的树形存储结构，每个节点都有值，整棵树是经过排序的
  • 特点是*根节点的值最小(最大)*，且根节点的两个子树也是一个堆
  • 常用来实现优先队列，存储随意
-------------本文结束感谢您的阅读-------------