Javascript Data Structure 1.0.6 beta

• 简单介绍
• 简单使用
• leetCode刷题辅助函数
  • 1. 链表
  • 2. 二叉树
• 数据结构类的使用
  • 二叉搜索树
  • 字典
  • 哈希表
  • 单向链表
  • 集合
  • 栈
  • 最小栈
  • 队列
  • 优先队列
  • 排序
• License

简单介绍

This NPM package includes common data structures encapsulated in JS and some auxiliary functions that display linked lists and binary trees in JS language.

NPM库功能描述

这个NPM包括了用JS封装常见的数据结构以及在JS语言中将链表和二叉树展示的辅助函数

• NPM中的类名

类名	功能
BinaryTree	二叉搜索树
Dictionary	字典
HashMap	哈希表
LinkedList	单向链表
MinStack	最小栈
PriorityQueue	优先队列
Queue	队列
MySet	集合
Sort	排序
Stack	栈
BinaryTreeHelper	辅助JS刷leetcode的二叉树题目
LinkedListHelper	辅助JS刷leetcode的链表题目

简单使用

• 安装NPM

npm i @karl_fang/data-structure

• 卸载NPM

npm uninstall @karl_fang/data-structure

• 引入使用

1. Vue中引入

<script>
// HelloWorld.vue
import { LinkedListHelper } from '@karl_fang/data-structure';
export default {
  name: "HelloWorld",
  props: {
    msg: String,
  },
  mounted() {
    let list = new LinkedListHelper([3, 5, 8, 1, 2]);
    list.toString(); // 3 --> 5 --> 8 --> 1 --> 2
  },
};
</script>

2. 一般JS文件中引入

import { LinkedListHelper } from '@karl_fang/data-structure';
let list = new LinkedListHelper([3, 5, 8, 1, 2]);
list.toString();
// 3 --> 5 --> 8 --> 1 --> 2

记得在package.json文件中加入"type": "module"，否则不能使用import关键字

leetCode刷题辅助函数

1. 链表

• 类名：LinkedListHelper

1.1 constructor

参数：

array：{number[] | string[]} 想要转成链表的元素所组成的数组

...args： {number}【可选】环形链表的入环点的下标，范围是[0, list.length)

1.2 相关函数

函数	参数	返回值	功能
arrayToLinkedList(array)	{number[] | string[]} array 将链表元素以数组形式传入	{ListNode} 链表的头节点	将数组转化成链表
toString()	{void} 无需传入参数	{void} 无返回值	将环形链表或普通链表打印
getNthNode()	{number} 链表第n个节点 【可选】默认为头节点(n=1)	{treeNode} 链表的头节点	获得链表的头节点

小提示💡

• getNthNode如果n为正整数：大于链表长度返回null
• getNthNode如果n为0：返回头节点
• getNthNode如果n为负整数：返回倒数第n个节点，如果n的绝对值大于链表的长度，则返回头节点

1.3 arrayToLinkedList

功能： 将数组转化成链表

参数：

array：{number[] | string[] | boolean[]} 含有原始值的数组

返回值：{ListNode} 链表的头

例子：

import { LinkedListHelper } from '@karl_fang/data-structure';
let list1 = new LinkedListHelper([2, 4, 6, 5, 3]); // 普通链表
list1.toString(); 
// 2 --> 4 --> 6 --> 5 --> 3
let list2 = new LinkedListHelper([2, 4, 6, 5, 3], 2); // 环形链表
list2.toString(); 
// 2 --> 4 --> 6 --> 5 --> 3 --> [Circular *3 from index=2] 6...
console.log(list2.getNthNode());

2. 二叉树

• 类名：BinaryTreeHelper

2.1 constructor

参数：

array：{number[] | string[]} 想要转成二叉树的元素所组成的数组

必须遵守💡

数组的个数必须满足2^{depth+1}-1，其中depth是二叉树的层数，根节点层数为0，如果没有值用null代替

2.2 相关函数

函数	参数	返回值	功能
arrayToBinaryTree(array)	{number[] |string[] | boolean[]} array 将二叉树元素以数组形式传入	{TreeNode} 二叉树的root节点	将数组转化为二叉树
logTree(initDepth = 0)	{number} initDepth 【可选】开始展示的层数	{void} 无返回值	打印树结构
getRoot()	{void} 无需传入参数	{TreeNode} 二叉树的root节点	获取二叉树根节点
inOrderTraversal()	{void} 无需传入参数	{void} 无返回值	中序遍历
preOrderTraversal()	{void} 无需传入参数	{void} 无返回值	先序遍历
postOrderTraversal()	{void} 无需传入参数	{void} 无返回值	后序遍历
LogMyTree(root, initDepth = 0)	{TreeNode} root 二叉树的根节点，{number} initDepth 【可选】开始展示的层数	{void} 无返回值	打印树结构 (静态方法)

2.3 arrayToBinaryTree

功能： 将数组转化成二叉树

参数：

array：{number[] | string[] | boolean[]} 含有原始值的数组

返回值：{TreeNode} 二叉树的root节点

例子：

import { BinaryTreeHelper } from '@karl_fang/data-structure';
let bst = new BinaryTreeHelper([1, 2, null, 6, 5, null, null]);

2.4 logTree

功能： 打印树结构

参数：

initDepth：{number} 可选 从第initDepth层开始展示的二叉树

小提示💡

initDepth范围：[0, 层数]，层数的计算root算第0层

返回值：{void} 无返回值

例子：

import { BinaryTreeHelper } from '@karl_fang/data-structure';
let bst = new BinaryTreeHelper([1, 2, null, 6, 5, 7, 9]);
bst.logTree();
/*
Binary Tree Map(Parent Node / subtree)
  第1层
    (null / root) 1
  第2层
    (1 / left) 2
  第3层
    (2 / left) 6
    (2 / right) 5
*/
bst.logTree(2);
/*
Binary Tree Map(Parent Node / subtree)
  第3层
    (2 / left) 6
    (2 / right) 5
*/

2.5 LogMyTree

小提示💡

功能与logTree一样，只是为了方便打印非构造函数生成的二叉树实例。

数据结构类的使用

二叉搜索树

• 类名：BinaryTree

• 相关函数

函数	参数	返回值	功能
insert(val)	{number} val 节点的值	{void} 无返回值	插入树的节点
getMin()	{void} 无需传入参数	{number} 最小值	获取BST中的最小值
getMax()	{void} 无需传入参数	{number} 最大值	获取BST中的最大值
has(val)	{number} val 需要判断的数字	{boolean} 存在返回true，否则返回false	判断指定的val值是否存在
remove(val)	{number} val 指定节点的值	{void} 无返回值	删除指定值的节点
inOrderTraversal()	{void} 无需传入参数	{void} 无返回值	中序遍历
preOrderTraversal()	{void} 无需传入参数	{void} 无返回值	先序遍历
postOrderTraversal()	{void} 无需传入参数	{void} 无返回值	后序遍历
toString(initDepth = 0)	{number} initDepth 【可选】 初始树的深度，默认为0，即从root开始	{void} 无返回值	打印树结构

• 例子：

import { BinaryTree } from "@karl_fang/data-structure";
let bst = new BinaryTree();
bst.insert(10);
bst.insert(5);
bst.insert(17);
bst.insert(7);
bst.insert(14);
bst.insert(3);
bst.insert(16);
bst.insert(1);
bst.toString();
console.log("------------------------");
console.log("max:", bst.getMax());
console.log("min:", bst.getMin());
console.log("------------------------");
console.log(bst.has(1));
console.log(bst.has(2));
console.log(bst.has(3));
console.log(bst.has(4));
console.log(bst.has(8));
console.log(bst.has(12));
console.log(bst.has(16));
console.log("------------------------");
bst.remove(1);
bst.remove(5);
bst.remove(17);
bst.remove(10);
bst.toString();

字典

• 类名：Dictionary

• 相关函数

函数	参数	返回值	功能
has(key)	{any} key 键	@returns {boolean}	判断是否存在键值
set(key, val)	{any} key 键，推荐number或string类型；{any} val 值	{void} 无返回值	增加 (相同键名则会后者被覆盖)
find(key)	{any} key 键	{any} 返回对应键的值	查找指定键的值
remove(key)	{any} key 键	{void} 无返回值	删除指定键的值
length()	{void} 无需传入参数	{number} 返回字典中键值对的个数	获取字典中键值对的个数
toString()	{void} 无需传入参数	{void} 无返回值	展示字典的键值对
clear()	{void} 无需传入参数	{void} 无返回值	清空字典
sort()	{void} 无需传入参数	{void} 无返回值	按键值排序

• 例子：

import { Dictionary } from "@karl_fang/data-structure";
let dictionary = new Dictionary([{ key: 2, val: 1 }, { key: 'hahaha', val: 'xixixi' }]);
dictionary.toString();
dictionary.set(666, "999");
dictionary.set("key", "value");
dictionary.set(666, "888");
dictionary.set([1,2,3], true);
dictionary.toString();
console.log(dictionary.has(666));
console.log(dictionary.has("keys"));
console.log(dictionary.has("key"));
console.log(dictionary.find("key"));
console.log(dictionary.find("keys"));
dictionary.remove("key");
dictionary.remove("keys");
dictionary.toString();
console.log(dictionary.length());
dictionary.sort();
dictionary.clear();
dictionary.toString();
console.log(dictionary.length());

哈希表

• 类名：HashMap
• 相关函数

函数	参数	返回值	功能
add(key, value)	{any} key 键，推荐number或string类型；{any} value 值	{void} 无返回值	增加 (如果不存在则添加，如果存在则把值进行修改)
getValue(key)	{any} key 键	{any} 返回对应键的值	根据属性名获取键值对
update(key, val)	{any} key 键；{any} val 值	{void} 无返回值	更新键值对
remove(key)	{any} key 键	{void} 无返回值	根据属性名删除键值对
toString()	{void} 无需传入参数	{void} 无返回值	展示哈希表的键值对
length()	{void} 无需传入参数	{number} 返回哈希表中键值对的个数	获取哈希表中键值对的个数
isEmpty()	{void} 无需传入参数	{boolean} 是否为空	判断哈希表是否为空

• 例子：

import { HashMap } from "@karl_fang/data-structure";
let map = new HashMap();
map.add("666", "hahaha");
map.add("6", true);
map.add("iloveyou", "zy");
map.add("test", 666);
map.add("hashMap", [1, 2, 3]);
map.toString();
map.add("hashMap", [1, 2, 3, 4]);
map.add("test", "cover");
map.toString();
console.log("------------------------");
console.log(map.getValue("test"));
console.log(map.getValue("test1"));
console.log(map.getValue("iloveyou"));
console.log("------------------------");
map.update("66", "hahaha");
map.update("6", "9")
console.log(map.getValue("6"));
console.log("------------------------");
console.log(map.getValue("test"));
map.remove("test");
console.log(map.getValue("test"));
map.toString();
console.log(map.length());
console.log(map.isEmpty());

单向链表

• 类名：LinkedList
• 相关函数

函数	参数	返回值	功能
append(val)	{any} val 添加的元素值，推荐number或string类型	{void} 无返回值	向链表尾部添加节点
insert(position, val)	{number} position 插入的下表位置；{number | string} val 插入的值	{void} 无返回值	在指定下标处插入节点
getValByPosition(position)	{number} position 要获取元素的下标	{number/string} 指定下标元素的值	获取指定下标元素的值
indexOf(val)	{number | string} val 待查找的值	{number} 找到返回下标，找不到返回-1	查找指定元素对应的第一个下标
has(key)	{number | string} key 待查找的键	{boolean} 存在返回true，不存在返回false	查找指定键是否存在
getValue(key)	{number | string} key 待查找的键	{number/string} 存在返回值，否则返回undefined	查找指定键对应的值
updateVal(position, val)	{number} position 要更新节点的下标；{number | string} val 新值	{void} 无返回值	更新指定下标节点的值
removeByPosition(position)	{number} position 要删除的节点的下标	{void} 无返回值	删除指定下标的元素
removeByVal(val)	{number | string} val 要删除的值	{void} 无返回值	删除第一个指定元素的值
static reverseList(oldHead)	{ListNode} oldHead 需要翻转链表的头节点	{ListNode} 返回翻转后的链表的头节点	翻转链表
removeNthFromEnd(n)	{number} n 范围[0,length]	{void} 无返回值	删除倒数第n个节点(不包括head节点)
length()	{void} 无需传入参数	{number} 链表中元素个数	获取链表的元素个数(除了head节点外的个数)
getHeadNode()	{void} 无需传入参数	{ListNode} 返回链表的头节点	获取链表的头节点
toString()	{void} 无需传入参数	{void} 无返回值	将链表以字符串形式打印
static linkedListToString(head)	{ListNode} head 链表的头节点	{void} 无返回值	将链表以字符串形式打印

• 例子：

import { LinkedList } from "@karl_fang/data-structure";
let linkedlist = new LinkedList([1, 2, 3, 4, 5, 6]);
linkedlist.toString();
console.log(linkedlist.length());
linkedlist.append(7);
linkedlist.append(8);
linkedlist.toString();
console.log(linkedlist.length());
console.log("------------------------");
linkedlist.insert(0, 666);
linkedlist.insert(4, 9);
linkedlist.insert(10, 10);
linkedlist.toString();
// linkedlist.insert(12, 9); 会有报错提示
console.log("------------------------");
console.log(linkedlist.getValByPosition(0));
console.log(linkedlist.getValByPosition(3));
console.log(linkedlist.length());
console.log(linkedlist.getValByPosition(linkedlist.length()));
console.log("------------------------");
console.log(linkedlist.indexOf('head'));
console.log(linkedlist.indexOf(0));
console.log(linkedlist.indexOf(2));
console.log(linkedlist.indexOf(9));
console.log(linkedlist.indexOf(6));
console.log("------------------------");
linkedlist.updateVal(0, "newHead");
linkedlist.updateVal(3, 999);
linkedlist.updateVal(8, 888);
linkedlist.toString();
console.log("------------------------");
linkedlist.removeByPosition(1);
linkedlist.toString();
linkedlist.removeByPosition(3);
linkedlist.toString();
linkedlist.removeByPosition(7);
linkedlist.toString();
linkedlist.removeByPosition(linkedlist.length());
linkedlist.toString();
console.log("------------------------");
linkedlist.removeByVal(888);
linkedlist.removeByVal(1);
linkedlist.removeByVal(5);
linkedlist.toString();
// linkedlist.removeByVal(666);
console.log("------------------------");
console.log(LinkedList.linkedListToString(LinkedList.reverseList(linkedlist.getHeadNode())));
console.log("------------------------");
linkedlist.toString();
linkedlist.removeNthFromEnd(2);
linkedlist.toString();
console.log("------------------------");
let ll = new LinkedList();
ll.append([1, 2, 3]);
console.log(LinkedList.linkedListToString(ll.getHeadNode()));
console.log(ll.indexOf([1, 2, 3, 4]));
console.log(ll.indexOf([1, 2, 3]));
console.log("------------------------");
let lll = new LinkedList();
lll.append([1, 2]);
lll.append(["key", 666]);
lll.append(["haha", true]);
console.log(lll.has(1));
console.log(lll.has(2));
console.log(lll.has("key"));
console.log(lll.has("hahaha"));
console.log("------------------------");

集合

• 类名：MySet
• 相关函数

函数	参数	返回值	功能
type()	{void} 无需传入参数	{"string"/"number"/"both"/"none"} 集合的类型	判断集合是纯数字还是纯字符串
sort(methods)	{"desc" | "asc"} methods 排序方式 "desc"降序，"asc"升序	{Set} 排序后的集合	集合排序
add(data)	{number | string} data 要添加的值	{boolean} 是否添加成功	添加元素
remove(data)	{number | string} data 要删除的值	{boolean} 是否删除成功	删除元素
union(target)	{MySet} target 待求并集的MySet对象实例	{MySet} 并集对象集合	并集
interesct(target)	{MySet} target 待求交集的MySet对象实例	{MySet} 交集对象集合	交集
subset(target)	{MySet} target 待求子集的MySet对象实例	{boolean} 判断结果	子集
difference (smallRange, bigRange)	{MySet} smallRange 小范围的集合；{MySet} bigRange 大范围的集合	{MySet} 补集的集合	补集
toString ()	{void} 无需传入参数	{string} 集合的字符串形式	将集合以字符串展示
getSet ()	{void} 无需传入参数	{number[]/string[]} 集合的数组形式	将集合以数组展示

• 例子：

import { MySet } from '@karl_fang/data-structure';
let set = new MySet();
// let set = new MySet([1, 2, 3], [11, 12, 13]);
console.log(set.type());
set.add(1);
set.add(1);
set.add(2);
set.add(2);
set.add(3);
set.toString();
console.log("------------------------");
set.remove(4);
set.remove(1);
set.remove(2);
set.getSet();
console.log(set.type());
set.add("aaa");
console.log(set.type());
console.log("------------------------");
set.remove("aaa");
set.add(1);
set.add(2);
set.add(3);
set.add(4);
set.add(5);
set.add(6);
set.sort().toString();
console.log("---------------------");
set.union(new MySet([])).toString();
set.union(new MySet([1, 2, 3])).toString();
set.union(new MySet([1, 2, 3, 7, 8, 9])).toString();
console.log("------------------------");
set.interesct(new MySet([])).toString();
set.interesct(new MySet([1, 2, 3])).toString();
set.interesct(new MySet([1, 2, 3, 7, 8, 9])).toString();
console.log("------------------------");
console.log(set.subset(new MySet([1, 2, 3, 4, 9])));
console.log(set.subset(new MySet([1, 2, 3])));
console.log(set.subset(new MySet([1])));
console.log(set.subset(new MySet([])));
console.log("------------------------");
set.difference(set, new MySet([1, 2, 3, 4, 5, 6, 7, 8, 9, 10])).toString();
set.difference(set, new MySet([1, 2, 3, 4, 5, 6])).toString();
// set.difference(set, new MySet([1, 2, 3, 4, 5])).toString(); 会报错提示
set.getSet();

栈

• 类名：Stack
• 相关函数

函数	参数	返回值	功能
push(element)	{any} element 待被压入栈的元素所组成的数组，推荐number或string类型	{void} 无返回值	入栈
top ()	{void} 无需传入参数	{any} 栈顶元素	返回栈顶元素
pop ()	{void} 无需传入参数	{any} 栈顶元素	弹出栈顶元素
length ()	{void} 无需传入参数	{number} 栈中元素个数	返回栈的元素个数
clear ()	{void} 无需传入参数	{void} 无返回值	清空栈中所有元素
toString ()	{void} 无需传入参数	{void} 无返回值	以字符串形式打印栈中元素

• 例子：

import { Stack } from '@karl_fang/data-structure';
let stack = new Stack();
stack.push([1, 2, 3, 4]);
stack.toString();
console.log(stack.top());
console.log(stack.pop());
stack.toString();
console.log(stack.length());
stack.clear();
console.log(stack.length());
console.log("------------------------");
stack.push([1, 2, 3]);
console.log(stack.pop());
console.log(stack.pop());
console.log(stack.pop());
console.log(stack.pop());
console.log(stack.length());
stack.toString();
console.log("------------------------");
stack.push([1, 3]);
console.log(stack.length());
console.log(stack.top());

最小栈

• 类名：MinStack
• 相关函数

函数	参数	返回值	功能
push(val)	{number[]} val 需压入栈的元素数组	{void} 无返回值	压入栈
pop()	{void} 无需传入参数	{void} 无返回值	弹出栈顶元素
top()	{void} 无需传入参数	{number} 栈顶元素	获取栈顶元素
getMin()	{void} 无需传入参数	{number} 当前栈内最小值	获取当前栈内最小值
toString ()	{void} 无需传入参数	{void} 无返回值	以字符串形式打印栈中元素
length ()	{void} 无需传入参数	{number} 栈中元素个数	返回栈的元素个数
clear ()	{void} 无需传入参数	{void} 无返回值	清空栈中所有元素

• 例子：

import { MinStack } from "@karl_fang/data-structure";
let minStack = new MinStack();
minStack.push([6, 4, 2, 3, 1, 6]);
minStack.toString();
while (minStack.length()) {
  minStack.toString();
  console.log("当前栈内元素最小值为:" + minStack.getMin());
  minStack.pop();
}
minStack.push([1, 2, 3]);
console.log(minStack.top());
minStack.clear();
console.log(minStack.length());
minStack.toString();

队列

• 类名：Queue
• 相关函数

函数	参数	返回值	功能
enqueue(element)	{any} element 待被添加到队列的元素所组成的数组	{void} 无返回值	入队
dequeue()	{void} 无需传入参数	{any} 队列第一个元素	出队
front()	{void} 无需传入参数	{any} 返回队列第一个元素	查看队列第一个元素
length ()	{void} 无需传入参数	{number} 栈中元素个数	返回栈的元素个数
clear ()	{void} 无需传入参数	{void} 无返回值	清空队列中所有元素
toString ()	{void} 无需传入参数	{void} 无返回值	以字符串形式打印栈中元素

• 例子：

import { Queue } from '@karl_fang/data-structure';
let queue = new Queue();
queue.enqueue([1, 2, 3, 4]);
queue.toString();
console.log(queue.front());
console.log(queue.dequeue());
queue.toString();
console.log(queue.length());
queue.clear();
console.log(queue.length());
console.log("------------------------");
queue.enqueue([1, 2, 3]);
console.log(queue.dequeue());
console.log(queue.dequeue());
console.log(queue.dequeue());
console.log(queue.dequeue());
console.log(queue.length());
queue.toString();
console.log("------------------------");
queue.enqueue([1, 3]);
console.log(queue.length());
console.log(queue.front());

优先队列

• 类名：PriorityQueue

priority 优先队列元素的优先等级，值越大优先级越高

• 相关函数

函数	参数	返回值	功能
enqueue(element)	{any} queueNodeArray 待加入优先队列的键值对数组	{void} 无返回值	入队
dequeue()	{void} 无需传入参数	{any} 队列第一个元素	出队
front()	{void} 无需传入参数	{any} 队列第一个元素	查看队列第一个元素
length ()	{void} 无需传入参数	{number} 栈中元素个数	返回栈的元素个数
clear ()	{void} 无需传入参数	{void} 无返回值	清空队列中所有元素
toString ()	{void} 无需传入参数	{void} 无返回值	以字符串形式打印栈中元素

• 例子：

import { PriorityQueue } from '@karl_fang/data-structure';
let queue = new PriorityQueue();
queue.enqueue([{val: 'a', priority: 1}, {val: 'b', priority: 2}, {val: 'c', priority: 3}]);
queue.toString();
console.log(queue.front());
console.log(queue.dequeue());
queue.toString();
console.log(queue.length());
queue.clear();
console.log(queue.length());
console.log("------------------------");
queue.enqueue([{ val: 'aa', priority: 3 }, { val: 'ba', priority: 1 }, { val: 'ac', priority: 1 }]);
console.log(queue.dequeue());
console.log(queue.dequeue());
console.log(queue.dequeue());
console.log(queue.dequeue());
console.log(queue.length());
queue.toString();
console.log("------------------------");
queue.enqueue([{val: 666, priority: 1}, {val: 'b', priority: 2}]);
console.log(queue.length());
console.log(queue.front());

排序

• 类名：Sort
• 相关函数

函数	参数	返回值	功能
static bubbleSort (array)	{number[]} array 待排序的数组	{number[]} 排序后的数组	冒泡排序
static selectionSort (array)	{number[]} array 待排序的数组	{number[]} 排序后的数组	选择排序
static insertionSort (array)	{number[]} array 待排序的数组	{number[]} 排序后的数组	插入排序
static shellSort (array)	{number[]} array 待排序的数组	{number[]} 排序后的数组	希尔排序
static quickSort (array)	{number[]} array 待排序的数组	{number[]} 排序后的数组	快速排序

• 例子：

import { Sort } from '@karl_fang/data-structure';
let arr = [7, 3, 5, 0, 2, 1, 6, 4];
console.log(Sort.bubbleSort(arr));
console.log(Sort.selectionSort(arr));
console.log(Sort.insertionSort(arr));
console.log(Sort.shellSort(arr));
console.log(Sort.quickSort(arr));

License

MIT