本文实例讲述了C#数据结构之顺序表(SeqList)实现方法。分享给大家供大家参考，具体如下：
线性结构 (Linear Stucture)是数据结构(Data Structure)中最基本的结构，其特征用图形表示如下：
即：每个元素前面有且只有一个元素(称为[前驱])，同样后面有且只有一个元素(称为"后继")--注：起始元素的前驱认为是空，末尾元素的后继认为也是空，这样在概念上就不冲突了。
线性表(List)是线性结构的一种典型实现，它又可以分为：顺序表(SeqList)和链表(LinkList)二大类.
顺序表（SeqList）的基本特征为：元素在内部存储时是一个接一个在存储单元中按顺序存储的，所以只要知道"起始元素的存储地址"--称为顺序表的基地址(Base Address)以及顺序表中任何元素的位置(即它是第几个元素)，就能直接定位到该元素的地址，从而直接访问到该元素的值。也就是说存储/读取每个元素所用的时间是相同的，即所谓的[ 随机存取 ]
C#语言中数组(Array)在内存中占用的就是一组连续的存储区域，所以用数组来实现顺序表再适用不过。
先来定义线性表的通用接口IListDS.cs(注：DS为DataStructure的缩写)
namespace 线性表
{
public interface IListDS<T>
{
//取得线性表的实际元素个数
int Count();
//清空线性表
void Clear();
//判断线性表是否为空
bool IsEmpty();
//（在末端）追加元素
void Append(T item);
//在位置i[前面]插入元素item
void InsertBefore(T item, int i);
//在位置i[后面]插入元素item
void InsertAfter(T item, int i);
//删除索引i处的元素
T RemoveAt( int i);
//获得索引位置i处的元素
T GetItemAt( int i);
//返回元素value的索引
int IndexOf(T value);
//反转线性表的所有元素
void Reverse();
}
}
顺序表(SeqList)的实现：
using System;
using System.Text;
namespace 线性表
{
/// <summary>
/// 顺序表
/// </summary>
/// <typeparam name="T"></typeparam>
public class SeqList<T> : IListDS<T>
{
private int maxsize;
private T[] data;
private int last;
//类索引器
public T this [ int index]
{
get
{
return this .GetItemAt(index);
}
set
{
if (index < 0 || index > last + 1)
{
Console.WriteLine( "Position is error" );
return ;
}
data[index] = value;
}
}
//最后一个元素的下标
public int Last
{
get { return last; }
}
//最大容量
public int Maxsize
{
get { return this .maxsize; }
set { this .maxsize = value; }
}
//构造函数
public SeqList( int size)
{
data = new T[size];
maxsize = size;
last = -1;
}
//返回链表的实际长度
public int Count()
{
return last + 1;
}
//清空
public void Clear()
{
last = -1;
}
//是否空
public bool IsEmpty()
{
return last == -1;
}
//是否满
public bool IsFull()
{
return last == maxsize - 1;
}
//(在最后位置)追加元素
public void Append(T item)
{
if (IsFull())
{
Console.WriteLine( "List is full" );
return ;
}
data[++last] = item;
}
/// <summary>
///前插
/// </summary>
/// <param name="item">要插入的元素</param>
/// <param name="i">要插入的位置索引</param>
public void InsertBefore(T item, int i)
{
if (IsFull())
{
Console.WriteLine( "List is full" );
return ;
}
if (i < 0 || i > last + 1)
{
Console.WriteLine( "Position is error" );
return ;
}
if (i == last + 1)
{
data[last + 1] = item;
}
else
{
//位置i及i以后的元素，全部后移
for ( int j = last; j >= i; j--)
{
data[j + 1] = data[j];
}
data[i] = item;
}
++last;
}
/// <summary>
/// 后插
/// </summary>
/// <param name="item"></param>
/// <param name="i"></param>
public void InsertAfter(T item, int i)
{
if (IsFull())
{
Console.WriteLine( "List is full" );
return ;
}
if (i < 0 || i > last)
{
Console.WriteLine( "Position is error" );
return ;
}
if (i == last)
{
data[last + 1] = item;
}
else
{
//位置i以后的元素(不含位置i)，全部后移
for ( int j = last; j > i; j--)
{
data[j + 1] = data[j];
}
data[i+1] = item;
}
++last;
}
/// <summary>
/// 删除元素
/// </summary>
/// <param name="i">要删除的元素索引</param>
/// <returns></returns>
public T RemoveAt( int i)
{
T tmp = default (T);
if (IsEmpty())
{
Console.WriteLine( "List is empty" );
return tmp;
}
if (i < 0 || i > last)
{
Console.WriteLine( "Position is error!" );
return tmp;
}
if (i == last)
{
tmp = data[last];
}
else
{
tmp = data[i];
//位置i以及i以后的元素前移
for ( int j = i; j <= last; j++)
{
data[j] = data[j + 1];
}
}
--last;
return tmp;
}
/// <summary>
/// 获取第几个位置的元素
/// </summary>
/// <param name="i">第几个位置</param>
/// <returns></returns>
public T GetItemAt( int i)
{
if (IsEmpty() || (i < 0) || (i > last))
{
Console.WriteLine( "List is empty or Position is error!" );
return default (T);
}
return data[i];
}
/// <summary>
/// 定位元素的下标索引
/// </summary>
/// <param name="value"></param>
/// <returns></returns>
public int IndexOf(T value)
{
if (IsEmpty())
{
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>
public void Reverse()
{
T tmp = default (T);
for ( int i = 0; i <= last / 2; i++)
{
tmp = data[i];
data[i] = data[last-i];
data[last-i] = tmp;
}
}
public override string ToString()
{
StringBuilder sb = new StringBuilder();
for ( int i = 0; i <= last; i++)
{
sb.Append(data[i].ToString() + "，" );
}
return sb.ToString().TrimEnd( '，' );
}
}
}
测试代码片段：
Console.WriteLine( "顺序表测试开始..." );
SeqList< string > seq = new SeqList< string >(10);
seq.Append( "x" );
seq.InsertBefore( "w" , 0);
seq.InsertBefore( "v" , 0);
seq.Append( "y" );
seq.InsertBefore( "z" , seq.Count());
Console.WriteLine(seq.Count()); //5
Console.WriteLine(seq.ToString()); //v,w,x,y,z
Console.WriteLine(seq[1]); //w
Console.WriteLine(seq[0]); //v
Console.WriteLine(seq[4]); //z
Console.WriteLine(seq.IndexOf( "z" )); //4
Console.WriteLine(seq.RemoveAt(2)); //x
Console.WriteLine(seq.ToString()); //v,w,y,z
seq.InsertBefore( "x" , 2);
Console.WriteLine(seq.ToString()); //v,w,x,y,z
Console.WriteLine(seq.GetItemAt(2)); //x
seq.Reverse();
Console.WriteLine(seq.ToString()); //z,y,x,w,v
seq.InsertAfter( "z_1" , 0);
seq.InsertAfter( "y_1" , 2);
seq.InsertAfter( "v_1" , seq.Count()-1);
Console.WriteLine(seq.ToString()); //z，z_1，y，y_1，x，w，v，v_1
顺序表的优点：读取元素时可直接定位，所以在某些操作(比如将顺序表元素反转合围)中，不需要完全遍历，循环次数(即时间复杂度)相对完全遍历而言能减少一半。
顺序表的优点：插入/删除元素，因为要保持其顺序性，所以后续元素需要移动，增加了时间开销。
最后指出：.Net命名空间System.Collections.Generic中的List<T>就是一个内置的顺序表.
希望本文所述对大家C#程序设计有所帮助。
dy("nrwz");
查看更多关于C#数据结构之顺序表(SeqList)实例详解的详细内容...