javascript数组与列表教程

2016-02-22    编辑:edit02_lz     点击(
数组,就是相同数据类型的元素按一定顺序排列的集合,列表是一种数据项构成的有限序列,即按照一定的线性顺序,排列而成的数据项的集合,本文我们来分析一下javascript的数组与列表。

javascript: 数组



数组是编程世界里最常见的数据结构。任何一种编程语言都包含数组,只是形式稍微有差异。数组是编程语言中的内建类型,通常效率都很高。可以满足不同需求的数据存储,本章将探索javascript中的数组工作原理,以及它们的使用场合。

一:javascript中对数组的定义

数组的标准定义是:一个存储元素的线性集合(collection),元素可以通过索引来任意存储,索引通常是数字,用于计算元素之间存储位置的偏移量。几乎所有的编程语言都有类似的数据结构。然而javascript确略有不同。

javascript中数组是一种特殊的对象,用来表示偏移量的索引是该对象的属性,索引可能是整数。然而这些数字索引在内部被转换为字符串类型,这是因为javascript对象中的属性名必须是字符串。数组在javascript又是一种特殊的对象,所以效率上不如其他语言中的高。

javascript中的数组,严格的来说应该称作为对象,是特殊的javascript对象,在内部被归类为数组。由于Array在javascript中被当做对象,因此它有很多属性和方法在编程中使用。

二:使用数组

javascript中的数组非常灵活。但是创建数组和存取元素的方法就有好多种。也可以通过关不同的方式对数组进行进行查找和排序。javascript1.5还提供了一些函数,让程序员再处理数组时可以使用函数式编程技巧。

1.创建数组

最简单的方式就是通过[]操作符声明一个数组变量。

var numbers = [];

使用这样的方式创建数组,将得到一个长度为0的空数组。也可以通过内建的length来证明这一点。

console.log(numbers.length); //0

另外一种方式是在声明数组时,直接在[]操作符内放入一组元素。

var numbers = [1,2,3,4,5]
console.log(numbers.length); //5

也可以通过调用Array的构造函数进行创建数组

var numbers = new Array();
console.log(numbers.length);//0

同样可以为构造函数传入一组元素作为数组的初始值

var numbers = new Array(1,2,3,4,5)
console.log(numbers.length)

最后,在调用构造函数时,可以只传入一个参数,来指定数组的长度。

var numbers = new Array(10);
console.log(numbers.length);//10
console.log(numbers);//[]

在脚本语言中很常见的一个特性是,数组中的元素不必是同一种数据类型,这一点和其它编程语言不同,如下所示:

var objects = [1,"joe",true,null];

可以调用Array.isArray()来判断一个对象是否数组。如下所示范

var numbers = 3;
var arr = [7,4,123];
console.log(Array.isArray(numbers));//false
console.log(Array.isArray(arr)) //true

本节我们讨论的数组的创建,那种方式最好,大多数javascript专家推荐使用[],和Array的构造函数相比,这种方式被认为效率更高。

2.读写数组

在一条赋值语句中,可以使用[]操作符将数据赋值给数组。比如以下循环,将1-100的数字赋予给一个数组。

var num = [];
for (var i = 0; i < 100; ++i) {
    num[i] = i+1
    
};
console.log(num)

还可以使用[]操作符读取数组中的元素,如下所示:

var numbers = [1,2,3,4,5]
var sum = numbers[0]+ numbers[1] + numbers[2] + numbers[3] + numbers[4];
console.log(sum) //15

要依次取得数组中的所有元素,使用for循环更加简单。

var numbers = [1,2,3,5,8,13,21];
var sum = 0;
for (var i = 0; i < numbers.length; i++) {
    sum += numbers[i]
}
console.log(sum);//53

3.由字符串生成数组

调用字符串对象split()方法也可以生成数组。该方法通过一些常见的分割符,比如分割单词的空格,将一个字符串分为几部分,并将每个部分作为一个元素保存在一个新建的数组中。

下面的一段代码演示了split()的使用方法。


var sent = "the quik brown fox jumped over zhe lazy dog";
var word = sent.split(" ")
console.log(word) ;//["the", "quik", "brown", "fox", "jumped", "over", "zhe", "lazy", "dog"]
for (var i = 0; i < word.length; ++i){
    word[i]
    console.log("word " + i + ":" + word[i])
}


4.对数组的整体性操作

有几个操作作为一个整体进行的。首先,可以将一个数组赋值给另外一个数组:

var nums = [];
for (var i = 0; i < 10 ; ++i){
    nums[i] = i + 1;
}
var sam = nums;
console.log(sam)

但是,当把一个数组赋值给另外一个数组时,只是为被赋值的数组增加了一个新的引用。当你通过原引用修改了数组的值,另外一个引用也会感知到这个变化。下面的代码展示了这个情况。


var nums = [];
for (var i = 0; i < 100; +i){
    nums[i] = i + 1;
}
var sament = nums;
nums[0] = 400;
console.log(sament[0])//400


这种复制被称为浅复制,新数组任然会指向原来的数组,一个更好的方案是深复制,将原数组的每一个元素都复制到新数组中,可以写一个方法来复制函数来做这件事情

function arr_copy(arr1, arr2){
    for (var i = 0; i < arr1.length; i++){
        arr2[i] = arr1[i]
    }
}

var nums = [];
for (i = 0; i < 100; i++) {
    nums[i] = i + 1;
}

var sament = [];
arr_copy(nums,sament);
nums[0] = 400;
console.log(sament[0])//1


三:存取函数

javascript提供了一组用来访问数组元素的函数,叫存取函数,这些函数返回目标数组的某种变体。

1.查找元素

indexof()函数是最常用的存取函数之一,用来查找传进来的参数在目标数组中是否存在。如果目标函数中存在该参数,就返回该元素在数组中索引。如果不包含,就返回-1.indexof()对大小写敏感

如果数组中包含多个相同的元素,则indexof()则返回第一个与参数相同的元素索引。有另外一个功能类似的函数,lastIndexOf().该函数返回相同元素的最后一个元素的索引,如果没有找到相同元素,则返回-1.如下.indexof()对大小写敏感

var str="Hello world!"
console.log(str.indexOf("Hello"))
console.log(str.indexOf("World"))
console.log(str.indexOf("world"))

如果数组中包含多个相同的元素,则indexof()则返回第一个与参数相同的元素索引。有另外一个功能类似的函数,lastIndexOf().该函数返回相同元素的最后一个元素的索引,如果没有找到相同元素,则返回-1.如下


var names = ["David", "Mike", "Cynthia", "Mike", "Jennifer"];
var name = "Mike";
var firstPos = names.indexOf(name);
console.log(firstPos)//1

var lastPos = names.lastIndexOf(name)

console.log(lastPos)//3


2.数组的字符串表示

有两个方法可以将数组转化为字符串:join()和toString(),这两个方法都返回一个包含数组所有元素的字符串,各元素之间用逗号隔开,下面是一些例子

var names = ["David", "Mike", "Cynthia", "Mike", "Jennifer"];
var namestr = names.join();
namestr.toString();
console.log(namestr);//David,Mike,Cynthia,Mike,Jennifer


3.由已有数组创建新数组

concat()和splice()方法允许通过已经有的数组创建新数组。concat方法可以合并多个数组创建一个新数组,splice()方法截取一个数组的子集创建一个新数组

我们先来看看,concat方法的工作原理。该方法发起者是一个数组,参数是另一个数组。作为参数的数组,其中所有的元素都被连接到调用concat()方法的数组后面,下面展示了concat()方法的工作原理


var cisDept = ["Mike", "Clayton", "Terrill", "Danny", "Jennifer"];
var dmpDept = ["Ramondy", "Cynthia", "Bryan"];
var itDiv = cisDept.concat(dmpDept);
console.log(itDiv) //["Mike", "Clayton", "Terrill", "Danny", "Jennifer", "Ramondy", "Cynthia", "Bryan"]

itDiv = dmpDept.concat(cisDept)
console.log(itDiv) ;//["Ramondy", "Cynthia", "Bryan", "Mike", "Clayton", "Terrill", "Danny", "Jennifer"]


输出为

Mike,Clayton,Terrill,Danny,Jennifer,Ramondy,Cynthia,Bryan

Ramondy,Cynthia,Bryan,Mike,Clayton,Terrill,Danny,Jennifer

splice()方法从现有数组里截取一个新数组。该方法的第一个参数是是截取的起始索引,第二个参数是截取的长度。下面的程序展示了splice()方法工作原理:

var itDiv = ["Mike", "Clayton", "Terrill", "Danny", "Jennifer", "Cynthia", "Bryan"];
var dmpDept = itDiv.splice(3,3) //["Danny", "Jennifer", "Cynthia"]

var cisDept = itDiv; //["Mike", "Clayton", "Terrill", "Bryan"]

splice()方法还有其它的用法,比如为一个数组增加或移除元素,具体请参考:
https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/splice

4.可变函数


javascript中有一组可变函数,使用它们,可以不必引用数组中某个元素,就能改变数组内容。这些函数通常化简繁。让困难的事情变得容易。

为数组添加元素

有两个方法 可以为数组添加元素,push()和unshift()。push()方法会将一个元素添加到数组末尾。

var nums = [1,2,3,4,5];
nums.push(6)
console.log(nums);//[1, 2, 3, 4, 5, 6]

也可用使用数组的length属性为数组添加元素,但push()看起来更直观。

var nums = [1,2,3,4,5];
nums[nums.length] = 6;
console.log(nums)

和在数组的末尾添加元素比起来,在数组的开头添加元素更难,如果不利于数组提供的可变函数,则新的元素添加进来后,需要把后面的每个元素都相应的向后移一个位置。下面的代码展示了这个过程。


var nums = [111,2,3,4,5,22,2]
var newnum = 1;
var _n = nums.length;
for (var i = _n; i >= 0; --i){
    nums[i] = nums[i-1]
}
nums[0] = newnum;
console.log(nums) //[1, 111, 2, 3, 4, 5, 22, 2]


不过随着数组中储存的元素越来越多,上述代码会变得原来越低效。

unshift()方法可以将元素添加在数组的开头,下面代码展示改方法的用法。


var nums = [2,3,4,5,6]
var newnum = 1;
nums.unshift(newnum);


var nums2 = [3,4,5];
nums2.unshift(newnum,1,2)
console.log(nums2) ;//[1, 1, 2, 3, 4, 5]


其中第二次出现的unshift(),展示了可以一次调用,为数组添加多个元素。

2. 从数组中删除元素

使用pop()方法可以删除数组末尾元素:

var nums = [1,2,3,4,5,9]
nums.pop()
console.log(nums)

如果没有可变函数,从数组中删除第一个元素需要将后续元素各自向前移动一个位置

var nums = [9,1,2,3,4,5,6];
for (var i = 0; i < nums.length; ++i) {
    nums[i] = nums[i+1]
}

除了要将后续的元素向前移动一位,还多出了一个元素。



shift()方法可以删除数组中的第一个元素,下面代码展示其用法。

var nums  = [11,1,2,3,4,5,6,7];
nums.shift();
console.log(nums)

这组数组末尾那个多余的逗号消失了。pop()和shift()方法都将删掉的元素作为方法返回值返回,因此,可以使用一个变量来保存删除的元素。

var nums = [7,1,2,3,4,5,6];
var _d = nums.shift();
nums.push(_d)
console.log(nums)//[1, 2, 3, 4, 5, 6, 7]

3.从数组的中间位置添加和删除元素

删除数组的第一个元素和在数组开头添加一个元素存在同样的问题 ,两种操作都需要将数组中的剩余元素向前或向后移,然而splice()方法可以帮助我们执行其中的任何一种操作。

使用splice()方法为数组添加元素,需要提供以下参数

起始索引
需要添加元素的个数(添加元素时该参数为0)
想要添加进数组的元素

var nums = [1,2,3,7,8,9]
var newElement = [4,5,6]
nums.splice(3,0,newElement)

要插入的数组不必组织成一个数组,可以是任意元素序列

var nums = [1,2,3,7,8,9]
nums.splice(3,0,11,22,3,4,5)
console.log(nums);//[1, 2, 3, 11, 22, 3, 4, 5, 7, 8, 9]


下面是splice()方法从数组中删除元素的例子

var nums = [1, 2, 3, 11, 22, 3, 4, 5, 7, 8, 9]
nums.splice(3,3)
console.log(nums);//[1, 2, 3, 4, 5, 7, 8, 9]

4.为数组排序。

剩下的两个方法是为数组排序。第一个方法是reverse(),该方法将数组数组中的元素进行反翻转。下面的例子展示了此用法。

var nums = [1,2,3,4,5,6]
nums.reverse();
console.log(nums);//[6, 5, 4, 3, 2, 1]

对数组的排序是经常要遇到的要求,如果元素是字符串类型,那么数组的可变方法sort()就变得非常好使。

var names = ["David", "Mike", "Cynthia", "Mike", "Jennifer"];
names.sort();
console.log(names);//["Cynthia", "David", "Jennifer", "Mike", "Mike"]

但是,如果数组元素是数字类型,那么sort()方法的排序就不那么让人满意了。

var nums = [3,1,2,100,4,200]
nums.sort()
console.log(nums);//[1, 100, 2, 200, 3, 4]

sort()方法是按照字典排序时对元素进行排序的,因此,它将定元素都是字符串类型,在上一个例子中,即使元素是数字类型,也是会被认为为字符串类型。为了让sort()方法也能排序数字类型的元素,可以在调用方法时传入一个比较大小的函数。排序时,sort()方法将会比较两个数组元素的大小。

对于数字类型,该函数可以是一个简单的相减操作,从一个数字减去另外一个数字。搞清楚这些后我们将如下操作:

function compare(num1, num2){
    return num1 - num2;
}
var nums = [3,1,2,100,4,200]
nums.sort(compare);
console.log(nums);//[1, 2, 3, 4, 100, 200]

5.迭代器方法

最后是迭代器方法,这些方法对数组中的每一个元素应用一个函数,可以返回一个值,一组值或一个新数组。


1.不生成新数组的迭代器方法。
我们讨论的第一组迭代器不产生任何新数组,相反,它们要么对于数组中的每个元素执行某种操作,要么返回一个值。

这组中第一个方法是forEach(),该方法接受一个函数作为参数,对数组中的每个元素使用该函数。

function square(num){
    console.log(num,num * num);
}
var nums = [1,2,3,4,5,6,7,8,9,10]
nums.forEach(square);

另外一个迭代器方法是every(),该方法接受一个返回值为布尔类型的函数,对数组中的每个元素使用该函数。如果对于所有的元素,该函数均返回true,则该方法返回true,下面是一个例子:


function isEven(num){
    return num % 2 == 0;
}

var nums = [2,4,6,8,10];
var even = nums.every(isEven);
if (even) {
    console.log("全是偶数")
} else {
    console.log("不全是偶数")
}



some()方法也接受一个返回值为布尔类型的函数,只要一个元素使得该函数返回true,该方法就返回true.

function isEven(num){
    return num % 2 == 0;
}
var nums = [1,2,4,5,6,7,8,9,10]
var someEven = nums.some(isEven);
console.log(someEven)

reduce()方法接受一个函数,返回一个值。该方法会从一个累加值开始,不断对累加值和数组中的后续元素调用该函数,直到数组中的最后一个元素,最后返回得到的累加值。下面这个例子展示了如何使用reduce()

function add(num1, num2){
    return num1 + num2;
}
var nums = [1,2,3,4,5,6,7,8,9,10];
var sum = nums.reduce(add);
console.log(sum);//55


reduce()方法和add()函数一起,从左至右,依次对数组中的元素求和,其执行过程如下:


add(1,2) -> 3
add(3,3) -> 6
add(6,4) -> 10
add(10,5) -> 15
add(15,6) -> 21
add(21,7) -> 28
add(28,8) -> 36
add(36,9) -> 45
add(45,10) -> 55



reduce()方法也可以用来将数组中的元素连成一个长的字符串。

function concat(accString, item){
    return accString + item;
}
var words = ['the ', 'quick ', 'brown ', 'fox '];
var sentence = words.reduce(concat)
console.log(sentence) ;//the quick brown fox

javascript还提供了reduceRight()方法,和reduce()不同,它是从右至左执行。下面的程序使用reduceRight()方法将数组中的元素进行翻转。

function concat(accString, item){
    return accString + item;
}
var words = ['the ', 'quick ', 'brown ', 'fox '];
var sentence = words.reduceRight(concat)
console.log(sentence) ;//fox brown quick the

2.生成新数组的迭代器方法

有两个迭代器方法可以产生新数组:map()和filter()。map()和forEach()有点儿像。对数组中的每个元素使用某个函数。两者的区别是map()返回一个新的数组,该数组的元素是对原有元素应用某个函数得到的结果。下面给出一个例子:

function curve(grade){
    return grade += 5;
}
var grades = [1,3,5,8,10];
var newgrades = grades.map(curve);
console.log(newgrades)

下面是对一个字符串数组使用map()方法的例子:


function first(word){
    return word[0]
}

var words = ['for', 'your', 'information'];
var acronym = words.map(first);
console.log(acronym.join(""));//fyi



filter()和every()类似,传入一个返回值为布尔类型的函数。和every()方法不同的是,当对数组中所有的元素应用该函数,当结果为true时,该方法不返回true,而是返回一个新数组。该组包含该函数结果为true的元素。下面是一个例子。


function isEven(num){
    return num % 2 == 0;
}

function isOdd(num){
    return num % 2 != 0;
}

var nums = [];
for (var i = 0; i < 20; ++i){
    nums[i] = i + 1;
}
console.log(nums)

var events = nums.filter(isEven)
console.log(events);//[2, 4, 6, 8, 10, 12, 14, 16, 18, 20]

var odds = nums.filter(isOdd);
console.log(odds);//[1, 3, 5, 7, 9, 11, 13, 15, 17, 19]



下面是使用filter()方法的有趣案例


function passing(num){
    return num >= 60;
}
var grades = [];
for (var i = 0; i < 20; ++i){
    grades[i] = Math.floor(Math.random()*101);
}
console.log(grades);//[4, 56, 87, 62, 24, 54, 80, 7, 95, 98, 40, 43, 56, 79, 84, 52, 87, 23, 43, 18]
var passGardes = grades.filter(passing);
console.log(passGardes);//[87, 62, 80, 95, 98, 79, 84, 87]随机



当然,还可以使用filter()过滤字符串数组,下面的这个例子展示了那些不包含"cie"的单词:


function after(str) {
    if (str.indexOf("cie") > -1) {
        return true
    }
    return false;
}
var words = ["recieve", "deceive" , "percieve", "deceit", "concieven"];
var nocie = words.filter(after);
console.log(nocie);//["recieve", "percieve", "concieven"]



六,二维和多维数组

javascript只支持一维数组,但是通过在数组里保存数组元素的方式,可以轻松创建多维数组。本节将讨论如何在javascript中创建二维数组。

1.创建二维数组

二维数组类似一种由行和列构成的数据表格。在javascript创建二维数组,需要创建一个数组,然后让数组的每个元素也是一个数组。最起码,我们需要知道二维数组要包含多少行,有了这个信息,就可以创建一个n行1列的二维数组了。

var twod = [];
var row = 5;
for (var i = 0; i < row; ++i){
    twod[i] = [];
}
console.log(twod);//[Array[0], Array[0], Array[0], Array[0], Array[0]]

这样做的问题是,数组中的每个元素都是undefined。更好的方式是通过扩展javascript数组对象,为其增加一个新方法。该方法根据传入的参数,设定了数组的行数,列数和初始值。下面是这个方法的定义;


Array.matrix = function(numrows, numcols, initial) {
    var arr = [];
    for (var i = 0; i < numrows; ++i){
        var columns = [];
        for (var j = 0; j < numcols; ++j) {
            columns[j] = initial;
        }
    arr[i] = columns
    }
    return arr;
}



下面是该测试方法的一些测试代码:

var nums = Array.matrix(5,5,0);
console.log(nums[1][1]);//0

var names = Array.matrix(3,3,"");
console.log(names)
names[1][2] = "Joe";

还可以使用使用一行代码和使用一组初始值来初始化一个二维数组

var grades = [[1,35,1],[123,52,14],[123,12,5,21,5,2]]

对于小规模数据,这是创建二维数组的最简单的方式。

2.处理二维数组的元素

处理二维数组中的元素,有两种最基本的方式:按列访问和按行访问。

对于这两种方式,我们均使用一组嵌入式的for循环。对于按列访问,外层循环对于行,内层循环对应列。

以数组grades为例,每一行对于一个学生的成绩记录。我们可以将该学生的所有成绩相加,然后除以科目数得到该学生的平均成绩。下面的代码展示了这个过程。


var grades = [[89,77,78],[76,62,81],[91,94,89]];
var total = 0;
var average = 0.0;
for (var row = 0; row < grades.length; ++i) {
    for (var col = 0; col < grades[row].length; ++col){
        total += grades[row][col]
    }

    average = total / grades[row].length;
    console.log("Student" + parseInt(row + 1) + " average: " + average.toFixed(2));
    total = 0;
    average = 0.0;



内层循环由这个表达式控制;

col < grades[row].length

这个表达式之所以多行,是因为每一行都是一个数组,我们可以使用数组的length属性判断每行包含多少行。

Student1 average: 81.33
Student2 average: 73.00
Student3 average: 91.33

对于按行访问,只需要稍微调整for循环的顺序,使外层循环对应列,内存循环对应行即可。下面的程序计算了一个学生的各科成绩。


var grades = [[89,77,78],[76,62,81],[91,94,89]];
var total = 0;
var average = 0.0;
for (var col = 0; col < grades.length; ++col) {
    for(var row = 0; row < grades[col].length; ++row){
        total += grades[row][col]
    }

    average = total / grades[col].length;
    console.log("Test " + parseInt(col+1) + "average " + average.toFixed(2));

    total = 0;
    average = 0.0;
}



输出

Test 1average 85.33
Test 2average 77.67
Test 3average 82.67

3.层次不齐的数组

层次不齐的数组是指数组中每行的元素个数彼此不同。很多编程语言在处理这样的数组时表现的都不是很好,但javascript表现良好,是因为每一行的长度可以通过计算得到。

为了给个示例,假设数组grades中,每个学生的成绩记录个数是不一样的,不用修改代码,依然可以正确计算出正确的平均分。


var grades = [[89,77],[76,82,81],[91,94,89,99]];
var total = 0;
var average = 0.0;
for (var row = 0; row < grades.length; ++row){
    
    for (var col = 0; col < grades[row].length; ++col){
        total += grades[row][col];
    }

    average = total / grades[row].length;
    console.log("Student" + parseInt(row + 1) + " average " + average.toFixed(2));

    total = 0;
    average = 0.0;
}



注意,第一名同学有两门课成绩,第二名有三门课成绩,第三名有4门课成绩。因为程序在内层for循环计算了每个数组的长度,即使数组中每一行的长度不一,程序依然不会出现什么问题。该段程序输出为:

Student1 average 83.00
Student2 average 79.67
Student3 average 93.25



七,对象数组

到目前为止,本章讨论的数组都只包含基本数据类型的元素,比如数字和字符串。数组还可以包含对象,数组的方法和属性对对象依然适用。

请看下面的例子:


function Point(x,y) {
    this.x = x;
    this.y = y;
}

function displayPts(arr) {
    for (var i = 0; i < arr.length; ++i) {
        console.log(arr[i].x + ", " + arr[i].y);
    }
}
var p1 = new Point(1,2);
var p2 = new Point(3,5);
var p3 = new Point(2,8);
var p4 = new Point(4,4);
var points = [p1,p2,p3,p4]

for (var i = 0 ; i < points.length; ++i) {
    console.log("Point " + parseInt(i+1) + ": " + points[i].x + ", " + points[i].y)
}

var p5 = new Point(12,-3);

points.push(p5)
displayPts(points);

points.shift();
console.log(points)

displayPts(points)



适用push()方法将点(12,-3)添加进数组,适用shift()方法将(1,2)从数组移除。

八,对象中的数组。

在对象中,可以使用数组存储复杂的数据。很多数据都能被实现成一个对象,对象内部使用数组保存数据。

下面的例子,我们创建了一个对象,用于保存观测到的最高气温数据,该对象有两个方法,一个方法用来增加一条新的气温记录,另外一个方法用来计算存储在对象中的平均气温。代码如下


function weekTemps() {
    this.dataStore = [];
    this.add = add;
    this.average = average;
}

function add(temp) {
    this.dataStore.push(temp)
}

function average() {
    var total = 0;
    for (var i = 0; i < this.dataStore.length; ++i) {
        total += this.dataStore[i];
    }
    return total / this.dataStore.length;
}

var thisWeek = new weekTemps();
thisWeek.add(52);
thisWeek.add(55);
thisWeek.add(61);
thisWeek.add(65);
thisWeek.add(55);
thisWeek.add(50);
thisWeek.add(52);
thisWeek.add(49);
console.log(thisWeek.average());//54.875



add()方法中用到了数组的push()方法,将元素添加到数组dataStore中,为什么这个方法名叫add()而不是叫push()?这是因为在自定义方法时,一个直观的名字是非常有用的技巧(不是所有人知道push一个元素是什么意思,但是所有人add一个元素是什么意思。)


javascript: 列表


在日常生活中,人们经常使用列表:待办事项列表,购物清单,十佳榜单,最后十名榜单等。计算机也在使用列表,尤其是列表中元素保存的是太多时。当不需要一个很长的序列中查找元素,或对其进行排序时,列表显得尤为有用。反之,如果数据结构非常复杂,列表的作用就没有那么大了。

本章展示了如果创建一个简单的列表类,我们首先给列表给出抽象的数据类型定义,然后描述如何实现抽象数据类型(ADT),最后,分析几个列表适合解决的实际问题。

一,列表的抽象数据类型定义

为了设计列表的抽象数据类型,需要给出列表的定义,包括列表应该有哪些属性,应该在列表上执行哪些操作。

列表是一组有序的数据,每个列表中的数据项称为元素。在javascript中,列表中的元素可以是任意数据类型。列表中可以保存多少元素并没有限定(在实际使用时会受到程序内存的限制)。

不包含任何元素的列表称为空列表。列表中包含元素的个数称为列表的length。在内部的实现上,用一个变量的listSize保存列表中元素的个数。可以在列表的末尾append一个元素,也可以给列表起始位置insert一个元素。使用remove方法从列表中删除元素,使用clear方法清空列表中的所有的元素。

还可以使用toString()方法显示列表中所有的元素,使用getElement()方法显示当前元素。 列表中拥有描述元素位置的属性。列表有前有后(front和end),使用next()方法可以从当前元素移动到下一个元素,使用prev()方法可以移动当前元素到上一个元素。还可以使用moveTo(n)方法直接移动到指定的位置。currPos属性表示列表中当前的位置。

列表的抽象数据类型并未指明列表的存储结构,在本章的实现中,我们使用一个dataStore来存储元素。

列表的抽象数据定义。


listSize(属性)     列表中元素的个数
pos(属性)     列表的当前位置
length(属性)     返回列表中元素的个数
clear(方法)     清空列表中所有的元素
toString(方法)     返回列表中的字符串形式
getElement(方法)     返回当前位置的元素
insert(方法 )     在现有元素后插入新元素
append(方法)     在列表末尾增加新元素
remove(方法)     从列表中删除元素
front(方法)     将列表中的当前元素设置到第一个元素
end(方法)     将列表中的当前元素位置移动到最后一个
prev(方法)     将当前位置后移一位
next(方法)     将当前位置前移一位
currPos(方法)     返回列表的当前位置
moveTo(方法)     将当前位置移动到指定位置

二,实现列表类

根据上面定义的列表抽象数据类型,可以直接实现一个List类,让我们从定义构造函数开始,虽然它本身并不是列表抽象数据类型的一部分。


function List() {
    this.listSize = 0;
    this.pos = 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;
}



1.append: 给列表添加元素

我们实现的第一个方法是append(),该方法给列表的下一个位置添加一个新的元素,这个位置刚好等于变量listSize的值。

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

当新元素就位后,变量的listSize就增加1

2.remove:从列表中删除元素

接下来我们看一下如何从列表中删除一个元素。remove()方法是List类中较难实现的一个方法。首先,要在列表中找到该元素,然后删除它。并且调整底层数组对象以填补删除元素后留下的空白。好消息是可以使用splice()方法来简化这一过程,我们先从一个辅助方法find()开始,该方法用于查找要删除的元素。

3.find在列表中查找某一元素

find()方法通过数组对象dataStore进行迭代,查找给定的元素。如果找到,就返回该元素的位置。如果找不到,返回-1.这是在数组中找不到元素时返回的标准值。我们可以在remove()方法中利用此值做错误校验。

remove方法使用find()方法返回的位置对数组dataStore进行截取。数组改变后,将变量listSize的值减1。以反映列表的最新长度。如果元素删除成功,则返回true,否则返回false.


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



4.length列表中有多少个元素

length()返回列表中元素的个数。

function length() {
    return this.listSize;
}

5.toStirng:显示列表中的元素

现在可以创建一个方法,用来显示列表中元素。下面是一段简短的代码,实现了toString()方法。

function toString() {
    return this.dataStore;
}

严格的来说,此方法返回的是一个数组,而不是一个字符串,但它的目的是为了显示当前的一个状态,因此返回一个数组就足够了。

我们暂时测试下目前实现的代码,检验我们之前创建的方法。


var names = new List();
names.append('锤锤');
names.append('牛牛');
names.append('豆豆');
console.log(names.dataStore);//["锤锤", "牛牛", "豆豆"]
names.remove('牛牛');

console.log(names.dataStore);//["锤锤", "豆豆"]



6.insert: 向列表中插入一个元素

接下来我们要讨论的方法是insert()。如果在前面的列表中删除“牛牛”,现在又想将它放回原来的位置,该怎么办?insert()方法需要知道元素插入到什么位置(因此,现在的实现方法是假设插入到列表中某个元素之后,知道足额写后,就可以定义insert()方法啦)。


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;
}



实现的过程中,insert()方法使用到find()方法,find()方法会找到传入的after参数在列表中的位置,找到该位置后,使用splice()得到将元素插入该位置后,然后将变量listSize加1并返回true.表明插入成功。

7.clear:清空列表中的所有元素。

接下来,我们需要一个方法清空列表中所有元素,为插入新元素腾出空间。

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

clear()方法使用delete操作符删除数组dataStore,接着创建新的空数组。最后一行将listSize和pos值设为0,表明是一个空的新列表。

8.判定给定值是否在列表中

当需要判断一个给定值是否在列表中时,contains()方法就变得很有用。下面是该方法定义:


function contains(element) {
    for (var i = 0; i < this.dataStore.length; ++i) {
        if (this.dataStore[i] == element) {
            return true;
        }
    }
    return false;
}



9.遍历列表

最后的一组方法允许用户在列表上自由移动,最后一个方法getElement()返回列表当前的元素


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

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

function prev() {
    if (this.pos > 0) {
        --this.pos;
    }
}

function next() {
    if (this.pos < this.listSize - 1) {
        ++this.pos;
    }
}

function currPos() {
    return this.pos;
}

function moveTo(position) {
    this.pos = position;
}

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



现在我们创建一个由姓名组成的列表,来展示怎么使用它。


var names = new List();
names.append('锤锤');
names.append('牛牛');
names.append('豆豆');
names.append('羊羊');
names.append('兔兔');
names.append('花花');



现在移动到列表中的第一个元素,并且显示它。

names.front();
console.log(names.getElement());//显示 “锤锤”

接下来向前移动一个单位并显示它:

names.next();
console.log(names.getElement()); //显示 “牛牛”

上面的代码展示这些行为实际上是迭代器的概念,这也是接下来要讨论的内容。

3.使用迭代器访问列表

使用迭代器,可以不必关系数据的内部存储方式。以实现对列表的遍历。前面提到的方法fornt(),end(),prev(),next()和currPos就实现了List类的一个迭代器。以下是和使用数组索引的方式相比,使用迭代器的一些优点。

访问列表元素时不必关心底层的数据存储结构
当为列表添加一个元素时,索引的值就不对了,此时只用更新列表,而不用更新迭代器。
可以用不同类型的数据存储方式实现List类,迭代器为访问列表里的元素提供了统一的方式。

了解了这些优点后,我使用一个迭代器遍历列表的例子:

for(names.front(); names.currPos() < names.length(); names.next()) {
    console.log(names.getElement())
}

在for循环的一开始,将列表中的当前位置设置为第一个元素。只要currPos的值小于列表的长度,就一直循环,每一次循环都调用next()方法将当前的位置向前移动一位。

同理,还可以从后向前遍历列表,代码如下:

for (names.front(); names.currPos() >= 0; names.prev()) {
    console.log(names.getElement())
}


循环从列表的最后一个元素开始,当 当前位置大于或等于0时,调用prev()方法后移一位。

迭代器只是用来在列表上随意移动,而不应该和人和为列表增加或删除元素的方法一起使用。

四,一个基于列表的应用。

1.读取文本

为了展示如何使用列表,我们实现一个类似Redbox的租赁自助查询系统。

var _movies = "(1)RogueTrader(《魔鬼营业员》)NNN(2)TradingPlaces(《颠倒乾坤》)NNN(3)WallStreet(《华尔街》)NNN(4)WallStreet2:MoneyNeverSleeps(《华尔街2:金钱永不眠》)NNN(5)BoilerRoom(《开水房》)NNN(6)GlengarryGlen Ross(《拜金一族》)NNN(7)Enron:TheSmartestGuysInTheRoom(《安然风暴:屋内聪明人》)NNN(8)Trader(《交易员》)NNN(9)AmericanPsycho(《美国精神病人》)NNN(10)BonfireoftheVanities(《虚荣的篝火》)";
var movies = _movies.split("NNN");

上面的split()程序将字符串分割为数组,多一个空格,虽然多一个空格无伤大雅,但是在比较字符串时是个灾难,因此,我们需要在循环里使用trim()方法删除每个数组元素末尾的空格。要是有一个函数能将这些操作封装起来就再好不过了。


function createArr(file){
  var arr = file.split("NNN");
  for (var i = 0; i < arr.length; ++i) {
     arr[i] = arr[i].trim();
  }
  return arr;
}



2.使用列表管理影碟租赁

下面要将数组保存到一个列表,代码如下:

var movieList = new List();

for (var i = 0;  i < movies.length; ++i) {
    movieList.append(movies[i])
}

现在可以写一个函数来显示影碟清单了:

function displayList(list) {
    for (list.front(); list.currPos() < list.length(); list.next()) {
        console.log(list.getElement())
    }
}

displayList()函数对于原生的数据类型没有什么问题,比如由字符串组成的列表。但是它用不了自定义类型。比如我们将下面定义的Customer对象。让我对它稍微做修改,让它可以发现列表是由Customer对象组成的。这样就可以对应的进行显示了。下面是重新定义的displayList()函数:


function displayList(list) {
    for (list.front(); list.currPos() < list.length(); list.next()) {
        if (list.getElement() instanceof Customer) {
            console.log(list.getElement()['name'] + ", " +
                list.getElement()["movie"]
                );
        }

        else {
            console.log(list.getElement())
        }
    }
}



对于列表中的每一个元素,都使用instanceof操作符判断元素是否是Customer对象。如果是,就使用name和movie做索引。得到客户检出的值。如果不是,就返回该元素即可。

现在已经有了movies,还需要创建一个新的列表,Customers,用来保存在系统中检出电影的客户:

var customers = new List();

该列表包含Customer对象,该对象由用户的姓名和用户检出电影组成。下面是Costomer对象的构造函数。

function Customer(name, movie) {
    this.name = name;
    this.movie = movie;
}

接下来,需要创建一个允许用户检出的电影函数。该函数有两个参数:客户端姓名和客户想要检出的电影。如果改电影目前可以租赁,该方法会从清单里删除该元素,同时加入客户列表customers.这个操作会用到列表的contains()方法。

下面是用于检出电影的函数:


function checkout(name, movie, filmList, customerList) {
    if (movieList.contains(movie)) {
        var c = new Customer(name, movie);
        customerList.append(c);
        filmList.remove(movie)
    }
    else {
        console.log(movie + "is not available")
    }
}



下面使用简单的代码测试checkout函数


var movies =  createArr(_movies);
var movieList = new List();
var customers = new List();
for (var i = 0; i < movies.length; ++i) {
    movieList.append(movies[i])
}

//显示xx
displayList(movieList)

checkout("RogueTrader","交易员",movieList,customers);
//xx

displayList(customers)



对于列表的方法,就更新至此,可以根据自己的需要,增加更健壮的方法去实现。

符:测试代码


function List() {
    this.listSize = 0;
    this.pos = 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;
}

//给列表添加元素
function append(element) {
    this.dataStore[this.listSize++] = element;
}

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

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

//length
function length() {
    return this.listSize;
}

//toString
function toString() {
    return this.dataStore;
}

//insert
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;
}

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

//contains判断给定值是否在列表中
function contains(element) {
    for (var i = 0; i < this.dataStore.length; ++i) {
        if (this.dataStore[i] == element) {
            return true;
        }
    }
    return false;
}

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

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

function prev() {
    if (this.pos > 0) {
        --this.pos;
    }
}

function next() {
    if (this.pos < this.listSize - 1) {
        ++this.pos;
    }
}

function currPos() {
    return this.pos;
}

function moveTo(position) {
    this.pos = position;
}

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

//var names = new List();
//names.append('锤锤');
//names.append('牛牛');
//names.append('豆豆');
//names.append('羊羊');
//names.append('兔兔');
//names.append('花花');

//console.log(names.dataStore);

//names.front();
//console.log(names.getElement());//显示 “锤锤”

//names.next();

//console.log(names.getElement()); //显示 “豆豆”

//  for(names.front(); names.currPos() < names.length(); names.next()) {
//     console.log(names.getElement())
// }

var _movies = "(1)RogueTrader(《魔鬼营业员》) NNN(2)TradingPlaces(《颠倒乾坤》)NNN(3)WallStreet(《华尔街》)NNN(4)WallStreet2:MoneyNeverSleeps(《华尔街2:金钱永不眠》)NNN(5)BoilerRoom(《开水房》)NNN(6)GlengarryGlen Ross(《拜金一族》)NNN(7)Enron:TheSmartestGuysInTheRoom(《安然风暴:屋内聪明人》)NNN(8)Trader(《交易员》)NNN(9)AmericanPsycho(《美国精神病人》)NNN(10)BonfireoftheVanities(《虚荣的篝火》)   ";

function createArr(file){
  var arr = file.split("NNN");
  for (var i = 0; i < arr.length; ++i) {
     arr[i] = arr[i].trim();
  }
  return arr;
}

var movies =  createArr(_movies)

//将数组保存到一个列表
var movieList = new List();

for (var i = 0;  i < movies.length; ++i) {
    movieList.append(movies[i])
}

//console.log(movieList)
var customers = new List();

//显示影碟清单
function displayList(list) {
    for (list.front(); list.currPos() < list.length(); list.next()) {
        if (list.getElement() instanceof Customer) {
            console.log(list.getElement()['name'] + ", " +
                list.getElement()["movie"]
                );
        }

        else {
            console.log(list.getElement())
        }
    }
}

//displayList(movieList.dataStore)

function Customer(name, movie) {
    this.name = name;
    this.movie = movie;
}

//检出电影的函数
function checkout(name, movie, filmList, customerList) {
    if (movieList.contains(movie)) {
        var c = new Customer(name, movie);
        customerList.append(c);
        filmList.remove(movie)
    }
    else {
        console.log(movie + "is not available")
    }
}

displayList(movieList)