C#与数据结构

    上述代码通过在一个数组（第8行代码的成员变量_items）的基础上做进一步抽象，构建了一个可动态改变空间的顺序表ArrayList，并实现了一些基础操作，下面对之进行一一介绍。

    1.    初始化

    这里实现了2种初始方法，第一种为13～16行代码，它把顺序表空间初始化为一个0长度数组。这样做的目的是为了调用方便。做为成员变量的object类型数组_items默认会被初始化为null，如果不把它初始化为0长度数组，在使用代码 ArrayList arr = new ArrayList() 来创建ArrayList后试图访问它的Count属性将会导致错误发生。

    第二种初始化方法为18～27行代码，它根据capacity参数所指定的值来初始化_items数组的长度，如果初始化一个长度为100的ArrayList数组可以使用如下代码：

    ArrayList arr = new ArrayList(100)

    当可以预见ArrayList所操作的大概元素个数时，使用这种方法可以在一定程序上避免数组重复创建和数据迁移，以提高性能和减少内存垃圾回收的压力。

    2.    动态改变存储空间操作

    39～52行的EnsureCapacity(int min)方法用于空间不足时使空间加倍，从代码：

    int num = (this._items.Length == 0) ? _defaultCapacity : (this._items.Length * 2);

    可以得知，当元素个数为0是，空间增长为4，否则将翻倍。改变空间大小的代码是在Capacity属性中的set访问器中实现的（代码99～122行）。代码

    object[] destinationArray = new object[value];

    创建了一个新的object数组，它在内存中开辟了一个新的空间用于存放元素。代码

    Array.Copy(this._items, 0, destinationArray, 0, this._size);

    把_items数组中的元素全部拷贝到新数组destinationArray中，可以把它理解为数据搬新家。最后通过

    this._items = destinationArray;

    使用于存放数据的成员变量_items指向新的数组对象destinationArray。

    88～91行的TrimToSize()方法用于裁减多余空间，实际的裁减操作也是在Capacity属性中的set访问器中实现。这个操作也会导致数组的重新创建和数据迁移，建议一般情况下不使用此操作，除非集合中的剩余空间很多。

    3.    元素的读写操作

    131～149行代码实现了一个索引器，这样就可以使用中括号加索引号来读取和给元素赋值，使ArrayList的使用看上去和数组很相似。

    4.    元素的添加和插入操作

    29～37行的Add(object value)方法实现了添加元素的功能。元素添加在集合的末尾，成员变量_size用于指示当前元素个数，它总是指向集合中的最后一个元素。

    54～71行的Insert(int index, object value)方法用于在指定索引处插入一个元素。为了保证顺序表中的每个元素物理上相邻，插入点后面的所有元素都将后移一位，其效果如图2.7(a)所示。

    1.    元素的删除操作

    73～86行的RemoveAt(int index)方法用于删除指定索引的元素，删除指定元素后，删除点后的所有元素将向前移动一位其效果如图2.7(b)所示。

    下面对ArrayList类进行测试。

    【例2-1】ArrayList的使用

    新建一个控制台应用程序，并在项目中把上面的ArrayList.cs文件做为一个【现有项】添加进去。在代码窗体前面使用如下语句加入LinearList命名空间：

上一页  [1] [2] [3] [4] 下一页