《数据结构与算法-JavaScript描述》--数据结构
ps：最近想学英语，如果哪位朋友有全英文书籍想要卖（最好难度不大@-@），可以私聊我，收购。
----------超长文预警，需要花费大量时间----------
今天整理《数据结构与算法-JavaScript描述》中所讲的数据结构。
1、数组
关于数组，之前整理过思维导图，感觉比书上的全。
数组.png
2、列表
在日常生活中，人们经常使用列表:待办事项列表、购物清单、十佳榜单、最后十名榜单 等。计算机程序也在使用列表，尤其是列表中保存的元素不是太多时。当不需要在一个很 长的序列中查找元素，或者对其进行排序时，列表显得尤为有用。反之，如果数据结构非 常复杂，列表的作用就没有那么大了。
不包含任何元素的列表称为空列表。列表中包含元素的个数称为列表的 length。在内部实 现上，用一个变量 listSize 保存列表中元素的个数。可以在列表末尾 append 一个元素， 也可以在一个给定元素后或列表的起始位置 insert 一个元素。使用 remove 方法从列表中 删除元素，使用 clear 方法清空列表中所有的元素。还可以使用 toString() 方法显示列表中所有的元素，使用 getElement() 方法显示当前元素。
列表拥有描述元素位置的属性。列表有前有后(分别对应 front 和 end)。使用 next() 方 法可以从当前元素移动到下一个元素，使用 prev() 方法可以移动到当前元素的前一个元 素。还可以使用 moveTo(n) 方法直接移动到指定位置，这里的 n 表示要移动到第 n 个位置。 currPos 属性表示列表中的当前位置。
JavaScript实现列表
// 列表
function List(){
this.listSize = 0; // 列表的元素个数
this.pos = 0; //列表的当前位置
this.dataStore = [];//初始化一个空数组来保存列表元素
// length:列表中有多少个元素
this.length = function(){
return this.listSize;
};
// clear:清空列表中所有的元素
this.clear = function(){
delete this.dataStore;
this.dataStore = [];
this.listSize = this.pos = 0;
};
// 判断元素是否在当前列表中，如果在返回元素下标，不在返回-1
this.find = function(element){
for(var i = 0 ; i < this.dataStore.length ; i++){
if(this.dataStore[i] == element){
return i;
}
}
return -1;
};
// 显示列表中的元素
this.toString = function(){
return this.dataStore;
};
// insert:在element元素后面插入after元素
this.insert = function(element,after){
var insertPos = this.find(after);
if(insertPos > -1){
this.dataStore.splice(insertPos+1,0,element);
this.listSize++;
return true;
}
return false;
};
// append：在列表末尾插入一个元素
this.append = function(element){
this.dataStore[this.listSize++] = element;
};
// remove：从列表中删除元素
this.remove = function(element){
var foundAt = this.find(element);
if (foundAt > -1){
this.dataStore.splice(foundAt,1)
this.listSize--;
return true;
}
return false;
};
// front：将列表的当前位置设移动到第一个元素
this.front = function(){
return this.pos = 0;
};
// getElement：返回当前位置的元素
this.getElement = function() {
return this.dataStore[this.pos]
};
// contains:判断给定值是否在列表中
this.contains = function(element){
for (var i = 0 ; i < this.dataStore.length ; i++){
if(this.dataStore[i] == element){
return true;
}
}
return false
};
// 最后一组方法允许用户在列表上自由移动
// 将列表的当前位置移动到最后一个元素
this.end = function(){
return this.pos = this.listSize-1;
};
// 将当前位置后移一位
this.prev = function(){
if(this.pos>0){
return this.pos--;
}
};
// 将当前位置前移一位
this.next = function(){
if(this.pos < this.listSize-1){
return ++this.pos;
}else{
return this.pos = this.listSize;
}
};
// 返回列表的当前位置
this.currPos = function(){
return this.pos;
};
// 将当前位置移动到指定位置
this.moveTo = function(position){
return this.pos = position;
};
}
// 测试
var names = new List();
names.append("Clayton");
names.append("Raymond");
names.append("Cynthia");
names.append("Jennifer");
names.append("Bryan");
names.append("Danny");
console.log(names.toString())
//["Clayton", "Raymond", "Cynthia", "Jennifer", "Bryan", "Danny"]
console.log(names.listSize) //6
console.log(names.find('Danny')) // 5
console.log(names.insert('Luckfine','Jennifer')) // true
console.log(names.toString())
//["Clayton", "Raymond", "Cynthia", "Jennifer", "Luckfine", "Bryan", "Danny"]
console.log(names.listSize) //7
console.log(names.remove('Luckfine')) //true
console.log(names.toString())
//["Clayton", "Raymond", "Cynthia", "Jennifer", "Bryan", "Danny"]
console.log(names.listSize) //6
console.log(names.front()) // 0
console.log(names.getElement()) // Clayton
console.log(names.next())// 1
console.log(names.getElement()) //Raymond
console.log(names.moveTo(4))
console.log(names.getElement())//Bryan
console.log(names.currPos()) //4
console.log(names.end()) //5
console.log(names.getElement()) //Danny
小案例：使用列表管理实现影碟租赁
// 使用列表管理影碟租赁
var movies = ['《肖申克的救赎》','《教父》','《低俗小说》','《黄金三镖客','《十二怒汉》','《辛德勒名单》','《黑暗骑士》','《指环王:王者归来》','《搏击俱乐部》','《星球大战 5:帝国反击战》','《飞越疯人院》','《指环王:护戒使者》','《盗梦空间》','《好家伙》','《星球大战》','《黑客帝国》','《阿甘正传》','《上帝之城》']
var movieList = new List();
var customers = new List();
for (var i = 0; i < movies.length; ++i) {
movieList.append(movies[i]);
}
// displayList函数来显示影碟店里现有的影碟清单
function displayList(list) {
for (list.front(); list.currPos() < list.length(); list.next()) {
// 如果传进来的是顾客借阅的书，那就显示借阅者和借阅的影碟
if (list.getElement() instanceof Customer) {
console.log(list.getElement()["name"] + ", " +
list.getElement()["movie"]);
} else {
console.log(list.getElement());
}
}
}
// 用来存已经借阅的客户和影碟
function Customer(name, movie) {
this.name = name;
this.movie = movie;
}
// 借阅影碟
function checkOut(name, movie, filmList, customerList) {
if (movieList.contains(movie)) {
var c = new Customer(name, movie);
customerList.append(c);
filmList.remove(movie);
} else {
console.log(movie + " is not available.");
}
}
// 归还影碟
function checkIn(name, movie, filmList, customerList) {
// console.log([name, movie])
for (customers.front(); customers.currPos() < customers.length(); customers.next()) {
// 在借阅列表中判断有无归还的影碟，如果有，将其移除
if(customers.getElement()["name"]==name && customers.getElement()["movie"]==movie){
customers.remove(customers.getElement())
filmList.append(movie);
}else{
console.log(movie + " is not available.");
}
}
}
console.log(checkOut('Luckfine','《星球大战》',movieList,customers))
console.log(checkOut('Luckfine','《肖申克的救赎》',movieList,customers))
console.log(checkIn('Luckfine','《肖申克的救赎》',movieList,customers))
console.log(customers.toString())
console.log(displayList(customers))
3、栈
栈是一种特殊的列表，栈内的元素只能通过列表的一端访问，这一端称为栈顶。咖啡厅内 的一摞盘子是现实世界中常见的栈的例子。只能从最上面取盘子，盘子洗净后，也只能摞 在这一摞盘子的最上面。栈被称为一种后入先出(LIFO，last-in-first-out)的数据结构。
由于栈具有后入先出的特点，所以任何不在栈顶的元素都无法访问。为了得到栈底的元 素，必须先拿掉上面的元素。
JavaScript实现栈
function Stack() {
this.dataStore = []; // 保存栈内元素
this.top = 0; //变量top记录栈顶位置 初始化为0
//向栈内压入新元素
this.push = function(element){
return this.dataStore[this.top++] = element;
};
//它返回栈顶元素，同时将变量 top 的值减 1
this.pop = function(){
return this.dataStore[--this.top];
};
//返回数组的第 top-1 个位置的元素，即栈顶元素
this.peek = function(){
return this.dataStore[this.top-1];
};
//clear() 方法 清除栈内所有元素
this.clear = function(){
return this.top = 0;
};
//length 属性记录栈内元素的个数
this.length = function(){
return this.top;
};
}
// 测试stack类的实现
var s = new Stack();
s.push("David");
s.push("Raymond");
s.push("Bryan");
console.log(s.length())
console.log(s.peek());
console.log(s.pop())
console.log(s.length())
s.clear();
console.log(s.length());
// 判定给定的字符串是否是回文
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('helleh')); //true
4、队列
队列是一种列表，不同的是队列只能在队尾插入元素，在队首删除元素。队列用于存储按 顺序排列的数据，先进先出，这点和栈不一样，在栈中，最后入栈的元素反而被优先处 理。可以将队列想象成在银行前排队的人群，排在最前面的人第一个办理业务，新来的人 只能在后面排队，直到轮到他们为止。
队列是一种先进先出(First-In-First-Out，FIFO)的数据结构。队列被用在很多地方，比如 提交操作系统执行的一系列进程、打印任务池等，一些仿真系统用队列来模拟银行或杂货 店里排队的顾客。
JavaScript实现队列
// 使用数组来实现队列看起来顺理成章。JavaScript 中的数组具有其他编程语言中没有的优点， 数组的 push() 方法可以在数组末尾加入元素，shift() 方法则可删除数组的第一个元素。
function Queue() {
this.dataStore = [];
// enqueue() 方法向队尾添加一个元素:
this.enqueue = function(element){
return this.dataStore.push(element);
};
// dequeue() 方法删除队首的元素
this.dequeue = function(){
return this.dataStore.shift();
};
// 读取队首
this.front = function(){
return this.dataStore[0];
};
// 读取队尾
this.back = function(){
return this.dataStore[this.dataStore.length-1];
};
// toString() 方法显示队列内的所有元素
this.toString = function(){
var retStr = "";
for (var i = 0; i < this.dataStore.length; ++i) {
retStr += this.dataStore[i] + "\n";
}
return retStr;
};
// 判断队列是否为空:
this.empty = function(){
if (this.dataStore.length == 0) {
return true;
} else {
return false;
}
};
}
var q = new Queue();
q.enqueue("Meredith");
q.enqueue("Cynthia");
q.enqueue("Jennifer");
console.log(q.toString())//Meredith Cynthia Jennifer
q.dequeue();
console.log(q.toString())//Cynthia Jennifer
console.log(q.front())//Cynthia
console.log(q.back())//Jennifer
console.log(q.enqueue('Luckfine'))
console.log(q.toString()) //Cynthia Jennifer Luckfine
5、链表
链表是由一组节点组成的集合。每个节点都使用一个对象的引用指向它的后继。指向另一 个节点的引用叫做链。
数组元素靠它们的位置进行引用，链表元素则是靠相互之间的关系进行引用。在图 6-1 中， 我们说 bread 跟在 milk 后面，而不说 bread 是链表中的第二个元素。遍历链表，就是跟着 链接，从链表的首元素一直走到尾元素(但这不包含链表的头节点，头节点常常用来作为 链表的接入点)。图中另外一个值得注意的地方是，链表的尾元素指向一个 null 节点。
链表中插入一个节点的效率很高。向链表中插入一个节点，需要修改它前面的节点(前 驱)，使其指向新加入的节点，而新加入的节点则指向原来前驱指向的节点。图 6-3 演示了 如何在 eggs 后加入 cookies。
从链表中删除一个元素也很简单。将待删除元素的前驱节点指向待删除元素的后继节点，同时
将待删除元素指向 null，元素就删除成功了。图 6-4 演示了从链表中删除“bacon”的过程。
JavaScript实现链表
function Node(element) {
this.element = element;//element 用来保存节点上的数据
this.next = null;//next 用来保存指向下一个节点的链接
}
function LList() {
this.head = new Node("head");
// 遍历链表，查找给定数据。如果找到数据，该方法就返回保存该数据的节点。
// find() 方法演示了如何在链表上进行移动。首先，创建一个新节点，并将链表的头节点赋 给这个新创建的节点。然后在链表上进行循环，如果当前节点的 element 属性和我们要找 的信息不符，就从当前节点移动到下一个节点。如果查找成功，该方法返回包含该数据的 节点;否则，返回 null。
this.find = function(item){
var currNode = this.head;
while (currNode.element != item) {
currNode = currNode.next;
}
return currNode;
};
// insert():向链表中插入一个节点
// 该方法向链表中插入一个节点。向链表中插入新节点 时，需要明确指出要在哪个节点前面或后面插入。一旦找到“后面”的节点，就可以将新节点插入链表了。首先，将新节点的 next 属性设 置为“后面”节点的 next 属性对应的值。然后设置“后面”节点的 next 属性指向新节点。
this.insert = function(newElement, item){
var newNode = new Node(newElement);
var current = this.find(item);
newNode.next = current.next;
current.next = newNode;
};
// 从链表中删除节点时，需要先找到待删除节点前面的节点。找到这个节点后，修改它的 next 属性，使其不再指向待删除节点，而是指向待删除节点的下一个节点。
this.remove = function(item){
var prevNode = this.findPrevious(item);
if (!(prevNode.next == null)) {
prevNode.next = prevNode.next.next;
}
};
this.display = function(){
var currNode = this.head;
while (!(currNode.next == null)) {
console.log(currNode.next.element);
currNode = currNode.next;
}
};
this.findPrevious = function(item){
var currNode = this.head;
while (!(currNode.next == null) && (currNode.next.element != item)) {
currNode = currNode.next;
}
return currNode;
}
}
var cities = new LList();
cities.insert("Conway", "head");
cities.insert("Russellville", "Conway");
cities.insert("Alma", "Russellville");
cities.display()//Conway Russellville Alma
cities.remove("Carlisle")
cities.display();//Russellville Alma
双向链表
尽管从链表的头节点遍历到尾节点很简单，但反过来，从后向前遍历则没那么简单。通过 给 Node 对象增加一个属性，该属性存储指向前驱节点的链接，这样就容易多了。此时向链 表插入一个节点需要更多的工作，我们需要指出该节点正确的前驱和后继。但是在从链表 中删除节点时，效率提高了，不需要再查找待删除节点的前驱节点了。图 6-5 演示了双向 链表的工作原理。
双向链表的 remove() 方法比单向链表的效率更高，因为不需要再查找前驱节点了。首先需 要在链表中找出存储待删除数据的节点，然后设置该节点前驱的 next 属性，使其指向待删 除节点的后继;设置该节点后继的 previous 属性，使其指向待删除节点的前驱。
JavaScript实现双向链表
function Node(element) {
this.element = element;
this.next = null;
this.previous = null;
}
function LList() {
this.head = new Node("head");
this.find = function(item){
var currNode = this.head;
while (currNode.element != item) {
currNode = currNode.next;
}
return currNode;
};
//双向链表的 insert() 方法和单向链表的类似，但是需要设置新节点的 previous 属性，使 其指向该节点的前驱。
this.insert = function(newElement,item){
var newNode = new Node(newElement);
var current = this.find(item);
newNode.next = current.next;
newNode.previous = current;
current.next = newNode;
};
this.display = function(){
var currNode = this.head;
while (!(currNode.next == null)) {
console.log(currNode.next.element);
currNode = currNode.next;
}
};
this.dispReverse = function(){
var currNode = this.head;
currNode = this.findLast();
while (!(currNode.previous == null)) {
console.log(currNode.element);
currNode = currNode.previous;
}
};
this.findLast = function(){
var currNode = this.head;
while (!(currNode.next == null)) {
currNode = currNode.next;
}
return currNode;
}
this.remove = function(item){
var currNode = this.find(item);
if (!(currNode.next == null)) {
currNode.previous.next = currNode.next;
currNode.next.previous = currNode.previous;
currNode.next = null;
currNode.previous = null;
}
};
}
var cities = new LList();
cities.insert("Conway", "head");
cities.insert("Russellville", "Conway");
cities.insert("Carlisle", "Russellville");
cities.insert("Alma", "Carlisle");
cities.display();//Conway Russellville Carlisle Alma
循环链表
如果你希望可以从后向前遍历链表，但是又不想付出额外代价来创建一个双向链表，那么
就需要使用循环链表。从循环链表的尾节点向后移动，就等于从后向前遍历链表。
循环链表和单向链表相似，节点类型都是一样的。唯一的区别是，在创建循环链表时，让
其头节点的 next 属性指向它本身，即: head.next = head
只需要修改一处，就将单向链表变成了循环链表。但是其他一些方法需要修改才能工作正 常。比如，display() 就需要修改，原来的方式在循环链表里会陷入死循环。while 循环的 循环条件需要修改，需要检查头节点，当循环到头节点时退出循环。
循环链表的 display() 方法如下所示:
function display() {
var currNode = this.head;
while (!(currNode.next == null) &&
!(currNode.next.element == "head")) {
print(currNode.next.element);
currNode = currNode.next;
} }
知道了怎么修改 display() 方法，就应该会修改其他方法了。
6、字典
字典是一种以键 - 值对形式存储数据的数据结构，就像电话号码簿里的名字和电话号码一 样。要找一个电话时，先找名字，名字找到了，紧挨着它的电话号码也就找到了。这里的 键是指你用来查找的东西，值是查找得到的结果。
JavaScript实现字典
function Dictionary() {
this.datastore = new Array();
// add()：该方法接受两个参数:键和值。键是值在字典中的索引。
this.add = function(key, value){
this.datastore[key] = value;
this.datastore.length++;
console.log(this.datastore)
};
// find()：该方法以键作为参数，返回和其关联的值。
this.find = function(key){
return this.datastore[key];
};
// remove():删除一组键值对
this.remove = function(key){
delete this.datastore[key];
this.datastore.length--;
};
// 显示字典中所有的键 - 值对
this.showAll = function(){
for(var key in this.datastore) {
console.log(key,this.datastore[key]);
}
};
// 字典中的元素个数
this.count = function(){
return this.datastore.length;
};
// 清空字典
this.clear = function(){
for(var key in this.datastore) {
delete this.datastore[key];
this.datastore.length--;
}
}
}
var pbook = new Dictionary();
pbook.add("Mike","123");
pbook.add("David", "345");
pbook.add("Cynthia", "456");
pbook.showAll();
pbook.remove("Cynthia");
console.log(pbook.count());//2
pbook.clear();
console.log(pbook.count());//0
7、散列
散列是一种常用的数据存储技术，散列后的数据可以快速地插入或取用。散列使用的数据 结构叫做散列表。在散列表上插入、删除和取用数据都非常快，但是对于查找操作来说却 效率低下，比如查找一组数据中的最大值和最小值。
我们的散列表是基于数组进行设计的。数组的长度是预先设定的，如有需要，可以随时增 加。所有元素根据和该元素对应的键，保存在数组的特定位置，该键和我们前面讲到的字 典中的键是类似的概念。使用散列表存储数据时，通过一个散列函数将键映射为一个数 字，这个数字的范围是 0 到散列表的长度。
理想情况下，散列函数会将每个键值映射为一个唯一的数组索引。然而，键的数量是无限 的，数组的长度是有限的(理论上，在 JavaScript 中是这样)，一个更现实的目标是让散列 函数尽量将键均匀地映射到数组中。
即使使用一个高效的散列函数，仍然存在将两个键映射成同一个值的可能，这种现象称为 碰撞(collision)，当碰撞发生时，我们需要有方案去解决。
要确定的最后一个问题是:散列表中的数组究竟应该有多大?这是编写散列函数时必须要 考虑的。对数组大小常见的限制是:数组长度应该是一个质数。
先说针对字符串的散列，乍一看，将字符串中每个字符的 ASCII 码值相加似乎是一个不错的散列函数。这样散列值就是 ASCII 码值的和除以数组长度的余数。
为了避免碰撞，首先要确保散列表中用来存储数据的数组其大小是个质数。这一点很关 键，这和计算散列值时使用的取余运算有关。数组的长度应该在 100 以上，这是为了让数 据在散列表中分布得更加均匀。通过试验我们发现，比 100 大且不会让例 8-1 中的数据产 生碰撞的第一个质数是 137。使用其他更接近 100 的质数，在该数据集上依然会产生碰撞。
为了避免碰撞，在给散列表一个合适的大小后，接下来要有一个计算散列值的更好方法。 霍纳算法很好地解决了这个问题。本书不会过多深入该算法的数学细节，在此算法中，新 的散列函数仍然先计算字符串中各字符的 ASCII 码值，不过求和时每次要乘以一个质数。 大多数算法书建议使用一个较小的质数，比如 31，但是对于我们的数据集，31 不起作用， 我们使用 37，这样刚好不会产生碰撞。
综上，用JavaScript实现字符串的散列
function HashTable(){
// 创建一个长度为137的数组
this.table = new Array(137);
// 为了避免碰撞，在给散列表一个合适的大小后，接下来要有一个计算散列值的更好方法。 霍纳算法很好地解决了这个问题。本书不会过多深入该算法的数学细节，在此算法中，新 的散列函数仍然先计算字符串中各字符的 ASCII 码值，不过求和时每次要乘以一个质数。 大多数算法书建议使用一个较小的质数，比如 31，但是对于我们的数据集，31 不起作用， 我们使用 37，这样刚好不会产生碰撞。
this.betterHash = function(string){
const H = 37;
var total = 0;
for (var i = 0; i < string.length; ++i) {
total += H * total + string.charCodeAt(i);
}
total = total % this.table.length;
if (total < 0) {
total += this.table.length-1;
}
return parseInt(total);
};
// 显示散列中的所有数据
this.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]);
}
}
};
// 向散列中添加数据
this.put = function(data){
var pos = this.betterHash(data);
this.table[pos] = data;
};
}
var someNames = ["David", "Jennifer", "Donnie", "Raymond",
"Cynthia", "Mike", "Clayton", "Danny", "Jonathan"];
var hTable = new HashTable();
for (var i = 0; i < someNames.length; ++i) {
hTable.put(someNames[i]);
}
hTable.showDistro();
结果：
碰撞处理：
当散列函数对于多个输入产生同样的输出时，就产生了碰撞。
1、开链法：当碰撞发生时，我们仍然希望将键存储到通过散列算法产生的索引位置上，但实际上，不 可能将多份数据存储到一个数组单元中。开链法是指实现散列表的底层数组中，每个数组 元素又是一个新的数据结构，比如另一个数组，这样就能存储多个键了。使用这种技术， 即使两个键散列后的值相同，依然被保存在同样的位置，只不过它们在第二个数组中的位 置不一样罢了。
2、线性探测法：线性探测法隶属于一种更一般化的散列技术:开放 寻址散列。当发生碰撞时，线性探测法检查散列表中的下一个位置是否为空。如果为空， 就将数据存入该位置;如果不为空，则继续检查下一个位置，直到找到一个空的位置为 止。该技术是基于这样一个事实:每个散列表都会有很多空的单元格，可以使用它们来存 储数据。
当存储数据使用的数组特别大时，选择线性探测法要比开链法好。这里有一个公式，常常 可以帮助我们选择使用哪种碰撞解决办法:如果数组的大小是待存储数据个数的 1.5 倍， 那么使用开链法;如果数组的大小是待存储数据的两倍及两倍以上时，那么使用线性探 测法。
8、集合
集合(set)是一种包含不同元素的数据结构。集合中的元素称为成员。集合的两个最重 要特性是:首先，集合中的成员是无序的;其次，集合中不允许相同成员存在。
下面是一些使用集合时必须了解的定义。
• 不包含任何成员的集合称为空集，全集则是包含一切可能成员的集合。
• 如果两个集合的成员完全相同，则称两个集合相等。
• 如果一个集合中所有的成员都属于另外一个集合，则前一集合称为后一集合的子集。
对集合的基本操作有下面几种。
• 并集 将两个集合中的成员进行合并，得到一个新集合。
• 交集 两个集合中共同存在的成员组成一个新的集合。
• 补集 属于一个集合而不属于另一个集合的成员组成的集合。
JavaScript实现集合
function Set() {
// 用数组去保存集合
this.dataStore = [];
// 向集合中添加数据
this.add = function(data){
if (this.dataStore.indexOf(data) < 0) {
this.dataStore.push(data);
return true;
} else {
return false;
}
};
// 从集合中删除数据
this.remove = function(){
var pos = this.dataStore.indexOf(data);
if (pos > -1) {
this.dataStore.splice(pos,1);
return true;
} else {
return false;
}
};
// 集合长度
this.size = function(){
return this.dataStore.length;
};
// 并集
this.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
};
// 交集
this.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;
};
// 子集
this.subset = function(set){
if (this.size() > set.size()) {
return false;
} else {
for (var i = 0 ; i < this.dataStore.length; i++){
if (!set.contains(this.dataStore[i])) {
return false;
}
}
}
return true
};
// 补集
this.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;
};
// 显示集合中的所有数据
this.show = function(){
return this.dataStore;
};
// 判断集合中是否包含某个元素
this.contains = function (data){
if (this.dataStore.indexOf(data) > -1) {
return true;
}
else {
return false;
}
}
}
var cis = new Set();
cis.add("Raymond");
cis.add("Cynthia");
var dmp = new Set();
dmp.add("Raymond");
dmp.add("Cynthia");
dmp.add("Bryan");
console.log(cis.subset(dmp)); //true
9、二叉树和二叉查找树
树是计算机科学中经常用到的一种数据结构。树是一种非线性的数据结构，以分层的方式 存储数据。树被用来存储具有层级关系的数据，比如文件系统中的文件;树还被用来存储 有序列表。本章将研究一种特殊的树:二叉树。选择树而不是那些基本的数据结构，是因 为在二叉树上进行查找非常快(而在链表上查找则不是这样)，为二叉树添加或删除元素 也非常快(而对数组执行添加或删除操作则不是这样)
一棵树最上面的节点称为 根节点，如果一个节点下面连接多个节点，那么该节点称为父节点，它下面的节点称为子 节点。一个节点可以有 0 个、1 个或多个子节点。没有任何子节点的节点称为叶子节点。
二叉树是一种特殊的树，它的子节点个数不超过两个。
从一个节点到另一个节点的这一组边称为路径，在图中用虚线表示。以某种特定顺序 访问树中所有的节点称为树的遍历。
二叉查找树是一种 特殊的二叉树，相对较小的值保存在左节点中，较大的值保存在右节点中。这一特性使得 查找的效率很高，对于数值型和非数值型的数据，比如单词和字符串，都是如此。
JavaScript实现二叉查找树(注意看注释)
// Node 对象既保存数据，也保存和其他节点的链接(left 和 right)，show() 方法用来显示 保存在节点中的数据。
function Node(data,left,right){
this.data = data;
this.count = 1;
this.left = left;
this.right = right;
this.show = function(){
return console.log(this.data);
}
}
// 现在可以创建一个类，用来表示二叉查找树(BST)。我们让类只包含一个数据成员:一个 表示二叉查找树根节点的 Node 对象。该类的构造函数将根节点初始化为 null，以此创建 一个空节点。
function BST(){
this.root = null;
// 用来向树中加入新节点
// 检查 BST 是否有根节点，如果没有，那么这是棵新树，该节点就是根节点，这个方法 到此也就完成了;否则，进入下一步。如果待插入节点不是根节点，那么就需要准备遍历 BST，找到插入的适当位置。该过程类 似于遍历链表。用一个变量存储当前节点，一层层地遍历 BST。
// (1) 设根节点为当前节点。
// (2) 如果待插入节点保存的数据小于当前节点，则设新的当前节点为原节点的左节点;反
// 之，执行第 4 步。
// (3) 如果当前节点的左节点为 null，就将新的节点插入这个位置，退出循环;反之，继续
// 执行下一次循环。
// (4) 设新的当前节点为原节点的右节点。
// (5) 如果当前节点的右节点为 null，就将新的节点插入这个位置，退出循环;反之，继续
// 执行下一次循环。
this.insert = function(data){
var n = new Node(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;
}
}
}
}
};
// 中序遍历的访问路径
// 中序遍历按照节点上的键值，以升序访问 BST 上的所有节点。先序遍历先访问根节点，然后以同样方式访问左子树和右子树。后序 遍历先访问叶子节点，从左子树到右子树，再到根节点。
this.inOrder = function(node){
if(!(node == null)){
this.inOrder(node.left);
node.show();
this.inOrder(node.right);
}
};
// 先序遍历
// 注意 inOrder() 和 preOrder() 方法的唯一区别，就是 if 语句中代码的顺序。在 inOrder() 方法中，show() 函数像三明治一样夹在两个递归调用之间;在 preOrder() 方法中，show() 函数放在两个递归调用之前。
this.preOrder = function(node){
if(!(node == null)){
node.show();
this.inOrder(node.left);
this.inOrder(node.right);
}
}
// 后序遍历
this.postOrder = function(node){
if(!(node == null)){
this.inOrder(node.left);
this.inOrder(node.right);
node.show();
}
}
// 查找最小值
// 查找 BST 上的最小值和最大值非常简单。因为较小的值总是在左子节点上，在 BST 上查找最小值，只需要遍历左子树，直到找到最后一个节点。
this.getMin = function(){
var current = this.root;
while (!(current.left == null)) {
current = current.left;
}
return current.data;
}
// 查找最大值
// 在 BST 上查找最大值，只需要遍历右子树，直到找到最后一个节点，该节点上保存的值即 为最大值。
this.getMax = function(){
var current = this.root;
while (!(current.right == null)) {
current = current.right;
}
return current.data;
}
// 查找给定值
// 在 BST 上查找给定值，需要比较该值和当前节点上的值的大小。通过比较，就能确定如果给定值不在当前节点时，该向左遍历还是向右遍历。
this.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;
}
// 从二叉查找树上删除节点
// 从 BST 中删除节点的第一步是判断当前节点是否包含待删除的数据，如果包含，则删除该 节点;如果不包含，则比较当前节点上的数据和待删除的数据。如果待删除数据小于当前 节点上的数据，则移至当前节点的左子节点继续比较;如果删除数据大于当前节点上的数 据，则移至当前节点的右子节点继续比较。
// 如果待删除节点是叶子节点(没有子节点的节点)，那么只需要将从父节点指向它的链接 指向 null。
// 如果待删除节点只包含一个子节点，那么原本指向它的节点就得做些调整，使其指向它的子节点。
// 最后，如果待删除节点包含两个子节点，正确的做法有两种:要么查找待删除节点左子树 上的最大值，要么查找其右子树上的最小值。
this.remove = function(data){
root = this.removeNode(this.root,data)
}
this.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;
}
}
// 计数
// BST 的一个用途是记录一组数据集中数据出现的次数。比如，可以使用 BST 记录考试成 绩的分布。给定一组考试成绩，可以写一段程序将它们加入一个 BST，如果某成绩尚未在 BST 中出现，就将其加入 BST;如果已经出现，就将出现的次数加 1。
// 为了解决该问题，我们来修改 Node 对象，为其增加一个记录成绩出现频次的成员，同时我 们还需要一个方法，当在 BST 中发现某成绩时，需要将出现的次数加 1，并且更新该节点。
this.update = function update(data){
var grade = this.find(data);
grade.count++;
return grade;
}
}
var nums = new BST();
nums.insert(23);
nums.insert(45);
nums.insert(16);
nums.insert(37);
nums.insert(3);
nums.insert(99);
nums.insert(99);
nums.insert(22);
// console.log("Inorder traversal: ");
// nums.inOrder(nums.root);
// nums.preOrder(nums.root)
nums.postOrder(nums.root);
console.log(nums.getMin());
console.log(nums.getMax());
console.log(nums.find(23));
console.log(nums.update(99))
console.log(nums.removeNode(99))
console.log(nums.update(99))
10、图和图算法
后续。
整理不易，且看且珍惜。
