发布个最近自己写的东东,应该有用,虽然还是半成品囧
这个库本来是为了在找工作前复习数据结构用的,写着写着就想着干脆做成库吧,就把常用到的一些结构做了封装,写了一些算法.废话少说,先看看主要有些啥东东:
System.DataStructures
这个命名空间包含了异常类的定义和几个基本的线性表接口定义,可以说是整个库的基础.这里重点介绍下linearcollection<T>接口,几乎所有的线性容器类(包括部分非线性容器)都继承自它并实现了这样两条函数:
void forEach(Predicate<T> Continue);
void forEachRev(Predicate<T> Continue);
forEach:使用正序遍历集合,Continue用于控制是否继续遍历(true继续,false结束)
forEachRev:forEach的反序版(哈希表dictionary没有实现这个方法,因为其内部使用的拉链法用的是单链表无法由尾部开始遍历)
System.DataStructures.List 包含一些线性结构
list<T> 顺序表,
linkedlist<T>双链表
stack<T>栈
queue<T>队列

  这里先说下库的类命名规则.我没有采用常见的头字母大写的命名规则,起初是为了list和linkedlist与.net类库的区分,后面除去工具类外就干脆类名全小写了.类的方法和属性则是头一个词小写剩下的首字母大写.除了基本的线性结构的接口用linea/list开头外,其余的接口一律以abs(抽象)开头,同样是一律的小写.

  先说list<T>,它实现了一个基于数组的顺序表,你可以自定义初始的元素个数和预分配粒度.所谓预分配粒度是指如果需要修改数组大小则新数组的大小必须是这个粒度的整数倍.一个适当的粒度的设置可以平衡减少插入删除操作的性能损失和空间的浪费.另外list<T>所占用的空间目前是只增不减的.暂时不考虑让它在空闲空间过多时缩减数组.

  接下来是linkedlist<T>,这是一个双链表;基本上和.net自带的差不多,但又有些许不同;它实现了和List<T>一样的接口,意味着它也能以元素下标的方式来访问元素,就效率上来说…访问头节点和尾节点的速度是一样的.最慢的是访问位于节点链中间的元素.

  接着是stack<T>和queue<T>;它们和.net的实现就很不一样了,最大的特点是你可以选择其内部实现是基于顺序表还是基于链表甚至于自己实现的其它方法;只要在初始化的时候指定一个listcontainer<T>即可.

System.DataStructures.Hash 哈希表.
  这个命名空间只有一个主要的类即dictionary<key,value>,是基于拉链法的哈希表实现.用法和.net的字典差不多.就不多写了

System.DataStructures.Tree 树
abstreenode<T>
abstree<T>: abstreenode<T>
abstreenodecollection<T>:IEnumerable<abstreenode<T>>
tree<T>

前三个是树这个类的通用接口,后面许多工具函数都用到它们.需要注意的树这个接口/类本身只是一个比较特殊的节点而已.
tree<T>基于兄弟儿子链实现的树.
  另外还有两个没用的类narytree和binarytree,本来是要做成n叉树的,结果暂时用不到写了一半成了半成品丢在那儿,目前基本没任何使用价值.

System.DataStructures.Graph 图
  这里实现了两种图结构,一种是基于邻接矩阵的mgraph,另一种是基于邻接表的graph.两者同样实现了统一的接口便于编写算法.但需要注意的是mgraph每两个顶点间至多只能有一条边.另外基于邻接矩阵的mgraph在边的处理上要比graph快;所以被我用于实现语法检查.

System.DataStructures.Utilities 工具库
这里实现了一些常用的算法和好用的工具:

UMPtrHelper静态类,提供了两条很简单的函数用于访问多维(2d/3d)的非托管指针,它可以把[i,j]或[i,j,k]的下标换算成对应的一维数组下标.在使用BitmapData等需要使用到多维数组指针的时候颇有用.

IntConverter 静态类,提供了两条函数实现整数和字符串间的相互转换,不过它支持任意进
进制.类本身提供了2进制 10进制 8进制 16进制(大小写)的字符集,使用者自身也可以通过提供自己的字符集来使用任何进制(比如自动命名类就使用了一个自定的64进制的字符集,话说这个转换类就是转为了它写的).另外它输出的字串永远是带符号的.即输入-10转成16进制后输出的字符串是-a,而不像系统的函数输入-1输出变成了FFFFFFFF.

TreeHelper 提供了几条函数用于树结构的对拷(同类/不同类).树的先根遍历.
treeviewAdapter 一个适配器,通过它可以把几乎所有针对abstree写的算法应用到TreeView控件的TreeNode上,不过速度比起tree<T>稍慢.treetest中有例子.

ScriptParser 这应该可以算是我这个库的特色了:两个简单的脚本解析(正反向)器.以前做实验的时候需要生成所需的数据;对线性结构还好说;基本一个for就可以搞定.树/图之类的就痛苦了.现在有这两个解析器就轻松多了.比如我要构造一棵树,只需要写一个脚本:
A{
B;
C{
D;
}
E{
F{
G;
}
}
}
通过解析器和Lambda表达式就可以很轻松的生成一棵或多棵对应的树.在我的机器上treetest中载入有457092个节点的脚本(使用节点名直接赋值,使用较慢的treeviewAdapter)耗时在5000毫秒左右.总体速度还算过得去:)

而对于图,则只需要描述它所有的边及其权值:

a<->b;a->c;a<-w1-d;c->d;b<-w2->d;c-w3->e;

即可,如果有孤立无边相连的节点则使用关键字

defVertex x,y,z;

定义.同样结合Lambda表达式就可以很快的构造出一个图结构.节点的命名规则很简单.字母+数字+”_”+”$”, 大小写敏感,无所谓谁开头,允许重复,不限长度.不过在图脚本中要注意不能使用defVertex关键字作为顶点/权名.否则会报语法错误.所有脚本皆使用C++风格的注释.另外两个解析器都使用了mgraph用于语法的检测.可以作为图结构的demo看.

  最后介绍下唯一的一个GUI测试treetest(不修改测试代码直接打开就是它).点击”载入驱动器”会由右边的ComboBox对应的驱动器的文件系统构造成一个tree<T>;再通过适配器使用helper提供的函数复制到TreeNode,最后添加到左边的TreeView中;
单击”载入脚本”则直接使用适配器通过脚本构造相应的TreeNode添加至TreeView中.两个导出脚本使用反向解析器把树解析为脚本保存,区别是一个只解析选定的节点,另一个将解析TreeView中所有的节点.导出有两个选项:

导出使用缩进:选中后将对导出的脚本进行缩进增强可读性,否则导出的将是连续一行的字符.
导出编码:直接使用节点的值作为脚本中对应的节点名,对于无法直接使用的节点值,将被base64编码后转义至合法节点名.debug目录下有一个很大的2.txt文件是由我的C盘构造的脚本,已编码.主要就是测试把节点数据直接编码在脚本中的方法.(注:由于本身很大且又使用了base64解码,再加上TreeView添加大量新节点导致的延迟.所以载入它整个窗体都会有一段时间的假死.)

嗯…有这些东西应该多少会在平时做设计算法之类的活的时候有些帮助了.最后说说库本身的代码问题:

  1. enumerator问题.为了兼容foreach语句我自然实现了迭代器.可是由于开始对于yield return的一些个人的错误臆想导致自己做了许多无用功,其直接结果就是出现了不少专门写的enumerator类囧.总之就是修改成yield return要改动不少(enumerator往往意味着较高的耦合),而且这些enumerator本身也还没发现有啥问题工作良好;就这么放着吧.