数据结构（C#语言版）——线性表

现在的位置: 首页 > 综合 > 正文

数据结构（C#语言版）——线性表

2011年12月14日 ⁄ 综合 ⁄ 共 2404字 ⁄ 字号小中大 ⁄ 评论关闭

线性表

线性表(List)：由n(n>=0)个相同类型的数据元素构成的有限序列。
简记L=(D，R) D：数据元素的有限集合；R：数据元素之间关系的有限集合。
线性表的基本操作：求长度、清空操作、判断线性表是否为空、附加操作、插入操作、删除操作、取表元。

/// <summary>
/// 线性表的基本操作接口
/// 线性表(List)：由n(n>=0)个相同类型的数据元素构成的有限序列。
/// 简记L=(D，R) D：数据元素的有限集合；R：数据元素之间关系的有限集合。
/// </summary>
/// <typeparam name="T">元素类型</typeparam>
public interface IList<T>: IEnumerable<T> {
    /// <summary>
    /// 列表长度
    /// </summary>
    int Count { get; }
  
    /// <summary>
    /// 清空列表
    /// </summary>
    void Clear();
  
    /// <summary>
    /// 判断是否为空
    /// </summary>
    bool IsEmpty { get; }
  
    /// <summary>
    /// 添加一个数据项至列表尾部
    /// </summary>
    /// <param name="value">插入项</param>
    void Add(T value);
  
    /// <summary>
    /// 在指定位置插入一个数据项
    /// </summary>
    /// <param name="value">数据项</param>
    /// <param name="index">位置</param>
    void Insert(T value, int index);
  
    /// <summary>
    /// 删除指定位置的数据项
    /// </summary>
    /// <param name="index">位置</param>
    void Delete(int index);
  
    /// <summary>
    /// 获取指定位置的数据项
    /// </summary>
    /// <param name="index">位置</param>
    /// <returns>数据项</returns>
    T this[int index] { get; set; }
}

顺序表

在内存中用一块地址连续的空间依次存放线性表的数据元素，这种方式存储的线性表叫顺序表。

顺序表是用地址连续的存储单元顺序存储线性表中的各个数据元素，逻辑上相邻的数据元素在物理位置上也相邻。因此，在顺序表中查找任何一个位置上的数据元素非常方便，这是顺序存储的优点。但是，在对顺序表进行插入和删除时，需要通过移动数据元素来实现，影响了运行效率。

顺序表实现：

public class SequenceList<T> : IList<T> {
    private const int Step = 16;
    private int _capacity;
    private T[] _datas;
    private int _last = -1;
  
    public SequenceList() : this(Step) {}
  
    public SequenceList(int capacity) {
        this._capacity = capacity;
        this._datas = new T[capacity];
    } 
  
    #region Implementation of IEnumerable
  
    public IEnumerator<T> GetEnumerator() {
        int index = 0;
        while(index<=this._last) {
            yield return this._datas[index++];
        }
    }
  
    IEnumerator IEnumerable.GetEnumerator() {
        return GetEnumerator();
    }
  
    #endregion
  
    #region Implementation of IList<T>
  
    /// <summary>
    /// 列表长度
    /// </summary>
    public int Count {
        get { return this._last + 1; }
    }
  
    /// <summary>
    /// 清空列表
    /// </summary>
    public void Clear() {
        this._last = -1;
    }
  
    /// <summary>
    /// 判断是否为空
    /// </summary>
    public bool IsEmpty {
        get { return this._last == -1; }
    }
  
    /// <summary>
    /// 添加一个数据项至列表尾部
    /// </summary>
    /// <param name="value">插入项</param>
    public void Add(T value) {
        if(this._last+1==this._capacity) {
            Reassign();
        }
        this._last++;
        this._datas[this._last] = value;
    }
  
    private void Reassign() {
        this._capacity += Step;
        T[] newDatas = new T[this._capacity];
        int index = 0;
        while(index<=this._last) {