欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2023-11-08 15:10:34
本文实例讲述了c#实现顺序表(线性表)的方法。分享给大家供大家参考,具体如下: 基本思想是使用数组作为盛放元素的容器,数组一开始的大小要实现确定,并使用一个pointer...

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

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

为避免装箱拆箱,这里使用泛型,代替object。使用object的例子可以参照本站这篇文章:,这个链接中的例子实现的是队列,并没 有使用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#相关内容感兴趣的读者可查看本站专题:《c#数据结构与算法教程》、《c#遍历算法与技巧总结》、《c#程序设计之线程使用技巧总结》、《c#操作excel技巧总结》、《c#中xml文件操作技巧汇总》、《c#常见控件用法教程》、《winform控件用法总结》、《c#数组操作技巧总结》及《c#面向对象程序设计入门教程

希望本文所述对大家c#程序设计有所帮助。