读【数据结构与算法】之字典
字典是一种以键-值形式存储数据的数据结构。
在JS中Object类就是以字典的形式设计的。所以在JS中实现字典是很容易的，且能够基于对象（非Object类）来封装出来字典。
字典类的基础是Array类，而不是Object类，但由于Array也是对象，所以上边所说基于对象是没错的。为什么是Array而不是Object呢，因为有好多场景需要有一个可以排序的字典，而在JS中是不能对对象的属性排序的。
基础实现：
/**
* Class Dictionary
* 字典 Dictionary
*/
function Dictionary() {
this._data = []; // 用于存储数据的数组
}
Dictionary.prototype = {
constructor: Dictionary,
/**
* 添加项
* @param {String} key 添加项的键
* @param {Any} value 添加项的值
* @return {Undefined} undefined
*/
add: function add(key, value) {
this._data[key] = value;
},
/**
* 查找键的值
* @param {String} key 键
* @return {Any} 值
*/
find: function find(key) {
return this._data[key];
},
/**
* 删除给定键的项
* @param {String} key 键
* @return {Boolean} 是否删除成功
*/
remove: function remove(key) {
return delete this._data[key];
},
/**
* 得到所有键值
* @return {Array} 结果数组
*/
showAll: function showAll() {
var ret = [];
for (var key in this._data) {
if (this._data.hasOwnProperty(key)) {
ret.push(key + ' -> ' + this._data[key]);
}
}
return ret;
},
/**
* 所有项个数
* @return {Number} 个数值
*/
count: function count() {
if (Object.keys) return Object.keys(this._data).length;
var n = 0;
for (var key in this._data) {
if (this._data.hasOwnProperty(key)) {
n++;
}
}
return n;
},
/**
* 清空字典
* @return {Undefined} undefined
*/
clear: function clear() {
for (var key in this._data) {
if (this._data.hasOwnProperty(key)) {
delete this._data[key];
}
}
}
};
现在额外的增加对字典的排序功能。在JS中数组是可以排序的，那对于字典中按键排序输入结果的实现也是基于数组的排序的。
简单来说就是利用字典中所有的key，排序之后输入就好。
function showAll(sorted) {
var ret = [], key, keys = [];
if (sorted) {
for (key in this._data) {
if (this._data.hasOwnProperty(key)) {
keys.push(key);
}
}
keys = keys.sort();
for (var i = 0, len = keys.length; i < len; i++) {
ret.push(keys[i] + ' -> ' + this._data[keys[i]]);
}
return ret;
}
for (key in this._data) {
if (this._data.hasOwnProperty(key)) {
ret.push(key + ' -> ' + this._data[key]);
}
}
return ret;
}
具体运行例子请看demojs实现字典