C#实现顺序表(线性表)完整实例
本文实例讲述了C#实现顺序表(线性表)的方法。分享给大家供大家参考，具体如下：
基本思想是使用数组作为盛放元素的容器，数组一开始的大小要实现确定，并使用一个Pointer指向顺序表中最后的元素。顺序表中的元素是数组中元素的子集。顺序表在内存中是连续的，优势是查找，弱势是插入元素和删除元素。
为避免装箱拆箱，这里使用泛型，代替object。使用object的例子可以参照本站这篇文章：https://www.nhooo.com/article/87603.htm，这个链接中的例子实现的是队列，并没有使用Pointer来标识顺序表中最后一个元素，而是动态的调整数组的大小，这与本例明显不同，动态调整数组大小开销较大。使用object同样可以完成顺序表数据结构，但是频繁装箱拆箱造成较大的开销，应使用泛型代替。
usingSystem;
usingSystem.Collections.Generic;
usingSystem.Linq;
usingSystem.Text;
namespaceLinearList
{
publicinterfaceIListDS<T>
{
intGetLength();
voidInsert(Titem,inti);
voidAdd(Titem);
boolIsEmpty();
TGetElement(inti);
voidDelete(inti);
voidClear();
intLocateElement(Titem);
voidReverse();
}
//顺序表类
classSequenceList<T>:IListDS<T>
{
privateintintMaxSize;//最大容量事先确定，使用数组必须先确定容量
privateT[]tItems;//使用数组盛放元素
privateintintPointerLast;//始终指向最后一个元素的位置
publicintMaxSize
{
get{returnthis.intMaxSize;}
set{this.intMaxSize=value;}
}
publicTthis[inti]//索引器方便返回
{
get{returnthis.tItems[i];}
}
publicintPointerLast
{
get{returnthis.intPointerLast;}
}
publicSequenceList(intsize)
{
this.intMaxSize=size;
this.tItems=newT[size];//在这里初始化最合理
this.intPointerLast=-1;//初始值设为-1，此时数组中元素个数为0
}
publicboolIsFull()//判断是否超出容量
{
returnthis.intPointerLast+1==this.intMaxSize;
}
#regionIListDS<T>成员
publicintGetLength()
{
returnthis.intPointerLast+1;//不能返回tItems的长度
}
publicvoidInsert(Titem,inti)//设i为第i个元素，从1开始。该函数表示在第i个元素后面插入item
{
if(i<1||i>this.intPointerLast+1)
{
Console.WriteLine("Theinsertinglocationiswrong!");
return;
}
if(this.IsFull())
{
Console.WriteLine("Thislinearlistisfull!Can'tinsertanynewitems!");
return;
}
//如果可以添加
this.intPointerLast++;
for(intj=this.intPointerLast;j>=i+1;j--)
{
this.tItems[j]=this.tItems[j-1];
}
this.tItems[i]=item;
}
publicvoidAdd(Titem)
{
if(this.IsFull())//如果超出最大容量，则无法添加新元素
{
Console.WriteLine("Thislinearlistisfull!Can'taddanynewitems!");
}
else
{
this.tItems[++this.intPointerLast]=item;//表长+1
}
}
publicboolIsEmpty()
{
returnthis.intPointerLast==-1;
}
publicTGetElement(inti)//设i最小从0开始
{
if(this.intPointerLast==-1)
{
Console.WriteLine("Therearenoelementsinthislinearlist!");
returndefault(T);
}
if(i>this.intPointerLast||i<0)
{
Console.WriteLine("Exceedthecapability!");
returndefault(T);
}
returnthis.tItems[i];
}
publicvoidDelete(inti)//设i最小从0开始
{
if(this.intPointerLast==-1)
{
Console.WriteLine("Therearenoelementsinthislinearlist!");
return;
}
if(i>this.intPointerLast||i<0)
{
Console.WriteLine("Deletinglocationiswrong!");
return;
}
for(intj=i;j<this.intPointerLast;j++)
{
this.tItems[j]=this.tItems[j+1];
}
this.intPointerLast--;//表长-1
}
publicvoidClear()
{
this.intPointerLast=-1;
}
publicintLocateElement(Titem)
{
if(this.intPointerLast==-1)
{
Console.WriteLine("Therearenoitemsinthelist!");
return-1;
}
for(inti=0;i<=this.intPointerLast;i++)
{
if(this.tItems[i].Equals(item))//若是自定义类型，则T类必须把Equals函数override
{
returni;
}
}
Console.WriteLine("Notfound");
return-1;
}
publicvoidReverse()
{
if(this.intPointerLast==-1)
{
Console.WriteLine("Therearenoitemsinthelist!");
}
else
{
inti=0;
intj=this.GetLength()/2;//结果为下界整数，正好用于循环
while(i<j)
{
Ttmp=this.tItems[i];
this.tItems[i]=this.tItems[this.intPointerLast-i];
this.tItems[this.intPointerLast-i]=tmp;
i++;
}
}
}
#endregion
}
classProgram
{
staticvoidMain(string[]args)
{
}
}
}
基于顺序表的合并排序：
//基于顺序表的合并排序
staticprivateSequenceList<int>Merge(SequenceList<int>s1,SequenceList<int>s2)
{
SequenceList<int>sList=newSequenceList<int>(20);
inti=0;
intj=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++;
}
returnsList;
}
else//即j>s2.PointerLast
{
while(i<=s1.PointerLast)
{
sList.Add(s1[i]);
i++;
}
returnsList;
}
}
更多关于C#相关内容感兴趣的读者可查看本站专题：《C#数据结构与算法教程》、《C#遍历算法与技巧总结》、《C#程序设计之线程使用技巧总结》、《C#操作Excel技巧总结》、《C#中XML文件操作技巧汇总》、《C#常见控件用法教程》、《WinForm控件用法总结》、《C#数组操作技巧总结》及《C#面向对象程序设计入门教程》
希望本文所述对大家C#程序设计有所帮助。