数据结构与算法

不作声

发布于 2020-07-14 11:26:37

3720

发布于 2020-07-14 11:26:37

文章被收录于专栏：M不作声

常见的数据结构

线性表链表是一个线性结构，同时也是一个天然的递归结构，链表增加了节点的指针域，空间开销比较大。 循环单链表是链表的最后一个节点指向第一个节点，构成一个链环。 双向链表是节点中包含两个指针部分，一个指向前驱元，一个指向后继元。
栈和队列 栈是一个线性结构，只能在某一端添加或删除数据，遵循先进后出的原则。对栈的基本操作有进栈（push）和（pop）出栈，相当于插入和删除最后一个元素。可以用数组实现。 队列是一种特殊的线性表，只允许在表的前端（front）进行删除操作，在表的后端（rear）进行插入操作。
树与二叉树
- 树，是由n个有限节点组成一个具有层次关系的集合，是一种非常重要的数据结构。每个节点有零个或多个子节点，没有父节点的节点称为根节点；每个非根节点有且只有一个父节点；没有子节点的节点称为叶子结点；除了根节点外，每个子节点都可以分为多个不相交的子树。
- 二叉树，是每个节点最多拥有两个子节点，分别为左节点和右节点。
- 二叉查找树，也叫二叉排序树，二叉搜索树。与二叉树的区别在于每个节点的值都比他的左子树大，比右子树小
图图，是一种比树更为复杂的数据结构。树的节点之间是一对多的关系，且存在父子的层级划分；图的顶点之间是多对多的关系，并且所有的节点都是平等的，没有谁是父谁是子。

树的遍历

树的遍历分为深度优先搜索和广度优先搜索。深度优先搜索有先序遍历、中序遍历、和后序遍历三种方式。广度优先搜索是层次遍历。

先序遍历算法：先访问根节点，然后访问左节点，最后访问右节点。

preTraversal() {
  this._pre(this.root)
}
_pre(node) {
  if(node) {
    console.log(node.value)
    this._pre(node.left)
    this._pre(node.right)
  }
}

中序遍历算法：先访问左节点，然后访问根节点，最后访问右节点。

midTraversal() {
  this._mid(this.root)
}

_mid(node) {
  if(node) {
    this._mid(node.left)
    console.(node.value)
    this._mid(node.right)
  }
}

后序遍历算法：先访问左节点，然后访问右节点，最后访问根节点。

backIraversal() {
  this._back(this.root)
}
_bcak(node) {
  if(node) {
    this._back(node.left)
    this._back(node.right)
    console.log(node.value)
  }
}

层次遍历，使用队列结构完成。

breadthTraversal() {
  if(!this.root) return null
  let q = new Queue()
  q.enQueue(this.root)
  while (!q.isEmpty()) {
    let n = q.deQueue()
    if(n.left) q.enQueue(n.left)
    if(n.right) q.enQueue(n.right)
  }
}

树节点的插入和删除

节点插入将该节点的值与树上节点的值做比较，如果小于，继续遍历左子树；如果大于，继续遍历右子树。如果左右子树为空，那么直接插入。如果大于左子树，则判断右子树；如果小于右子树，则判断左子树。
节点删除，节点删除分为三种情况
- 需要删除的节点没有子树
- 需要删除的节点只有一条子树
- 需要删除的节点有左右两条树
最复杂的是第三种情况，解决办法为：找到需要删除节点p的直接前缀p（或直接后缀）s，用s来替换节点p，然后再删除此节点s。

delect(v) {
  this.root = this._delect(this.root, v)
}
_delect(node, v){
  if(!node) return null
  // 判断在左子树还是在右子树
  if(node.value < v) {
    node.right = this._delect(node.right.v)
  } eles if(node.value > v) {
    node.left = this._delect(node.left.v)
  } else {
    if (!node.left) return node.right
    if (!node.right) return node.left
    // _getMin()获取右树上最小的节点 _delectMin()删除最小节点
    // 
    let min = this._getMin(node.right)
    min.right = this._delectMin(node.right)
    min.left = node.left
    node = min
  }
  // 维护size
  node.size = this._getSize(node.left) + this._getSize(node.right) + 1
  return node
}

插入排序

构建有序序列，扫描已排序序列，将数据插入到有序序列中合适的位置。

function checkArray(array) {
  return Array.isArray(array)
}

function swaps(array, left, right) {
  let rightValue = array[right]
  array[right] = array[left]
  array[left] = rightValue
}

function insertion(array) {
  if (!checkArray(array)) return
  for (let i = 1; i < array.length; i++) {
    for (let j = i - 1; j >= 0 && array[j] > array[j + 1]; j--)
      swap(array, j, j +1)
  }
  return array;
}

选择排序

在序列中找出最小的元素，放到排序序列的起始位置，然后再从剩下的序列中再找出最小的元素，重复这个过程。

function select(array) {
  if (!checkArray(array)) return
  for (let i = 0; i < array.length - 1; i++) {
    let minIndex = i;
    for(let j = i + 1; j < array.length; j++) {
      minIndex = array[j] < array[minIndex] ? j : minIndex;
    }
    swap(array, i, minIndex);
  }
  return array;
}

冒泡排序

比较两个元素，将较大的元素放在后边，当一次循环完成后，最大的元素被放在最后的位置，循环这个过程，知道排序完成。

代码实现：

funciton bubble(array) {
  checkArray(array);
  for (let i = array.legth - 1; i > 0; i--){
    for (let j = 0; j < i; j++) {
      if (array[j] > array[j + 1]) swap(array, j, j+1)
    }
  }
}

快速排序

在序列中选取一个值，将比该值小的元素放在左边，比该值大的放在右边，在分别对左右两侧的元素做相同的操作，直到排序完成。

function sort(array) {
  if (!checkArray(array)) return
  quickSort(array, 0, array.length - 1);
  return array;
}

function quickSort(array, left, right) {
  if (left < right) {
    swap(array, , right)
    // 随机取值，然后和末尾交换，这样做比固定取一个位置的复杂度略低
    let indexs = part(array, parseInt(Math.random() * (right - left + 1)) + left, right);
    quickSort(array, left, indexs[0]);
    quickSort(array, indexs[1] + 1, right);
  }
}
function part(array, left, right) {
  let less = left - 1;
  let more = right;
  while (left < more) {
    if (array[left] < array[right]) {
      // 当前值比基准值小，`less` 和 `left` 都加一
	   ++less;
       ++left;
    } else if (array[left] > array[right]) {
      // 当前值比基准值大，将当前值和右边的值交换
      // 并且不改变 `left`，因为当前换过来的值还没有判断过大小
      swap(array, --more, left);
    } else {
      // 和基准值相同，只移动下标
      left++;
    }
  }
  // 将基准值和比基准值大的第一个值交换位置
  // 这样数组就变成 `[比基准值小, 基准值, 比基准值大]`
  swap(array, right, more);
  return [less, more];
}

归并排序

将序列的元素分成多个具有两个元素的子序列，将子序列排序后再将两个子序列合并，再排序再合并，直到合并为一个数组。

function sort(array) {
  if (!checkArray(array)) return
  mergeSort(array, 0, array.length - 1);
  return array;
}

function mergeSort(array, left, right) {
  // 左右索引相同说明已经只有一个数
  if (left === right) return;
  // 等同于 `left + (right - left) / 2`
  // 相比 `(left + right) / 2` 来说更加安全，不会溢出
  // 使用位运算是因为位运算比四则运算快
  let mid = parseInt(left + ((right - left) >> 1));
  mergeSort(array, left, mid);
  mergeSort(array, mid + 1, right);

  let help = [];
  let i = 0;
  let p1 = left;
  let p2 = mid + 1;
  while (p1 <= mid && p2 <= right) {
    help[i++] = array[p1] < array[p2] ? array[p1++] : array[p2++];
  }
  while (p1 <= mid) {
    help[i++] = array[p1++];
  }
  while (p2 <= right) {
    help[i++] = array[p2++];
  }
  for (let i = 0; i < help.length; i++) {
    array[left + i] = help[i];
  }
  return array;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020.07.10，如有侵权请联系 cloudcommunity@tencent.com 删除

数据结构