数据结构与算法(三)线性表的顺序存储结构

发布时间:2019-11-28 21:22:32 阅读:28

    首先,我们大概先了解下什么是线性表。

    线性表:零个或多个数据元素的有限数列。

    数据元素 1 对 1的关系,这种关系是位置关系。

    线性表元素个数n(n>=0)定义为线性表的长度,当n=0时,称为空表。

     

    然后我们了解一下数据类型和抽象数据类型

    一.数据类型

    先看看为什么会有不同的数据类型呢?很简单,很多东西不能一概而论,而是需要更精确的划分。计算机计算1+1并不需要多么大的空间,但是计算10000000000+1000000000就得需要有个比较大的空间来放。还有有时候会计算小数,小数的位数不一样,需要的空间也就不一样。数字1和字母a也需要区分啊,于是开发者就想出了“数据类型”这一招,用来描述不同的数据的集合。

    我记得最早接触的数据类型就是int了。当初一个int a;就把我看得神魂颠倒,不知所以。像这种类型,就是一个基本的数据类型。以前总以为数据类型就是一个描述数据到底是什么玩意儿的东东,现在再去看,倒是有点儿浅了。数据类型学术点呢,是一个值的集合和定义在这个值集合的一组操作的总称。一种数据类型也可以看成是一种已经实现了的“数据结构”。

    按“值”是否可分解,将其分为两类:

    1.原子类型:其值不可分解,通常由语言直接提供,像C++中的int,float,double等等。

    2.结构类型:其值可以分解为若干部分(分量),是程序员自定义的,比如结构体,类等等。

    ps:对于什么是“原子”,经常会看到什么“原子操作”,“原子类型”,一般就是指不可再分的。

     

    二.抽象的数据类型

    抽象数据类型(abstract data type,ADT)只是一个数学模型以及定义在模型上的一组操作。通常是对数据的抽象,定义了数据的取值范围以及对数据操作的集合。

    其实,数据类型和抽象数据类型可以看成一种概念。比如,各种计算机都拥有的整数类型就是一个抽象数据类型,尽管实现方法不同,但他们的数学特性相同。

    抽象数据类型的特征是实现与操作分离,从而实现封装。

    看到有人举出了“超级玛丽”例子,觉得写得很不错,如下:

    就像“超级玛丽”这个经典的任天堂游戏,里面的游戏主角是马里奥,我们给他定义了基本操作,前进、后退、跳、打子弹等。这就是一个抽象数据类型,定义了一个数据对象、对象中各元素之间的关系及对数据元素的操作。至于,到底是哪些操作,这只能由设计者根据实际需要来定。像马里奥可能开始只能走和跳,后来发现应该增加一种打子弹的操作,再后来又有了按住打子弹键后前进就有跑的操作。这都是根据实际情况来定的。

    事实上,抽象数据类型体现了程序设计中问题分解和信息隐藏的特征。它把问题分解为多个规模较小且容易处理的问题,然后把每个功能模块的实现为一个独立单元,通过一次或多次调用来实现整个问题。

     

    最后进重点,线性表的顺序存储结构

    u=3642763191,618991523&fm=214&gp=0.jpg

    1:定义

    线性表的顺序存储结构,指的是用一段地址连续的存储单元依次存储线性表的数据元素。

     

    2:顺序存储属性

    我觉得,举一个比较恰当的列子就是强语法语言中的数组。一个萝卜一个坑,每个元素都有自己固定的位置。

    (1):存储空间的起始位置

    (2):线性表的最大存储容量

    (3):线性表的当前长度

     

    3:地址计算方法

    这里需要注意一下,线性表是从1开始的。

    我们的下标是从0开始的。

     

     

    下边我们写一个线性表顺醋存储结构的小例子:我这里使用的是C#。

    文末有实例,可下载。

    首先定义一个线性表顺序存储结构的接口类:ILineTotal.cs

    /// <summary>
        /// 泛型接口
        /// </summary>
        /// <typeparam name="T">数据类型</typeparam>
        interface ILineTotal<T>
        {
            /// <summary>
            /// 是否为空
            /// </summary>
            /// <returns></returns>
            bool IsEmptyTableLine();
            /// <summary>
            /// 根据下标获取数据
            /// </summary>
            T GetTableData(int index);
            /// <summary>
            ///  在中间插入数据
            /// </summary>
            bool InsertTableData(T data, int Index);
            /// <summary>
            /// 是否是最大长度
            /// </summary>
            /// <returns>true/false</returns>
            bool IsMaxSize();
            /// <summary>
            /// 在末尾插入数据
            /// </summary>
            /// <param name="data"></param>
            /// <returns></returns>
            bool InsertTableEndData(T data);
            /// <summary>
            ///
            /// </summary>
            /// <param name="index"></param>
            /// <returns></returns>
            bool DeleteTableData(int index);
            /// <summary>
            /// 清空表
            /// </summary>
            /// <returns></returns>
            bool ClearTableData();
            /// <summary>
            /// 翻转数组
            /// </summary>
            /// <returns></returns>
            bool FlipTableLine();
            /// <summary>
            /// 返回元素索引,如果这个元素在线性表中
            /// </summary>
            /// <param name="item"></param>
            /// <returns></returns>
            int ReturnDataIndex(T item);
        }

     

    线性表顺序存储结构类:tableLine.cs

    /// <summary>
        /// 线性表顺序存储结构类(泛型类)
        /// </summary>
        class tableLine<T> :ILineTotal<T>
        {
            /// <summary>
            /// 定义一个数组
            /// </summary>
            public T[] TArray = null;
            /// <summary>
            /// 数组最大下标
            /// </summary>
            public int MaxSize = 0;
            /// <summary>
            /// 最后一个数据索引
            /// </summary>
            public int lastDataIndex = 0;
            /// <summary>
            /// 构造函数
            /// </summary>
            /// <param name="lenght">线性表长度</param>
            public tableLine(int length)
            {
                MaxSize = length - 1;
                // 定义一个线性表
                TArray = new T[length];
            }
            /// <summary>
            /// 是否为空的线性表
            /// </summary>
            /// <returns></returns>
            public bool IsEmptyTableLine()
            {
                try
                {
                    if (TArray.GetLength(0) > 0)
                    {
                        return false;
                    }
                    else
                    {
                        return true;
                    }
                }
                catch (Exception)
                {
                    Console.WriteLine("IsEmptyTableLine出错");
                    return false;
                }
            }
            /// <summary>
            /// 根据下标获取数据
            /// </summary>
            public T GetTableData(int index)
            {
                T data = TArray[index];
                return data;
            }
            /// <summary>
            /// 在中间插入数据
            /// 一个萝卜一个坑,有人插队,其余数据下标后移
            /// </summary>
            /// <param name="data">要插入的数据</param>
            /// <param name="Index">插入的下标</param>
            public bool InsertTableData(T data, int Index)
            {
                try
                {
                    // 如果数组超出最大长度
                    if (IsMaxSize())
                    {
                        Console.WriteLine("数组已满");
                        return false;
                    }
                    lastDataIndex++;
                    // 现将这个索引本身及其之后的数据向后挪一位(最大下标加一)
                    for (int i = lastDataIndex + 1; i > Index; i--)
                    {
                        TArray[i] = TArray[i - 1];
                    }
                    // 插入
                    TArray[Index] = data;
                    return true;
                }
                catch (Exception)
                {
                    Console.WriteLine("在中间插入数据出错");
                    return false;
                }
            }
            /// <summary>
            /// 是否是最大长度
            /// </summary>
            /// <returns></returns>
            public bool IsMaxSize()
            {
                if (lastDataIndex >= MaxSize)
                {
                    return true;
                }
                else
                {
                    return false;
                }
            }
            /// <summary>
            /// 在末尾插入数据
            /// </summary>
            public bool InsertTableEndData(T data)
            {
                try
                {
                    // 如果数组超出最大长度
                    if (IsMaxSize())
                    {
                        return false;
                    }
                    lastDataIndex++;
                    TArray[lastDataIndex] = data;
                    return true;
                }
                catch (Exception)
                {
                    Console.WriteLine("在末尾插入数据出错");
                    return false;
                }
               
            }
            /// <summary>
            /// 删除指定下标数据
            /// </summary>
            public bool DeleteTableData(int index)
            {
                // 数据长度
                int dataLength = TArray.Length;
                if (index > dataLength - 1)
                {
                    Console.WriteLine("传入下标超出了数组范围");
                    return false;
                }
                for (int i = index; i < lastDataIndex; i++)
                {
                    TArray[i] = TArray[i + 1];
                }
                TArray[lastDataIndex] = default(T);
                lastDataIndex--;
                return true;
            }
            /// <summary>
            /// 清空表
            /// </summary>
            public bool ClearTableData()
            {
                try
                {
                    if (TArray.Length <= 0)
                    {
                        Console.WriteLine("数据表为空");
                    }
                    Array.Clear(TArray, 0, TArray.Length);
                    return true;
                }
                catch (Exception)
                {
                    Console.WriteLine("清空线性表出错");
                    return false;
                }
               
            }
            /// <summary>
            /// 翻转线性表
            /// </summary>
            public bool FlipTableLine()
            {
                Array.Reverse(TArray);
                return true;
            }
            /// <summary>
            /// 返回元素索引,如果这个元素在线性表中
            /// </summary>
            public int ReturnDataIndex(T item)
            {
                int index = Array.IndexOf(TArray, item); // 这里的1就是你要查找的值
                return index;
            }
        }

     

    客户端调用:Program.cs

    static void Main(string[] args)
            {
                // 最后一个数据的索引
                int lastDataIndex = 0;
                // 实例化一个线性表
                tableLine<int> tableLineObj = new tableLine<int>(10);
                lastDataIndex = tableLineObj.TArray.Length - 3;
                for (int i = 0; i < tableLineObj.TArray.Length - 2; i++)
                {
                    tableLineObj.TArray[i] = i + 1;
                    Console.WriteLine(tableLineObj.TArray[i]);
                }
                // 最后一个下标赋值
                tableLineObj.lastDataIndex = lastDataIndex;
                // 查看线性表是否为空
                bool isEmpty =  tableLineObj.IsEmptyTableLine();
                Console.WriteLine("线性表为空:"+ isEmpty);
                Console.WriteLine("=================================================================");
     
                int fiveData = tableLineObj.GetTableData(4);
                Console.WriteLine("第五个数为:"+ fiveData);
                Console.WriteLine("=================================================================");
     
                bool insertRes = tableLineObj.InsertTableData(100,4);
                Console.WriteLine("中间插入数据:"+ insertRes);
     
                for (int i = 0; i < tableLineObj.TArray.Length; i++)
                {
                    Console.WriteLine(tableLineObj.TArray[i]);
                }//*/
                Console.WriteLine("=================================================================");
     
                bool insertEnd = tableLineObj.InsertTableEndData(50);
                Console.WriteLine("末尾追加插入数据:" + insertEnd);
                for (int i = 0; i < tableLineObj.TArray.Length; i++)
                {
                    Console.WriteLine(tableLineObj.TArray[i]);
                }
                Console.WriteLine("=================================================================");
     
                bool deleteRes = tableLineObj.DeleteTableData(3);
                Console.WriteLine("删除指定下标数据:" + deleteRes);
                for (int i = 0; i < tableLineObj.TArray.Length; i++)
                {
                    Console.WriteLine(tableLineObj.TArray[i]);
                }
                Console.WriteLine("=================================================================");
     
                bool flipRes = tableLineObj.FlipTableLine();
                Console.WriteLine("反转线性表:" + flipRes);
                for (int i = 0; i < tableLineObj.TArray.Length; i++)
                {
                    Console.WriteLine(tableLineObj.TArray[i]);
                }
                Console.WriteLine("=================================================================");
     
                int dataIndex = tableLineObj.ReturnDataIndex(100);
                Console.WriteLine("100对应的下标:" + dataIndex);
                Console.WriteLine("=================================================================");
     
                /*bool clearRes = tableLineObj.ClearTableData();
                Console.WriteLine("清空线性表:" + clearRes);
                for (int i = 0; i < tableLineObj.TArray.Length; i++)
                {
                    Console.WriteLine(tableLineObj.TArray[i]);
                }
    Console.WriteLine("=================================================================");//*/
                Console.ReadKey();
            }

     

    大概例子就是这样。


    最后说下顺序存储结构的优缺点:

    优点:

    1:无须为表中元素之间的逻辑关系而增加额外的存储空间。

    2:可以快速的存取表中任一位置的元素。

    缺点:

    1:插入和删除操作需要移动大量元素

    2:当线性表长度变化较大时,难以确定存储空间的容量

    3:造成存储空间的“碎片”


    文末有例子可下载。

    有好的建议,请在下方输入你的评论。

关键字数据结构 算法