PHP8.1.21版本已发布
vue8.1.21版本已发布
jquery8.1.21版本已发布

javascript有数据结构吗

WBOY
WBOY 原创
2022-06-17 11:01:22 1813浏览

javascript中有数据结构,数据结构是指相互之间存在一种或者多种特定关系的数据元素集合;数据结构能够有效的管理数据对象,提升运算性能,javascript中的数据结构有列表、栈、队列、链表、字典、散列、图和二叉查找树。

本教程操作环境:windows10系统、javascript1.8.5版、Dell G3电脑。

javascript有数据结构吗

javascript有数据结构

数据结构:列表、栈、队列、链表、字典、散列、图和二叉查找树

列表

在日常生活中,人们经常使用列表:待办事项列表、购物清单、最佳十名榜单等等。而计算机程序也在使用列表,在下面的条件下,选择列表作为数据结构就显得尤为有用:

数据结构较为简单

不需要在一个长序列中查找元素,或者对其进行排序

反之,如果数据结构非常复杂,列表的作用就没有那么大了。

栈是一种特殊的列表,栈内的元素只能通过列表的一端访问,这一端称为栈顶。想象一下,我们平常在饭馆见到的一摞盘子就是现实世界常见的栈的例子,只能从最上面取盘子,盘子洗干净后,也只能放在最上面。栈被称为一种后入先出的数据结构。是一种高效的数据结构,因为数据只能在栈顶添加或删除,所以这样的操作很快。

使用条件:

只要数据的保存满足后入先出或先进后出的原理,都优先考虑使用栈

队列

队列也是一种列表,不同的是队列只能在队尾插入元素,在队首删除元素。想象一下,我们在银行排队,排在最前面的人第一个办理业务,而后面来的人只能排在队伍的后面,直到轮到他们为止。

使用条件:

只要数据的保存满足先进先出、后入后出的原理,都优先考虑使用队列

常见应用场景:

队列主要用在和时间有关的地方,特别是操作系统中,队列是实现多任务的重要机制

消息机制可以通过队列来实现,进程调度也是使用队列来实现

链表

链表也是一种列表,为什么需要出现链表,JavaScript中数组的主要问题时,它们被实现成了对象,与其他语言(比如C++和Java)的数组相对,效率很低。如果你发现数组在实际使用时很慢,就可以考虑使用链表来代替它。

使用条件:

链表几乎可以用在任何可以使用一维数组的情况中。如果需要随机访问,数组仍然是更好的选择。

字典

字典是一种以键-值对行驶存储数据的数据结构,JavaScript中的Object类就是以字典的形式设计的。JavaScript可以通过实现字典类,让这种字典类型的对象使用起来更加简单,字典可以实现对象拥有的常见功能,并相应拓展自己想要的功能,而对象在JavaScript编写中随处可见,所以字典的作用也异常明显了。

散列

散列(也称为哈希表)是一种的常用的数组存储技术,散列后的数组可以快速地插入或取用。散列使用的数据结构叫做散列表。在散列表上插入、删除和取用数据都非常快,但对于查找操作来说却效率低下,比如查找一组数组中的最大值和最小值。这些操作需要求助于其他数据结构,比如下面介绍的二叉查找树。

散列表在JavaScript中可以基础数组去进行设计。数组的长度是预先设定的,所有元素根据和该元素对应的键,保存在数组的特定位置,这里的键和对象的键是类型的概念。使用散列表存储数组时,通过一个散列函数将键映射为一个数字,这个数字的范围是0到散列表的长度。

即使使用一个高效的散列函数,依然存在将两个键映射为同一个值得可能,这种现象叫做碰撞。常见碰撞的处理方法有:开链法和线性探测法(具体概念有兴趣的可以网上自信了解)

使用条件:

可以用于数据的插入、删除和取用,不适用于查找数据

图由边的集合及顶点的集合组成。地图是我们身边很常见的现实场景,比如每两个城镇都由某种道路相连。上面的每个城镇可以看作一个顶点,连接城镇的道路便是边。边由顶点对(v1, v2)定义,v1和v2分别是图中的两个顶点。顶点也有权重,也成为成本。如果一个图的顶点对是有序的,则称之为有向图(例如常见的流程图),反之,称之为无序图。

使用场景(用图对现实中的系统建模):

交通系统,可以用顶点表示街道的十字路口,边可以表示街道。加权的边可以表示限速或者车道的数量。可以用该系统判断最佳路线及最有可能堵车的街道。

任何运输系统都可以用图来建模。比如,航空公司可以用图来为其飞行系统建模。将每个机场看成顶点,将经过两个顶点的每条航线看作一条边。加权的边可以表示从一个机场到另一个机场的航班成本,或两个机场间的距离,这取决于建模的对象是什么。

搜索图的算法主要有两种: 深度优先搜索和广度优先搜索。

二叉树和二叉查找树

树是计算机科学中经常用到的一种数据结构。树是一种非线性的数据结构,以分层的方式存储数据。

二叉树每个节点的子节点不允许超过两个。一个父节点的两个子节点分别称为左节点和右节点,通过将子节点的个数限定为2,可以写出高效的程序在树中插入、查找和删除数据。

二叉查找树(BST)是一种特殊的二叉树,相对较小的值保存在左节点中,较大的值保存在右节点中。这一特性使得查找的效率很高,对于数值型和非数值型的数据,比如单词和字符串,都是如此。

二叉查找树实现方法

function Node(data, left, right) { // 创建节点
  this.data = data;
  this.left = left;
  this.right = right;
  this.show = show
}
function show () { // 显示树的数据
  return this.data
}
function BST () { // 二叉查找树类
  this.root = null;
  this.insert = insert;
  this.inOrder = inOrder; // inOrder是遍历BST的方式
}
function insert (data) { // 向树中插入数据
  var n = new Node(data, null, null)
  if (this.root == null) {
    this.root = n;
  } else {
    var current = this.root;
    var parent;
    while (true) {
  parent = current
  if (data < current.data) {
current = current.left;
if (current == null) {
  parent.left = n;
  break;
}
  } else {
current = current.right;
if (current == null) {
  parent.right = n;
  break;
}
  }
    }
  }
}

遍历BST的方式有三种:中序遍历(以升序访问树中所有节点,先访问左节点,再访问根节点,最后访问右节点)、先序遍历(先访问根节点,再以同样的方式访问左节点和右节点)、后序遍历(先访问叶子节点,从左子树到右子树,再到根节点)

【相关推荐:javascript视频教程web前端

声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn核实处理。