DIV CSS 佈局教程網

JavaScript 資料結構與演算法:列表(List)完整實作
編輯:關於JavaScript     

前言:日常生活中我們經常使用列表。去購物前列下要買的東西,考完試後學校公布成績排名,這些都是列表。電腦裡同樣大量使用列表。那麼列表適合用在什麼場合,又不適合用在什麼場合?

答案是:當列表元素數量不多時很合適,因為對列表中的元素進行查找或排序時效率還算不錯;反之,元素數量龐大時就不適合了,這時該考慮雜湊表、樹或其他結構。

一、列表的抽象資料型別定義

要設計列表的抽象資料型別,得先想清楚它應該具備哪些屬性、支援哪些操作。

列表是一組有序的資料,每個資料項稱為元素。在 JavaScript 中,列表元素可以是任意資料型別,且元素數量沒有事先約定,實際上限只受程式記憶體限制。

基于此,我們可以規劃出三個屬性:

  • listSize:保存列表中元素的個數。
  • pos:列表的目前位置,也就是目前元素的索引。
  • dataStore:初始化一個空陣列來保存元素;搭配 pos 即可取出目前元素,寫成 dataStore[pos]。

方法則包含 append、remove、find、length、toString、insert、clear、contains,以及一組游標操作 front、end、prev、next、curPos、moveTo、getElement。

二、實作 List 類別

依據上述定義,我們可以用「建構函式 + 原型」的模式實作出 List 類別:

function List() {
  this.listSize = 0;   // 列表的元素個數
  this.pos = 0;        // 列表目前位置
  this.dataStore = []; // 初始化一個空陣列來保存列表元素
}

List.prototype = {

  // 給列表末尾添加元素
  append: function(element) {
    var self = this;
    self.dataStore[this.listSize++] = element;
  },

  // 從列表中刪除元素
  remove: function(element) {
    var self = this;
    var curIndex = self.find(element);
    if (curIndex > -1) {
      self.dataStore.splice(curIndex, 1);
      --self.listSize;
      return true;
    }
    return false;
  },

  // 查找列表中的元素,回傳索引
  find: function(element) {
    var self = this;
    for (var i = 0, dataLen = self.dataStore.length; i < dataLen; i++) {
      if (self.dataStore[i] == element) {
        return i;
      }
    }
    return -1;
  },

  // 回傳列表中元素的個數
  length: function() {
    return this.listSize;
  },

  // 顯示列表中的元素
  toString: function() {
    return this.dataStore;
  },

  /*
   * 在指定元素後面插入一個元素
   * @param element      要插入的元素
   * @param elementAfter 插入到哪個元素之後
   */
  insert: function(element, elementAfter) {
    var self = this;
    var insertPos = self.find(elementAfter);
    if (insertPos > -1) {
      self.dataStore.splice(insertPos + 1, 0, element);
      ++self.listSize;
      return true;
    }
    return false;
  },

  // 清空列表中的所有元素
  clear: function() {
    delete this.dataStore;
    this.dataStore = [];
    this.listSize = this.pos = 0;
  },

  // 判斷給定的元素是否在列表中
  contains: function(element) {
    var self = this;
    for (var i = 0, ilen = self.dataStore.length; i < ilen; i++) {
      if (self.dataStore[i] == element) {
        return true;
      }
    }
    return false;
  },

  // 將目前位置移動到第一個位置
  front: function() {
    this.pos = 0;
  },

  // 將目前位置移動到最後一個位置
  end: function() {
    this.pos = this.listSize - 1;
  },

  // 將目前位置往前移一位
  prev: function() {
    if (this.pos > 0) {
      --this.pos;
    }
  },

  // 將目前位置往後移一位
  next: function() {
    if (this.pos < this.listSize - 1) {
      ++this.pos;
    }
  },

  // 回傳列表目前位置
  curPos: function() {
    return this.pos;
  },

  // 將目前位置移動到指定位置
  moveTo: function(n) {
    this.pos = n;
  },

  // 回傳目前位置的元素
  getElement: function() {
    return this.dataStore[this.pos];
  }
};

設計上的觀察

這個實作把「資料存放」與「游標位置」分開管理,因此 pos 可以獨立移動而不影響資料本身,這正是列表能靈活遍歷的原因。其中 find 採的是線性搜尋,時間複雜度 O(n),這也解釋了為何列表不適合大量資料——若元素必須保持有序且需頻繁查找,改用二分搜尋或哈希結構會快得多。

另外,contains 與 find 邏輯幾乎相同,實作上可以讓 contains 直接呼叫 find(element) > -1 來消除重複程式碼。掌握這種「先定義抽象型別、再逐步實作方法」的思維方式,比記住某個具體結構更有價值——之後設計自己的抽象類別時,就能沿用好習慣。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved