数据结构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>就是一个内置的顺序表.

上一篇:数据结构与算法(一) 线性表之顺序表


下一篇:写正则表达式的一些小工具