数据结构与算法-字典(js实现)

       字典是一种以键 - 值对形式存储数据的数据结构,就像电话号码簿里的名字和电话号码一样。要找一个电话时,先找名字,名字找到了,紧挨着它的电话号码也就找到了。这里的键是指你用来查找的东西,值是查找得到的结果。

       JavaScript 的 Object 类就是以字典的形式设计的。本文将使用 Object 类本身的特性,实现一个 Dictionary 类,让这种字典类型的对象使用起来更加简单。你也可以只使用数组和对象来实现本文展示的方法,但是定义一个 Dictionary 类更方便,也更有意思。比如,使用 () 引用键就比使用 [] 简单。当然,还有其他一些便利,比如可以定义对整体进行操作的方法,举个例子,显示字典中的所有元素,这样就不必在主程序中使用循环去遍历字典了。

字典类的js实现

字典很类似一个关联数组，而js没有提供关联数组这种数据类型，但是我们可以使用对象来很好的模拟，下面我们也将使用字面量对象作为字典类的基础:

function Dictionary() {
  this.datastore = {};//使用单例模式创建数据集合对象
}
//插入一项数据
Dictionary.prototype.add=function(key,value){
  this.datastore[key]=value;
}
//查找某一项
Dictionary.prototype.find=function(key){
  return this.datastore[key];
}
//移除某一项
Dictionary.prototype.remove=function(key){
  delete this.datastore[key];
}
//打印输出所有条目
Dictionary.prototype.showAll=function(){
  for(var key in this.datastore) {
    console.log(key + " -> " + this.datastore[key]);
  }
}
//计算长度
Dictionary.prototype.conut=function(){
  return Object.keys(this.datastore).length;
}
//清空
Dictionary.prototype.clear=function(){
  this.datastore={};
}
//排序(不改变原数据)
Dictionary.prototype.sort=function(){
  var keys=Object.keys(this.datastore).sort();
  var res=new Dictionary;
  for(var i=0;i<keys.length;i++){
    res.add(keys[i],this.datastore[keys[i]]);
  }
  return res;//返回新的字典
}

 测试：

var dic=new Dictionary;
//添加四项数据
dic.add("name","likek");
dic.add("age","18");
dic.add("sex","male");
dic.add("country","china");
//输出
dic.showAll();
/*
name -> likek
age -> 18
sex -> male
country -> china
*/
//查找
dic.find("sex");
"male"
//移除
dic.remove("age");
//长度
dic.conut()；//3
//排序
var dic2=dic.sort();
//排序后的数据
dic2.showAll();
/*
country -> china
name -> likek
sex -> male
*/

 在<<数据结构与算法javascript描述>>一书中写道：“ Dictionay 类的基础是 Array 类,而不是 Object 类。本章稍后将提到,我们想对字典中的键排序,而 JavaScript 中是不能对对象的属性进行排序的 “。我个人认为这句话是错的，我们知道在js中数组也是对象，如果对数组直接添加字符串类型的键的话，那么对此数组之后的一系列操作实际上和对普通的对象操作是没什么两样的，当然，要实现排序的的话，两者也是一样的方法，几乎没有什么区别。另外，此书中对字典的遍历输出以及字典的排序算法的实现等也错的比较离谱。