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

简介: 线性表:零个或多个数据元素的有限数列。数据元素 1 对 1的关系,这种关系是位置关系。线性表元素个数n(n>=0)定义为线性表的长度,当n=0时,称为空表。

QQ图片20220425214541.jpg

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


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


数据元素 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)只是一个数学模型以及定义在模型上的一组操作。通常是对数据的抽象,定义了数据的取值范围以及对数据操作的集合。


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


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


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


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


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

 

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


QQ图片20220425214544.png


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:造成存储空间的“碎片”



目录
相关文章
|
23天前
|
存储 搜索推荐 算法
【数据结构】树型结构详解 + 堆的实现(c语言)(附源码)
本文介绍了树和二叉树的基本概念及结构,重点讲解了堆这一重要的数据结构。堆是一种特殊的完全二叉树,常用于实现优先队列和高效的排序算法(如堆排序)。文章详细描述了堆的性质、存储方式及其实现方法,包括插入、删除和取堆顶数据等操作的具体实现。通过这些内容,读者可以全面了解堆的原理和应用。
61 16
|
27天前
|
算法 测试技术 开发者
在Python开发中,性能优化和代码审查至关重要。性能优化通过改进代码结构和算法提高程序运行速度,减少资源消耗
在Python开发中,性能优化和代码审查至关重要。性能优化通过改进代码结构和算法提高程序运行速度,减少资源消耗;代码审查通过检查源代码发现潜在问题,提高代码质量和团队协作效率。本文介绍了一些实用的技巧和工具,帮助开发者提升开发效率。
34 3
|
2月前
|
存储 缓存 算法
如何通过优化算法和代码结构来提升易语言程序的执行效率?
如何通过优化算法和代码结构来提升易语言程序的执行效率?
|
2月前
|
存储 安全 数据库
除了 HashMap,还有哪些数据结构可以实现键值对存储?
【10月更文挑战第11天】 除了`HashMap`,其他常见支持键值对存储的数据结构包括:`TreeMap`(基于红黑树,键有序)、`LinkedHashMap`(保留插入顺序)、`HashTable`(线程安全)、`B-Tree`和`B+Tree`(高效存储大量数据)、`SkipList`(通过跳跃指针提高查找效率)及`UnorderedMap`(类似`HashMap`)。选择合适的数据结构需根据排序、并发、存储和查找性能等需求。
|
2月前
|
存储 Java
数据结构第二篇【关于java线性表(顺序表)的基本操作】
数据结构第二篇【关于java线性表(顺序表)的基本操作】
31 6
|
27天前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之王道第2.3章节之线性表精题汇总二(5)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
IKU达人之数据结构与算法系列学习×单双链表精题详解、数据结构、C++、排序算法、java 、动态规划 你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
2月前
|
存储
【数据结构】线性表和顺序表
【数据结构】线性表和顺序表
22 1
|
2月前
探索顺序结构:栈的实现方式
探索顺序结构:栈的实现方式
|
2月前
01(数据结构考研)线性表相关操作代码
01(数据结构考研)线性表相关操作代码
72 0
|
2月前
|
存储 算法
【数据结构】二叉树——顺序结构——堆及其实现
【数据结构】二叉树——顺序结构——堆及其实现
下一篇
无影云桌面