《数据结构与算法JavaScript描述》(笔记)

数组

定义

一个存储元素的线性集合，元素可以通过索引来任意存取，索引通常是数字，用来计算元素之间存储位置的偏移量。

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

由于Array在JavaScript中被当做对象，因此它有许多属性和方法可以在编程时使用。

创建数组

1. 字面量
   最简单的方式是通过[]操作符声明一个数组变量：

   var numbers = [1,2];

通过这种方式，你将得到一个长度为2的空数组。可以通过调用内建的length属性来验证这一点：

print(numbers.length); // 2

2. 构造函数

var numbers = new Array(1,2);

当只传一个参数，该参数用来指定数组的长度，而不是数组的第一个元素：

var numbers = new Array(2);// 创建了一个长度为2的空数组[,]

在脚本语言里很常见的一个特性是，数组中的元素不必是同一种数据类型。

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

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

var numbers = 1;
var arr = [1,2];
console.log(Array.isArray(numbers));// 显示false
console.log(Array.isArray(arr));// 显示true

大多数JavaScript专家推荐使用[]操作符，和使用Array的构造函数相比，这个方式被认为效率更高。

读写数组

可以通过[]操作符将数据赋给数组

var nums = [];
nums[0] = 1;
console.log(nums[0]);// 1

还可以使用[]操作符读取数组中的元素

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

javascript中的数组也是对象，数组的长度可以任意增长，超出其创建时指定的长度。

由字符串生成数组

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

var str = "hello world";
var arr = str.split(" ");
console.log(arr);// ["hello", "world"]

对数组的整体性操作

首先，可以将一个数组赋给另外一个数组：

var arr1 = [1,2];
var arr2 = arr1;
console.log(arr1);// [1,2]
console.log(arr2);// [1,2]

当把一个数组赋给另外一个数组时，只是为被赋值的数组增加了一个新的引用。当你通过原引用修改了数组的值，另外一个引用也会感知到这个变化。

var arr1 = [1,2];
var arr2 = arr1;
arr1[0] = 0;
console.log(arr1);// [0,2]
console.log(arr2);// [0,2]

这种行为被称为浅复制，新数组依然指向原来的数组。一个更好的方案是使用深复制，将原数组中的每一个元素都复制一份到新数组中。可以写一个深复制函数来做这件事。

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

查找元素

indexOf用来查找传进来的参数在目标数组中是否存在。如果目标数组包含该参数，就返回该元素在数组中的索引；如果不包含，就返回-1。如果数组中包含多个相同的元素，则总是返回第一个与参数相同的元素的索引。有另外一个功能与之类似的函数：lastIndexOf,该函数返回相同元素中最后一个元素的索引，如果没有找到相同元素，则返回-1。

数组的字符串表示

join和toString返回一个包含数组所有元素的字符串，各元素之间用逗号分隔开。

var arr = [1,2];
console.log(arr.toString());// "1,2"
console.log(arr.join());// "1,2"
console.log(arr.join("-"));// "1-2"

由已有数组创建新数组

concat的发起者是一个数组，参数是另一个数组。作为参数的数组，其中的所有元素都被连接到调用concat()方法的数组后面。

var arr1 = [1];
var arr2 = [2];
var arr3 = arr1.concat(arr2);
console.log(arr3);// [1,2]

splice方法的第一个参数是截取的起始索引，第二个参数是截取的长度。

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

为数组添加元素

push方法将一个元素添加到数组末尾

var arr = [1];
arr.push(2);
console.log(arr);// [1,2]

unshift方法可以将元素添加到数组的开头

var arr = [1];
arr.unshift(2);
console.log(arr);

从数组中删除元素

pop方法可以删除数组末尾的元素

var arr = [1,2];
arr.pop();
console.log(arr);// 1

shift方法可以删除数组的第一个元素

var arr = [1,2];
arr.shift();
console.log(arr);// 2

pop和shift方法都将删除的元素作为方法的返回值返回。

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

使用splice为数组添加元素

1. 起始索引（也就是你希望开始添加元素的地方）
2. 需要删除的元素个数（添加元素时该参数设为0）
3. 想要添加进数组的元素

插入元素

var arr1 = [1,2];
arr1.splice(1,0,3,4);
console.log(arr1);// [1,3,4,2]

删除元素

var arr1 = [1,2,3];
arr1.splice(1,1);
console.log(arr1);// [1,3]

为数组排序
reverse,将数组中元素的顺序进行翻转。

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

sort,将数组排序,是按照字典顺序进行排序的，即使元素是数字类型，也被认为是字符串类型。

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

为了让sort()方法也能排序数字类型的元素，可以在调用方法时传入一个大小比较函数，排序时，sort()方法将会根据该函数比较数组中两个元素的大小，从而决定整个数组的顺序。

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

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

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

var arr = [1,2];
arr.forEach(function (item) {
    console.log(item);
});
// 1
// 2

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

var arr = [1,2];
var ret = arr.every(function (item) {
    return item > 0;
});
console.log(ret);// true

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

var arr = [1,2];
var ret = arr.some(function (item) {
    return item > 1;
});
console.log(ret);// true

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

function add(total, value) {
    return total + value;
}
var arr = [1,2,3];
var sum = arr.reduce(add);
console.log(sum);// 6

reduce也可以将数组元素连接成一个长的字符串

function concat(total, value) {
    return total + value;
}
var arr = ['1','2','3'];
var sum = arr.reduce(concat);
console.log(sum);// 123

reduceRight和reduce方法不同，它是从右到左执行。

function concat(total, value) {
    return total + value;
}
var arr = ['1','2','3'];
var sum = arr.reduceRight(concat);
console.log(sum);// 321

生成新数组的迭代器方法

map和forEach有点像，对数组的每个元素使用某个函数。两者的区别是map返回一个新的数组，该数组的元素是对原有元素应用某个函数得到的结果。

var arr = [1, 2];
var newArr = arr.map(function(item) {
    return item + 1;
});
console.log(newArr);// [2, 3]

filter和every类似，传入一个返回值为布尔类型的函数。该方法返回一个新数组，该数组包含应用该函数后结果为true的元素。

var arr = [1,2,3];
var newArr = arr.filter(function(item) {
    return item % 2;
});
console.log(newArr);// [1, 3]

二维和多维数组

JavaScript只支持一维数组，但是通过在数组里保存数组元素的方式，可以轻松创建多维数组。

创建二维数组

创建一个n行1列的二维数组：

var arr = [];
var rows = 2;
for (var i = 0; i < rows; ++i) {
    arr[i] = [];
}
console.log(arr);// [Array(0), Array(0)]

还可以仅用一行代码就创建并且使用一组初始值来初始化一个二维数组：

var arr = [[1, 2], [1, 2], [1, 2]];
console.log(arr[0][1]);// 2

处理二维数组的元素

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

对于按列访问，外层循环对应行，内层循环对应列。

var arr = [[1, 2], [1, 2]];
for (var i = 0; i < arr.length; ++i) {
    for (var j = 0; j < arr[i].length; ++j) {
        console.log(arr[i][j]);
    }
}
// 1
// 2
// 1
// 2

按行访问，外层循环对应列，内层循环对应行。

var arr = [[1, 2], [1, 2]];
for (var i = 0; i < arr.length; ++i) {
    for (var j = 0; j < arr[i].length; ++j) {
        console.log(arr[j][i]);
    }
}
// 1
// 1
// 2
// 2

对象数组

数组还可以包含对象

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

对象中的数组

对象内部使用数组保存数据

function weekTemps() {
    this.data = [];
    this.add = add;
}
function add(temp) {
    this.data.push(temp);
}
var thisWeek = new weekTemps();
thisWeek.add(1);
console.log(thisWeek.data); // [1]

列表

当不需要在一个很长的序列中查找元素，或者对其进行排序时，列表显得尤为有用。反之，如果数据结构非常复杂，列表的作用就没有那么大了。

列表的抽象数据类型定义

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

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

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

下表展示了列表的完整抽象数据类型定义

实现列表类

让我们从定义构造函数开始，虽然它本身并不是列表抽象数据类型定义的一部分

function List() {
    this.listSize = 0;
    this.pos = 0;
    this.dataStore = [];
    this.clear = clear;
    this.find = find;
    this.toString = toString;
    this.insert = insert;
    this.append = appendl
    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.length = length;
    this.contains = contains;
}

append:给列表添加元素

该方法给列表的下一个位置增加一个新的元素

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

find: 在列表中查找某一元素

find方法通过对数组对象dataStore进行迭代，查找给定的元素。如果找到，就返回该元素在列表中的位置，否则返回-1。

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

使用迭代器访问列表

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

1. 访问列表元素时不必关心底层的数据存储结构
2. 当为列表添加一个元素时，索引的值就不对了，此时只用更新列表，而不用更新迭代器。
3. 可以用不同类型的数据存储方式实现cList类，迭代器为访问列表里的元素提供了一种统一的方式
   来看一下使用迭代器遍历列表的例子

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

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

栈

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

对栈的操作

栈是一种特殊的列表，栈内的元素只能通过列表的一端访问，这一端称为栈顶。栈被称作一种后入先出的数据结构。

对栈的两种主演操作是将一个元素压入栈和将一个元素弹出栈。入栈使用push()方法，出栈使用pop方法。

另一个常用的操作是预览栈顶的元素。pop()方法虽然可以访问栈顶的元素，但是调用该方法后，栈顶元素也从栈中被永久性地删除了。peek()方法则只返回栈顶元素，而不删除它。

为了记录栈顶元素的位置，同时也为了标记哪里可以加入新元素，我们使用变量top,当向栈内压入元素时，该变量增大；从栈内弹出元素时，该变量减小。
clear方法清除栈内所有元素，length属性记录栈内元素的个数。我们还定义了一个empty属性，用以表示栈内是否含有元素，不过使用length属性也可以达到同样的目的。

栈的实现

我们的实现以定义Stack类的构造函数开始：

function Stack() {
    this.dataStore = [];
    this.top = 0;
    this.push = push;
    this.pop = pop;
    this.peek = peek;
}

push方法

function push(element) {
    this.dataStore[this.top++] = element;
}

pop方法

function pop() {
    return this.dataStore[--this.top];
}

peek方法

function peek() {
    return this.dataStore[this.top-1];
}

length方法

function length() {
    return this.top;
}

clear方法

function clear() {
    this.top = 0;
}

使用-数制间的相互转换

可以利用栈将一个数字从一种数制转换成另一种数值。假设想将数字n转换为以b为基数的数字，实现转换的算法如下。

1. 最高位为n%b,将此位压入栈
2. 使用n/b代替n
3. 重复步骤1和2，直到n等于0，且没有余数
4. 持续将栈内元素弹出，直到栈为空，依次将这些元素排列，就得到转换后数字的字符串形式

此算法只针对基数为2-9的情况

function mulBase(num, base) {
    var s = new Stack();
    do {
        s.push(num % base);
        num = Math.floor(num /= base);
    } while (num > 0);
    var converted = "";
    while (s.length() > 0) {
        converted += s.pop();
    }
    return converted;
}

使用-递归演示

栈常常被用来实现编程语言，使用栈实现递归即为一例。详细讲解如何使用栈来实现递归过程超出了本书范围，这里只用栈来模拟递归过程。
下面是一个递归函数

function factorial(n) {
    if (n === 0) {
        return 1;
    } else {
        return n * factorial(n-1);
    }
}
console.log(factorial(5));// 120

使用栈模拟递归

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;
}
console.log(fact(5));// 120

队列

队列是一种列表，不同的是队列只能在队尾插入元素，在队首删除元素。队列用于存储按顺序排列的数据，先进先出。

对队列的操作

插入操作也叫做入队，删除操作也叫做出队。入队操作在队尾插入新元素，出队操作删除队头的元素。

读取队头的元素叫做peek(),该操作返回队头元素，但不把它从队列中删除。length属性说明了队列中存储了多少元素；clear方法用于清空队列中的所有元素。

一个用数组实现的队列

数组的push方法可以在数组末尾加入元素，shift()方法可删除数组的第一个元素。
先实现一个Queue类，

function Queue() {
    this.dataStore = [];
    this.enqueue = enqueue;
    this.dequeue = dequeue;
    this.front = front;
    this.back = back;
    this.toString = toString;
    this.empty = empty;
}

enqueue()方法向队尾添加一个元素

function enqueue(element) {
    this.dataStore.push(element);
}

dequeue()方法删除队首的元素

function dequeue() {
    return this.dataStore.shift();
}

可以使用如下方法读取队首和队尾的元素

function front() {
    return this.dataStore[0];
}
function back() {
    return this.dataStore[this.dataStore.length-1];
}

toString方法显示队列内的所有元素

function toString() {
    var retStr = "";
    for (var i = 0; i < this.dataStore.length; ++i) {
        retStr += this.dataStore[i] + "\n";
    }
    return retStr;
}

判读队列是否为空

function empty() {
    if (this.dataStore.length === 0) {
        return true;
    } else {
        return false;
    }
}

优先队列

也有一些使用队列的应用，在删除元素时不必遵守先进先出的约定。这种应用，需要使用一个叫做优先队列的数据结构来进行模拟。
先来定义存储队列元素的对象，然后再构建我们的优先队列系统：

function Patient(name, code) {
    this.name = name;
    this.code = code;
}

现在需要重新定义dequeue方法，使其删除队列中拥有最高优先级的元素。我们规定：优先码的值最小的元素优先级最高。新的dequeue方法遍历队列的底层存储数组，从中找出优先码最低的元素，然后使用数组的splice方法删除优先级最高的元素。新的dequeue方法定义如下所示：

function dequeue() {
    var priority = this.dataStore[0].code;
    for (var i = 1; i < this.dataStore.length; ++i) {
        if (this.dataStore[i].code < priority) {
            priority = i;
        }
    }
    return this.dataStore.splice(priority, 1);
}

链表

数组的缺点

数组不总是组织数据的最佳数据结构，原因如下。在很多编程语言中，数组的长度是固定的，所以当数组已被数据填满时，再要加入新的元素就会非常困难。在数组中，添加和删除元素也很麻烦，因为需要将数组中的其他元素向前或向后平移，以反映数组刚刚进行了添加或删除操作。当然，JavaScript的数组并不存在上述问题，因为使用split方法不需要再访问数组中的其他元素了。

JavaScript中数组的主要问题是，它们被实现成了对象，与其他语言（比如C++和Java）的数组相比，效率很低。

如果你发现数组在实际使用时很慢，就可以考虑使用链表来替代它。除了对数据的随机访问，链表几乎可以用在任何可以使用一维数组的情况中。如果需要随机访问，数组仍然是更好的选择。

定义链表

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

数组元素靠它们的位置进行引用，链表元素则是靠相互之间的关系进行引用。我们说bread跟在milk后面，而不说bread是链表中的第二个元素。遍历链表，就是跟着链接，从链表的首元素一直走到尾元素（但这不包括链表的头节点，头节点常常用来作为链表的接入点）。图中另外一个值得注意的地方是，链表的尾元素指向一个null节点。

链表中插入一个节点的效率很高。向链表中插入一个节点，需要修改它前面的节点（前驱），使其指向新加入的节点，而新加入的节点则指向原来前驱指向的节点。

从链表中删除一个元素也很简单。将待删除元素的前驱节点指向待删除元素的后继节点，同时将待删除元素指向null，元素就删除成功了。

链表还有其他一些操作，但插入和删除元素最能说明链表为什么如此有用。

设计一个基于对象的链表

我们设计的链表包含两个类。Node类用来表示节点，LinkedList类提供了插入节点、删除节点、显示列表元素的方法，以及其他一些辅助方法。

Node类

Node类包含两个属性：element用来保存节点上的数据，next用来保存指向下一个节点的链接。我们使用一个构造函数来创建节点，该构造函数设置了这两个属性的值：

function Node(element) {
    this.element = element;
    this.next = null;
}

LinkedList类

LList类提供了对链表进行操作的方法。该类的功能包括插入删除节点、在列表中查找给定的值。该类也有一个构造函数，链表只有一个属性，那就是使用一个Node对象来保存该链表的头节点。

function LList() {
    this.head = new Node("head");
    this.find = find;
    this.insert = insert;
    this.remove = remove;
    this.display = display;
}

head节点的next属性被初始化为null，当有新元素插入时，next会指向新的元素，所以在这里我们没有修改next的值

插入新节点

首先介绍如何在一个一直节点后面插入元素，在一个已知节点后面插入元素时，先要找到“后面”的节点。首先创建一个辅助方法find,该方法遍历链表，查找给定数据。如果找到数据，该方法就返回保存该数据的节点。

function find(item) {
    var currNode = this.head;
    while (currNode.element != item) {
        currNode = currNode.next;
    }
    return currNode;
}

一旦找到“后面”的节点，就可以将新节点插入链表了。首先，将新节点的next属性设置为“后面”节点的next属性对应的值。然后设置“后面”节点的next属性指向新节点。

function insert(newElement, item) {
    var newNode = new Node(newElement);
    var current = this.find(item);
    newNode.next = current.next;
    current.next = newNode;
}

在定义一个display方法

function display() {
    var currNode = this.head;
    while (!(currNode.next == null)) {
        console.log(currNode.next.element);
        currNode = currNode.next;
    }
}

从链表中删除一个节点

从链表中删除节点时，需要先找到待删除节点前面的节点。找到这个节点后，修改它的next属性，使其不再指向待删除节点，而是指向待删除节点的下一个节点。首先定义findPrevious方法：

function findPrevious(item) {
    var currNode = this.head;
    while (!(currNode.next == null) && (currNode.next.element != item)) {
        currNode = currNode.next;
    }
    return currNode;
}

remove方法

function remove(item) {
    var prevNode = this.findPrevious(item);
    if (!(prevNode.next == null)) {
        prevNode.next = prevNode.next.next;
    }
}

双向链表

链表从后向前遍历不容易，双向链表很容易做到，下图演示了双向链表的工作原理

首当其冲的是要为Node类增加一个previous属性

function Node(element) {
    this.element = element;
    this.next = null
    this.previous = null;
}

insert方法

function insert(newElement, item) {
    var newNode = new Node(newElement);
    var current = this.find(item);
    newNode.next = current.next;
    newNode.previous = current;
    current.next = newNode;
}

remove方法比单向链表的效率更高，因为不需要再查找前驱节点了。

remove方法

function remove(item) {
    var currNode = this.find(item);
    if (!(currNode.next == null)) {
        currNode.previous.next = currNode.next;
        currNode.next.previous = currNode.previous;
        currNode.next = null;
        currNode.previous = null;
    }
}

为了完成以反序显示链表中元素这类任务，findLast方法找出了链表中的最后一个节点

function findLast() {
    var currNode = this.head;
    while (!(currNode.next == null)) {
        currNode = currNode.next;
    }
    return currNode;
}

反序显示链表中元素

function dispReverse() {
    var currNode = this.head;
    currNode = this.findLast();
    while (!(currNode.previous == null)) {
        console.log(currNode.element);
        currNode = currNode.previous;
    }
}

循环链表

循环链表和单向链表相似，唯一的区别是，让其头节点的next属性指向它本身

head.next = head

这种行为会传导至链表中的每个节点，使得每个节点的next属性都指向链表的头节点，换句话说。链表的尾节点指向头节点，形成了一个循环链表

修改LList类的构造函数

function LList() {
    this.head = new Node("head");
    this.head.next = this.head;
    this.find = find;
    this.insert = insert;
    this.display = display;
    this.findPrevious = findPrevious;
    this.remove = remove;
}

只需要修改一处，就将单向链表变成循环链表。其他方法也需要做一下修改，比如display

function display() {
    var currNode = this.head;
    while (!(currNode.next == null) && !(currNode.next.element == "head")) {
        console.log(currNode.next.element);
        currNode = currNode.next;
    }
}

链表的其他方法

advance(n)
在链表中向前移动n个节点
back(n)
在双向链表中向后移动n个节点
show()
只显示当前节点

字典

字典是一种以键-值对形式存储数据的数据结构，JavaScript的Object类就是以字典的形式设计的。

Dictionary类

Dictionary类的基础是Array类，而不是Object类。我们相对字典中的键排序，而JavaScript中是不能对对象的属性进行排序的。但是不要忘记，JavaScript中一切皆对象，数组也是对象。

function Dictionary() {
    this.datastore = new Array();
}

add方法

function add(key, value) {
    this.datastore[key] = value;
}

find方法

function find(key) {
    return this.datastore[key];
}

删除方法需要使用JavaScript中的一个内置函数：delete。该函数是Object类的一部分，使用对键的引用作为参数。该函数同时删除掉键和与其关联的值。

function remove(key) {
    delete this.datastore[key];
}

显示字典中所有的键-值对

function showAll() {
    for (var key in Object.keys(this.datastore)) {
        console.log(key + ' -> ' + this.datastore[key]);
    }
}

调用Object类的keys方法可以返回传入参数中存储的所有键。

Dictionary类的辅助方法

count方法

function count() {
    var n = 0;
    for (var key in Object.keys(this.datastore)) {
        ++n;
    }
    return n;
}

当键的类型为字符串时，length属性就不管用了。请看例子：

var nums1 = new Array();
nums1[0] = 1;
nums1[1] = 2;
console.log(nums1.length);// 2
var nums2 = new Array();
nums2['a'] = 1;
nums2['b'] = 2;
console.log(nums2.length);// 0

clear方法

function clear() {
    for (var key in Object.keys(this.datastore)) {
        delete this.datastore[key];
    }
}

为Dictionary类添加排序功能

我们无需太关心数据在字典中的实际存储顺序，然而，很多人都希望看到一个有序的字典。
重新定义showAll方法

function showAll() {
    for(var key in Object.keys(this.datastore).sort()) {
        console.log(key + " -> " + this.datastore[key]);
    }
}

散列

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

散列概览

我们的散列表是基于数组进行设计的。数组的长度是预先设定的，如有需要，可以随时增加。所有元素根据和该元素对应的键，保存在数组的特定位置。使用散列表存储数据时，通过一个散列函数将键映射为一个数字，这个数字的范围是0到散列表的长度。

理想情况下，散列函数会将每个键值映射为一个唯一的数组索引。然而，键的数量是无限的，数组的长度是有限的，一个更现实的目标是让散列函数尽量将键均匀地映射到数组中。

将两个键映射成同一值，这种现象称为碰撞。我们稍后会讨论如何解决。

要确定的最后一个问题是：散列表中的数组究竟应该有多大？对数组大小常见的限制是：数组长度应该是一个质数。下图阐释了散列的概念

HashTable类

构造函数定义如下：

function HashTable() {
    this.table = new Array(137);
    this.simpleHash = simpleHash;
    this.showDistro = showDistro;
    this.put = put;
}

选择一个散列函数

散列函数的选择依赖于键值的数据类型。如果键是整型，最简单的散列函数就是以数组的长度对键取余。在一些情况下，比如数组的长度是10，而键值都是10的倍数，就不推荐使用这种方式了。这也是数组的长度为什么要是质数的原因之一，就像我们在上个构造函数中，设定数组的长度为137一样。如果键是随机的整数，则散列函数应该更均匀地分布这些键。这种散列方式称为除留余数法.

选择针对字符串类型的散列函数就比较难了，乍一看将字符串中每个字符的ASCII码值相加似乎是一个不错的散列函数。这样散列值就是ASCII码值的和除以数组长度的余数。

function simpleHash(data) {
    var total = 0;
    for (var i = 0; i < data.length; ++i) {
        total += data.charCodeAt(i);
    }
    return total % this.table.length;
}

put()

function put(data) {
    var pos = this.simpleHash(data);
    this.table[pos] = data;
}

showDistro()

function showDistro() {
    for (var i = 0; i < this.table.length; ++i) {
        if (this.table[i] != undefined) {
            console.log(i + ": " + this.table[i]);
        }
    }
}

你会发现，数据并不是均匀分布的，人名向数组的两端集中。还有一个更严重的问题，由于散列值发生了碰撞，初始数组中的人名并没有全部显示。

一个更好的散列函数

首先要确保散列表中用来存储数据的数组其大小是一个质数。我们取了不会让上例发生碰撞的最小质数137。
接下来要有一个计算散列值的更好方法。霍纳算法很好地解决了这个问题。在此算法中，新的散列函数仍然先计算字符串中各字符的ASCII码值，不过求和时每次都要乘以一个质数。

function betterHash(string, arr) {
    const H = 37;
    var tatal = 0;
    for (var i = 0; i < string.length; ++i) {
        total += H * total + string.charCodeAt(i);
    }
    total = total % arr.length;
    return parseInt(total);
}

对散列表排序、从散列表中取值

修改put方法，使得该方法同时接受建和数据作为参数。

function put(key, data) {
    var pos = this.betterHash(key);
    this.table[pos] = data;
}

get方法

function get(key) {
    return this.table[this.betterHash(key)];
}

碰撞处理-开链法

开链法是指实现散列表的底层数组中，每个数组元素又是一个新的数据结构，比如另一个数组，这样就能存储多个键了。使用这种技术，即使两个键散列后的值相同，依然被保存在同样的位置，只不过它们在第二个数组中的位置不一样罢了。

实现开链法的方法是：在创建存储散列过的键值的数组时，通过调用一个函数创建一个新的空数组，然后将该数组赋给散列表里的每个数组元素。这样就创建了一个二维数组，我们也称这个数组为链。

function buildChains() {
    for (var i = 0; i < this.table.length; ++i) {
        this.table[i] = new Array();
    }
}

将上述代码和函数声明加入HashTable类。使用前先调用

var hTable = new HashTable();
hTable.buildChains();
...

showDistro修改

function showDistro() {
    for (var i = 0; i < this.table.length; ++i) {
        if (this.table[i][0] != undefined) {
            console.log(i + ": " + this.table[i]);
        }
    }
}

put方法修改

function put(key, data) {
    var pos = this.betterHash(key);
    var index = 0;
    if (this.table[pos][index] == undefined) {
        this.table[pos][index+1] = data;
    }
    ++index;
    else {
        while (this.table[pos][index] != undefined) {
            ++index;
        }
        this.table[pos][index+1] = data;
    }
}

前面的例子只保存数据，新的put方法则不同，它即保存数据，也保存键值。该方法使用链中两个连续的单元格，第一个用来保存键值，第二个用来保存数据。
get方法修改

function get(key) {
    var index = 0;
    var hash = this.betterHash(key);
    if (this.table[hash][index] = key) {
        return this.table[hash][index+1];
    }
    index += 2;
    else {
        while (this.table[hash][index] != key) {
            index += 2;
        }
        return this.table[hash][index+1];
    }
    return undefined;
}

线性探测法

线性探测法隶属于一种更一般化的散列技术：开放寻址散列。当发生碰撞时，线性探测法检查散列表中的下一个位置是否为空。如果为空，就将数据存入该位置；如果不为空，则继续检查下一个位置，直到找到一个空的位置为止。该技术基于一个事实：每个散列表都会有很多空的单元格，可以使用它们来存储数据。如果数组的大小是待存储数据的两倍及两倍以上时，那么使用线性探测法比较好。
为了实现一个真实的数据存取系统，需要为HashTable类增加一个新的数组，用来存储数据。数组table和values并行工作，当将一个键值保存到数组table中时，将数据存入数组values中相应的位置上。
在构造函数中加入：

this.values = [];

在put方法中使用线性探测技术

function put(key, data) {
    var pos = this.betterHash(key);
    if (this.table[pos] == undefined) {
        this.table[pos] = key;
        this.values[pos] = data;
    }
    else {
        while (this.table[pos] != undefined) {
            pos++;
        }
        this.table[pos] = key;
        this.values[pos] = data;
    }
}

get方法

function get(key) {
    var hash = -1;
    hash = this.betterHash(key);
    if (hash > -1) {
        for (var i = hash; this.table[hash] != undefined; i ++) {
            if (this.table[hash] == key) {
                return this.values[hash];
            }
        }
    }
    return undefined;
}

集合

集合(set)是一种包含不同元素的数据结构。集合中的元素称为成员。集合的两个最重要的特性是：首先，集合中的成员是无序的；其次，集合中不允许相同成员存在。

集合的定义、操作和属性

集合是由一组无序但彼此之间又有一定相关性的成员构成的，每个成员在集合中只能出行一次。

集合的定义

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

对集合的操作

1. 并集
   将两个集合中的成员进行合并，得到一个新集合

2. 交集
   两个集合中共同存在的成员组成一个新的集合

3. 补集
   属于一个集合而不属于另一个集合的成员组成的集合

Set类的实现

构造函数

function Set() {
    this.dataStore = [];
    this.add = add;
    this.remove = remove;
    this.size = size;
    this.union = union;
    this.intersect = intersect;
    this.subset = subset;
    this.difference = difference;
    this.show = show;
}

add方法

function add(data) {
    if (this.dataStore.indexOf(data) < 0) {
        this.dataStore.push(data);
        return true;
    } else {
        return false;
    }
}

remove方法

function remove(data) {
    var pos = this.dataStore.indexOf(data);
    if (pos > -1) {
        this.dataStore.splice(pos, 1);
        return true;
    } else {
        return false;
    }
}

show方法

function show() {
    return this.dataStore;
}

更多集合操作

contains方法

function contains(data) {
    if (this.dataStore.indexOf(data) > -1) {
        return true;
    } else {
        return false;
    }
}

union方法

function union(set) {
    var tempSet = new Set();
    for (var i = 0; i < this.dataStore.length; ++i) {
        tempSet.add(this.dataStore[i]);
    }
    for (var i = 0; i < set.dataStore.length; ++i) {
        if (!tempSet.contains(set.dataStore[i])) {
            tempSet.dataStore.push(set.dataStore[i]);
        }
    }
    return tempSet;
}

intersect方法求两个集合的交集。

function intersect(set) {
    var tempSet = new Set();
    for (var i = 0; i < this.dataStore.length; ++i) {
        if (set.contains(this.dataStore[i])) {
            tempSet.add(this.dataStore[i]);
        }
    }
    return tempSet;
}

subset(子集)

function subset(set) {
    if (this.size() > set.size()) {
        return false;
    } else {
        for (var member in this.dataStore) {
            if (!set.contains(member)) {
                return false;
            }
        }
    }
    return true;
}

size方法定义如下：

function size() {
    return this.dataStore.length;
}

difference方法返回的是一个新集合，该集合包含那些属于第一个集合但不属于第二个集合的成员。

function difference(set) {
    var tempSet = new Set();
    for (var i = 0; i < this.dataStore.length; ++i) {
        if (!set.contains(this.dataStore[i])) {
            tempSet.add(this.dataStore[i]);
        }
    }
    return tempSet;
}

二叉树和二叉查找树

树是一种非线性的数据结构，以分层的方式存储数据。树被用来存储具有层级关系的数据，比如文件系统中的文件；树还被用来存储有序列表。本章研究一种特殊的树：二叉树。在二叉树上进行查找非常快（在链表上查找则不是），为二叉树添加或删除元素也非常快（对数组执行添加或删除操作则不是）。

树的定义

树由一组以边连接的节点组成。公司的组织结构图就是一个例子

每个方框都是一个节点，连接方框的线叫做边。节点代表了该组织中的各个职位，边描述了各职位间的关系。

下图展示了更多关于树的术语，一棵树最上面的节点称为根节点，如果一个节点下面连接多个节点，那么该节点称为父节点，它下面的节点称为子节点。没有任何子节点的节点称为叶子节点。

二叉树是一种特殊的树，它的子节点个数不超过两个。

沿着一组特定的边，可以从一个节点走到另外一个与它不直接相连的节点。从一个节点到另一个节点的这一组边称为路径，在图中用虚线表示。以某种特定顺序访问树中所有的节点称为树的遍历。

树可以分为几个层次，根节点是第0层，它的子节点是第1层，子节点的子节点是第2层，以此类推。树中任何一层的节点可以都看作是子树的根，该子树包含根节点的子节点，子节点的子节点等。我们定义树的层数就是树的深度。

最后，每个节点都有一个与之相关的值，该值有时被称作键。

二叉树和二叉查找树

二叉树每个节点的子节点不允许超过两个。通过将子节点的个数限定为2，可以写出高效的程序在树中插入、查找和删除数据。

一个父节点的两个子节点分别称为左节点和右节点。在一些二叉树的实现中，左节点包含一组特定的值，右节点包含另一组特定的值。

当考虑某种特殊的二叉树，比如二叉查找树时，确定子节点非常重要。二叉查找树是一种特殊的二叉树，相对较小的值保存在左节点中，较大的值保存在右节点中。这一个特性使得查找的效率很高，对于数值型和非数值型的数据，比如单词和字符串，都是如此。

实现二叉查找树

Node类

function Node(data) {
    this.data = data;
    this.left = left;
    this.right = right;
    this.show = show;
}

function show() {
    return this.data;
}

现在可以创建一个类，用来表示二叉查找树（BST）。我们让类只包含一个数据成员：一个表示二叉查找树根节点的Node对象。该类的构造函数将根节点初始化为null，以此创建一个空节点。

BST先要有一个insert方法，用来向树中加入新节点。这个方法有点复杂，需要着重讲解。首先要创建一个Node对象，将数据传入该对象保存。

其次检查BST是否有根节点，如果没有，那么这是棵新树，该节点就是根节点，这个方法到此也就完成了；否则，进入下一步。

如果待插入节点不是根节点，那么就需要准备遍历BST，找到插入的适当位置。该过程类似于遍历链表。用一个变量存储当前节点，一层层地遍历BST.

进入BST以后，下一步就要决定将节点放在哪个地方。找到正确的插入点时，会跳出循环。查找正确插入点的算法如下：

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

   function Node(data, left, right) {
       this.data = data;
       this.left = left;
       this.right = right;
       this.show = show;
   }
   function show() {
       return this.data;
   }
   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上的所有节点。先序遍历先访问根节点，然后以同样方式访问左子树和右子树。后序遍历先访问叶子节点，从左子树到右子树，再到根节点。
中序遍历

function inOrder(node) {
    if (!(node == null)) {
        inOrder(node.left);
        console.log(node.show() + " ");
        inOrder(node.right);
    }
}

中序遍历按照节点上的键值，以升序访问BST上的所有节点。
10 22 30 56 77 81 92

先序遍历

function preOrder(node) {
    if (!(node == null)) {
        console.log(node.show() + " ");
        preOrder(node.left);
        preOrder(node.right);
    }
}

先序遍历先访问根节点，然后以同样方式访问左子树和右子树。
50 10 5 15 70 60 80

后序遍历

function postOrder(node) {
    if (!(node == null)) {
        postOrder(node.left);
        postOrder(node.right);
        console.log(node.show() + " ");
    }
}

后序遍历先访问叶子节点，从左子树到右子树，再到根节点。
3 22 16 37 99 45 23

查找最小值和最大值

查找最小值

function getMin() {
    var current = this.root;
    while (!(current.left == null)) {
        current = current.left;
    }
    return current.data;
}

查找最大值

function getMax() {
    var current = this.root;
    while (!(current.right == null)) {
        current = current.right;
    }
    return current.data;
}

查找给定值

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

如果找到给定值，该方法返回保存该值得节点；如果没找到，该方法返回null.

从二叉查找树上删除节点(??没怎么看懂)

我们使用递归操作，同时定义两方法：remove()和removeNode()
从BST中删除节点的第一步是判断当前节点是否包含待删除的数据，如果包含，则删除该节点；如果不包含，则比较当前节点上的数据和待删除的数据。如果待删除数据小于当前节点上的数据，则移至当前节点的左子节点继续比较；如果删除数据大于当前节点上的数据，则移至当前节点的右子节点继续比较。

如果待删除节点是叶子节点（没有子节点的节点），那么只需要将从父节点指向它的链接指向null.

如果待删除节点只包含一个子节点，那么原本指向它的节点就得做些调整，使其指向它的子节点。

最后，如果待删除节点包含两个子节点，正确的做法有两种：要么查找待删除节点左子树上的最大值，要么查找其右子树上的最小值。这里我们选择后一种方式。

我们需要一个查找子树上最小值的方法，后面会用它找到的最小值创建一个临时节点。将临时节点上的值复制到待删除节点，然后再删除临时节点。

整个删除过程由两个方法完成。remove方法只是简单地接收删除数据，调用removeNode删除它，后者才是完成主要工作的方法：

function remove(data) {
    root = removeNode(this.root, data);
}
function removeNode(node, data) {
    if (node == null) {
        return null;
    }
    if (data == node.data) {
        // 没有子节点的节点
        if (node.left == null && node.right == null) {
            return null;
        }
        // 没有左子节点的节点
        if (node.left == null) {
            return node.right;
        }
        // 没有右子节点的节点
        if (node.right == null) {
            return node.left;
        }
        // 有两个子节点的节点
        var tempNode = getSmallest(node.right);
        node.data = tempNode.data;
        node.right = removeNode(node.right,   tempNode.data);
        return node;
    } else if (data < node.data) {
        node.left = removeNode(node.left, data);
        return node;
    } else {
        node.right = removeNode(node.right, data);
        return node;
    }
}

计数

我们来修改Node对象，为其增加一个记录成绩出现频次的成员，同时我们还需要一个方法，当在BST中发现某成绩时，需要将出现的次数加1，并且更新该节点。
先修改Node对象的定义

function Node(data, left, right) {
    this.data = data;
    this.count = 1;
    this.left = left;
    this.right = right;
    this.show = show;
}

增加一个新方法update

function update(data) {
    var grade = this.find(data);
    grade.count ++;
    return grade;
}

图和图算法

本章将讨论用图给网络建模。

图的定义

图由边的集合及顶点的集合组成。边有顶点对（v1,v2）定义，v1和v2分别是图中的两个顶点。顶点也有权重，也称成本。如果一个图的顶点对是有序的，则可以称之为有向图。在对有向图中的顶点对排序后，便可以在两个顶点之间绘制一个箭头。有向图表明了顶点的流向。下图展示了一个有向图。

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

图中的一系列顶点构成路径，路径中所有的顶点都由边连接。路径的长度用路径中第一个顶点到最后一个顶点之间边的数量表示。由指向自身的顶点组成的路径称为环，环的长度为0。

圈是至少有一条边的路径，且路径的第一个顶点和最后一个顶点相同。无论是有向图还是无向图，只要是没有重复边或重复顶点的圈，就是一个简单圈。除了第一个和最后一个顶点以外，路径的其他顶点有重复的圈称为平凡圈。

如果两个顶点之间有路径，那么这两个顶点就是强连通的，反之亦然。如果有向图的所有的顶点都是强连通的，那么这个有向图也是强连通的。

表示顶点

创建图类的第一步就是要创建一个Vertex类来保存顶点和边。这个类有两个数据成员：一个用于标识顶点，另一个是表明这个顶点是否被访问过的布尔值。

function Vertex(label) {
    this.label = label;
}

我们将所有顶点保存在数组中，在图类里，可以通过它们在数组中的位置引用它们。

表示边

图的实际信息都保存在边上面，因为它们描述了图的结构。
我们将表示图的边的方法称为邻接表或者邻接表数组。这种方法将边存储为由顶点的相邻顶点列表构成的数组，并以此顶点作为索引。使用这种方案，当我们在程序中引用一个顶点时，可以高效地访问与这个顶点相连的所有顶点的列表。比如，如果顶点2与顶点0、1、3、4相连，并且它存储在数组中索引为2的位置，那么，访问这个元素，我们可以访问到索引为2的位置处由顶点0、1、3、4组成的数组。本章将选用这种表示方法。

另一种表示图边的方法被称为邻接矩阵。它是一个二维数组，其中的元素表示两个顶点之间是否有一条边。

构建图

Graph类的定义

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

这个类会记录一个图表示了多少条边，并使用一个长度与图的顶点数相同的数组来记录顶点的数量。通过for循环为数组中的每个元素添加一个子数组来存储所有的相邻顶点，并将所有元素初始化为空字符串。
addEdge

function addEdge(v, w) {
    this.adj[v].push(w);
    this.adj[w].push(v);
    this.edges ++;
}

showGraph

function showGraph() {
    for (var i = 0; i < this.vertices; ++i) {
        console.log(i + "->");
        for (var j = 0; j < this.vertices; ++j) {
            if (this.adj[i][j] != undefined) {
                console.log(this.adj[i][j] + ' ');
            }
        }
    }
}

测试程序

g = new Graph(5);
g.addEdge(0,1);
g.addEdge(0,2);
g.addEdge(1,3);
g.addEdge(2,4);
g.showGraph();

搜索图

确定从一个指定的顶点可以到达其他哪些顶点，这是经常对图执行的操作。图上的这些操作是用搜索算法执行的。在图上可以执行两种基础搜索：深度优先搜索和广度优先搜索。

深度优先搜索

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

深度优先搜索算法比较简单：访问一个没有访问过的顶点，将它标记为已访问，再递归地去访问在初始顶点的邻接表中其他没有访问过的顶点。

要让该算法运行，需要为Graph类添加一个数组，用来存储已访问过的顶点，将它所有元素的值全部初始化为false.

this.marked = [];
for (var i = 0; i < this.vertices; ++i) {
    this.marked[i] = false;
}

深度优先搜索函数

function dfs(v) {
    this.marked[v] = true;
    if (this.adj[v] != undefined) {
        console.log("visited vertex: " + v);
    }
    for (var w in this.adj[v]) {
        if (!this.marked[w]) {
            this.dfs(w);
        }
    }
}

测试

g = new Graph(5);
g.addEdge(0,1);
g.addEdge(0,2);
g.addEdge(1,3);
g.addEdge(2,4);
g.showGraph();
g.dfs(0);

广度优先搜索

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

广度优先搜索算法使用了抽象的队列而不是数组来对已访问过的顶点进行排序。工作原理如下

1. 查找与当前顶点相邻的未访问顶点，将其添加到已访问顶点列表及队列中
2. 从图中取出下一个顶点v，添加到已访问的顶点列表
3. 将所有与v相邻的未访问顶点添加到队列

   function bfs(s) {
       var queue = [];
       this.marked[s] = true;
       queue.push(s); // 添加到队尾
       while (queue.length > 0) {
           var v = queue.shift();
           if (v = undefined) {
               console.log("visited vertex:" + v);
           }
           for (var w in this.adj[v]) {
               if (!this.marked[w]) {
                   this.edgeTo[w] = v;
                   this.marked[w] = true;
                   queue.push(w);
               }
           }
       }
   }

查找最短路径 ???暂略

在执行广度优先搜索时，会自动查找从一个顶点到另一个相连顶点的最短路径。例如，要查找从顶点A到顶点D的最短路径，我们首先会查找从A到D是否有任何一条单边路径，接着查找两条边的路径，以此类推。因此我们可以轻松地修改广度优先搜索算法，找出最短路径。

拓扑排序 ???暂略

排序算法

本文将介绍数据排序的基本算法和高级算法。这些算法都只依赖数组来存储数据。

数组测试平台

首先我们构造一个数组测试平台类

function CArray(numElements) {
    this.dataStore = [];
    this.numElements = numElements;
    this.toString = toString;
    this.clear = clear;
    this.setData = setData;
    this.swap = swap;
}
function setData() {
    for (var i = 0; i < this.numElements; ++i) {
    this.dataStore[i] = Math.floor(Math.random() * (this.numElements + 1));
    }
}
function clear() {
    for (var i = 0; i < this.numElements; ++i) {
    this.dataStore[i] = 0;
    }
}
function toString() {
    var restr = "";
    for (var i = 0; i < this.numElements; ++i) {
    restr += this.dataStore[i] + " ";
    if (i > 0 && i % 10 == 0) {
        restr += "\n";
    }
    }
    return restr;
}
function swap(arr, index1, index2) {
    var temp = arr[index1];
    arr[index1] = arr[index2];
    arr[index2] = temp;
}

使用测试平台类

var numElements = 100;
var myNums = new CArray(numElements);
myNums.setData();
console.log(myNums.toString());

基本排序算法

这些算法非常逼真地模拟了人类在现实生活中对数据的排序。

冒泡排序

它是最慢的排序算法之一，但也是一种最容易实现的排序算法。
之所以叫冒泡排序是因为使用这种排序算法排序时，数据值会像气泡一样从数组的一端漂浮到另一端。假设正在将一组数字按照升序排列，较大的值会浮动到数组的右侧，而较小的值则会浮动到数组的左侧。之所以会产生这种现象是因为算法会多次在数组中移动，比较相邻的数据，当左侧值大于右侧值时将它们进行互换。

冒泡排序的代码

function bubbleSort() {
    var numElements = this.dataStore.length;
    for (var outer = numElements; outer >= 2; --outer) {
        for (var inner = 0; inner < outer - 1; ++inner) {
            if (this.dataStore[inner] > this.dataStore[inner + 1]) {
                this.swap(this.dataStore, inner, inner + 1);
            }
        }
    }
}

排序过程（手动输入的测试数据）

外层循环限定了未排序的范围(从numElements到2),内层循环从左侧的数据开始逐步比较交换，使得未排序范围中最大的数移动到了最右侧，外层排序范围不断缩小，直到还剩两个未排序元素时再比较交换便完成了排序

选择排序

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

function selectionSort() {
    var min;
    for (var outer = 0; outer <= this.dataStore.length - 2; ++outer) {
        min = outer;
        for (var inner = outer + 1; inner <= this.dataStore.length - 1; ++inner) {
            if (this.dataStore[inner] < this.dataStore[min]) {
                min = inner;
            }
        }
        swap(this.dataStore, outer, min);
    }
}

排序过程

插入排序

插入排序有两个循环。外循环将数组元素挨个移动，而内循环则对外循环中选中的元素进行比较。如果外循环中选中的元素比内循环中选中的元素小，那么数组元素会向右移动，为内循环中的这个元素腾出位置。

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

基本排序算法的计时比较

10000个随机数测试

bubbleSort();// 100ms左右
selectionSort();// 50ms左右
insertionSort();// 27ms左右

选择排序和插入排序要比冒泡排序快，插入排序是这三种算法中最快的。

高级排序算法-希尔排序

希尔排序在插入排序的基础上做了很大的改善。它会首先比较距离较远的元素，而非相邻的元素。这样可以使离正确位置很远的元素更快地回到合适的位置。当开始用这个算法遍历数据集时，所有元素之间的距离会不断减小，直到处理到数据集的末尾，这时算法比较的就是相邻元素了。希尔排序的工作原理是，通过定义一个间隔序列来表示排序过程中进行比较的元素之间有多远的间隔。我们可以动态定义间隔序列，不过大部分场景算法要用到的间隔序列可以提前定义好。Marchin Ciura在发表的一篇论文中定义的间隔序列为：701,301,132,57,23,10,4,1。这里我们通过一个小的数据集合来看看这个算法是怎么运行的。

function shellsort() {
    var temp;
    for (var g = 0; g < this.gaps.length; ++g) {
    for (var i = this.gaps[g]; i < this.dataStore.length; ++i) {
        temp = this.dataStore[i];
        for (var j = i; j >= this.gaps[g] && this.dataStore[j-this.gaps[g]] > temp; j -= this.gaps[g]) {
        this.dataStore[j] = this.dataStore[j - this.gaps[g]];
        }
        this.dataStore[j] = temp;
    }
    }
}

我们需要在CArray类中增加对间隔序列的定义：

this.gaps = [5,3,1];

计算动态间隔序列

Sedgewick的算法通过下面的代码片段来决定初始间隔值：

var N = this.dataStore.length;
var h = 1;
while (h < N/3) {
    h = 3 * h + 1;
}

间隔值确定好后，这个函数就可以像之前定义的shellsort()函数一样运行了，唯一的区别是，回到外循环之前的最后一条语句会计算一个新的间隔值：

h = (h-1)/3;

动态计算间隔序列的希尔排序

function shellsort1() {
    var N = this.dataStore.length;
    var h = 1;
    while (h < N/3) {
        h = 3 * h + 1;
    }
    while (h >= 1) {
        for (var i = h; i < N; i ++) {
            for (var j = i; j >= h && this.dataStore[j] < this.dataStore[j-h]; j -= h) {
                this.swap(this.dataStore, j, j - h);
            }
        }
        h = (h-1)/3;
    }
}

对于10000个随机数的排序测试：

myNums.shellsort(); // 20ms左右
myNums.shellsort1(); // 8ms左右

归并排序

归并排序把一系列排好序的子序列合并成一个大的完整有序序列。我们需要两个排好序的子数组，然后通过比较数据大小，从最小的数据开始插入，最后合并得到第三个数组。然而，在实际情况中，归并排序还有一些问题，我们需要更大的空间来合并存储两个子数组。

2.自底向上的归并排序

通常来讲，归并排序会使用递归的算法来实现。然而，在JavaScript中这种方式不太可行，因为递归的深度太深了。所以，我们使用一种非递归的方式来实现这个算法，这种策略称为自底向上的归并排序。
这个算法首先将数据集分解为一组只有一个元素的数组。然后通过创建一组左右子数组将它们慢慢合并起来，每次合并都保存一部分排好序的数据，直到最后剩下的这个数组所有的数据都已完美排序。

算法代码

function mergeSort() {
    var arr = this.dataStore;
    if (arr.length < 2) {
    return;
    }
    var step = 1;
    var left, right;
    while (step < arr.length) {
    left = 0;
    right = step;
    while (right + step <= arr.length) {
        this.mergeArrays(arr, left, left+step, right, right+step);
        left = right + step;
        right = left + step;
    }
    if (right < arr.length) {
        this.mergeArrays(arr, left, left+step, right, arr.length);
    }
    step *= 2;
    }
}

function mergeArrays(arr, startLeft, stopLeft, startRight, stopRight) {
    var rightArr = new Array(stopRight - startRight + 1);
    var leftArr = new Array(stopLeft - startLeft + 1);
    k = startRight;
    for (var i = 0; i < (rightArr.length-1); ++i) {
    rightArr[i] = arr[k];
    ++k;
    }
    k = startLeft;
    for (var i = 0; i < (leftArr.length-1); ++i) {
    leftArr[i] = arr[k];
    ++k;
    }
    rightArr[rightArr.length - 1] = Infinity;
    leftArr[leftArr.length - 1] = Infinity;
    var m = 0;
    var n = 0;
    for (var k = startLeft; k < stopRight; ++k) {
    if (leftArr[m] <= rightArr[n]) {
        arr[k] = leftArr[m];
        m++;
    } else {
        arr[k] = rightArr[n];
        n++;
    }
    }
}

快速排序

快速排序是处理大数据集最快的排序算法之一。它是一种分而治之的算法，通过递归的方法将数据依次分解为包含较小元素和较大元素的不同子序列。该算法不断重复这个步骤直到所有数据都是有序的。
这个算法首先要在列表中选择一个元素作为基准值(pivot)。数据排序围绕基准值进行，将列表中小于基准值的元素移到数组的底部，将大于基准值的元素移到数组的顶部。

算法伪代码

1. 选择一个基准元素，将列表分隔成两个子序列
2. 对列表重新排序，将所有小于基准值的元素放在基准值的前面，所有大于基准值得元素放在基准值的后面
3. 分别对较小元素的子序列和较大元素的子序列重复步骤1和2
   程序如下：

   function qSort(list) {
       var 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 this.qSort(lesser).concat(pivot, this.qSort(greater));
   }

在qSort函数返回前输出排序过程

console.log(lesser.concat(pivot, greater).toString());

10000个随机数排序测试

qSort(); // 17ms左右

快速排序算法非常适用于大型数据集合；在处理小数据集时性能反而会下降。
附测试平台代码

<!DOCTYPE html>
<html lang="en">
<head>
</head>
<body>
  <script>
    function CArray(numElements) {
      // this.dataStore = [72, 54, 58, 30, 31, 78, 2, 77, 82, 72];
      this.dataStore = [];
      // this.dataStore = [44, 75, 23, 43, 55, 12, 64, 77 ,33];
      this.numElements = numElements;
      this.toString = toString;
      this.clear = clear;
      this.setData = setData;
      this.swap = swap;
      this.bubbleSort = bubbleSort;
      this.selectionSort = selectionSort;
      this.insertionSort = insertionSort;
      this.shellsort = shellsort;
      this.shellsort1 = shellsort1;
      this.mergeSort = mergeSort;
      this.mergeArrays = mergeArrays;
      this.qSort = qSort;
      this.gaps = [5, 3, 1];
    }
    function setData() {
      for (var i = 0; i < this.numElements; ++i) {
        this.dataStore[i] = Math.floor(Math.random() * (this.numElements + 1));
      }
    }
    function clear() {
      for (var i = 0; i < this.numElements; ++i) {
        this.dataStore[i] = 0;
      }
    }
    function toString() {
      var restr = "";
      for (var i = 0; i < this.numElements; ++i) {
        restr += this.dataStore[i] + " ";
        if (i > 0 && i % 10 == 0) {
          restr += "\n";
        }
      }
      return restr;
    }
    function swap(arr, index1, index2) {
      var temp = arr[index1];
      arr[index1] = arr[index2];
      arr[index2] = temp;
    }
    function selectionSort() {
        var min;
        for (var outer = 0; outer <= this.dataStore.length - 2; ++outer) {
            min = outer;
            for (var inner = outer + 1; inner <= this.dataStore.length - 1; ++inner) {
                if (this.dataStore[inner] < this.dataStore[min]) {
                    min = inner;
                }
            }
            swap(this.dataStore, outer, min);
        }
    }
    function bubbleSort() {
        var numElements = this.dataStore.length;
        for (var outer = numElements; outer >= 2; --outer) {
            for (var inner = 0; inner < outer - 1; ++inner) {
                if (this.dataStore[inner] > this.dataStore[inner + 1]) {
                    this.swap(this.dataStore, inner, inner + 1);
                }
            }
        }
    }
    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;
      }
    }
    function shellsort() {
      var temp;
      for (var g = 0; g < this.gaps.length; ++g) {
        for (var i = this.gaps[g]; i < this.dataStore.length; ++i) {
          temp = this.dataStore[i];
          for (var j = i; j >= this.gaps[g] && this.dataStore[j-this.gaps[g]] > temp; j -= this.gaps[g]) {
            this.dataStore[j] = this.dataStore[j - this.gaps[g]];
          }
          this.dataStore[j] = temp;
        }
      }
    }
    function shellsort1() {
      var N = this.dataStore.length;
      var h = 1;
      while (h < N/3) {
          h = 3 * h + 1;
      }
      while (h >= 1) {
          for (var i = h; i < N; i ++) {
              for (var j = i; j >= h && this.dataStore[j] < this.dataStore[j-h]; j -= h) {
                  this.swap(this.dataStore, j, j - h);
              }
          }
          h = (h-1)/3;
      }
    }
    function mergeSort() {
      var arr = this.dataStore;
      if (arr.length < 2) {
        return;
      }
      var step = 1;
      var left, right;
      while (step < arr.length) {
        left = 0;
        right = step;
        while (right + step <= arr.length) {
          this.mergeArrays(arr, left, left+step, right, right+step);
          left = right + step;
          right = left + step;
        }
        if (right < arr.length) {
          this.mergeArrays(arr, left, left+step, right, arr.length);
        }
        step *= 2;
      }
    }
    function mergeArrays(arr, startLeft, stopLeft, startRight, stopRight) {
      var rightArr = new Array(stopRight - startRight + 1);
      var leftArr = new Array(stopLeft - startLeft + 1);
      k = startRight;
      for (var i = 0; i < (rightArr.length-1); ++i) {
        rightArr[i] = arr[k];
        ++k;
      }
      k = startLeft;
      for (var i = 0; i < (leftArr.length-1); ++i) {
        leftArr[i] = arr[k];
        ++k;
      }
      rightArr[rightArr.length - 1] = Infinity;
      leftArr[leftArr.length - 1] = Infinity;
      var m = 0;
      var n = 0;
      for (var k = startLeft; k < stopRight; ++k) {
        if (leftArr[m] <= rightArr[n]) {
          arr[k] = leftArr[m];
          m++;
        } else {
          arr[k] = rightArr[n];
          n++;
        }
      }
    }
    function qSort(list) {
        var 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 this.qSort(lesser).concat(pivot, this.qSort(greater));
    }
    var numElements = 200000;
    var myNums = new CArray(numElements);
    myNums.setData();
    // console.log(myNums.toString());
    var startTime = new Date().getTime();
    // myNums.insertionSort();// 27ms左右
    // myNums.bubbleSort();// 100ms左右
    // myNums.selectionSort();// 50ms左右
    // myNums.shellsort(); // 20ms左右
    // myNums.shellsort1(); // 8ms左右
    // myNums.mergeSort(); // 9ms左右
    myNums.dataStore = myNums.qSort(myNums.dataStore); // 17ms左右
    var endTime = new Date().getTime();
    console.log('耗时: ' + (endTime - startTime) + '毫秒');
    // console.log(myNums.toString());
    
  </script>
</body>
</html>

检索算法

本章只介绍数据检索的一个方面：如何在列表中查找特定的值。有两种方式：顺序查找和二分查找。顺序查找适用于元素随机排列的列表；二分查找适用于元素已排序的列表。二分查找效率更高，但是你必须在进行查找之前花费额外的时间将列表中的元素排序。

顺序查找

对于查找数据来说，最简单的方法就是从列表的第一个元素开始对列表元素逐个进行判断。这种方法称为顺序查找，有时也被称为线性查找。它属于暴力查找技巧的一种，在执行查找时可能会访问到数据结构里的所有元素。

function seqSearch(arr, data) {
    for (var i = 0; i < arr.length; ++i) {
        if (arr[i] == data) {
            return i;
        }
    }
    return -1;
}

查找最小值和最大值

首先看看如何在数组中查找最小值，算法如下

1. 将数组第一个元素赋值给一个变量，把这个变量作为最小值。
2. 开始遍历数组，从第二个元素开始依次同当前最小值进行比较
3. 如果当前元素数值小于当前最小值，则将当前元素设为新的最小值
4. 移动到下一个元素，并且重复步骤3
5. 当程序结束时，这个变量中存储的就是最小值

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

使用自组织数据

对于未排序的数据集来说，当被查找的数据位于数据集的起始位置时，查找是最快的。通过将成功找到的元素置于数据集的起始位置，可以保证在以后的操作中该元素能被更快地查找到。这就是自组织数据：数据的位置并非由程序员在程序执行之前就组织好，而是在程序运行过程中由程序自动组织的。

我们可以很轻松地对seqSearch函数进行改动以加入自组织方式。

function seqSearch(arr, data) {
    for (var i = 0; i < arr.length; ++i) {
        if (arr[i] == data) {
            if (i > 0) {
                swap(arr,i,i-1);
            }
            return true;
        }
    }
    return false;
}

function swap(arr, index, index1) {
    temp = arr[index];
    arr[index] = arr[index1];
    arr[index1] = temp;
}

使用这个方法后，查找最频繁的元素最终会移动到数据集的起始位置。
另外一种给seqSearch函数添加自组织数据的方法是：将找到的元素移动到数据集的起始位置，如果这个元素已经很接近起始位置，则不会对它的位置进行交换。我们参照“80-20原则”，仅当数据位于数据集的前20%元素之外时，该数据才需要被重新移动到数据集的起始位置。

function seqSearch(arr, data) {
    for (var i = 0; i < arr.length; ++i) {
        if (arr[i] == data && i > (arr.length * 0.2)) {
            swap(arr,i,0);
            return true;
        } else if (arr[i] == data) {
            return true;
        }
    }
    return false;
}

二分查找算法

这个算法只对有序的数据集有效。算法描述如下

1. 将数组的第一个位置设置为下边界(0).
2. 将数组最后一个元素所在的位置设置为上边界(数组的长度减1).
3. 若下边界等于或小于上边界，则做如下操作
   a.将中点设置为（上边界加上下边界）除以2
   b.如果中点的元素小于查询的值，则将下边界设置为中点元素所在下标加1
   c.如果中点的元素大于查询的值，则将上边界设置为中点元素所在下标减1
   d.否则中点元素即为要查找的数据，可以进行返回。

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

计算重复次数

function count(arr, data) {
    var count = 0;
    var position = binSearch(arr, data);
    if (position > -1) {
        ++count;
        for (var i = position - 1; i > 0; --i) {
            if (arr[i] == data) {
                ++count;
            } else {
                break;
            }
        }
        for (var i = position+1; i < arr.length; ++i) {
            if (arr[i] == data) {
                ++count;
            } else {
                break;
            }
        }
    }
    return count;
}

查找文本数据

很显然顺序查找也适用于查找文本
二分法查找，需要先对文本排序

function insertionsort(arr) {
    var temp, inner;
    for (var outer = 1; outer <= arr.length-1; ++outer) {
        temp = arr[outer];
        inner = outer;
        while (inner > 0 && (arr[inner-1] >= temp)) {
            arr[inner] = arr[inner-1];
            --inner;
        }
        arr[inner] = temp;
    }
}