JS中的算法与数据结构之字典(Dictionary)实例详解

前端  /  管理员 发布于 4年前   540

本文实例讲述了JS中的算法与数据结构之字典(Dictionary)。分享给大家供大家参考，具体如下：

字典(Dictionary)

字典(Dictionary)是一种以 键-值对 形式存储数据的数据结构 ，就如同我们平时查看通讯录一样，要找一个电话，首先先找到该号码的机主名字，名字找到了，紧接着电话号码也就有了。这里的键就是你用来查找的东西，本例中指代的就是名字，值就是查找得到的结果，也就是对应的电话号码。

其实，JavaScript 中的 Object 类就是以字典的形式设计的，下面我们将会借助 Object 类的特性，自主实现一个 Dictionary 类，让这种字典类型的对象使用起来更加方便。

字典的实现

字典（Dictionary）类的基础是 Array 类。

同之前的我们所看到的数据结构一样，字典类也应该有添加、删除、清空等操作，于是我们可以先定义一个字典类的基础数据类型，如下图。

 
数据类型定义

有了上述的数据类型定义，我们 Dictionary 类构造函数定义也就迎刃而解了

//字典类function Dictionary () {  this.dataStore = [];  this.add = add;     // 添加元素  this.find = find;    // 查找元素  this.remove = remove;  // 删除元素  this.count = count;   // 字典中元素个数  this.showAll = showAll; // 显示字典元素  this.clear = clear;   // 清空字典}

add：向字典添加一个元素

上面我们也提到，字典是以 键值对 的方式存储数据的，因此，add 方法就需要接受两个参数，分别是 键和值 ，其中键表示其在字典中的索引，实现如下

//向字典添加元素function add( key , value ){  this.dataStore[key] = value;}

没错，就是这么简单！接着我们来看看 find 方法

find：查找字典中的元素

我们是以键值对方式存储的，因此我们只需要传入需要查找的键，就可以顺理成章的取到对应的值，这对应于JS中的数组也是十分简单的；

//查找字典中的元素function find( key ){  return this.dataStore[key];}

有了添加和查找，接下来就是删除了！

remove：删除字典中的一个元素

要想删除字典中的一个元素，即删除一个 键值对 ， 我们需要借助 JS 提供的一个内置的函数 ： delete ，这个函数我们并不陌生，它可以同时删除键和与其对应的值，那么 remove 方法定义就很简单了

//删除一个元素function remove( key ){  if( this.dataStore[key] ) delete this.dataStore[key];  else return 'Not Found';}

除此之外，我们还想显示字典中的所有键值对，showAll 方法来完成。

showAll：显示字典中所以键值对

//显示字典元素function showAll () {  for( var key in this.dataStore ){    console.log( key + '->' + this.dataStore[key] );  }}

我们已经完成了字典的基本操作，现在我们做个小测试，

//实例化字典类var directory = new Dictionary();//添加元素directory.add( 'Jack' , '138****5505' );directory.add( 'Alice' , '156****6606');directory.add( 'Tom' , '180****8808');//显示字典directory.showAll();     // Jack->138****5505               // Alice->156****6606               // Tom->180****8808            directory.remove( 'Tom' );directory.showAll();     // Jack->138****5505               // Alice->156****6606

我们定义的时候看到了还有两个方法没有实现呢，一个是 count ， 另一个是 clear ，下面我们一起来实现。

count：查看字典中元素的个数

该方法有时候会很有用，不过实现起来可能会跟你想的不太一样，我们先看看如何实现的

//查看字典中元素的个数function count(){  var n = 0 ;  for ( var key in this.dataStore ){    ++n;  }  return n;}

怎么样，是不是跟想的不太一样，为什么不用 length 属性，不是很简单么？其实不然，我们的键为字符串的时候，数组的 length 属性就不起作用了，请看下面的例子：

var nums = [ 0 , 1 , 2 ] ;console.log(nums.length)    // 3var directory = [];directory['Jack'] = '138****5505';directory['Alice'] = '156****6606';directory['Tom'] = '180****8808';console.log(directory.length)  // 0

现在是不是又了解了一个坑！哈哈，我们把最后一个clear方法实现一下。

clear：清空字典

//清空字典function clear(){  for( var key in this.dataStore ){    delete this.dataStore[key];  }}

至此，字典的功能已基本完成了，我们利用上述的代码继续走下去，测试测试

console.log(directory.count());   // 2directory.clear();console.log(directory.count());   // 0

字典中我们通常都是用键来取值，所以我们无须关心s数据在字典中的实际存储顺序，但我们希望能看到显示字典内容的时候是有序的，这也很简单，我们只需稍微改造一下我们的 showAll 方法即可。

//改造后的showAllfunction showAll(){  var sortKeys = Object.keys(this.dataStore).sort();  for( var key in sortKeys ){    console.log( sortKeys[key] + '->' + this.dataStore[sortKeys[key]] );  }}

和我们之前的方法唯一的区别就是，我们拿到了键之后，对其进行了一次 sort 排序，下面我们看看新方法的输出。

// 重新打印上述字典directory.showAll();    // Alice->156****6606              // Jack->138****5505              // Tom->180****8808

要注意的是，上述 showAll 方法中，进行 Object.keys().sort()排序后，返回的是新的一个数组，类似下面的形式，

//sortKeys["Alice", "Jack", "Tom"]

此时，数组的 key 是 0、1、2，这样是不是就清晰很多了呢？

至此，我们已基本了解了字典的一些内容，并且我们可以用JS自己去实现一个字典了，有木有很棒！接下来，大家加油~

感兴趣的朋友可以使用在线HTML/CSS/JavaScript代码运行工具：http://tools..net.cn/code/HtmlJsRun测试上述代码运行效果。

更多关于JavaScript相关内容可查看本站专题：《JavaScript数学运算用法总结》、《JavaScript数据结构与算法技巧总结》、《JavaScript数组操作技巧总结》、《JavaScript排序算法总结》、《JavaScript遍历算法与技巧总结》、《JavaScript查找算法技巧总结》及《JavaScript错误与调试技巧总结》

希望本文所述对大家JavaScript程序设计有所帮助。

您可能感兴趣的文章:

• js canvas实现画图、滤镜效果
• 纯JavaScript实现HTML5 Canvas六种特效滤镜示例
• js模拟滤镜的图片渐显效果
• tweenjs缓动算法的使用实例分析
• JS中的算法与数据结构之集合(Set)实例详解
• JS中的算法与数据结构之列表(List)实例详解
• JS实现的排列组合算法示例
• nodejs中各种加密算法的实现详解
• JavaScript多种滤镜算法实现代码实例