这个库本来是为了在找工作前复习数据结构用的,写着写着就想着干脆做成库吧,就把常用到的一些结构做了封装,写了一些算法.废话少说,先看看主要有些啥东东:
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本身也还没发现有啥问题工作良好;就这么放着吧. 2. 类耦合问题.从总体架构上来说耦合应该不算高,即时在没有除去那些糟糕的测试代码的情况下VS的可维护性测评给我打了87的不算低的分.但在容器及其对应的节点类以及集合间的耦合程度还是很高的.比如tree和treenode,它们之间经常会跨类直接访问到甚至直接修改对方的内部成员.不过都是为了让外部表现得更像.net的风格:). 3. 代码有些混乱的问题,因为大量的使用了泛型,泛型约束和Lambda表达式.而且有些泛型可能看起来还有些奇怪.所以代码可能一眼看上去觉得有些有些混乱.特别解析器部分的代码...这个没办法,这是我写的第三个成型的状态机,总体还不成熟囧,刚开始还请教清洁工用正则做预处理去除注释来着.结果后来发现不可行(或许有其它用正则的办法?不过我是正则白痴囧...实在找不出使用正则的同时通过某些畸形却又合法的注释的办法),只好老老实实的扫描了一遍文本:(.另外估计还会有刚开始接触编程的菜鸟对我构造语法图用的那堆二维int数组的出处感到不解.那是根据我画的图构造的邻接矩阵.图我拍了下来一块儿打包了:). 4. VS工程的问题;为了方便测试.整个工程我做成了命令行exe.不过稍加修改去除那堆乱七八糟的测试代码就能编译成库来用. 嗯.先写这么多了,这个库基本从基础的数组开始构筑,中途没使用任何.net提供的现成类或算法.应该也能给刚学数据结构的菜鸟做下参考.最后..因为总体代码比较凌乱,只完成了60%左右,且测试不足.估计bug不少,尚不知能否实用.不过用来测试和设计一些算法应该不成问题.未来可能准备添加二叉树,二叉堆,一些用于和.net类库互操作的适配器(类似treeviewAdapter的东东)以及一些常用的树图算法(搜索,排序,最短路径,拓补排序啥的).希望这东西能对大家多少有点用:)下载地址
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本身也还没发现有啥问题工作良好;就这么放着吧. 2. 类耦合问题.从总体架构上来说耦合应该不算高,即时在没有除去那些糟糕的测试代码的情况下VS的可维护性测评给我打了87的不算低的分.但在容器及其对应的节点类以及集合间的耦合程度还是很高的.比如tree和treenode,它们之间经常会跨类直接访问到甚至直接修改对方的内部成员.不过都是为了让外部表现得更像.net的风格:). 3. 代码有些混乱的问题,因为大量的使用了泛型,泛型约束和Lambda表达式.而且有些泛型可能看起来还有些奇怪.所以代码可能一眼看上去觉得有些有些混乱.特别解析器部分的代码...这个没办法,这是我写的第三个成型的状态机,总体还不成熟囧,刚开始还请教清洁工用正则做预处理去除注释来着.结果后来发现不可行(或许有其它用正则的办法?不过我是正则白痴囧...实在找不出使用正则的同时通过某些畸形却又合法的注释的办法),只好老老实实的扫描了一遍文本:(.另外估计还会有刚开始接触编程的菜鸟对我构造语法图用的那堆二维int数组的出处感到不解.那是根据我画的图构造的邻接矩阵.图我拍了下来一块儿打包了:). 4. VS工程的问题;为了方便测试.整个工程我做成了命令行exe.不过稍加修改去除那堆乱七八糟的测试代码就能编译成库来用. 嗯.先写这么多了,这个库基本从基础的数组开始构筑,中途没使用任何.net提供的现成类或算法.应该也能给刚学数据结构的菜鸟做下参考.最后..因为总体代码比较凌乱,只完成了60%左右,且测试不足.估计bug不少,尚不知能否实用.不过用来测试和设计一些算法应该不成问题.未来可能准备添加二叉树,二叉堆,一些用于和.net类库互操作的适配器(类似treeviewAdapter的东东)以及一些常用的树图算法(搜索,排序,最短路径,拓补排序啥的).希望这东西能对大家多少有点用:)下载地址
瞅瞅
>--------------我要赚好多的分，给我的小弟弟买糖吃!--------------<
scriptParser_tree.cs
脚本解析器公用函数
removeComment第一行.
有个StringReaderEx sreaderex = new StringReaderEx(script);
是多余的.估计是修改算法的时候忘了删了@_@.
------------------------------------
怎么可能呢?C#和Net上的其它语言是没有自已的类的
2.部分的确是重复开发了(线性表部分).不然达不到锻炼的效果
3.多核并行要考虑的东西太多了,而且很灵活并不适合把算法写死.我认为要并行的话自己按需求自己lock同步比较好你可能搞错那个脚本的用途了...那是为了方便手工录入试验数据.数据库当然可以用于存储那些数据.如果只是因为测试算法需要这样一棵树:
A{
B{
C;
}
D;
}
对应数据表:
0 A -1
1 B 0
2 C 1
3 D 0
你觉得哪个更直观更便于录入呢?这个脚本只是提供一个便捷的录入工具和小规模数据量情况下的一个存储方案而已,我那个C盘的457092个节点的文件系统属于极端情况;纯粹是为了测试解析器的性能.速度且不说,一般谁会把几十万个节点全载入内存处理?总得考虑内存耗用的情况吧?数据库当然可以用来存储这些数据,但生成树/图就需要你自己编写对应的算法了.至于数据绑定...我还真没听说哪个基本结构类库和数据库绑定的...记住这不是UI库.
有本书不错.建议你去读一下这一章"纯文本的威力"就知道我做这个解析器的目的了.