浏览 5811 次
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (0)
|
|
---|---|
作者 | 正文 |
发表时间:2007-04-27
《Introduction to Algorithms, Second Edition 》 看了一段时间,对里面的提到的几种字典数据结构算法很感兴趣,因此照着书上的描述做了一些实现。使用 C++ 实现了:BinarySearchTree, RedBlackTree, BalancedTree, SkipList, SortedArray 。
对着 MIT 的 源代码下载: http://spdict.googlecode.com/files/spdict-0.2.src.tar.gz http://code.google.com/p/spdict/downloads/list 只实现了字典的 3 个基本操作:search,insert,remove 。 class SP_Dictionary { public: virtual ~SP_Dictionary(); virtual int insert( void * item ) = 0; virtual const void * search( const void * key ) const = 0; virtual void * remove( const void * key ) = 0; virtual int getCount() const = 0; virtual SP_DictIterator * getIterator() const = 0; }; 另外还针对各种字典数据结构实现了 iterator 。 class SP_DictIterator { public: virtual ~SP_DictIterator(); virtual const void * getNext( int * level = 0 ) = 0; }; 在 version 0.2 中基于 SP_Dictionary 接口实现了一个 cache 类。 class SP_Cache { public: virtual ~SP_Cache(); virtual int put( void * item, time_t expTime = 0 ) = 0; virtual int get( const void * key, void * resultHolder ) = 0; virtual int erase( const void * key ) = 0; virtual void * remove( const void * key, time_t * expTime = 0 ) = 0; virtual SP_CacheStatistics * getStatistics() = 0; }; 程序包里面有一个测试程序,采用随机生成测试数据的方法,对各种不同的字典数据结构进行测试,可以方便地对比不同算法各种操作的性能。命令行的使用方法如下: bash-2.05a$ ./testdict -v ./testdict [-t type] [-c count] -t type : bst ( brinary search tree ) rb ( red-black tree ) bt ( balanced tree ) sl ( skip list ) sa ( sorted array ) -c count, test how many items 程序在 linux 下开发,在 solaris 和 windows 平台也进行过测试。 linux/solaris 使用 Makefile 进行构建,windows 有相关的 vc++ 的工程文件。 声明:ITeye文章版权属于作者,受法律保护。没有作者书面许可不得转载。
推荐链接
|
|
返回顶楼 | |