Data Structures and Algorithms DotNet－ 1、群集

Created at 2016-09-15 Updated at 2018-05-01 Category Data Structures and Algorithms Tag Data Structures and Algorithms / DotNet

数据结构与算法－1、群集

1、群集的定义

群集（Collection），是一种结构化的数据类型，它存储数据并且提供数据向集群中添加、删除和更新操作，以及对集群的不同属性值进行设置与返回的操作。
群集有一套定义好的属性（如Count）和操作（如Add,Insert,Remove,Clear,Contains,IndexOf）。

2、集群的描述

2.1、线性群集

例如数组，数据里面的元素顺次相连，由位置来决定次序。

2.1.1、直接存取群集

2.1.1.1、数组

最常见的就是数组，数组是具有相同数据类型的元素的群集，所有元素可以通过整数索引直接存取访问。
c#中的数组是通过类实现的。
c#中的数组是静态的，初始化后，元素数量是固定的。

数组的数据结构

|0|1|2|3|4|5|

添加

把新元素放置在数组尾部的第一个空位上

插入

需要顺序向后移动一些元素，为新元素腾出空位

删除

如果是尾部元素，直接移除。如果是其它位置的元素，为了保持数组中元素的连续性，需要调整一些数组元素的位置。

ArrayList类

用于简化线性群集操作所提供的数组类。

2.1.1.2、字符串

字符串是自负的群集，可以基于字符的索引对其进行存取。
c#中的字符串是通过类实现的。
c#中字符串是不可变的，一旦初始化，就不能改变它。修改字符串，实际上是创建了一个字符串的副本，可能导致性能下降。

StringBuilder类

处理可变字符串的类。

2.1.1.3、结构

结构是一种复合数据类型，可以拥有不同数据类型的数据。例如一名雇员的纪录，包含姓名，薪水，工号等。
c#中的结构是增强后的版本，可以定义方法，来操作数据，看起来很像是一个类。与类不同的是，结构不能用于继承。
c#中很多元素都是用类来实现的，但是主要的几个基本元素，还是通过结构来实现的，如Int32 。

2.1.2、顺序存储群集

顺序存储群集中的元素是按顺序存储的，这类群集也称为线性表。
它可以动态扩展和收缩。

2.1.2.1、线性表的数据结构

|0| |1| |2| |3| |4| |5|

2.1.2.2、线性表的遍历方法

线性表的元素不支持直接存取访问，而是通过数据项的位置对其进行存取。要访问某个元素，就要遍历线性表，直到达到要找的元素的位置为止。通常线性表允许两种遍历表的方法：

单向从前往后遍历
双向遍历

购物清单就是一个简单的线性表，顺次记录着要购买的商品，一旦找到一个，就把它从清单上划掉。
线性表按顺序存储的元素，既可以是有序元素，也可以是无序元素。

2.1.2.3、限制元素访问的线性表

有些特殊的线性表，会限制访问数据元素。

2.1.2.3.1、栈

元素只能从顶端入栈（push），也只能从顶端出栈（pop），是后进先出的。常用于算术表达式的计算，和平衡符号。

2.1.2.3.2、队列

元素只能在表尾入队，在表头出队，是先进先出的。
有一种特殊的队列叫做优先队列，队列中的元素拥有不同的优先级，允许优先级最高的元素最先出队。例如医院急诊室，会先救护心脏病突发患者，再处理手臂骨折患者。

2.1.2.4、索引群集

2.1.2.4.1、散列表

散列表的数据结构

Reinhard Hsu
101163
5
“IT Dept”

拥有一个键，和与该键相关联的一组数据值。
散列表中有一个特殊函数，叫做散列函数，可以把键，转换成用来检索数据的整数索引。用这个索引，访问与键相关联的数据。
C#中的HashTable类，就是存储散列表的数据的。

2.1.2.4.2、字典

它由一系列键值对构成，就像英文词典一样，单词就是键，单词的定义就是值。虽然键不一定是整数，但是采用了这种索引方案，所以还是将字典称为联合数组。
C#中的几种Dictionary类，就是这类字典。

2.2、非线性群集

例如树，堆，图，和集，群集内的元素没有次序之分。

2.2.1、层次群集

层次群集，是一组划分了层次的数据项集合，位于某一层的数据项，可能会友位于下一较低层上的后继数据项。

2.2.1.1、树

树是一种常见的层次群集。它有一个数据项作为根，其他数据值作为叶子挂在根下面。树的元素叫做节点，某一个节点下面的元素叫做它的子节点。
操作系统的文件系统，是采用树型群集设计，其中一个目录作为根，其他子目录作为根的孩子。

2.2.1.1.1、二叉树

二叉树是树群集的一种特殊类型，树中每个节点最多只有两个孩子。
二叉查找树，又称二叉搜索树，它可以极大提高查找大量数据的效率，它的定义如下：

它或者是一棵空树，或者是具有下列性质的二叉树：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉排序树。

2.2.1.1.2、堆

堆也是树的一种类型，它总是把最小数据值放置在根节点上。我们经常用堆来排序，被称作堆排序。堆的插入和删除操作总是会导致堆的重组。

2.2.2、组群集

无序的数据项，组成的非线性群集，被称为组。主要由三种类型：集合，图，和网络。

2.2.2.1、集合

集合是一种无序数据值的群集，并且集合中每一个数据值都是唯一的。例如，一个班级的学生的列表，就是一个集合的实例。
集合的操作包括联合和交叉。

2.2.2.2、图

图，是由节点集合，以及与节点相连的边集合组成的。
图在物流管理，和作业调度方面广泛应用。“旅行商”问题，就是要求在旅行预算允许的条件下，为商人确定最有效的完整旅行路线，使其走遍要去的所有城市。
如果有10个城市，就要检查10的阶乘条路线，有100座城市，就要检查100的阶乘条路线，只能找到一种近似的解决方案。

2.2.2.3、网络

网络，是一种特殊类型的图，它的每一条边，都被赋予了权。权，代表了从一个节点移动到另一个节点所花费的代价。

3、泛型编程

面向对象编程面临着“代码膨胀”的问题。为了说明方法参数的所有的可能的数据类型，就要覆写某个方法，甚至覆写一套方法集合，这时候就发生了代码膨胀。
代码膨胀的一种解决方案，是使某个值具有多种数据类型，同时仅提供此值的一种定义，这种方法就叫泛型编程。
泛型编程提供数据类型的占位符，在编译时会由特定的数据类型来填充。
比如Swap函数：

void Swap<T>(ref T val1,ref T val2)
{
	T temp;
	temp=val1;
	val1=val2;
	val2=temp;
}

4、DotNet运行环境

DotNet环境中，需要考虑程序运行的线程，和随时都有可能发生的垃圾回收。

4.1、DotNet的垃圾回收机制

C#用堆内存来给引用类型（例如，字符串、数组，类实例对象）分配存储空间。
值类型（例如，普通变量），存储在栈内存区域中。
对引用类型的引用也存储在栈中，但实际的数据则以引用类型的形式存储在堆中。
存储在栈中的值类型变量，在子程序完全执行结束时，就可以释放掉。而存储在堆中的引用类型变量，一直到没有引用堆数据的行为时，才能通过调用资源回收来移除。
在程序执行过程中，资源回收会在任何时候发生。如果你需要强制调用资源回收，可以使用：

GC.Collect();

存储在堆中的每个对象，都有一个finalizer的方法，它是删除对象前执行的最后一步。执行完上面的强制资源回收的代码后，也不能确信对象已经被立即删除了。如果你想等待堆上的所有对象的finalizer方法都执行完毕之后，再做别的事，可以执行下面等待代码：

1 2	GC.Collect(); GC.WaitForPendingFinalizers();

4.2、程序的线程

DotNet环境中，程序是运行在应用程序域中。一个进程里，可以有多个应用程序域，也可以有多个线程。线程可以在多个应用程序域之间穿梭，但同一时刻，只能处于一个应用程序域内。具体可以查看C#综合揭秘——细说进程、应用程序域与上下文之间的关系。

要获取程序消耗的CPU时间，需要确保获取时间的代码只存在于自身程序分配的进程中，而不在操作系统执行的其他任务里。可以使用下面的代码：

Process.GetCurrentProcess().TotalProcessorTime;

这与Stopwatch有什么区别呢？区别是，Stopwatch除了统计程序自身的CPU消耗时间外，还会统计操作系统执行的其它任务所消耗的时间，例如将程序运行结果打印到屏幕的I/O消耗的时间。

5、性能测试

写入1亿个数字

5.1、数组

834.277ms

5.2、ArrayList

13701.914ms

5.3、List

2194.376ms

5.4、总结

可以看出，数组最快，List是数组的2.6倍，ArrayList是数组的16.4倍。