【搬迁】使用js构造数组/列表/栈/队列/链表对象

[escawn]

• 本文首发于简书
• 发表日期：2016/09/04

数组

js中本身就有数组对象，数组中的每一项都可以保存任何类型的数据.且ECMAScript 数组的大小是可以动态调整的,即可以随着数据的添加自动增长以容纳新增数据。接下来创建的列表、队列、链表等对象都是基于数组的。

数组的构造

数组的创建也有构造函数和对象字面量两种方法。在使用 Array 构造函数时也可以省略 new 操作符。

var colors = Array(3); // 创建一个包含 3 项的数组
var names = Array("Greg"); // 创建一个包含 1 项,即字符串"Greg"的数组

数组的方法

(1)数组的转换方法toString( )

• 调用 数组的 toString()方法会返回由数组中每个值的字符串形式拼接而成的一个以逗号分隔的字符串
• alert( )一个数组时，会先给数组调用toString( )方法

(2)数组的连接方法join( )

• join( )方法只接收一个参数,即用作分隔符的字符串,然后返回包含所有数组项的字符串。

var colors = ["red", "green", "blue"];
    alert(colors.join(","));       //red,green,blue
    alert(colors.join("||"));      //red||green||blue

(3)数组栈方法

• push()方法可以接收任意数量的参数,把它们逐个添加到数组末尾,并返回修改后数组的长度。
• pop()方法则从数组末尾移除最后一项,减少数组的 length 值,然后返回移除的项

(4)数组队列方法

• unshift( )方法能在数组前端添加任意个项并返回新数组的长度
• shift( ),能够移除数组中的第一个项并返回该项,同时将数组长度减 1

(5)数组重排列方法

• reverse( )反转数组项的顺序。

• sort( )默认情况下，按升序排列。sort( )比较的是字符串，会调用每个数组项的**toString( )方法**.sort( )方法可以接收一个比较函数作为参 数。比较函数接收两个参数,如果第一个参数应该位于第二个之前则返回一个负数,如果两个参数相等则返回 0,如果第一个参数应该位于第二个之后则返回一个正数。

(6)数组的操作方法

• concat（ ）：会先创建当前数组一个副本,然后将接收到的参数添加到这个副本的末尾,最后返回新构建的数组。

• slice( ) ：可以接受一或两个参数,即要返回项的起始和结束位置。在只有一个参数的情况下,slice()方法返回从该 参数指定位置开始到当前数组末尾的所有项。如果有两个参数,该方法返回起始和结束位置之间的项— —但不包括结束位置的项。注意,slice()方法不会影响原始数组。（两个参数时包括前面不包括后面）

• splice( )：
  只需指定 3 个参数:起始位置、要删除的项数和要插入的任意数量的项。例如, splice (2,1,"red","green")会删除当前数组位置 2 的项,然后再从位置 2 开始插入字符串 "red"和"green"。

(7)数组的位置方法

• indexOf( )和 lastIndexOf( )：接收两个参数——要查找的项和(可选的)表示查找起点位置的索引。
• indexOf( )方法从数组的开头(位置0)开始向后查找,lastIndexOf( )方法则从数组的末尾开始向前查找。

(8)数组的迭代方法
每个方法都接收两个参数:要在每一项上运行的函数和 (可选的)运行该函数的作用域对象——影响 this 的值。传入这些方法中的函数会接收三个参数:数组项的值、该项在数组中的位置和数组对象本身。

• **every( ):**对数组中的每一项运行给定函数,如果该函数对每一项都返回 true,则返回 true。
• **filter( ):**对数组中的每一项运行给定函数,返回该函数会返回 true 的项组成的数组。
• **forEach( ):**对数组中的每一项运行给定函数。这个方法没有返回值。
• **map( ):**对数组中的每一项运行给定函数,返回每次函数调用的结果组成的数组。
• **some( ):**对数组中的每一项运行给定函数,如果该函数对任一项返回 true,则返回 true。

(9)数组的归并方法

• 两个归并数组的方法:reduce()和 reduceRight()。这两个方法都会迭代数组的所有项,然后构建一个最终返回的值。其中,reduce()方法从数组的第一项开始,逐个遍历 到最后。而 reduceRight()则从数组的最后一项开始,向前遍历到第一项。

• 这两个方法都接收两个参数:一个在每一项上调用的函数和(可选的)作为归并基础的初始值。传给 reduce()和 reduceRight()的函数接收 4个参数:前一个值、当前值、项的索引和数组对象。这个函数返回的任何值都会作为第一个参数自动传给下一项。第一次迭代发生在数组的第二项上,因此第 一个参数是数组的第一项,第二个参数就是数组的第二项。

 var values = [1,2,3,4,5];
    var sum = values.reduce(function(prev, cur, index, array){
        return prev + cur;
    });
    alert(sum); //15

列表

其实列表与数组的作用与定义都十分相似。每个列表中的数据项称为元素，列表中的元素可以是任意数据类型。列表中可以保存多少元素并没有事先限定,实际使用时元素的数量受到程序内存的限制。

列表的构造

function List(){
  this.listSize = 0;
  this.dataStore = [];
  this.pos = 0;
}
List.prototype = {
  constructor:List;
  //向列表添加数据
  addElement:function(element){
    this.dataStore[this.listSize++] = element;
  }
  
  //查找列表中的数据
  findElement:function(element){
    //不用indexOf()方法是因为只能返回找到的第一个元素的位置
    var arr = [];
    for (var i = 0; i < this.dataStore.length; ++i) {
      if (this.dataStore[i] == element) { 
        arr.push(i);
      }
    }
    return arr;
}

  //从列表删除数据
  removeElement:function(element){
    var foundAt = this.findElement(element);
    if (foundAt.length>0){
      for(var i=0;i<foundAt.length;i++){
        this.dataStore.splice(foundAt[i],1); 
        --this.listSize;
      }
      return true;
    }
    return false;
  }

  //列表中有多少个元素
  length:function(){
    function length() { 
      return this.listSize;
    }
  }

  //向列表中插入一个元素
  insertElement:function(element,index){
    //假设插入是指插入到列表中某个位置上
    this.dataStore.splice(index,0,element)；
    return true;
  }

  //清空列表
  clearList:function(){
    delete this.dataStore; 
    this.dataStore = []; 
    this.listSize= 0;
  }

  //将列表的当前位置移动到第一个元素
  front:function() { 
    this.pos = 0;
  }

  //将列表的当前位置移动到最后一个元素
  end:function() { 
    this.pos = this.listSize-1;
  }
  
  //将当前位置前移一位
  pre:function() { 
    if (this.pos > 0) {
       --this.pos; 
    }
  }

  //将当前位置后移一位
  next:function() { 
    if (this.pos < this.listSize-1) {
     ++this.pos; 
    }
  }

  //将当前位置移动到指定位置
  moveTo:function(position) { 
    this.pos = position;
  }
}

列表的属性

• listSize：列表的元素个数
• dataStore：列表的存储位置
• pos：列表的当前位置

列表的方法

• addElement：向列表添加数据
• findElement：查找列表中的数据
• removeElement：从列表删除数据
• length：返回列表中元素个数
• insertElement：向列表中插入一个元素
• clearList：清空列表
• front：将列表的当前位置移动到第一个元素
• end：将列表的当前位置移动到最后一个元素
• pre：将当前位置前移一位
• next：将当前位置后移一位
• moveTo：将当前位置移动到指定位置

栈

栈是一种特殊的列表,栈内的元素只能通过列表的一端访问,这一端称为栈顶。栈被称为一种**后入先出(LIFO,last-in-first-out)**的数据结构。

栈的构造函数

function Stack(){
  this.top = 0；
  this.dataStore = [];
}
Stack.prototype = {
  constructor:Stack;
 //向栈中添加元素
  push:function(element){
    this.dataStore[this.top++] = element;
  }

  //栈顶元素出栈，并返回
  pop:function(){
    return this.dataStore[--this.top];
  }

  //返回栈顶元素
  peek:function() { 
    return this.dataStore[this.top-1];
  }

  //清空栈
  clear:function(){
    this.dataStore.length = 0;
  }

  
}

栈的属性

• top：记录栈顶位置
• dataStore：栈中元素的存储位置

栈的方法

• top：返回栈顶的元素
• push：向栈中添加元素
• pop：栈顶元素出栈
• peek：返回栈顶元素
• clear：清空栈

队列

队列是一种列表,不同的是队列只能在队尾插入元素,在队首删除元素。队列用于存储按顺序排列的数据,先进先出(First-In-First-Out,FIFO)

队列的构造

function   Queue(){ 
  this.dataStore = [];
}
Queue.prototype = { 
  constructor:Queue;
  //向队尾添加一个元素
  enqueue:function(element){
    this.dataStore.push(element);  
  }

  //删除队首的元素
  dequeue:function(){
    return this.dataStore.shift();
  }

  //读取队首的元素
  front:function(){
    return this.dataStore[0];
  }

  //读取队尾的元素:
  end:function(){
    return this.dataStore[this.dataStore.length-1];
  }
}

队列的属性

• dataStore：队列的存储

队列的方法

• enqueue：向队尾添加一个元素
• dequeue：删除队首的元素
• front：读取队首元素
• end：读取队尾元素

链表

链表是由一组节点组成的集合。每个节点都使用一个对象的引用指向它的后继。指向另一个节点的引用叫做链。数组元素靠它们的位置进行引用,链表元素则是靠相互之间的关系进行引用。

链表的构造

//链表上的节点
function Node(element){
  this.element = element;
  this.next = null;
}

//链表
function LinkedList(){
  this.head = new Node("head");
}

LinkedList.prototype = {
  constructor:LinkedList;
  //寻找节点
  find:function(item){
    var currNode = this.head; 
    while (currNode.element != item) {
      currNode = currNode.next; }
     return currNode;
  }

  //插入节点
  insert:function(new,item){
    var newNode = new Node(new);
    var current = this.find(item);
    newNode.next = current.next;
    current.next = newNode;
  }

  //寻找这个节点的上一个节点
  findPrevious:function(item){
    var currNode = this.head;
    while (!(currNode.next == null) &&(currNode.next.element != item)) { 
      currNode = currNode.next;
    }
    return currNode;
  }

  //删除节点
  remove:function(item){
    var pre = this.findPrevious(item);
    pre.next = pre.next.next; 
  }
}

链表的属性

• head：链表的第一个节点

链表的方法

• find:寻找节点
• insert：插入节点
• findPrevious:寻找这个节点的上一个节点
• remove：删除节点