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

C#数据结构之顺序表(SeqList)实例详解

程序员文章站 2022-06-25 08:51:02
本文实例讲述了c#数据结构之顺序表(seqlist)实现方法。分享给大家供大家参考,具体如下: 线性结构(linear stucture)是数据结构(data struc...

本文实例讲述了c#数据结构之顺序表(seqlist)实现方法。分享给大家供大家参考,具体如下:

线性结构(linear stucture)是数据结构(data structure)中最基本的结构,其特征用图形表示如下:

C#数据结构之顺序表(SeqList)实例详解

即:每个元素前面有且只有一个元素(称为“前驱”),同样后面有且只有一个元素(称为"后继")--注:起始元素的前驱认为是空,末尾元素的后继认为也是空,这样在概念上就不冲突了。

线性表(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#程序设计有所帮助。