logo头像

总有人间一两风，填我十万八千梦

JS实现复杂数据结构

JS JS 计算机基础 数据结构 2017/03/26

一、哈希表

简介

javascript 里面是没有哈希表的，而在 java、C#、C++ 中会经常用到这一种数据结构，同时在刷 Leetcode 过程中也会经常用到。细细看来，其实 javascript 的 object 的属性与哈希表非常类似。我们只需要在其基础上封装一些 HashTable 的函数，就能够得到一个精简版的哈希表。

加入函数

函数名说明返回值
add(key,value)添加项无
getValue(key)根据key取值object
remove(key)根据key删除一项无
containsKey(key)是否包含某个keybool
containsValue(value)是否包含某个值bool
getValues()获取所有的值的数组array
getKeys()获取所有的key的数组array
getSize()获取项总数int
clear()清空哈希表无

代码实现

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
function HashTable() {
    var size = 0;
    var entry = new Object();
    this.add = function (key, value) {
        if (!this.containsKey(key)) {
            size++;
        }
        entry[key] = value;
    }
    this.getValue = function (key) {
        return this.containsKey(key) ? entry[key] : null;
    }
    this.remove = function (key) {
        if (this.containsKey(key) && (delete entry[key])) {
            size--;
        }
    }
    this.containsKey = function (key) {
        return (key in entry);
    }
    this.containsValue = function (value) {
        for (var prop in entry) {
            if (entry[prop] == value) {
                return true;
            }
        }
        return false;
    }
    this.getValues = function () {
        var values = new Array();
        for (var prop in entry) {
            values.push(entry[prop]);
        }
        return values;
    }
    this.getKeys = function () {
        var keys = new Array();
        for (var prop in entry) {
            keys.push(prop);
        }
        return keys;
    }
    this.getSize = function () {
        return size;
    }
    this.clear = function () {
        size = 0;
        entry = new Object();
    }
}

使用示例

1
2
3
4
var manHT = new HashTable();
manHT.add("p1","刘备");
manHT.add("p2","关羽");
$("#div1").text(manHT.getValue("p1"));

参考文章

二、栈

简介

栈是一种遵从后进先出原则(LIFO，全称为 Last In First Out)的有序集合。栈顶永远是最新的元素。

加入函数

函数名说明返回值
push(element(s))添加几个元素到栈顶无
pop()移除并返回栈顶元素object
peek()返回栈顶元素object
isAmpty检查栈是否为空bool
clear移除栈中所有元素无
size返回栈中元素个数int
print以字符串显示栈中所有内容string
top记录栈顶位置int

代码实现

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
function Stack(){
  this.dataStore = [];//保存栈内元素
  this.top = 0;
  this.push=function (element) {
      this.dataStore[this.top++] = element;//添加一个元素并将top+1
  },
  this.peek=function () {
      return this.dataStore[this.top-1];//返回栈顶元素
  },
  this.pop=function () {
      return this.dataStore[--this.top];//返回栈顶元素并将top-1
  },
  this.clear=function () {
      this.top = 0;//将top归0
  },
  this.size=function () {
      return this.top;//返回栈内的元素个数
  },
  this.isAmpty = function() {
      return this.dataStore.length === 0;//确定栈是否为空
  };
  this.print = function(){
      console.log(this.dataStore.toString());
  }
}

使用示例

1
2
3
4
5
6
7
8
9
10
11
var lk=new Stack();
lk.push("likeke");
lk.push("zhangsan");
lk.push("wangwu");
lk.peek();//"wangwu"
lk.size();3
lk.pop();//"wangwu"
lk.peek();//"zhangsan"
lk.clear();
lk.peek();//undefind
lk.size();0

参考文章

三、队列

简介

队列是一种先进先出的结构。队列也是一种表结构，不同的是队列只能在队尾插入元素，在队首删除元素；在 JS 中可以用数组来实现队列结构

加入函数

函数名说明返回值
enqueue在队列的末尾添加一个元素无
dequeue出队，删除队列的第一个元素并返回object
front取出队列的第一个元素object
back取出队列的最后一个元素object
toString将队列中的元素以字符串形式输出string
empty判断队列是否为空bool
count返回队列中元素的个数int
clear清楚队列无

代码实现

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
function Queue(){
    this.dataStore = [],//队列数据
    this.enqueue = function(){ //入队，就是在数组的末尾添加一个元素
        this.dataStore.push(element);
    },
    this.dequeue = function(){//出队，就是删除数组的第一个元素
        return this.dataStore.shift();
    },
    this.front = function(){//取出数组的第一个元素
        return this.dataStore[0];
    },
    this.back = function(){//取出数组的最后一个元素
        return this.dataStore[this.dataStore.length-1];
    },
    this.toString = function(){//将数组中的元素以字符串形式输出
        var retStr = "";
        for (var i=0; i<this.dataStore.length; ++i) {
            retStr += this.dataStore[i] + "&nbsp;"
        }
        return retStr;
    },
    this.empty = function(){//判断数组是否为空
        if(this.dataStore.length == 0){
            return true;
        }else{
            return false;
        }
    },
    this.count = function(){//返回数组中元素的个数
        return this.dataStore.length;
    },
    this.clear = function(){//清除队列
        this.dataStore = [];
    }
}

使用示例

1
2
3
4
5
6
7
var q = new Queue();
q.enqueue("Meredith");
q.enqueue("Cynthia");
q.enqueue("Jennifer");
console.log(q.toString());//Meredith Cynthia Jennifer
console.log(q.front());//Meredith
console.log(q.back());//Jennifer

参考文章

四、单链表

简介

单链表是一种链式存取的数据结构。链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。

加入函数

函数名说明返回值
value(_key)根据key的值来获取value值value
add(_key,_value)”往链表的尾部加入一个节点value
insert(_key,node)”从某节点之后插入新节点node无
insertBefore(_key,node)从某节点之后插入新节点node无
remove(_key)从链表中移除一个key无
removeAt(n)删除指定位置的节点无
removeAll清空链表无
exists(_key)检查链表类中是否存在一个keybool
getJSON转换成JSON字符串str
getArrayJSON将所有节点的value转换成JSON字符串，数组格式array
getNodeByIndex取第N个位置的节点（头节点为第0个位置）node
getNodeByValue查询值为V的节点（返回第一个找到的）node
print打印输出所有节点string
sort对链表进行排序无
hasSameValueNode测试单链表L中是否有重复元素bool
reverseSingleLink单链表元素反转link

代码实现

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
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
function linkNode(\_key, \_value) {// 链表类的节点类
    this.Key = _key;
    this.Value = _value;
    this.next = null;
}
function Link() {// 创建一个链表类
    this.root = new linkNode(null, null); //root永远是个空节点
    this.end = this.root;
}
Link.prototype = {
    count: 0,//key的数量
    value: function (_key) {//根据key的值来获取value值
        var i = this.root;
        while (Boolean(i = i.next)) {
            if (i.Key == _key)
                return i.Value;
        }
    },
    add: function (\_key, \_value) {// 往链表的尾部中加入一个节点
        var i = this.root;
        while (Boolean(i = i.next)) {
            if (i.Key == _key)
                return i.Value = _value;
        }
        var node = new linkNode(\_key, \_value);
        if (this.count == 0)
            this.root.next = node;
        else
            this.end.next = node;
        this.end = node;
        this.count++;
        return _value;
    },
    insert: function (_key, node) {// 从链表类的某节点之后插入新节点node.
        var i = this.root;
        while (Boolean(i = i.next)) {
            if (i.Key == _key) {
                var tmp = i.next;
                i.next = node;
                node.next = tmp;
                break;
            }
        }
    },
    insertBefore: function (_key, node) {// 从链表类的某节点之后插入新节点node.
        var i = this.root;
        while (Boolean(i = i.next)) {
            if (i.next.Key == _key) {
                var tmp = i.next;
                i.next = node;
                node.next = tmp;
                break;
            }
        }
    },
    remove: function (_key) {// 从链表类中移除一个key
        var i = this.root;
        do
        {
            if (i.next.Key == _key) {
                if (i.next.next == null)
                    this.end = i;
                i.next = i.next.next;
                this.count--;
                return;
            }
        } while (Boolean(i = i.next))
    },
    removeAt : function (n) {//删除指定位置的节点
        if (n <= 0) {
            return;
        }
        var preNode = this.getNodeByIndex(n - 1);
        preNode.next = preNode.next.next;
    },
    removeAll: function () {// 清空链表类
        this.root = new linkNode(null, null);
        this.end = this.root;
        this.count = 0;
    },
    exists: function (_key) {// 检查链表类中是否存在一个key
        var i = this.root;
        while (Boolean(i = i.next))
            if (i.Key == _key)
                return true;
        return false;
    },
    getJSON: function () {// 转换成JSON字符串，内部方法，用于递归
        var me = this;
        var getChild = function (node) {
            var str = "";
            str += "{\\"Key\\":\\"" + node.Key + "\\",\\"Value\\":" + me.Obj2str(node.Value);
            if (node.next != null)
                str += ",\\"next\\":" + getChild(node.next);
            else
                str += ",\\"next\\":\\"null\\"";
            str += "}";
            return str;
        };
        var link = "{\\"root\\":{\\"Key\\":\\"null\\",\\"Value\\":\\"null\\",\\"next\\":";
        if (this.count == 0)//如果空表
        {
            return "{\\"root\\":{\\"Key\\":\\"null\\",\\"Value\\":\\"null\\",\\"next\\":\\"null\\"},\\"end\\":{\\"Key\\":\\"null\\",\\"Value\\":\\"null\\",\\"next\\":\\"null\\"},\\"count\\":\\"0\\"}";
        }
        link += getChild(this.root.next) + "}";
        //加上end
        link += ",\\"end\\":{\\"Key\\":\\"" + this.end.Key + "\\",\\"Value\\":" + me.Obj2str(this.end.Value) + ",\\"next\\":\\"null\\"";
        link += "},\\"count\\":\\"" + this.count + "\\"}";
        return link;
    },
    getArrayJSON: function () {// 转所有节点的value换成JSON字符串,数组格式
        var link = "{'link':[";
        var i = this.root;
        while (Boolean(i = i.next)) {
            link += this.Obj2str(i.Value) + ",";
        }
        link = link.substr(0, link.length - 1);
        link += "]}";
        return link;
    },
    getNodeByIndex: function (n) {//取第N个位置的节点(约定头节点为第0个位置)，N大于链表元素个数时，返回最后一个元素
        var p = this.head;
        var i = 0;
        while (p.next != null && i < n) {
            p = p.next;
            i++;
        }
        return p;
    },
    getNodeByValue: function (v) {//查询值为V的节点，如果链表中有多个相同值的节点，返回第一个找到的
        var p = this.head;
        while (p.next != null) {
            p = p.next;
            if (p.data == v) {
                return p;
            }
        }
        return null;
    },
    print: function () {//打印输出所有节点
        var p = this.head;
        while (p.next != null) {
            p = p.next;
            print(p.data + " ");
        }
        println("");
    },
    sort: function (fn) {// 对链表进行排序
        if (fn != null) {
            var i = this.root;
            while (Boolean(i = i.next)) {
                var j = this.root;
                while (Boolean(j = j.next)) {
                    if (j.next != null) {
                        if (fn.call(this, j)) {
                            var Key = j.Key;
                            var Value = j.Value;
                            j.Key = j.next.Key;
                            j.Value = j.next.Value;
                            j.next.Key = Key;
                            j.next.Value = Value;
                        }
                    }
                }
                this.end = i;
            }
        }
    }
};
function print(msg) {//打印内容
    document.write(msg);
}

function println(msg) {//换行打印内容
    print(msg + "<br/>");
}

function hasSameValueNode(singleLink) {//测试单链表L中是否有重复元素
    var i = singleLink.head;
    while (i.next != null) {
        i = i.next;
        var j = i;
        while (j.next != null) {
            j = j.next;
            if (i.data == j.data) {
                return true;
            }
        }
    }
    return false;
}

function reverseSingleLink(singleLink) {//单链表元素反转
    var arr = new Array();
    var p = singleLink.head;
    //先跑一遍，把所有节点放入数组
    while (p.next != null) {
        p = p.next;
        arr.push(p.data);
    }
    var newLink = new SingleLink();
    //再从后向前遍历数组,加入新链表
    for (var i = arr.length - 1; i >= 0; i--) {
        newLink.insert(arr[i]);
    }
    return newLink;
}

使用示例

1
2
3
4
5
6
7
8
9
var linkTest = new SingleLink();
    linkTest.insert('A');
    linkTest.insert('B');
    linkTest.insert('C');
    linkTest.insert('D');
    linkTest.print();//A B C D

    var newLink = reverseSingleLink(linkTest);
    newLink.print();//D C B A

二叉堆

todo: https://www.zoo.team/article/binary-heap-with-js

参考文章

赏
支付宝打赏 微信打赏

听说赞过就能年薪百万

转载声明：商业转载请联系作者获得授权,非商业转载请注明出处 © Merrier说
访问量:   |   访客数:
Copyright © 2018 | Powered by Hexo | Theme by Snippet | ICP 证： 京ICP备17022347号-1