线性结构
1 数组
1.1 数组的创建和初始化
1 | // 创建和初始化数组 |
1.2 数组的常见操作
1.末尾添加元素的三种方式
- 通过数组下标
- 通过方法push(参数1,参数2,…)2.首位插入元素
1
2
3
4var numbers = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
numbers[numbers.length - 1] = 10;
numbers.push(11, 12);
console.log(numbers) - 移动数组的后面的元素,在首位添加元素
- 通过unshift(参数1,参数2)方法(参数里面是按照顺序插入的)3.删除最后元素
1
2
3
4
5
6
7for (var i = numbers.length; i > 0; i--) {
numbers[i] = numbers[i - 1];
}
numbers[0] = 100;
numbers.unshift(-1);
numbers.unshift(-2, -3);//插入以后按照顺序排放,-2,-3,
console.log(numbers); - pop():返回删除的元素4.删除第一个元素
1
console.log(numbers.pop());
- 通过移动后面的元素覆盖前面的元素删除
- shift():删除第一个元素并且返回5.删除指定位置的元素
1
2
3
4
5for (var i = 0; i < numbers.length; i++) {
numbers[i] = numbers[i + 1];
}
console.log(numbers);
console.log(numbers.shift()); - splice(index,n,element1,element2,…)
- index:删除的索引起始位置
- n:删除的元素的个数,0为不删除,直接插入元素
- element:删除之后的替代元素
- 直接修改数组
1
2numbers.splice(5, 3, 'a', 'c');
console.log(numbers);1.3 数组的合并
- concat(arrayX,arrayX,……,arrayX):连接两个或者多个数组,并返回结果数组
- “+”:返回的是字符串,实际是字符串的拼接
1
2
3
4
5
6
7var num1 = [1, 2, 3];
var num2 = [3, 4, 5];
var newnum = num2.concat(num1);
console.log(newnum);
// 字符串的拼接
console.log(num1 + num2)
console.log(typeof (num1 + num2));//1,2,33,4,5
- map():对数组中的每个元素调用匿名函数中的方法并返回一个新的数组,不会改变原数组
- filter()过滤符合条件的,返回一个新的数组,不会改变原数组
- some()查找数组中是否有满足条件的,返回true,false
- every():判断数组中的元素是否满足条件,所有的都满足才会返回true,some还要有一个满足就会返回true
- stringObject.indexOf(searchvalue,fromindex):可返回某个指定的字符串值在字符串中首次出现的位置。
- searchvalue:查找的值
- fromindex:开始检索的位置
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23var names = ["abc", "cb", "mba", "dna"];
var newNames = names.map(function (t) {
return t + '-abc';
})
console.log(newNames);
// 获取包含a的字符
var newNames1 = names.filter(function (t) {
return t.indexOf('a') != -1;
})
console.log(newNames1);
names.forEach(element => {
console.log(element)
});
// 判断数组中是否都含有a元素,全部含有返回true
var flag = names.every(function (value) {
return value.indexOf('a') != -1;
})
console.log(flag)
// 判断是否含有a,只要有一个满足则返回true
var flags = names.some(function (value) {
return value.indexOf('a') != -1;
})
console.log(flags);1.4 reduce方法
- reduce()方法接收函数作为累加器,reduce方法为数组中的每一个方法依次执行回调函数,不包括数组中被删除的或未被赋值的,接收四个参数
- arr.reduce(callback,[initialValue])
- callback函数中有四个参数
- previousValue (上一次调用回调返回的值,或者是提供的初始值(initialValue))
- currentValue (数组中当前被处理的元素)
- index (当前元素在数组中的索引)
- array (调用的数组)
- initialValue (作为第一次调用 callback 的第一个参数。)设置prev的初始类型和初始值
- 此方法不兼容IE9
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15var numbers = [1, 2, 3, 4];
//reduce()实现叠加
var total = numbers.reduce(function (pre, cur, index, arr) {
console.log(pre);
console.log(cur);
console.log(index);
console.log(arr);
return pre + cur;
});//1+2+3+4
// 设置第二个参数来设置初始值
var initValue = numbers.reduce(function (pre, cur) {
console.log(pre);
console.log(cur);
return pre + cur;
}, 5);//5+1+2+3+42 栈
- 栈是先进后出(FILO)
2.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// 封装栈
function Stack() {
this.items = [];
// 封装方法
/*
这里有两种方法实现,
- 通过普通函数
- 通过对象原型(建议使用这种)
*/
// 压栈
Stack.prototype.push = function (element) {
this.items.push(element);//不需要有返回值
}
// 从栈中取出元素
Stack.prototype.pop = function () {
return this.items.pop();
}
// 取出栈中的最后一个元素
Stack.prototype.peek = function () {
return this.items[this.items.length - 1];
}
// 判断栈是否为空
Stack.prototype.isEmpty = function () {
return this.items.length == 0;
}
// 获取栈中元素的个数
Stack.prototype.size = function () {
return this.items.length;
}
// toString()方法
Stack.prototype.toString = function () {
var str = '';
for (var i = 0; i < this.items.length; i++) {
str += this.items[i] + ' ';
}
return str;
}
}
var s = new Stack();
s.push(20);
s.push(3);
s.push(4);
s.push(20);
s.push(3);
s.push(4);
s.push(20);
s.push(3);
s.push(4);
console.log(s.toString());
s.pop();
console.log(s.toString());
s.pop();
console.log(s.toString());
var a = s.peek();
console.log(a);
console.log(s.isEmpty());
console.log(s.size());2 十进制转为二进制
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18// 1.应用:十进制转化为二进制
function dec2bin(num) {
var stack = new Stack();
// 通过循环计算压栈
while (num > 0) {
// 压栈
stack.push(num % 2);
// 计算结果
num = Math.floor(num / 2);
}
// 打印输出的值
var str = '';
while (!stack.isEmpty()) {
str += stack.pop();
}
return str;
} - 逻辑实现
基于链表实现
- 暂时先不讲
3 队列
- 队列分为
- 此方法不兼容IE9
- 基础队列
- 优先级队列
3.1 基于数组实现
3.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// 定义队列
function Queue() {
// 定义属性
this.items = [];
// 定义方法
Queue.prototype.enqueue = function (ele) {
// 从队尾插入元素
this.items.push(ele);
}
// 删除头元素
Queue.prototype.dequeue = function () {
return this.items.shift();
}
// 查看队头元素
Queue.prototype.front = function () {
return this.items[0];
}
// 是否为空
Queue.prototype.isEmpty = function () {
return this.items.length == 0;
}
// 返回队列包含的元素格式
Queue.prototype.size = function () {
return this.items.length;
}
// toString()方法
Queue.prototype.toString = function () {
var str = '';
for (var i = 0; i < this.items.length; i++) {
str += this.items[i] + ' ';
}
return str;
}
}
var queue = new Queue();
queue.enqueue('as');
queue.enqueue('ae');
queue.enqueue('e');
queue.enqueue('r');
console.log(queue.toString());
queue.dequeue();
console.log(queue.toString());
console.log(queue.isEmpty());
console.log(queue.size());
console.log(queue.front());3.1.2 面试题击鼓传花
- 数到谁淘汰谁,从下一个人继续开始,最终剩余的人是获胜的人,返回获胜的人的下标志
- 判断条件:size==0
- 数到指定数字值(5)的人淘汰
- 实现
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/*
namelist:人员列表加入到队列中
num:淘汰的数字
*/
function passGame(namelist, num) {
var queue = new Queue();
// 将人员列表加入到队列中
for (var i = 0; i < namelist.length; i++) {
queue.enqueue(namelist[i]);
}
// 开始数数
while (queue.size() > 1) {
// 数到1-(num-1)的人删除后加入到队列末尾
for (var i = 0; i < num - 1; i++) {
queue.enqueue(queue.dequeue());
}
// 数到num的人是删除
queue.dequeue();
}
// 获取剩余的人
console.log(queue.size());
var name = queue.dequeue();
var nameindex = namelist.indexOf(name);
// 获取对应的数字序列号
return nameindex;
}
var list = ['a', 'b', 'c', 'd', 'e']
passGame(list, 5)3.1.3 优先级队列
- 数字越小,优先级越高
- 实现分析
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// 封装优先级队列
function PriorityQueue() {
var items = []
// 封装一个新的构造函数, 用于保存元素和元素的优先级
function QueueElement(element, priority) {
this.element = element
this.priority = priority
}
// 添加元素的方法
this.enqueue = function (element, priority) {
// 1.根据传入的元素, 创建新的QueueElement
var queueElement = new QueueElement(element, priority)
// 2.获取传入元素应该在正确的位置
if (this.isEmpty()) {
items.push(queueElement)
} else {
var added = false
for (var i = 0; i < items.length; i++) {
// 注意: 我们这里是数字越小, 优先级越高
if (queueElement.priority < items[i].priority) {
items.splice(i, 0, queueElement)
added = true
break
}
}
// 遍历完所有的元素, 优先级都大于新插入的元素时, 就插入到最后
if (!added) {
items.push(queueElement)
}
}
}
// 删除元素的方法
this.dequeue = function () {
return items.shift()
}
// 获取前端的元素
this.front = function () {
return items[0]
}
// 查看元素是否为空
this.isEmpty = function () {
return items.length == 0
}
// 获取元素的个数
this.size = function () {
return items.length
}
}
// 创建优先级队列对象
var pQueue = new PriorityQueue()
// 添加元素
pQueue.enqueue("abc", 10)
pQueue.enqueue("cba", 5)
pQueue.enqueue("nba", 12)
pQueue.enqueue("mba", 3)
// 遍历所有的元素
var size = pQueue.size()
for (var i = 0; i < size; i++) {
var item = pQueue.dequeue()
alert(item.element + "-" + item.priority)
}3.2 基于链表实现
暂不介绍4 链表
- 链表结构
4.1 单链表
- 封装
1
2
3
4
5
6
7
8
9
10
11
12// 封装链表
function LinkList() {
// 封装节点类
function Node(data) {
this.data = data;
this.next = null;//节点引用
};
//封装属性
this.head = null;
this.length = 0;
<!-- 封装方法 -->
}4.1.1链表常用的方法
append():向链表尾部添加数据
- 链表本身为空,新添加的数据为唯一数据
- 链表本身不为空,需要向其他节点后面追加节点
- 添加示意图
- 代码实现:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22// 1.append()方法:在末尾追加元素
LinkList.prototype.append = function (element) {
// (1).创建元素
var node = new Node(element);
// (2)判断链表
if (this.head === null) {
// 链表为空
this.head = node;
} else {
// 链表不为空
// 查找链表节点中next为空的家电并插入
var current = this.head;
while (current.next) {
// 移动指针查找
current = current.next;
}
// 插入节点
current.next = node;
}
// (3)修改length
this.length++;
}toString()
- 代码
1
2
3
4
5
6
7
8
9
10
11LinkList.prototype.toString = function () {
// 定义变量保存当前指针位置和字符串的输出
var current = this.head;
var listString = '';
while (current) {
listString += current.data + ' ';
current = current.next;
}
// 返回最终的的结果
return listString;
}insert():插入元素到链表的任意位置
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// 3.insert(position,data),插入的位置和插入的元素,position指的是下标值
LinkList.prototype.insert = function (position, data) {
// (1)越界问题
if (position < 0 || position > this.length) {
return false;
}
// (2).定义变量保存信息
var newNode = new Node(data);
var current = this.head;
// 保存待插入位置的前一个node
var previous = null;
var index = 0;//判断指针移动所在位置的索引号
if (position == 0) {//第一个位置插入
newNode.next = current;
this.head = newNode;
} else {
while (index++ < position) {
previous = current;//始终指向前一个位置
current = current.next;//指向下一个位置
}
// (3)找到待插入的位置后插入元素,先链接next
newNode.next = current;
previous.next = newNode;
console.log(this);
}
// (4)length
this.length++;
return true;//必须添加返回值
}get(position):获取指定位置的元素
- 判断越界
- 判断指针位置
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15LinkList.prototype.get = function (position) {
// (1)判断数组越界
if (position > this.length || position < 0) {
return null;
}
// (2)移动指针获取指定位置的元素
var current = this.head;
var index = 0;
while (index < position) {
// alert(current.data)
current = current.next;
index++;
}
return current.data;
}indexOf(data)返回指定元素所在的索引值,不存在则返回-1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16LinkList.prototype.indexOf = function (data) {
// (1)需要两个变量进行信息存储
var index = 0;
var current = this.head;
// (2)查找元素所在的位置
while (current) {
if (current.data === data) {
// 返回index
return index;
}
index++;
current = current.next;
}
// 没有找到则返回-1
return -1;
}update(position,data)修改指定位置的内容
1
2
3
4
5
6
7
8
9
10
11
12
13
14
156.
LinkList.prototype.update = function (position, data) {
// (1)越界判断
if (position > this.length || position < 0) {
return false;
}
var index = 0;
var current = this.head;
while (index++ < position) {
current = current.next;
}
//修改指定位置的值
current.data = data;
return true;
}removeAt(position):删除指定位置的元素
- 涉及到位置的需要考虑越界问题
- 链表长度有变化的需要考虑length的变化
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
27LinkList.prototype.removeAt = function (position) {
// 位置涉及越界
if (position > this.length || position < 0) {
return null;
}
//需要两个变量来存储
var index = 0;
var current = this.head;
var previous = null;
// 判断是否移除第一项
if (position == 0) {
// 直接将指针移动到下下个位置
this.head = current.next;
} else {
while (index++ < position) {
previous = current;
current = current.next;
}
// 找到位置删除元素
previous.next = current.next;
}
// 修改length
this.length--;
// 返回删除的元素
return current.data;
}remove(data):删除指定元素
1
2
3
4
5
6LinkList.prototype.remove = function (data) {
// 获取元素的位置
var index = this.indexOf(data);
// 删除指定元素
return this.removeAt(index);
}isEmpty():判断是否为空
size():返回链表的长度
4.2 双链表
- 双向链表示意图
- 双向链表的特点
- 双向链表示意图
- 可以使用一个head和一个tail分别指向头部和尾部的节点
- 每个节点由三个部分组成
- pre:前一个节点的指针
- item:保存的元素
- next:后一个节点的指针
- 双向链表的第一个节点的pre=null
- 双向链表的最后一个节点的next=null
4.2.1双向链表的封装
1
2
3
4
5
6
7
8
9
10
11
12
13
14function DoubleLinkList() {
// 创建节点构造函数
function Node(data) {
this.pre = null;
this.data = data;
this.next = null;
}
// 定义属性
this.length = 0;
this.head = null;
this.tail = null;
// 定义相关的操作方法
}4.2.2链表常用的方法
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
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229// 创建双向链表对象
function DoubleLinkList() {
// 创建节点构造函数
function Node(data) {
this.pre = null;
this.data = data;
this.next = null;
}
// 定义属性
this.length = 0;
this.head = null;
this.tail = null;
// 定义相关的操作方法
// 1.在表尾追加元素append()
DoubleLinkList.prototype.append = function (data) {
// (1)创建元素节点
var node = new Node(data);
// 判断列表是否为空
if (this.head == null) {
this.head = node;
this.tail = node;
} else {
// 连接末尾元素
this.tail.next = node;
node.pre = this.tail;
this.tail = node;//移动tail值
}
// 修改length
this.length++;
}
// 2.insert()在任意的位置插入元素
DoubleLinkList.prototype.insert = function (position, data) {
// 越界
if (position > this.length || position < 0) {
return false;
}
// 创建节点
var newNode = new Node(data);
// 查找位置
if (position == 0) {
// 在第一个位置插入元素
// 判断链表是否为空
if (!this.head) {
this.head = newNode;
this.tail = newNode;
} else {
this.head.pre = newNode;
newNode.next = this.head;
this.head = newNode;
}
} else if (position == this.length) {
// 插入到末尾
this.tail.next = newNode;
newNode.pre = this.tail;
this.tail = newNode;
} else {
// 中间的位置
var index = 0;
var current = this.head;
var previous = null;
//查找插入的位置
while (index++ < position) {
previous = current;
current = current.next;
}
// 交换节点的执行顺序
newNode.next = current;
newNode.pre = previous;
current.pre = newNode;
previous.next = newNode;
}
// 修改length
this.length++;
return true;
}
// 3.toString()
DoubleLinkList.prototype.toString = function () {
return this.backwardString();
}
// 4.backwardString()从前往后输出
DoubleLinkList.prototype.backwardString = function () {
var current = this.head;
var str = '';
while (current) {
str += current.data + ' ';
current = current.next;
}
return str;
}
// 5.forwardString()从后往前输出
DoubleLinkList.prototype.forwardString = function () {
var current = this.tail;
var str = '';
while (current) {
str += current.data + ' ';
current = current.pre;
}
return str;
}
// 6.get(position)获取指定位置的元素
DoubleLinkList.prototype.get = function (position) {
// 越界
if (position > this.length || position < 0) {
return null;
}
// 获取位置
// 如果length/2>position从前往后遍历.反之从前往后遍历
if (this.length / 2 > position) {
var current = this.head;
var index = 0;
while (index++ < position) {
current = current.next;
}
return current.data;
} else {
var current = this.tail;
var index = 0;
while (index++ < position) {
current = current.pre;
}
return current.data;
}
}
// 7.indexOf(data)
DoubleLinkList.prototype.indexOf = function (data) {
var current = this.head;
var index = 0;
while (current) {
if (current.data == data) {
return index;
}
current = current.next;
index++;
}
// 没有找到则返回-1
return -1;
}
// 8.update()
DoubleLinkList.prototype.update = function (position, newdata) {
if (position > this.length || position < 0) {
return false;
}
// 获取位置
// 如果length/2>position从前往后遍历.反之从前往后遍历
if (this.length / 2 > position) {
var current = this.head;
var index = 0;
while (index++ < position) {
current = current.next;
}
current.data = newdata;
return true;
} else {
var current = this.tail;
var index = 0;
while (index++ < position) {
current = current.pre;
}
current.data = newdata
return true;
}
}
// 9.removeAt(position)根据位置删除对应的元素
DoubleLinkList.prototype.removeAt = function (position) {
// 越界
if (position < 0 || position >= this.length) {
return null;
}
// 判断移出的位置
var current = this.head;
// (1)是不是只有一个节点
if (this.length === 1) {
this.head = null;
this.tail = null;
current = this.tail;
} else {
// 删除的是第一个位置
if (position == 0) {
current = this.head;
this.head.next.pre = null;
this.head = this.head.next;
} else if (position == this.length - 1) {
// 删除最后节点
current = this.tail;
this.tail.pre.next = null;
this.tail = this.tail.pre;
} else {
// 删除中间节点
var index = 0;
while (index++ < position) {
current = current.next;
}
current.next.pre = current.pre;
current.pre.next = current.next;
}
}
// 修改length
this.length--;
return current.data;
}
// 10.remove(data)
DoubleLinkList.prototype.remove = function (data) {
var index = this.indexOf(data);
return this.removeAt(index);
}
// 11.isEmpty()
DoubleLinkList.prototype.isEmpty = function () {
return this.length == 0;
}
// 12.size()
DoubleLinkList.prototype.size = function () {
return this.length;
}
// 13.getHead()
DoubleLinkList.prototype.getHead = function () {
return this.head.data;
}
// 14.getTail()
DoubleLinkList.prototype.getTail = function () {
return this.tail.data
}
}5 集合
- Object.keys(obj):方法会返回一个由一个给定对象的自身可枚举属性组成的数组,数组中属性名的排列顺序和使用 for…in 循环遍历该对象时返回的顺序一致 。
- Object.hasOwnProperty(键名):方法会返回一个布尔值,指示对象自身属性中是否具有指定的属性(也就是,是否有指定的键)。
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
53function Set() {
// 封装属性,这里采用对象的方式来存储集合的元素
this.items = {};
// 集合方法
// has(value)是否含有key
Set.prototype.has = function (key) {
return this.items.hasOwnProperty(key)
}
// 添加元素
Set.prototype.add = function (value) {
// 判断是否含有
if (this.has(value)) {
return false;
}
//添加,键值对的形式
this.items[value] = value;
return true;
}
// 删除
Set.prototype.remove = function (value) {
if (!this.has(value)) {
return false;
}
delete this.items[value];
return true;
}
// 清空clear
Set.prototype.clear = function () {
this.items = {}
}
// size,Object.keys()返回的是一个含有键名的数组
Set.prototype.size = function () {
return Object.keys(this.items).length;
// 考虑兼容性使用一下代码
var count = 0;
for (var value in this.items) {
if (this.items.hasOwnProperty(value)) {
count++;
}
}
return count;
}
// 获取集合中所有的值
Set.prototype.values = function () {
return Object.values(this.items);
// 考虑兼容性
// var keys = []
// for (var value in this.items) {
// keys.push(value)
// }
// return keys
}
}- Set类的方法
- Set中键值对的名称一般是相同的
mdn set结构详解5.2 集合之间常见的操作
5.2.1 并集
1 | Set.prototype.unionSet = function (SetB) { |
5.2.2 交集
1 | Set.prototype.intersectionSet = function (otherSet) { |
5.2.3 差集
1 | Set.prototype.differenceSet = function (otherSet) { |
5.2.4 子集
- return 在forEach()中不能跳出函数体解决方案见博文
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22Set.prototype.subSet = function (otherSet) {
// otherset是不是this的子集
var values = this.values();
// for (var i = 0; i < values.length; i++) {
// if (!otherSet.has(values[i])) {
// return false;
// }
// }
// return true
try {
values.forEach(value => {
if (!otherSet.has(values[i])) {
throw new Error();//主动抛出错误跳出循环
}
});
} catch (error) {
//抛出错误执行语句
return false;
}
}6 字典
- 字典的主要特点:一一对应(键值对)
- 数组,集合和字典的比较
- 数组存储的是可重复的,有序的,可以通过下标存取
- 集合存储无序的,不可重复的,不可通过下标存取
- 字典中存储的键值对,键不可以重复,值可以重复,获取值通过key来实现
- 数组和集合存储的都是单个数值/字符
- 深入理解
- 字典 是一种以键-值对形式存储数据的数据结构,比如:名字-电话号码,通过名字就能找到对应的电话号码,名字就是键(key),电话号就是值(value)。
- 字典中的键,是值在字典中的索引。
- 对于javascript来说,字典类(Dictionary)的基础是Array类,js中的Array既是一个数组,同时也是一个字典。
- 字典既可以是对象也可以是数组
6.1 字典的创建和使用
- 字典的创建
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15// 字典的创建和使用
var dic = { a: 1, b: 2, c: 3 };
// 输出最初的字典元素
console.log('输出最初的字典元素');
for (var key in dic) {
console.log("key:" + key + ",value:" + dic[key]);
}
//输出按照keys排序后的字典元素
console.log('输出按照keys排序后的字典元素')
var res = Object.keys(dic).sort()
for (var key in res) {
console.log("key:" + res[key] + ",value:" + dic[res[key]]);
}
// 输出按照value值进行排序的结果
console.log('输出按照value值进行排序的结果');
6.2 简单的字典操作
- 键值对中放入键如果是数组会按照顺序进行输出
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15// 简单的字典操作
var dict = new Array();//定义一个字典
// 字典中添加键值对
dic['one'] = '1';
dic['two'] = '2';
dic['8'] = '5';
dic['four'] = '4';
dic['six'] = 'eight';
dic['7'] = 'eight';
dic['6'] = 'eight';
// 输出
for (var key in dic) {
// 键值对中放入键如果是数组会按照顺序进行输出
console.log(key + ':' + dic[key]);
} - 删除字典中的元素
- 字典的封装
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// 添加键值对
function add(key, value) {
this.datastore[key] = value;
}
// 显示字典中的键值
function show() {
for (var key in this.datastore) {
console.log(key + ":" + this.datastore[key]);
}
}
// 根据key查找对应的值
function find(key) {
return this.datastore[key];
}
// 根据key删除对应的值
function remove(key) {
delete this.datastore[key];
}
// 计算字典中的字数
function count() {
var n = 0;
for (var key in Object.keys(this.datastore)) {
++n;
}
return n;
}
// 字典按照键排序,并输出排序后的结果
function kSort() {
var dict = this.datastore;
var res = Object.keys(dict).sort();
for (var key in res) {
console.log(res[key] + ":" + dict[res[key]]);
}
}
// 字典按照值排序,并输出排序后的结果
function vSort() {
var dict = this.datastore;
var res = Object.keys(dict).sort(function (a, b) {
return dict[a] - dict[b];
});
for (var key in res) {
console.log(res[key] + ":" + dict[res[key]]);
}
}
// 清空字典内存
function clear() {
for (var key in this.datastore) {
delete this.datastore[key];
}
}
function Dict() {
// 定义数组,保存字典元素
this.datastore = new Array();
// 定义方法
this.add = add;//添加字典中的键值内容
this.show = show;//显示字典中的键值
this.find = find;//按key查找元素并进行返回
this.remove = remove;//删掉相对应的键值
this.count = count;//计算字典中的元素个数
this.kSsort = kSort;//按key排序
this.vSort = vSort;//按value排序
this.clear = clear;//清空字典
}
// 创建实例
var dict = new Dict();
dict.add('aaa', '4')
dict.add('bbb', '5')
dict.add('ccc', '2')
dict.add('eee', '3')
dict.add('fff', '12')
dict.add('ggg', '11')
dict.add('ddd', '9')
dict.show();
console.log(dict.find('aaa'));
dict.remove('eee');
dict.show();
console.log(dict.count());
dict.kSsort();
console.log('----')
dict.vSort();
dict.clear(); - 执行结果
本文作者:
SparkParis
本文链接: https://sparkparis.github.io/2020/04/11/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%841/
版权声明: 本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。转载请注明出处!
本文链接: https://sparkparis.github.io/2020/04/11/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%841/
版权声明: 本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。转载请注明出处!