// JS高级-数据结构的封装
/*
我们知道在JS中，常常用来组织数据的无非是数组和对象（这些基础就不介绍了）。但在数据结构中，还有一些抽象的数据类型：列表、栈、队列、链表、字典、散列、集合、二叉树、图等，可以用来更好的对实际场景建模。当然这些数据类型，原生JS不支持，那么就需要通过封装来模拟，其底层还是数组和对象（被看穿喽~），接下来我们挨个来解析吧
*/
/*
一、列表
定义：列表是一组有序的数据，每个列表中的数据项称为元素。元素可以是任意数据类型， 也不事先限定元素个数。
生活中经常使用到列表，通讯录、购物车、十佳榜单等。当不需要在一个很长的序列中查找元素或排序可以使用列表。
列表的封装代码：
*/
function List() {//列表的构造函数
this._dataStore = []; //初始化一个空数组来保存列表元素
this._pos = 0;//当前的位置
}
List.prototype={
constructor:List,
clear:function(){//清空列表
delete this._dataStore;
this._dataStore = []; this._pos = 0;
},
find:function(element){//在列表中查找某一元素，若有返回位置，否则返回-1
for (var i = 0; i < this._dataStore.length; ++i) {
if (this._dataStore[i] === element) {return i;}
};return -1;
},
contains:function(element){//判断给定值是否在列表中
for (var i = 0; i < this._dataStore.length; ++i) {
if (this._dataStore[i] === element) {return true; break;}
};return false;
},
insert:function(element, after){//当前位置插入新元素
var insert_pos = this.find(after);
if (insert_pos > -1) {this._dataStore.splice(insert_pos+1, 0, element);return true;};
return false;
},
append:function(element){this._dataStore[this._dataStore.length] = element;},//末尾添加新元素
remove:function(element){//删除元素
var foundAt = this.find(element);
if (foundAt > -1) {this._dataStore.splice(foundAt,1);return true;};
return false;
},
front:function(){this._pos = 0;},//将当前位置指针设为表首
end:function(){this._pos = this._dataStore.length-1;},//将当前位置指针设为表尾
prev:function(){if (this._pos > 0) {this._pos;}},//当前位置上移指针
next:function(){if (this._pos < this._dataStore.length-1) {++this._pos;}},//当前位置下移指针
moveTo:function(_position){this._pos = _position;},//移动当前位置指针到指定位置
length:function(){return this._dataStore.length;},//获取列表的中元素的个数
curr_pos:function(){return this._pos;},//返回当前位置指针
getElement:function(){return this._dataStore[this._pos];},//返回当前位置的列表项
toString:function(){return this._dataStore;}//返回列表的字符串形式
}
//列表与数组比较类似，只是简单的对数组做了二次封装，用案例来展示一下列表的使用场景，进一步加深理解。
//案例：影碟租赁自助查询系统
var moviearr=[''''肖申克的救赎'''',''''教父'''',''''教父 2'''',''''低俗小说'''',''''黄金三镖客'''',''''十二怒汉'''',''''辛德勒名单'''',''''黑暗骑士'''',''''指环王：王者归来'''',''''搏击俱乐部'''',''''星球大战5：帝国反击战'''',''''飞越疯人院'''',''''指环王：护戒使者'''',''''盗梦空间'''',''''好家伙'''',''''星球大战'''',''''七武士'''',''''黑客帝国'''',''''阿甘正传'''',''''上帝之城''''];//数据
var movieList = new List();//电影列表
for (var i = 0; i < moviearr.length; ++i) {movieList.append(moviearr[i]);}//将数据添加到‘电影列表’
var customerList = new List();//客户列表
function Customer(name, movie) {//客户租赁对象的构造函数
this.name = name;
this.movie = movie;
}
function checkOut(name, movie, movieList, customerList) {//某客户需要租赁某电影，同时维护两个列表
if(movieList.contains(movie)){//若检索电影在列表中，新建客户对象添加到客户列表，同时在电影列表中删除该电影
var c = new Customer(name, movie);
customerList.append(c);
movieList.remove(movie);
}else{console.log(movie + " is not available.");}//若不在电影列表中，则提示不可租赁
//打印维护后的两个列表
console.log(''''movieList:''''+movieList.toString()+''''\n customerList:''''+JSON.stringify(customerList.toString()))
}
checkOut(''''gavin'''',''''黑客帝国'''',movieList,customerList);
checkOut(''''gavin'''',''''星球大战'''',movieList,customerList);
checkOut(''''zoe'''',''''辛德勒名单'''',movieList,customerList);
checkOut(''''gulei'''',''''黑客帝国'''',movieList,customerList);
/*
二、栈
定义：栈是一种特殊的列表， 栈内的元素只能通过列表的一端访问， 这一端称为栈顶。
栈是一种后入先出（ LIFO， last-in-first-out） 的数据结构，任何不在栈顶的元素都无法访问。 为了得到栈底的元素， 必须先拿掉上面的元素。生活中常见的例子如：餐厅的一摞盘子，只能从上面逐个取，洗净的盘子也只能摞在最上面。
栈的封装代码：
*/
function Stack() {//栈的构造函数
this._dataStore = [];//初始化一个空数组来保存列表元素
this._top = 0;//记录栈顶的位置
}
Stack.prototype={
constructor:Stack,
clear:function(){//清空栈
delete this._dataStore;
this._dataStore = []; this._top = 0;
},
push:function(element){this._dataStore[this._top++] = element;},//向栈内添加元素
pop:function(){return this._dataStore[this._top];},//从栈内取出元素
peek:function(){return this._dataStore[this._top-1]},//查看栈顶元素
length:function(){return this._top;}//获取列表的中元素的个数
}
//相对列表来说，栈的方法不多显得很简洁，同样来几个案例，帮助理解栈的使用场景
//案例一：回文
function isPalindrome(word){
var s = new Stack();
for (var i = 0; i < word.length; ++i) {s.push(word[i]);}
var rword = "";
while (s.length() > 0) {rword += s.pop();}
if (word == rword) {return true;}else {return false;}
}
console.log(isPalindrome("hello"));//false
console.log(isPalindrome("racecar"));//true
//案例二：递归演示
function factorial(n) {
if (n === 0) {return 1;}else {return n * factorial(n-1);}
}
function fact(n) {
var s = new Stack();
while (n > 1) {s.push(n);}
var product = 1;
while (s.length() > 0) {product *= s.pop();}
return product;
}
console.log(factorial(5))//120
console.log(fact(5))//120
/*
三、队列
定义：列队也是一种特殊的列表， 不同的是队列只能在队尾插入元素， 在队首删除元素。
列队是一种先进先出（ First-In-First-Out， FIFO）的数据结构。排在前面的优先处理，后面的依次排队，直到轮到它。生活中常见的例子如：打印任务池，模拟柜台排队的顾客等。
队列的封装代码：
*/
function Queue() {//队列的构造函数
this._dataStore = [];//初始化一个空数组来保存元素
}
Queue.prototype={
constructor:Queue,
clear:function(){//清空队列
delete this._dataStore;
this._dataStore = []; this._top = 0;
},
enqueue:function(element){this._dataStore.push(element)},//向队尾添加一个元素
dequeue:function(){return this._dataStore.shift();},//删除队首元素
front:function(){return this._dataStore[0];},//读取队首元素
back:function(){return this._dataStore[this._dataStore.length-1];},//读取队尾元素
empty:function(){if(this._dataStore.length === 0){return true;}else{return false;}},//判断队列是否为空
toString:function(){//将队列元素拼接字符串
var retStr = "";
for (var i = 0; i < this._dataStore.length; ++i) {retStr += this._dataStore[i] + ",";}
return retStr;
}
}
//列队比栈稍微复杂一点，总体来说也是比较容易理解的。
//案例：舞伴分配
function Dancer(name, sex) {
this.name = name;
this.sex = sex;
}
function getDancers(males, females) {
var names = [''''F Allison McMillan'''',''''M Frank Opitz'''',''''M Mason McMillan'''',''''M Clayton Ruff'''',''''F Cheryl Ferenback'''',''''M Raymond Williams'''',''''F Jennifer Ingram'''',''''M Bryan Frazer'''',''''M David Durr'''',''''M Danny Martin'''',''''F Aurora Adney''''];
for(var i = 0; i < names.length; ++i) {
var dancer = names[i].split(" ");
var sex = dancer[0];
var name = dancer[1];
if (sex == "F") {females.enqueue(new Dancer(name, sex));
} else {males.enqueue(new Dancer(name, sex));}
}
}
function dance(males, females) {
console.log("The dance partners are: \n");
while (!females.empty() && !males.empty()) {
var person1 = females.dequeue();
var person2 = males.dequeue();
console.log("Female dancer is: " + person1.name+" and the male dancer is: " + person2.name);
}
}
var maleDancers = new Queue();
var femaleDancers = new Queue();
getDancers(maleDancers, femaleDancers);
dance(maleDancers, femaleDancers);
if (!femaleDancers.empty()) {console.log(femaleDancers.front().name + " is waiting to dance.");}
if (!maleDancers.empty()) {console.log(maleDancers.front().name + " is waiting to dance.");}
//在一般情况下，从列表中删除元素是优先删除先入队的元素，但有时候也可能需要使用一种优先队列的数据来模拟，比如医院的急诊，主要通过给队列中每个元素添加一个优先级别，并改写dequeue方法实现。
dequeue:function() {
var priority = this._dataStore[0].code;//code表示优先级别，数值越小优先级越高
for (var i = 1; i < this._dataStore.length; ++i) {priority =Math.min(priority,i);}
return this.dataStore.splice(priority,1);
}
/*
四、链表
定义：链表是由一组节点组成的集合，每个节点都使用一个对象的引用指向下一个节点，这个引用叫做链。
除了对数据的随机访问，链表几乎可以代替一维数组。它与数组的主要区别是：数组的元素靠位置进行引用，链表靠相互指向进行引用。
链表的封装代码：
*/
function Node(element) {//链表中节点的构造函数
this.element = element;
this.next = null;
}
function LList() {//链表的构造函数
this.head = new Node("head");
}
LList.prototype={
constructor:LList,
find:function(item){//查找链表，如果找到则返回该节点，否者返回头节点
var currNode = this.head;
while (currNode.element != item) {currNode = currNode.next;}
return currNode;
},
insert:function(newElement, item){//在找到的节点后，新增一个节点
var newNode = new Node(newElement);//新增节点
var current = this.find(item);//查找节点
newNode.next = current.next;//先将当前节点的next赋值给新节点的next
current.next = newNode;//再将当前节点的next设置为新节点
},
display:function(){
var currNode = this.head;
while (currNode.next!==null){console.log(currNode.next.element);currNode = currNode.next; }
},
findPrev:function(item){//查找链表，返回当前节点的上一个节点
var currNode = this.head;
while (currNode.next!==null && currNode.next.element!==item){ currNode = currNode.next; }
return currNode;
},
remove:function(item){//在链表中删除给定的节点
var prevNode = this.findPrev(item);
if (prevNode.next !== null) { prevNode.next = prevNode.next.next;}
}
}
/*
跟之前的三种数据结构不同，链表没有采用数组作为底层数据存储。而是采用对象节点作为基础，同时每个节点中都含有一个next属性指向另一个对象，与优先队列的中的优先级别code颇为类似。总体来看链表是通过每个节点的next属性，将散列的对象连接到了一起。
如上我们只是实现了单向链表，从头遍历到尾很简单，想要反过来遍历就没那么容易了。我们可以通过给节点增加一个prev属性，指向它的前一个节点，也能实现双向链表。当然，双向链表在新增和删除节点时的操作也要复杂一些，需要同时修改前后节点的next或prev属性。
另外，我们还可以让单向链表的尾节点指向首节点，这样就变成了循环列表。这样需要对链表的一些方法进行改造，防止遍历链表时出现无限循环。
*/
/*
五、字典
定义：字典是一种以键值对形式存储的数据结构。
JS中对象就是以字典的形式设计的，但字典的基础是数组，而不是对象。这样可以进行排序，况且JS中一切皆对象，数组也不例外。
字典的封装代码：
*/
function Dictionary() {//字典的构造函数
this._datastore = new Array();
}
Dictionary.prototype={
constructor:Dictionary,
add:function(key,value){ this._datastore[key]=value; },//增加一条键值对
find:function(key){ return this._datastore[key] },//查找指定key，返回对应value的值
remove:function(key){ delete this._datastore[key] },//删除指定key的键值对
showAll:function(){ //打印字典的所有键值对
//若需排序可以给Object.keys(this._datastore)数组追加sort方法
Object.keys(this._datastore).forEach(function(key){console.log(key+" -> "+this._datastore[key]);}.bind(this))
},
count:function(){//返回字典所含键值对数量
var n = 0;
for(var key in this._datastore) {++n;}
return n;
},
clear:function(){ //清空字典
Object.keys(this._datastore).forEach(function(key){ delete this._datastore[key];}.bind(this))
}
}
//字典依然采用数组作为底层数据存储，但是与普通按序号索引的数组不同，它只能以key进行查询。
/*
六、散列
定义：散列是一种常用的数据存储技术， 散列后的数据可以快速地插入或取用。 散列使用的数据结构叫做散列表。
是通过一个散列函数（Hash，哈希）将键映射为一个范围是 0 到散列表长度的数字。
散列的封装代码：
*/
function HashTable() {//散列的构造函数
this._table = new Array(137);//数组的长度应该为质数，即预算散列表的长度
}
HashTable.prototype={
constructor:HashTable,
simpleHash:function(data){//简单的散列函数（返回键字符串的ASCII累加除数组长度的余数）
var total = 0;
for (var i = 0; i < data.length; ++i) {total += data.charCodeAt(i);}
return total % this._table.length;
},
betterHash:function(data){//更好的散列函数算法，减少碰撞
const H = 37;
var total = 0;
for (var i = 0; i < data.length; ++i) {total += H * total + data.charCodeAt(i);}
total = total % this._table.length;
if (total < 0) {total += this._table.length-1;}
return parseInt(total);
},
put:function(data){var pos = this.simpleHash(data);this._table[pos] = data;},//使用简单散列函数
//put:function(key,data){var pos = this.betterHash(key);this._table[pos] = data;},//使用高级散列函数
showDistro:function(){//显示散列表中的数据
var n = 0;
for (var i = 0; i < this._table.length; ++i) {
if (this._table[i] !== undefined) {console.log(i + ": " + this._table[i]);}
}
},
get:function(key){return this._table[this.betterHash(key)];},
}
/*
散列其实是通过一种机制（散列函数），将数据存储到散列表对应的位置上去，当机制跟内容相关时仅出现修改才会改变。（MD5类似散列函数的机制）
当散列函数对于多个输入产生同样的输出时称为碰撞。开链法（用数组存储多个相同输出）和探测法（线性探测下个位置，直到有空值存入）
*/
//案列：数据存储
var students = ["David", "Jennifer", "Donnie", "Raymond", "Cynthia", "Mike", "Clayton", "Danny", "Jonathan"];
var hTable = new HashTable();
for (var i = 0; i < students.length; ++i) {hTable.put(students[i]);}
hTable.showDistro();//九条数据，被散列成八条，产生于了一个碰撞
/*
七、集合
定义：是一种不含不同元素的数据结构，这些元素是无序且不重复的。
集合的封装代码：
*/
function Set() {//集合的构造函数
this._dataStore = [];
}
Set.prototype={
constructor:Set,
add:function(data){//向集合中添加元素
if (this._dataStore.indexOf(data) < 0) {this._dataStore.push(data);return true;
} else {return false;}
},
remove:function(data){//从集合中移除元素
var pos = this._dataStore.indexOf(data);
if (pos > -1) {this._dataStore.splice(pos,1);return true;
} else {return false;}
},
contains:function(){//检查一个元素是否在集合中
if (this._dataStore.indexOf(data) > -1) {return true;} else {return false;}
},
size:function(){return this._dataStore.length},//返回集合的长度
union:function(set){//返回与另一个集合的并集
var tempSet = new Set();
for (var i = 0; i < this._dataStore.length; ++i) {tempSet.add(this._dataStore[i]);}
for (var i = 0; i < set.dataStore.length; ++i) {
if (!tempSet.contains(set.dataStore[i])) {tempSet.dataStore.push(set.dataStore[i]);}
}
return tempSet;
},
intersect:function(set){//返回与另一个集合的交集
var tempSet = new Set();
for (var i = 0; i < this._dataStore.length; ++i) {
if (set.contains(this._dataStore[i])) {tempSet.add(this._dataStore[i]);}
}
return tempSet;
},
subset:function(set){//判断集合是否其他集合的子集
if (this.size() > set.size()) {return false;
} else {
this._dataStore.foreach(function(member){if (!set.contains(member)) {return false;}})
}
return true;
},
difference:function(set){//返回与另一个集合的补集
var tempSet = new Set();
for (var i = 0; i < this._dataStore.length; ++i) {
if (!set.contains(this._dataStore[i])) {tempSet.add(this._dataStore[i]);}
}
return tempSet;
},
show:function(){return this._dataStore;},//显示集合中的元素
}
//集合的数据结构比较简单，主要实现了添加元素时检查唯一性，以及交集、并集、补集的方法和子集的检查。
/*
八、二叉树和二叉查找树
定义：树由一组以边连接的节点组成，二叉树是子节点不超过两个的特殊树。
二叉树的封装代码：
*/
function Node2(data, left, right) {//二叉树中节点的构造函数
this.data = data;
this.left = left;
this.right = right;
this.show = function(){return this.data;};
}
function BST(){//二叉查找树的构造函数
this.root = null;
}
BST.prototype={
constructor:BST,
insert:function(data){//插入节点
var n = new Node2(data, null, null);
if (this.root == null) {
this.root = n;
} else {
var current = this.root;
var parent;
while (true) {
parent = current;
if (data < current.data) {
current = current.left;if (current == null) {parent.left = n;break;}
} else {
current = current.right;if (current == null) {parent.right = n;break;}
}
}
}
},
inOrder:function(node){
if (!(node == null)) {
this.inOrder(node.left);
console.log(node.show() + " ");
this.inOrder(node.right);
}
},
getMin:function(){//获取最小的数，即最左节点
var current = this.root;
while (!(current.left == null)) {current = current.left;}
return current.data;
},
getMax:function(){//获取最大的数，即最右节点
var current = this.root;
while (!(current.right == null)) {current = current.right;}
return current.data;
},
find:function(data){//查找指定的值
var current = this.root;
while (current != null) {
if (current.data == data) {return current;
} else if (data < current.data) {current = current.left;
} else {current = current.right;}
}
return null;
},
remove:function(data){ root = this.removeNode(this.root, data);},//调用removeNode删除节点
removeNode:function(node,data){ //删除节点
if (node == null) {return null;}
if (data == node.data) {
if (node.left == null && node.right == null) {return null;} // 没有子节点的节点
if (node.left == null) {return node.right;} // 没有左子节点的节点
if (node.right == null) {return node.left;} // 没有右子节点的节点
// 有两个子节点的节点
var tempNode = getSmallest(node.right);
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;
}
}
}
//二叉树有点类似链表的数据结构，采用节点的左右属性来指向两个子节点。
/*
九、图和图算法
定义：图是由边的集合即顶点的集合组成的。常用于地图和航班等信息数据的建模。
图的封装代码：
*/
function Graph(v) {//图的构造函数,v表示顶点的数量
this.vertices = v;
this.edges = 0;
this.adj = [];
for (var i = 0; i < this.vertices; ++i) {
this.adj[i] = [];
this.adj[i].push("");
}
this.marked = [];//遍历标志位
for (var i = 0; i < this.vertices; ++i) {this.marked[i] = false;}
this.edgeTo = [];//路径查找时，存储两个顶点之间的边
}
Graph.prototype={
constructor:Graph,
addEdge:function(v,w){//增加一条从顶点v到顶点w的边
this.adj[v].push(w);
this.adj[w].push(v);
this.edges++;
},
showGraph:function(){var p='''''''';//显示当前图的结构
for (var i = 0; i < this.vertices; ++i) { p+=''''顶点''''+i+'''' ->'''';
for (var j = 0; j < this.vertices; ++j) {
if (this.adj[i][j] !== undefined){ p+=this.adj[i][j]+'''' '''';}
};p+=''''\n'''';
}console.log(p)
},
dfs:function(v){//深度优先搜索
this.marked[v] = true;
if (this.adj[v] !== undefined) {console.log("深度优先: " + v);}
for(var w in this.adj[v]) {
if(!this.marked[this.adj[v][w]]){this.dfs(this.adj[v][w]);}
}
},
bfs:function(s){//广度优先搜索
var queue = [];
this.marked[s] = true;
queue.push(s); // 添加到队尾
while (queue.length > 0) {
var v = queue.shift(); // 从队首移除
if (v!==''''''''&&v !== undefined) {console.log("广度优先: " + v);}
for(var w in this.adj[v]) {
if (!this.marked[this.adj[v][w]]) {
this.marked[this.adj[v][w]] = true;
this.edgeTo[this.adj[v][w]] = v;
queue.push(this.adj[v][w]);
}
}
}
},
pathTo:function(v){//获取最短路径，即顶点v到顶点0的边（必须先广度搜索生成edgeTo）
var source = 0;
if (!this.marked[v]) {return undefined;}
var path = [];
for (var i = v; i != source; i = this.edgeTo[i]) {path.push(i);}
path.push(source);
return path;
}
}
//在对图数据模型进行搜索时，有深度优先和广度优先两种。当进行最短路径查找时，就是广度优先搜索的过程。