javascript資料結構之雙鍊錶插入排序實例詳解_javascript技巧-js教程-PHP中文網

首頁

web前端

js教程

javascript資料結構之雙鍊錶插入排序實例詳解_javascript技巧

WBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWB

May 16, 2016 pm 03:29 PM

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程式設計有所幫助。

陳述

本文內容由網友自願投稿，版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容，請聯絡admin@php.cn

JavaScript數據類型：瀏覽器和nodejs之間是否有區別？May 14, 2025 am 12:15 AM

JavaScript核心數據類型在瀏覽器和Node.js中一致，但處理方式和額外類型有所不同。 1)全局對像在瀏覽器中為window，在Node.js中為global。 2)Node.js獨有Buffer對象，用於處理二進制數據。 3)性能和時間處理在兩者間也有差異，需根據環境調整代碼。

JavaScript評論：使用//和 / * * / * / * /May 13, 2025 pm 03:49 PM

JavaScriptusestwotypesofcomments:single-line(//)andmulti-line(//).1)Use//forquicknotesorsingle-lineexplanations.2)Use//forlongerexplanationsorcommentingoutblocksofcode.Commentsshouldexplainthe'why',notthe'what',andbeplacedabovetherelevantcodeforclari

Python vs. JavaScript：開發人員的比較分析May 09, 2025 am 12:22 AM

Python和JavaScript的主要區別在於類型系統和應用場景。 1.Python使用動態類型，適合科學計算和數據分析。 2.JavaScript採用弱類型，廣泛用於前端和全棧開發。兩者在異步編程和性能優化上各有優勢，選擇時應根據項目需求決定。

Python vs. JavaScript：選擇合適的工具May 08, 2025 am 12:10 AM

選擇Python還是JavaScript取決於項目類型：1)數據科學和自動化任務選擇Python；2)前端和全棧開發選擇JavaScript。 Python因其在數據處理和自動化方面的強大庫而備受青睞，而JavaScript則因其在網頁交互和全棧開發中的優勢而不可或缺。

Python和JavaScript：了解每個的優勢May 06, 2025 am 12:15 AM

Python和JavaScript各有優勢，選擇取決於項目需求和個人偏好。 1.Python易學，語法簡潔，適用於數據科學和後端開發，但執行速度較慢。 2.JavaScript在前端開發中無處不在，異步編程能力強，Node.js使其適用於全棧開發，但語法可能複雜且易出錯。

JavaScript的核心：它是在C還是C上構建的？May 05, 2025 am 12:07 AM

javascriptisnotbuiltoncorc; sanInterpretedlanguagethatrunsonenginesoftenwritteninc.1）JavascriptwasdesignedAsignedAsalightWeight，drackendedlanguageforwebbrowsers.2）Enginesevolvedfromsimpleterterpretpretpretpretpreterterpretpretpretpretpretpretpretpretpretcompilerers，典型地，替代品。

JavaScript應用程序：從前端到後端May 04, 2025 am 12:12 AM

JavaScript可用於前端和後端開發。前端通過DOM操作增強用戶體驗，後端通過Node.js處理服務器任務。 1.前端示例：改變網頁文本內容。 2.後端示例：創建Node.js服務器。

Python vs. JavaScript：您應該學到哪種語言？May 03, 2025 am 12:10 AM

選擇Python還是JavaScript應基於職業發展、學習曲線和生態系統：1)職業發展：Python適合數據科學和後端開發，JavaScript適合前端和全棧開發。 2)學習曲線：Python語法簡潔，適合初學者；JavaScript語法靈活。 3)生態系統：Python有豐富的科學計算庫，JavaScript有強大的前端框架。

See all articles