Welcome
欢迎访问Liber的博客，这是最新的一篇技术文章。
数据结构：数组和链表
新建一个html文件，body里面含有两个div，一个div里含有字符串4,2,5,7,1,3, 一个div为空。同时建立一个按钮叫pop，一个按钮叫push，push按钮旁边再建立一个text input。
实现以下效果:
(1) 空的div里 显示 将第一个div里数字排序后的结果
(2) 点击pop后第一个div里的最后一个数字消失，同时更新排序结果
(3) 在text input里输入一个数字，点击push按钮后将新的数字添加到第一个div数字字符串的结尾，同时更新排序结果
api-solution.js:
/*
#### 使用ECMAScript提供的sort API实现
#### 思路：
- 使用两个数组分别存放未排序的数组以及排好序的数组：original, sorted
- 每次pop操作，调用original的pop方法，然后复制original对其调用sort方法，得到新的sorted数组
- 同样的方式处理push操作
#### 缺点：
api-solution的主要问题在于，每次入栈出栈都要执行sort
而sort(v8的实现是优化过的快排)的时间复杂度平均为O(nlogn)
#### 优化方案：
请参见optimized-solution.js
*/
var utils = {
compare: function (value1, value2) {
return value1 - value2;
},
sort: function (arr) {
return arr.concat().sort(this.compare);
}
};
var app = {
original: [],
sorted: [],
initialize: function () {
this.initOriginal();
this.initSorted();
this.render();
this.subscribe();
},
initOriginal: function () {
var stringArr = document.querySelector('#original').innerHTML.split(',');
this.original = stringArr.map(function (item) {
return parseInt(item, 10);
});
},
initSorted: function () {
this.sorted = utils.sort(this.original);
},
subscribe: function () {
document.querySelector('#pop').addEventListener('click', (function () {
this.original.pop();
this.sorted = utils.sort(this.original);
this.render();
}).bind(this));
document.querySelector('#push').addEventListener('click', (function () {
var input = document.querySelector('input');
var number = parseInt(input.value, 10);
if (!isNaN(number)) {
this.original.push(number);
this.sorted = utils.sort(this.original);
}
input.value = '';
this.render();
}).bind(this));
},
render: function () {
document.querySelector('#original').innerHTML = this.original.join(',');
document.querySelector('#sorted').innerHTML = this.sorted.join(',');
}
};
app.initialize();
optimized-solution.js:
/*
#### 思路：
- 利用Hash找到pop元素的位置 - O(1)
- 利用链表根据找到的位置进行删除 - O(1)
- 利用链表遍历hash在相应位置进行插入 - O(logn)
#### 具体实现：
- 初始化两个数组original, sorted
- 初始化一个哈希linkListHash，其key随机生成，其值为对象，存放original的值，对象之间实现成一个双向链表
- 初始化一个数组originalList，每一项的值是一个对象，存放original对应的值和该值在linkListHash中对应的key
- 对originalList进行pop出栈，根据出栈元素的key找到linkListHash中对应的属性，在链表中删除出栈元素，最后删除该属性
- 对originalList进行push入栈，遍历链表，找到相应的位置插入入栈元素，为linkListHash添加新key及其值
*/
var utils = {
compare: function (value1, value2) {
return value1 - value2;
},
sort: function (arr) {
return arr.concat().sort(this.compare);
},
findKey: function (hash, data) {
for (var key in hash) {
if (hash[key].data === data) {
return key;
}
}
}
};
var app = {
original: [],
sorted: [],
linkListHash: {},
originalList: [],
head: null,
initialize: function () {
this.initOriginal();
this.initSorted();
this.initLinkListHash();
this.initOriginalList();
this.render();
this.subscribe();
},
initOriginal: function () {
var stringArr = document.querySelector('#original').innerHTML.split(',');
this.original = stringArr.map(function (item) {
return parseInt(item, 10);
});
},
initSorted: function () {
this.sorted = utils.sort(this.original);
},
initLinkListHash: function () {
var head = null;
var linkListHash = {};
var lastNode = null;
for (var i = 0; i < this.sorted.length; i++) {
var obj = {
data: this.sorted[i],
prev: lastNode
};
if (!lastNode) {
head = obj;
} else {
lastNode.next = obj;
}
linkListHash[Math.random()] = obj;
lastNode = obj;
}
this.head = head;
this.linkListHash = linkListHash;
},
initOriginalList: function () {
var originalList = [];
for (var i = 0; i < this.original.length; i++) {
var obj = {
data: this.original[i],
key: utils.findKey(this.linkListHash, this.original[i])
};
originalList.push(obj);
}
this.originalList = originalList;
},
subscribe: function () {
document.querySelector('#pop').addEventListener('click', (function () {
this.original.pop();
this.popHash();
this.render();
}).bind(this));
document.querySelector('#push').addEventListener('click', (function () {
var input = document.querySelector('input');
var number = parseInt(input.value, 10);
if (!isNaN(number)) {
this.original.push(number);
this.pushHash(number);
}
input.value = '';
this.render();
}).bind(this));
},
popHash: function () {
if (this.originalList.length === 0) {
return;
}
var key = (this.originalList.pop()).key;
var targetObj = this.linkListHash[key];
if (!targetObj.next && !targetObj.prev) {
this.head = null;
} else if (!targetObj.prev) {
this.head = targetObj.next;
targetObj.next.prev = null;
} else if (targetObj.next) {
targetObj.prev.next = targetObj.next;
targetObj.next.prev = targetObj.prev;
} else {
targetObj.prev.next = null;
targetObj.prev = null;
}
delete this.linkListHash[key];
},
pushHash: function (data) {
var key = Math.random();
this.originalList.push({data: data, key: key});
var newObj = {
data: data,
key: key,
next: null,
prev: null
};
var node = this.head;
if (!node) {
this.head = newObj;
} else {
while (node) {
if (data < node.data) {
if (!node.prev) {
newObj.next = node;
node.prev = newObj;
this.head = newObj;
} else {
node.prev.next = newObj;
newObj.prev = node.prev;
newObj.next = node;
node.prev = newObj;
}
break;
} else if (!node.next) {
node.next = newObj;
newObj.prev = node;
break;
}
node = node.next;
}
}
this.linkListHash[key] = newObj;
},
renderOriginal: function () {
document.querySelector('#original').innerHTML = this.original.join(',');
},
renderSorted: function () {
var arr = [];
var node = this.head;
while (node) {
arr.push(node.data);
node = node.next;
}
document.querySelector('#sorted').innerHTML = arr.join(',');
},
render: function () {
this.renderOriginal();
this.renderSorted();
}
};
app.initialize();