数据结构对于工作中的作用可大可小，在当前前端的使用场景并没有十分广泛，但是对于一个对于开发者来说，技术不断精进是一个循序渐进的过程，所以很有必要进行学习。
js 数据结构
实现斐波那契数列
var fibonaci = [];
fibonaci[0] = 1;
fibonacip[1] = 1;
for (var i=2; i<20; i++) {
fibonaci[i] = fibonaci[i-1] + fibonaci[i-2];
}
console.log(fibonaci);
// [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765]
数组常用操作
// 初始化一个数组
var numbers = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
// 添加一个数字10到数组最后的位置
// 方式一
numbers[numbers.length] = 10;
numbers.push(11, 12);
// 在数组首位插入元素
for (var i=numbers.length; i>0; i--) {
numbers[i] = numbers[i-1];
}
numbers[0] = -1;
// -1,0,1,2,3,4,5,6,7,8,9,10,11,12,13
//通过unshift在首位插入元素
numbers.unshift(-2);
numbers.unshift(-4, -3);
// -4,-3,-2...
// 删除最后的元素
numbers.pop();
// -4,-3....12
// 删除首位元素
// -4,-3,-2...12
// -3,-2...12,undefined
for (var i=0; i<numbers.length; i++) {
numbers[i] = numbers[i+1];
}
numbers.pop();
numbers.unshift();
// 删除指定位置的元素
numbers.splice(5, 3);
// -3,-2,-1,0,1,5,...12
//指定位置插入元素
numbers.splice(5, 0, 4, 3, 2);
// 修改指定位置的元素
numbers.splice(5, 3, 'a', 'b', 'c');
栈(后进先出)
// stack
function Stack() {
// 栈中的属性
var items = [];
// 栈相关的方法
// 压栈操作
this.push = function(element) {
items.push(element);
};
// 出栈操作
this.pop = function() {
return items.pop();
};
// peek操作
this.peek = function() {
return items[items.length - 1];
};
// 判断栈中的元素是否为空
this.isEmpty = function() {
return items.length === 0;
};
// 获取栈中的个数
this.size = function() {
return items.length;
};
}
var stack = new Stack();
stack.push(6);
stack.push(5);
stack.pop();
stack.push(4);
stack.pop();
stack.push(3);
stack.pop();
console.log(stack.size());
// 十进制转二进制
function dec2bin(decNumber) {
// 定义变量
var stack = new Stack();
var remainer;
// 循环除法
while(decNumber > 0) {
remainer = decNumber % 2;
decNumber = Math.floor(decNumber / 2);
stack.push(remainer);
}
// 将数据取出
var binayrStrng = "";
while (!stack.isEmpty()) {
binayrStrng += stack.pop();
}
return binayrStrng;
}
console.log(dec2bin(10));
console.log(dec2bin(233));
队列
// 自定义队列(先进先出)
function Queue() {
var items = [];
// 队列的操作方法
// enter
this.enqueue = function(element) {
items.push(element);
};
// delete
this.dequeue = function() {
return items.shift();
};
// 查看前端的元素
this.front = function() {
return items[0];
};
// 查看队列是否为空
this.isEmpty = function() {
return items.length === 0;
};
// 查看队列中元素的个数
this.size = function() {
return items.length;
};
}
var queue = new Queue();
queue.enqueue("abc");
queue.enqueue("cba");
queue.enqueue("nba");
queue.dequeue();
console.log(queue.front());
console.log(queue.isEmpty());
console.log(queue.size());
优先队列
// 封装有限队列
function PriorityQueue() {
var items = [];
// 封装一个新的构造函数，用于保存元素和优先级
function QueueElement(element, priority) {
this.element = element;
this.priority = priority;
}
// 添加元素的方法
this.enqueue = function(element, priority) {
// 根据传入的元素，创建新的QueueElement
var queueElement = new QueueElement(element, priority);
// 获取传入元素应该放置在正确的位置上
if (this.isEmpty()) {
items.push(queueElement);
} else {
var added = false;
for (var i=0; i<items.length; i++) {
// 注意： 我们这里是数字越小，优先级越高
if (queueElement.priority < items[i].priority) {
items.splice(i, 0, queueElement);
added = true;
break;
}
}
// 遍历完所有的元素，优先级都大于新插入的元素时，就插入到最后
if (!added) {
items.push(queueElement);
}
}
};
this.dequeue = function() {
return items.shift();
};
this.front = function() {
return items[0];
};
this.isEmpty = function() {
return items.length === 0;
};
this.size = function() {
return items.length;
};
}
var pQueue = new PriorityQueue();
// 添加元素
pQueue.enqueue('abc', 10);
pQueue.enqueue('cba', 5);
pQueue.enqueue('nba', 12);
pQueue.enqueue('mba', 3);
console.log(pQueue.size());
var size = pQueue.size();
for (var i=0; i<size; i++) {
var item = pQueue.dequeue();
console.log(item.element + '-' + item.priority);
}
// mba-3
// cba-5
// abc-10
// nba-12
实现击鼓传花的函数
function passGame(nameList, num) {
// 创建队列
var queue = new Queue();
// 通过for循环，把nameList放入队列中
for (var i=0; i<nameList.length; i++) {
queue.enqueue(nameList[i]);
}
// 寻找最后剩下的人
while(queue.size() > 1) {
// 将num-1前的前端取出放在队列的后端
for (var i=0; i<num; i++) {
queue.enqueue(queue.dequeue());
}
// 将num个人，从队列中移除
queue.dequeue();
}
// 获取剩下的一个人
console.log(queue.size());
var endName = queue.dequeue();
console.log('最后留下的人: ', endName);
// 获取该人在队列中的位置
return nameList.indexOf(endName);
}
var names = ['jogh', 'jack', 'camila', 'ingrid', 'carl'];
var index = passGame(names, 7);
console.log('最终的位置: ', index);
链表
// 链表
// 封装链表的构造函数
function LinkedList() {
// 封装一个Node类，用于保存每个节点信息
function Node(element) {
this.element = element;
this.next = null;
}
// 链表中的属性
this.length = 0;
this.head = null;
// 链表尾部追加元素
LinkedList.prototype.append = function(element) {
// 根据新元素创建节点
var newNode = new Node(element);
console.log(this.head);
// 判断原来的链表是否为空
if (this.head === null) {
this.head = newNode;
} else {
// 定义变量，保存当前找到的节点
var current = this.head;
while (current.next) {
current = current.next;
}
current.next = newNode;
}
// 链表的长度增加1
this.length++;
};
// 链表的toString方法
LinkedList.prototype.toString = function() {
// 定义两个变量
var current = this.head;
var listString = "";
// 循环获取链表中所有的元素
while (current) {
listString += "," + current.element;
current = current.next;
}
// 返回最终结果
return listString.slice(1);
};
// 根据下表删除元素
LinkedList.prototype.insert = function(position, element) {
// 检测越界问题，越界插入失败
if (position < 0 || position > this.length) return false;
// 定义变量，保存信息
var newNode = new Node(element);
var current = this.head;
var previous = null,
index = 0;
// 判断是否列表是否在第一个位置插入
if (position === 0) {
newNode.next = current;
this.head = newNode;
} else {
while (index++ < position) {
previous = current;
current = current.next;
}
newNode.next = current;
previous.next = newNode;
}
this.length++;
return true;
};
// 根据位置移除节点
LinkedList.prototype.removeAt = function(position) {
// 越界移除失败，返回null
if (position < 0 || position >= this.length) return null;
// 定义变量，保存信息
var current = this.head;
var previous = null;
var index = 0;
// 判断是否是移除第一项
if (position === 0) {
this.head = current.next;
} else {
while (index++ < position) {
previous = current;
current = current.next;
}
previous.next = current.next;
}
this.length--;
// 返回移除的数据
return current.element;
};
// 根据元素获取链表中的位置
LinkedList.prototype.indexOf = function(element) {
var current = this.head,
index = 0;
// 找到元素所在的位置
while (current) {
if (current.element === element) {
return index;
}
index++;
current = current.next;
}
// 没有找到，返回-1
return -1;
};
// 根据元素删除信息
LinkedList.prototype.remove = function(element) {
var index = this.indexOf(element);
return this.removeAt(index);
};
// 判断链表是否为空
LinkedList.prototype.isEmpty = function() {
return this.length === 0;
};
// 获取链表的长度
LinkedList.prototype.size = function() {
return this.length;
};
// 获取第一个节点
LinkedList.prototype.getFirst = function() {
return this.head.element;
};
}
var list = new LinkedList();
list.append(15);
list.append(10);
list.append(20);
console.log(list);
list.insert(0, 100);
list.insert(4, 200);
list.insert(2, 300);
list.removeAt(0);
list.removeAt(1);
list.removeAt(3);
console.log(list.indexOf(15));
console.log(list.indexOf(10));
list.remove(15);
console.log(list);
console.log(list.isEmpty());
console.log(list.size());
console.log(list.getFirst());
console.log(list.toString());
// null
// Node {element: 15, next: null}
// Node {element: 15, next: Node}
// LinkedList {length: 3, head: Node}
// 0
// 1
// LinkedList {length: 2, head: Node}
// false
// 2
// 10
// 10,20
双向链表
// 创建双向链表的构造函数
function DoublyLinkedList() {
// 创建节点的构造函数
function Node(element) {
this.element = element;
this.next = null;
this.prev = null;
}
this.length = 0;
this.head = null;
this.tail = null;
// 定义相关操作方法
// 在尾部追加数据
DoublyLinkedList.prototype.append = function(element) {
// 根据元素创建节点
var newNode = new Node(element);
if (this.head === null) {
this.head = newNode;
this.tail = newNode;
} else {
this.tail.next = newNode;
newNode.prev = this.tail;
this.tail = newNode;
}
this.length++;
};
// 在任意位置插入数据
DoublyLinkedList.prototype.insert = function(position, element) {
if (position < 0 || position > this.length) return false;
var newNode = new Node(element);
if (position === 0) {
// 在第一个位置插入
if (this.head === null) {
this.head = newNode;
this.tail = newNode;
} else {
this.head.prev = newNode;
newNode.next = this.head;
this.head = newNode;
}
} else if (position === this.length) {
// 在尾部位置插入
this.tail.next = newNode;
newNode.prev = this.tail;
this.tail = newNode;
} else {
// 在中间位置插入
var index = 0;
var current = this.head;
var previous = null;
while (index++ < position) {
previous = current;
current = current.next;
}
newNode.next = current;
newNode.prev = previous;
current.prev = newNode;
previous.next = newNode;
}
this.length++;
return true;
};
// 根据位置删除对应的元素
DoublyLinkedList.prototype.removeAt = function(position) {
if (position < 0 || position >= this.length) return null;
var current = this.head;
if (position === 0) {
if (this.length === 1) {
this.head = null;
this.tail = null;
} else {
this.head = this.head.next;
this.head.prev = null;
}
} else if (position === this.length - 1) {
current = this.tail;
this.tail = this.tail.prev;
this.tail.next = null;
} else {
var index = 0;
var previous = null;
while (index++ < position) {
previous = current;
current = current.next;
}
previous.next = current.next;
current.next.prev = previous;
}
this.length--;
return current.element;
};
// 根据元素获取在链表中的位置
DoublyLinkedList.prototype.indexOf = function(element) {
var current = this.head;
var index = 0;
while (current) {
if (current.element === element) {
return index;
}
index++;
current = current.next;
}
return -1;
};
// 根据元素删除
DoublyLinkedList.prototype.remove = function(element) {
var index = this.indexOf(element);
return this.removeAt(index);
};
// 判断是否为空
DoublyLinkedList.prototype.isEmpty = function() {
return this.length === 0;
};
// 获取链表的长度
DoublyLinkedList.prototype.size = function() {
return this.length;
};
// 获取第一个元素
DoublyLinkedList.prototype.getHead = function() {
return this.head.element;
};
// 获取最后一个元素
DoublyLinkedList.prototype.getTail = function() {
return this.tail.element;
};
// 正向遍历方法
DoublyLinkedList.prototype.forwardString = function() {
var current = this.head;
var forwardStr = "";
while (current) {
forwardStr += "," + current.element;
current = current.next;
}
return forwardStr.slice(1);
};
// 反向遍历方法
DoublyLinkedList.prototype.reverseString = function() {
var current = this.tail;
var reverseStr = "";
while (current) {
reverseStr += "," + current.element;
current = current.prev;
}
return reverseStr.slice(1);
};
// 实现toString方法
DoublyLinkedList.prototype.toString = function() {
return this.forwardString();
};
}
var list = new DoublyLinkedList();
list.append("abc");
list.append("cba");
list.append("nba");
list.append("mba");
console.log(list.forwardString());
console.log(list.reverseString());
console.log(list);
list.insert(0, "100");
list.insert(2, "200");
list.insert(6, "300");
console.log(list);
console.log(list.indexOf("abc"));
console.log(list.indexOf("cba"));
console.log(list.remove("abc"));
console.log(list.getHead());
console.log(list.getTail());
console.log(list.isEmpty());
console.log(list.size());
// abc,cba,nba,mba
// mba,nba,cba,abc
// DoublyLinkedList {length: 6, head: Node, tail: Node, constructor: Object}
// DoublyLinkedList {length: 6, head: Node, tail: Node, constructor: Object}
// 1
// 3
// abc
// 100
// 300
// false
// 6
集合
// 封装集合的构造函数
function Set() {
this.items = {};
// 判断集合是否存在某个元素
Set.prototype.has = function(value) {
return this.items.hasOwnProperty(value);
};
// 向集合添加元素
Set.prototype.add = function(value) {
if (this.has(value)) return false;
this.items[value] = value;
return true;
};
// 从集合删除某个元素
Set.prototype.remove = function(value) {
if (!this.has(value)) return false;
delete this.items[value];
return true;
};
// 清空集合中的所有的元素
Set.prototype.clear = function() {
this.items = {};
};
// 获取集合的大小
Set.prototype.size = function() {
return Object.keys(this.items).length;
};
// 获取集合的所有的值
Set.prototype.values = function() {
return Object.keys(this.items);
};
// 集合的并集
Set.prototype.union = function(otherSet) {};
}
var set = new Set();
set.add(1);
console.log(set.values());
set.add(1);
console.log(set.values());
set.add(100);
set.add(200);
console.log(set.values());
console.log(set.has(100));
set.remove(100);
console.log(set.values());
console.log(set.size());
set.clear();
console.log(set.size());
// ["1"]
// ["1"]
// ["1", "100", "200"]
// true
// ["1", "200"]
// 2
// 0
字典
// 创建字典的构造函数
function Dictionay() {
this.items = {};
// 添加键值对
Dictionay.prototype.set = function(key, value) {
this.items[key] = value;
};
// 判断字典是否有某个值
Dictionay.prototype.has = function(key) {
return this.items.hasOwnProperty(key);
};
Dictionay.prototype.remove = function(key) {
if (!this.has(key)) return false;
delete this.items[key];
return true;
};
// 根据key去获取value
Dictionay.prototype.get = function(key) {
return this.has(key) ? this.items[key] : undefined;
};
// 获取所有的key
Dictionay.prototype.keys = function() {
return Object.keys(this.items);
};
// 获取所有的value
Dictionay.prototype.values = function() {
return Object.values(this.items);
};
Dictionay.prototype.size = function() {
return this.keys().length;
};
Dictionay.prototype.clear = function() {
this.items = {};
};
}
var dict = new Dictionay();
dict.set('age', 18);
dict.set('name', 'code');
dict.set('height', '1.7');
dict.set('address', 'sz');
console.log(dict.keys());
console.log(dict.values());
console.log(dict.size());
console.log(dict.get("name"));
dict.remove("height");
console.log(dict.keys());
dict.clear();
// ["age", "name", "height", "address"]
// [18, "code", "1.7", "sz"]
// 4
// code
哈希函数
function hashFunc(str, max) {
// 初始化hashCode的值
var hashCode = 0;
// 霍纳算法，来计算hashCode的值
for (var i = 0; i < str.length; i++) {
hashCode = 37 * hashCode + str.charCodeAt(i);
}
// 取模运算
hashCode = hashCode % max;
return hashCode;
}
console.log(hashFunc('abc', 7));
console.log(hashFunc('cba', 7));
console.log(hashFunc('nba', 7));
console.log(hashFunc('mba', 7));
哈希表
// 创建HashTable构造函数
function HashTable() {
this.storage = [];
this.count = 0;
this.limit = 8;
// 判断是否是质数
HashTable.prototype.isPrime = function(num) {
var temp = parseInt(Math.sqrt(num));
for (var i = 2; i<=temp; i++) {
if (num % 2 === 0) {
return false;
}
}
return true;
};
// 获取质数
HashTable.prototype.getPrime = function(num) {
while (!this.isPrime(num)) {
num++;
}
return num;
};
// 哈希函数
HashTable.prototype.hashFunc = function (str, max) {
// 初始化hashCode的值
var hashCode = 0;
// 霍纳算法，来计算hashCode的值
for (var i = 0; i < str.length; i++) {
hashCode = 37 * hashCode + str.charCodeAt(i);
}
// 取模运算
hashCode = hashCode % max;
return hashCode;
};
// 插入数据方法
HashTable.prototype.put = function(key, value) {
// 获取key对应的index
var index = this.hashFunc(key, this.limit);
// 取出数组
var bucket = this.storage[index];
if (bucket === undefined) {
bucket = [];
this.storage[index] = bucket;
}
// 判断新增还是原来的值
var override = false;
for (var i=0; i<bucket.length; i++) {
var tuple = bucket[i];
if (tuple[0] === key) {
tuple[1] = value;
override = true;
}
}
if (!override) {
bucket.push([key, value]);
this.count++;
if (this.count > this.limit * 0.75) {
var primeNum = this.getPrime(this.limit * 2);
this.resize(primeNum);
}
}
};
// 获取存放的数据
HashTable.prototype.get = function(key) {
var index = this.hashFunc(key, this.limit);
var bucket = this.storage[index];
if (bucket === null) {
return null;
}
for (var i=0; i<bucket.length; i++) {
var tuple = bucket[i];
if (tuple[0] === key) {
return tuple[1];
}
return null;
}
};
// 删除数据
HashTable.prototype.remove = function(key) {
var index = this.hashFunc(key, this.limit);
var bucket = this.storage[index];
if (bucket === null) {
return null;
}
for (var i=0; i<bucket.length; i++) {
var tuple = bucket[i];
if (tuple[0] === key) {
bucket.splice(i, 1);
this.count--;
if (this.limit > 7 && this.count < this.limit * 0.25) {
var primeNum = this.getPrime(Math.floor(this.limit / 2));
}
}
return tuple[1];
}
return null;
};
// isEmpty方法
HashTable.prototype.isEmpty = function() {
return this.count === 0;
};
// size
HashTable.prototype.size = function() {
return this.count;
};
// 哈希表扩容
HashTable.prototype.resize = function(newLimit) {
var oldStorage = this.storage;
this.limit = newLimit;
this.count = 0;
this.storage = [];
oldStorage.forEach(function(bucket) {
if (bucket === null) {
return;
}
for (var i=0; i<bucket.length; i++) {
var tuple = bucket[i];
this.put(tuple[0], tuple[1]);
}
}).bind(this);
};
}
var ht = new HashTable();
ht.put('abc', '123');
ht.put('cba', '321');
ht.put('nba', '521');
ht.put('nba', '520');
console.log(ht.get('abc'));
二叉查找树
// 创建BinarySearchTree
function BinarySearchTree() {
// 创建节点构造函数
function Node(key) {
this.key = key;
this.left = null;
this.right = null;
}
// 保持根的属性
this.root = null;
// 二叉树的相关的操作方法
// 向树插入数据
BinarySearchTree.prototype.insert = function(key) {
// 根据key创建对应的node
var newNode = new Node(key);
// 判断根节点是否有值
if (this.root === null) {
this.root = newNode;
} else {
this.insertNode(this.root, newNode);
}
};
BinarySearchTree.prototype.insertNode = function(node, newNode) {
if (newNode.key < node.key) {
// 准备向左子树插入数据
if (node.left === null) {
// node的左子树上没有内容
node.left = newNode;
} else {
// node的左子树上已经有了内容
this.insertNode(node.left, newNode);
}
} else {
// 准备向右子树上插入内容
if (node.right === null) {
// node的右子树上没有内容
node.right = newNode;
} else {
// node的右子树上有内容
this.insertNode(node.right, newNode);
}
}
};
// 获取最大、最小值
BinarySearchTree.prototype.min = function() {
var node = this.root;
while (node.left !== null) {
node = node.left;
}
return node.key;
};
BinarySearchTree.prototype.max = function() {
var node = this.root;
while (node.right !== null) {
node = node.right;
}
return node.key;
};
// 搜索特定的值
BinarySearchTree.prototype.search = function(key) {
return this.searchNode(this.root, key);
};
BinarySearchTree.prototype.searchNode = function(node, key) {
// 如果传入的node为null那么，就退出递归
if (node === null) {
return false;
}
// 判断node的节点的值和传入的key大小
if (node.key > key) {
return this.searchNode(node.left, key); // 传入的key较小，向左边继续查找
} else if (node.key < key) {
// 传入的key较大，向右边继续查找
return this.searchNode(node.right, key);
} else {
// 相同，说明找到key
return true;
}
};
BinarySearchTree.prototype.search = function(key) {
var node = this.root;
while (node !== null) {
if (node !== null) {
node = node.left;
} else if (node.key < key) {
node = node.right;
} else {
return true;
}
}
return false;
};
// 删除节点
BinarySearchTree.prototype.remove = function(key) {
var node = this.root;
var parent = null;
while (node) {
if (node.key > key) {
parent = node;
node = node.left;
} else if (node.key < key) {
parent = node;
node = node.right;
} else {
if (node.left === null && node.right === null) {
}
}
}
};
BinarySearchTree.prototype.removeNode = function(node, key) {
if (node === null) return null;
if (node.key > key) {
node.left = this.removeNode(node.left, key);
}
};
// 删除结点
BinarySearchTree.prototype.remove = function(key) {
// 1.定义临时保存的变量
var current = this.root;
var parent = this.root;
var isLeftChild = true;
// 2.开始查找节点
while (current.key !== key) {
parent = current;
if (key < current.key) {
isLeftChild = true;
current = current.left;
} else {
isLeftChild = false;
current = current.right;
}
// 如果发现current已经指向null, 那么说明没有找到要删除的数据
if (current === null) return false;
}
// 3.删除的结点是叶结点
if (current.left === null && current.right === null) {
if (current === this.root) {
this.root = null;
} else if (isLeftChild) {
parent.left = null;
} else {
parent.right = null;
}
}
// 4.删除有一个子节点的节点
else if (current.right === null) {
if (current === this.root) {
this.root = current.left;
} else if (isLeftChild) {
parent.left = current.left;
} else {
parent.right = current.left;
}
} else if (current.left === null) {
if (current === this.root) {
this.root = current.right;
} else if (isLeftChild) {
parent.left = current.right;
} else {
parent.right = current.right;
}
}
// 5.删除有两个节点的节点
else {
// 1.获取后继节点
var successor = this.getSuccessor(current);
// 2.判断是否是根节点
if (current === this.root) {
this.root = successor;
} else if (isLeftChild) {
parent.left = successor;
} else {
parent.right = successor;
}
// 3.将删除节点的左子树赋值给successor
successor.left = current.left;
}
return true;
};
// 找后继的方法
BinarySearchTree.prototype.getSuccessor = function(delNode) {
// 1.使用变量保存临时的节点
var successorParent = delNode;
var successor = delNode;
var current = delNode.right; // 要从右子树开始找
// 2.寻找节点
while (current !== null) {
successorParent = successor;
successor = current;
current = current.left;
}
// 3.如果是删除图中15的情况, 还需要如下代码
if (successor !== delNode.right) {
successorParent.left = successorParent.right;
successor.right = delNode.right;
}
};
// 遍历方法
// 先序遍历
BinarySearchTree.prototype.preOrderTraversal = function(handler) {
this.preOrderTranversalNode(this.root, handler);
};
BinarySearchTree.prototype.preOrderTranversalNode = function(node, handler) {
if (node !== null) {
handler(node.key);
this.preOrderTranversalNode(node.left, handler);
this.preOrderTranversalNode(node.right, handler);
}
};
// 中序遍历
BinarySearchTree.prototype.inOrderTraversal = function(handler) {
this.inOrderTraversalNode(this.root, handler);
};
BinarySearchTree.prototype.inOrderTraversalNode = function(node, handler) {
if (node !== null) {
this.inOrderTraversalNode(node.left, handler);
handler(node.key);
this.inOrderTraversalNode(node.right, handler);
}
};
// 后续遍历
BinarySearchTree.prototype.postOrderTraversal = function(handler) {
this.postOrderTraversalNode(this.root, handler);
};
BinarySearchTree.prototype.postOrderTraversalNode = function(node, handler) {
if (node !== null) {
this.postOrderTraversalNode(node.left, handler);
this.postOrderTraversalNode(node.right, handler);
handler(node.key);
}
};
}
// 测试代码
var bst = new BinarySearchTree();
// 插入数据
bst.insert(11);
bst.insert(7);
bst.insert(15);
bst.insert(5);
bst.insert(3);
bst.insert(9);
bst.insert(8);
bst.insert(10);
bst.insert(13);
bst.insert(12);
bst.insert(14);
bst.insert(20);
bst.insert(18);
bst.insert(25);
bst.insert(6);
// 测试前序遍历结果
var resultString = "";
bst.preOrderTraversal(function(key) {
resultString += key + " ";
});
console.log(resultString); // 11 7 5 3 6 9 8 10 15 13 12 14 20 18 25
// 测试中序遍历结果
resultString = "";
bst.inOrderTraversal(function(key) {
resultString += key + " ";
});
console.log(resultString); // 3 5 6 7 8 9 10 11 12 13 14 15 18 20 25
// 测试后续遍历结果
resultString = "";
bst.postOrderTraversal(function(key) {
resultString += key + " ";
});
console.log(resultString); // 3 6 5 8 10 9 7 12 14 13 18 25 20 15 11
// 获取最值
console.log(bst.min()); // 3
console.log(bst.max()); // 25
// 查找特定的值
console.log(bst.search(10)); // true
console.log(bst.search(21)); // false
// 查找数据
console.log(bst.remove(10));
console.log(bst.remove(21));
图
// 创建子弟啊的构造函数
function Dictory() {
this.items = {};
Dictory.prototype.set = function(key, value) {
this.items[key] = value;
};
Dictory.prototype.has = function(key) {
return this.items.hasOwnProperty(key);
};
Dictory.prototype.remove = function(key) {
if (!this.has(key)) return false;
delete this.items[key];
return true;
};
Dictory.prototype.get = function(key) {
return this.has(key) ? this.items[key] : undefined;
};
Dictory.prototype.keys = function() {
return Object.keys(this.items);
};
Dictory.prototype.values = function() {
return Object.values(this.items);
};
Dictory.prototype.size = function() {
return this.keys().length;
};
Dictory.prototype.clear = function() {
this.items = {};
};
}
// 自定义队列
function Queue() {
var items = [];
this.enqueue = function(element) {
items.push(element);
};
this.dequeue = function() {
return items.shift();
};
this.front = function() {
return items[0];
};
this.isEmpty = function() {
return items.length === 0;
};
this.size = function() {
return items.length;
};
}
// 图类
function Graph() {
// 属性
this.vertexes = []; // 存储定点
this.adjList = new Dictory(); // 存储边
// 添加方法
Graph.prototype.addVertex = function(v) {
this.vertexes.push(v);
this.adjList.set(v, []);
};
Graph.prototype.addEdge = function(v, w) {
this.adjList.get(v).push(w);
this.adjList.get(w).push(v);
};
Graph.prototype.toString = function() {
var resultStr = "";
for (var i = 0; i < this.vertexes.length; i++) {
resultStr += this.vertexes[i] + "->";
var adj = this.vertexes.get(this.vertexes[i]);
for (var j = 0; j < adj.length; j++) {
resultStr += adj[j] + " ";
}
resultStr += "\n";
}
return resultStr;
};
// 初始化颜色
Graph.prototype.initializeColor = function() {
var colors = [];
for (var i = 0; i < this.vertexes.length; i++) {
colors[this.vertexes[i]] = "white";
}
return colors;
};
// 广度优先算法
Graph.prototype.bfs = function(v, handler) {
var color = this.initializeColor();
var queue = new Queue();
queue.enqueue(v);
while (!queue.isEmpty()) {
var qv = queue.dequeue();
var qAdj = this.adjList.get(qv);
color[qv] = "gray";
for (var i = 0; i < qAdj.length; i++) {
var a = qAdj[i];
if (color[a] === "white") {
color[a] = "gray";
queue.enqueue(a);
}
}
color[qv] = "black";
if (handler) {
handler(qv);
}
}
};
// 深度优先搜索
Graph.prototype.dfs = function(handler) {
var color = this.initializeColor();
for (var i = 0; i < this.vertexes.length; i++) {
if (color[this.vertexes[i]] === "white") {
this.dfsVisit(this.vertexes[i], color, handler);
}
}
};
// dfs的递归调用方法
Graph.prototype.dfsVisit = function(u, color, handler) {
// 将u的颜色设置为灰色
color[u] = "gray";
// 处理u顶点
if (handler) {
handler(u);
}
// u的所有领接顶点的访问
var uAdj = this.adjList.get(u);
for (var i=0; i<uAdj.length; i++) {
var w = uAdj[i];
if (color[w] === "white") {
this.dfsVisit(w, color, handler);
}
}
// 将u设置为黑色
color[u] = "black";
};
}
var graph = new Graph();
var myVertexes = ["A", "B", "C", "D", "E", "F", "G", "H", "I"];
for (var i=0; i<myVertexes.length; i++) {
graph.addVertex(myVertexes[i]);
}
graph.addEdge('A', 'B');
graph.addEdge('A', 'C');
graph.addEdge('A', 'D');
graph.addEdge('C', 'D');
graph.addEdge('C', 'G');
graph.addEdge('D', 'G');
graph.addEdge('D', 'H');
graph.addEdge('B', 'E');
graph.addEdge('B', 'F');
graph.addEdge('E', 'I');
console.log(graph);
// 调用广度优先算法
var result = "";
graph.bfs(graph.vertexes[0], function(v) {
result += v+" ";
});
console.log(result);
// A B C D E F G H I
result = "";
// 调用深度优先算法
graph.dfs(function(v) {
result += v+" ";
});
console.log(result);
// A B E I F C D G H
排序
document.getElementById("app").innerHTML = `排序`;
// 创建列表
// 封装ArrayList
function ArrayList() {
this.array = [];
ArrayList.prototype.insert = function(item) {
this.array.push(item);
};
ArrayList.prototype.toString = function() {
return this.array.join();
};
// 冒泡排序(把大的数往右移动)
ArrayList.prototype.bubbleSort = function() {
var length = this.array.length;
// 反向循环
for (var i = length - 1; i >= 0; i--) {
// 根据i的次数，比较循环到i的位置
for (var j = 0; j < i; j++) {
// 如果j位置比j+1位置的数据大，那么就交换
if (this.array[j] > this.array[j + 1]) {
this.swap(j, j + 1);
}
}
}
};
ArrayList.prototype.swap = function(m, n) {
var temp = this.array[m];
this.array[m] = this.array[n];
this.array[n] = temp;
};
// 选择排序
ArrayList.prototype.selectionSort = function() {
var length = this.array.length;
for (var i = 0; i < length - 1; i++) {
var min = i;
for (var j = min + 1; j < length; j++) {
if (this.array[min] > this.array[j]) {
min = j;
}
}
this.swap(min, i);
}
};
// 插入排序
ArrayList.prototype.insertionSort = function() {
var length = this.array.length;
for (var i = 1; i < length; i++) {
var j = i;
var temp = this.array[i];
while (j > 0 && this.array[j - 1] > temp) {
this.array[j] = this.array[j - 1];
j--;
}
this.array[j] = temp;
}
};
// 希尔排序
ArrayList.prototype.shellSort = function() {
var length = this.array.length;
var gap = Math.floor(length / 2);
while (gap > 0) {
for (var i = gap; i < length; i++) {
var j = i;
var temp = this.array[i];
while (j > gap - 1 && this.array[j - gap] > temp) {
this.array[j] = this.array[j - gap];
j -= gap;
}
this.array[j] = temp;
}
gap = Math.floor(gap / 2);
}
};
ArrayList.prototype.median = function(left, right) {
var center = Math.floor((left + right) / 2);
if (this.array[left] > this.array[center]) {
this.swap(left, center);
}
if (this.array[center] > this.array[right]) {
this.swap(center, right);
}
if (this.array[left] > this.array[right]) {
this.swap(left, right);
}
this.swap(center, right - 1);
return this.array[right - 1];
};
// 快速排序
ArrayList.prototype.quickSort = function() {
this.quickSortRec(0, this.array.length - 1);
};
ArrayList.prototype.quickSortRec = function(left, right) {
if (left >= right) return;
var pivot = this.median(left, right);
var i = left;
var j = right - 1;
while (true) {
while (this.array[++i] < pivot) {}
while (this.array[--j] > pivot) {}
if (i < j) {
this.swap(i, j);
} else {
break;
}
}
this.swap(i, right - 1);
this.quickSortRec(left, i - 1);
this.quickSortRec(i + 1, right);
};
}
// 初始化数据
var list = new ArrayList();
list.insert(3);
list.insert(6);
list.insert(4);
list.insert(2);
list.insert(11);
list.insert(10);
list.insert(5);
console.log(list);
// list.bubbleSort();
// list.selectionSort();
// list.insertionSort();
// list.shellSort();
// var pivot = list.median(1, 6); // left:6 right:5 center:2
list.quickSort();
console.log(list);