当前位置:首页 >> 网络编程

JS中的算法与数据结构之列表(List)实例详解

本文实例讲述了JS中的算法与数据结构之列表(List)。分享给大家供大家参考,具体如下:

前言

前端很少有机会接触到算法,大多都交互性的操作,所以不少前端工程师会抱着这么一种想法:我是做前端的,为什么要学数据结构与算法?没有数据结构与算法,我一样很好的完成工作。实际上,算法是一个宽泛的概念,我们平时写的任何代码都可以成为算法,它是对一个问题的解决方案的准确而完整的描述,是解决一系列问题的清晰指令,它代表着用系统的方法描述解决问题的策略机制。随着现在互联网的飞速发展,前端工程师已不是靠几个选择器操作加链接加事件就能应付的,越来越复杂的产品和基础库,需要坚实的数据结构与算法才能驾驭,所以我认为前端工程师也是应该要重视算法和数据结构,这对于自己的职业发展是有很大帮助的。当然,算法的学习也不是一朝一夕的事情,这是一个过程,得自己去摸索,去实践,去总结,我这里只是将一些常见的算法和数据结构用 JavaScript 去实现,起到一个抛砖引玉的作用。


列表(List)

列表是计算机中一种常见的数据结构,日常生活中的购物清单,待办事项等都可以成为列表,它是一组有序的数据,每个列表中的数据项称为元素。在javascript中,列表中的元素可以是任意数据类型。列表中可以保存多少元素并没有限定(在实际使用时会受到程序内存的限制)。列表中会有一些常见属性或方法,比如列表中的元素个数,列表当前的位置,向列表末尾增加一个元素,从列表中删除一个元素,清空列表等一系列操作。接下来,我们抽象出一个列表的数据类型定义,并用JS中的数组去实现它。

JS中的算法与数据结构之列表(List)实例详解 
列表的数据类型定义

列表类

/*定义List类*/
 function List () {
  this.listSize = 0;  //初始化元素个数为0
  this.pos = 0;    //初始化位置为0
  this.dataStore = []; //初始化空数组来保存列表元素
  this.clear = clear;
  this.find = find;  //寻找元素
  this.toString = toString; //显示列表中的元素
  this.insert = insert;
  this.append = append;
  this.remove = remove;
  this.front = front;
  this.end = end;
  this.prev = prev;
  this.next = next;
  this.length = length; //列表中的元素总数
  this.currPos = currPos;
  this.moveTo = moveTo;
  this.getElement = getElement;
  this.contains = contains; //判断给定值是否在列表中
}

接着我们来实现这些方法。

首先得可以添加元素,所以我们先来编写 append 方法

append:向列表中添加一个元素

//该方法给列表的最后一个位置添加一个新的元素,待插入成功后,更新列表中的元素个数

function append ( element ) {
  this.dataStore[this.listSize++] = element;
}

这样我们就可以往列表里面添加元素了,接着我们来看查找 find 方法

find:查找列表中的某一个元素

//该方法通过循环查找给定元素是否在列表中,如果存在返回元素的位置,否则返回 -1

function find(element){
  for( var i = 0 ; i < this.dataStore.length ; i ++ ){
      if( this.dataStore[i] == element ){
        return i;
      }
    }
  return -1;
}

可以插入元素,那总得可以删除了,我们利用 remove 方法删除一个元素

remove:删除列表中的某一元素

//该方法通过使用find()方法返回元素的位置对 dataStore 数组进行截取,如果删除成功,返回 true , 并将 listSize 的值减1,更新列表长度,否则返回 false

function remove ( element ) {
  var foundAt = this.find(element);
  if( foundAt > -1 ){
    this.dataStore.splice( foundAt , 1 );
    --this.listSize;
    return true;
  }
  return false;
}

我想知道我的列表还有多少个元素的时候,就得构建 length 方法,

length:返回列表中总的元素个数

//该方法直接将 listSize 返回即可

function length(){
  return this.listSize;
}


如果能显示我的列表元素就好了,这个可以有,我们来看看 toString 方法,

toString:显示列表的元素

//该方法直接返回了列表数组,显示出当前列表内容

function toString(){
  return this.dataStore;
}


现在我们的列表已经有了基本的一些功能,不妨下试试

//构造列表对象
var fruits = new List();
//添加三个元素
fruits.append('Apple');
fruits.append('Grape');
fruits.append('Banana');

//打印列表
console.log( fruits.toString() )   // ["Apple", "Grape", "Banana"]
//查看列表长度
console.log( fruits.length() )    // 3
//查找 Banana 的位置
console.log( fruits.find('Banana') ) // 2
//删除 Grape 
fruits.remove('Grape');
console.log( fruits.toString() )   // ["Apple", "Banana"]


如果我们删除了 Grape 元素 , 我们还想将它放回到原来的位置 ,这时候我们就需要调用 insert 方法

insert:向列表某个位置添加一个元素

//该方法需要传入两个参数,第一个参数表示待插入的元素,第二个参数表示待插入元素的前一个元素,用于确定插入元素的位置,并调用 splice 方法更改列表数组,插入成功后更新 listSize 并返回 true , 否则返回 false;
function insert( element , after ){
  var insertPos = this.find( after );
  if( insertPos > -1 ){
    this.dataStore.splice( insertPos + 1 , 0 , element );
    this.listSize ++;
    return true;
  }
  return false;
}


现在,我们把 Grape 放到原来的位置上去;

fruits.insert( 'Grape' , 'Apple' );
console.log( fruits.toString() )    // ["Apple", "Grape", "Banana"]


ok,现在已经能够把 Grape 插入到原来的位置了。

如果我吃完了所有水果,我现在想要清空列表,我们就需要一个 clear 方法;

clear:清空列表

//该方法使用 delete 操作符删除 dataStore 数组 , 接着创建新的数组,并将其 listSize 和 pos 初始化设为 1 。

function clear(){
  delete this.dataStore;
  this.dataStore = [];
  this.listSize = this.pos = 0;
}


我们不妨试一试。

fruits.clear();
console.log( fruits.toString() );   // []


成功了!

上面我们看到了列表中有个 pos 属性,表示当前列表所在的位置,我们接下来就围绕它做点事情,让用户可以自由操作列表

front:将列表的位置移到第一个位置上

//该方法只要将 pos 置为 0 即可

function front(){
  this.pos = 0 ;
}


end:将列表的位置移到最后一个位置上

//同上,该方法只要将 pos 置为列表长度减 1 即可,因为数组下标从 0 开始嘛

function end(){
  this.pos = this.listSize - 1;
}


prev:将当前位置前移一位

//只要将 pos 的位置减 1 即可,但要主要不能越界

function prev(){
  if( this.pos > 0 ){
    this.pos --;
  }else{
    console.log('您当前已在首位');
  }
}


next:将当前位置后移一位

//同理,只要将 pos 的位置加 1 即可,但要主要不能越界

function next(){
  if( this.pos < this.listSize - 1 ){
    ++this.pos;
  }else{
    console.log('您当前已在末尾');
  }
}


moveTo:将当前位置移动到指定位置

//直接改变 pos 的值即可,注意输入的合法性

function moveTo( position ){
  if( position < 0 || position > (this.listSize - 1) ){
    console.log('请输入正确的位置');
  }else{
    this.pos = position;
  }
}


我既然可以随意改变我的列表位置,那我总得知道我当前位置在哪里啊,因此我们需要 currPos 和 getElement 两个方法分别返回当前的位置和元素;

currPos:返回列表的当前位置

//只需将 pos 直接返回即可

function currPos(){
  return this.pos;
}


getElement:返回当前位置的元素

//直接取对应的元素就好

function getElement(){
  return this.dataStore[this.pos];
}


接着,我们测试一下,首先将列表恢复到清空前的样子,然后我们在多添加几个元素进去。

//再添加几个
fruits.append('Pear');
fruits.append('Orange');
fruits.append('Strawberry');
console.log( fruits.toString() );  // ["Apple", "Grape", "Banana", "Pear", "Orange", "Strawberry"]

//我们先看当前的位置和元素
console.log( fruits.currPos() );   // 0
console.log( fruits.getElement() ); // Apple

//我们尝试改变一下
fruits.moveTo( 2 );
fruits.next();
console.log( fruits.currPos() );   // 3
console.log( fruits.getElement() ); // Pear
fruits.end();
fruits.prev();
console.log( fruits.currPos() );   // 4
console.log( fruits.getElement() ); // Orange


至此,我们已经基本完成了列表的所有功能,还差最后一个,判断给定元素是否在列表内,我们这里采用 contains 方法

contains:判断给定值是否在列表中

//我们直接利用利用 indexOf() 或者采用跟为高级的 ES6 中的 includes 方法来判断

//ES5
function contains( element ){
  if( this.dataStore.indexOf( element ) > -1 ) return true;
  else return false;
}

//ES6

function contains( element ){
  return this.dataStore.includes( element );
}


( ps:对 ES6 不太熟悉的同学,也可以参考本站https://www.jb51.net/article/138409.htm )

写完测试一下,

console.log(fruits.contains('Banana'));     // true
console.log(fruits.contains('Watermelon'));   // false


大功告成!我们自己用 javascript 实现了一个列表,至于后面如何拓展,自己可以发散思维,多动手实践实践,一起加油!

感兴趣的朋友可以使用在线HTML/CSS/JavaScript代码运行工具:http://tools.jb51.net/code/HtmlJsRun测试上述代码运行效果。

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

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

上一篇: Vue 权限控制的两种方法(路由验证)
下一篇: jQuery zTree插件快速实现目录树