当前位置:首页 > 编程教程 > javascript技术文章 > JS实现线性表的链式表示方法示例【经典数据结构】

JS实现线性表的链式表示方法的实例内容

  • 发布时间:
  • 作者:码农之家
  • 点击:85

这篇文章主要知识点是关于JS、线性表、链式表示、数据结构、的内容,如果大家想对相关知识点有系统深入的学习,可以参阅以下电子书

JavaScript语言精粹
JavaScript语言精粹超清修订版
  • 类型:JavaScript大小:9.9 MB格式:PDF作者:克罗克福德
立即下载

JS实现线性表的链式表示方法示例【经典数据结构】

本文实例讲述了JS实现线性表的链式表示方法。分享给大家供大家参考,具体如下:

从上一节可以,顺序存储结构的弱点就是在插入或删除操作时,需要移动大量元素。所以这里需要介绍一下链式存储结构,由于它不要求逻辑上相邻的元素在物理位置上也相邻,所以它没有顺序存储结构的弱点,但是也没有顺序表可随机存取的优点。

下面介绍一下什么是链表

线性表的链式存储结构用一组任意的存储单元存储线性表的数据元素。所以,每一个数据元素除了存储自身的信息之外,还需要存储一个指向其后继的存储位置的信息。这两部分信息组成了元素的存储映像,称为结点

结点包括两个域:数据域指针域

数据域是元素中存储数据元素的信息。

指针域是元素中存储的后继存储位置的信息。

n个结点链接成为链表,就是线性表的链式存储结构,又由于此链表的每个结点中只包含一个指针域,所有又称为线性链表或单链表

举一个例子

JS实现线性表的链式表示方法示例【经典数据结构】

上图表示的线性表为

ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG

这样应该就好理解多了吧。

下面我们通过js代码来实现链表的插入和删除还有查找操作

<!DOCTYPE html>
<html>
<head>
<meta charset="UTF-8"/>
<script type = "text/javascript">
 var Node = function(newData){//创建节点对象
 this.next = null;
 this.data = null;
 this.Init = function(){
  this.data = newData;
 };
 this.Init();
 }
 //定义链表类
 var List = function(){
 this.head = null;
 this.size = 0;
 this.Init = function(){
  this.head = null;
  this.size = 0;
 }
 this.Init();
 this.Insert = function(newData){//初始批量插入操作
  this.size += 1;
  var newNode = new Node(newData);
  if(this.head == null){
  this.head = newNode;
  return;
  }
  var tempNode = this.head;
  while(tempNode.next != null)
  tempNode = tempNode.next;//找到链表尾部
  tempNode.next = newNode;//将新元素插入到链表尾部
 };
 this.GetData = function(pos){//查找操作
  if(pos >= this.size || pos < 0)
  return null;
  else{
  tempNode = this.head;
  for(i = 0;i < pos;i++)
   tempNode = tempNode.next; //找到所处位置
  return tempNode.data;
  }
 };
 this.Remove = function(pos){//移除某一位置节点
  if(pos >= this.size || pos < 0)
  return null;
  this.size -= 1;
  tempNode = this.head;
  if(pos == 0){
  this.head = this.head.next;
  return this.head;
  }
  for(i = 0;i < pos - 1;i++){
  tempNode = tempNode.next;
  }
  tempNode.next = tempNode.next.next;
  return tempNode.next;
 };
 this.InsertBefore=function(data,pos){//从某一位置前插入节点
  if(pos>=this.size||pos<0)
  return null;
  this.size+=1;
  tempNode=this.head;
  var newNode = new Node(data);//将数据创造节点
  if(pos==0){
  newNode.next=tempNode;
  return newNode.next;
  }
  for(i=0;i<pos-1;i++){
  tempNode=tempNode.next;//找到插入的位置
  }
  newNode.next=tempNode.next;//插入操作
  tempNode.next=newNode;
  return newNode.next;
 };
 this.Print = function(){//输出
  document.write("链表中元素: <br>");
  tempNode = this.head;
  while(tempNode != null){
  document.write(tempNode.data + " ");
  tempNode = tempNode.next;
  }
  document.write("<br>");
 };
 };
 //运行测试:
 var list = new List();
 var array = new Array(1,2,3,4,5,6);
 for(i = 0;i < array.length;i++){
 list.Insert(array[i]);
 }
 list.Print();
 document.write("查找操作下标为4的元素: <br>");
 var data= list.GetData(4);
 document.write(data+"<br>");
 document.write("删除操作: <br>");
 list.Remove(5);
 list.Print();
 document.write("插入操作: <br>");
 list.InsertBefore(8,3);
 list.Print();
 document.write("链表大小: " + list.size);
</script>
</head>
<body>
</body>
</html>

运行得到结果为

JS实现线性表的链式表示方法示例【经典数据结构】

先分析一下插入和删除的代码。

 this.InsertBefore=function(data,pos){//从某一位置前插入节点
  if(pos>=this.size||pos<0)
    return null;
  this.size+=1;
  tempNode=this.head;
  var newNode = new Node(data);//将数据创造节点
  if(pos==0){
    newNode.next=tempNode;
    return newNode.next;
  }
  for(i=0;i<pos-1;i++){
    tempNode=tempNode.next;//找到插入的位置
  }
    newNode.next=tempNode.next;//插入操作
    tempNode.next=newNode;
  return newNode.next;
};
this.Remove = function(pos){//移除某一位置节点
      if(pos >= this.size || pos < 0)
       return null;
      this.size -= 1;
      tempNode = this.head;
      if(pos == 0){
       this.head = this.head.next;
       return this.head;
      }
      for(i = 0;i < pos - 1;i++){
       tempNode = tempNode.next;
      }
      tempNode.next = tempNode.next.next;
      return tempNode.next;
};

可以看出,插入和删除的世界复杂度都为o(n)。因为在第i个结点前插入或删除都得找到第i-1个元素。

再来看看初始化方法Insert,

this.Insert = function(newData){//初始批量插入操作
      this.size+= 1;
      var newNode = new Node(newData);
      if(this.head == null){
       this.head = newNode;
       return;
      }
      var tempNode = this.head;
      while(tempNode.next != null)
       tempNode = tempNode.next;//找到链表尾部
      tempNode.next= newNode;//将新元素插入到链表尾部
};

初始的插入Insert方法的时间复杂度也是o(n)。

下面介绍一下另外一种形式的链式存储结构,就是循环链表。它的特点就表中的最后一个结点的指针域指向头结点,整个链表形成一个环。有时候,在循环链表中设立尾指针而不设立头指针,可以简化操作。比如两个线性表集合为一个表时,仅需将一个表的表尾和另一个表的表头相接。这个操作的时间复杂度是o(1)。

如下图所示

JS实现线性表的链式表示方法示例【经典数据结构】

上面介绍的链表只能通过某个结点出发寻找后面的结点。也就是说在单链表中,寻找下一结点的时间复杂度为o(1),而寻找上一结点的时间复杂度为o(n)。为了克服单链表这种单向性的缺点,可以利用双向链表

希望本文所述对大家JavaScript程序设计有所帮助。

以上就是本次给大家分享的关于java的全部知识点内容总结,大家还可以在下方相关文章里找到相关文章进一步学习,感谢大家的阅读和支持。

您可能感兴趣的文章:

  • 深入理解JavaScript执行环境及作用域链
  • javascript 相关电子书
    学习笔记
    网友NO.403474

    利用原生JS与jQuery实现数字线性变化的动画

    前言 大家应该都有所体会,在一些数据展示的专题页里,有时候希望数字能动态从某一个数变化到另一个数,以此来吸引用户眼球,突出数据。于是有了下文。 在这里,我用了两种方式:一种是原生的JavaScript,另一种是jQuery插件。 数字线性变化的原理很简单,就是让数字增量变化,并循环动画。 原生JS版 首先获取DOM元素。为了兼容到IE6,兼容性方法如下: var domUtil = { // 获取DOM元素 get: function(query) { var _this = this; if(document.querySelector) { return document.querySelector(query); } else { var elements = document; var queryStrArray = query.split(/ +/); for(var i = 0; i queryStrArray.length; i++) { var domName = queryStrArray[i]; elements = _this.getElementsOfParentNode(domName, elements); } if(elements.length == 1) { return elements[0]; } else { return elements; } } }, // 获取DOM元素 getElementsOfParentNode: function(domName, parentNode) { var _this ……

    网友NO.734138

    js 将线性数据转为树形的示例代码

    在日常开发工作中,我们经常碰到将线性的数据转换成树的需求,今天给大家分享一个简单的转换算法。 数据结构 下面是我们转换前的数据: [ { "id":1, "parent_id":0, "name":"四川省" }, { "id":2, "parent_id":0, "name":"广东省" }, { "id":3, "parent_id":0, "name":"江西省" }, { "id":5, "parent_id":1, "name":"成都市" }, { "id":6, "parent_id":5, "name":"锦江区" }, { "id":7, "parent_id":6, "name":"九眼桥" }, { "id":8, "parent_id":6, "name":"兰桂坊" }, { "id":9, "parent_id":2, "name":"东莞市" }, { "id":10, "parent_id":9, "name":"长安镇" }, { "id":11, "parent_id":3, "name":"南昌市" }] 我们转换后的结果是: [ { "id":1, "parent_id":0, "name":"四川省", "children":[ { "id":5, "parent_id":1, "name":"成都市", "children":[ { "id":6, "parent_id":5, "name":"锦江区", "children":[ { "id":7, "parent_id":6, "name":"九眼桥" }, { "id":8, "parent_id":6, "name":"兰桂坊" } ] } ] } ] }, { "id":2, "parent_id":0,……

    <
    1
    >

    Copyright 2018-2020 www.xz577.com 码农之家

    版权投诉 / 书籍推广 / 赞助:520161757@qq.com