数据结构与算法

  • 集合

    集合是由一组无序且唯一的项组成的。这个数据结构使用了与有限集合相同的数学概念,但应用在计算机科学的数据结构中。在数学中,集合也有并集、交集、差集等基本操作,在下面的代码中也会实现这些操作。

    值的相等:因为 Set 中的值总是唯一的,所以需要判断两个值是否相等。判断相等的算法与严格相等(===操作符)不同。具体来说,对于 Set , +0 (+0 严格相等于-0)和-0是不同的值。尽管在最新的 ECMAScript 6规范中这点已被更改。从Gecko 29.0和 recent nightly Chrome开始,Set 视 +0 和 -0 为相同的值。另外,NaN和undefined都可以

  • 1、 图

    图是网络结构的抽象模型。图是一组由边连接的节点,任何二元关系都可以用图来表示。

    1.1、图的相关概念

    一个图G = (V,E)由以下元素组成。

    • V:一组顶点
    • E:一组边,连接V中的顶点

    下图表示一个图:

    20170305013731

    由一条边连接在一起的顶点称为相邻顶点。比如上图的A和B是相邻的,A和D是相邻的,A和C是相邻的,A和E不是相邻的。一个顶点的度是其相邻顶点的数量。比如,A和其他三个顶点相连接,因此,A的度为3;E和其他两个顶点相连,因此E的度为2。路径是顶点v1,v2,...,vk的一个连续序列,其中v[i]和v[i+1]是相邻的。以上的图为例,其中的路径有ABEI和ACDG。

    1.2、图的表

  • 1、排序

    1.1、冒泡排序

    冒泡排序比较任何两个相邻的项,如果第一个项比第二个大,则交换它们。元素项向上移动至正确的顺序,就好像气泡升至表面一样,冒泡排序因此得名。

    function ArrayList(){
        var array = [];
        this.insert = function(item){
            array.push(item);
        };
        var swap = function(index1, index2){ //交换值
            var aux = array[index1];
            array[index1] = arra
  • 1、栈

    栈是一种遵从后进先出(LIFO)原则的有序集合。新添加的或待删除的元素都保存在栈的末尾。称作栈顶,另一端就叫栈底。在栈里,新元素都靠近栈顶,旧元素都靠近栈底。现在通过数组的方法来实现栈,代码如下:

    function Stack() {
      var items = [];
      this.push = function(element){//添加一个(或几个)新元素到栈顶
        items.push(element);
      };
      this.pop = function(){//移除栈顶的元素,同时返回被移除元素
        return items.pop();
      };
      this.
  • 1、字典

    字典存储的是[键,值]对,其中键名是用来查询特定元素的。字典和集合很相似,集合以[值,值]的形式存储元素,字典则是以[键,值]的形式来存储元素。字典也称映射。示例代码如下:

    function Dictionary(){
        var items = {};
        this.set = function(key, value){
            items[key] = value; 
        };
        this.remove = function(key){
            if (this.has(key)){
                delete items[key];