数据结构:数组和链表
Liber 2017-03-21 20:54

新建一个html文件,body里面含有两个div,一个div里含有字符串4,2,5,7,1,3, 一个div为空。同时建立一个按钮叫pop,一个按钮叫push,push按钮旁边再建立一个text input。

实现以下效果:

(1) 空的div里 显示 将第一个div里数字排序后的结果

(2) 点击pop后第一个div里的最后一个数字消失,同时更新排序结果

(3) 在text input里输入一个数字,点击push按钮后将新的数字添加到第一个div数字字符串的结尾,同时更新排序结果


api-solution.js:

/*
#### 使用ECMAScript提供的sort API实现

#### 思路:
- 使用两个数组分别存放未排序的数组以及排好序的数组:original, sorted
- 每次pop操作,调用original的pop方法,然后复制original对其调用sort方法,得到新的sorted数组
- 同样的方式处理push操作

#### 缺点:
api-solution的主要问题在于,每次入栈出栈都要执行sort
而sort(v8的实现是优化过的快排)的时间复杂度平均为O(nlogn)

#### 优化方案:
请参见optimized-solution.js
*/

var utils = {
  compare: function (value1, value2) {
    return value1 - value2;
  },
  sort: function (arr) {
    return arr.concat().sort(this.compare);
  }
};

var app = {
  original: [],
  sorted: [],

  initialize: function () {
    this.initOriginal();
    this.initSorted();
    this.render();

    this.subscribe();
  },

  initOriginal: function () {
    var stringArr = document.querySelector('#original').innerHTML.split(',');
    this.original = stringArr.map(function (item) {
      return parseInt(item, 10);
    });
  },

  initSorted: function () {
    this.sorted = utils.sort(this.original);
  },

  subscribe: function () {
    document.querySelector('#pop').addEventListener('click', (function () {
      this.original.pop();
      this.sorted = utils.sort(this.original);

      this.render();
    }).bind(this));

    document.querySelector('#push').addEventListener('click', (function () {
      var input = document.querySelector('input');
      var number = parseInt(input.value, 10);

      if (!isNaN(number)) {
        this.original.push(number);
        this.sorted = utils.sort(this.original);
      }

      input.value = '';
      this.render();
    }).bind(this));
  },

  render: function () {
    document.querySelector('#original').innerHTML = this.original.join(',');
    document.querySelector('#sorted').innerHTML = this.sorted.join(',');
  }
};

app.initialize();


optimized-solution.js:

/*
#### 思路:
- 利用Hash找到pop元素的位置 - O(1)
- 利用链表根据找到的位置进行删除 - O(1)
- 利用链表遍历hash在相应位置进行插入 - O(logn)

#### 具体实现:
- 初始化两个数组original, sorted
- 初始化一个哈希linkListHash,其key随机生成,其值为对象,存放original的值,对象之间实现成一个双向链表
- 初始化一个数组originalList,每一项的值是一个对象,存放original对应的值和该值在linkListHash中对应的key
- 对originalList进行pop出栈,根据出栈元素的key找到linkListHash中对应的属性,在链表中删除出栈元素,最后删除该属性
- 对originalList进行push入栈,遍历链表,找到相应的位置插入入栈元素,为linkListHash添加新key及其值
*/

var utils = {
  compare: function (value1, value2) {
    return value1 - value2;
  },
  sort: function (arr) {
    return arr.concat().sort(this.compare);
  },
  findKey: function (hash, data) {
    for (var key in hash) {
      if (hash[key].data === data) {
        return key;
      }
    }
  }
};

var app = {
  original: [],
  sorted: [],
  linkListHash: {},
  originalList: [],

  head: null,

  initialize: function () {
    this.initOriginal();
    this.initSorted();
    this.initLinkListHash();
    this.initOriginalList();
    this.render();

    this.subscribe();
  },

  initOriginal: function () {
    var stringArr = document.querySelector('#original').innerHTML.split(',');
    this.original = stringArr.map(function (item) {
      return parseInt(item, 10);
    });
  },

  initSorted: function () {
    this.sorted = utils.sort(this.original);
  },

  initLinkListHash: function () {
    var head = null;
    var linkListHash = {};
    var lastNode = null;

    for (var i = 0; i < this.sorted.length; i++) {
      var obj = {
        data: this.sorted[i],
        prev: lastNode
      };
      if (!lastNode) {
        head = obj;
      } else {
        lastNode.next = obj;
      }
      linkListHash[Math.random()] = obj;
      lastNode = obj;
    }

    this.head = head;
    this.linkListHash = linkListHash;
  },

  initOriginalList: function () {
    var originalList = [];
    for (var i = 0; i < this.original.length; i++) {
      var obj = {
        data: this.original[i],
        key: utils.findKey(this.linkListHash, this.original[i])
      };
      originalList.push(obj);
    }

    this.originalList = originalList;
  },

  subscribe: function () {
    document.querySelector('#pop').addEventListener('click', (function () {
      this.original.pop();
      this.popHash();

      this.render();
    }).bind(this));

    document.querySelector('#push').addEventListener('click', (function () {
      var input = document.querySelector('input');
      var number = parseInt(input.value, 10);

      if (!isNaN(number)) {
        this.original.push(number);
        this.pushHash(number);
      }

      input.value = '';
      this.render();
    }).bind(this));
  },

  popHash: function () {
    if (this.originalList.length === 0) {
      return;
    }

    var key = (this.originalList.pop()).key;
    var targetObj = this.linkListHash[key];

    if (!targetObj.next && !targetObj.prev) {
      this.head = null;
    } else if (!targetObj.prev) {
      this.head = targetObj.next;
      targetObj.next.prev = null;
    } else if (targetObj.next) {
      targetObj.prev.next = targetObj.next;
      targetObj.next.prev = targetObj.prev;
    } else {
      targetObj.prev.next = null;
      targetObj.prev = null;
    }

    delete this.linkListHash[key];
  },

  pushHash: function (data) {
    var key = Math.random();
    this.originalList.push({data: data, key: key});

    var newObj = {
      data: data,
      key: key,
      next: null,
      prev: null
    };
    var node = this.head;

    if (!node) {
      this.head = newObj;
    } else {
      while (node) {
        if (data < node.data) {
          if (!node.prev) {
            newObj.next = node;
            node.prev = newObj;
            this.head = newObj;
          } else {
            node.prev.next = newObj;
            newObj.prev = node.prev;
            newObj.next = node;
            node.prev = newObj;
          }
          break;
        } else if (!node.next) {
          node.next = newObj;
          newObj.prev = node;
          break;
        }

        node = node.next;
      }
    }

    this.linkListHash[key] = newObj;
  },

  renderOriginal: function () {
    document.querySelector('#original').innerHTML = this.original.join(',');
  },

  renderSorted: function () {
    var arr = [];
    var node = this.head;
    while (node) {
      arr.push(node.data);
      node = node.next;
    }
    document.querySelector('#sorted').innerHTML = arr.join(',');
  },

  render: function () {
    this.renderOriginal();
    this.renderSorted();
  }
};

app.initialize();