2.2.3 ArrayList
如果要动态地改变数组所占用内存空间的大小，则需以数组为基础进一步抽象，以实现这个功能。以图2.2的学生宿舍为例，为了使A班的所学生住在连续的宿舍内，可以把A班的学生全部搬迁到连续的5间空宿舍内。其效果如图2.6所示：
现实中，为了让一个班新加入的10个学生能跟原来的学生住在一起而把班级整体搬迁，这样的做法显示不合适，因为搬迁的成本太高。但在计算机中，内存成片区域间的拷贝成本是非常低的，这样的解决方案是合理可行的。
但是这个解决方案还存在问题，如果一个班级频繁地有新学生加入，为了保证学生能住在连续的宿舍内，整个班级就不得不频繁地搬迁。可以采用以空间换时间的做法来解决这个问题，在学生每次搬迁时，都让班级宿舍的数量是原来的两倍。也就是说，如果原来一个班级有4间宿舍，搬迁后就变为8间，再次搬迁则变为16间。如图2.2所示，A班的宿舍为201～208。206～208这三间宿舍做为本班备用宿舍，不再允许其他班级的学生搬入。
C#中的ArrayList正是采用上述方法来动态改变数组大小的。ArrayList又被称为动态数组，它的存储空间可以被动态改变，同时还拥有添加、删除元素的功能。
下面列出了ArrayList的部分核心代码：
| 【ArrayList.cs】
using System;
namespace LinearList
{
public class ArrayList
{
// 成员变量
private const int _defaultCapacity = 4; //默认初始容量
private object[] _items; //用于存放元素的数组
private int _size; //指示当前元素个数
//当元素个数为零时的数组状态
private static readonly object[] emptyArray = new object[0];
// 方法
public ArrayList() //默认构造方法
{ //这样做可以避免元素个数为零时的访问出错
this._items = emptyArray;
}
//指定ArrayList初始容量的构造方法
public ArrayList(int capacity)
{
if (capacity < 0)
{ //当容量参数为负数时引发异常
throw new ArgumentOutOfRangeException("capacity",
"为ArrayList指定的初始容量不能为负数");
}
//按照capacity参数指定的长度的值初始化数组
this._items = new object[capacity];
}
//添加一个方法
public virtual int Add(object value)
{ //当空间满时
if (this._size == this._items.Length)
{ //调整空间
this.EnsureCapacity(this._size + 1);
}
this._items[this._size] = value; //添加元素
return this._size++; //使长度加1
}
//动态调整数组空间
private void EnsureCapacity(int min)
{
if (this._items.Length < min)
{ //空间加倍
int num = (this._items.Length == 0) ?
_defaultCapacity : (this._items.Length * 2);
if (num < min)
{
num = min;
}
//调用Capacity的set访问器以按照num的值调整数组空间
this.Capacity = num;
}
}
//在指定索引入插入指定元素
public virtual void Insert(int index, object value)
{
if ((index < 0) || (index > this._size))
{
throw new ArgumentOutOfRangeException("index", "索引超出范围");
}
if (this._size == this._items.Length)
{ //当空间满时调整空间
this.EnsureCapacity(this._size + 1);
}
if (index < this._size)
{ //插入点后面的所有元素向后移动一位
Array.Copy(this._items, index,
this._items, index + 1, this._size - index);
}
this._items[index] = value; //插入元素
this._size++; //使长度加1
}
//移除指定索引的元素
public virtual void RemoveAt(int index)
{
if ((index < 0) || (index >= this._size))
{
throw new ArgumentOutOfRangeException("index", "索引超出范围");
}
this._size--; //使长度减1
if (index < this._size)
{ //使被删除元素后的所有元素向前移动一位
Array.Copy(this._items, index + 1,
this._items, index, this._size - index);
}
this._items[this._size] = null; //最后一位空出的元素置空
}
//裁减空间，使存储空间正好适合元素个数
public virtual void TrimToSize()
{
this.Capacity = this._size;
}
// 属性
public virtual int Capacity //指示ArrayList的存储空间
{
get
{
return this._items.Length;
}
set
{
if (value != this._items.Length)
{
if (value < this._size)
{
throw new ArgumentOutOfRangeException("value", "容量太小");
}
if (value > 0)
{ //开辟一块新的内存空间存储元素
object[] destinationArray = new object[value];
if (this._size > 0)
{ //把元素搬迁到新空间内
Array.Copy(this._items, 0,
destinationArray, 0, this._size);
}
this._items = destinationArray;
}
else //最小空间为_defaultCapacity所指定的数目，这里是4
{
this._items = new object[_defaultCapacity];
}
}
}
}
public virtual int Count //只读属性，指示当前元素个数
{
get
{
return this._size;
}
}
public virtual object this[int index] //索引器
{
get //获取指定索引的元素值
{
if ((index < 0) || (index >= this._size))
{
throw new ArgumentOutOfRangeException("index", "索引超出范围");
}
return this._items[index];
}
set //设置指定索引的元素值
{
if ((index < 0) || (index >= this._size))
{
throw new ArgumentOutOfRangeException("index", "索引超出范围");
}
this._items[index] = value;
}
}
}
} |
更多内容请看PCdog.com--数据结构、
数据结构相关文章专题
