-
c#实现顺序表
这几天需要实现各种数据结构（泛型）.主要实现线性表和链表。
线性表是由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
}
}
刚完成,还未经过测试.
刚完成,还未经过测试.
