常见问题

  1. 什么是数据结构？

    用于表示数据关系的结构

    常见的数据结构有：数组、链表、树、图等

  2. 什么是算法？

    根据已知数据得到结果数据的计算方法

    常见的算法有：穷举法、分治法、贪心算法、动态规划

  3. 数据结构和算法有什么关系？

    数据结构关心的是如何使用合适的结构存储数据

    算法关心的是计算过程

    有了相应的数据结构，免不了对这种数据结构的各种变化进行运算，所以，很多时候，某种数据结构都会自然而然的搭配不少算法。

  4. 数据结构和算法课程使用什么计算机语言？

    数据结构和算法属于计算机基础课程，它们和具体的语言无关，用任何语言都可以实现。

    本课程采用JavaScript语言。

递归知识回顾

递归（recursion）是函数式编程思想的产物，它使用数学函数的思想进行运算，只要在数学逻辑上是合理的，即代码中的函数一定合理

使用递归时，无须深究其运行过程！

斐波拉契数列的特点是：第1位和第2位固定为1，后面的位，其数字等于前两位之和，比如：

[1, 1, 2, 3, 5, 8, 13, 21, ……]

求斐波拉契数列第n位的值，n>0

如果使用函数f(n)来表示斐波拉契数列第n位的值，通过数学分析，可以轻松得到：

1
2
3
f(1) = 1
f(2) = 1
f(n) = f(n-1) + f(n-2)

以上等式考虑到了所有情况，并且在数学逻辑上是合理的，因此，可以轻松书写到代码中：

1
2
3
4
5
6
7
// 求斐波拉契数列第n位的值
function f(n){
    if(n === 1 || n === 2){
      	return 1;
    }
    return f(n-1) + f(n-2);
}

线性结构

线性结构是数据结构中的一种分类，用于表示一系列的元素形成的有序集合。

常见的线性结构包括：数组、链表、栈、队列

数组

特别注意：这里所说的数组是数据结构中的数组，和JS中的数组不一样

数组是一整块连续的内存空间，它由固定数量的元素组成，数组具有以下基本特征：

  1. 整个数组占用的内存空间是连续的

  2. 数组中元素的数量是固定的（不可增加也不可减少），创建数组时就必须指定其长度

  3. 每个元素占用的内存大小是完全一样的
    image.png

根据数组的基本特征，我们可以推导出数组具有以下特点：

  1. 通过下标寻找对应的元素效率极高，因此遍历速度快
  2. 无法添加和删除数据，虽然可以通过某种算法完成类似操作，但会增加额外的内存开销或时间开销
  3. 如果数组需要的空间很大，可能一时无法找到足够大的连续内存

JS中的数组

在ES6之前，JS没有真正意义的数组，所谓的Array，实际上是一个对象。

ES6之后，出现真正的数组（类型化数组），但是由于只能存储数字，因此功能有限

目前来讲，JS语言只具备不完善的数组（类型化数组）

链表

为弥补数组的缺陷而出现的一种数据结构，它具有以下基本特征：

  1. 每个元素除了存储数据，需要有额外的内存存储一个引用（地址），来指向下一个元素

  2. 每个元素占用的内存空间并不要求是连续的

  3. 往往使用链表的第一个节点（根节点）来代表整个链表

    image-20200724152732227

根据链表的基本特征，我们可以推导出它具有以下特点：

  1. 长度是可变的，随时可以增加和删除元素
  2. 插入和删除元素的效率极高
  3. 由于要存储下一个元素的地址，会增加额外的内存开销
  4. 通过下标查询链表中的某个节点，效率很低，因此链表的下标遍历效率低

手动用代码实现链表

实际上，很多语言本身已经实现了链表，但链表作为一种基础的数据结构，通过手写代码实现链表，不仅可以锻炼程序思维和代码转换能力，对于后序的复杂数据结构的学习也是非常有帮助的。

因此，手写链表是学习数据结构和算法的一门基本功

手写一个链表结构，并完成一些链表的相关函数，要实现以下功能：

创建一个构造函数，用来创建Node节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * 创建node节点
 * @param {*} value 要创建node节点的值
 */
function Node(value) {
  this.value = value;
  this.next = null;
}
var a = new Node("A");
var b = new Node("B");
var c = new Node("C");
var d = new Node("D");
var e = new Node("E");
a.next = b;
b.next = c;
c.next = d;
d.next = e;

​ 注意： 一下所有的例子创建node节点都是以此构造函数生成，并创建一个链表。

  1. 遍历打印

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    /**
     * 遍历打印整个链表的数据
     * @param {*} node 
     */
    function print(node) {
      if (!node) return;
      console.log(node.value);
      if (node.next) print(node.next);
    }
    print(a);

    打印出的值为ABCDE

    line-3.png

  2. 获取链表的长度

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    /**
     * 获取链表的长度
     * @param {} node
     */
    function getLength(node) {
      if (!node) return 0;
      return 1 + getLength(node.next);
    }

    console.log(getLength(a));

    打印结果是5

  3. 通过下标获取链表中的某个数据

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    /**
     * 通过下标  获取链表中的某个数据
     * @param {*} node  链表
     * @param {*} index  下标
     */
    function selectValue(node, index) {
        /**
         * 辅助函数 通过判断当前下标和要查找的下标是否相等来查找值
         * @param {*} node  链表
         * @param {*} index  要查找的值的索引
         * @param {*} curIndex  当前的索引值
         */
      function _selectValue(node, index, curIndex) {
        if (!node) throw Error("超出界限");
        if (index === curIndex) return node.value;
        curIndex++;
        return _selectValue(node.next, index, curIndex);
      }
      return _selectValue(node, index, 0);
    }

    console.log(selectValue(a, 2));

    输出结果是C

  4. 通过下标设置链表中的某个数据

    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
    /**
     * 通过下标设置（修改）链表中的某个数据
     * @param {*} node  链表
     * @param {*} index  要修改的索引
     * @param {*} value  要修改为的值
     */
    function setNode(node, index, value) {
      var nodes = node;
      /**
       * 辅助函数  通过判断当前下标和要查找的下标是否相等来修改值
       * @param {*} node 当前的链表
       * @param {*} index 要修改的索引
       * @param {*} curIndex 当前的索引值
       */
      function _setNode(node, index, curIndex) {
        if (!node) throw Error("数据错误");
        if (index === curIndex) {
          node.value = value;
          return nodes;
        }
        curIndex++;
        return _setNode(node.next, index, curIndex);
      }
      return _setNode(node, index, 0);
    }

    console.log(setNode(a, 3, "k"));Node {value: "A", next: Node}

    // 打印的数据
    next: Node
    next: Node
    next: Node
    next: Node
    next: null
    value: "E"
    __proto__: Object
    value: "k"
    __proto__: Object
    value: "C"
    __proto__: Object
    value: "B"
    __proto__: Object
    value: "A"

  5. 在链表末尾加入一个新节点

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    /**
     * 在链表末尾加入一个新节点
     * @param {*} node  链表
     * @param {*} pushValue  要加入的新值
     */
    function pushNode(node, pushValue) {
      if (node.next) {
        return pushNode(node.next, pushValue);
      } else {
        var w = new Node(pushValue);
        return (node.next = w);
      }
    }
    console.log(pushNode(a, "w"));

  6. 在链表某一个节点之后加入一个新节点

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19

    /**
     * 在链表的某一个节点以后加入一个新的节点
     * @param {*} node 
     * @param {*} beforeNode 
     * @param {*} value 
     */
    function insertNode(node, beforeNode, value) {
      if (node === beforeNode) {
        var newNode = new Node(value);
        newNode.next = node.next;
        node.next = newNode;
      } else {
        return insertNode(node.next, beforeNode, value);
      }
    }

    insertNode(a, b, "l")
    console.log(a);

  7. 删除一个链表节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * 删除一个链表的某一个节点
 * @param {*} node 
 * @param {*} deleteValue 
 */
function deleteNode(node, deleteValue) {
  if (!node) throw Error("数据错误");
  if (node.next === deleteValue) {
    node.next = deleteValue.next;
  } else {
    deleteNode(node.next, deleteValue);
  }
}

deleteNode(a, c);
print(a)//A B l k E w

完整代码

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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
/**
 * 创建node节点
 * @param {*} value 要创建node节点的值
 */
function Node(value) {
  this.value = value;
  this.next = null;
}

var a = new Node("A");
var b = new Node("B");
var c = new Node("C");
var d = new Node("D");
var e = new Node("E");

a.next = b;
b.next = c;
c.next = d;
d.next = e;
console.log(a);

/**
 * 遍历打印整个链表的数据
 * @param {*} node
 */
function print(node) {
  if (!node) return;
  console.log(node.value);
  if (node.next) print(node.next);
}
print(a);

/**
 * 获取链表的长度
 * @param {} node
 */
function getLength(node) {
  if (!node) return 0;
  return 1 + getLength(node.next);
}

console.log(getLength(a));

/**
 * 通过下标  获取链表中的某个数据
 * @param {*} node  链表
 * @param {*} index  下标
 */
function selectValue(node, index) {
  /**
   * 辅助函数 通过判断当前下标和要查找的下标是否相等来查找值
   * @param {*} node  链表
   * @param {*} index  要查找的值的索引
   * @param {*} curIndex  当前的索引值
   */
  function _selectValue(node, index, curIndex) {
    if (!node) {
      throw Error("超出界限");
    }
    if (index === curIndex) {
      return node.value;
    }
    curIndex++;
    return _selectValue(node.next, index, curIndex);
  }
  return _selectValue(node, index, 0);
}

console.log(selectValue(a, 2));

/**
 * 通过下标设置（修改）链表中的某个数据
 * @param {*} node  链表
 * @param {*} index  要修改的索引
 * @param {*} value  要修改为的值
 */
function setNode(node, index, value) {
  var nodes = node;
  /**
   * 辅助函数  通过判断当前下标和要查找的下标是否相等来修改值
   * @param {*} node 当前的链表
   * @param {*} index 要修改的索引
   * @param {*} curIndex 当前的索引值
   */
  function _setNode(node, index, curIndex) {
    if (!node) throw Error("数据错误");
    if (index === curIndex) {
      node.value = value;
      return nodes;
    }
    curIndex++;
    return _setNode(node.next, index, curIndex);
  }
  return _setNode(node, index, 0);
}

console.log(setNode(a, 3, "k"));

/**
 * 在链表末尾加入一个新节点
 * @param {*} node  链表
 * @param {*} pushValue  要加入的新值
 */
function pushNode(node, pushValue) {
  if (node.next) {
    return pushNode(node.next, pushValue);
  } else {
    var w = new Node(pushValue);
    return (node.next = w);
  }
}
console.log(pushNode(a, "w"));

/**
 * 在链表的某一个节点以后加入一个新的节点
 * @param {*} node
 * @param {*} beforeNode
 * @param {*} value
 */
function insertNode(node, beforeNode, value) {
  if (node === beforeNode) {
    var newNode = new Node(value);
    newNode.next = node.next;
    node.next = newNode;
  } else {
    return insertNode(node.next, beforeNode, value);
  }
}

insertNode(a, b, "l");
console.log(a);

/**
 * 删除一个链表的某一个节点
 * @param {*} node 
 * @param {*} deleteValue 
 */
function deleteNode(node, deleteValue) {
  if (!node) throw Error("数据错误");
  if (node.next === deleteValue) {
    node.next = deleteValue.next;
  } else {
    deleteNode(node.next, deleteValue);
  }
}

deleteNode(a, c);
print(a)

注意：部分文章可能会在不就的将来更新

如果能够帮助到你，是小编最大的荣幸

当然 有 不好的地方 请大家帮忙指出 学习永无止境

小编一直认为 人外有人 天外有天 一起学习 共同进步

让我们共同加油吧！！！