欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

javascript數(shù)據(jù)結(jié)構(gòu)之雙鏈表插入排序?qū)嵗斀?/h1>
 更新時間：2015年11月25日 15:33:56   作者：Jimmy.Yang  
這篇文章主要介紹了javascript數(shù)據(jù)結(jié)構(gòu)之雙鏈表插入排序?qū)崿F(xiàn)方法,較為詳細(xì)的分析了插入排序的原理及雙鏈表插入排序的實現(xiàn)技巧,對于學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)具有一定參考借鑒價值,需要的朋友可以參考下

本文實例講述了javascript數(shù)據(jù)結(jié)構(gòu)之雙鏈表插入排序?qū)崿F(xiàn)方法。分享給大家供大家參考，具體如下：

數(shù)組存儲前提下，插入排序算法，在最壞情況下，前面的元素需要不斷向后移，以便在插入點留出空位，讓目標(biāo)元素插入。

換成鏈表時，顯然無需做這種大量移動，根據(jù)每個節(jié)點的前驅(qū)節(jié)點“指針”，向前找到插入點后，直接把目標(biāo)值從原鏈表上摘下，然后在插入點把鏈表斷成二截，然后跟目標(biāo)點重新接起來即可。

<!doctype html>
<html>
<head>
  <title>雙鏈表-插入排序</title>
  <meta http-equiv="Content-Type" content="text/html; charset=gb2312" />
</head>
<script type="text/javascript">
  //節(jié)點類
  var Node = function (pData) {
    this.next = null; //后繼“指針”
    this.prev = null; //前驅(qū)"指針"
    this.data = pData;
  }
  //單鏈表(約定：頭節(jié)點不放內(nèi)容，當(dāng)哨兵位，有效元素從頭節(jié)點后的第1個元素開始)
  var DbLinkList = function () {
    this.head = new Node(null); //頭節(jié)點   
    //插入新元素
    this.insert = function (pNodeValue) {
      var newNode = new Node(pNodeValue);
      //如果只有頭節(jié)點
      if (this.head.next == null) {
        this.head.next = newNode;
        newNode.prev = this.head;
        return;
      }
      //否則遍歷找到尾節(jié)點
      var p = this.head;
      while (p.next != null) {
        p = p.next;
      }
      p.next = newNode;
      newNode.prev = p;
    }
    //獲取第n個元素的數(shù)據(jù)值
    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;
    }
    //取尾節(jié)點
    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的前驅(qū)節(jié)點，不用調(diào)整，
        //忽略，直接進(jìn)入下一輪
        if (t.next == p) {
          p = p.next;
          continue;
        }
        //將p的后續(xù)節(jié)點先保護起來，以便下一輪循環(huán)時確定起始位置
        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(); //打印輸出，調(diào)試用  
        //重新將p定位到下一輪循環(huán)的"正確"起始節(jié)點
        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>

運行結(jié)果如下：

 --排序前---

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程序設(shè)計有所幫助。

相關(guān)文章

  • 10個在JavaScript開發(fā)中常遇到的BUG

    10個在JavaScript開發(fā)中常遇到的BUG

    給大家詳細(xì)著整理了在JavaScript開發(fā)中大家經(jīng)常遇到的BUG和問題，需要的朋友參考學(xué)習(xí)下吧。
    2017-12-12
  • 微信外喚起微信小程序的方法詳解

    微信外喚起微信小程序的方法詳解

    這篇文章主要介紹了微信外喚起微信小程序的方法,結(jié)合實例形式詳細(xì)分析了微信外喚起微信小程序的相關(guān)步驟、原理與操作注意事項,需要的朋友可以參考下
    2023-07-07
  • js最簡單的雙向綁定實例講解

    js最簡單的雙向綁定實例講解

    下面小編就為大家分享一篇js最簡單的雙向綁定實例講解，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧
    2018-01-01
  • 獲取數(shù)組中最大最小值方法js代碼(自寫)

    獲取數(shù)組中最大最小值方法js代碼(自寫)

    經(jīng)搜索獲取數(shù)組中最大最小值的方法實在是太多了，不過大同小異，本文自寫了一個，有需要的朋友可以參考下，希望對大家有所幫助
    2013-08-08
  • 微信小程序在其他頁面監(jiān)聽globalData中值的變化

    微信小程序在其他頁面監(jiān)聽globalData中值的變化

    這篇文章主要給大家介紹了關(guān)于微信小程序如何在其他頁面監(jiān)聽globalData中值的變化的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，對大家學(xué)習(xí)或者使用微信小程序具有一定的參考學(xué)習(xí)價值，需要的朋友們下面來一起學(xué)習(xí)學(xué)習(xí)吧
    2019-07-07
  • Javascript實現(xiàn)獲取窗口的大小和位置代碼分享

    Javascript實現(xiàn)獲取窗口的大小和位置代碼分享

    這篇文章主要分享了一段Javascript實現(xiàn)獲取窗口的大小和位置代碼，兼容性非常好，這里推薦給大家
    2014-12-12
  • JavaScript confirm選擇判斷

    JavaScript confirm選擇判斷

    可以判斷confirm選擇了是否
    2008-10-10
  • 淺談redux, koa, express 中間件實現(xiàn)對比解析

    淺談redux, koa, express 中間件實現(xiàn)對比解析

    這篇文章主要介紹了淺談redux, koa, express 中間件實現(xiàn)對比解析，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2019-05-05
  • js確認(rèn)刪除對話框效果的示例代碼

    js確認(rèn)刪除對話框效果的示例代碼

    本篇文章主要是對js確認(rèn)刪除對話框效果的示例代碼進(jìn)行了介紹，需要的朋友可以過來參考下，希望對大家有所幫助
    2014-02-02
  • JS實現(xiàn)隨機抽取三人

    JS實現(xiàn)隨機抽取三人

    這篇文章主要為大家詳細(xì)介紹了JS實現(xiàn)隨機抽取三人，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下
    2019-11-11

最新評論