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、图和图算法

后续。

整理不易，且看且珍惜。