javascript 数据结构与算法 笔记2.1
2019-01-16 本文已影响0人
wudimingwo
通读第二遍
第一章
image.png
image.png
你会发现 隐式类型转换 发生最多的就是 Number 了
image.png
image.png
第二章 数组
数组, 以及数组的各种原型方法,工具方法.
这些都基础知识都没什么好说的.
push,pop,shift,unshift,slice,splice
forEach,filter,map,every,some,reduce,reduceRight,
indexOf,lastIndexOf,include
Array.of()
Array.from()
copywithin
repeat
fill
image.png
image.png
第三章 栈
用js实现一下, 比你想象的要简单
image.png
最简单的版本
function Stack () {
let item = [];
this.push = function (ele) {
item.push(ele);
}
this.pop = function () {
return item.pop()
}
this.peek = function () {
return item[item.length - 1]
}
this.isEmpty = function () {
return item.length === 0
}
this.clear = function () {
item = [];
}
this.size = function () {
return item.length;
}
}
var stack = new Stack();
栈就是一种数据存储,和取出的一种顺序,
这种顺序就是要最后进的最先出去.
后进先出,(也就是先进后出)
其实刚开始碰到这个栈的时候, 我觉得挺无聊的,
因为观察一下就可以发现,
数组能够完成这个栈的所有概念.
上面的 栈的封装, 内部用的也确实是 数组.(我相信不用数组也可以)
后来我想明白了,跟数组相比
关键不在于功能的实现, 而是功能的限定.
比如说数组除了栈的操作之外, 我们还可以有很多的操作,
比如取出数据时, 可以不用从最后一个取, 从中间就可以取.
栈的封装, 意思就是不允许有这种操作, 只能用后进先出的顺序进行操作.
上面封装, 把所有方法放在了实例上, 我们可以把数据放在实例上,
把方法放在 原型上
function Stack () {
this.item = [];
}
Stack.prototype.push = function (ele) {
this.item.push(ele);
}
Stack.prototype.pop = function () {
return this.item.pop()
}
Stack.prototype.peek = function () {
return this.item[this.item.length - 1]
}
Stack.prototype.isEmpty = function () {
return this.item.length === 0
}
Stack.prototype.clear = function () {
this.item = [];
}
Stack.prototype.size = function () {
return this.item.length;
}
var stack = new Stack();
用es6
class Stack {
constructor() {
this.item = []
}
push(ele) {
this.item.push(ele);
}
pop() {
return this.item.pop()
}
peek() {
return this.item[this.item.length - 1]
}
isEmpty() {
return this.item.length === 0
}
clear() {
this.item = [];
}
size() {
return this.item.length;
}
}
var stack = new Stack();
书上说这样很不好, 因为 生成的实例当中 item属性暴露了,
可以直接通过 stack.item[1] = 111 的方式读取和修改数据了,
作为一个栈, 我们可能不想要这样
let Stack = (function () {
var _item = Symbol();
return class Stack {
constructor() {
this[_item] = [];
}
push(ele) {
this[_item].push(ele);
}
pop() {
return this[_item].pop()
}
peek() {
return this[_item][this[_item].length - 1]
}
isEmpty() {
return this[_item].length === 0
}
clear() {
this[_item] = [];
}
size() {
return this[_item].length;
}
}
})();
这样为好很多, 因为我们通过实例stack 很难访问
stack[_item] 来修改数据.
但实际上,还是可以访问到的.
因为有方法, 可以拿到实例的Symble属性
比如这样
var stack = new Stack();
var symbolArr = Object.getOwnPropertySymbols(stack);/ 返回stack 对象的所有symbol属性的数组
stack[symbolArr[0]];/ 这样就会返回所有数据了.
如果想完全杜绝通过实例访问除了栈方式之外的读写数据的方式,
就可以用weakMap
let Stack = (function () {
var _item = new WeakMap();
return class Stack {
constructor() {
_item.set(this,[]);
}
push(ele) {
_item.get(this).push(ele);
}
pop() {
return _item.get(this).pop();
}
peek() {
var len = _item.get(this).length - 1;
return _item.get(this)[len];
}
isEmpty() {
return _item.get(this).length === 0
}
clear() {
_item.set(this,[]);
}
size() {
return _item.get(this).length;
}
}
})();
var stack = new Stack();
实话实说, 这个我是服的.
因为数组的位置压根跟this位置没关系.通过this 是无法获取 数组的.
文中说有个缺点:
无法扩展继承,因为无法访问私有变量.
,可如果指的是下面这种情形的话, 实际上是可以访问私有变量, 并且继承的
class Stack1 extends Stack {
constructor () {
super()
}
}
var stack = new Stack1();
应用1, 进制转换
function divedeBy2 (decNumber) {
// 思路, 求余,存起来.
var remStack = new Stack(),
rem,
str = '';
while (decNumber > 0){
rem = decNumber%2;
remStack.push(rem);
decNumber = Math.floor(decNumber / 2);
}
while (remStack.size()){
str += remStack.pop();
}
return str
}
实际上, 完全可以用 数组实现. 只是从概念上来讲, 后进先出,即栈正好非常符合,
所以栈这个东西, 包括后面的队列, 他的价值主要在这个概念上,
可以转换成别的进制 即 10进制转成别的进制
function baseConverter(decNumber, base) {
var remStack = new Stack(),
rem,
baseString = '',
digits = '0123456789ABCDEF'; //{6}
while(decNumber > 0) {
rem = Math.floor(decNumber % base);
remStack.push(rem);
decNumber = Math.floor(decNumber / base);
}
while(!remStack.isEmpty()) {
baseString += digits[remStack.pop()]; //{7}
}
return baseString;
}
稍微变动一下, 把其他进制改成 十进制
function baseConverter(decNumber, base) {
decNumber = decNumber.toString().toUpperCase();
digits = '0123456789ABCDEF';
var len = decNumber.length;
var i = 0;
var res = 0;
while (--len >= 0) {
res += Number(digits.indexOf(decNumber[len])) * (base**i++)
}
return res
}
第四章 队列
image.png
我们简单代码实现一下, 上面的几个 方法.
封装在实例上
function Queue() {
this.item = [];
}
Queue.prototype.enqueue = function(ele) {
this.item.push(ele);
}
Queue.prototype.dequeue = function() {
return this.item.shift()
}
Queue.prototype.front = function() {
return this.item[0]
}
Queue.prototype.isEmpty = function() {
return this.item.length === 0
}
Queue.prototype.clear = function() {
this.item = [];
}
Queue.prototype.size = function() {
return this.item.length;
}
var que = new Queue();
封装在原型上
let Queue = (function() {
var _item = new WeakMap();
return class Queue {
constructor() {
_item.set(this, []);
}
enqueue(ele) {
_item.get(this).push(ele);
}
dequeue() {
return _item.get(this).shift();
}
front() {
return _item.get(this)[0];
}
isEmpty() {
return _item.get(this).length === 0
}
clear() {
_item.set(this, []);
}
size() {
return _item.get(this).length;
}
}
})();
var que = new Queue();
你肯定发现了, 这跟栈非常的相似,
栈和队列都是有序的,只是一个是后进先出, 一个是先进先出.
(其实如果重点放在出字上的话, 可以说成, 先出后进的, 先出先进的)
优先队列
主要是 enquque 不同,
出队列的顺序, 在进队列的时候就已经决定了.
let PriorityQueue = (function() {
var _item = new WeakMap();
function QueEle (ele,pt) {
this.ele = ele;
this.pt = pt;
}
return class Queue {
constructor() {
_item.set(this, []);
}
enqueue(ele,pt) {
var pt = pt || 0;
var item = _item.get(this);
var len = item.length;
var added = false;
for(var i = 0 ; i < len; i++) {
if (pt > item[i].pt ) {
//插入操作.
item.splice(i,0,new QueEle(ele,pt))
added = true;
break;
}
}
if (!added) {
// 如果优先级 最低 就放在最后
_item.get(this).push(new QueEle(ele,pt));
}
}
//其他方法和默认的Queue实现相同
})();
var que = new PriorityQueue();
书上源码是这个
function PriorityQueue() {
let items = [];
function QueueElement(element, priority) { // {1}
this.element = element;
this.priority = priority;
}
this.enqueue = function(element, priority) {
let queueElement = new QueueElement(element, priority);
let added = false;
for(let i = 0; i < items.length; i++) {
if(queueElement.priority < items[i].priority) { // {2}
items.splice(i, 0, queueElement); // {3}
added = true;
break; // {4}
}
}
if(!added) {
items.push(queueElement); //{5}
}
};
this.print = function() {
for(let i = 0; i < items.length; i++) {
console.log(`${items[i].element} -
${items[i].priority}`);
}
};
//其他方法和默认的Queue实现相同
}
理论上来讲,
我们也可以弄一个
优先栈, 即, 有权重高的, 就先出权重高的, 如果没有就走后进先出.
而实际上, 跟这个是一模一样的.
也就是 队列和栈,数据进来的方式是一模一样的.
循环队列——击鼓传花
书上就举了一个例子,
核心就一句话
for (let i=0; i<num; i++){
queue.enqueue(queue.dequeue()); / 这一句
}
出队列的同时, 又进了队列,
实际上完成的是 从队列的头转到了队列尾.
队列可以有这种循环操作,
但栈是没有这种循环操作的.
因为后进先出,我把新出来的弄进去, 下回第一个出来的还是这一个.
假设我就想把后进来的放在栈底, 也不是不行,
那我就要用另一个容器把所有的项都先拿出来, 然后再把刚才那个先放进去.
这个动作相比队列来讲, 就要大很多.
其实好好想想的话,
栈和队列可以是同一个结构, 本来两者的结构就可以相同,
唯一不同就是出栈,或者出列的方式,
假设我们同时留出两个api 一个可以先进先出, 一个可以先进后出.
那理论上他即是栈, 也是队列?
进来的通道只有一种, 出去的通道就是两种?
第五章 链表
链表和数组的区别, 原文是这么说的
相对于传统的数组，链表的一个好处在于，添加或移除元素的时候不需要移动其他元素。然
而，链表需要使用指针，因此实现链表时需要额外注意。数组的另一个细节是可以直接访问任何
位置的任何元素，而要想访问链表中间的一个元素，需要从起点（表头）开始迭代列表直到找到
所需的元素。
这表达的很清晰了, 但非要我自己理解的话,就是
数组是, 每个项的参考都是那条线, 对号入座.(就像是一个尺?)
而链表是, 参考的不是一条线,(坐标系不是一条线), 而是另一个项
严格来讲, 我觉得两者虽然不同, 但并非矛盾,即,
不是说,用了数组方式放置数据,就不能用链表放入数据,
两者应该也可以同时存在.
单向链表
image.png
image.png
我的凑合出的版本
function LinkedList () {
let Node = function (ele) {
this.ele = ele;
this.next = null;
}
let length = 0;
let head = null;
this.append = function (ele) {
var node = new Node(ele);
if (head === null) {
head = node
} else {
var current = head;
while (current.next){
current = current.next;
}
current.next = node;
}
}
this.insert = function (position, ele) {
// 这里的position 代表的应该是index head 的index 应该是0
var node = new Node(ele);
if (position == 0) {
node.next = head;
head = node;
} else{
var i = 1;
var current = head;
while (current.next && i++ < position){
current = current.next;
}
node.next = current.next ? current.next.next : null;
current.next = node;
}
}
this.removeAt = function (position) {
if (position == 0) {
head = head.next;
} else{
var i = 1;
var current = head;
while (current.next && i++ < position){
current = current.next;
}
current.next = current.next ? current.next.next : null ;
}
}
this.remove = function (ele) {
var current = head;
while (current.next){
if (current.ele === ele) {
current = current.next;
break;
}
current = current.next;
}
current.next = current.next ? current.next.next : null;
}
this.indexOf = function (ele) {
var current = head;
var i = 0;
while (current.next){
if (current.ele === ele) {
return i
break;
}
current = current.next;
i++;
}
return -1;
}
this.isEmpty = function () {
return head.ele === null ? true : false;
}
this.size = function () {
if (head === null) {
return 0
}
var current = head;
var i = 1;
while (current.next){
i++;
current = current.next;
}
return i
}
this.getHead = function () {
return head;
}
this.get = function (position) {
if (position === 0) {
return head;
}
var current = head;
var i = 0;
while (current.next){
if (i == position) {
return current;
}
i++;
current = current.next;
}
if (i == position) {
return current
}
return null
}
this.toString = function () {
}
this.print = function () {
var str = '';
var current = head;
while (current.next){
str += current.ele + '---';
}
return str;
}
}
var linkNode = new LinkedList();
linkNode.append(1);
linkNode.append(4);
linkNode.append(8);
linkNode.append(3);
linkNode.append(109);
书上的版本
function LinkedList() {
let Node = function(ele) {
this.element = ele;
this.next = null;
}
let length = 0;
let head = null;
this.append = function(element) {
let node = new Node(element), //{1}
current; //{2}
if(head === null) { //列表中第一个节点 //{3}
head = node;
} else {
current = head; //{4}
//循环列表，直到找到最后一项
while(current.next) {
current = current.next;
}
//找到最后一项，将其next赋为node，建立链接
current.next = node; //{5}
}
length++; //更新列表的长度 //{6}
};
this.removeAt = function(position) {
//检查越界值
if(position > -1 && position < length) { // {1}
let current = head, // {2}
previous, // {3}
index = 0; // {4}
//移除第一项
if(position === 0) { // {5}
head = current.next;
} else {
while(index++ < position) { // {6}
previous = current; // {7}
current = current.next; // {8}
}
//将previous与current的下一项链接起来：跳过current，从而移除它
previous.next = current.next; // {9}
}
length--; // {10}
return current.element;
} else {
return null; // {11}
}
};
this.insert = function(position, element) {
//检查越界值
if(position >= 0 && position <= length) { //{1}
let node = new Node(element),
current = head,
previous,
index = 0;
if(position === 0) { //在第一个位置添加
node.next = current; //{2}
head = node;
} else {
while(index++ < position) { //{3}
previous = current;
current = current.next;
} // 结束时, index 必然等于 position 即 current 必然是要插入的位置.
node.next = current; //{4}
previous.next = node; //{5}
}
length++; //更新列表的长度
return true;
} else {
return false; //{6}// 其实这里可以考虑 用 插入在尾部来代替?
}
};
this.indexOf = function(element) {
let current = head, //{1}
index = -1;
while(current) { //{2}
if(element === current.element) {
return index; //{3}
}
index++; //{4}
current = current.next; //{5}
}
return -1;
};
this.remove = function(element) {
let index = this.indexOf(element);
return this.removeAt(index);
};
this.isEmpty = function() {
return length === 0;
};
this.size = function() {
return length;
};
this.getHead = function() {
return head;
};
this.toString = function() {
let current = head, //{1}
string = ''; //{2}
while(current) { //{3}
string += current.element + (current.next ? 'n' : ''); //{4}
current = current.next; //{5}
}
return string; //{6}
};
}
设定一个length 属性 能省很多东西啊.
嗯~设定恰当的中间属性是有用的.
我现在最想学到的一项能力
怎样才能快速把迭代和递归写出来的能力.
像链表这种结构, 其实我很容易理解,
但我发现, 即使我完全理解了链表结构,
想要写出来 迭代或者递归结构,
也总是消耗比较长的时间.
我觉得应该存在是没有找到一种通用的方法.
我自己总结的是
- 找到或者设定 循环变量
像数组,他的参考是一个类似尺子的感觉, 所以遍历的概念比较直观,也容易想象.
而像链表, 他的参考是另一个项,所以循环变量就是一种指针移动的感觉.
循环变量可以有不止一个 - 找到 循环条件 (也许就是算法导论里所说的循环不变式?)
- 查看中间情况是否成立,
- 查看第一个和最后一个的情况是否成立.
双向链表
image.png
function LinkedList() {
let Node = function(ele) {
this.element = ele;
this.next = null;
this.prev = null;
}
let length = 0;
let head = null;
let tail = null;
this.insert = function(position, element) {
//检查越界值
if(position >= 0 && position <= length) {
let node = new Node(element),
current = head,
previous,
index = 0;
if(position === 0) { //在第一个位置添加
if(!head) { //新增的 {1}
head = node;
tail = node;
} else {
node.next = current;
current.prev = node; //新增的 {2}
head = node;
}
} else if(position === length) { //最后一项 //新增的
current = tail; // {3}
current.next = node;
node.prev = current;
tail = node;
} else {
while(index++ < position) { //{4}
previous = current;
current = current.next;
}
node.next = current; //{5}
previous.next = node;
current.prev = node; //新增的
node.prev = previous; //新增的
}
length++; //更新列表的长度
return true;
} else {
return false;
}
};
this.removeAt = function(position) {
//检查越界值
if(position > -1 && position < length) {
let current = head,
previous,
index = 0;
//移除第一项
if(position === 0) {
head = current.next; // {1}
//如果只有一项，更新tail //新增的
if(length === 1) { // {2}
tail = null;
} else {
head.prev = null; // {3}
}
} else if(position === length - 1) { //最后一项 //新增的
current = tail; // {4}
tail = current.prev;
tail.next = null;
} else {
while(index++ < position) { // {5}
previous = current;
current = current.next;
}
//将previous与current的下一项链接起来——跳过current
previous.next = current.next; // {6}
current.next.prev = previous; //新增的
}
length--;
return current.element;
} else {
return null;
}
};
/书上没写 append
第一种 可以用insert 来弄
this.append = function(element) {
this.insert(length - 1, element)
}
/ 第二种 可以这样?
this.append = function(element) {
let node = new Node(element), //{1}
current; //{2}
if(head == null) {
head = node;
tail = node;
} else {
current = tail;
current.next = node;
node.prev = current;
tail = node;
}
}
}
循环链表
循环链表可以是单向链表, 也可以是双向链表.
特点是 head.prev 是 tail
tail.next 是 head
我们对双向链表稍作改动, 不过我没验证
function CircularLinkedList() {
let Node = function(ele) {
this.element = ele;
this.next = null;
this.prev = null;
}
let length = 0;
let head = null;
let tail = null;
this.insert = function(position, element) {
//检查越界值
if(position >= 0 && position <= length) {
let node = new Node(element),
current = head,
previous,
index = 0;
if(position === 0) { //在第一个位置添加
if(!head) { //新增的 {1}
head = node;
head.prev = tail;
tail = node;
tail.next = head;
} else {
node.next = current;
current.prev = node; //新增的 {2}
head = node;
head.prev = tail;
tail.next = head;
}
} else if(position === length) { //最后一项 //新增的
current = tail; // {3}
current.next = node;
node.prev = current;
tail = node;
tail.next = head;
head.prev = tail;
} else {
while(index++ < position) { //{4}
previous = current;
current = current.next;
}
node.next = current; //{5}
previous.next = node;
current.prev = node; //新增的
node.prev = previous; //新增的
}
length++; //更新列表的长度
return true;
} else {
return false;
}
};
this.removeAt = function(position) {
//检查越界值
if(position > -1 && position < length) {
let current = head,
previous,
index = 0;
//移除第一项
if(position === 0) {
head = current.next; // {1}
//如果只有一项，更新tail //新增的
if(length === 1) { // {2}
tail = null;
} else {
head.prev = tail; // {3}
tail.next = head;
}
} else if(position === length - 1) { //最后一项 //新增的
current = tail; // {4}
tail = current.prev;
tail.next = head;
head.prev = tail;
} else {
while(index++ < position) { // {5}
previous = current;
current = current.next;
}
//将previous与current的下一项链接起来——跳过current
previous.next = current.next; // {6}
current.next.prev = previous; //新增的
}
length--;
return current.element;
} else {
return null;
}
};
this.append = function(element) {
let node = new Node(element), //{1}
current; //{2}
if(head == null) {
head = node;
tail = node;
} else {
current = tail;
current.next = node;
node.prev = current;
tail = node;
tail.next = head;
head.prev = tail;
}
}
...
}
实际上, 双向链表以及 循环链表应该比单向链表起码多弄几个api
比如 返回最后一个元素 getTail
倒数版本
lastIndexOf()
removeAtLast()
...
回头再想?
第六章 集合
image.png
集合基本的实现, 用对象
这是有缺陷的, 值存入对象时, 是通过 值值 为键值对的形式存入的
这就导致不同类型的数据在作为键存入时,会转化为字符串.
比如 1 和 '1' 就会互相覆盖.
并且数据类型为对象的的元素, 基本就无法实现.
可以考虑用 es6 中的Map
function Set () {
var items = {};
this.delete = function (value) {
if (this.has(value)) {
delete items[value]
return true
}
return false
}
this.add = function (value) {
if (!this.has(value)) {
items[value] = value;
return true;
}
return false
}
this.has = function (value) {
return items.hasOwnProperty(value)
}
this.clear = function () {
items = {}
}
this.size = function () {
var len = 0;
for(var value in items) {
if (this.has(value)) {
len++
}
}
return len;
// 或者 return Object.keys(items).length;
}
this.values = function () {
var arr = [];
for(var value in items) {
if (this.has(value)) {
arr.push(value)
}
}
return arr
}
image.png
并集
image.png
this.union = function (aSet) {
var newSet = new Set();
var aSetArr = aSet.values();
for(var i = 0; i < aSetArr.length; i++) {
newSet.add(aSetArr[i])
}
var bSetArr = this.values();
for(var i = 0; i < bSetArr.length; i++) {
newSet.add(bSetArr[i])
}
return newSet;
}
这充分告诉我们一个道理,
如果我一上来就想要实现这个并集操作, 我可能会有点头大,
但我一旦在上面对集合这个概念本身做出了很好的封装之后,
集合的这些操作似乎就变得很简单.
基础概念很重要.基础api 看似简单, 但很重要
所以有时候之所以难是因为基础概念没弄明白,
基础API没有弄好
交集
image.png
this.intersection = function (aSet) {
// 创建新的集合对象
var newSet = new Set();
// 遍历 aSet
var arr = aSet.values();
for(var i = 0; i < arr.length; i++) {
if(this.has(arr[i])) {
newSet.add(arr[i])
}
}
return newSet
}
差集
image.png
this.difference = function (aSet) {
var newSet = new Set();
var arr = this.values();
for(var i = 0; i < arr.length; i++) {
if(!aSet.has(arr[i])) {
newSet.add(arr[i])
}
}
return newSet
}
子集
image.png
子集和上面几个不太一样,
上面几个是运算之后, 想要返回一个集合,
而子集则是想要返回一个判断, 一个布尔值
我刚开始是这么想的
只要有一个集合A中的元素,集合B没有 则A一定不是 B的子集
反之, 如果没有一个元素 是集合B 没有的, 就表示 A 一定就是 B的子集
this.subset = function (aSet) {
var arr = this.values();
for(var i = 0; i < arr.length; i++) {
if(!aSet.has(arr[i])) {
return false
}
}
return true
}
对照书中的之后, 发现有个地方挺不同的
this.subset = function(otherSet) {
if(this.size() > otherSet.size()) { //{1}
return false;
} else {
let values = this.values();
for(let i = 0; i < values.length; i++) { //{2}
if(!otherSet.has(values[i])) { //{3}
return false; //{4}
}
}
return true; //{5}
}
};
行 {1} 没有也可以实现功能.
不过有这一句 能够省很多性能, 省很多计算.
用ES6 原生 Set模拟
基础api 不用封装, 自带了一些api
模拟并集
let union = function(SetA,SetB) {
let newSet = new Set();
for (let x of SetA) { newSet.add(x) }
for (let x of SetB) { newSet.add(x) }
return newSet;
}
模拟交集
let intersection = function(SetA,SetB) {
let newSet = new Set();
for(let x of SetA) {
if (SetB.has(x)) {
newSet.add(x)
}
}
return newSet
}
模拟差集
let difference = function(SetA,SetB) {
let newSet = new Set();
for(let x of SetA) {
if (!SetB.has(x)) {
newSet.add(x)
}
}
return newSet
}
模拟子集判断
let subset = function(SetA, SetB) {
let newSet = new Set();
if (SetA.size > SetB.size) {
return false
}
for(let x of SetA) {
if(!SetB.has(x)) {
return false
}
}
return true
}
文章不能太长?
