做前端的同学不少都是自学成才或者半路出家,计算机基础的知识比较薄弱,尤其是数据结构和算法这块,所以今天整理了一下常见的数据结构和对应的Javascript的实现,希望能帮助大家完善这方面的知识体系。
创新互联"三网合一"的企业建站思路。企业可建设拥有电脑版、微信版、手机版的企业网站。实现跨屏营销,产品发布一步更新,电脑网络+移动网络一网打尽,满足企业的营销需求!创新互联具备承接各种类型的成都网站制作、成都做网站、外贸营销网站建设项目的能力。经过十多年的努力的开拓,为不同行业的企事业单位提供了优质的服务,并获得了客户的一致好评。
1. Stack(栈)
Stack的特点是后进先出(last in first out)。生活中常见的Stack的例子比如一摞书,你最后放上去的那本你之后会最先拿走;又比如浏览器的访问历史,当点击返回按钮,最后访问的网站最先从历史记录中弹出。
Javascript的Array天生具备了Stack的特性,但我们也可以从头实现一个 Stack类:
- function Stack() {
- this.count = 0;
- this.storage = {};
- this.push = function (value) {
- this.storage[this.count] = value;
- this.count++;
- }
- this.pop = function () {
- if (this.count === 0) {
- return undefined;
- }
- this.count--;
- var result = this.storage[this.count];
- delete this.storage[this.count];
- return result;
- }
- this.peek = function () {
- return this.storage[this.count - 1];
- }
- this.size = function () {
- return this.count;
- }
- }
2. Queue(队列)
Queue和Stack有一些类似,不同的是Stack是先进后出,而Queue是先进先出。Queue在生活中的例子比如排队上公交,排在第一个的总是最先上车;又比如打印机的打印队列,排在前面的最先打印。
Javascript中的Array已经具备了Queue的一些特性,所以我们可以借助Array实现一个Queue类型:
- function Queue() {
- var collection = [];
- this.print = function () {
- console.log(collection);
- }
- this.enqueue = function (element) {
- collection.push(element);
- }
- this.dequeue = function () {
- return collection.shift();
- }
- this.front = function () {
- return collection[0];
- }
- this.isEmpty = function () {
- return collection.length === 0;
- }
- this.size = function () {
- return collection.length;
- }
- }
Priority Queue(优先队列)
Queue还有个升级版本,给每个元素赋予优先级,优先级高的元素入列时将排到低优先级元素之前。区别主要是enqueue方法的实现:
- function PriorityQueue() {
- ...
- this.enqueue = function (element) {
- if (this.isEmpty()) {
- collection.push(element);
- } else {
- var added = false;
- for (var i = 0; i < collection.length; i++) {
- if (element[1] < collection[i][1]) {
- collection.splice(i, 0, element);
- added = true;
- break;
- }
- }
- if (!added) {
- collection.push(element);
- }
- }
- }
- }
测试一下:
- var pQ = new PriorityQueue();
- pQ.enqueue(['gannicus', 3]);
- pQ.enqueue(['spartacus', 1]);
- pQ.enqueue(['crixus', 2]);
- pQ.enqueue(['oenomaus', 4]);
- pQ.print();
结果:
- [
- [ 'spartacus', 1 ],
- [ 'crixus', 2 ],
- [ 'gannicus', 3 ],
- [ 'oenomaus', 4 ]
- ]
3. Linked List(链表)
顾名思义,链表是一种链式数据结构,链上的每个节点包含两种信息:节点本身的数据和指向下一个节点的指针。链表和传统的数组都是线性的数据结构,存储的都是一个序列的数据,但也有很多区别,如下表:
一个单向链表通常具有以下方法:
单向链表的Javascript实现:
- /**
- * 链表中的节点
- */
- function Node(element) {
- // 节点中的数据
- this.element = element;
- // 指向下一个节点的指针
- this.next = null;
- }
- function LinkedList() {
- var length = 0;
- var head = null;
- this.size = function () {
- return length;
- }
- this.head = function () {
- return head;
- }
- this.add = function (element) {
- var node = new Node(element);
- if (head == null) {
- head = node;
- } else {
- var currentNode = head;
- while (currentNode.next) {
- currentNode = currentNode.next;
- }
- currentNode.next = node;
- }
- length++;
- }
- this.remove = function (element) {
- var currentNode = head;
- var previousNode;
- if (currentNode.element === element) {
- head = currentNode.next;
- } else {
- while (currentNode.element !== element) {
- previousNode = currentNode;
- currentNode = currentNode.next;
- }
- previousNode.next = currentNode.next;
- }
- length--;
- }
- this.isEmpty = function () {
- return length === 0;
- }
- this.indexOf = function (element) {
- var currentNode = head;
- var index = -1;
- while (currentNode) {
- index++;
- if (currentNode.element === element) {
- return index;
- }
- currentNode = currentNode.next;
- }
- return -1;
- }
- this.elementAt = function (index) {
- var currentNode = head;
- var count = 0;
- while (count < index) {
- count++;
- currentNode = currentNode.next;
- }
- return currentNode.element;
- }
- this.addAt = function (index, element) {
- var node = new Node(element);
- var currentNode = head;
- var previousNode;
- var currentIndex = 0;
- if (index > length) {
- return false;
- }
- if (index === 0) {
- node.next = currentNode;
- head = node;
- } else {
- while (currentIndex < index) {
- currentIndex++;
- previousNode = currentNode;
- currentNode = currentNode.next;
- }
- node.next = currentNode;
- previousNode.next = node;
- }
- length++;
- }
- this.removeAt = function (index) {
- var currentNode = head;
- var previousNode;
- var currentIndex = 0;
- if (index < 0 || index >= length) {
- return null;
- }
- if (index === 0) {
- head = currentIndex.next;
- } else {
- while (currentIndex < index) {
- currentIndex++;
- previousNode = currentNode;
- currentNode = currentNode.next;
- }
- previousNode.next = currentNode.next;
- }
- length--;
- return currentNode.element;
- }
- }
4. Set(集合)
集合是数学中的一个基本概念,表示具有某种特性的对象汇总成的集体。在ES6中也引入了集合类型Set,Set和Array有一定程度的相似,不同的是Set中不允许出现重复的元素而且是无序的。
一个典型的Set应该具有以下方法:
使用Javascript可以将Set进行如下实现,为了区别于ES6中的Set命名为MySet:
- function MySet() {
- var collection = [];
- this.has = function (element) {
- return (collection.indexOf(element) !== -1);
- }
- this.values = function () {
- return collection;
- }
- this.size = function () {
- return collection.length;
- }
- this.add = function (element) {
- if (!this.has(element)) {
- collection.push(element);
- return true;
- }
- return false;
- }
- this.remove = function (element) {
- if (this.has(element)) {
- index = collection.indexOf(element);
- collection.splice(index, 1);
- return true;
- }
- return false;
- }
- this.union = function (otherSet) {
- var unionSet = new MySet();
- var firstSet = this.values();
- var secondSet = otherSet.values();
- firstSet.forEach(function (e) {
- unionSet.add(e);
- });
- secondSet.forEach(function (e) {
- unionSet.add(e);
- });
- return unionSet;
- }
- this.intersection = function (otherSet) {
- var intersectionSet = new MySet();
- var firstSet = this.values();
- firstSet.forEach(function (e) {
- if (otherSet.has(e)) {
- intersectionSet.add(e);
- }
- });
- return intersectionSet;
- }
- this.difference = function (otherSet) {
- var differenceSet = new MySet();
- var firstSet = this.values();
- firstSet.forEach(function (e) {
- if (!otherSet.has(e)) {
- differenceSet.add(e);
- }
- });
- return differenceSet;
- }
- this.subset = function (otherSet) {
- var firstSet = this.values();
- return firstSet.every(function (value) {
- return otherSet.has(value);
- });
- }
- }
5. Hash Table(哈希表/散列表)
Hash Table是一种用于存储键值对(key value pair)的数据结构,因为Hash Table根据key查询value的速度很快,所以它常用于实现Map、Dictinary、Object等数据结构。如上图所示,Hash Table内部使用一个hash函数将传入的键转换成一串数字,而这串数字将作为键值对实际的key,通过这个key查询对应的value非常快,时间复杂度将达到O(1)。Hash函数要求相同输入对应的输出必须相等,而不同输入对应的输出必须不等,相当于对每对数据打上唯一的指纹。
一个Hash Table通常具有下列方法:
一个简易版本的Hash Table的Javascript实现:
- function hash(string, max) {
- var hash = 0;
- for (var i = 0; i < string.length; i++) {
- hash += string.charCodeAt(i);
- }
- return hash % max;
- }
- function HashTable() {
- let storage = [];
- const storageLimit = 4;
- this.add = function (key, value) {
- var index = hash(key, storageLimit);
- if (storage[index] === undefined) {
- storage[index] = [
- [key, value]
- ];
- } else {
- var inserted = false;
- for (var i = 0; i < storage[index].length; i++) {
- if (storage[index][i][0] === key) {
- storage[index][i][1] = value;
- inserted = true;
- }
- }
- if (inserted === false) {
- storage[index].push([key, value]);
- }
- }
- }
- this.remove = function (key) {
- var index = hash(key, storageLimit);
- if (storage[index].length === 1 && storage[index][0][0] === key) {
- delete storage[index];
- } else {
- for (var i = 0; i < storage[index]; i++) {
- if (storage[index][i][0] === key) {
- delete storage[index][i];
- }
- }
- }
- }
- this.lookup = function (key) {
- var index = hash(key, storageLimit);
- if (storage[index] === undefined) {
- return undefined;
- } else {
- for (var i = 0; i < storage[index].length; i++) {
- if (storage[index][i][0] === key) {
- return storage[index][i][1];
- }
- }
- }
- }
- }
6. Tree(树)
顾名思义,Tree的数据结构和自然界中的树极其相似,有根、树枝、叶子,如上图所示。Tree是一种多层数据结构,与Array、Stack、Queue相比是一种非线性的数据结构,在进行插入和搜索操作时很高效。在描述一个Tree时经常会用到下列概念:
我们以二叉查找树为例,展示树在Javascript中的实现。在二叉查找树中,即每个节点最多只有两个子节点,而左侧子节点小于当前节点,而右侧子节点大于当前节点,如图所示:
一个二叉查找树应该具有以下常用方法:
以下是二叉查找树的Javascript实现:
- class Node {
- constructor(data, left = null, right = null) {
- this.data = data;
- this.left = left;
- this.right = right;
- }
- }
- class BST {
- constructor() {
- this.root = null;
- }
- add(data) {
- const node = this.root;
- if (node === null) {
- this.root = new Node(data);
- return;
- } else {
- const searchTree = function (node) {
- if (data < node.data) {
- if (node.left === null) {
- node.left = new Node(data);
- return;
- } else if (node.left !== null) {
- return searchTree(node.left);
- }
- } else if (data > node.data) {
- if (node.right === null) {
- node.right = new Node(data);
- return;
- } else if (node.right !== null) {
- return searchTree(node.right);
- }
- } else {
- return null;
- }
- };
- return searchTree(node);
- }
- }
- findMin() {
- let current = this.root;
- while (current.left !== null) {
- current = current.left;
- }
- return current.data;
- }
- findMax() {
- let current = this.root;
- while (current.right !== null) {
- current = current.right;
- }
- return current.data;
- }
- find(data) {
- let current = this.root;
- while (current.data !== data) {
- if (data < current.data) {
- current = current.left
- } else {
- current = current.right;
- }
- if (current === null) {
- return null;
- }
- }
- return current;
- }
- isPresent(data) {
- let current = this.root;
- while (current) {
- if (data === current.data) {
- return true;
- }
- if (data < current.data) {
- current = current.left;
- } else {
- current = current.right;
- }
- }
- return false;
- }
- remove(data) {
- const removeNode = function (node, data) {
- if (node == null) {
- return null;
- }
- if (data == node.data) {
- // node没有子节点
- if (node.left == null && node.right == null) {
- return null;
- }
- // node没有左侧子节点
- if (node.left == null) {
- return node.right;
- }
- // node没有右侧子节点
- if (node.right == null) {
- return node.left;
- }
- // node有两个子节点
- var tempNode = node.right;
- while (tempNode.left !== null) {
- tempNode = tempNode.left;
- }
- node.data = tempNode.data;
- node.right = removeNode(node.right, tempNode.data);
- return node;
- } else if (data < node.data) {
- node.left = removeNode(node.left, data);
- return node;
- } else {
- node.right = removeNode(node.right, data);
- return node;
- }
- }
- this.root = removeNode(this.root, data);
- }
- }
测试一下:
- const bst = new BST();
- bst.add(4);
- bst.add(2);
- bst.add(6);
- bst.add(1);
- bst.add(3);
- bst.add(5);
- bst.add(7);
- bst.remove(4);
- console.log(bst.findMin());
- console.log(bst.findMax());
- bst.remove(7);
- console.log(bst.findMax());
- console.log(bst.isPresent(4));
打印结果:
- 1
- 7
- 6
- false
7. Trie(字典树,读音同try)
Trie也可以叫做Prefix Tree(前缀树),也是一种搜索树。Trie分步骤存储数据,树中的每个节点代表一个步骤,trie常用于存储单词以便快速查找,比如实现单词的自动完成功能。 Trie中的每个节点都包含一个单词的字母,跟着树的分支可以可以拼写出一个完整的单词,每个节点还包含一个布尔值表示该节点是否是单词的最后一个字母。
Trie一般有以下方法:
- /**
- * Trie的节点
- */
- function Node() {
- this.keys = new Map();
- this.end = false;
- this.setEnd = function () {
- this.end = true;
- };
- this.isEnd = function () {
- return this.end;
- }
- }
- function Trie() {
- this.root = new Node();
- this.add = function (input, node = this.root) {
- if (input.length === 0) {
- node.setEnd();
- return;
- } else if (!node.keys.has(input[0])) {
- node.keys.set(input[0], new Node());
- return this.add(input.substr(1), node.keys.get(input[0]));
- } else {
- return this.add(input.substr(1), node.keys.get(input[0]));
- }
- }
- this.isWord = function (word) {
- let node = this.root;
- while (word.length > 1) {
- if (!node.keys.has(word[0])) {
- return false;
- } else {
- node = node.keys.get(word[0]);
- word = word.substr(1);
- }
- }
- return (node.keys.has(word) && node.keys.get(word).isEnd()) ? true : false;
- }
- this.print = function () {
- let words = new Array();
- let search = function (node = this.root, string) {
- if (node.keys.size != 0) {
- for (let letter of node.keys.keys()) {
- search(node.keys.get(letter), string.concat(letter));
- }
- if (node.isEnd()) {
- words.push(string);
- &nbs
标题名称:常见数据结构和Javascript实现总结
网页网址:http://www.stwzsj.com/qtweb/news2/12602.html网站建设、网络推广公司-创新互联,是专注品牌与效果的网站制作,网络营销seo公司;服务项目有等
声明:本网站发布的内容(图片、视频和文字)以用户投稿、用户转载内容为主,如果涉及侵权请尽快告知,我们将会在第一时间删除。文章观点不代表本网站立场,如需处理请联系客服。电话:028-86922220;邮箱:631063699@qq.com。内容未经允许不得转载,或转载时需注明来源: 创新互联