学习JavaScript数据结构和算法（部分一）

112 阅读 0 评论 74 点赞

我是靠谱客的博主昏睡小猫咪，这篇文章主要介绍学习JavaScript数据结构和算法（部分一），现在分享给大家，希望可以做个参考。

看了 Loiane Groner 著的《学习JavaScript数据结构与算法》一书，自己写篇博客对着敲敲代码：
全文包含十个部分，分别是：数组、栈、队列、链表、集合、字典与散列表、树、图、排序和搜索算法、算法补充知识。

知识点其他部分参考：
学习JavaScript数据结构和算法（部分一）
学习JavaScript数据结构和算法（部分二）
学习JavaScript数据结构和算法（部分三）
学习JavaScript数据结构和算法（部分四）

面向对象编程

JavaScript里的对象就是普通名值对的集合。创建一个普通对象有两种方式。第一种方式是：

复制代码

1
var obj = new Object();

第二种方式是：

复制代码

1
var obj = {};

在面向对象编程（OOP）中，对象是类的实例，一个类定义了对象的特征。我们会创建很多类来表示算法和数据结构。例如我们声明了一个类来表示书：

复制代码

1
2
3
4
5
function Book(title, pages, isbn){
    this.title = title;
    this.pages = pages;
    this.isbn = isbn;
}

下面用代码来实例化这个类：

复制代码

1
var book = new Book('title', 'pag', 'isbn');

然后我们可以访问和修改对象的属性：

复制代码

1
2
3
console.log(book.title);
book.title = 'new title';
console.log(book.title);

类可以包含函数。可以声明和使用函数，如下在原型上定义实例共享函数：

复制代码

1
2
3
4
Book.prototype.printTitle = function(){
    console.log(this.title);
}
book.printTitle();

也可以直接在类的定义里声明函数。

1、数组

1.1 创建和初始化数组:
两种方式：

复制代码

1
2
let array = new Array();
let array = [];

1.2 添加和删除元素: 后进后出（push、pop）、前进前出（unshift、shift）、splice

1.3 常用方法:

方法名	描述
concat	连接两个或更多数组，并返回结果，不影响原数组
slice	传入索引值，将数组里对应索引范围内的元素作为新数组返回，不影响原数组
splice	指定位置/索引，就可以删除相应位置和数量的元素，并以新元素代替，影响原数组
reverse	数组元素反转，影响原数组
toString	将数组整体作为字符串返回，不影响原数组
join	将所有的数组元素以指定字符连接成字符串，不影响原数组
indexOf	返回第一个与给定参数相等的数组元素的索引，没有找到则返回-1
lastIndexOf	返回与给定参数相等的数组元素索引的最大值
sort	按照字符对应的ASCII值对数组排序，支持传入指定排序方法的函数作为参数
map	对数组中的每一项运行给定函数，返回每次函数调用的结果组成的数组
forEach	对数组中的每一项运行给定函数，不影响原数组中的项
filter	对数组中的每一项运行给定函数，返回该函数会返回true的项组成的数组
every	对数组中的每一项运行给定函数，如果该函数中每一项都返回true，则返回true
some	对数组中的每一项运行给定函数，如果该函数中任一项返回true，则返回true
reduce	接收一个函数作为参数，做数组的累加器，或者拼接数组项作为字符串,不改变原数组

复制代码

1
2
3
4
5
6
7
8
9
10
11
//其它函数都比较常用，reduce函数用的少，举例说明一下
function compute(total, currentValue){
    return total + currentValue;
}
let arr = [2, 5, 13];
let res = arr.reduce(compute);
console.log(res);  //20

let strArr = ["s", "r", "f"];
let str = strArr.reduce(compute);
console.log(str);  //"srf"

2、栈

栈是一种遵从后进先出原则的有序集合。新添加的或待删除的元素都保存在栈的末尾，称作栈顶，另一端就叫栈底。

2.1 创建栈:
我们将创建一个类来表示栈，选择数组来保存栈里的元素,然后为栈声明如下方法：
* push(element(s))：添加一个（或几个）新元素到栈顶；
* pop()：移除栈顶的元素，同时返回被移除的元素；
* peek()：返回栈顶的元素，不对栈做任何修改；
* isEmpty()：如果栈里没有任何元素就返回true，否则返回false；
* clear()：移除栈里的所有元素；
* size()：返回栈里的元素个数。
实现代码如下：

复制代码

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
function Stack(){
    let items = [];
    //push方法
    this.push = function(element){
        items.push(element);
    }
    //pop方法
    this.pop = function(){
        return items.pop();
    }
    //peek方法
    this.peek = function(){
        return items[items.length-1];
    }
    //isEmpty方法
    this.isEmpty = function(){
        return items.length == 0;
    }
    //clear方法
    this.clear = function(){
        items=[];
    }
    //size方法
    this.size = function(){
        return items.length;
    }
}
//使用栈
let stack = new Stack();
console.log(stack.isEmpty());    //true
stack.push(1);
stack.push(5);
console.log(stack.size());      //2
console.log(stack.peek());      //5
console.log(stack.pop());       //5
stack.clear();
console.log(stack.isEmpty());   //true

2.2 栈的应用:

复制代码

//1、用于进制换算
function baseConverter(number){
    let stack  = new Stack();
    while(number){
        stack.push(number % 2);
        number = Math.floor(number/2);
    }
    let baseString = "";
    while( !stack.isEmpty() ){
        baseString += stack.pop();
    }
    return baseString;
}
console.log(baseConverter(8));   //1000

//2、用于判断字符串是否是回文字符串
function isPalindrome(word){
    let stack = new Stack();
    for(let i=0,len=word.length; i<len; i++){
        stack.push(word[i]);
    }
    let newword="";
    while(stack.size() !== 0){
        newword += stack.pop();
    }
    if(newword == word){
        return true;
    }else{
        return false;
    }
}
console.log(isPalindrome("abdcse"));    //false
console.log(isPalindrome("abccba"));    //true

//3、使用栈模拟递归过程
//阶乘递归实现
function factorial(n){
    if(n === 0){
        return 1;
    }else{
        return n*factorial(n-1);
    }
}
console.log(factorial(4));      //24
//栈实现递归
function stackFactorial(n){
    let stack  = new Stack();
    while(n){
        stack.push(n--);
    }
    let res = 1;
    while(stack.size() !== 0){
        res *= stack.pop();
    }
    return res;
}
console.log(stackFactorial(4));     //24

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
//1、用于进制换算
function baseConverter(number){
    let stack  = new Stack();
    while(number){
        stack.push(number % 2);
        number = Math.floor(number/2);
    }
    let baseString = "";
    while( !stack.isEmpty() ){
        baseString += stack.pop();
    }
    return baseString;
}
console.log(baseConverter(8));   //1000

//2、用于判断字符串是否是回文字符串
function isPalindrome(word){
    let stack = new Stack();
    for(let i=0,len=word.length; i<len; i++){
        stack.push(word[i]);
    }
    let newword="";
    while(stack.size() !== 0){
        newword += stack.pop();
    }
    if(newword == word){
        return true;
    }else{
        return false;
    }
}
console.log(isPalindrome("abdcse"));    //false
console.log(isPalindrome("abccba"));    //true

//3、使用栈模拟递归过程
//阶乘递归实现
function factorial(n){
    if(n === 0){
        return 1;
    }else{
        return n*factorial(n-1);
    }
}
console.log(factorial(4));      //24
//栈实现递归
function stackFactorial(n){
    let stack  = new Stack();
    while(n){
        stack.push(n--);
    }
    let res = 1;
    while(stack.size() !== 0){
        res *= stack.pop();
    }
    return res;
}
console.log(stackFactorial(4));     //24

3、队列

队列是遵循先进先出原则的一组有序的项，队列在尾部添加新元素，并从顶部移除元素。

3.1 创建队列:
创建一个类来表示队列，使用数组用于储存队列中的元素，然后为栈声明如下方法：（与栈结构非常相似）
* enquene(element(s))：向队列尾部添加一个（或多个）新的项；
* dequene()：移除队列的第一（即排在队列最前面的）项，并返回被移除的元素；
* front()：返回队列中的第一个元素，队列没变动；
* isEmpty()：如果队列中不包含任何元素，返回true，否则返回false；
* size()：返回队列包含的元素个数。
实现代码如下：

复制代码

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
function Quene(){
    let items = [];
    //enquene方法
    this.enquene = function(element){
        items.push(element);
    }
    //dequene方法
    this.dequene = function(){
        return items.shift();
    }
    //front方法
    this.front = function(){
        return items[0];
    }
    //isEmpty方法
    this.isEmpty = function(){
        return items.length == 0;
    }
    //clear方法
    this.clear= function(){
        items = [];
    }
    //size方法
    this.size = function(){
        return items.length;
    }
}
//使用队列
let quene= new Quene();
console.log(quene.isEmpty());    //true
quene.enquene(1);
quene.enquene(5);
console.log(quene.size());      //2
console.log(quene.front());     //1
console.log(quene.dequene());   //1
quene.clear();
console.log(quene.isEmpty());   //true

3.2 队列的改进版:

复制代码

//1、优先队列（额外创建一个特殊元素，他包含了要添加到队列的元素及其优先级）
//元素的添加和移除是基于优先级的,对于优先级相同的元素，依旧遵循先进先出的原则
function PriorityQuene() {
    let items = [];
    function QueneElement(element, priority){
        this.element = element;
        this.priority = priority;
    }
    this.enquene = function(element, priority){
        let queneElement = new QueneElement(element, priority);
        //队列为空时，元素直接放置；不为空时，先比较优先级
        if(this.isEmpty()){
            items.push(queneElement);
        }else{
            let added = false;
            for(let i=0; i<items.length; i++){
                if(queneElement.priority < items[i].priority){
                    items.splice(i, 0, queneElement); //将元素插入下标为i的位置
                    added = true;
                    break;
                }   
            }
            if(!added){
                items.push(queneElement);
            }
        }
    };
    //其他方法
}

//2、循环队列 (击鼓传花游戏)
//孩子们围成一个圈，把花尽快传给旁边的人，某一刻传花停止，花在谁手里，谁就淘汰，知道最后只剩一个孩子,返回这个孩子
function hotPotato(nameList,num){
    let quene = new Quene();
    for(let i=0; i<nameList.length; i++){
        quene.enquene(nameList[i]);
    }
    while(quene.size() > 1){
        for(let j=0; j<num; j++){
            quene.enquene(quene.dequene());
        }
        quene.dequene();
    }
    return quene.dequene();
}
var names = ['John','Jack','Camila','Ingrid','Carl'];
var winner = hotPotato(names, 7);
console.log('胜利者：' + winner);      //胜利者：John

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
43
44
45
46
47
48
//1、优先队列（额外创建一个特殊元素，他包含了要添加到队列的元素及其优先级）
//元素的添加和移除是基于优先级的,对于优先级相同的元素，依旧遵循先进先出的原则
function PriorityQuene() {
    let items = [];
    function QueneElement(element, priority){
        this.element = element;
        this.priority = priority;
    }
    this.enquene = function(element, priority){
        let queneElement = new QueneElement(element, priority);
        //队列为空时，元素直接放置；不为空时，先比较优先级
        if(this.isEmpty()){
            items.push(queneElement);
        }else{
            let added = false;
            for(let i=0; i<items.length; i++){
                if(queneElement.priority < items[i].priority){
                    items.splice(i, 0, queneElement); //将元素插入下标为i的位置
                    added = true;
                    break;
                }   
            }
            if(!added){
                items.push(queneElement);
            }
        }
    };
    //其他方法
}

//2、循环队列 (击鼓传花游戏)
//孩子们围成一个圈，把花尽快传给旁边的人，某一刻传花停止，花在谁手里，谁就淘汰，知道最后只剩一个孩子,返回这个孩子
function hotPotato(nameList,num){
    let quene = new Quene();
    for(let i=0; i<nameList.length; i++){
        quene.enquene(nameList[i]);
    }
    while(quene.size() > 1){
        for(let j=0; j<num; j++){
            quene.enquene(quene.dequene());
        }
        quene.dequene();
    }
    return quene.dequene();
}
var names = ['John','Jack','Camila','Ingrid','Carl'];
var winner = hotPotato(names, 7);
console.log('胜利者：' + winner);      //胜利者：John

4、链表

要存储多个元素，数组可能是最常用的数据结构。数组查询数据方便，但是在数组中插入或移除项的成本很高，因为需要移动元素。

链表是存储有序元素的集合，但不同于数组，链表中的元素在内存中并不是连续放置的。每个元素由一个存储元素本身的节点和一个指向下一个元素的引用（也称为指针或链接）组成。相对于传统的数组，链表的一个好处在于，添加或移除元素的时候不需要移动其他的元素。但是数组可以直接访问任何位置的任何元素，而想要访问链表中间的一个元素，需要从起点（表头）开始迭代列表知道找到所需的元素。

4.1 单向链表
下图展示一个单向链表的结构：

单向链表实现代码：

复制代码

function Node(element){   //Node类表示要加入链表的项
    this.element = element;  //要添加到列表的值
    this.next = null;        //指向下一个节点项的指针
}
function LinkedList(){
    let length = 0;
    let head = null;
    //链表方法
    this.append = append;  //向链表尾部添加元素
    this.insert = insert;  //向链表特定位置插入元素
    this.remove = remove;  //移除元素
    this.removeAt = removeAt ;  //移除特定位置的元素
    this.indexOf = indexOf;  //返回元素在链表中的索引。没有该元素则返回-1。
    this.isEmpty = isEmpty;   //判断链表是否为空
    this.size = size;  //返回链表包含元素个数
    this.toString = toString;   //由于链表项使用了Node类，就需要重写继承自JavaScript对象默认的toString方法，让其只输出元素的值。
    this.getHead = getHead;  //获取表头
}
//List的验证：
let list = new LinkedList();
list.append(15);
list.append(10);
list.insert(1,44);
console.log(list.size());   //3
list.removeAt(1);
list.remove(10);
console.log(list.size());    //1
console.log(list.indexOf(15));  //0
list.removeAt(0);
console.log(list.isEmpty());    //true

//1、向链表尾部添加元素
function append(element){
    let node = new Node(element);
    let current;
    if(this.head == null){   //空链表
        this.head = node;
    }else{
        current = this.head;
        while(current.next){
            current = current.next;  //循环到最后一个元素
        }
        current.next = node;  //将新节点赋给最后一个元素的next指针，建立连接    
    }
    length++;   //更新链表长度
}

//3、移除元素，第一种是根据元素的值移除元素；第二种是从特定位置移除一个元素，现在我们看看第一种。第二种移除方法见于indexOf方法之后。
function removeAt(position){
    if(position < 0 || position > length){
        return null;
    }
    let current = this.head;
    let previous, index = 0;
    if(position == 0){
        this.head = current.next;
    }else{
        while(index++ < position){
            previous = current;
            current = current.next;
        }
        previous.next = current.next;
    }
    length--;
    return current.element;   //返回被删除元素的值
}

//4、toString方法，会把LinkedList对象转换成一个字符串
function toString(){
    let current = this.head;
    let str = '';
    while(current){
        str += current.element;
        current = current.next;
    }
    return str;
}

//5、indexOf方法
function indexOf(element){
    let current = this.head;
    let index = 0;
    while(current){
        if(current.element == element){
            return index;
        }
        current = current.next;
        index++;
    }
    return -1;
}
//6、remove方法（可以依靠indexOf方法和removeAt方法实现）
function remove(element){
    let index = this.indexOf(element);
    return this.removeAt(index);
}

//7、isEmpty方法（链表的length是内部控制的，因为LinkedList是从头构建的）
function isEmpty(){
    return length === 0;
}
//8、size方法
function size(){
    return length;
}
//9、getHead方法
//因为head变量是LinkedList类的私有变量（这意味着它不能在LinkedList实例外部被访问和更改，只有通过linkedList实例才可以）。
//但是，如果我们需要在类的外部循环访问列表，就需要提供一种获取类的第一个元素的方法。
function getHead(){
    return this.head;
}

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
function Node(element){   //Node类表示要加入链表的项
    this.element = element;  //要添加到列表的值
    this.next = null;        //指向下一个节点项的指针
}
function LinkedList(){
    let length = 0;
    let head = null;
    //链表方法
    this.append = append;  //向链表尾部添加元素
    this.insert = insert;  //向链表特定位置插入元素
    this.remove = remove;  //移除元素
    this.removeAt = removeAt ;  //移除特定位置的元素
    this.indexOf = indexOf;  //返回元素在链表中的索引。没有该元素则返回-1。
    this.isEmpty = isEmpty;   //判断链表是否为空
    this.size = size;  //返回链表包含元素个数
    this.toString = toString;   //由于链表项使用了Node类，就需要重写继承自JavaScript对象默认的toString方法，让其只输出元素的值。
    this.getHead = getHead;  //获取表头
}
//List的验证：
let list = new LinkedList();
list.append(15);
list.append(10);
list.insert(1,44);
console.log(list.size());   //3
list.removeAt(1);
list.remove(10);
console.log(list.size());    //1
console.log(list.indexOf(15));  //0
list.removeAt(0);
console.log(list.isEmpty());    //true

//1、向链表尾部添加元素
function append(element){
    let node = new Node(element);
    let current;
    if(this.head == null){   //空链表
        this.head = node;
    }else{
        current = this.head;
        while(current.next){
            current = current.next;  //循环到最后一个元素
        }
        current.next = node;  //将新节点赋给最后一个元素的next指针，建立连接    
    }
    length++;   //更新链表长度
}

//2、向链表特定位置插入元素
function insert(position, element){
    //检查越界值
    if(position < 0 || position > length){
        return false;
    }
    let node = new Node(element);
    let current = this.head, index = 0, previous;
    if(position == 0){  //在第一个位置添加
        node.next = current;
        this.head = node;
    }else{
        while(index++ < position){
            previous = current;
            current = current.next;
        }
        node.next = current;
        previous.next = node;
    }
    length++;
    return true;
}

//3、移除元素，第一种是根据元素的值移除元素；第二种是从特定位置移除一个元素，现在我们看看第一种。第二种移除方法见于indexOf方法之后。
function removeAt(position){
    if(position < 0 || position > length){
        return null;
    }
    let current = this.head;
    let previous, index = 0;
    if(position == 0){
        this.head = current.next;
    }else{
        while(index++ < position){
            previous = current;
            current = current.next;
        }
        previous.next = current.next;
    }
    length--;
    return current.element;   //返回被删除元素的值
}

//4、toString方法，会把LinkedList对象转换成一个字符串
function toString(){
    let current = this.head;
    let str = '';
    while(current){
        str += current.element;
        current = current.next;
    }
    return str;
}

//5、indexOf方法
function indexOf(element){
    let current = this.head;
    let index = 0;
    while(current){
        if(current.element == element){
            return index;
        }
        current = current.next;
        index++;
    }
    return -1;
}
//6、remove方法（可以依靠indexOf方法和removeAt方法实现）
function remove(element){
    let index = this.indexOf(element);
    return this.removeAt(index);
}

//7、isEmpty方法（链表的length是内部控制的，因为LinkedList是从头构建的）
function isEmpty(){
    return length === 0;
}
//8、size方法
function size(){
    return length;
}
//9、getHead方法
//因为head变量是LinkedList类的私有变量（这意味着它不能在LinkedList实例外部被访问和更改，只有通过linkedList实例才可以）。
//但是，如果我们需要在类的外部循环访问列表，就需要提供一种获取类的第一个元素的方法。
function getHead(){
    return this.head;
}

4.2 双向链表
双向链表与单向链表的区别在于，在单向链表中，一个节点只有链向下一个节点的链接，而在双向链表中，链接是双向的：一个链向下一个元素，另一个链向前一个元素。如下图所示：
这里写图片描述
双向链表代码实现：

复制代码

function Node(element){
    this.element = element;
    this.next = null;
    this.prev = null;
}
function DoublyLinkedList(){
    let length = 0;
    let head = null;
    let tail = null;  //新增的，保存对列表最后一项的引用
    //方法
    this.append = append;  //向链表尾部添加元素
    this.insert = insert;  //向链表特定位置插入元素
    this.remove = remove;  //移除元素
    this.removeAt = removeAt ;  //移除特定位置的元素
    this.indexOf = indexOf;  //返回元素在链表中的索引。没有该元素则返回-1。
    this.isEmpty = isEmpty;   //判断链表是否为空
    this.size = size;  //返回链表包含元素个数
    this.toString = toString;   //由于链表项使用了Node类，就需要重写继承自JavaScript对象默认的toString方法，让其只输出元素的值。
    this.getHead = getHead;  //获取表头
}
//DoublyLinkedList的验证
let list = new DoublyLinkedList();
list.append(15);
list.append(10);
list.insert(1,44);
console.log(list.size());   //3
list.removeAt(1);
list.remove(10);
console.log(list.size());    //1
console.log(list.indexOf(15));  //0
list.removeAt(0);
console.log(list.isEmpty());    //true

//1、向链表尾部添加元素
function append(element){
    let node = new Node(element);
    let current;
    if(this.head == null){   //空链表,只需要把head和tail都指向这个新节点
        this.head = node;
        this.tail = node;
    }else{
        current = this.tail;  //获取最后一项
        current.next = node;  //将新节点赋给最后一个元素的next指针，建立连接
        node.prev = current;  //还有前驱节点
        this.tail = node;  //更新对最后一个节点的引用   
    }
    length++;   //更新链表长度
}

//2、向链表特定位置插入元素
function insert(position, element){
    //检查越界值
    if(position < 0 || position > length){
        return false;
    }
    let node = new Node(element);
    let current = this.head, index = 0, previous;
    if(position == 0){  //在第一个位置添加
        if(!this.head){   //空列表情况
            this.head = node;
            this.tail = node;   
        }else{
            node.next = current;
            current.prev = node;
            this.head = node;
        }
    }else if(position == length){
        current = this.tail;
        current.next = node;
        node.prev = current;
        this.tail = node;   
    }else{
        while(index++ < position){
            previous = current;
            current = current.next;
        }
        node.next = current;
        current.prev = node;
        previous.next = node;
        node.prev = previous;
    }
    length++;
    return true;
}

//3、移除元素，第一种是根据元素的值移除元素；第二种是从特定位置移除一个元素，现在我们看看第一种。第二种移除方法见于indexOf方法之后。
function removeAt(position){
    if(position < 0 || position >= length){
        return null;
    }
    let current = this.head;
    let previous, index = 0;
    if(position === 0){   //删除第一个
        this.head = current.next;
        if(length === 1){
            this.tail = null;
        }else{
            this.head.prev = null;
        }
    }else if(position === length-1){      //删除最后一个
        current = this.tail;
        previous = current.prev;
        previous.next = null;
        this.tail = previous;
    }else{
        while(index++ < position){
            previous = current;
            current = current.next;
        }
        previous.next = current.next;
        current.next.prev = previous;
    }
    length--;
    return current.element;   //返回被删除元素的值
}

//7、isEmpty方法
function isEmpty(){
    return length === 0;
}
//8、size方法
function size(){
    return length;
}
//9、getHead方法
function getHead(){
    return this.head;
}

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
function Node(element){
    this.element = element;
    this.next = null;
    this.prev = null;
}
function DoublyLinkedList(){
    let length = 0;
    let head = null;
    let tail = null;  //新增的，保存对列表最后一项的引用
    //方法
    this.append = append;  //向链表尾部添加元素
    this.insert = insert;  //向链表特定位置插入元素
    this.remove = remove;  //移除元素
    this.removeAt = removeAt ;  //移除特定位置的元素
    this.indexOf = indexOf;  //返回元素在链表中的索引。没有该元素则返回-1。
    this.isEmpty = isEmpty;   //判断链表是否为空
    this.size = size;  //返回链表包含元素个数
    this.toString = toString;   //由于链表项使用了Node类，就需要重写继承自JavaScript对象默认的toString方法，让其只输出元素的值。
    this.getHead = getHead;  //获取表头
}
//DoublyLinkedList的验证
let list = new DoublyLinkedList();
list.append(15);
list.append(10);
list.insert(1,44);
console.log(list.size());   //3
list.removeAt(1);
list.remove(10);
console.log(list.size());    //1
console.log(list.indexOf(15));  //0
list.removeAt(0);
console.log(list.isEmpty());    //true

//1、向链表尾部添加元素
function append(element){
    let node = new Node(element);
    let current;
    if(this.head == null){   //空链表,只需要把head和tail都指向这个新节点
        this.head = node;
        this.tail = node;
    }else{
        current = this.tail;  //获取最后一项
        current.next = node;  //将新节点赋给最后一个元素的next指针，建立连接
        node.prev = current;  //还有前驱节点
        this.tail = node;  //更新对最后一个节点的引用   
    }
    length++;   //更新链表长度
}

//2、向链表特定位置插入元素
function insert(position, element){
    //检查越界值
    if(position < 0 || position > length){
        return false;
    }
    let node = new Node(element);
    let current = this.head, index = 0, previous;
    if(position == 0){  //在第一个位置添加
        if(!this.head){   //空列表情况
            this.head = node;
            this.tail = node;   
        }else{
            node.next = current;
            current.prev = node;
            this.head = node;
        }
    }else if(position == length){
        current = this.tail;
        current.next = node;
        node.prev = current;
        this.tail = node;   
    }else{
        while(index++ < position){
            previous = current;
            current = current.next;
        }
        node.next = current;
        current.prev = node;
        previous.next = node;
        node.prev = previous;
    }
    length++;
    return true;
}

//3、移除元素，第一种是根据元素的值移除元素；第二种是从特定位置移除一个元素，现在我们看看第一种。第二种移除方法见于indexOf方法之后。
function removeAt(position){
    if(position < 0 || position >= length){
        return null;
    }
    let current = this.head;
    let previous, index = 0;
    if(position === 0){   //删除第一个
        this.head = current.next;
        if(length === 1){
            this.tail = null;
        }else{
            this.head.prev = null;
        }
    }else if(position === length-1){      //删除最后一个
        current = this.tail;
        previous = current.prev;
        previous.next = null;
        this.tail = previous;
    }else{
        while(index++ < position){
            previous = current;
            current = current.next;
        }
        previous.next = current.next;
        current.next.prev = previous;
    }
    length--;
    return current.element;   //返回被删除元素的值
}

//4、toString方法，会把LinkedList对象转换成一个字符串
function toString(){
    let current = this.head;
    let str = '';
    while(current){
        str += current.element;
        current = current.next;
    }
    return str;
}

//5、indexOf方法
function indexOf(element){
    let current = this.head;
    let index = 0;
    while(current){
        if(current.element == element){
            return index;
        }
        current = current.next;
        index++;
    }
    return -1;
}
//6、remove方法（可以依靠indexOf方法和removeAt方法实现）
function remove(element){
    let index = this.indexOf(element);
    return this.removeAt(index);
}

//7、isEmpty方法
function isEmpty(){
    return length === 0;
}
//8、size方法
function size(){
    return length;
}
//9、getHead方法
function getHead(){
    return this.head;
}

4.3 循环链表
循环链表可以像单向链表一样，只有单向引用，也可以像双向链表一样有双向引用。循环链表和链表之间唯一的区别在于，最后一个元素指向下一个元素的指针不是引用null，而是指向第一个元素。如下图所示：
这里写图片描述

循环链表方法与单向链表、双向链表类似。

5、集合

集合是由一组无序且唯一（即不能重复）的项组成。这个数据结构使用了与有限集合相同的数学概念。不包含任何元素的集合是空集。

5.1 创建集合：（实现Set类）

复制代码

function Set(){
    let items = {};    //创建一个空对象为基础,但是也可以用数组来实现，不过javascript对象不允许一个键指向两个不同的属性，保证了集合里的元素都是唯一的
    //方法
    //1、has方法，如果值在集合中，返回true，否则返回false。
    //hasOwnProperty:只会检测实例属性，如果使用（value in items），就会检测原型属性加上实例属性
    this.has = function(value){
        return items.hasOwnProperty(value);  
    };

//2、add方法，向集合添加一个新的项
    this.add = function(value){
        if( !this.has(value) ){
            items[value] = value; //添加一个值的时候，把它同时作为键和值保存，因为这样有利于查找这个值。
            return true;
        }
        return false;  //添加重复的项就返回错误
    };

//3、remove方法，从集合移除一个值
    this.remove= function(value){
        if( this.has(value)){
            delete items[value];
            return true;
        }
        return false;
    };
    //4、clear方法，移除集合中所有的值
    this.clear = function(){
        items = {};
    };
    //5、size方法，返回集合中有多少项
    this.size = function(){
        let count = 0;
        for(let prop in items){
            if(items.hasOwnProperty(prop)){
                count++;
            }
        }
        return count;
    };

//6、values方法，遍历items对象的所有属性，把它们添加至一个数组并返回
    this.values = function(){
        let keys = [];
        for(let key in items){
            keys.push(key);
        }
        return keys;
    };
}

//使用Set类：
let set = new Set();
set.add(1);
console.log(set.values()); //输出["1"]
console.log(set.has(1)); //输出true
console.log(set.size()); //输出1
set.add(2);
console.log(set.values()); //输出["1", "2"]
console.log(set.has(2)); //true
console.log(set.size()); //2
set.remove(1);
console.log(set.values()); //输出["2"]
set.remove(2);
console.log(set.values()); //输出[]

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
function Set(){
    let items = {};    //创建一个空对象为基础,但是也可以用数组来实现，不过javascript对象不允许一个键指向两个不同的属性，保证了集合里的元素都是唯一的
    //方法
    //1、has方法，如果值在集合中，返回true，否则返回false。
    //hasOwnProperty:只会检测实例属性，如果使用（value in items），就会检测原型属性加上实例属性
    this.has = function(value){
        return items.hasOwnProperty(value);  
    };

    //2、add方法，向集合添加一个新的项
    this.add = function(value){
        if( !this.has(value) ){
            items[value] = value; //添加一个值的时候，把它同时作为键和值保存，因为这样有利于查找这个值。
            return true;
        }
        return false;  //添加重复的项就返回错误
    };

    //3、remove方法，从集合移除一个值
    this.remove= function(value){
        if( this.has(value)){
            delete items[value];
            return true;
        }
        return false;
    };
    //4、clear方法，移除集合中所有的值
    this.clear = function(){
        items = {};
    };
    //5、size方法，返回集合中有多少项
    this.size = function(){
        let count = 0;
        for(let prop in items){
            if(items.hasOwnProperty(prop)){
                count++;
            }
        }
        return count;
    };

    //6、values方法，遍历items对象的所有属性，把它们添加至一个数组并返回
    this.values = function(){
        let keys = [];
        for(let key in items){
            keys.push(key);
        }
        return keys;
    };
}

//使用Set类：
let set = new Set();
set.add(1);
console.log(set.values()); //输出["1"]
console.log(set.has(1)); //输出true
console.log(set.size()); //输出1
set.add(2);
console.log(set.values()); //输出["1", "2"]
console.log(set.has(2)); //true
console.log(set.size()); //2
set.remove(1);
console.log(set.values()); //输出["2"]
set.remove(2);
console.log(set.values()); //输出[]

5.2 集合操作：
对集合可以进行如下操作：
* 并集：对于给定的两个集合，返回一个包含两个集合中所有元素的新集合。
* 交集：对于给定的两个集合，返回一个包含两个集合中共有元素的新集合。
* 差集：对于给定的两个集合，返回一个包含所有存在于第一个集合且不存在于第二个集
合的元素的新集合。
* 子集：验证一个给定集合是否是另一集合的子集。

各方法代码实现如下：

复制代码

//并集方法：union
this.union = function(otherSet){
    let unionSet = new Set();   //用于存放并集中的值
    let values = this.values();
    for(let i=0; i<values.length; i++){
        unionSet.add(values[i]);
    }
    values = otherSet.values();
    for(let i=0; i<values.length; i++){
        unionSet.add(values[i]);   //add函数会去重
    }
    return unionSet;
};

//交集方法：intersection
this.intersection = function(otherSet){
    let intersection = new Set();
    let values = this.values();
    for(let i=0; i<values.length; i++){
        if( otherSet.has(values[i]) ){
            intersection.add(values[i]);
        }
    }
    return intersection;
};

//差集方法：difference
this.difference = function(otherSet){
    let differenceSet = new Set();
    let values = this.values();
    for(let i=0; i<values.length; i++){
        if( !otherSet.has(values[i]) ){
            differenceSet.add(values[i]);
        }
    }
    return differenceSet;
};

//子集方法：subset
this.subset = function(otherSet){
    if(this.size() > otherSet.size()){
        return false;
    }
    let values = this.values();
    for(let i=0; i<values.length; i++){
        if( !otherSet.has(values[i]) ){
            return false;
        }
    }
    return true;
};

//将各函数至于Set函数中，测试下列代码：
let setA = new Set();
setA.add(1);
setA.add(2);
setA.add(3);
let setB = new Set();
setB.add(3);
setB.add(4);
setB.add(5);
let unionAB = setA.union(setB);
console.log(unionAB.values());    //["1", "2", "3", "4", "5"]
let intersectionAB = setA.intersection(setB);
console.log(intersectionAB .values());    //["3"]
let differenceAB = setA.difference(setB);
console.log(differenceAB.values());    //["1", "2"]
let setC = new Set();
setC.add(1);
console.log(setA.subset(setB));    //false
console.log(setC.subset(setA));    //true

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
//并集方法：union
this.union = function(otherSet){
    let unionSet = new Set();   //用于存放并集中的值
    let values = this.values();
    for(let i=0; i<values.length; i++){
        unionSet.add(values[i]);
    }
    values = otherSet.values();
    for(let i=0; i<values.length; i++){
        unionSet.add(values[i]);   //add函数会去重
    }
    return unionSet;
};

//交集方法：intersection
this.intersection = function(otherSet){
    let intersection = new Set();
    let values = this.values();
    for(let i=0; i<values.length; i++){
        if( otherSet.has(values[i]) ){
            intersection.add(values[i]);
        }
    }
    return intersection;
};

//差集方法：difference
this.difference = function(otherSet){
    let differenceSet = new Set();
    let values = this.values();
    for(let i=0; i<values.length; i++){
        if( !otherSet.has(values[i]) ){
            differenceSet.add(values[i]);
        }
    }
    return differenceSet;
};

//子集方法：subset
this.subset = function(otherSet){
    if(this.size() > otherSet.size()){
        return false;
    }
    let values = this.values();
    for(let i=0; i<values.length; i++){
        if( !otherSet.has(values[i]) ){
            return false;
        }
    }
    return true;
};

//将各函数至于Set函数中，测试下列代码：
let setA = new Set();
setA.add(1);
setA.add(2);
setA.add(3);
let setB = new Set();
setB.add(3);
setB.add(4);
setB.add(5);
let unionAB = setA.union(setB);
console.log(unionAB.values());    //["1", "2", "3", "4", "5"]
let intersectionAB = setA.intersection(setB);
console.log(intersectionAB .values());    //["3"]
let differenceAB = setA.difference(setB);
console.log(differenceAB.values());    //["1", "2"]
let setC = new Set();
setC.add(1);
console.log(setA.subset(setB));    //false
console.log(setC.subset(setA));    //true