DIV CSS 佈局教程網

 DIV+CSS佈局教程網 >> 網頁腳本 >> JavaScript入門知識 >> 關於JavaScript >> javascript數據結構之雙鏈表插入排序實例詳解
javascript數據結構之雙鏈表插入排序實例詳解
編輯:關於JavaScript     

本文實例講述了javascript數據結構之雙鏈表插入排序實現方法。分享給大家供大家參考,具體如下:

數組存儲前提下,插入排序算法,在最壞情況下,前面的元素需要不斷向後移,以便在插入點留出空位,讓目標元素插入。

換成鏈表時,顯然無需做這種大量移動,根據每個節點的前驅節點“指針”,向前找到插入點後,直接把目標值從原鏈表上摘下,然後在插入點把鏈表斷成二截,然後跟目標點重新接起來即可。

<!doctype html>
<html>
<head>
  <title>雙鏈表-插入排序</title>
  <meta http-equiv="Content-Type" content="text/html; charset=gb2312" />
</head>
<script type="text/javascript">
  //節點類
  var Node = function (pData) {
    this.next = null; //後繼“指針”
    this.prev = null; //前驅"指針"
    this.data = pData;
  }
  //單鏈表(約定:頭節點不放內容,當哨兵位,有效元素從頭節點後的第1個元素開始)
  var DbLinkList = function () {
    this.head = new Node(null); //頭節點   
    //插入新元素
    this.insert = function (pNodeValue) {
      var newNode = new Node(pNodeValue);
      //如果只有頭節點
      if (this.head.next == null) {
        this.head.next = newNode;
        newNode.prev = this.head;
        return;
      }
      //否則遍歷找到尾節點
      var p = this.head;
      while (p.next != null) {
        p = p.next;
      }
      p.next = newNode;
      newNode.prev = p;
    }
    //獲取第n個元素的數據值
    this.getData = function (index) {
      if (index < 1 || index > this.size) {
        return null;
      }
      var p = this.head;
      var i = 1;
      while (p.next != null && i <= index) {
        p = p.next;
        i += 1;
      }
      return p.data;
    }
    //取尾節點
    this.getTail = function () {
      if (this.head.next == null) {
        return null;
      }
      var p = this.head.next;
      while (p.next != null) {
        p = p.next;
      }
      return p;
    }
    //刪除指定位置的元素
    this.removeAt = function (index) {
      if (index < 1 || index > this.size) {
        return null;
      }
      var p = this.head;
      var i = 1;
      //從頭開始遍歷,找到index位置的前一個元素
      while (p.next != null && i < index) {
        p = p.next;
        i += 1;
      }
      p.next = p.next.next; //修改index位置前一個元素的後繼指針
      p.next.prev = p;
      return p.data; //返回刪除元素的值    
    }
    //打印所有元素
    this.print = function () {
      document.write("<br/>");
      if (this.head.next == null) {
        return;
      }
      var p = this.head.next;
      while (p.next != null) {
        document.write(p.data + " ");
        p = p.next;
      }
      document.write(p.data + " "); //最後一個元素,需要單獨打印
      document.write("<br/>");
    }
    //從後打印所有元素
    this.printFromBack = function () {
      document.write("該鏈表共有" + this.size + "個元素,從後向前分別為:<br/>");
      var tail = this.getTail();
      var p = tail;
      if (p == null) {
        return;
      }
      while (p.prev != null) {
        document.write(p.data + " ");
        p = p.prev;
      }
      document.write("<br/>");
    }
    //插入排序
    this.insertSort = function () {
      if (this.head.next == null || this.head.next.next == null) {
        return;
      }
      var p = this.head.next;
      while (true) {
        if (p == null) {
          return;
        }
        var t = p.prev;
        //向前查找p之前的插入點
        while (t.prev != null && t.data > p.data) {
          t = t.prev;
        }
        //如果插入點就是p的前驅節點,不用調整,
        //忽略,直接進入下一輪
        if (t.next == p) {
          p = p.next;
          continue;
        }
        //將p的後續節點先保護起來,以便下一輪循環時確定起始位置
        var x = p.next;
        //將p從鏈表上摘下
        if (p.next != null) {
          p.next.prev = p.prev;
        }
        p.prev.next = p.next;
        //p插入到t之後
        t.next.prev = p;
        p.next = t.next;
        t.next = p;
        p.prev = t;
        this.print(); //打印輸出,調試用  
        //重新將p定位到下一輪循環的"正確"起始節點
        p = x;
      }
    }
  }
  var linkTest = new DbLinkList();
  linkTest.insert(10);
  linkTest.insert(9);
  linkTest.insert(8);
  linkTest.insert(7);
  linkTest.insert(6);
  linkTest.insert(5);
  linkTest.insert(4);
  linkTest.insert(3);
  linkTest.insert(2);
  linkTest.insert(1);
  document.write("--排序前---<br/>")
  linkTest.print();
  linkTest.insertSort();
  document.write("<br/>--排序後---<br/>")
  linkTest.print();
</script>
</html>

運行結果如下:

 --排序前---

10 9 8 7 6 5 4 3 2 1 

9 10 8 7 6 5 4 3 2 1 

8 9 10 7 6 5 4 3 2 1 

7 8 9 10 6 5 4 3 2 1 

6 7 8 9 10 5 4 3 2 1 

5 6 7 8 9 10 4 3 2 1 

4 5 6 7 8 9 10 3 2 1 

3 4 5 6 7 8 9 10 2 1 

2 3 4 5 6 7 8 9 10 1 

1 2 3 4 5 6 7 8 9 10 

--排序後---

1 2 3 4 5 6 7 8 9 10

希望本文所述對大家JavaScript程序設計有所幫助。

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