C#实现顺序表(线性表)完整实例

本文实例讲述了C#实现顺序表(线性表)的方法。分享给大家供大家参考，具体如下：

基本思想是使用数组作为盛放元素的容器，数组一开始的大小要实现确定，并使用一个Pointer指向顺序表中最后的元素。顺序表中的元素是数组中元素的子集。顺序表在内存中是连续的，优势是查找，弱势是插入元素和删除元素。

为避免装箱拆箱，这里使用泛型，代替object。使用object的例子可以参照本站这篇文章：https://www.jb51.net/article/87603.htm，这个链接中的例子实现的是队列，并没 有使用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#程序设计有所帮助。