本文实例讲述了C#实现顺序表(线性表)的方法。分享给大家供大家参考，具体如下：
基本思想是使用数组作为盛放元素的容器，数组一开始的大小要实现确定，并使用一个Pointer指向顺序表中最后的元素。顺序表中的元素是数组中元素的子集。顺序表在内存中是连续的，优势是查找，弱势是插入元素和删除元素。
为避免装箱拆箱，这里使用泛型，代替object。使用object的例子可以参照本站这篇文章： http://HdhCmsTestzzvips测试数据/article/208157.html ，这个链接中的例子实现的是队列，并没 有使用Pointer来标识 顺序表中最后一个元素，而是动态的调整数组的大小，这与本例明显不同，动态调整数组大小开销较大。使用object同样可以完成顺序表数据结构，但是频繁装箱拆箱造成较大的开销，应使用泛型代替。
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace LinearList
{
public interface IListDS<T>
{
int GetLength();
void Insert(T item, int i);
void Add(T item);
bool IsEmpty();
T GetElement( int i);
void Delete( int i);
void Clear();
int LocateElement(T item);
void Reverse();
}
//顺序表类
class SequenceList<T>:IListDS<T>
{
private int intMaxSize; //最大容量事先确定，使用数组必须先确定容量
private T[] tItems; //使用数组盛放元素
private int intPointerLast; //始终指向最后一个元素的位置
public int MaxSize
{
get { return this .intMaxSize; }
set { this .intMaxSize = value; }
}
public T this [ int i] //索引器方便返回
{
get { return this .tItems[i]; }
}
public int PointerLast
{
get { return this .intPointerLast; }
}
public SequenceList( int size)
{
this .intMaxSize = size;
this .tItems = new T[size]; //在这里初始化最合理
this .intPointerLast = -1; //初始值设为-1，此时数组中元素个数为0
}
public bool IsFull() //判断是否超出容量
{
return this .intPointerLast+1 == this .intMaxSize;
}
#region IListDS<T> 成员
public int GetLength()
{
return this .intPointerLast + 1; //不能返回tItems的长度
}
public void Insert(T item, int i) //设i为第i个元素，从1开始。该函数表示在第i个元素后面插入item
{
if (i < 1 || i > this .intPointerLast + 1)
{
Console.WriteLine( "The inserting location is wrong!" );
return ;
}
if ( this .IsFull())
{
Console.WriteLine( "This linear list is full! Can't insert any new items!" );
return ;
}
//如果可以添加
this .intPointerLast++;
for ( int j= this .intPointerLast;j>=i+1;j--)
{
this .tItems[j] = this .tItems[j - 1];
}
this .tItems[i] = item;
}
public void Add(T item)
{
if ( this .IsFull()) //如果超出最大容量，则无法添加新元素
{
Console.WriteLine( "This linear list is full! Can't add any new items!" );
}
else
{
this .tItems[++ this .intPointerLast] = item; //表长+1
}
}
public bool IsEmpty()
{
return this .intPointerLast == -1;
}
public T GetElement( int i) //设i最小从0开始
{
if ( this .intPointerLast == -1)
{
Console.WriteLine( "There are no elements in this linear list!" );
return default (T);
}
if (i > this .intPointerLast||i<0)
{
Console.WriteLine( "Exceed the capability!" );
return default (T);
}
return this .tItems[i];
}
public void Delete( int i) //设i最小从0开始
{
if ( this .intPointerLast == -1)
{
Console.WriteLine( "There are no elements in this linear list!" );
return ;
}
if (i > this .intPointerLast || i < 0)
{
Console.WriteLine( "Deleting location is wrong!" );
return ;
}
for ( int j = i; j < this .intPointerLast; j++)
{
this .tItems[j] = this .tItems[j + 1];
}
this .intPointerLast--; //表长-1
}
public void Clear()
{
this .intPointerLast = -1;
}
public int LocateElement(T item)
{
if ( this .intPointerLast == -1)
{
Console.WriteLine( "There are no items in the list!" );
return -1;
}
for ( int i = 0; i <= this .intPointerLast; i++)
{
if ( this .tItems[i].Equals(item)) //若是自定义类型，则T类必须把Equals函数override
{
return i;
}
}
Console.WriteLine( "Not found" );
return -1;
}
public void Reverse()
{
if ( this .intPointerLast == -1)
{
Console.WriteLine( "There are no items in the list!" );
}
else
{
int i = 0;
int j = this .GetLength() / 2; //结果为下界整数，正好用于循环
while (i < j)
{
T tmp = this .tItems[i];
this .tItems[i] = this .tItems[ this .intPointerLast - i];
this .tItems[ this .intPointerLast - i] = tmp;
i++;
}
}
}
#endregion
}
class Program
{
static void Main( string [] args)
{
}
}
}
基于顺序表的合并排序：
//基于顺序表的合并排序
static private SequenceList< int > Merge(SequenceList< int > s1,SequenceList< int > s2)
{
SequenceList< int > sList = new SequenceList< int >(20);
int i = 0;
int j = 0;
while (i<=s1.PointerLast&&j<=s2.PointerLast)
{
if (s1[i] < s2[j])
{
sList.Add(s1[i]);
i++;
}
else
{
sList.Add(s2[j]);
j++;
}
}
if (i > s1.PointerLast)
{
while (j <= s2.PointerLast)
{
sList.Add(s2[j]);
j++;
}
return sList;
}
else //即j>s2.PointerLast
{
while (i <= s1.PointerLast)
{
sList.Add(s1[i]);
i++;
}
return sList;
}
}
希望本文所述对大家C#程序设计有所帮助。
dy("nrwz");
查看更多关于C#实现顺序表(线性表)完整实例的详细内容...