双链表插入排序实例代码

吐槽君 分类:实例代码

本章节分享一段代码实例,它实现了双链表插入排序功能。

需要的朋友可以做一下参考,在代码之后会有简单的介绍,代码实例如下:

<!doctype html>
<html>
<head>
<meta charset=" utf-8">
<meta name="author" content="http://www.pipipi.net/" />
<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>
</head>
<body>
</body>
</html>

数组存储前提下,插入排序算法,在最坏情况下,前面的元素需要不断向后移,以便在插入点留出空位,让目标元素插入。

换成链表时,显然无需做这种大量移动,根据每个节点的前驱节点“指针”,向前找到插入点后,直接把目标值从原链表上摘下,然后在插入点把链表断成二截,然后跟目标点重新接起来即可。

双链表插入排序实例代码,这样的场景在实际项目中还是用的比较多的,关于双链表插入排序实例代码就介绍到这了。

双链表插入排序实例代码属于前端实例代码,有关更多实例代码大家可以查看

网站出售中,有意者加微信:javadudu

回复

我来回复
  • 暂无回复内容