发表于 | 分类于

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

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
function Dictionary(){
    this.dataStore = new Array();
    this.add = add;
    this.find = find;
    this.remove = remove;
    this.showAll = showAll;
    this.count = count;
    this.clear = clear;
}

// 向字典中添加键值对
function add(key, value){
    this.dataStore[key] = value;
}

// 通过键返回值
function find(key){
    return this.dataStore[key];
}

// 通过键删除键值对
function remove(key){
    delete this.dataStore[key];
}

function showAll() {
    if (Object.keys(this.dataStore).length == 0){
        console.log('null')
    }
    for (let key of Object.keys(this.dataStore).sort()) { // 对键值进行排序
        console.log(key + '->' + this.dataStore[key]);
    }
}

function count(){
    return Object.keys(this.dataStore).length;
    // 方法二
    // let n = 0;
    // for (let key in Object.keys(this.dataStore)){
    //     n++;
    // }
    // return n;
}

function clear(){
    for(let key of Object.keys(this.dataStore)){
        delete this.dataStore[key];
    }
}

// 测试代码
let book = new Dictionary();
book.add('c', '1');
book.add('b', '2');
book.add('a', '3');
console.log('a的值为：'+book.find('a'));
book.remove('b')
console.log(book.count());
book.showAll();
book.clear();
book.showAll();
console.log(book.count());

发表于 | 分类于

双向链表给链上的每个节点增加了一个指向前驱节点的链接，使得从后向前遍历链表时变得简单；同时删除节点时，也不用像单向链表那样寻找待删除节点的前驱节点。

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
// 基于链表都是由节点组成的，我们需要定义一个节点类
function Node(element){
    this.element = element; // 保存节点上的数据
    this.next = null; // 保存指向下一个节点的链接
    this.prev = null; // 保存指向上一个节点的链接
}

// 实现链表类
function LList(){
    this.head = new Node('head');
    this.find = find;
    this.findLast = findLast;
    this.insert = insert;
    this.display = display;
    this.remove = remove;
    this.reverse = reverse;
}

// 插入新节点，需要知道在哪个节点前面或后面插入
// 因此首先要找到一个已知节点
function find(item){
    let currNode = this.head;
    while (currNode.element != item){
        currNode = currNode.next;
    }
    return currNode;
}

// 找到最后一个节点
function findLast(){
    let currNode = this.head;
    while (currNode.next != null) {
        currNode = currNode.next;
    }
    return currNode;
}

// 找到插入的相对点后，设置新节点的前后指向
function insert(newElement, item){
    let newNode = new Node(newElement);
    let current = this.find(item);
    newNode.next = current.next;
    newNode.prev = current;
    current.next = newNode;
}

// 展示链表所有节点(不显示头节点)
function display(){
    let currNode = this.head;
    while (currNode.next != null){
        console.log(currNode.next.element);
        currNode = currNode.next;
    }
}

// 直接找到待删除节点，更改前后指向
function remove(item){
    let currNode = this.find(item);
    if(currNode.next != null){
        currNode.prev.next = currNode.next;
        currNode.next.prev = currNode.prev;
        currNode.prev = null;
        currNode.next = null;
    }
}

function reverse(){
    let currNode = this.findLast();
    while(currNode.prev != null){
        console.log(currNode.element);
        currNode = currNode.prev;
    }
}

// 测试代码
let llist = new LList()
llist.insert("a", "head")
llist.insert("b", "a")
llist.insert("c", "b")
llist.insert("d", "c")
console.log(llist.findLast())
llist.display()
console.log('------')
llist.reverse()
console.log('------')
llist.remove("c")
llist.display()

发表于 | 分类于

在JavaScript中，由于数组被实现为对象，与其他语言相比效率很低。当我们发觉使用数组时运行效率很慢，那么就应该考虑链表。

链表是由一组节点组成的集合，每个节点都使用一个对象的引用来指向它后面的节点，这个指向后面节点的引用就被称为链。

数组和链表的区别：

  • 数组靠位置来引用，链表靠节点之间的相互关系来引用

遍历链表时不包含头节点，头节点作为链表的接入点；链表的尾元素指向一个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
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
// 基于链表都是由节点组成的，我们需要定义一个节点类
function Node(element){
    this.element = element; // 保存节点上的数据
    this.next = null; // 保存指向下一个节点的链接
}

// 实现链表类
function LList(){
    this.head = new Node('head');
    this.find = find;
    this.insert = insert;
    this.display = display;
    this.findPrevious = findPrevious;
    this.remove = remove;
}

// 插入新节点，需要知道在哪个节点前面或后面插入
// 因此首先要找到一个已知节点
function find(item){
    let currNode = this.head;
    while (currNode.element != item){
        currNode = currNode.next;
    }
    return currNode;
}

// 找到插入的相对点后，就可以插入节点了
function insert(newElement, item){
    let newNode = new Node(newElement);
    let current = this.find(item);
    newNode.next = current.next;
    current.next = newNode;
}

// 展示链表所有节点(不显示头节点)
function display(){
    let currNode = this.head;
    while (currNode.next != null){
        console.log(currNode.next.element);
        currNode = currNode.next;
    }
}

// 从链表中删除节点
// 首先要找到待删除节点的前一个节点，让这个节点的next属性不再指向待删除节点，而是指向待删除节点的下一个节点
function findPrevious(item){
    let currNode = this.head;
    while(currNode.next != null && currNode.next.element != item){
        currNode = currNode.next;
    }
    return currNode;
}

// 找到待删除节点的前一个节点后，就可以删除节点了
function remove(item){
    let prevNode = this.findPrevious(item);
    if(prevNode.next != null){
        // prevNode.next = item.next; 这样写是错的，因为item是节点的elment属性的值，并不是节点本身
        prevNode.next = prevNode.next.next;
    }
}

// 测试代码
let llist = new LList();
llist.insert("a", "head");
llist.insert("b", "a");
llist.insert("c", "b");
llist.insert("d", "c");
llist.display();
llist.remove("c");
llist.display();

发表于 | 分类于

队列用于存储按顺序排列的数据，是一种先进先出的数据结构，最后入栈的元素反而被优先处理

应用场景

  • 提交操作系统执行的一系列进程
  • 打印任务池
  • 模拟银行的仿真系统
  • 等等
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
function Queue() {
    this.dataStore = [];
    this.enqueue = enqueue;
    this.dequeue = dequeue;
    this.front = front;
    this.back = back;
    this.toString = toString;
    this.empty = empty;
}
// 向队尾添加一个元素
function enqueue(element){
    this.dataStore.push(element)
}

// 删除队尾元素
function dequeue(){
    return this.dataStore.shift()
}

// 读取队首、队尾元素
function front(){
    return this.dataStore[0]
}
function back(){
    return this.dataStore[this.dataStore.length-1]
}

function toString(){
    let str = ''
    for(let i = 0; i < this.dataStore.length; ++i){
        str += this.dataStore[i] + '\n'
    }
    return str
}

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

// 测试代码
let q = new Queue()
q.enqueue('a')
q.enqueue('b')
q.enqueue('c')
console.log(q.toString())
q.dequeue()
console.log(q.toString())
console.log(q.front())
console.log(q.back())

发表于 | 分类于 
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 quickSort(arr) {
    if(arr.length == 0){
        return []; // 控制递归的终止
    }
    let lesser = [],
        greater = [],
        pivot = arr[0]; // 一般将第一个或最后一个作为基准数
    for (let i = 1; i <= arr.length - 1; i++) {
        // 因为基准数是第一个数，循环从第二个数开始
        if (arr[i] < pivot) {
            lesser.push(arr[i]);
        } else {
            greater.push(arr[i]);
        }
    }
    // 对子序列进行以上操作，通过递归实现
    return quickSort(lesser).concat(pivot, quickSort(greater));
}

// 测试代码
let arr = [];
for (let i = 0; i < 10; ++i) {
    arr[i] = Math.floor((Math.random() * 100) + 1);
}
console.log(arr);
console.log(quickSort(arr));

发表于 | 分类于 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function insertSort(arr){
    // 假设第一个数是已排序的，那么未排序就从第二个数开始，依次从未排序数组中取值，到已排序数组中比较
    for(let outer = 1; outer <= arr.length -1; outer++){
        // 将未排序的数遍历已排序的数组
        for(let inner = 0; inner <= outer -1; inner++){
            // 如果未排序的数比已排序的数小，这里有个技巧，直接从前往后遍历，就可以直接将要插入的值用splice插入
            if(arr[outer] < arr[inner]){
                // 插入到已排序的、比它大的数的前面
                arr.splice(inner, 0, arr[outer]);
                // 将其自身从未排序数组中删除，这里的outer + 1是因为，前面执行了添加，导致数组都整体往后移动一位，所以被插入的数组索引加一
                arr.splice(outer + 1, 1);
            }
        }
    }
}

发表于 | 分类于 
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
function CArray(numElements) {
    this.dataStore = [];
    this.pos = 0;
    this.numElements = numElements;
    this.insert = insert;
    this.toString = toString;
    this.clear = clear;
    this.setData = setData;
    this.swap = swap;
    this.bubbleSort = bubbleSort;
    this.selectSort = selectSort;
    for (let i = 0; i < numElements; ++i) {
        this.dataStore[i] = i;
    }
    function setData() {
        for (let i = 0; i < this.numElements; ++i) {
            this.dataStore[i] = Math.floor(Math.random() * (this.numElements + 1));
        }
    }
    function clear() {
        for (let i = 0; i < this.dataStore.length; ++i) {
            this.dataStore[i] = 0;
        }
    }
    function insert(element) {
        this.dataStore[this.pos++] = element;
    }
    function toString() {
        let str = '';
        for (let i = 0; i < this.dataStore.length; ++i) {
            str += this.dataStore[i] + ' ';
            // 每逢十个换行
            if (i > 0 & i % 10 == 0) {
                str += '\n';
            }
        }
        return str;
    }
    function swap(arr, index1, index2) {
        let temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }
    function bubbleSort() {
        let numElements = this.dataStore.length;
        let temp;
        // 外循环用于遍历数组中的每一项元素
        for (let outer = numElements; outer >= 2; --outer) {
            // 内循环用于比较元素
            for (let inner = 0; inner <= outer - 1; ++inner) {
                if (this.dataStore[inner] > this.dataStore[inner + 1]) {
                    swap(this.dataStore, inner, inner + 1);
                }
            }
        }
    }
    function selectSort() {
        let min;
        for (let outer = 0; outer <= this.dataStore.length - 2; ++outer) {
            min = outer;
            for (let inner = outer + 1; inner <= this.dataStore.length - 1; ++inner) {
                if (this.dataStore[inner] < this.dataStore[min]) {
                    swap(this.dataStore, inner, min);
                }
            }
        }
    }
}

// 测试代码
let numElements = 10;
let myNums = new CArray(numElements);
myNums.setData();
console.log(myNums.toString());
myNums.selectSort();
console.log(myNums.toString());