JavaScriptデータ構造の二重連結リスト挿入ソート例を詳しく解説_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 プログラミングのすべての人に役立つことを願っています。
ホットAIツール
Undresser.AI Undress
リアルなヌード写真を作成する AI 搭載アプリ
AI Clothes Remover
写真から衣服を削除するオンライン AI ツール。
Undress AI Tool
脱衣画像を無料で
Clothoff.io
AI衣類リムーバー
Video Face Swap
完全無料の AI 顔交換ツールを使用して、あらゆるビデオの顔を簡単に交換できます。
人気の記事
ホットツール
メモ帳++7.3.1
使いやすく無料のコードエディター
SublimeText3 中国語版
中国語版、とても使いやすい
ゼンドスタジオ 13.0.1
強力な PHP 統合開発環境
ドリームウィーバー CS6
ビジュアル Web 開発ツール
SublimeText3 Mac版
神レベルのコード編集ソフト（SublimeText3）
ホットトピック
7642
15
1392
52
90
11
33
150
WebSocket と JavaScript を使用してオンライン音声認識システムを実装する方法
Dec 17, 2023 pm 02:54 PM
WebSocket と JavaScript を使用してオンライン音声認識システムを実装する方法 はじめに: 技術の継続的な発展により、音声認識技術は人工知能の分野の重要な部分になりました。 WebSocket と JavaScript をベースとしたオンライン音声認識システムは、低遅延、リアルタイム、クロスプラットフォームという特徴があり、広く使用されるソリューションとなっています。この記事では、WebSocket と JavaScript を使用してオンライン音声認識システムを実装する方法を紹介します。
WebSocket と JavaScript: リアルタイム監視システムを実装するための主要テクノロジー
Dec 17, 2023 pm 05:30 PM
WebSocketとJavaScript：リアルタイム監視システムを実現するためのキーテクノロジー はじめに： インターネット技術の急速な発展に伴い、リアルタイム監視システムは様々な分野で広く利用されています。リアルタイム監視を実現するための重要なテクノロジーの 1 つは、WebSocket と JavaScript の組み合わせです。この記事では、リアルタイム監視システムにおける WebSocket と JavaScript のアプリケーションを紹介し、コード例を示し、その実装原理を詳しく説明します。 1.WebSocketテクノロジー
JavaScript と WebSocket を使用してリアルタイムのオンライン注文システムを実装する方法
Dec 17, 2023 pm 12:09 PM
JavaScript と WebSocket を使用してリアルタイム オンライン注文システムを実装する方法の紹介: インターネットの普及とテクノロジーの進歩に伴い、ますます多くのレストランがオンライン注文サービスを提供し始めています。リアルタイムのオンライン注文システムを実装するには、JavaScript と WebSocket テクノロジを使用できます。 WebSocket は、TCP プロトコルをベースとした全二重通信プロトコルで、クライアントとサーバー間のリアルタイム双方向通信を実現します。リアルタイムオンラインオーダーシステムにおいて、ユーザーが料理を選択して注文するとき
WebSocketとJavaScriptを使ったオンライン予約システムの実装方法
Dec 17, 2023 am 09:39 AM
WebSocket と JavaScript を使用してオンライン予約システムを実装する方法 今日のデジタル時代では、ますます多くの企業やサービスがオンライン予約機能を提供する必要があります。効率的かつリアルタイムのオンライン予約システムを実装することが重要です。この記事では、WebSocket と JavaScript を使用してオンライン予約システムを実装する方法と、具体的なコード例を紹介します。 1. WebSocket とは何ですか? WebSocket は、単一の TCP 接続における全二重方式です。
JavaScript と WebSocket: 効率的なリアルタイム天気予報システムの構築
Dec 17, 2023 pm 05:13 PM
JavaScript と WebSocket: 効率的なリアルタイム天気予報システムの構築 はじめに: 今日、天気予報の精度は日常生活と意思決定にとって非常に重要です。テクノロジーの発展に伴い、リアルタイムで気象データを取得することで、より正確で信頼性の高い天気予報を提供できるようになりました。この記事では、JavaScript と WebSocket テクノロジを使用して効率的なリアルタイム天気予報システムを構築する方法を学びます。この記事では、具体的なコード例を通じて実装プロセスを説明します。私たちは
簡単な JavaScript チュートリアル: HTTP ステータス コードを取得する方法
Jan 05, 2024 pm 06:08 PM
JavaScript チュートリアル: HTTP ステータス コードを取得する方法、特定のコード例が必要です 序文: Web 開発では、サーバーとのデータ対話が頻繁に発生します。サーバーと通信するとき、多くの場合、返された HTTP ステータス コードを取得して操作が成功したかどうかを判断し、さまざまなステータス コードに基づいて対応する処理を実行する必要があります。この記事では、JavaScript を使用して HTTP ステータス コードを取得する方法を説明し、いくつかの実用的なコード例を示します。 XMLHttpRequestの使用
JavaScriptでinsertBeforeを使用する方法
Nov 24, 2023 am 11:56 AM
使用法: JavaScript では、insertBefore() メソッドを使用して、DOM ツリーに新しいノードを挿入します。このメソッドには、挿入される新しいノードと参照ノード (つまり、新しいノードが挿入されるノード) の 2 つのパラメータが必要です。
JavaScript と WebSocket: 効率的なリアルタイム画像処理システムの構築
Dec 17, 2023 am 08:41 AM
JavaScript は Web 開発で広く使用されているプログラミング言語であり、WebSocket はリアルタイム通信に使用されるネットワーク プロトコルです。 2 つの強力な機能を組み合わせることで、効率的なリアルタイム画像処理システムを構築できます。この記事では、JavaScript と WebSocket を使用してこのシステムを実装する方法と、具体的なコード例を紹介します。まず、リアルタイム画像処理システムの要件と目標を明確にする必要があります。リアルタイムの画像データを収集できるカメラ デバイスがあるとします。
