數據結構(C#)：順序表

線性表是有限個數據元素的序列。線性表的存儲有順序存儲和鏈式存儲兩種。

為使線性表支持相同的API，定義了以下接口，分別用順表和鏈表實現。

/*
* File　　 :　 ILinerList.cs
* Author　 :　 Zhenxing Zhou
* Date　　 :　 2008-12-06
* Blog　　 :　 http://www.xianfen.net/
*/
using System.Collections.Generic;
namespace Xianfen.Net.DataStructure
{
　　 interface ILinearList<T> : IEnumerable<T>
　　 {
　　　　 void Add(T t);
　　　　 void AddHead(T t);
　　　　 void AddTail(T t);
　　　　 void Clear();
　　　　 int Count { get; }
　　　　 int Find(T t);
　　　　 T GetAt(int pos);
　　　　 T GetHead();
　　　　 T GetTail();
　　　　 void InsertAt(T t, int pos);
　　　　 bool IsEmpty { get; }
　　　　 void RemoveAll();
　　　　 void RemoveAt(int pos);
　　　　 void RemoveHead();
　　　　 void RemoveTail();
　　　　 void SetAt(int pos, T t);
　　 }
}

本篇實現順序表的存取。順序表的存取有很多中實現方式。

線性表的順序存儲是指用一組地址連續的存儲單元以此存儲線性表的元素。兩個邏輯相鄰的元素在物 理上也是相鄰的，能夠快速取得指定索引的元素；但插入、刪除元素時需要移動元素，效率較低；存儲區 是連續的，長度一般不能在原存儲區的基礎上擴大，擴大存儲區需要復制原來的元素。

代碼實現：

/*
* File　　 :　 SequentialList.cs
* Author　 :　 Zhenxing Zhou
* Date　　 :　 2008-12-06
* Blog　　 :　 http://www.xianfen.net/
*/
using System;
using System.Collections;
using System.Collections.Generic;

namespace Xianfen.Net.DataStructure
{
　　 public class SequentialList<T> : ILinearList<T>
　　 {
　　　　 private T[] m_List;
　　　　 private int m_Count;
　　　　 private int m_Capacity;

　　　　 public int Count
　　　　 {
　　　　　　 get { return m_Count; }
　　　　 }

　　　　 public bool IsEmpty
　　　　 {
　　　　　　 get { return m_Count == 0; }
　　　　 }

　　　　 public SequentialList()
　　　　　　 : this(16)
　　　　 {
　　　　 }

　　　　 public SequentialList(int capacity)
　　　　 {
　　　　　　 m_Count = 0;
　　　　　　 m_Capacity = capacity;
　　　　　　 m_List = new T[m_Capacity];
　　　　 }

　　　　 public void Add(T t)
　　　　 {
　　　　　　 InsertAt(t, m_Count);
　　　　 }

　　　　 public void AddHead(T t)
　　　　 {
　　　　　　 InsertAt(t, 0);
　　　　 }

　　　　 public void AddTail(T t)
　　　　 {
　　　　　　 Add(t);
　　　　 }

　　　　 public void Clear()
　　　　 {
　　　　　　 m_Count = 0;
　　　　 }

　　　　 public int Find(T t)
　　　　 {
　　　　　　 for (int i = 0; i < m_Count; i++)
　　　　　　 {
　　　　　　　　 if (m_List[i].Equals(t))
　　　　　　　　 {
　　　　　　　　　　 return i;
　　　　　　　　 }
　　　　　　 }

　　　　　　 return -1;
　　　　 }

　　　　 public T GetAt(int pos)
　　　　 {
　　　　　　 if (pos >= m_Count || pos < 0)
　　　　　　 {
　　　　　　　　 throw new IndexOutOfRangeException("pos");
　　　　　　 }

　　　　　　 return m_List[pos];
　　　　 }

　　　　 public T GetHead()
　　　　 {
　　　　　　 return m_List[0];
　　　　 }

　　　　 public T GetTail()
　　　　 {
　　　　　　 return m_List[m_Count - 1];
　　　　 }

　　　　 public void InsertAt(T t, int pos)
　　　　 {
　　　　　　 if (pos > m_Count)
　　　　　　 {
　　　　　　　　 throw new IndexOutOfRangeException("pos");
　　　　　　 }

　　　　　　 if (m_Count == int.MaxValue)
　　　　　　 {
　　　　　　　　 throw new ArithmeticException();
　　　　　　 }

　　　　　　 EnsureCapacity();

　　　　　　 for (int i = m_Count - 1; i >= pos; i--)
　　　　　　 {
　　　　　　　　 m_List[i + 1] = m_List[i];
　　　　　　 }

　　　　　　 m_List[pos] = t;
　　　　　　 m_Count++;
　　　　 }

　　　　 public void RemoveAll()
　　　　 {
　　　　　　 Clear();
　　　　 }

　　　　 public void RemoveAt(int pos)
　　　　 {
　　　　　　 if (pos >= m_Count || pos < 0)
　　　　　　 {
　　　　　　　　 throw new IndexOutOfRangeException("pos");
　　　　　　 }

　　　　　　 for (int i = pos; i < m_Count; i++)
　　　　　　 {
　　　　　　　　 m_List[i] = m_List[i + 1];
　　　　　　 }

　　　　　　 m_Count--;
　　　　 }

　　　　 public void RemoveHead()
　　　　 {
　　　　　　 RemoveAt(0);
　　　　 }

　　　　 public void RemoveTail()
　　　　 {
　　　　　　 RemoveAt(m_Count - 1);
　　　　 }

　　　　 public void SetAt(int pos, T t)
　　　　 {
　　　　　　 if (pos >= m_Count || pos < 0)
　　　　　　 {
　　　　　　　　 throw new IndexOutOfRangeException("pos");
　　　　　　 }

　　　　　　 m_List[pos] = t;
　　　　 }

　　　　 // 空間不足時，重新分配足夠大的空間，原內容復制到新的空間。
　　　　 // 分配算法類似與StringBuilder的空間再分配方式。
　　　　 private void EnsureCapacity()
　　　　 {
　　　　　　 if (m_Count + 1 > m_Capacity)
　　　　　　 {
　　　　　　　　 m_Capacity *= 2;

　　　　　　　　 if (m_Count + 1 > m_Capacity)
　　　　　　　　 {
　　　　　　　　　　 m_Capacity = m_Count + 1;
　　　　　　　　 }

　　　　　　　　 T[] tempArray = new T[m_Capacity];

　　　　　　　　 for (int i = 0; i < m_Count; i++)
　　　　　　　　 {
　　　　　　　　　　 tempArray[i] = m_List[i];
　　　　　　　　 }

　　　　　　　　 m_List = tempArray;
　　　　　　 }
　　　　 }

　　　　 public IEnumerator<T> GetEnumerator()
　　　　 {
　　　　　　 for (int i = 0; i < m_Count; i++)
　　　　　　 {
　　　　　　　　 yield return m_List[i];
　　　　　　 }
　　　　 }

　　　　 IEnumerator IEnumerable.GetEnumerator()
　　　　 {
　　　　　　 return GetEnumerator();
　　　　 }
　　 }
}

如果發現BUG請留言指出，下一篇介紹單鏈表的實現。