大家好,我是苏州程序大白,今天跟大家讲讲C#中数据结构体与算法。内容有点多。我这里会持续更新,希望大家关注我、支持我,谢谢大家。不废话了下面我们开始
(注:群集指Collection) 本文章介绍如何使用C#开发和实现数据结构和算法, 期间用到的数据结构在. NETFramework库的System. Collections中. 在本章首先将讨论如何使用数组实现自制的群集类, 然后学习. NETFramework的群集类, 最终帮助我们理解群集的概念. 泛型是C#2. 0的一个重要补充. 泛型允许C#程序员不必因不同的数据类型而多次重载函数. C#2. 0提供了一个特殊的库, System. Collections. Generic, 它为一些System. Collections中的数据结构提供泛型支持. 本章将向读者介绍泛型编程. 本章最后, 介绍了一个自定义的类, Timing类, 我们将在几章中使用它来衡量数据结构或算法的性能. 它将取代大O分析, 这不是因为大O分析不重要, 而是因为这本书对数据结构和算法的研究采取了更偏向实践的方法。
群集是一种结构化的数据类型, 用于保存和操作数据, 能够完成数据的添加, 删除, 与修改, 并能赋值和读取群集的各种设置属性。 群集可以分为两种类型:线性和非线性. 线性群集指, 群集中的元素顺序排列, 彼此之间具有前后关系. 线性群集中的元素通常按照位置排序. 现实中, 货物清单就是线性群集的一个例子;在计算机世界中, Array被设计为线性群集。 非线性群集中的元素彼此之间没有位置关系. 组织结构图是非线性群集的一个例子, 就像金字塔的形状那样. 在计算机世界中, tree, heap, graph和set都是非线性群集。 无论是哪一种群集, 都有属性定义, 描述它们本身和可以对它们进行的操作. 比如Count属性, 它表示群集中元素的数量. 对群集的操作, 称之为方法, 比如用于添加元素的Add方法, 用于移除指定元素的Remove方法, 用于移除所有元素的Clear方法, 用于检查某个元素是否存在于群集中的Contains方法, 以及用于检查指定元素在群集中索引的IndexOf方法等。
两个主要群集类型还有一些子类别. 线性群集既可以是直接访问的也可以是顺序访问的;非线性群集既可以是分组的也可以是分级的, 本节对它们都会进行介绍.
可直接访问群集的代表是Array, Array中元素的数据类型相同, 并可以通过整数索引直接访问, 如下图:
Array的可以是静态的, 表示在声明Array时指定的元素总数在程序中固定不变;或者Array也可以是动态的, 动态Array的元素数量可以通过ReDim或ReDimPreserve语句增加. 在C#中, Array不是一种基本数据类型, 而是类. 本节后面探究Array更多的细节时, 会讨论Array是如何作为类使用的。 我们可以使用Array存储线性群集. 简单的向第一个或最后一个空位放置就可以为Array增加元素. 而向Array中间插入元素则不太容易和有效率, 因为我们需要将插入位置后面的所有元素向后移动, 以便为新元素让出空位. 同样的原因, 在首位或末尾移除Array元素并不难, 而在中间移除元素则不太容易并效率低下. 根本原因是我们对Array做的任何操作都需要保持元素之间的连续性, 关于这部分的细节将在本节后面讨论. . NETFramework提供了专门的ArrayList类来使线性群集的编程更加容易, 第三章将探讨这部分内容 另一种可以直接访问的群集类型是string, 它是字符串的群集, 也可以通过索引访问每个元素. string在C#中也以类的形式实现, 该类提供了一大批用于对字符串操作的方法, 如连接字符串, 返回子字符串, 插入字符, 移除字符等, 会在后面详细介绍 C#的字符串是不可变的, 初始化后不能改变, 修改字符串时, 实际将创建字符串的副本, 而不是修改原始的字符串. 这种机制在一些情况下会降低程序运行的性能, 因此. NETFramework提供了StringBuilder类来提供使用可变字符串的途径. 这部分内容也放在了后面详细介绍 最后一种可直接方法的群集类型是Struct, 它是一种包含许多不同数据类型的复合数据类型. 比如, 一名员工的信息包括姓名(字符串), 工资(数字), 身份证号(数字或字符串)等等. 由于这些数据分散的存储在单独的变量中不方便管理, 因此编程语言提供了Struct用于存储这种情况的数据组合 C#中Struct的一个强大之处是, 在其内部可以定义方法, 这使它表现的像是类不过它并不能继承或派生新类型:
using System;
public struct Name {
private string fname, mname, lname;
public Name(string first, string middle, string last) {
fname = first;
mname = middle;
lname = last;
}
public string firstName {
get {return fname;}
set {fname = firstName;}
}
public string middleName {
get {return mname;}
set {mname = middleName;}
}
public string lastName {
get {return lname;}
set {lname = lastName;}
}
public override string ToString() {
return (String.Format("{0} {1} {2}", fname, mname,lname));
}
public string Initials() {
return (String.Format("{0}{1}{2}",fname.Substring(0,1), mname.Substring(0,1), lname.Substring(0,1)));
}
}
public class NameTest {
static void Main() {
Name myName = new Name("Michael", "Mason", "McMillan");
string fullName, inits;
fullName = myName.ToString();
inits = myName.Initials();
Console.WriteLine("My name is {0}.", fullName);
Console.WriteLine("My initials are {0}.", inits);}
}
. NET环境下的许多内容都被实现为了类, 但有几种基本类型是使用Struct实现的, 比如说整数类型Int32就是一种Struct类型, 该Struct类型提供的方法之一Parse方法, 可以将代表数字的字符串转类型换为整数类型:
using System;
public class IntStruct {
static void Main() {
int num;
string snum;
Console.Write("Enter a number: ");
snum = Console.ReadLine();
num = Int32.Parse(snum);
Console.WriteLine(num);
}
}
按顺序访问的群集 可顺序访问的群集就是一种按照顺序存储元素的列表, 所以叫这种群集为线性表. 线性表创建时并不需要限制其大小, 也就是说它可以动态的扩展或收缩. 线性表中的项不能被直接访问, 它们由在列表中的位置引用, 第一个元素在头, 最后一个元素在尾, 如下图:
由于不能直接存取线性表的元素, 为了访问某个元素就需要遍历线性表直到到达要找元素的 位置为止. 线性表的实现通常允许两种遍历表的方法:一种是单向从前往后遍历, 而另一种 则是双向遍历, 即从前向后和从后向前遍历。 线性表的一个简单实例就是购物清单. 顺次写下要购买的全部商品就会形成一张购物清单. 在购物时一旦找到某种商品就把它从清单中划掉。 线性表可以是有序的, 也可以是无序的. 有序列表的顺序具有特定的含义, 比如下列称谓: 少林寺驻武当山办事处大神父王喇嘛 而无序线性表则是由无序元素组成的. 在第2章对二叉查找算法与简单线性查找算法进行 讨论时就会发现线性表的顺序会在查找表中数据时产生很大的差异. 线性表的某些类型限制访问数据元素. 这类线性表有堆栈(Stack)和队列. 堆栈是一种只允许在表头 (或顶端)存取数据的表. 在表的顶端放置数据项, 而且也只能从表的顶端移出数据项. 正是基于这种原因, 堆栈也被称为后进先出结构. 这里把向堆栈添加数据项的操作称为入堆栈(push), 而把从堆栈移出数据项的操作称为出堆栈(pop). 如图展示了堆栈的这两种操作。
堆栈是非常常见的一种数据结构, 特别是在计算机系统编程中尤为普遍. 在堆栈的众多应用 中, 它常用于算术表达式的计算和平衡符号. 队列是一种只允许在表尾进行数据项添加和只能在表头进行移出操作的表. 它也被称为是先进先出结构. 这 里把向队列添加数据项称为入队(EnQueue), 而把从队列移出数据项称为离队(DeQueue). 如图展示了队列的这两种操作。
队列既可用于调度操作系统任务的系统编程, 也可用于模拟研究的编程. 在每一种能想象到的少量情况下, 队列都可以为模拟等待队列产生极好的结构. 优先队列是队列的一种特殊类 型. 它允许具有最高优先级的数据项被最先移出队列. 例如, 优先队列可以用来研究医院急 诊室的操作, 这里应该对心脏病突发患者先进行救护, 然后再处理手臂骨折患者. 最后要讨论的一类线性群集被称为通用的索引群集. 这类群集的第一种就是哈希表. 它存储 了一组与关键字相关联的数据值. 在哈希表中有一个被称为哈希函数的特殊函数. 此函数会 取走一个数据值, 并且把此数据值(称为关键字)转换成用来取回数据的整数索引. 然后此 索引会用来存取访问与关键字相关联的数据记录. 例如, 一条雇员记录可能由雇员姓名、薪 水、工作年限以及所工作的部门组成. 此结构如图所示. 此数据记录的关键字就是雇员 的姓名. C#有一个称为HashTable的类用来存储哈希表的数据. 会在后面文章讨论此结构。
另外一种通用的索引群集就是字典. 它是由一系列键值对构成的. 此结 构与词典书籍类似, 词典中的词是关键字, 而词的定义则是与关键字相关联的值. 关键字就是与 其相关联的值内的索引. 虽然索引不需要就是整数, 但是由于上述这种索引方案, 所以还是 常把字典称为关联数组. 后面文章会对. NET框架内容的几种字典类进行讨论。
非线性群集分为两大主要类型:层次群集和组群集. 层次群集是一组划分了层次的数据项集 合. 位于某一层的数据项可能会有位于下一较低层上的后继数据项. 树是一种常见的层次群集. 树群集看上去像是一棵倒立的树, 其中一个数据项作为根, 而其 他数据值则作为叶子挂在根的下面. 树的元素被称为节点, 而且在特定节点下面的元素被称 为是此节点的孩子. 如图展示了一棵实例树.
树在几种不同的领域都有应用. 大多数现代操作系统的文件系统都是采用树群集设计而成 的, 其中一个目录作为根, 而其他子目录则作为根的孩子们. 二叉树是树群集的一种特殊类型, 树中每个节点最多只有两个孩子. 二叉树可以变成二叉查 找树, 这样做可以极大地提高查找大量数据的效率. 实现的方法是依据从根到要存储数据的 节点的路径为最短路径的方式来放置节点. 还有一种树类型就是堆. 堆始终把最小数据值放置在根节点上. 在删 除时会移除根节点. 此外, 堆的插入和删除操作总是会导致堆的重组, 因为只有这样才能把 最小值放在根节点上. 我们经常会用堆来排序, 这被称为是堆排序. 通过反复删除根节点以及重组堆的方式就可以对存储在堆内的数据元素进行排序. 后面文章将对几种不同类型的树进行讨论.
数据项为无序的非线性群集被称为组. 集合set、图graph和网络network是组群集的三种主要类型. 集合是一种无序数据值的群集, 并且集合中每一个数据值都是唯一的. 就像整数一样, 班级中学生的列表就是一个集合的实例. 在集合上执行的操作包括联合和交叉. 如图显示 了集合操作的实例. ![在这里插入图片描述](https://img-blog.csdnimg.cn/20210428112848971.png
图是由节点集合以及与节点相连的边集合组成的. 图用来对必须访问图中每个节点的情况进行建模, 而且有些时候还要按照特定顺序进行访问. 这样做的目的是为了找到“遍历”图的 最有效的方法. 图可用于物流及工作的调度, 也可用于计算机科学和数学研究领域. 大家可能听说过“旅行商”问题. 这就是图问题的一种特殊类型. 此问题要求在旅行预算允许的条件下为需要拜访路线 中所有城市的商人确定最有效的完整旅行路线. 此问题的实例图表示在图中.
此问题是被称为NP-完备问题的其中一部分内容. 这就意味着针对此类型的大量问题是无 法知道确切解决方案的. 例如, 为了找到图上所示问题的解决方案, 需要检查10的阶乘 这么多条线路, 这等于是3628800条线路. 如果把问题扩展为100座城市, 就需要检查 100的阶乘条线路. 就目前方法而言是无法用现在方法实现的. 因此需要找到一种近似的 解决方案. 网络是图的一种特殊类型. 网络的每一条边都被赋予了权. 权同使用某边从一个节点移动到 另一个节点所花费的代价相关. 如图描述了带权的城市网络, 其中这里的权是两座城市(节 点)之间的英里数。
至此已经对将要在本书中讨论的不同群集类型做了总体的概述. 下面就准备实际看一看这些 群集是如何用C#实现的了. 首先会看到如何用来自. NET框架的抽象类CollectionBase 类来构建一个Collection类。
. NET框架库不包括用于存储数据的通用Collection类, 但是大家可以使用一种抽象的类 CollectionBase类来构造属于自己的Collection类. CollectionBase类为程序员提供了实现 定制Collection类的能力. CollectionBase类隐含实现了两个为构造Collection类所必需的 接口, 即ICollection和IEnumerable, 而留给程序员要做的工作就只是对这些作为Collection类特殊内容的方法的实现.
本节将要说明如何用C#来实现自身的Collection类. 这是出于几种目的考虑. 首先, 如果大家不是很熟悉面向对象编程(OOP), 那么这个实现将会展示一些简单的用C# 进行面向对象编程的技巧. 其次, 就如同讨论各种C#数据结构一样, 此节内容还可用于讨 论一些将要出现的性能问题. 最后, 就像本书中其他实现章节一样, 本节内容也会使人获益 良多, 因为仅仅用语言自身的元素就能重新实现已存在的数据结构实在是充满乐趣的事. 正 如DonKunth(计算机科学的先驱之一)所说的那样, 也许只有把一些知识教给计算机后才算真正的学到了它们. 所以, 比起使用日常编程库中选取现成的类来使用, 通过讲解C#如何实现不 同数据结构的过程将会使大家学会更多关于这些结构的知识.
在C#中定义一个Collection类最简单的方法就是把在System. Collections库中的抽象类CollectionBase作为基础类. 此类提供了一套可以实现构造自身群集的抽象方 法集合. CollectionBase类还提供了一种基础的数据结构——InnerList(一个ArrayList). 此结构可以用作自身类的基础. 本章节会看到如何使用CollectionBase来构造Collection 类.
弥补Collection类的全部方法包括一些与类的基础数据结构InnerList相交互的类型. 本节第一部分要实现的方法是Add方法、Remove方法、Count方法和Clear方法. 尽管还有其他方法可以使类更有用, 但是上述这些方法是类的绝对基本要素. 首先从Add方法开始. 该方法有一个参数, 即Object变量. 此变量用来保存群集要添加 的数据项. 代码如下所示:
using System;
using System.Collections;
public class Collection : CollectionBase{
public void Add(Object item) {
InnerList.Add(item);
}
}
ArrayList把数据作为对象(即Object数据类型)来存储. 这就是把参数item声明为Object 的原因. 第2章将会学到更多有关ArrayList的内容. Remove方法的实现与上述类似:
public void Remove(Object item)
{
InnerList.Remove(item);
}
接下来是Count方法. Count最常作为属性来实现, 但是这里更喜欢把它用作方法. 而且, 由于是在基础类CollectionBase中实现Count, 所以必须用new关键字来隐藏在CollectionBase中已有的Count定义:
public new int Count()
{
return InnerList.Count;
}
Clear方法应该把全部数据项从InnerList中移除. 这里也需要在方法定义中使用new关键字:
public new void Clear()
{
InnerList.Clear();
}
这些方法目前对于Collection类已经足够了. 接着来看一段使用了Collection类的程序代码:
using System;
using System.Collections;
public class Collection : CollectionBase {
public void Add(Object item)
{
InnerList.Add(item);
}
public void Remove(Object item)
{
InnerList.Remove(item);
}
public new void Clear()
{
InnerList.Clear();
}
public new int Count()
{
return InnerList.Count;
}
}
class chapter1{
static void Main()
{
Collection names = new Collection();
names.Add("David");
names.Add("Bernica");
names.Add("Raymond");
names.Add("Clayton");
foreach (Object name in names) {
Console.WriteLine(name);
}
Console.WriteLine("名字的总数是: " + names.Count());
names.Remove("Raymond");
Console.WriteLine("名字的总数是: " + names.Count());
names.Clear();
Console.WriteLine("名字的总数是: " + names.Count());
}
}
为了创建一个更加有用的Collection类, 还可以实现几种其他的方法. 大家可以在练习中实 现一些这样的方法.
面向对象编程的问题之一就是所谓“代码膨胀”. 为了说明方法参数所有可能的数据 类型而需要重载某种方法或重载一系列方法时, 就会发生使得代码的数量急剧膨胀. 代码膨胀的解决方案之一就是使某个值呈现多种数据类型的能力, 同时仅提供此值的一种定义. 这种编程方法被称为泛型编程. 泛型编程提供数据类型“占位符”. 它在编译时由特定的数据类型填充. 这个占位符用一对 尖括号<>和放在括号间的标识符来表示. 下面来看一个实例. 泛型编程第一个规范实例就是Swap函数. 下面是C#中泛型Swap函数的定义:
static void Swap<T>(ref T val1, ref T val2)
{
T temp;
temp = val1;
val1 = val2;
val2 = temp;
}
数据类型占位符直接放置在函数名后边. 在方法调用的时候使用所需类型替换掉泛型标识符T, 这样被标记为T的数据类型就会按照指定的类型生效. 下面就是一个测试此代码的程序:
using System;
class chapter1
{
static void Main()
{
int num1 = 100;
int num2 = 200;
Console.WriteLine("num1: " + num1);
Console.WriteLine("num2: " + num2);
Swap<int>(ref num1, ref num2);
Console.WriteLine("num1: " + num1);
Console.WriteLine("num2: " + num2);
string str1 = "Sam";
string str2 = "Tom";
Console.WriteLine("String 1: " + str1);
Console.WriteLine("String 2: " + str2);
Swap<string>(ref str1, ref str2);
Console.WriteLine("String 1: " + str1);
Console.WriteLine("String 2: " + str2);
}
static void Swap<T>(ref T val1, ref T val2)
{
T temp;
temp = val1;
val1 = val2;
val2 = temp;
}
}
程序的输出如下所示:
除了泛型函数, 还可以创建泛型类. 泛型类的定义包括一个跟在类名后边的 泛型类型占位符. 任何定义中引用类名的时候都必须提供类型占位符. 下面的类定义说明了创建泛型类的方法:
public class Node<T>
{
T data;
Node<T> link;
public Node(T data, Node<T> link)
{
this.data = data;
this.link = link;
}
}
可以按照如下形式使用此类:
Node<string> node1 = new Node<string>("Mike", null);
Node<string> node2 = new Node<string>("Raymond", node1);
本文章讨论到的几种数据结构都将采用Node类. 因为泛型编程十分有用的, 所以C#提供了可以直接使用的泛型数据结构库. 在System. Collection. Generics命名空间中可以找到它们, 本书在介绍此命 名空间中的数据结构时, 还将探究它们的使用方法.
文章采用了一种实用的方法来分析数据结构与算法检测, 所以这里避开使用大O分析法, 而采用运行简单基准测试的方式来代替. 这种测试将会说明运行一段代码需要多少时间. 基准法测试是用时间测试的方式来衡量运行完整算法所花费的时间长度. , 基 准测试既是艺术也是科学, 为了获得准确的分析结果, 要仔细设计测试代码. 下面就来进行详细讨论. 一个简单的时间测试 首先时间测试需要一些代码. 出于简单的考虑, 这里将测试一个控制台打印数组内容的子程序(subroutine). 代码如下所示:
static void DisplayNums(int[] arr)
{
for (int i = 0; i <= arr.GetUpperBound(0); i++)
Console.Write(arr[i] + " ");
}
arr数组参数的初始化放在了程序的另外一部分, 这部分稍后再进行研究. 为了测试这个子程序, 需要创建一个变量, 并且把子程序调用时的系统时间赋值给此变量. 此外, 还需要一个变量用来存储子程序结束时的时间. 根据这些内容写出了下述这段代码:
DateTime startTime;
TimeSpan endTime;
startTime = DateTime.Now;
DisplayNums();
DisplayNums();
DisplayNums();
endTime = DateTime.Now.Subtract(startTime);
在笔记本中(运行环境:机器主频1. 4mHz, 操作系统WindowsXP专业版)上运行此 代码时, 子程序的运行时间大约为5秒左右(4. 9917秒). 虽然这段代码执行的时间测试 好像很有道理, 但是在. NET环境下运行时间代码是完全不合适的. 为什么呢? 首先, 代码测量的是从子程序调用开始到子程序返回主程序之间流失的时间. 但是测试所测 量的时间也包含了与C#程序同时运行的其他进程所用的时间. 其次, 时间代码不考虑. NET环境下执行的GC(garbagecollection). 在类似. NET这样的运行时间环 境中, 系统可能在执行GC的任何时刻暂停. 时间代码实例没有考虑GC时间, 所以时间测试结果很容易受GC影响. 那么到底应该怎么做呢? 用于. NET环境的时间测试
在. NET环境中编写时间测试代码时, 需要考虑到程序运行所处的线程, 以及GC可能在任何时候发生. 先来看一下如何处理GC. 首先讨论一下GC的用途. C#中的引用类型(例如字符串、数组以及类)被分配在内存的堆(heap)中, 堆是用来保存前面提到的类型的内存区域. 诸如普通变量这样的值类型则存储在堆栈中. 对引用类型的引用也存储在堆栈中, 但是引用所指向的实际的数据则存储在堆中. 当声明变量的子程序完全执行结束时就可以释放掉存储在堆栈中的变量. 而另一方面, 存储 在堆中的变量则会一直保留到调用GC过程的时候, 不过只有那些已经不在任何地方被引用的数据才会被GC过程从堆中释放掉
程序执行过程中, GC可以发生在任何时刻. 而我们要确保的是在时间测试代码运行期间, 不会发生GC. 可以通过手动调用GC过程来阻止GC随意发生. . NET环境为调用GC提供了专门的对象——GC. 为了使 系统执行GC, 一种简单的办法是使用如下语句:
GC.Collect();
但只这么做还不够. 存储在堆中的每一个对象都有一个称为finalizer的方法. finalizer方法是在删除对象之前执行的最后一步. 有关finalizer方法的问题是, 这些方法不 是按照系统方式运行的. 实际上我们甚至完全无法知道对象的finalizer是否执行了, 但是有一点可以肯定的是, 对象被删除之前一定会执行自身的finalizer方法. 因此, 我们添加了一行代码来告诉程序等待堆上所有对象的finalizer方法都运行后再继续: GC.WaitForPendingFinalizers( );
GC.WaitForPendingFinalizers( );
已经解决了计时过程中发生GC的问题, 还剩下一个问题——采用正确的线程(thread). 在. NET环境中, 程序 运行在进程(process)中, 也被叫做应用程序域(applicationdomain). 它允许操作系统在同一时间内分开运行每个不同的程序. 在进程内, 全部或部分程序是在线程内运行的. 操作系统通过线程来分配程序的执 行时间. 在用时间测试程序代码时, 需要确保时间测试的代码就在为自身程序分配 的进程中运行, 而不是被操作系统执行的其他任务的进程中. 在. NET框架下通过使用Process类可以做到这一点. 通过Process类的多种方法, 可以获取正在运行当前程序的进程、获取正在运行当前程序的线程, 以及获取线程此时的执行时间. 以上方法可以合并成一个调用. 此调用会把它的返回值赋值给一个变量(TimeSpan对象)用来存储开始时间. 如下列代码所示(没错, 就是两行代码):
//将用于存储指定线程的开始时间
TimeSpan startingTime;
startingTime = Process.GetCurrentProcess().Threads[0].UserProcessorTime;
剩下要做的就是在进行时间测试的代码段停止时记录代码执行耗费的时间. 做法如下:
duration = Process.GetCurrentProcess().Threads[0].UserProcessorTime.Subtract(startingTime);
现在根据上述信息, 创建基于线程的时间测试的完整代码如下:
using System;
using System.Diagnostics;
class chapter1
{
static void Main()
{
int[] nums = new int[100000];
BuildArray(nums); //原文没有, 我加的为了对比两种方法差异
DateTime startTime;//原文没有, 我加的为了对比两种方法差异
TimeSpan endTime;//原文没有, 我加的为了对比两种方法差异
startTime = DateTime.Now;
TimeSpan duration;
DisplayNums(nums);
DisplayNums(nums);
DisplayNums(nums);
duration = Process.GetCurrentProcess().TotalProcessorTime;
endTime = DateTime.Now.Subtract(startTime);//原文没有, 我加的为了对比两种方法差异
Console.WriteLine("普通计时: " + endTime.TotalSeconds);//原文没有, 我加的为了对比两种方法差异
Console.WriteLine("线程计时: " + duration.TotalSeconds);
Console.ReadLine();//原文没有, 我加的, 不然控制台自动关闭无法观察结果
}
static void BuildArray(int[] arr)
{
for (int i = 0; i <= 99999; i++)
arr[i] = i;
}
static void DisplayNums(int[] arr)
{
for (int i = 0; i <= arr.GetUpperBound(0); i++)
Console.Write(arr[i] + " ");
}
}
采用新改进的时间测试代码后, 程序的返回值为0. 2526. 把此数值与先前第一版时间测试 代码返回的将近5秒的数值进行比较. 很明显, 这两种时间测试方法之间存在显著差异. 因而. NET环境中的时间测试代码应该使用. NET方法来做. (校对补充:我win10下测试结果如下, 代码与上方一致, 不知道为什么差异那么大。)
虽然不需要一个类来运行时间测试代码, 但是把代码作为类来重写是有意义的, 主要原因是 如果能够减少测试的代码行数量, 就能保证代码的清晰. Timing类需要下列数据成员: • startingTime——用来存储正在测试的代码的开始时间. • duration——用来存储正在测试的代码的终止时间. straingTime和duration这两个成员用来存储时间, 数据类型是TimeSpan. 在构造方法中把这两个属性代表的时间都设置为0. Timing类代码如下:
//如果过你建立单独的类文件,需要这俩命名空间, 原文未写
using System;
using System.Diagnostics;
//用于进行基于线程的代码执行计时
public class Timing
{
//记录开始时间
TimeSpan startingTime;
//记录经过时间
TimeSpan duration;
public Timing()
{
startingTime = new TimeSpan(0);
duration = new TimeSpan(0);
}
public void StopTime()
{
//获得指定线程从startingTime开始, 经过的时间
duration = Process.GetCurrentProcess().Threads[0].UserProcessorTime.Subtract(startingTime);
}
public void startTime()
{
//手动调用GC过程, 降低程序运行期间发生GC的可能性
GC.Collect();
//等待GC结束的信号 再继续执行代码
GC.WaitForPendingFinalizers();
//记录指定线程的当前时间
startingTime = Process.GetCurrentProcess().Threads[0].UserProcessorTime;
}
public TimeSpan Result()
{
//返回计时结果
return duration;
}
}
让我们结合Timing类, 改写之前测试DisplayNums子程序执行时间的代码, 如下所示:
using System;
using System.Diagnostics;
using System.Threading;
public class Timing
{
TimeSpan duration;
public Timing()
{
duration = new TimeSpan(0);
}
public void stopTime()
{
duration = Process.GetCurrentProcess().TotalProcessorTime;
}
public void startTime()
{
GC.Collect();
GC.WaitForPendingFinalizers();
}
public TimeSpan Result()
{
return duration;
}
}
class chapter1
{
static void Main()
{
int[] nums = new int[100000];
BuildArray(nums);
Timing tObj = new Timing();
tObj.startTime();
DisplayNums(nums);
tObj.stopTime();
Console.WriteLine(".NET计时: " + tObj.Result().TotalSeconds);
}
static void BuildArray(int[] arr)
{
for (int i = 0; i < 100000; i++)
arr[i] = i;
}
static void DisplayNums(int[] arr)
{
for (int i = 0; i <= arr.GetUpperBound(0); i++)
Console.Write(arr[i] + " ");
}
}
结合了Timing类后, 减少了主函数中的几行代码, 不过比起精简代码更重要的使其是, 降低了主函数的代码复杂程度. 如果没有Timing类, 那么就需要像下面这样书写记录开始时间的代码:
startTime = Process.GetCurrentProcess( ).Threads[0].UserProcessorTime;
而如果使用Timing类, 那么把记录开始开始时间只需要调用Timing. startTime方法, 如下所示:
tObj.startTime( );
通过把冗长的赋值语句封装到类方法内, 可以使得代码更便于阅读而且降低出错的可能。
经常会用到的三种重要技术进行了回顾与介绍. 尽管不需要编写整个程序, 但是一些程序的代码以及要讨论的库都采用面向对象的方式来编写. 自行开发的Collection类说明了 许多基本面向对象的概念, 而且这些概念看似贯穿全书. 泛型编程允许程序员通过限制需要编写或重载的方法的数量来简化几种数据结构的定义. Timing类提供了简单有效的方法来 衡量所要学习的数据结构与算法的性能. • 我们将要编写的一些程序, 以及教程将要讲解的类库, 都是以面向对象的规范来编写的. 通过本章中书写的Collection类, 展示了面向对象编程的一些基本概念. • 泛型编程允许程序员通过限制需要方法数量的方式来简化一些数据结构的定义 • Timing类提供了简单有效的途径, 帮助我们衡量接下来要学习的数据结构与算法的性能.