這幾天需要實現各種數據結構（泛型）.主要實現線性表和鏈表。
線性表是由n(n>=0)個相同類型的數據元素構成的有限序列。除第一個元素外,其余元素只有一個直接前驅;除最後一個元素外,其余元素只有一個直接後繼。
順序表是把表中元素一個接一個地放進一快地址連續的空間，因此順序表的實現有數組來完成。
由於這次需要實現多種數據結構，各種數據結構都有相同的方法，比如求長度，清空等。因此定義一個公共接口:
namespace DateStructrues
{
public interface IDS<T>
{
int Count { get;} //求長度
void Clear(); //清空操作
bool IsEmpty{get;} //判斷線性表是否為空
}
}
線性表接口:
namespace DateStructrues.Lists
{
interface IListDS<T> : IDS<T>
{
void Append(T item); //附加操作
void Insert(T item, int index); //插入操作
T Delete(int index); //刪除操作
T GetElement(int index); //取表元
int Locate(T value); //按值查找
}
}
實現順序表:
using System;
namespace DateStructrues.Lists
{
public class SeqList<T> : IListDS<T> where T:IComparable<T>
{
#region Files
T[] data; //數組,存入順序表
int maxsize; //最大值
int last; //最後一個元素
#endregion
#region Properties
/// <value>
/// 按索引訪問或設置data數組
/// </value>
/// <param name="index">索引值</param>
/// <returns>泛型數組</returns>
public T this[uint index]
{
get
{
return data[index];
}
set
{
data[index] = value;
}
}
/// <value>
/// 訪問或設置線性表最大容量
/// </value>
public int Maxsize
{
get
{
return maxsize;
}
set
{
maxsize = value;
}
}
#endregion
#region Constructions
/// <summary>
/// 無參構造器
/// </summary>
public SeqList() : this(20) { }
/// <summary>
/// 有參構造器
/// </summary>
/// <param name="size">數組初始大小</param>
public SeqList(int size)
{
data = new T[size];
maxsize = size;
last = -1;
}
#endregion
#region Methods
/// <summary>
/// 判斷線性表是否為滿
/// </summary>
public virtual bool IsFull
{
get
{
if (last == maxsize - 1)
{
return true;
}
else
{
return false;
}
}
}
/// <summary>
///重寫ToString方法,方便測試.測試完成,刪除該方法.
/// </summary>
/// <returns></returns>
public override string ToString()
{
for (int i = 0; i <= last; ++i)
{
Console.WriteLine(data[i]);
}
return "OK";
}
/// <summary>
/// 順序查找
/// </summary>
/// <param name="data"></param>
/// <returns></returns>
public virtual int SeqSearch(T key)
{
Insert(key, 1);
int i=0;
for (i = last; !key.Equals(data[i]); --i) ;
return i;
}
#endregion
#region IListDS<T> members
/// <summary>
/// 在線性表末尾添加一個元素
/// 如果線性表已滿,退出
/// 否則data[++last] = item
/// </summary>
/// <param name="item">要添加到線性表末尾的值</param>
public virtual void Append(T item)
{
if (last == maxsize - 1)
{
Console.WriteLine("List is full");
}
data[++last] = item;
}
/// <summary>
/// 對線性表進行插入操作
/// </summary>
/// <param name="item">要插入的值</param>
/// <param name="index">線性表的索引值</param>
public virtual void Insert(T item, int intLocation)
{
//判斷表是否滿
if (last == maxsize - 1)
{
Console.WriteLine("List is full");
return;
}
//判斷插入的位置是否正確
else if ((intLocation < 1) || (intLocation > last + 2))
{
Console.WriteLine("Position is error!");
return;
}
//在順序表的表尾插入數據元素
else if (intLocation == last + 2)
{
data[intLocation - 1] = item;
}
//在表的其它位置插入數據元素
else
{
//移動元素
for (int i = last; i >= intLocation - 1; --i)
{
data[i + 1] = data[i];
}
//將新的數據元素插入到第i個位置上
data[intLocation - 1] = item;
//修改表長
++last;
}
}
/// <summary>
/// 對線性表進行刪除操作
/// </summary>
/// <param name="index">要刪除元素的索引</param>
/// <returns>被刪除的元素</returns>
public virtual T Delete(int intLocation)
{
T result = default(T);
//判斷順序表為空
if (last == -1)
{
Console.WriteLine("List is empty");
return result;
}
//判斷刪除的位置是否正確
else if ((intLocation < 1) || (intLocation > last + 1))
{
Console.WriteLine("Position is error!");
return result;
}
//刪除的是最後一個元素
else if (intLocation == last + 1)
{
result = data[last--];
return result;
}
//刪除的不是最後一個元素
else
{
result = data[intLocation - 1];
//元素移動
for (int j = intLocation; j <= last; ++j)
{
data[j - 1] = data[j];
}
}
--last; //修改表長
return result;
}
/// <summary>
/// 取出指定線性表索引位置的元素
/// </summary>
/// <param name="index"></param>
/// <returns></returns>
public virtual T GetElement(int intLocation)
{
T result = default(T);
//判斷順序表為空
if (last == -1)
{
Console.WriteLine("List is empty");
return result;
}
//判斷刪除的位置是否正確
else if ((intLocation < 1) || (intLocation > last + 1))
{
Console.WriteLine("Position is error!");
return result;
}
return data[intLocation - 1];
}
/// <summary>
/// 按給定元素在線性表中進行查找
/// </summary>
/// <param name="value">要查找的元素</param>
/// <returns>查找結果的索引值</returns>
public virtual int Locate(T value)
{
//判斷線性表是否為空
if (last == -1)
{
Console.WriteLine("List is Empty");
return -1;
}
int i = 0;
//遍歷線性表進行查找
for (i = 0; i <= last; ++i)
{
if (value.Equals(data[i]))
{
break;
}
}
//線性表內沒有匹配元素
if (i > last)
{
return -1;
}
return i;
}
/// <summary>
/// 按索引更新線性表元素
/// </summary>
/// <param name="newItem">更新後的元素</param>
/// <param name="intLocation">要更新的索引位置</param>
public virtual void Update(T newItem, int intLocation)
{
//判斷線性表是否為空
if (last == -1)
{
Console.WriteLine("List is Empty");
}
//判斷刪除的位置是否正確
else if ((intLocation < 1) || (intLocation > last + 1))
{
Console.WriteLine("Position is error!");
}
else
{
data[intLocation - 1] = newItem;
}
}
/// <summary>
/// 按元素值更新線性表元素
/// </summary>
/// <param name="newItem">更新後的元素</param>
/// <param name="oldItem">更新前的元素</param>
public virtual void Replace(T newItem, T oldItem)
{
//判斷線性表是否為空
if (last == -1)
{
Console.WriteLine("List is Empty");
}
int i = 0;
//遍歷線性表進行查找
for (i = 0; i <= last; ++i)
{
if (oldItem.Equals(data[i]))
{
data[i] = newItem;
}
}
//線性表內沒有匹配元素
if (i > last)
{
Console.WriteLine("List have no oldItem");
}
}
#endregion
#region IDS<T> members
/// <summary>
/// 獲取線性表長度
/// </summary>
public virtual int Count
{
get
{
return last + 1;
}
}
/// <summary>
/// 對線性表執行清空操作
/// </summary>
public virtual void Clear()
{
last = -1;
}
/// <summary>
/// 判斷線性表是否為空
/// </summary>
/// <returns></returns>
public virtual bool IsEmpty
{
get
{
if (last == -1)
{
return true;
}
else
{
return false;
}
}
}
#endregion
}
}
剛完成,還未經過測試.
