数据结构-准备

发表于 | 分类于 |
  • 《数据结构与算法JavaScript描述》读书笔记之一
  • 前两章为数组的方法复习

chapter-1 JavaScript编程环境和模型

语句

  • JavaScript中的switch语句和其他编程语言的一个主要区别是：在JavaScript中，用来判断的表达式可以是任意类型，不仅限于整型；而C++和Java等一些语言就要求该表达式必须为整型

    循环

  • while和for的用法：
    • 如果希望条件为真时执行一组语句，就选择while循环
    • 如果希望按执行次数执行一组语句，就选择for循环

      函数

  • 提供两种定义函数的方式：
    • 一种有返回值，目的是得到返回值
    • 一种没有返回值，也叫子程、void函数，目的是执行定义操作
  • JavaScript中，函数的参数传递方式都是按值传递，没有按引用传递的参数。但是JavaScript中有保存引用的对象，比如数组（可以按引用传递）。

    变量作用域

  • JavaScript拥有的是函数作用域，含义是JavaScript中没有块级作用域（可以在编写for循环的时候假设有），ES6的let可以实现

    递归

  • 任何可以被递归定义的函数，都可以被改写外迭代式的程序

chapter-2 数组

定义

  • 一个存储元素的线性集合（collection），元素可以通过索引来任意存取，索引通常是数字，用来计算元素之间存储位置的偏移量。
  • JavaScript的数组是一种特殊的对象（效率不如其他语言高），表示偏移量的索引是该对象的属性，索引可能是整数（内部转换为字符串类型，因为JavaScript对象中的属性名必须是字符串）

    数组操作

    创建

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    var numbers = [];// 创建
    numbers.length; // 长度
    var numbers = new Array(1,2,3,4,5);
    numbers.length; // 5
    var numbers = new Array(10); // 创建了一个长度为10的数组
    var numbers = 3;
    Array.isArray(numbers);// false 判断一个对象是否是数组
    // 字符串对象的split()方法也可以生成数组
    var sentence = 'the quick brown fox jumped over the lazy dog';
    words = sentence.split(' ');
1.jpeg

整体操作

浅复制：新数组依然指向原来的数组
深复制：原数组中的每一个元素都复制一份到新数组中

存取函数

一组用来访问数组元素的函数

  • indexOf 查找第一个匹配
  • lastIndexOf 查找最后一个匹配
  • join 返回字符串
  • toString 转换字符串
  • concat 合并多个数组创建新数组
  • splice 起始索引、截取长度、添加的元素
  • push，unshift 添加元素
  • pop， shift 删除元素
  • splice 添加元素
  • reverse 翻转
  • sort 排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 查找
var names = ['David', 'Mike', 'Cynthia', 'Claytou', 'Bryan', 'Raymond'];
names.indexOf('CCC');// -1
var names = ['David', 'Mike', 'Cynthia', 'Claytou', 'Bryan', 'Raymond'];
names.lastIndexOf('Bryan');// 4
// 添加
var nums = [1,2,3,7,8,9];
var newElement = [4,5,6];
nums.splice(3, 0, 4, 5, 6);
// 添加数组
var nums = [1,2,3,7,8,9];
var newElement = [4,5,6];
nums.splice(3, 0, newElement);
// 删除
var nums = [1,2,3,100,200,300,400,4,5];
nums.splice(3,4);
5.jpeg 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
var nums = [1,2,3,4,5];
nums.reverse();
// 按照字典顺序排序，假定元素都是字符串类型，即使是数字类型的元素，也被认为是字符串类型
var names = ['David', 'Mike', 'Cynthia', 'Claytou', 'Bryan', 'Raymond'];
names.sort();
var nums = [3,1,2,100,4,200];
nums.sort();
// 传入比较大小的函数，根据大小决定数组顺序
// 小 -> 大
var nums = [3,1,2,100,4,200];
nums.sort(function(num1, num2){
	return num1 - num2;
});
// 大 -> 小
var nums = [3,1,2,100,4,200];
nums.sort(function(num1, num2){
	return num2 - num1;
});
sort 说明
  • 若 a 小于 b，在排序后的数组中 a 应该出现在 b 之前，则返回一个小于 0 的值。
  • 若 a 等于 b，则返回 0。
  • 若 a 大于 b，则返回一个大于 0 的值。
  • 参考w3school：http://www.w3school.com.cn/jsref/jsref_sort.asp
2.jpeg

迭代器方法

不生成新数组的迭代器方法

执行操作或返回一个值

  • forEach
  • every 接受一个返回值，数组的每个元素使用该函数，如果所有的元素，该函数均返回true，则该方法返回true
  • some 接受一个返回值为布尔类型的函数，只要有一个元素使得该函数返回true，该方法返回true
  • reduce 累加值，不断对累加值和数组中后续元素调用该函数，例如数组求和
  • reduceRight
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    // some every
    var nums = [2,4,6,8,9];
    function isEven(num) {
    	return num % 2 === 0;
    }
    nums.every(isEven);// false
    nums.some(isEven);// true
    // reduce reduceRight
    var nums = ['1','2','3','4','5','6','7','8','9'];
    function add(total, current) {
    	return total + current;
    }
    nums.reduce(add);
    nums.reduceRight(add);
3.jpeg
生成新数组的迭代器方法
  • map 原有函数应用某个函数，返回新数组
  • filter 传入一个返回值为boolean的函数，返回新数组（true）
1
2
3
4
5
6
7
8
9
10
11
12
13
// map
function first(word){
	return word[0];
}
var words = ['for', 'your', 'information'];
var newwords = words.map(first);
// filter
function isOdd (num) {
	return num % 2 !== 0;
}
var nums = [1,2,3,4,5,6,7,8,9];
nums.filter(isOdd);
4.jpeg

二维多维数组

类似一种由行和列构成的数据表格

6.jpeg 7.jpeg 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// 生成带默认值的二维数组
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);
nums[1][2] = 3;
// 处理二维数组元素，按列访问，和按行访问
// 按行访问
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;
    console.log(total);
    console.log(average);
    total = 0;
    average = 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(average.toFixed(2));
    total = 0;
}