DIV CSS 佈局教程網

用 JavaScript 實作鏈結串列資料結構與氣泡排序
編輯:JavaScript綜合知識     

鏈結串列(Linked List)是一種以節點串接而成的動態資料結構,每個節點保存資料與指向下一個節點的參照。用 JavaScript 來實作它並不困難,而且能進一步在其上擴充排序、增刪改節點等操作。本文示範如何建立串列並以氣泡排序將其由小到大排列。

首先定義節點與串列本身,串列提供「列印」與「頭插法新增節點」兩個基本方法:

function Node(){
  this.data = null;
  this.next = null;
}

function GenericList(){
  this.head = null;
  this.current = null;

  // 列印所有節點
  this.print = function(){
    this.current = this.head;
    while (this.current != null){
      alert(this.current.data);
      this.current = this.current.next;
    }
  };

  // 以頭插法建立鏈結串列
  this.addHead = function(t){
    var node = new Node();
    node.data = t;
    node.next = this.head;
    this.head = node;
  };
}

接著讓排序類別繼承串列,並實作氣泡排序。排序時透過交換相鄰節點的方式,把較大的值逐步往後推:

function SortList(){
  // 氣泡排序鏈結串列
  this.BubbleSort = function(){
    if (this.head == null || this.head.next == null) return;
    var swapped;
    do {
      this.previous = null;
      this.current = this.head;
      swapped = false;
      while (this.current.next != null){
        if (this.current.data - this.current.next.data > 0){
          var tmp = this.current.next;
          this.current.next = this.current.next.next;
          tmp.next = this.current;
          if (this.previous == null) this.head = tmp;
          else this.previous.next = tmp;
          this.previous = tmp;
          swapped = true;
        } else {
          this.previous = this.current;
          this.current = this.current.next;
        }
      }
    } while (swapped);
  };
}

SortList.prototype = new GenericList();

最後用一個立即執行的主程式建立串列、印出未排序結果、排序後再印一次:

(function Main(){
  var sl = new SortList();
  for (var i = 0; i < arguments.length; i++){
    sl.addHead(arguments[i]);
  }
  alert("未排序的鏈結串列");
  sl.print();
  sl.BubbleSort();
  alert("已排序的鏈結串列(從小到大)");
  sl.print();
})("1", "2", "3", "4");

透過 SortList.prototype = new GenericList(),SortList 繼承了串列的 head、current 與 print 等方法,展現了原型鏈在 JavaScript 中的應用。在這個基礎上,讀者可以繼續擴充各種排序演算法與增刪改節點的功能。

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