JavaScript - 数据结构详解(一)
2020/1/21 5:27:13
本文主要是介绍JavaScript - 数据结构详解(一),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
数据结构的概念
数据结构,直白的理解,就是研究数据的存储方式。
数据结构是一门学科,它教会我们「如何存储具有复杂关系的数据更有助于后期对数据的再利用」。
存储结构
数据结构大致包含以下几种存储结构:
-
线性表
- 顺序表
- 链表
- 栈和队列
-
树结构
- 普通树
- 二叉树
- 线索二叉树等
- 图存储结构
下面对各种数据结构做详细讲解。
线性表
将具有 「一对一」 关系的数据 「线性」 地存储到物理空间中,这种存储结构就称为线性存储结构(简称线性表)。
使用线性表存储数据的方式可以这样理解,即「把所有数据用一根线儿串起来,再存储到物理空间中」。
使用线性表存储的数据,要求数据类型必须一致。
线性表并不是一种具体的存储结构,它包含顺序存储结构和链式存储结构,是顺序表和链表的统称。
上图中我们可以看出,线性表存储数据可细分为以下 2
种:
- 如图
3a)
所示,将数据依次存储在连续的整块物理空间中,这种存储结构称为顺序存储结构(简称顺序表); - 如图
3b)
所示,数据分散的存储在物理空间中,通过一根线保存着它们之间的逻辑关系,这种存储结构称为链式存储结构(简称链表);
前驱和后继
数据结构中,一组数据中的每个个体被称为数据元素,简称元素。
另外,对于具有 「一对一」 逻辑关系的数据,我们一直在用「某一元素的左侧(前边)或右侧(后边)」这样不专业的词,其实线性表中有更准确的术语:
- 某一元素的左侧相邻元素称为 直接前驱,位于此元素左侧的所有元素都统称为 前驱元素;
- 某一元素的右侧相邻元素称为 直接后继,位于此元素右侧的所有元素都统称为 后继元素;
如下图,元素 3
它的直接前驱是 2
,此元素的前驱元素有 2
个,分别是 1
和 2
;同理,此元素的直接后继是 4
,后继元素也有 2
个,分别是 4
和 5
。
顺序表
顺序表,全名顺序存储结构,是线性表的一种。
顺序表存储数据时,会提前申请一整块足够大小的物理空间,然后将数据依次存储起来,存储时做到数据元素之间不留一丝缝隙。
顺序表,简单的理解就是常用的数组,例如使用顺序表存储 [1, 2, 3, 4, 5]
,如图:
由于顺序表结构的底层实现借助的就是数组,因此对于初学者来说,可以把顺序表完全等价为数组,但实则不是这样。数据结构是研究数据存储方式的一门学科,它囊括的都是各种存储结构,而数组只是各种编程语言中的基本数据类型,并不属于数据结构的范畴。
顺序表的初始化
使用顺序表存储数据之前,除了要申请足够大小的物理空间之外,为了方便后期使用表中的数据,顺序表还需要实时记录以下 2
项数据:
- 顺序表申请的存储容量;
- 顺序表的长度,也就是表中存储数据元素的个数;
由于顺序表可以简单的理解为数组,所以在这里就定义一个数组,将数组当作一个顺序表来处理。
和大多数其他语言不同,JavaScript
数组的length
是没有上界的。 所以存储容量也是动态变化的。
// 定义一个顺序表 function List(list) { this.data = list || []; this.getLength = getLength; this.clear = clear; // 清空顺序表 this.insertEl = insertEl; // 插入元素 this.removeEl = removeEl; // 删除元素 this.changeEl = changeEl; // 更改元素 this.findEl = findEl; // 查找元素 }
顺序表插入元素
向已有顺序表中插入数据元素,根据插入位置的不同,可分为以下 3
种情况:
- 插入到顺序表的表头;
- 在表的中间位置插入元素;
- 尾随顺序表中已有元素,作为顺序表中的最后一个元素;
虽然数据元素插入顺序表中的位置有所不同,但是都使用的是同一种方式去解决,即:通过遍历,找到数据元素要插入的位置,然后做如下两步工作:
- 将要插入位置元素以及后续的元素整体向后移动一个位置;
- 将元素放到腾出来的位置上;
例如,在 [1, 2, 3, 4, 5]
的第 3 个位置上插入元素 6
,实现过程如下:
- 遍历至顺序表存储第
3
个数据元素的位置。 - 将元素
3
以及后续元素4
和5
整体向后移动一个位置。 - 将新元素
6
放入腾出的位置。
function getLength() { return this.data.length; } /** * @param {any} el 要插入的元素 * @param {Number} index 元素下标 */ function insertEl(el, index) { if (index > this.getLength() || index < 0) { throw new Error('插入位置有错'); } else { // 插入操作,需要将从插入位置开始的后续元素,逐个后移 for (var len = this.getLength(); len >= index; len--) { this.data[len] = this.data[len - 1]; } // 后移完成后,直接将所需插入元素,添加到顺序表的相应位置 this.data[index] = el; return this.data; } }
为数组添加元素,可以通过push()
、unshift()
、splice(index, 0, element)
方法实现。
// 向数组头部添加元素: arr.unshift(); // 向数组末尾添加元素: arr.push(); // 向数组下标 index 处插入元素: arr.splice(index, 0, el)
顺序表删除元素
从顺序表中删除指定元素,只需找到目标元素,并将其后续所有元素整体前移 1
个位置即可。
后续元素整体前移一个位置,会直接将目标元素删除,可间接实现删除元素的目的。
例如,从 [1, 2, 3, 4, 5]
中删除元素 3
的过程,如下图所示:
js 代码实现:
/** * @param {Number} index 被删除元素的下标 */ function removeEl(index) { if (index > this.getLength() || index < 0) { throw new Error('删除位置有误'); } else { // 删除操作 for (var i = index; i < this.getLength() - 1; i++) { this.data[i] = this.data[i + 1]; } this.data.length--; return this.data; } }
删除数组的元素,可以通过pop()
、shift()
、splice(index, 1)
方法实现。
// 从数组头部删除元素: arr.shift(); // 从数组末尾删除元素: arr.pop(); // 从数组下标 index 处删除一个元素: arr.splice(index, 1);
顺序表查找元素
顺序表中查找目标元素,可以使用多种查找算法实现,比如说二分查找算法、插值查找算法等。
这里,我们选择顺序查找算法,具体实现代码为:
/** * @param {any} el 需要查找的元素 */ function findEl(el) { for (let i = 0; i < this.getLength(); i++) { if (this.data[i] == el) { return i; // 第一次匹配到的元素的下标 } } return -1; //如果查找失败,返回 -1 }
查找数组元素的下标,可以使用indexOf()
、lastIndexOf()
方法实现。
顺序表更改元素
顺序表更改元素的实现过程是:
- 找到目标元素;
- 直接修改该元素的值;
/** * @param {any} el 需要更改的元素 * @param {any} newEl 为新的数据元素 */ function changeEl( el, newEl) { const index = this.findEl(el); this.data[index] = newEl; return this.data; }
以上是顺序表使用过程中最常用的基本操作,这里给出完整的实现代码:
class List { constructor(list) { this.data = list || []; } clear() { delete this.data; this.data = []; return this.data; } getLength() { return this.data.length; } insertEl(index, el) { if (index > this.getLength() || index < 0) { throw new Error('插入位置有错'); } else { // 插入操作,需要将从插入位置开始的后续元素,逐个后移 for (var len = this.getLength(); len >= index; len--) { this.data[len] = this.data[len - 1]; } // 后移完成后,直接将所需插入元素,添加到顺序表的相应位置 this.data[index] = el; return this.data; } } // 通过下标删除元素 removeEl(index) { if (index > this.getLength() || index < 0) { throw new Error('删除位置有误'); } else { // 删除操作 for (var i = index; i < this.getLength() - 1; i++) { this.data[i] = this.data[i + 1]; } this.data.length--; return this.data; } } changeEl(el, newEl) { const index = this.findEl(el); this.data[index] = newEl; return this.data; } findEl(el) { for (let i = 0; i < this.getLength(); i++) { if (this.data[i] == el) { return i; // 第一次匹配到的元素的下标 } } return -1; //如果查找失败,返回 -1 } } const list = new List([1, 2, 3, 4, 5]) console.log('初始化顺序表:') console.log(list.data.join(',')); console.log('删除下标为 0 的元素:') console.log(list.removeEl(0).join(',')); console.log('在下标为 3 的位置插入元素 6:') console.log(list.insertEl(3, 6).join(',')); console.log('查找元素 3 的下标:') console.log(list.findEl(3)); console.log('将元素 3 改为 6:') console.log(list.changeEl(3, 6).join(','))
程序运行结果:
初始化顺序表: 1,2,3,4,5 删除下标为 0 的元素: 2,3,4,5 在下标为 3 的位置插入元素 6: 2,3,4,6,5 查找元素 3 的下标: 1 将元素 3 改为 6: 2,6,4,6,5
顺序表(数组)的缺点
数组不总是组织数据的最佳数据结构,原因如下。在很多编程语言中,数组的长度是固定的,所以当数组已被数据填满时,再要加入新的元素就会非常困难。在数组中,添加和删除元素也很麻烦,因为需要将数组中的其他元素向前或向后平移,以反映数组刚刚进行了添加或删除操作。
然而,JavaScript
的数组并不存在上述问题,因为使用 split()
方法不需要再访问数组中的其他元素了。
JavaScript
中数组的主要问题是,它们被实现成了对象,与其他语言(比如 C++ 和 Java) 的数组相比,效率很低(请参考 Crockford 那本书的第 6 章)。
如果你发现数组在实际使用时很慢,就可以考虑使用链表
来替代它。除了对数据的随机访问,链表
几乎可以用在任何可以使用一维数组的情况中。如果需要随机访问,数组仍然是更好的选择。
链表
链表,别名链式存储结构
或单链表
,用于存储逻辑关系为 「一对一」 的数据。
我们知道,使用顺序表(底层实现靠数组)时,需要提前申请一定大小的存储空间,这块存储空间的物理地址是连续的,如下图所示。
链表则完全不同,使用链表存储数据时,是随用随申请,因此数据的存储位置是相互分离的,换句话说,数据的存储位置是随机的。
我们看到,上图根本无法体现出各数据之间的逻辑关系。对此,链表的解决方案是,每个数据元素在存储时都配备一个指针,用于指向自己的直接后继元素,如下图所示。
数据元素随机存储,并通过指针表示数据之间逻辑关系的存储结构就是链式存储结构。
链表的节点
链表中每个数据的存储都由以下两部分组成:
- 数据元素本身,其所在的区域称为数据域;
- 指向直接后继元素的指针,所在的区域称为指针域;
链表中存储各数据元素的结构如下图所示:
上图所示的结构在链表中称为节点。也就是说,链表实际存储的是一个一个的节点,真正的数据元素包含在这些节点中
:
头节点、头指针和首元节点
其实,一个完整的链表需要由以下几部分构成:
-
头指针
:一个普通的指针,它的特点是永远指向链表第一个节点的位置。很明显,头指针用于指明链表的位置,便于后期找到链表并使用表中的数据; -
节点
:链表中的节点又细分为头节点
、首元节点
和其他节点
:-
头节点
:其实就是一个不存任何数据的空节点,通常作为链表的第一个节点。对于链表来说,头节点不是必须的,它的作用只是为了方便解决某些实际问题; -
首元节点
:由于头节点(也就是空节点)的缘故,链表中称第一个存有数据的节点为首元节点。首元节点只是对链表中第一个存有数据节点的一个称谓,没有实际意义; -
其他节点
:链表中其他的节点;
-
一个存储 [1, 2, 3]
的完整链表结构如图所示:
链表中有头节点时,头指针指向头节点;反之,若链表中没有头节点,则头指针指向首元节点。
链表的初始化
我们设计的链表包含两个类:
-
Node
类用来表示节点; -
LinkedList
类提供了插入的节点、删除节点、显示列表元素的方法,以及其他辅助方法。
Node
类包含两个属性,element
和 next
。
// Node 类 class Node { constructor(element) { this.element = element; // element 用来保存节点上的数据 this.next = null; // next 用来保存指向下一节点的指针 } }
LinkedList
类提供了对链表进行操作的方法。链表只有一个属性,那就是使用一个 Node
对象来保存该链表的头节点。
function LinkedList() { // head 节点的 next 属性被初始化为 null,当有新元素插入时,next 会指向新的元素 this.head = new Node('head'); this.find = find; this.insert = insert; this.findPrevious = findPrevious; this.remove = remove; this.display = display; }
链表插入元素
同顺序表一样,向链表中增添元素,根据添加位置不同,可分为以下 3
种情况:
- 插入到链表的头部(头节点之后),作为首元节点;
- 插入到链表中间的某个位置;
- 插入到链表的最末端,作为链表中最后一个数据元素;
虽然新元素的插入位置不固定,但是链表插入元素的思想是固定的,只需做以下两步操作,即可将新元素插入到指定的位置:
- 将新节点的
next
指针指向插入位置后的节点; - 将插入位置前节点的
next
指针指向插入节点;
例如,我们在链表 [1, 2, 3, 4]
的基础上分别实现在头部、中间部位、尾部插入新元素 5
,其实现过程如下图所示:
注意
:链表插入元素的操作必须是先步骤1
,再步骤2
;反之,若先执行步骤2
,除非再添加一个指针,作为插入位置后续链表的头指针,否则会导致插入位置后的这部分链表丢失,无法再实现步骤1
。
创建一个辅助方法 find()
,该方法遍历链表,查找给定数据。
find()
方法实现:
function find(item) { var currNode = this.head; // 创建一个新节点 while (currNode.element != item) { // 如果当前节点数据不符合我们要找的节点 currNode = currNode.next; // 当前节点移动到一下节点 } return currNode; }
一旦找到 给定
的节点,就可以将新节点插入链表了。首先,将新节点的 next
指针指向 给定
节点 next
指向的节点。然后设置 给定
节点的 next
属性指向新节点。
insert()
方法的定义如下:
function insert(newElement, item) { var newNode = new Node(newElement); var current = this.find(item); // 向链表插入节点 newNode newNode.next = current.next; // 将新节点的 next 指针指向插入位置后的节点 (步骤 1) current.next = newNode; // 设置插入位置前的 next 指针指向新节点(步骤2) }
现在已经可以开始测试我们的链表实现了。然而在测试之前,先来定义一个 display()
方法,该方法用来显示链表中的元素:
function display() { var currNode = this.head; while(!(currNode.next == null)) { // 当当前节点的 next 指针为 null 时 循环结束 //为了不显示头节点,程序只访问当前节点的下一个节点中保存的数据 console.log(chrrNode.next.element); currNode = currNode.next; } }
测试程序:
function Node(element) { this.element = element; this.next = null; } function LinkedList() { this.head = new Node('head'); this.find = find; this.insert = insert; this.findPrevious = findPrevious; this.remove = remove; this.display = display; } function find(item) { var currNode= this.head; while(currNode.element != item) { currNode = currNode.next; } return currNode; } function insert(newElement, item) { var newNode = new Node(newElement); var current = this.find(item); newNode.next = current.next; current.next = newNode; } function findPrevious() {} function remove() {} function display() { var currNode = this.head; while(!(currNode.next == null)) { console.log(currNode.next.element) currNode = currNode.next; } } var list = new LinkedList(); list.insert(1, 'head') list.insert(2, 1) list.insert(3, 2) list.insert(4, 3) list.display()
程序运行结果:
1 2 3 4
链表删除元素
从链表中删除指定数据元素时,需要进行以下 2
步操作:
- 需要先找到待删除节点前面的节点
直接前驱节点
; - 找到这个节点后,修改它的
next
指针,使其不再指向待删除节点;
从链表中删除节点时,需要先找到待删除节点的直接前驱节点
。找到这个节点后,修改它的 next
指针,我们可以定义一个方法 findPrevious()
,来做这件事。
findPrevious()
方法遍历链表中的元素,检查每一个节点的 直接后继节点
中是否存储着待删除数据。如果找到,返回该节点(待删除节点的直接前驱节点
)。
function findPrevious(item) { var currNode = this.head; while(!(currNode.next == null) && currNode.next.element != item) { currNode = currNode.next; } return currNode; }
删除节点的原理很简单,找到该节点的直接前驱节点 prevNode
后,修改它的 next
指针:
prevNode.next = prevNode.next.next;
remove()
方法的 js
实现:
function remove(item) { var prevNode = this.findPrevious(item); if(!(prevNode.next == null)) { prevNode.next = prevNode.next.next; } }
测试程序:
... var list = new LinkedList(); list.insert(1, 'head') list.insert(2, 1) list.insert(3, 2) list.insert(4, 3) list.display() list.remove(2) list.display()
程序运行结果:
// 没调用 list.remove(2) 之前 1 2 3 4 // 调用list.remove(2) 1 3 4
链表更改节点
更新链表中的元素,只需通过遍历找到存储此元素的节点,对节点中的数据域做更改操作即可。
function change(index, newElement) { var currNode = this.head; for(var i = 0; i <= index; i++) { currNode = currNode.next; if (currNode == null) { throw new Error('更新位置无效'); return; } } currNode.element = newElement; return currNode; }
最后给出 js
实现的拥有基本操作 增删改查
的链表完整代码:
class Node { constructor(element) { this.element = element; this.next = null; } } class LinkedList { constructor() { this.head = new Node('head'); } // 链表查找元素 find(item) { var currNode= this.head; while(currNode.element != item) { currNode = currNode.next; } return currNode; } // 链表添加元素 insert(newElement, item) { var newNode = new Node(newElement); var current = this.find(item); newNode.next = current.next; current.next = newNode; } // 链表查找直接前驱节点(辅助方法) findPrevious(item) { var currNode = this.head; while(!(currNode.next == null) && currNode.next.element != item) { currNode = currNode.next; } return currNode; } // 链表删除节点 remove(item) { var prevNode = this.findPrevious(item); if(!(prevNode.next == null)) { prevNode.next = prevNode.next.next; } } // 链表更改节点 change(index, newElement) { var currNode = this.head; for(var i = 0; i <= index; i++) { currNode = currNode.next; if (currNode == null) { throw new Error('更新位置无效'); return; } } currNode.element = newElement; return currNode; } display() { var currNode = this.head; while(!(currNode.next == null)) { console.log(currNode.next.element) currNode = currNode.next; } } } var list = new LinkedList(); list.insert(1, 'head') list.insert(2, 1) list.insert(3, 2) list.insert(4, 3) console.log('初始化链表:') list.display() // 1, 2, 3, 4 list.remove(2) console.log('删除数据为 2 的节点: ') list.display() // 1, 3, 4 list.change(2, 6) console.log('将下标为 2 的 节点数据更改为 6:') list.display() // 1, 3, 6
整体程序运行结果:
初始化链表: 1 2 3 4 删除数据为 2 的节点: 1 3 4 将下标为 2 的 节点数据更改为 6: 1 3 6
这篇关于JavaScript - 数据结构详解(一)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-30毕设私活神器
- 2024-05-30html
- 2024-05-09一定要避坑:关于微信H5分享,温馨提示你不要再踩坑了!!!
- 2024-05-09本地项目放到公网访问!炒鸡煎蛋!
- 2024-04-07金融企业区域集中库的设计构想和测试验证
- 2024-03-11前端CSS的工程化——掌握Sass这四大特性就够了
- 2024-02-21h5关联css样式(html怎么和css关联)-icode9专业技术文章分享
- 2024-02-07Firefox禁止远程字体加速网页加载及图标字体补充安装
- 2024-02-07一个菜鸡前端的3年总结-「2023」
- 2024-01-18最火前端Web组态软件(可视化)