Skip to content

Instantly share code, notes, and snippets.

@JaysonHwang

JaysonHwang/0_dataStructures_and_algorithms.md

Last active January 21, 2017 03:58
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save JaysonHwang/6db80bbcadcc5466bb7e4b5e8bb302e7 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save JaysonHwang/6db80bbcadcc5466bb7e4b5e8bb302e7 to your computer and use it in GitHub Desktop.
Download ZIP
javascript数据结构和算法
Raw
0_dataStructures_and_algorithms.md

目录

  1. Array 数组
  2. Stack 堆栈
  3. Queue 队列
  4. MinPriorityQueue 最小值优先队列
  5. MaxPriorityQueue 最大值优先队列
  6. LinkedList 链表
  7. Set 集合
  8. Dictionary 字典
  9. HashTable 散列表
  10. HashSet 散列集合
  11. BinarySearchTree 二叉树
Raw
Array.md

数组

对尾部的操作

var arr=[0,1,2];
arr.push(3); // 尾部添加一个元素
arr.push(3,4); // 尾部添加2个元素
Array.prototype.push.apply(arr,[3,4]); // 尾部添加2个元素(以数组形式)
Array.prototype.splice.apply(arr,[arr.length,0].concat([3,4])); // 尾部添加2个元素(以数组形式)

arr.pop(); // 尾部删除一个元素
Array.prototype.splice.call(arr,arr.length-2,2); // 尾部添加2个元素

对头的操作

var arr=[0,1,2];
arr.unshift(-1); // 头部添加一个元素
arr.unshift(-2,-1); // 头部添加2个元素
Array.prototype.unshift.apply(arr,[3,4]); // 头部添加2个元素(以数组形式)
Array.prototype.splice.apply(arr,[0,0].concat([3,4])); // 尾部添加2个元素(以数组形式)

arr.pop(); // 尾部删除一个元素
Array.prototype.splice.call(arr,arr.length-2,2); // 尾部添加2个元素
Raw
BinarySearchTree.js
/**
* 二叉树
*/
function BinarySearchTree() {
var Node = function(key){
this.key = key;
this.left = null;
this.right = null;
};
var root = null;
// 辅助方法(插入节点)
var insertNode = function(node, newNode){
if (newNode.key < node.key){
if (node.left === null){
node.left = newNode;
} else {
insertNode(node.left, newNode);
}
} else {
if (node.right === null){
node.right = newNode;
} else {
insertNode(node.right, newNode);
}
}
};
// 插入节点
this.insert = function(key){
var newNode = new Node(key);
if (root === null){
root = newNode;
} else {
insertNode(root,newNode);
}
};
// 辅助方法(中序遍历)
var inOrderTraverseNode = function (node, callback) {
if (node !== null) {
inOrderTraverseNode(node.left, callback);
callback(node.key);
inOrderTraverseNode(node.right, callback);
}
};
// 中序遍历-从小到大
this.inOrderTraverse = function(callback){
inOrderTraverseNode(root, callback);
};
// 辅助方法(先序遍历)
var preOrderTraverseNode = function (node, callback) {
if (node !== null) {
callback(node.key); //{1}
preOrderTraverseNode(node.left, callback);
preOrderTraverseNode(node.right, callback);
}
};
// 先序遍历-优先于后台节点
this.preOrderTraverse = function(callback){
preOrderTraverseNode(root, callback);
};
// 辅助方法(后序遍历)
var postOrderTraverseNode = function (node, callback) {
if (node !== null) {
postOrderTraverseNode(node.left, callback);
postOrderTraverseNode(node.right, callback);
callback(node.key);
}
};
// 后序遍历
this.postOrderTraverse = function(callback){
postOrderTraverseNode(root, callback);
};
// 辅助方法(最小值)
var minNode = function (node) {
if (node){
while (node && node.left !== null) {
node = node.left;
}
return node.key;
}
return null;
};
// 最小值
this.min = function() {
return minNode(root);
};
// 辅助方法(最大值)
var maxNode = function (node) {
if (node){
while (node && node.right !== null) {
node = node.right;
}
return node.key;
}
return null;
};
// 最大值
this.max = function() {
return maxNode(root);
};
// 辅助方法(搜索特定值)
var searchNode = function(node, key){
if (node === null){
return false;
}
if (key < node.key){
return searchNode(node.left, key);
} else if (key > node.key){
return searchNode(node.right, key);
} else {
return true;
}
};
// 搜索特定值
this.search = function(key){
return searchNode(root, key);
};
this.remove = function(key){
root = removeNode(root, key);
};
var removeNode = function(node, key){
if (node === null){
return null;
}
if (key < node.key){
node.left = removeNode(node.left, key);
return node;
} else if (key > node.key){
node.right = removeNode(node.right, key);
return node;
} else {
if (node.left === null && node.right === null){
node = null;
return node;
}
if (node.left === null){
node = node.right;
return node;
} else if (node.right === null){
node = node.left;
return node;
}
var aux = findMinNode(node.right);
node.key = aux.key;
node.right = removeNode(node.right, aux.key);
return node;
}
};
}
Raw
CircularLinkedList.js
// 单向循环链表
// 双向循环链表
function CircularLinkedList(){
}
Raw
Dictionary.js
/**
* 字典
*/
function Dictionary() {
var items = {};
this.has = function(key) {
return items.hasOwnProperty(key);
}
this.set = function(key, value) {
items[key] = value;
}
this.remove = function(key) {
if (this.has(key)) {
delete items[key];
return true;
}
return false;
}
this.get = function(key) {
return this.has(key) ? items[key] : undefined;
};
this.values = function() {
var values = [];
for (var k in items) {
if (this.has(k)) {
values.push(items[k]);
}
}
return values;
};
this.keys=function(){
return Object.keys(items);
}
this.clear=function(){
items={};
}
this.size=function(){
return Object.keys(items).length;
}
this.getItems = function() {
return items;
}
}
Raw
DoublyLinkedList.js
/**
* 双向链表
*/
function DoublyLinkedList() {
var Node = function (element) {
this.element = element;
this.next = null;
this.prev = null;
};
var length = 0;
var head = null;
var tail = null;
this.insert = function (position, element) {
if (position >= 0 && position <= length) {
var node = new Node(element);
var current = head;
var previous;
var index = 0;
if (position === 0) {
if (!head) {
head = node;
tail = node;
} else {
node.next = current;
current.prev = node;
head = node;
}
} else if (position === length) {
current = tail;
current.next = node;
node.prev = current;
tail = node;
} else {
while (index++ < position) {
previous = current;
current = current.next;
}
node.next = current;
previous.next = node;
current.prev = node;
node.prev = previous;
}
length++;
return true;
} else {
return false;
}
};
this.removeAt = function (position) {
if (position > -1 && position < length) {
var current = head,
previous,
index = 0;
if (position === 0) {
head = current.next;
if (length === 1) {
tail = null;
} else {
head.prev = null;
}
} else if (position === length - 1) {
current = tail;
tail = current.prev;
tail.next = null;
} else {
while (index++ < position) {
previous = current;
current = current.next;
}
previous.next = current.next;
current.next.prev = previous;
}
length--;
return current.element;
} else {
return null;
}
};
}
Raw
HashSet.js
/**
* 散列集合
*/
function HashSet(){
}
Raw
HashTable.js
/**
* 散列表（没解决冲突）
*/
function HashTable() {
var table = [];
// 简单散列函数
var loseloseHashCode = function (key) {
var hash = 0;
for (var i = 0; i < key.length; i++) {
hash += key.charCodeAt(i);
}
return hash % 37;
};
// 更好的散列函数
var djb2HashCode = function (key) {
var hash = 5381;
for (var i = 0; i < key.length; i++) {
hash = hash * 33 + key.charCodeAt(i);
}
return hash % 1013; //{4}
};
this.put = function(key, value) {
var position = loseloseHashCode(key);
console.log(position + ' - ' + key);
table[position] = value;
};
this.get = function (key) {
return table[loseloseHashCode(key)];
};
this.remove = function(key) {
table[loseloseHashCode(key)] = undefined;
};
this.print=function(){
for (var i = 0; i < table.length; ++i) {
if (table[i] !== undefined) {
console.log(i + ": " + table[i]);
}
}
}
}
/**
* 散列表（使用分离链接来解决冲突）
*/
function HashTable() {
var table = [];
var ValuePair = function(key, value){
this.key = key;
this.value = value;
this.toString = function() {
return '[' + this.key + ' - ' + this.value + ']';
}
};
var loseloseHashCode = function (key) {
var hash = 0;
for (var i = 0; i < key.length; i++) {
hash += key.charCodeAt(i);
}
return hash % 37;
};
this.put = function(key, value) {
var position = loseloseHashCode(key);
if (table[position] == undefined) {
table[position] = new LinkedList();
}
table[position].append(new ValuePair(key, value));
};
this.get = function(key) {
var position = loseloseHashCode(key);
if (table[position] !== undefined){
var current = table[position].getHead();
while(current.next){
if (current.element.key === key){
return current.element.value;
}
current = current.next;
}
if (current.element.key === key){
return current.element.value;
}
}
return undefined;
};
this.remove = function(key){
var position = loseloseHashCode(key);
if (table[position] !== undefined){
var current = table[position].getHead();
while(current.next){
if (current.element.key === key){
table[position].remove(current.element);
if (table[position].isEmpty()){
table[position] = undefined;
}
return true;
}
current = current.next;
}
if (current.element.key === key){
table[position].remove(current.element);
if (table[position].isEmpty()){
table[position] = undefined;
}
return true;
}
}
return false;
};
this.print=function(){
for (var i = 0; i < table.length; ++i) {
if (table[i] !== undefined) {
console.log(i + ": " + table[i]);
}
}
}
}
/**
* 散列表(使用线性探查方法来解决冲突)
*/
function HashTable() {
var table = [];
var ValuePair = function(key, value){
this.key = key;
this.value = value;
this.toString = function() {
return '[' + this.key + ' - ' + this.value + ']';
}
};
var loseloseHashCode = function (key) {
var hash = 0;
for (var i = 0; i < key.length; i++) {
hash += key.charCodeAt(i);
}
return hash % 37;
};
this.put = function(key, value) {
var position = loseloseHashCode(key);
if (table[position] == undefined) {
table[position] = new ValuePair(key, value);
}else {
var index = ++position;
while (table[index] != undefined){
index++;
}
table[index] = new ValuePair(key, value);
}
};
this.get = function(key) {
var position = loseloseHashCode(key);
if (table[position] !== undefined){
if (table[position].key === key) {
return table[position].value;
} else {
var index = ++position;
while (table[index] === undefined || table[index].key !== key){
index++;
}
if (table[index].key === key) {
return table[index].value;
}
}
}
return undefined;
};
this.remove = function(key) {
var position = loseloseHashCode(key);
if (table[position] !== undefined){
if (table[position].key === key) {
return table[position].value;
} else {
var index = ++position;
while (table[index] === undefined || table[index].key !== key){
index++;
}
if (table[index].key === key) {
table[index] = undefined;
}
}
}
table[index] = undefined;
};
this.print=function(){
for (var i = 0; i < table.length; ++i) {
if (table[i] !== undefined) {
console.log(i + ": " + table[i]);
}
}
}
}
Raw
LinkedList.js
/**
* 链表
*/
function LinkedList() {
var Node = function(element){
this.element = element;
this.next = null;
};
var length = 0;
var head = null;
this.append = function(element){
var node = new Node(element);
var current;
if (head === null){
head = node;
} else {
current = head;
// 循环列表,直到找到最后一项
while(current.next){
current = current.next;
}
// 找到最后一项,将其next赋值为node,建立连接
current.next = node;
}
length++;
}
this.removeAt = function(position){
// 检查越界
if(position > -1 && position < length){
var current = head;
var previous;
var index = 0;
// 移除第一项
if (position === 0){
head = current.next;
} else {
while (index++ < position){
previous = current;
current = current.next;
}
previous.next = current.next;
}
length--;
return current.element;
} else {
return null;
}
};
this.insert = function(position, element){
if (position >= 0 && position <= length){
var node = new Node(element);
var current = head;
var previous;
var index = 0;
if (position === 0){
node.next = current;
head = node;
} else {
while (index++ < position){
previous = current;
current = current.next;
}
node.next = current;
previous.next = node;
}
length++;
return true;
} else {
return false;
}
};
this.indexOf = function(element){
var current = head;
var index = -1;
while (current) {
index++;
if (element === current.element) {
return index;
}
current = current.next;
}
return -1;
};
this.remove = function(element){
var index = this.indexOf(element);
return this.removeAt(index);
};
this.isEmpty = function() {
return length === 0;
};
this.size = function() {
return length;
};
this.getHead = function(){
return head;
};
this.toString = function(){
var current = head;
var string = '';
while (current) {
string +=current.element+',';
current = current.next;
}
return string;
};
}
Raw
MaxPriorityQueue.js
/**
* 最小优先队列
*/
function MaxPriorityQueue() {
var items = [];
function QueueElement (element, priority){
this.element = element;
this.priority = priority;
}
this.enqueue = function(element, priority){
var queueElement = new QueueElement(element, priority);
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.end = function(){
return items[items.length-1];
}
this.isEmpty = function(){
return items.length == 0;
};
this.clear = function(){
items = [];
};
this.size = function(){
return items.length;
};
this.print = function(){
console.table(items);
};
};
Raw
MinPriorityQueue.js
/**
* 最小优先队列
*/
function MinPriorityQueue() {
var items = [];
function QueueElement (element, priority){
this.element = element;
this.priority = priority;
}
this.enqueue = function(element, priority){
var queueElement = new QueueElement(element, priority);
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.end = function(){
return items[items.length-1];
}
this.isEmpty = function(){
return items.length == 0;
};
this.clear = function(){
items = [];
};
this.size = function(){
return items.length;
};
this.print = function(){
console.table(items);
};
};
Raw
Queue.js
/**
* 队列
*/
function Queue() {
var items = [];
this.enqueue = function(element){
items.push(element);
};
this.dequeue = function(){
return items.shift();
};
this.front = function(){
return items[0];
};
this.end = function(){
return items[items.length-1];
}
this.isEmpty = function(){
return items.length == 0;
};
this.clear = function(){
items = [];
};
this.size = function(){
return items.length;
};
this.print = function(){
console.log(items.toString());
};
}
Raw
Set.js
/**
* 集合
*/
function Set() {
var items = {};
this.has = function(value){
return items.hasOwnProperty(value);
};
this.add = function(value){
if (!this.has(value)){
items[value] = value;
return true;
}
return false;
};
this.remove = function(value){
if (this.has(value)){
delete items[value];
return true;
}
return false;
};
this.clear = function(){
items = {};
};
this.size = function(){
return Object.keys(items).length;
};
this.values = function(){
return Object.keys(items);
};
// 并集
this.union = function(otherSet){
var unionSet = new Set();
var values = this.values();
for (var i=0; i<values.length; i++){
unionSet.add(values[i]);
}
values = otherSet.values();
for (var i=0; i<values.length; i++){
unionSet.add(values[i]);
}
return unionSet;
};
// 交集
this.intersection = function(otherSet){
var intersectionSet = new Set();
var values = this.values();
for (var i=0; i<values.length; i++){
if (otherSet.has(values[i])){
intersectionSet.add(values[i]);
}
}
return intersectionSet;
}
// 差集
this.difference = function(otherSet){
var differenceSet = new Set();
var values = this.values();
for (var i=0; i<values.length; i++){
if (!otherSet.has(values[i])){
differenceSet.add(values[i]);
}
}
return differenceSet;
};
// 子集
this.subset = function(otherSet){
if (this.size() > otherSet.size()){
return false;
} else {
var values = this.values();
for (var i=0; i<values.length; i++){
if (!otherSet.has(values[i])){
return false;
}
}
return true;
}
};
}
Raw
Stack.js
/**
* 堆栈
*/
function Stack() {
var items = [];
this.push = function(element){
items.push(element);
};
this.pop = function(){
return items.pop();
};
this.peek = function(){
return items[items.length-1];
};
this.isEmpty = function(){
return items.length == 0;
};
this.size = function(){
return items.length;
};
this.clear = function(){
items = [];
};
this.print = function(){
console.log(items.toString());
};
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment