JavaScriptデータ構造の二重連結リスト挿入ソート例を詳しく解説

ホームページ

ウェブフロントエンド

jsチュートリアル

JavaScriptデータ構造の二重連結リスト挿入ソート例を詳しく解説_JavaScriptスキル

WBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWB

May 16, 2016 pm 03:29 PM

javascript挿入ソート

この記事の例では、JavaScript データ構造での二重リンクリスト挿入ソートの実装方法を説明します。参考のために皆さんと共有してください。詳細は次のとおりです:

配列ストレージの前提下では、挿入ソートアルゴリズムでは、最悪の場合、挿入ポイントにターゲット要素を挿入するためのスペースを残すために、前の要素を継続的に後方に移動する必要があります。

リンクされたリストに切り替える場合、当然、そのような大量の移動を行う必要はありません。各ノードの先行ノード「ポインタ」に従って、前方の挿入ポイントを見つけた後、ターゲット値が直接削除されます。元のリンクリストを削除し、挿入ポイントでターゲット値を削除します。リンクリストを 2 つに分割して、ターゲットポイントに再接続します。

<!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）グローバルオブジェクトはブラウザのウィンドウであり、node.jsのグローバルです2）バイナリデータの処理に使用されるNode.jsの一意のバッファオブジェクト。 3）パフォーマンスと時間の処理にも違いがあり、環境に従ってコードを調整する必要があります。

JavaScriptコメント：//および / * *を使用するためのガイドMay 13, 2025 pm 03:49 PM

javascriptusestwotypesofcomments：シングルライン（//）およびマルチライン（//）

Python vs. JavaScript：開発者の比較分析May 09, 2025 am 12:22 AM

PythonとJavaScriptの主な違いは、タイプシステムとアプリケーションシナリオです。 1。Pythonは、科学的コンピューティングとデータ分析に適した動的タイプを使用します。 2。JavaScriptは弱いタイプを採用し、フロントエンドとフルスタックの開発で広く使用されています。この2つは、非同期プログラミングとパフォーマンスの最適化に独自の利点があり、選択する際にプロジェクトの要件に従って決定する必要があります。

Python vs. JavaScript：ジョブに適したツールを選択するMay 08, 2025 am 12:10 AM

PythonまたはJavaScriptを選択するかどうかは、プロジェクトの種類によって異なります。1）データサイエンスおよび自動化タスクのPythonを選択します。 2）フロントエンドとフルスタック開発のためにJavaScriptを選択します。 Pythonは、データ処理と自動化における強力なライブラリに好まれていますが、JavaScriptはWebインタラクションとフルスタック開発の利点に不可欠です。

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;それは、解釈されていることを解釈しました。

JavaScriptアプリケーション：フロントエンドからバックエンドまでMay 04, 2025 am 12:12 AM

JavaScriptは、フロントエンドおよびバックエンド開発に使用できます。フロントエンドは、DOM操作を介してユーザーエクスペリエンスを強化し、バックエンドはnode.jsを介してサーバータスクを処理することを処理します。 1.フロントエンドの例：Webページテキストのコンテンツを変更します。 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

ホットAIツール

Undresser.AI Undress

リアルなヌード写真を作成する AI 搭載アプリ

AI Clothes Remover

写真から衣服を削除するオンライン AI ツール。

Undress AI Tool

脱衣画像を無料で

Clothoff.io

AI衣類リムーバー

Video Face Swap

完全無料の AI 顔交換ツールを使用して、あらゆるビデオの顔を簡単に交換できます。

ホットツール

SAP NetWeaver Server Adapter for Eclipse

Eclipse を SAP NetWeaver アプリケーションサーバーと統合します。

SublimeText3 英語版

推奨: Win バージョン、コードプロンプトをサポート!

SecLists

SecLists は、セキュリティテスターの究極の相棒です。これは、セキュリティ評価中に頻繁に使用されるさまざまな種類のリストを 1 か所にまとめたものです。 SecLists は、セキュリティテスターが必要とする可能性のあるすべてのリストを便利に提供することで、セキュリティテストをより効率的かつ生産的にするのに役立ちます。リストの種類には、ユーザー名、パスワード、URL、ファジングペイロード、機密データパターン、Web シェルなどが含まれます。テスターはこのリポジトリを新しいテストマシンにプルするだけで、必要なあらゆる種類のリストにアクセスできるようになります。