用顺序表解决线性表的编程问题

àì夳堔傛蜴生んèń 2021-09-18 03:16 314阅读 0赞

用顺序表解决线性表的编程问题 ：

数据结构在计算机中的表示称为存储结构。存储结构有顺序存储结构和链式存储结构。这里讨论顺序存储结构

顺序表的存储结构可用C\#中的一维数组来表示。数组的元素类型使用泛型，以实现不同数据类型的线性表间代码的重用；因为用数组存储顺序表，需预先为顺序表分配最大存储空间，用字段maxsize表示顺序表的最大长度；由于经常需要在顺序表中插入或删除数据元素，顺序表的实际表长是可变的，用length字段表示顺序表的实际长度。

using System;
    
    namespace 用顺序表解决线性表的编程问题
    {
        class Program
        {
            static void Main(string[] args)
            {
    
            }
        }
    
    
        interface IlinarList<T>
        {
            void InsertNode(T a, int i);//插入数据元素(这里只讲前插)是指假设顺序表中已有length (0<=length<=maxsize-1)个数据元素，在第i (1<=i<=length+1)个数据元素位置插入一个新的数据元素
            void DeleteNode(int i);     //删除数据元素.
            T SearchNode(int i);//查找表元素
            T SearchNode(T value);//定位元素
            int GetLength();//求表长度
            void Clear();//清空操作
            bool IsEmpty();//判断线性表是否为空
        }
    
        public class SeqList<T> : IlinarList<T>
        {
            private int maxsize;//顺序表的最大容量
            private T[] data;//数组,用于存储顺序表中的数据元素
            private int length;//顺序表的实际长度
    
            /// <summary>
            /// 实际长度属性
            /// </summary>
            public int Length
            {
                get { return length; }
            }
    
            /// <summary>
            /// 最大容量属性
            /// </summary>
            public int Maxsize
            {
                get { return maxsize; }
                set { maxsize = value; }
            } 
    
            /// <summary>
            /// 初始化线性表
            /// </summary>
            /// <param name="size"></param>
            public SeqList (int size)
            {
                maxsize = size;
                data = new T[maxsize];
                length = 0;
            }
    
            /// <summary>
            /// 判断顺序表是否已满
            /// </summary>
            /// <returns></returns>
            public bool IsFull()
            {
                if(length ==maxsize)
                {
                    return true;
                }else
                {
                    return false;
                }
            }
    
            /// <summary>
            /// 清空数据表
            /// </summary>
            public void Clear()
            {
                length = 0;
            }
    
            /// <summary>
            /// 假设顺序表中已有length (1<=length<=maxsize)个数据元素，删除指定位置i的数据元素
            /// </summary>
            /// <param name="i"></param>
            public void DeleteNode(int i)
            {
                if(IsEmpty())
                {
                    Console.WriteLine("List is empty");
                    return;
                }else if(i<1||i>length)
                {
                    Console.WriteLine("Position is error!");
                    return;
                }else
                {
                    for (int j = i; j < length; j++) // for (int j=length - 1; j >= i; j--)感觉也可以，但是没试过
                    {
                        data[j - 1] = data[j];
                    }
                    length--;
                }
                
            }
    
            /// <summary>
            /// 数据表的长度
            /// </summary>
            /// <returns></returns>
            public int GetLength()
            {
                return length;
            }
    
            /// <summary>
            /// 由于没有参数i,意味着没有指定插入位置i，所以此函数表示在顺序表的末尾追加数据元素
            /// </summary>
            /// <param name="a"></param>
            public void InsertNode(T a)
            {
                if(IsFull())
                {
                    Console.WriteLine("List is full");
                    return;
                }else
                {
                    data[length] = a;
                    length++;
                }
                
            }
            /// <summary>
            /// 指定了插入位置i，如果i<1||i>length+1,则无法插入数据元素
            /// </summary>
            /// <param name="a"></param>
            /// <param name="i"></param>
            public void InsertNode(T a, int i)
            {
                if(IsFull())
                {
                    Console.WriteLine("List is full");
                    return;
                }else if (i<1||i>length + 1)
                {
                    Console.WriteLine("Position is error!");
                    return;
                }else
                {
                    for (int j=length - 1; j <= i - 1; j--)
                    {
                        data[j + 1] = data[j];
                    }
                    data[i - 1] = a;
                }
                length++;
            }
    
            /// <summary>
            /// 判断顺序表是否为空
            /// </summary>
            /// <returns></returns>
            public bool IsEmpty()
            {
                if(length == 0)
                {
                    return true;
                }else
                {
                    return false;
                }
            }
    
            /// <summary>
            /// 获得顺序表的第i个数据元素
            /// </summary>
            /// <param name="i"></param>
            /// <returns></returns>
            public T SearchNode(int i)
            {
                if(IsEmpty())
                {
                    Console.WriteLine("List is empty");
                    return default(T ) ;
                }else if(i<1||i>length)
                {
                    Console.WriteLine("Position is error");
                    return default(T );
                }
                return data[i - 1];
            }
    
            /// <summary>
            /// 在顺序表中查找值为value的数据元素
            /// </summary>
            /// <param name="value"></param>
            /// <returns></returns>
            public T SearchNode(T value)
            {
                if(IsEmpty())
                {
                    Console.WriteLine("List is empty");
                    return default(T);
                }
                int i = 0;
                for (i = 0; i < length; i++)
                {
                    if(data [i].ToString ().Contains (value .ToString()))
                    {
                        break;
                    }
                }
                if(i>=length)
                {
                    return default(T);
                }
                return data[i];
            }
        }
    }