数据结构基础详解

数据结构的概念

数据结构,直白的理解,就是研究数据的存储方式。

数据结构是一门学科,它教会我们「如何存储具有复杂关系的数据更有助于后期对数据的再利用」。

存储结构

数据结构大致包含以下几种存储结构:

  1. 线性表
    • 顺序表
    • 链表
    • 栈和队列
  2. 树结构
    • 普通树
    • 二叉树
    • 线索二叉树等
  3. 图存储结构

下面对各种数据结构做详细讲解。

线性表

将具有 「一对一」 关系的数据 「线性」 地存储到物理空间中,这种存储结构就称为线性存储结构(简称线性表)。

使用线性表存储数据的方式可以这样理解,即「把所有数据用一根线儿串起来,再存储到物理空间中」。

线性表

使用线性表存储的数据,要求数据类型必须一致。

线性表并不是一种具体的存储结构,它包含顺序存储结构链式存储结构,是顺序表和链表的统称。

上图中我们可以看出,线性表存储数据可细分为以下 2 种:
如图 3a) 所示,将数据依次存储在连续的整块物理空间中,这种存储结构称为顺序存储结构(简称顺序表);
如图 3b) 所示,数据分散的存储在物理空间中,通过一根线保存着它们之间的逻辑关系,这种存储结构称为链式存储结构(简称链表);

前驱和后继

数据结构中,一组数据中的每个个体被称为数据元素,简称元素

另外,对于具有 「一对一」 逻辑关系的数据,我们一直在用「某一元素的左侧(前边)或右侧(后边)」这样不专业的词,其实线性表中有更准确的术语:

  • 某一元素的左侧相邻元素称为 直接前驱,位于此元素左侧的所有元素都统称为 前驱元素
  • 某一元素的右侧相邻元素称为 直接后继,位于此元素右侧的所有元素都统称为 后继元素

如下图,元素 3 它的直接前驱是 2 ,此元素的前驱元素有 2 个,分别是 12;同理,此元素的直接后继是 4 ,后继元素也有 2 个,分别是 45

前驱和后继

顺序表

顺序表,全名顺序存储结构,是线性表的一种。

顺序表存储数据时,会提前申请一整块足够大小的物理空间,然后将数据依次存储起来,存储时做到数据元素之间不留一丝缝隙。

顺序表,简单的理解就是常用的数组,例如使用顺序表存储 [1, 3, 5, 7, 9],如图:

顺序表

由于顺序表结构的底层实现借助的就是数组,因此对于初学者来说,可以把顺序表完全等价为数组,但实则不是这样。数据结构是研究数据存储方式的一门学科,它囊括的都是各种存储结构,而数组只是各种编程语言中的基本数据类型,并不属于数据结构的范畴。

顺序表的初始化

使用顺序表存储数据之前,除了要申请足够大小的物理空间之外,为了方便后期使用表中的数据,顺序表还需要实时记录以下 2 项数据:

  • 顺序表申请的存储容量;
  • 顺序表的长度,也就是表中存储数据元素的个数;

由于顺序表可以简单的理解为数组,所以在这里就定义一个数组,将数组当作一个顺序表来处理。

和大多数其他语言不同, JS 数组的 length 是没有上界的. 如果你用大于或等于当前 length 的数字作为下标来存储一个元素, 那么 length 值会被增大以容纳新元素, 不会发生数组越界错误,所以存储容量也是动态变化的。

1
// 定义一个顺序表
2
function List(list) {
3
  this.data = list || [];
4
  this.getLength = getLength;
5
  this.clear = clear; // 清空顺序表
6
  this.insertEl = insertEl; // 插入元素
7
  this.removeEl = removeEl; // 删除元素
8
  this.changeEl = changeEl; // 更改元素
9
  this.findEl = findEl;     // 查找元素
10
}

顺序表插入元素

向已有顺序表中插入数据元素,根据插入位置的不同,可分为以下 3 种情况:

  • 插入到顺序表的表头;
  • 在表的中间位置插入元素;
  • 尾随顺序表中已有元素,作为顺序表中的最后一个元素;

虽然数据元素插入顺序表中的位置有所不同,但是都使用的是同一种方式去解决,即:通过遍历,找到数据元素要插入的位置,然后做如下两步工作:

  • 将要插入位置元素以及后续的元素整体向后移动一个位置;
  • 将元素放到腾出来的位置上;

例如,在 [1, 2, 3, 4, 5] 的第 3 个位置上插入元素 6,实现过程如下:

  • 遍历至顺序表存储第 3 个数据元素的位置。

    找到目标元素位置

  • 将元素 3 以及后续元素 45 整体向后移动一个位置。

    将插入位置腾出

  • 将新元素 6 放入腾出的位置。

    插入目标元素

1
2
function getLength() {
3
  return this.data.length;
4
}
5
6
/**
7
 * @param {any} el 要插入的元素
8
 * @param {Number} index 元素下标
9
 */
10
function insertEl(el, index) {
11
  if (index > this.getLength() || index < 0) {
12
      throw new Error('插入位置有错');
13
  } else {
14
    // 插入操作,需要将从插入位置开始的后续元素,逐个后移
15
    for (var len = this.getLength(); len >= index; len--) {
16
        this.data[len] = this.data[len - 1];
17
    }
18
    // 后移完成后,直接将所需插入元素,添加到顺序表的相应位置
19
    this.data[index] = el;
20
    return this.data;
21
  }
22
}

为数组添加元素,可以通过 push()unshift()splice(index, 0, element) 方法实现。

1
// 向数组头部添加元素:
2
arr.unshift();
3
// 向数组末尾添加元素:
4
arr.push();
5
// 向数组下标 index 处插入元素:
6
arr.splice(index, 0, el)

顺序表删除元素

从顺序表中删除指定元素,只需找到目标元素,并将其后续所有元素整体前移 1 个位置即可。

后续元素整体前移一个位置,会直接将目标元素删除,可间接实现删除元素的目的。

例如,从 [1, 2, 3, 4, 5] 中删除元素 3 的过程,如下图所示:

顺序表删除元素

js 代码实现:

1
/**
2
 * @param {Number} index 被删除元素的下标
3
 */
4
function removeEl(index) {
5
  if (index > this.getLength() || index < 0) {
6
      throw new Error('删除位置有误');
7
  } else {
8
    // 删除操作
9
    for (var i = index; i < this.getLength() - 1; i++) {
10
       this.data[i] = this.data[i + 1];
11
    }
12
    this.data.length--;
13
    return this.data;
14
  }
15
}

删除数组的元素,可以通过 pop()shift()splice(index, 1) 方法实现。

1
// 从数组头部删除元素:
2
arr.shift();
3
// 从数组末尾删除元素:
4
arr.pop();
5
// 从数组下标 index 处删除一个元素:
6
arr.splice(index, 1);

顺序表查找元素

顺序表中查找目标元素,可以使用多种查找算法实现,比如说二分查找算法、插值查找算法等。

这里,我们选择顺序查找算法,具体实现代码为:

1
/**
2
 * @param {any} el 需要查找的元素
3
 */
4
function findEl(el) {
5
  for (let i = 0; i < this.getLength(); i++) {
6
    if (this.data[i] == el) {
7
        return i; // 第一次匹配到的元素的下标
8
    }
9
  }
10
  return -1; //如果查找失败,返回 -1
11
}

查找数组元素的下标,可以使用 indexOf()lastIndexOf() 方法实现。

顺序表更改元素

顺序表更改元素的实现过程是:

  • 找到目标元素;
  • 直接修改该元素的值;
1
/**
2
 * @param {any} el 需要更改的元素
3
 * @param {any} newEl 为新的数据元素
4
 */
5
function changeEl( el, newEl) {
6
  const index = this.findEl(el);
7
  this.data[index] = newEl;
8
  return this.data;
9
}

以上是顺序表使用过程中最常用的基本操作,这里给出完整的实现代码:

1
class List {
2
  constructor(list) {
3
    this.data = list || [];
4
  }
5
6
  clear() {
7
    delete this.data;
8
    this.data = [];
9
    return this.data;
10
  }
11
12
  getLength() {
13
    return this.data.length;
14
  }
15
16
  insertEl(index, el) {
17
    if (index > this.getLength() || index < 0) {
18
        throw new Error('插入位置有错');
19
    } else {
20
      // 插入操作,需要将从插入位置开始的后续元素,逐个后移
21
      for (var len = this.getLength(); len >= index; len--) {
22
          this.data[len] = this.data[len - 1];
23
      }
24
      // 后移完成后,直接将所需插入元素,添加到顺序表的相应位置
25
      this.data[index] = el;
26
      return this.data;
27
    }
28
  }
29
30
  // 通过下标删除元素
31
  removeEl(index) {
32
    if (index > this.getLength() || index < 0) {
33
        throw new Error('删除位置有误');
34
    } else {
35
      // 删除操作
36
      for (var i = index; i < this.getLength() - 1; i++) {
37
         this.data[i] = this.data[i + 1];
38
      }
39
      this.data.length--;
40
      return this.data;
41
    }
42
  }
43
44
  changeEl(el, newEl) {
45
    const index = this.findEl(el);
46
    this.data[index] = newEl;
47
    return this.data;
48
  }
49
50
  findEl(el) {
51
    for (let i = 0; i < this.getLength(); i++) {
52
      if (this.data[i] == el) {
53
          return i; // 第一次匹配到的元素的下标
54
      }
55
    }
56
    return -1; //如果查找失败,返回 -1
57
  }
58
}
59
60
const list = new List([1, 2, 3, 4, 5])
61
62
console.log('初始化顺序表:')
63
console.log(list.data.join(','));
64
65
console.log('删除下标为 0 的元素:')
66
console.log(list.removeEl(0).join(','));
67
68
console.log('在下标为 3 的位置插入元素 6:')
69
console.log(list.insertEl(3, 6).join(','));
70
71
console.log('查找元素 3 的下标:')
72
console.log(list.findEl(3));
73
74
console.log('将元素 3 改为 6:')
75
console.log(list.changeEl(3, 6).join(','))

程序运行结果:

1
初始化顺序表:
2
1,2,3,4,5
3
4
删除下标为 0 的元素:
5
2,3,4,5
6
7
在下标为 3 的位置插入元素 6:
8
2,3,4,6,5
9
10
查找元素 3 的下标:
11
1
12
13
将元素 3 改为 6:
14
2,6,4,6,5

顺序表(数组)的缺点

数组不总是组织数据的最佳数据结构,原因如下。在很多编程语言中,数组的长度是固定的,所以当数组已被数据填满时,再要加入新的元素就会非常困难。在数组中,添加和删除元素也很麻烦,因为需要将数组中的其他元素向前或向后平移,以反映数组刚刚进行了添加或删除操作。

然而,JavaScript 的数组并不存在上述问题,因为使用 split() 方法不需要再访问数组中的其他元素了。

JavaScript 中数组的主要问题是,它们被实现成了对象,与其他语言(比如 C++ 和 Java) 的数组相比,效率很低(请参考 Crockford 那本书的第 6 章)。

如果你发现数组在实际使用时很慢,就可以考虑使用链表来替代它。除了对数据的随机访问,链表几乎可以用在任何可以使用一维数组的情况中。如果需要随机访问,数组仍然是更好的选择。

链表

链表,别名链式存储结构单链表,用于存储逻辑关系为 「一对一」 的数据。

我们知道,使用顺序表(底层实现靠数组)时,需要提前申请一定大小的存储空间,这块存储空间的物理地址是连续的,如下图所示。

顺序表

链表则完全不同,使用链表存储数据时,是随用随申请,因此数据的存储位置是相互分离的,换句话说,数据的存储位置是随机的。

单链表

我们看到,上图根本无法体现出各数据之间的逻辑关系。对此,链表的解决方案是,每个数据元素在存储时都配备一个指针,用于指向自己的直接后继元素,如下图所示。

链表

数据元素随机存储,并通过指针表示数据之间逻辑关系的存储结构就是链式存储结构。

链表的节点

链表中每个数据的存储都由以下两部分组成:

  • 数据元素本身,其所在的区域称为数据域
  • 指向直接后继元素的指针,所在的区域称为指针域

链表中存储各数据元素的结构如下图所示:

链表

上图所示的结构在链表中称为节点。也就是说,链表实际存储的是一个一个的节点,真正的数据元素包含在这些节点中

节点

头节点、头指针和首元节点

其实,一个完整的链表需要由以下几部分构成:

  1. 头指针:一个普通的指针,它的特点是永远指向链表第一个节点的位置。很明显,头指针用于指明链表的位置,便于后期找到链表并使用表中的数据;

  2. 节点:链表中的节点又细分为头节点首元节点其他节点

    • 头节点:其实就是一个不存任何数据的空节点,通常作为链表的第一个节点。对于链表来说,头节点不是必须的,它的作用只是为了方便解决某些实际问题;

    • 首元节点:由于头节点(也就是空节点)的缘故,链表中称第一个存有数据的节点为首元节点。首元节点只是对链表中第一个存有数据节点的一个称谓,没有实际意义;

    • 其他节点:链表中其他的节点;

一个存储 [1, 2, 3] 的完整链表结构如图所示:

链表

链表中有头节点时,头指针指向头节点;反之,若链表中没有头节点,则头指针指向首元节点。

链表的初始化

我们设计的链表包含两个类:

  • Node 类用来表示节点;
  • LinkedList 类提供了插入的节点、删除节点、显示列表元素的方法,以及其他辅助方法。

Node 类包含两个属性,elementnext

1
// Node 类
2
class Node {
3
  constructor(element) {
4
    this.element = element; // element 用来保存节点上的数据
5
    this.next = null; // next 用来保存指向下一节点的指针
6
  }
7
}

LinkedList 类提供了对链表进行操作的方法。链表只有一个属性,那就是使用一个 Node 对象来保存该链表的头节点。

1
function LinkedList() { 
2
  // head 节点的 next 属性被初始化为 null,当有新元素插入时,next 会指向新的元素
3
  this.head = new Node('head');
4
  this.find = find;
5
  this.insert = insert;
6
  this.findPrevious = findPrevious;
7
  this.remove = remove;
8
  this.display = display;
9
}

链表插入元素

同顺序表一样,向链表中增添元素,根据添加位置不同,可分为以下 3 种情况:

  • 插入到链表的头部(头节点之后),作为首元节点;
  • 插入到链表中间的某个位置;
  • 插入到链表的最末端,作为链表中最后一个数据元素;

虽然新元素的插入位置不固定,但是链表插入元素的思想是固定的,只需做以下两步操作,即可将新元素插入到指定的位置:

  • 将新节点的 next 指针指向插入位置后的节点;
  • 将插入位置前节点的 next 指针指向插入节点;

例如,我们在链表 [1, 2, 3, 4] 的基础上分别实现在头部、中间部位、尾部插入新元素 5,其实现过程如下图所示:

链表插入节点

注意:链表插入元素的操作必须是先步骤 1,再步骤 2;反之,若先执行步骤 2,除非再添加一个指针,作为插入位置后续链表的头指针,否则会导致插入位置后的这部分链表丢失,无法再实现步骤 1

创建一个辅助方法 find(),该方法遍历链表,查找给定数据。

find() 方法实现:

1
function find(item) {
2
  var currNode = this.head; // 创建一个新节点
3
  while (currNode.element != item) { // 如果当前节点数据不符合我们要找的节点
4
      currNode = currNode.next; // 当前节点移动到一下节点
5
  }
6
  return currNode;
7
}

一旦找到 给定 的节点,就可以将新节点插入链表了。首先,将新节点的 next 指针指向 给定 节点 next 指向的节点。然后设置 给定 节点的 next 属性指向新节点。

insert() 方法的定义如下:

1
function insert(newElement, item) {
2
  var newNode = new Node(newElement);
3
  var current = this.find(item);
4
  // 向链表插入节点 newNode
5
  newNode.next = current.next; // 将新节点的 next 指针指向插入位置后的节点 (步骤 1)
6
  current.next = newNode; // 设置插入位置前的 next 指针指向新节点(步骤2)
7
}

现在已经可以开始测试我们的链表实现了。然而在测试之前,先来定义一个 display() 方法,该方法用来显示链表中的元素:

1
function display() {
2
  var currNode = this.head;
3
  while(!(currNode.next == null)) { // 当当前节点的 next 指针为 null 时 循环结束
4
    //为了不显示头节点,程序只访问当前节点的下一个节点中保存的数据
5
    console.log(chrrNode.next.element);
6
    currNode = currNode.next;
7
  }
8
}

测试程序:

1
function Node(element) {
2
  this.element = element;
3
  this.next = null;
4
}
5
6
function LinkedList() {
7
  this.head = new Node('head');
8
  this.find = find;
9
  this.insert = insert;
10
  this.findPrevious = findPrevious;
11
  this.remove = remove;
12
  this.display = display;
13
}
14
15
function find(item) {
16
  var currNode= this.head;
17
  while(currNode.element != item) {
18
    currNode = currNode.next;
19
  }
20
  return currNode;
21
}
22
23
function insert(newElement, item) {
24
  var newNode = new Node(newElement);
25
  var current = this.find(item);
26
  newNode.next = current.next;
27
  current.next = newNode;
28
}
29
function findPrevious() {}
30
function remove() {}
31
function display() {
32
  var currNode = this.head;
33
  while(!(currNode.next == null)) {
34
    console.log(currNode.next.element)
35
    currNode = currNode.next;
36
  }
37
}
38
var list = new LinkedList();
39
40
list.insert(1, 'head')
41
list.insert(2, 1)
42
list.insert(3, 2)
43
list.insert(4, 3)
44
list.display()

程序运行结果:

1
1
2
2
3
3
4
4

链表删除元素

从链表中删除指定数据元素时,需要进行以下 2 步操作:

  • 需要先找到待删除节点前面的节点 直接前驱节点
  • 找到这个节点后,修改它的 next 指针,使其不再指向待删除节点;

删除节点

从链表中删除节点时,需要先找到待删除节点的直接前驱节点。找到这个节点后,修改它的 next 指针,我们可以定义一个方法 findPrevious(),来做这件事。

findPrevious() 方法遍历链表中的元素,检查每一个节点的 直接后继节点 中是否存储着待删除数据。如果找到,返回该节点(待删除节点的直接前驱节点)。

1
function findPrevious(item) {
2
  var currNode = this.head;
3
  while(!(currNode.next == null) && currNode.next.element != item) {
4
    currNode = currNode.next;
5
  }
6
  return currNode;
7
}

删除节点的原理很简单,找到该节点的直接前驱节点 prevNode 后,修改它的 next 指针:

1
prevNode.next = prevNode.next.next;

remove() 方法的 js 实现:

1
function remove(item) {
2
  var prevNode = this.findPrevious(item);
3
  if(!(prevNode.next == null)) {
4
    prevNode.next = prevNode.next.next;
5
  }
6
}

测试程序:

1
...
2
var list = new LinkedList();
3
list.insert(1, 'head')
4
list.insert(2, 1)
5
list.insert(3, 2)
6
list.insert(4, 3)
7
list.display() 
8
list.remove(2)
9
list.display()

程序运行结果:

1
// 没调用 list.remove(2) 之前
2
1
3
2
4
3
5
4
6
// 调用list.remove(2)
7
1
8
3
9
4

链表更改节点

更新链表中的元素,只需通过遍历找到存储此元素的节点,对节点中的数据域做更改操作即可。

1
function change(index, newElement) {
2
  var currNode = this.head;
3
  for(var i = 0; i <= index; i++) {
4
    currNode = currNode.next;
5
    if (currNode == null) {
6
      throw new Error('更新位置无效');
7
      return;
8
    }
9
  }
10
  currNode.element = newElement;
11
  return currNode;
12
}

最后给出 js 实现的拥有基本操作 增删改查 的链表完整代码:

1
class Node {
2
  constructor(element) {
3
    this.element = element;
4
    this.next = null;
5
  }
6
}
7
8
class LinkedList {
9
  constructor() {
10
    this.head = new Node('head');
11
  }
12
  // 链表查找元素
13
  find(item) { 
14
    var currNode= this.head;
15
    while(currNode.element != item) {
16
      currNode = currNode.next;
17
    }
18
    return currNode;
19
  }
20
  // 链表添加元素
21
  insert(newElement, item) { 
22
    var newNode = new Node(newElement);
23
    var current = this.find(item);
24
    newNode.next = current.next;
25
    current.next = newNode;
26
  }
27
  // 链表查找直接前驱节点(辅助方法)
28
  findPrevious(item) {
29
    var currNode = this.head;
30
    while(!(currNode.next == null) && currNode.next.element != item) {
31
      currNode = currNode.next;
32
    }
33
    return currNode;
34
  }
35
  // 链表删除节点
36
  remove(item) {
37
    var prevNode = this.findPrevious(item);
38
    if(!(prevNode.next == null)) {
39
      prevNode.next = prevNode.next.next;
40
    }
41
  }
42
  // 链表更改节点
43
  change(index, newElement) {
44
    var currNode = this.head;
45
    for(var i = 0; i <= index; i++) {
46
      currNode = currNode.next;
47
      if (currNode == null) {
48
        throw new Error('更新位置无效');
49
        return;
50
      }
51
    }
52
    currNode.element = newElement;
53
    return currNode;
54
  }
55
  display() {
56
    var currNode = this.head;
57
    while(!(currNode.next == null)) {
58
      console.log(currNode.next.element)
59
      currNode = currNode.next;
60
    }
61
  }
62
}
63
64
var list = new LinkedList();
65
list.insert(1, 'head')
66
list.insert(2, 1)
67
list.insert(3, 2)
68
list.insert(4, 3)
69
console.log('初始化链表:')
70
list.display() // 1, 2, 3, 4
71
list.remove(2)
72
console.log('删除数据为 2 的节点: ')
73
list.display() // 1, 3, 4
74
list.change(2, 6) 
75
console.log('将下标为 2 的 节点数据更改为 6:')
76
list.display() // 1, 3, 6

整体程序运行结果:

1
初始化链表:
2
1
3
2
4
3
5
4
6
删除数据为 2 的节点: 
7
1
8
3
9
4
10
将下标为 2 的 节点数据更改为 6
11
1
12
3
13
6

下章节:

静态链表

双向链表

循环链表

双向循环链表

栈和队列

栈和队列隶属于线性表,是特殊的线性表,因为它们对线性表中元素的进出做了明确的要求。

中的元素只能从线性表的一端进出(另一端封死),且要遵循 「先入后出」 的原则,即先进栈的元素后出栈。

栈

栈结构如上图所示,像一个木桶,栈中含有 3 个元素,分别是 ABC,从在栈中的状态可以看出 A 最先进的栈,然后 B 进栈,最后 C 进栈。根据「先进后出」的原则,3 个元素出栈的顺序应该是:C 最先出栈,然后 B 出栈,最后才是 A 出栈。

队列中的元素只能从线性表的一端进,从另一端出,且要遵循「先入先出」的特点,即先进队列的元素也要先出队列。

队列

队列结构如上图所示,队列中有 3 个元素,分别是 ABC,从在队列中的状态可以看出是 A 先进队列,然后 B 进,最后 C 进。根据「先进先出」的原则,3 个元素出队列的顺序应该是 A 最先出队列,然后 B 出,最后 C 出。

树存储结构

树存储结构适合存储具有「一对多」关系的结构。

树结构

如图所示,其中张平只有一个父亲,但他却有两(多)个孩子,这就是「一对多」的关系,满足这种关系的数据可以使用树存储结构。

图存储结构

图存储结构适合存储具有「多对多」关系的结构。

图存储