数据结构与算法Javascript描述

, ,

JavaScript 的编程环境和模型

一、数组

数组是一种特殊的对象，用来表示偏移量的索引是该对象的属性，索引可 能是整数。

Array.isArray() 来判断一个对象是否是数组

【浅复制】新数组依然指向原来的数组。当把一个数组赋给另外一个数组时，只是为被赋值的数组增加了一个新的引用。当 你通过原引用修改了数组的值，另外一个引用也会感知到这个变化。

1
2
3
4
5
6
7
var nums = [];
for (var i = 0; i < 100; ++i) {
	nums[i] = i+1;
}
var samenums = nums;
nums[0] = 400;
print(samenums[0]); // 显示 400

【深复制】将 原数组中的每一个元素都复制一份到新数组中。

1
2
3
4
5
6
7
8
var nums = [];
for (var i = 0; i < 100; ++i) {
	nums[i] = i+1;
}
var samenums = [];
copy(nums, samenums);
nums[0] = 400;
print(samenums[0]); // 显示 1

存取函数

  • indexOf()

  • 将数组转化为字符串 join() 、toString()

  • 由已有数组创建新数组 合并concat() 、 截取splice()

可变函数

  • 为数组添加元素 push() 和 unshift()

  • 从数组中删除元素 pop() shift()

  • 从数组中间位置添加和删除元素 splice()

  • 为数组排序 reverse()翻转 sort()

迭代器方法

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

every() 该方法接受一个返回值为布尔类型的函数，对数组中的每 个元素使用该函数。如果对于所有的元素，该函数均返回 true，则该方法返回 true

1
2
3
4
5
6
7
8
9
10
11
12
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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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() 方法接受一个函数，返回一个值。该方法会从一个累加值开始，不断对累加值和 数组中的后续元素调用该函数，直到数组中的最后一个元素，最后【返回得到的累加值】。

reduceRight() 从右到左执行

1
2
3
4
5
6
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

生成新数组的迭代器方法 map() 和 filter()

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
//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

//filter() 和 every() 类似，传入一个返回值为布尔类型的函数
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;
}
var evens = nums.filter(isEven);
print("Even numbers: ");
print(evens);
var odds = nums.filter(isOdd);
print("Odd numbers: ");
print(odds);

二维和多维数组

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

对象数组

二、列表

列表是一组有序的数据。每个列表中的数据项称为元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//列表的抽象数据类型定义
listSize（属性） 列表的元素个数
pos（属性） 列表的当前位置
length（属性） 返回列表中元素的个数
clear（方法） 清空列表中的所有元素
toString（方法） 返回列表的字符串形式
getElement（方法） 返回当前位置的元素
insert（方法） 在现有元素后插入新元素
append（方法） 在列表的末尾添加新元素
remove（方法） 从列表中删除元素
front（方法） 将列表的当前位置设移动到第一个元素
end（方法） 将列表的当前位置移动到最后一个元素
prev（方法） 将当前位置后移一位
next（方法） 将当前位置前移一位
currPos（方法） 返回列表的当前位置
moveTo（方法） 将当前位置移动到指定位置

三、栈

后进先出

栈就是和列表类似的一种数据结构，栈是一种高效的数据结构，因为数据只能在栈顶添加或删除，所以这样的操作很快，而且容易实现。 栈的使用遍布程序语言实现的方方面面，从表达式求值到处理函数调用。

1
2
3
4
5
6
7
function Stack() {
  this.dataStore = [];
  this.top = 0;
  this.push = push;
  this.pop = pop;
  this.peek = peek;
}

【回文】是指这样一种现象：一个单词、短语或数字，从前往后写和从后往前写都是一样的。 比如，单词“dad”、“racecar”就是回文；如果忽略空格和标点符号，下面这个句子也是回 文，“A man, a plan, a canal: Panama”；数字 1001 也是回文。

使用栈判断一个单词是否是回文

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
function isPalindrome(word) {
  var s = new Stack();
  for (var i = 0; i < word.length; ++i) {
    s.push(word[i]);
  }
  var rword = "";
  while (s.length() > 0) {
    rword += s.pop();
  }
  if (word == rword) {
    return true;
  }
  else {
    return false;
  }
}
var word = "hello";
if (isPalindrome(word)) {
	print(word + " is a palindrome.");
}
else {
	print(word + " is not a palindrome.");
}
word = "racecar"
if (isPalindrome(word)) {
	print(word + " is a palindrome.");
}
else {
	print(word + " is not a palindrome.");
}

使用栈模拟递归过程

1
2
3
4
5
6
7
8
9
10
11
12
13
function fact(n) {
  var s = new Stack();
  while (n > 1) {
  	s.push(n--);
  }
  var product = 1;
  while (s.length() > 0) {
  	product *= s.pop();
  }
  return product;
}
print(factorial(5)); // 显示 120
print(fact(5)); // 显示 120

四、队列

先进先出

队列是一种列表，不同的是队列只能在队尾插入元素，在队首删除元素。队列用于存储按 顺序排列的数据，先进先出，这点和栈不一样，在栈中，最后入栈的元素反而被优先处 理。

队列是一种先进先出（First-In-First-Out，FIFO）的数据结构。队列被用在很多地方，比如 提交操作系统执行的一系列进程、打印任务池等，一些仿真系统用队列来模拟银行或杂货 店里排队的顾客。

五、链表

链表是由一组节点组成的集合。每个节点都使用一个对象的引用指向它的后继。指向另一 个节点的引用叫做链。

双向链表

循环链表

六、字典

字典是一种以键 - 值对形式存储数据的数据结构，就像电话号码簿里的名字和电话号码一 样。

Dictionay 类的基础是 Array 类，而不是 Object 类。

七、散列

散列是一种常用的数据存储技术，散列后的数据可以快速地插入或取用。散列使用的数据 结构叫做散列表。在散列表上插入、删除和取用数据都非常快，但是对于查找操作来说却 效率低下，比如查找一组数据中的最大值和最小值。

碰撞

当散列函数对于多个输入产生同样的输出时，就产生了碰撞。

  • 开链法 开链法是指实现散列表的底层数组中，每个数组 元素又是一个新的数据结构，比如另一个数组，这样就能存储多个键了。
  • 线性探测法 线性探测法隶属于一种更一般化的散列技术：开放 寻址散列。当发生碰撞时，线性探测法检查散列表中的下一个位置是否为空。如果为空， 就将数据存入该位置；如果不为空，则继续检查下一个位置，直到找到一个空的位置为 止。该技术是基于这样一个事实：每个散列表都会有很多空的单元格，可以使用它们来存 储数据。

八、集合

集合是由一组无序但彼此之间又有一定相关性的成员构成的，每个成员在集合中只能出现 一次。在数学上，用大括号将一组成员括起来表示集合，比如 {0,1,2,3,4,5,6,7,8,9}。集合 中成员的顺序是任意的，因此前面的集合也可以写做 {9,0,8,1,7,2,6,3,5,4}，或者其他任意 形式的组合，但是必须保证每个成员只能出现一次。

  • 不包含任何成员的集合称为空集，全集则是包含一切可能成员的集合。
  • 如果两个集合的成员完全相同，则称两个集合相等。
  • 如果一个集合中所有的成员都属于另外一个集合，则前一集合称为后一集合的子集。

并集、交集、补集

Set类

定义 union()、subset() 和 difference()

九、二叉树

树是一种非线性的数据结构，以分层的方式 存储数据。树被用来存储具有层级关系的数据，比如文件系统中的文件；树还被用来存储 有序列表。

二叉树。选择树而不是那些基本的数据结构，是因 为在二叉树上进行查找非常快（而在链表上查找则不是这样），为二叉树添加或删除元素 也非常快（而对数组执行添加或删除操作则不是这样）。

二叉查找树BST

相对较小的值保存在左节点中，较大的值保存在右节点中。这一特性使得 查找的效率很高，对于数值型和非数值型的数据，比如单词和字符串，都是如此。

1
2
3
4
5
6
7
8
9
function Node(data, left, right) {
  this.data = data;
  this.left = left;
  this.right = right;
  this.show = show;
}
function show() {
	return this.data;
}

查找正确插入点

(1) 设根节点为当前节点。
(2) 如果待插入节点保存的数据小于当前节点，则设新的当前节点为原节点的左节点；反
之，执行第 4 步。
(3) 如果当前节点的左节点为 null，就将新的节点插入这个位置，退出循环；反之，继续
执行下一次循环。
(4) 设新的当前节点为原节点的右节点。
(5) 如果当前节点的右节点为 null，就将新的节点插入这个位置，退出循环；反之，继续
执行下一次循环。

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
function BST() {
  this.root = null
  this.insert = insert
  this.inOrder = inOrder
}
function insert(data) {
  var n = new Node(data, null, null)
  if (this.root == null) {
  	this.root = n
  } else {
    var current = this.root
    var parent
    while (true) {
    	parent = current
      if (data < current.data) {
    	current = current.left
        if (current == null) {
    	parent.left = n
    	break
        }
      } else {
        current = current.right
        if (current == null) {
          parent.right = n
          break
        }
      }
    }
  }
}

遍历二叉查找树

三种遍历 BST 的方式：中序、先序和后序。中序遍历按照节点上的键值，以升序访问 BST 上的所有节点。先序遍历先访问根节点，然后以同样方式访问左子树和右子树。后序 遍历先访问叶子节点，从左子树到右子树，再到根节点。

中序遍历使用递归的方式最容易实现。该方法需要以升序访问树中所有节点，先访问左子 树，再访问根节点，最后访问右子树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function inOrder(node) {
  if (!(node == null)) {
    inOrder(node.left);
    putstr(node.show() + " ");
    inOrder(node.right);
  }
}
var nums = new BST();
nums.insert(23);
nums.insert(45);
nums.insert(16);
nums.insert(37);
nums.insert(3);
nums.insert(99);
nums.insert(22);
print("Inorder traversal: ");
inOrder(nums.root);
//Inorder traversal:
//3 16 22 23 37 45 99

在二叉查找树上进行查找

(1) 查找给定值

需要比较该值和当前节点上的值的大小。通过比较，就能确定如果 给定值不在当前节点时，该向左遍历还是向右遍历。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function find(data) {
  var current = this.root;
  while (current != null) {
    if (current.data == data) {
      return current;
    }
    else if (data < current.data) {
      current = current.left;
    }
    else {
      current = current.right;
    }
  }
  return null;
}

(2) 查找最小值

(3) 查找最大值

从二叉查找树上删除节点

从 BST 上删除节点的操作最复杂，其复杂程度取决于删除哪个节点。如果删除没有子节点 的节点，那么非常简单。如果节点只有一个子节点，不管是左子节点还是右子节点，就变得稍微有点复杂了。删除包含两个子节点的节点最复杂。

计数

BST 的一个用途是记录一组数据集中数据出现的次数。比

十、图

图由边的集合及顶点的集合组成。

顶点也有权重，也称为成本。如果一个 图的顶点对是有序的，则可以称之为有向图。

图是无序的，则称之为无序图，或无向图。

1
2
3
4
5
6
7
8
9
10
11
function Graph(v) {
  this.vertices = v;
  this.edges = 0;
  this.adj = [];
  for (var i = 0; I < this.vertices; ++i) {
    this.adj[i] = [];
    this.adj[i].push("");
  }
  this.addEdge = addEdge;
  this.toString = toString;
}

搜索图 深度优先搜索和广 度优先搜索

深度优先搜索包括从一条路径的起始顶点开始追溯，直到到达最后一个顶点，然后回溯， 继续追溯下一条路径，直到到达最后的顶点，如此往复，直到没有路径为止。

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
40
41
42
function Graph(v) {
  this.vertices = v;
  this.edges = 0;
  this.adj = [];
  for (var i = 0; i < this.vertices; ++i) {
    this.adj[i] = [];
    this.adj[i].push("");
  }
  this.addEdge = addEdge;
  this.showGraph = showGraph;
  this.dfs = dfs;
  this.marked = [];
  for (var i = 0; i < this.vertices; ++i) {
  	this.marked[i] = false;
  }
}
function addEdge(v, w) {
  this.adj[v].push(w);
  this.adj[w].push(v);
  this.edges++;
}
function showGraph() {
  for (var i = 0; i < this.vertices; ++i) {
  	putstr(i + " -> ");
    for (var j = 0; j< this.vertices; ++j) {
    if (this.adj[i][j] != undefined)
      putstr(this.add[i][j] + ' ');
    }
    print();
  }
}
function dfs(v) {
  this.marked[v] = true;
  if (this.adj[v] != undefined) {
  	print("Visited vertex: " + v);
  }
  for each(var w in this.adj[v]) {
    if (!this.marked[w]) {
      this.dfs(w);
    }
  }
}

广度优先搜索从第一个顶点开始，尝试访问尽可能靠近它的顶点。本质上，这种搜索在图 上是逐层移动的，首先检查最靠近第一个顶点的层，再逐渐向下移动到离起始顶点最远的 层。

广度优先搜索对应的最短路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function bfs(s) {
  var queue = [];
  this.marked[s] = true;
  queue.push(s); // 添加到队尾
  while (queue.length > 0) {
    var v = queue.shift(); // 从队首移除
    if (v == undefined) {
      print("Visisted vertex: " + v);
    }
    for each(var w in this.adj[v]) {
      if (!this.marked[w]) {
        this.edgeTo[w] = v;
        this.marked[w] = true;
        queue.push(w);
      }
    }
  }
}

拓扑排序会对有向图的所有顶点进行排序，使有向边从前面的顶点指向后面的顶点。

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
function topSort() {
  var stack = [];
  var visited = [];
  for (var i = 0; i < this.vertices; i++) {
  	visited[i] = false;
  }
  for (var i = 0; i < this.vertices; i++) {
    if (visited[i] == false) {
      this.topSortHelper(i, visited, stack);
    }
  }
  for (var i = 0; i < stack.length; i++) {
    if (stack[i] != undefined && stack[i] != false) {
      print(this.vertexList[stack[i]]);
    }
  }
}
function topSortHelper(v, visited, stack) {
  visited[v] = true;
  for each(var w in this.adj[v]) {
    if (!visited[w]) {
      this.topSortHelper(visited[w], visited, stack);
    }
  }
  stack.push(v);
}

十一、排序算法

冒泡排序

最慢的排序算法之一，但也是一种最容易实现的排 序算法。数据值会像气泡一样从数组的一端漂 浮到另一端。

1
2
3
4
5
6
7
8
9
10
11
function bubbleSort() {
  var numElements = this.dataStore.length;
  var temp;
  for ( var outer = numElements; outer >= 2; --outer) {
    for ( var inner = 0; inner <= outer - 1; ++inner ) {
      if (this.dataStore[inner] > this.dataStore[inner + 1]) {
      swap(this.dataStore, inner, inner + 1);
      }
    }
  }
}

选择排序

选择排序从数组的开头开始，将第一个元素和其他元 素进行比较。检查完所有元素后，最小的元素会被放到数组的第一个位置，然后算法会从 第二个位置继续。这个过程一直进行，当进行到数组的倒数第二个位置时，所有的数据便 完成了排序。选择排序会用到嵌套循环。

1
2
3
4
5
6
7
8
9
10
11
12
13
function selectionSort() {
  var min, temp;
  for (var outer = 0; outer <= this.dataStore.length-2; ++outer) {
    min = outer;
    for (var inner = outer + 1;
    inner <= this.dataStore.length-1; ++iner) {
      if (this.dataStore[inner] < this.dataStore[min]) {
        min = inner;
      }
      swap(this.dataStore, outer, min);
    }
  }
}

插入排序

插入排序类似于人类按数字或字母顺序对数据进行排序。插入排序有两个循环。外循环将数组元素挨个移动，而内循环则对外循环中选中的元素及 它后面的那个元素进行比较。如果外循环中选中的元素比内循环中选中的元素小，那么数 组元素会向右移动，为内循环中的这个元素腾出位置，就像之前介绍的姓氏卡片一样。

1
2
3
4
5
6
7
8
9
10
11
12
function insertionSort() {
  var temp, inner;
  for (var outer = 1; outer <= this.dataStore.length - 1; ++outer) {
    temp = this.dataStore[outer];
    inner = outer;
    while (inner > 0 && (this.dataStore[inner - 1] >= temp)) {
      this.dataStore[inner] = this.dataStore[inner - 1];
      --inner;
    }
    this.dataStore[inner] = temp;
  }
}

高级排序算法 希尔排序

这个算法在插入排序的基础上做了很大的改善。

工作原理是，通过定义一个间隔序列来表示在排序过程中进行比较的元素之 间有多远的间隔。我们可以动态定义间隔序列，不过对于大部分的实际应用场景，算法 要用到的间隔序列可以提前定义好。有一些公开定义的间隔序列，使用它们会得到不同 的结果。

高级排序算法 归并排序

把一系列排好序的子序列合并成一个大的完整有序序列。

  • 自顶向下的归并排序
  • 自底向上的归并排序

高级排序算法 快速排序

快速排序是处理大数据集最快的排序算法之一。它是一种分而治之的算法，通过递归的方 式将数据依次分解为包含较小元素和较大元素的不同子序列。该算法不断重复这个步骤直 到所有数据都是有序的。

首先要在列表中选择一个元素作为基准值（pivot）。数据排序围绕基准值进行， 将列表中小于基准值的元素移到数组的底部，将大于基准值的元素移到数组的顶部。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function qSort(list) {
  if (list.length == 0) {
     return [];
  }
  var lesser = [];
  var greater = [];
  var pivot = list[0];
  for (var i = 1; i < list.length; i++) {
    if (list[i] < pivot) {
    	lesser.push(list[i]);
    } else {
    	greater.push(list[i]);
    }
  }
  return qSort(lesser).concat(pivot, 		qSort(greater));
}

十二、检索算法

顺序查找（线性查找）

最简单的方法就是从列表的第一个元素开始对列表元素逐个进行判 断，直到找到了想要的结果，或者直到列表结尾也没有找到。

查找最小值和最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function findMin(arr) {
  var min = arr[0];
  for (var i = 1; i < arr.length; ++i) {
    if (arr[i] < min) {
    	min = arr[i];
    }
  }
  return min;
}
function findMax(arr) {
  var max = arr[0];
  for (var i = 1; i < arr.length; ++i) {
    if (arr[i] > max) {
    	max = arr[i];
    }
  }
  return max;
}

二分查找算法

二分查找算法比顺序查找算法更高效

  1. 将数组的第一个位置设置为下边界（0）

  2. 将数组最后一个元素所在的位置设置为上边界（数组的长度减 1）

  3. 若下边界等于或小于上边界，则做如下操作。

    1. a. 将中点设置为（上边界加上下边界）除以 2。
    2. b. 如果中点的元素小于查询的值，则将下边界设置为中点元素所在下标加 1。
    3. c. 如果中点的元素大于查询的值，则将上边界设置为中点元素所在下标减 1。
    4. d. 否则中点元素即为要查找的数据，可以进行返回
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
function binSearch(arr, data) {
  var upperBound = arr.length-1;
  var lowerBound = 0;
  while (lowerBound <= upperBound) {
    var mid = Math.floor((upperBound + lowerBound) / 2);
    if (arr[mid] < data) {
      lowerBound = mid + 1;
    }
    else if (arr[mid] > data) {
      upperBound = mid - 1;
    }
    else {
      return mid;
    }
  }
  return -1;
  }
  var nums = [];
  for (var i = 0; i < 100; ++i) {
  	nums[i] = Math.floor(Math.random() * 101);
  }
  insertionsort(nums);
  dispArr(nums);
  print();
  putstr(" 输入一个要查找的值：");
  var val = parseInt(readline());
  var retVal = binSearch(nums, val);
  if (retVal >= 0) {
    print(" 已找到 " + val + " ，所在位置为：" + retVal);
  }
  else {
  print(val + " 没有出现在这个数组中。");
}

十三、高级算法

动态规划

动态规划实例：计算斐波那契数列

动态规划有时被认为是一种与递归相反 的技术。递归是从顶部开始将问题分解，通过解决掉所有分解出小问题的方式，来解决整 个问题。动态规划解决方案从底部开始解决问题，将所有小问题解决掉，然后合并成一个 整体解决方案，从而解决掉整个大问题。

背包问题、寻找最长公共子串

贪心算法

贪心算法总是会选择当下的最优解，而不去考虑这一 次的选择会不会对未来的选择造成影响。是一种以寻找“优质解”为手段从而达成整体解决方案的算法。这些优质的解决 方案称为局部最优解。

找零问题、背包问题