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

这是我参与11月更文挑战的第23天，活动详情查看：2021最后一次更文挑战

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

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

数据元素 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

csharp复制代码/// <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

csharp复制代码/// <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

arduino复制代码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：造成存储空间的“碎片”

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

欢迎访问个人博客
guanchao.site

欢迎访问小程序：

在这里插入图片描述

本文转载自: 掘金

开发者博客 – 和开发相关的这里全都有