前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >数据结构与算法

数据结构与算法

作者头像
不作声
发布2020-07-14 11:26:37
3720
发布2020-07-14 11:26:37
举报
文章被收录于专栏:M不作声

常见的数据结构

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

树的遍历

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

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

代码语言:javascript
复制
preTraversal() {
  this._pre(this.root)
}
_pre(node) {
  if(node) {
    console.log(node.value)
    this._pre(node.left)
    this._pre(node.right)
  }
}

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

代码语言:javascript
复制
midTraversal() {
  this._mid(this.root)
}

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

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

代码语言:javascript
复制
backIraversal() {
  this._back(this.root)
}
_bcak(node) {
  if(node) {
    this._back(node.left)
    this._back(node.right)
    console.log(node.value)
  }
}

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

代码语言:javascript
复制
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。

代码语言:javascript
复制
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
}

插入排序

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

代码语言:javascript
复制
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;
}

选择排序

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

代码语言:javascript
复制
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;
}

冒泡排序

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

代码实现:

代码语言:javascript
复制
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)
    }
  }
}

快速排序

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

代码语言:javascript
复制
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];
}

归并排序

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

代码语言:javascript
复制
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 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 常见的数据结构
  • 树的遍历
  • 树节点的插入和删除
  • 插入排序
  • 选择排序
  • 冒泡排序
  • 快速排序
  • 归并排序
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档