javascript数据结构和算法[转]
字符串表示的数组
join() 和 toString() 函数返回数组的字符串表示.这两个函数通过将数组中的元素用逗号分隔符分割,返回字符串数组表示.
这里有个例子:
var names = ["David", "Cynthia", "Raymond", "Clayton", "Mike", "Jennifer"];
var namestr = names.join();
print(namestr); // David,Cynthia,Raymond,Clayton,Mike,Jennifer
namestr = names.toString();
print(namestr);
//打印 David,Cynthia,Raymond,Clayton,Mike,Jennifer
当你调用print()函数来打印数组时,它自动的为数组调用toString()函数.
print(names);
//打印 David,Cynthia,Raymond,Clayton,Mike,Jennifer
从已有数组中创建一个新的数组
concat()和splice()两个函数允许你从一个已有的数组创建一个新的数组.
concat()函数允许你将两个或者多个数组连接创建一个新的数组.
splice()函数允许你从一个已有数组创建一个子数组.
下面我们来看看concat()函数时如何工作的.
一个已有的数组调用concat()函数,并且传入另外一个数组作为参数.
这个参数将会连接到数组的后面.下面的程序显示concat():
var cisDept = ["Mike", "Clayton", "Terrill", "Danny", "Jennifer"];
var dmpDept = ["Raymond", "Cynthia", "Bryan"];
var itDiv = cisDept.concat(dmpDept);
print(itDiv);
itDiv = dmp.concat(cisDept);
print(itDiv);
程序将会输出:
Mike,Clayton,Terrill,Danny,Jennifer,Raymond,Cynthia,Bryan
Raymond,Cynthia,Bryan,Mike,Clayton,Terrill,Danny,Jennifer
第一行的输出显示是cisDept数组先输出.
第二行的输出显示是dmpDept数组先输出.
splice()函数从已有数组的内容中创建一个新的数组.
传递给数组的参数是开始分割的数组位置和获取数组元素的长度.
var itDiv = ["Mike","Clayton","Terrill","Raymond","Cynthia","Danny","Jennifer"]; var dmpDept = itDiv.splice(3,3);
var cisDept = itDiv;
print(dmpDept); // Raymond,Cynthia,Danny
print(cisDept); // Mike,Clayton,Terrill,Jennifer
slice()函数还有其他的用处,例如向数组中添加或者删除元素.
赋值函数
javascript提供一系列赋值函数,它们允许你不使用引用单个元素来修改数组内容.这些函数使复杂的赋值技术变得简单.
向数组中添加元素
push()和shift()函数可以用来向数组中添加元素.
push()函数用来向数组的尾部添加元素:
var nums = [1,2,3,4,5];
print(nums); // 1,2,3,4,5
nums.push(6);
print(nums); // 1,2,3,4,5,6
使用push()函数比使用length属性添加更加直观.
var nums = [1,2,3,4,5];
print(nums); // 1,2,3,4,5
nums[nums.length] = 6;
print(nums); // 1,2,3,4,5,6
向数组的首部比向数组的尾部添加数组更加困难.
如果不使用赋值函数的处理的话.那么数组中每个已知的元素都需要在新数据插入之前向后移动一位.
下面的代码来解释这个问题.
var nums = [2,3,4,5];
var newnum = 1;
var N = nums.length;
for (var i = N; i >= 0; --i) {
nums[i] = nums[i-1];
}
nums[0] = newnum;
print(nums); // 1,2,3,4,5
如果数组中存储数据的个数增长时这段代码将会越来越低效.
向数组的首部添加元素的赋值函数是unshift();
var nums = [2,3,4,5];
print(nums); // 2,3,4,5
var newnum = 1;
nums.unshift(newnum);
print(nums); // 1,2,3,4,5
nums = [3,4,5];
nums.unshift(newnum,1,2);
print(nums); // 1,2,3,4,5
你可以一次向函数传递多个元素来向数组首部添加元素.
移除数组中的元素
从数组的尾部移除数据可以简单的使用pop()赋值函数:
var nums = [1,2,3,4,5,9];
nums.pop();
print(nums); // 1,2,3,4,5
在不使用赋值语句的情况下,从数组的首部移除元素需要将数组的所有元素向前移动,这时会出现刚才向数组首部添加元素一样的低效.
var nums = [9,1,2,3,4,5];
print(nums);
for (var i = 0; i < nums.length; ++i) {
nums[i] = nums[i+1];
}
print(nums); // 1,2,3,4,5,
除了我们需要左移动数组元素以外的事实,我们还留下了一个多余的的元素.
当我们打印数组的时候,我们发现了在数组的尾部出现了一个多余的逗号.
从数组首部移除元素的赋值函数是shift().
var nums = [9,1,2,3,4,5];
nums.shift();
print(nums); // 1,2,3,4,5
你会发现在数组的尾部并没有出现多余的元素.
pop()函数和shift()函数都将会返回被移除的元素,所以你可以将它们存储到一个变量中.
var nums = [6,1,2,3,4,5];
var first = nums.shift(); // first gets the value 6
nums.push(first);
print(nums); // 1,2,3,4,5,6
向数组的中间部位添加或者删除元素
slice()函数可以用来向数组中添加或者删除元素.
使用slice()向数组中添加元素,你需要提供以下的参数.
开始下标(你想要插入元素的起始位置)
需要移除的元素个数(0表示你要添加元素)
你想要添加的元素
下面我们来看一个向数组中间添加元素的例子.
var nums = [1,2,3,7,8,9];
var newElements = [4,5,6];
nums.splice(3,0,newElements);
print(nums); // 1,2,3,4,5,6,7,8,9
插入数组的元素并不一定要是一个有名数组,它可以是任何形式的列表.
var nums = [1,2,3,7,8,9];
nums.splice(3,0,4,5,6);
print(nums);
在上面的例子中,4,5,6就代表着我们要插入到nums中的列表元素.
下面是一个使用splice()函数从数组中移除元素的例子.
var nums = [1,2,3,100,200,300,400,4,5];
nums.splice(3,4);
print(nums); // 1,2,3,4,5
给数组元素排序
最后两个赋值函数被用来对数组元素进行某种形式的排序.
第一个函数时reverse().将数组中的元素进行翻转.
var nums = [1,2,3,4,5];
nums.reverse();
print(nums); // 5,4,3,2,1
我们经常需要对数组中的元素进行排序.完成这个任务的赋值函数时sort(),它能够很好的处理字符串.
var names = ["David","Mike","Cynthia","Clayton","Bryan","Raymond"];
nums.sort();
print(nums); // Bryan,Clayton,Cynthia,David,Mike,Raymond
但是sort()却不能很好的处理数字.
var nums = [3,1,2,100,4,200];
nums.sort();
print(nums); // 1,100,2,200,3,4
sort()函数像字典一样,假定数组元素是字符串,因为在先前的的例子中,数组元素是数字.为了让其正确的对数字进行排序.我们可以向其传递一个排序函数作为第一个参数,.sort()函数将会用它来比较数组的元素对来决定它们的正确顺序.
对于数字来说,排序函数可以简单的将一个数减去另一个数.如果返回值是负数,表示左边的操作数小于右边的操作数,如果等于0,表示它们相等,如果大于0表示左边的操作数大于右边的操作数.
基于这一点,让我们重新运行之前的小程序.
.function compare(num1, num2) {
return num1 - num2;
}
var nums = [3,1,2,100,4,200];
nums.sort(compare);
print(nums); // 1,2,3,4,100,200
sort()函数使用compare()来数字化而不是字典化的排序数组.
迭代函数
我们要讲的最后一部分函数是迭代函数.
这些函数可以为每个数组元素执行一个操作,要么返回一个值,一个值的集合,或者是一个新的数组.
不生成新数组的迭代函数
我们首先要讨论的是不生成新数组迭代函数,取而代之,它们要么对数组的每个元素执行某些操作,要么生成一个简单的值.
第一个迭代函数是forEach().这个函数使用一个函数作为参数并且使每个数组元素调用该函数.
function square(num) {
print(num, num * num);
}
var nums = [1,2,3,4,5,6,7,8,9,10];
nums.forEach(square);
函数的输出是:
1 1
2 4
3 9
4 16
5 25
6 36
7 49
8 64
9 81
10 100
接下来的一个函数时every().向数组传递一个返回值为boolean类型的函数.
如果数组中的每个元素调用参数函数时都返回true,函数返回true.
function isEven(num) {
return num % 2 == 0;
}
var nums = [2,4,6,8,10];
var even = nums.every(isEven);
if (even) {
print("all numbers are even");
} else {
print("not all numbers are even");
}
返回的结果是:
all numbers are even
如果我们将数组改为:
var nums = [2,4,6,7,8,10];
那么程序将会输出:
not all numbers are even
some()函数同样带一个Boolean函数作为参数.并且在数组中至少有一个元素在调用参数函数之后返回true时返回true.
function isEven(num) {
return num % 2 == 0;
}
var nums = [1,2,3,4,5,6,7,8,9,10];
var someEven = nums.some(isEven);
if (someEven) {
print("some numbers are even");
} else {
print("no numbers are even");
}
nums = [1,3,5,7,9];
someEven = nums.some(isEven);
if (someEven) {
print("some numbers are even");
} else {
print("no numbers are even");
}
函数的结果是:
some numbers are even
no numbers are even
reduce()函数使用一个累加器作为参数,并且连续的计算直到数组结束.返回一个单值.
下面是一个使用reduce()对数组元素进行总计.
function add(runningTotal, currentValue) {
return runningTotal + currentValue;
}
var nums = [1,2,3,4,5,6,7,8,9,10];
var sum = nums.reduce(add);
print(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(accumulatedString,item){
return accumulatedString+item;
}
var words = [‘the’,’quick’,’brown’,’fox’];
var sentence = words.reduce(concat);
print(sentence);//打印“the quick brown fox”
javascript还提供了一个reduceRight()函数,它非常类似于reduce()函数,只是它是从右边往左边计算.下面的程序使用reduceRight()来对数组元素进行翻转操作.
function concat(accumulatedString,item){
return accumulatedString+item;
}
var words = [‘the’,’quick’,’brown’,’fox’];
var sentence = words.reduceRight(concat);
print(sentence); // displays "fox brown quick the"
返回新数组的迭代函数
map()和filter()是两个返回新数组的迭代函数.
map()类似于forEach()函数,为数组的每一个元素调用一个函数.
不同点是map()会返回调用函数之后的生成的新数组.
function curve(grade){
return grade += 5;
}
var grades = [77,65,81,92,83];
var newgrades = grades.map(curve);
print(newgrades);//82,70,86,97,88
下面是使用字符串的例子:
function first(word){
return word[0];
}
var words = [‘for’,’your’,’information’];
var acronym = words.map(first);
print(acronym.join(“”));//display ‘fyi’
在这个例子中,acronym数组保存了words数组中每个元素字符串的第一个字母.
然而,如果我们想展现数组中每个元素的首字母缩略词,我们需要调用toString()函数来使用逗号分隔数组的元素.
这里我们使用join()函数并且使用一个空字符串作为其分隔符.
filter()函数类似于every(),但是并不像every()那样返回一个Boolean值,它返回那些在调用给定函数之后返回true的那些数组元素.
function isEven(num){
return num % 2 == 0;
}
function isOdd(num){
return num % 2 !=0;
}
var nums = [];
for(var i=0;i<20; ++i){
num[i] = i+1;
}
var evens = nums.filter(isEven);
print(“Even numbers:”);
print(evens);
var odds = num.filter(isOdd);
print(“Odd numbers:”);
print(odds);
程序最终输出:
Even numbers:
2,4,6,8,10,12,14,16,18,20
Odd numbers:
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);
}
var passGrades = grades.filter(passing);
print("All grades: );
print(grades);
print("Passing grades: ");
print(passGrades);
程序输出:
All grades:
39,43,89,19,46,54,48,5,13,31,27,95,62,64,35,75,79,88,73,74
Passing grades: 89,95,62,64,75,79,88,73,74
当然,我们的filter可以使用在字符串上.
function after(c){
if(c.indexOf(‘cie’)>-1){
return true;
}
return false;
}
var words = ["recieve","deceive","percieve","deceit","concieve"];
var misspelled = words.filter(afterc);
print(misspelled); // displays recieve,percieve,concieve
二维数组和多维数组
javascript数组是一维的,但是你可以通过数组的数组这种形式来创建多维数组.
在这部分,我们将会讨论如何创建二维数组.
创建二维数组
二维数组的结构类似于电子表格那样带有行和列.
为了在javascript中创建二维数组,我们需要首先创建一个数组,然后使数组中的每个元素同样是一个数组.
至少,我们需要知道我们这个数组包含的行数.有了这个信息,我们就可以创建一个n行1列的二维数组了.
var twod = [];
var rows = 5;
for(var i=0;i<rows;++i){
var twod[i] = [];
}
这个方法的问题在于数组的每个元素都被设置为undefined.
创建二维数组的更好的方式就是遵循Javascript:Good Parts.
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);
print(nums[1][1]); // displays 0
var names = Array.matrix(3,3,"");
names[1][2] = "Joe";
print(names[1][2]); // display "Joe"
同样,我们可以创建一个二维数组并且在一行里初始化它们.
var grades = [[89,77,78],[76,82,81],[91,94,89]];
print(grades[2][2]);
对于小的数据集合,这种方法是创建一个二维数组最方便的方法.
加工二维数组的元素
加工一个二维数组有两种基本的模式.一种模式强调一列一列的获取.而另一种模式则强调从行获取元素.我们将会使用前面写过的代码片段grades数组 来演示这些模式的工作方式.
对于两种模式来说,我们都需要设置一系列嵌套的循环.,对于列获取模式来说,我们的外部循环在每行移动,而内部循环这是在列上移动.
对于grades数组,考虑到每一行代表着一个学生的一系列成绩
我们可以通过总计每一行的数值然后除以该行所有的元素个数算出每个学生的成绩.下面的代码展现的就是这个过程.
var grades = [[89, 77, 78],[76, 82, 81],[91, 94, 89]];
var total = 0;
var average = 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;
print(‘Student “ + parseInt(row+1)+ “ average: “ + average.toFixed(2));
total = 0;
average = 0.0;
}
内部循环被表达式:
col < grades[row].length;
控制.
这个之所以能正常工作是因为每一行都包含了一个数组,并且我们可以通过数组的length属性来得知数组每行有多少列.
每个学生成绩的平均值都使用toFixed(n)精确到2位.
Student 1 average: 81.33
Student 2 average: 79.67
Student 3 average: 91.33
为了展现按列计算.我们只需要简单的移动for循环使外部循环控制列,内部循环控制行.
var grades = [[89, 77, 78],[76, 82, 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;
print("Test " + parseInt(col+1) + " average: " + average.toFixed(2));
total = 0; average = 0.0;
}
程序的输出是：
Test 1 average: 85.33
Test 2 average: 84.33
Test 3 average: 82.67
参差不齐的数组
参差不齐的数组是指数组的每一行可能有不同数量的元素．一行可能有三个元素同时另一行可能只有一个元素．许多程序语言在处理这些参差不齐的数组时都会感到棘手．但是javascript 确不会.因为我们能够计算数组任意一行的长度.
举个例子.学生的成绩数组中学生拥有不同数量的成绩记录.我们甚至不需要修改程序就能够计算出每个学生成绩的平均值.
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;
print("Student " +parseInt(row+1) + " average: " + average.toFixed(2));
total = 0;
average = 0.0;
}
注意第一个学生有两个成绩,第二个学生有三个成绩,而第四个学生却有4个成绩.因为成绩计算每一列的长度,所以层次不齐的数组依然不会影响到程序.
下面是程序输出的结果:
Student 1 average: 83.00
Student 2 average: 79.67
Student 3 average: 93.25
数组对象
在这一章的所有例子中,数组的元素都是基本的数据类型,如数字和字符串.
数组同样可以包含对象,并且数组原有的属相和方法同样有效.
function Point(x,y) {
this.x = x; this.y = y;
}
function displayPts(arr) {
for (var i = 0; i < arr.length; ++i) {
print(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) {
print("Point " + parseInt(i+1) + ": " + points[i].x + ", " +points[i].y);
}
var p5 = new Point(12,-3);
points.push(p5);
print("After push: ");
displayPts(points);
points.shift();
print("After shift: ");
displayPts(points);
程序输出为:
Point 1: 1, 2
Point 2: 3, 5
Point 3: 2, 8
Point 4: 4, 4
After push:
1, 2
3, 5
2, 8
4, 4
12, -3
After shift:
3, 5
2, 8
4, 4
12, -3
point 12,-3 通过使用push()加入到数组中.point 1,2通过使用shift()移出数组.
对象中的数组
我们可以在对象中使用数组存储复杂的数据.我们在这本书中使用的许多数据结构都是通过实现一个对象,并且通过使用对象中的数组来存储数据的.
下面是该书使用的一些技巧.
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);
print(thisWeek.average()); // displays 54.875
