1、定义:
顺序表(Sequence List)是在计算机内在中以数组的形式保存的线性表,是指用一组地址连续的存储单元依次存储数据元素的线性结构。
public interface IListDS<T>
{
bool Insert(T item,int pos);//插入元素
bool IsEmpty();//是否为空
int GetLength();//得到容量
void Append(T item);//添加新元素
void Clear();//清空
T Delete(int pos);//删除元素
T GetElem(int pos);//根据索引查找
int Locate(T value);//根据值查找
}
2、实现:
public class SeqList<T>:IListDS<T>
{
#region 变量成员
private int maxsize;//容量
private T[] datas;//存放元素的数组
private int last;//末位置
#endregion
#region 属性
/// <summary>
/// 最后一个元素位置
/// </summary>
public int Last
{
get
{
return last;
}
}
/// <summary>
/// 容量
/// </summary>
public int MaxSize
{
get
{
return maxsize;
}
set
{
maxsize = value;
}
}
#endregion
/// <summary>
/// 索引器
/// </summary>
/// <param name="index"></param>
/// <returns></returns>
public T this[int index]
{
get
{
return datas[index];
}
set
{
datas[index] = value;
}
}
/// <summary>
/// 构造器
/// </summary>
/// <param name="size"></param>
public SeqList(int size)
{
datas = new T[size];
maxsize = size;
last = -1;
}
#region 方法成员
/// <summary>
/// 得到顺序表长度
/// </summary>
/// <returns></returns>
public int GetLength()
{
return last + 1;
}
/// <summary>
/// 清空顺序表
/// </summary>
public void Clear()
{
last = -1;
}
/// <summary>
/// 判断是否为空
/// </summary>
/// <returns></returns>
public bool IsEmpty()
{
if(last==-1)
return true;
return false;
}
/// <summary>
/// 判断顺序表是否已满
/// </summary>
/// <returns></returns>
public bool IsFull()
{
if (last == maxsize - 1)
return true;
return false;
}
/// <summary>
/// 添加新元素
/// </summary>
/// <param name="item"></param>
public void Append(T item)
{
if (IsFull())
{
Console.WriteLine("The List's already full yet");
return;
}
datas[++last] = item;
}
/// <summary>
/// 插入元素
/// </summary>
/// <param name="item">元素</param>
/// <param name="pos">位置</param>
/// <returns>是否插入成功</returns>
public bool Insert(T item, int pos)
{
if (IsFull())
{
Console.WriteLine("The List's already full yet");
return false;
}
if(pos<0 || pos>last+1)
{
Console.WriteLine("The position is error");
return false;
}
if (pos == last + 1)
datas[pos] = item;
else
{
for (int index = last; index >= pos; --index)
{
datas[index + 1] = datas[index];
}
datas[pos] = item;
}
++last;
return true;
}
/// <summary>
/// 删除元素
/// </summary>
/// <param name="pos"></param>
/// <returns></returns>
public T Delete(int pos)
{
T tmp = default(T);
if(IsEmpty())
{
Console.WriteLine("The List is empty");
return tmp;
}
if(pos<-0 || pos>last)
{
Console.WriteLine("The position is err");
return tmp;
}
if (pos == last)
tmp = datas[last];
else
{
tmp = datas[pos];
for (int index = pos; index < last; ++index)
{
datas[index] = datas[index + 1];
}
}
--last;
return tmp;
}
/// <summary>
/// 根据索引查找某一元素
/// </summary>
/// <param name="pos">索引</param>
/// <returns></returns>
public T GetElem(int pos)
{
if (IsEmpty() || (pos < 0) || pos > last)
{
Console.WriteLine("List is empty or the position is error");
return default(T);
}
return datas[pos];
}
/// <summary>
/// 根据值查找某一元素
/// </summary>
/// <param name="value"></param>
/// <returns></returns>
public int Locate(T value)
{
if (IsEmpty())
{
Console.WriteLine("List is empty");
return -1;
}
int index = 0;
for (index = 0; index <= last; ++index)
{
if (value.Equals(datas[index]))
break;
}
if (index > last)
return -1;
return index;
}
#endregion
}
3、演示:
class Program
{
static void Main(string[] args)
{
SeqList<int> seqList = new SeqList<int>(8);
seqList.Append(21);
seqList.Append(22);
seqList.Append(23);
Console.WriteLine("Inital the sequence list");
for(int i=0;i<seqList.GetLength();i++)
{
Console.WriteLine(seqList[i]);
}
Console.WriteLine("Insert method sample:");
seqList.Insert(20, 0);
seqList.Insert(24, 4);
for(int i=0;i<seqList.GetLength();i++)
{
Console.WriteLine(seqList[i]);
}
Console.WriteLine("Delete method sample:");
seqList.Delete(0);
for(int i=0;i<seqList.GetLength();i++)
{
Console.WriteLine(seqList[i]);
}
Console.WriteLine("The 2st item is:{0}", seqList.GetElem(1));
Console.WriteLine("The position of value 23 is:{0}", seqList.Locate(23));
Console.WriteLine("Empty the sequence list");
seqList.Clear();
Console.WriteLine("The length of the sequence list is {0}",seqList.GetLength());
Console.ReadKey();
}
}