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

Python vs. JavaScript：学习曲线和易用性Apr 16, 2025 am 12:12 AM

Python更适合初学者，学习曲线平缓，语法简洁；JavaScript适合前端开发，学习曲线较陡，语法灵活。1.Python语法直观，适用于数据科学和后端开发。2.JavaScript灵活，广泛用于前端和服务器端编程。

Python vs. JavaScript：社区，图书馆和资源Apr 15, 2025 am 12:16 AM

Python和JavaScript在社区、库和资源方面的对比各有优劣。1)Python社区友好，适合初学者，但前端开发资源不如JavaScript丰富。2)Python在数据科学和机器学习库方面强大，JavaScript则在前端开发库和框架上更胜一筹。3)两者的学习资源都丰富，但Python适合从官方文档开始，JavaScript则以MDNWebDocs为佳。选择应基于项目需求和个人兴趣。

从C/C到JavaScript：所有工作方式Apr 14, 2025 am 12:05 AM

从C/C 转向JavaScript需要适应动态类型、垃圾回收和异步编程等特点。1）C/C 是静态类型语言，需手动管理内存，而JavaScript是动态类型，垃圾回收自动处理。2）C/C 需编译成机器码，JavaScript则为解释型语言。3）JavaScript引入闭包、原型链和Promise等概念，增强了灵活性和异步编程能力。

JavaScript引擎：比较实施Apr 13, 2025 am 12:05 AM

不同JavaScript引擎在解析和执行JavaScript代码时，效果会有所不同，因为每个引擎的实现原理和优化策略各有差异。1.词法分析：将源码转换为词法单元。2.语法分析：生成抽象语法树。3.优化和编译：通过JIT编译器生成机器码。4.执行：运行机器码。V8引擎通过即时编译和隐藏类优化，SpiderMonkey使用类型推断系统，导致在相同代码上的性能表现不同。

超越浏览器：现实世界中的JavaScriptApr 12, 2025 am 12:06 AM

JavaScript在现实世界中的应用包括服务器端编程、移动应用开发和物联网控制：1.通过Node.js实现服务器端编程，适用于高并发请求处理。2.通过ReactNative进行移动应用开发，支持跨平台部署。3.通过Johnny-Five库用于物联网设备控制，适用于硬件交互。

使用Next.js（后端集成）构建多租户SaaS应用程序Apr 11, 2025 am 08:23 AM

我使用您的日常技术工具构建了功能性的多租户SaaS应用程序（一个Edtech应用程序），您可以做同样的事情。首先，什么是多租户SaaS应用程序？多租户SaaS应用程序可让您从唱歌中为多个客户提供服务

如何使用Next.js（前端集成）构建多租户SaaS应用程序Apr 11, 2025 am 08:22 AM

本文展示了与许可证确保的后端的前端集成，并使用Next.js构建功能性Edtech SaaS应用程序。前端获取用户权限以控制UI的可见性并确保API要求遵守角色库

JavaScript：探索网络语言的多功能性Apr 11, 2025 am 12:01 AM

JavaScript是现代Web开发的核心语言，因其多样性和灵活性而广泛应用。1)前端开发：通过DOM操作和现代框架（如React、Vue.js、Angular）构建动态网页和单页面应用。2)服务器端开发：Node.js利用非阻塞I/O模型处理高并发和实时应用。3)移动和桌面应用开发：通过ReactNative和Electron实现跨平台开发，提高开发效率。

See all articles