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

本文实例讲述了JS实现线性表的顺序表示方法。分享给大家供大家参考，具体如下：

线性表的顺序表示指的是用一组地址连接的存储单元依次存储线性表的数据元素。通常称这种存储结构的线性表为顺序表。

顺序表的特点是以元素在计算机内物理位置相邻来表示数据元素之间的逻辑关系。每一个数据元素的存储位置都和线性表的起始位置相差一个和数据元素在线性表中的位序成正比的常数。也就是说只要确定了存储线性表的起始位置，线性表中的任一元素都可以随机存储，所以说，顺序表是一种随机存取的存储结构。

高级语言中的数组与其相似，所以我们用数组来描述顺序存储结构。

下面描述了逻辑关系的变化

下面我们来实现插入和删除的过程

首先是插入

我们在第i（1<=i<=n）个元素之前插入一个元素，需将第i至n个元素向后移动一个位置。代码如下

<!DOCTYPE html>
<html>
 <head>
 <meta charset="utf-8">
 <title></title>
 </head>
 <body onload="ListInsert([1,2,3,4],2,5)">
 </body>
 <script type="text/javascript">
 function ListInsert(a,i,e){
  //在a的第i个位置之前插入e
  var j,
  a_len=a.length;
  for(j=a_len-1;j>=i-1;j--){
  a[j+1]=a[j];
  }
  a[i-1]=e;
  alert(a);//1,5,2,3,4
 }
 </script>
</html>

同样的道理，删除第i个元素的代码为

<!DOCTYPE html>
<html>
 <head>
 <meta charset="utf-8">
 <title></title>
 </head>
 <body onload="ListDelete([1,2,3,4,5,6,7,8],3)">
 </body>
 <script type="text/javascript">
 function ListDelete(a,i){
  //删除a集合第i个位置的值
  var e=a[i-1],//被删除的元素
  a_len=a.length;
  for(j=i-1;j<=a_len-1;j++){
  a[j-1]=a[j];
  }
  a[j-1]=null;
  alert(a);//1,2,4,5,6,7,8
 }
 </script>
</html>

从上面两个算法可以看出，时间主要耗费在移动元素上，而移动元素的个数取决于插入或删除元素的位置。根据概率论的相关知识，可以得出在顺序存储结构的线性表中插入或删除一个数据元素时，平均约移动表中一般元素。如果表长为n，则上面两个算法的时间复杂度是o(n/2)，又由于n/2和n都处于线性阶。所以直接表示为o(n)

更多关于JavaScript相关内容感兴趣的读者可查看本站专题：《JavaScript数据结构与算法技巧总结》、《JavaScript数学运算用法总结》、《JavaScript排序算法总结》、《JavaScript遍历算法与技巧总结》、《JavaScript查找算法技巧总结》及《JavaScript错误与调试技巧总结》

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

赞 (0)

相关推荐

  • JavaScript实现在数组中查找不同顺序排列的字符串

    需求描述:从一组数组中找出一组按不同顺序排列的字符串的数组元素.假如有这样一个数组: 复制代码 代码如下: [ 'abcd', 'hello', 'bdca', 'olleh', 'cadb', 'nba', 'abn', 'abc' ] 需要找出的结果是: 复制代码 代码如下: [ 'abcd', 'bdca', 'cadb' ] 那么这里的关键点是判断一组字符串是否是否只是字符的顺序不同,只要解决整个关键点其他都好办了. 方法1: 复制代码 代码如下: var stringClassify

  • javascript实现二分查找法实现代码

    一般二分都用到int[]型上.....在js中可能会更灵活的用到a-z上,或者用到拼音...或者用到...... 不过值得深思的一个问题是,如果为了实现对拼音之类的二分查找.而经过如下流程是否值得: 1.对拼音排序,貌似代码量不小吧. 2.然后再二分查找.这又需要识别拼音的大小,貌似也不算太小吧. 找到结果的速度快了,可是别人下你的js文件速度慢多了,呵呵,到底舍弃谁. 下面的代码甚至可以10亿条,一样会很快找到,可是用遍例的模式创建那个数组...所以还是别尝试了.只是给个思路,下次我再来发个j

  • js实现的二分查找算法实例

    本文实例讲述了js实现的二分查找算法.分享给大家供大家参考,具体如下: <!DOCTYPE html> <html> <head> <title>demo</title> <style type="text/css"> </style> <script type="text/javascript"> var binarySearch = function(array, s

  • js中通过父级进行查找定位元素

    复制代码 代码如下: <ul id="newslist"> <li> <span class="fr w160 tl">2013-06-24</span> <span class="news_list_icon fl mr8 icon" ></span> <span class="fl"><a href="{href}"

  • JS查找字符串中出现次数最多的字符

    JS查找字符串中出现次数最多的字符

    在一个字符串中,如 'zhaochucichuzuiduodezifu',我们要找出出现最多的字符.本文章将详细说明方法思路. 先介绍两个string对象中的两个方法:indexOf()和charAt()方法 indexOf()方法介绍 返回某个指定的字符串值在字符串中首次出现的位置 charAt()方法介绍 返回某个指定位置的字符 先做一个小测试,找到字符串'woainixiaoli'中的每一个'i'出现的位置. <script> var arr = 'woainixiaoli'; var

  • 基于JavaScript实现的顺序查找算法示例

    基于JavaScript实现的顺序查找算法示例

    本文实例讲述了基于JavaScript实现的顺序查找算法.分享给大家供大家参考,具体如下: 对于查找数据来说,最简单的方法就是从列表的第一个元素开始对列表元素逐个进行判断,直到找到了想要的结果.这个方法叫做顺序查找,有时候也被叫做线性查找.它属于暴力查找技巧的一种. 顺序查找实现起来非常简单,代码如下: function generalSearch(arr,data){//普通的顺序查找,就是遍历一遍看是否找到 for(var i=0;i<arr.length;i++){ if(arr[i]==

  • js基本算法:冒泡排序,二分查找的简单实例

    知识扩充: 时间复杂度:算法的时间复杂度是一个函数,描述了算法的运行时间.时间复杂度越低,效率越高. 自我理解:一个算法,运行了几次时间复杂度就为多少,如运行了n次,则时间复杂度为O(n). 1.冒泡排序 解析:1.比较相邻的两个元素,如果前一个比后一个大,则交换位置. 2.第一轮的时候最后一个元素应该是最大的一个. 3.按照步骤一的方法进行相邻两个元素的比较,这个时候由于最后一个元素已经是最大的了,所以最后一个元素不用比较. function sort(elements){ for(var i

  • js查找节点的方法小结

    本文实例总结了js查找节点的方法.分享给大家供大家参考.具体分析如下: 这里介绍查找节点的三种方法: 1. 根据id查找,返回值为对象: 复制代码 代码如下: document.getElementById(); 2. 根据div/p/....等html标签查找,返回数组(实际也是对象) 复制代码 代码如下: document.getElementsByTagName(); 3. 在表单中使用,根据表单name来查找 复制代码 代码如下: document.getElementsByName()

  • javascript下查找父节点的简单方法

    <div>        <a href="#">标题</a>        <ul id="demo">            <li><a href="#" onclick="selectThisItem(this)">项目一</a></li>                <ul>                 

  • JavaScript数据结构之二叉树的查找算法示例

    本文实例讲述了JavaScript数据结构之二叉树的查找算法.分享给大家供大家参考,具体如下: 前面文章介绍了二叉树的遍历,现在谈谈在二叉树中进行查找.对二叉查找树来说,一般有以下三类查找:最大值,最小值和给定值. 查找最小值就是遍历左子树,直到找到最后一个结点,这是因为在二叉查找树中较小的值总是在左子节点上的. 代码如下: function getMin(){//查找最小值 var current=this.root;//指向根节点 while(current.left!=null){ cur

  • JavaScript黑洞数字之运算路线查找算法(递归算法)实例

    JavaScript黑洞数字之运算路线查找算法(递归算法)实例

    本文实例讲述了JavaScript黑洞数字之运算路线查找算法.分享给大家供大家参考,具体如下: 运行效果截图如下: 具体代码如下: <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> <html xmlns="http://www.w3.org/19

  • JavaScript使用二分查找算法在数组中查找数据的方法

    本文实例讲述了JavaScript使用二分查找算法在数组中查找数据的方法.分享给大家供大家参考.具体分析如下: 二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好:其缺点是要求待查表为有序表,且插入删除困难.因此,折半查找方法适用于不经常变动而查找频繁的有序列表.首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功:否则利用中间位置记录将表分成前.后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一

随机推荐