开发者社区> yuanrengu> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

线性表简介

简介: 学习数据结构 -> 线性表 -> 线性表的介绍     线性表是一种典型的数据结构, 线性结构的基本特点是线性表中的数据元素是有序且有限的, 在线性结构中, 有且仅有一个被称为"开始数据元素"和一个"最后数据元素", 除了开始数据元素没有直接前驱, 最后一个数据元素没有直接后继外, 其余的数据元素有且仅有唯一的一个直接前驱和直接后继。
+关注继续查看

学习数据结构 -> 线性表 -> 线性表的介绍



    线性表是一种典型的数据结构, 线性结构的基本特点是线性表中的数据元素是有序且有限的, 在线性结构中, 有且仅有一个被称为"开始数据元素"和一个"最后数据元素", 除了开始数据元素没有直接前驱, 最后一个数据元素没有直接后继外, 其余的数据元素有且仅有唯一的一个直接前驱和直接后继。
    
    整理下来说, 线性表具有如下基本特征:
        1>. 线性结构中必然存在唯一一个"开始数据元素" ;
        2>. 线性结构中必然存在唯一一个"最后数据元素" ;
        3>. 除第一个数据元素外, 其他元素均有唯一一个直接前驱 ;
        4>. 除最后一个数据元素外, 其他元素均有唯一一个直接后继 。
        

一、线性表的定义
    线性结构的举例:
        ①. 英文大写字母表: a = { A, B, C, ..., X, Y, Z } ;
        ②. 一星期中的七天: a = { MONDAY, TUESDAY, WEDNESDAY, THUREDAY, FRIDAY, SATURDAY, SUNDAY } ;
    像这样, 由长度为n(n ≥ 0)的一组结点 a1, a2, ..., an 组成的有限序列称为线性表, 其中线性表中的每个成员称为线性表的结点。
    当 n  = 0 时, 线性表为空, 称为空表。
    如果 n > 0 , 则 a1 是线性表的第一个元素, an 是最后一个元素, 表中每一个结点ai(1 < i < n)都有唯一一个直接前驱a(i-1)和直接后继a(i+1)。
    

二、线性表的逻辑结构
    在线性表中, 一个数据元素是可以由若干数据项(Data Item)组成, 如学生成绩情况表, 在该线性表中, 任意数据元素 ai 包含了学生的学号、姓名、课程名称、分数等数据项。
    
    线性表的长度可根据需要增长或缩短, 而且, 非空线性表中的每一个元素都有一个确切的位置。也就是说, 对于线性表的数据元素不仅可以进行访问, 而且还可以进行插入、删除等操作。
    
    线性表中的数据元素的类型可以是多种多样的, 但在同一线性表中的数据元素必定具有相同的特性, 即同一线性表中的元素是属于同一数据对象, 且相邻的数据元素之间存在着一种序偶关系。
    

三、线性表的基本运算
    对于一个线性表, 有可能进行的操作如下:
        ● 创建一个线性表 ;
        ● 判断线性表是否为空 ;
        ● 确定线性表的长度 ;
        ● 查找第 k 个元素 ;
        ● 查找指定的元素 ;
        ● 删除第 k  个元素 ;
        ● 在第 k 个元素之前插入一个新元素 ;
        ● 销毁一个线性表。
        
    因此我们可以先定义线性表如下的基本运算:
        1>. 初始化线性表 InitiaList(L)
            初始条件: 无
            操作结果: 构造一个空的或者人们所需要的线性表L, 并返回线性表L 。
            
        2>. 线性表置空 SetNullList(L)
            初始条件: 线性表L已存在
            操作结构: 将已存在的线性表L置空, 并返回线性表L。
            
        3>. 求线性表的长度 GetListLength(L)
            初始条件: 线性表L已存在
            操作结构: 返回线性表L中的数据元素个数。
            
        4>. 找出线性表的第 i 个结点 GetListItem( L, i )
            初始条件: 线性表L已存在, 且 1 ≤ i ≤ n
            操作结果: 若初始条件满足, 则返回第 i 项数据元素, 否则返回NULL。
            
        5>. 取线性表中值为 x 的数据元素的直接前驱 GetItemPrior( L, x )
            初始条件: 线性表 L 已存在, 且数据 x 所在的位置 i 应满足 2 ≤ i ≤ n
            操作结果: 若 x 是线性表 L 中的数据元素, 并且不是第一个, 则返回该数据元素的直接前驱, 否则返回 NULL 。
            
        6>. 取线性表中值为 x 的数据元素的直接后继 GetItemNext( L, x )
            初始条件: 线性表 L 已存在, 且数据 x 所在的位置 i 应满足 1 ≤ i ≤ n-1
            操作结果: 若 x 是线性表 L 中的数据元素, 并且不是最后一个, 则返回该数据元素的直接后继, 否则返回 NULL 。
            
        7>. 插入结点 InsertItem( L, i, b )
            初始条件: 线性表L已经存在, 且 1 ≤ i ≤ n+1
            操作结果: 在线性表 L 中的第  i 项数据前插入一个新的且值为 b 的数据元素, 线性表 L 的长度增加 1。
            
        8>. 删除结点 DeleteItem( L, i )
            初始条件: 线性表 L 已存在, 且 1 ≤ i ≤ n
            操作结果: 将线性表 L 中的第 i 项数据元素删除, 线性表L的长度减 1。
            
    在以后实现线性表的运算中, 可以通过以上基本运算组合完成。
    

四、线性表的 ADT 描述
    线性表可以用一个抽象数据类型( Abstract Data Type, ADT )来进行描述, 描述如下:
    
    抽象数据类型 ADT LinearList
    {
        数据对象: D = { ai | ai ∈ ElemSet, i = 1, 2, ..., n, n ≥ 0 }
        数据关系: R = { < a(i-1), ai > | a(i-1), ai ∈ D, i = 2, 3, ..., n }
        基本操作:
            Create() : 创建一个空的线性表
            Destroy() : 销毁表
            IsEmpty() : 如果表为空则返回true, 否则返回false
            Length() : 返回表中的元素个数
            Find( k, x ): 寻找表中第 k 个元素, 若找到, 将他保存在 x 中, 若不存在, 则返回 false
            Index( x ) : 返回元素 x 在表中的位置, 若不再表中, 则返回 0
            Delete( k, x ) : 删除表中的第 k 个元素, 并把它保存到 x 中, 函数返回修改后的线性表
            Insert( k, x ) : 在第 k 个元素前插入 x , 函数返回修改后的线性表
    }
    

五、线性表的顺序存储
    在计算机内, 可以使用使用顺序存储结构和链式存储结构来表示线性表.
    
    线性表的顺序存储是指用一组连续的存储单元来存储线性表, 例如可以将线性表 N = { 10, 20, 30, 40, 50, 60, 70, 80, 90, 100 } 按如图所示的方式来存储:


    顺序存储就是把线性表的每一个元素一个接一个地存放在一块连续的存储单元中, 采用顺序存储方式存储的线性表又称为顺序表, 其特点如下:
        ①. 线性表的逻辑顺序与物理顺序一致 ;
        ②. 数据元素间的关系采用物理位置的相邻关系来实现。
    假设线性表中的每个元素需要占用c个存储单元, 并以所占的第一个单元的存储地址作为数据元素的存储起始位置, 那么线性表中第 i 个元素的存储位置 LOC(ai) 和第 i-1 个元素的存储位置 LOC( a(i-1) ) 之间满足下列关系:

        LOC(ai) = LOC( a(i-1) + c )


    假设线性表中第一个数据元素 a1 所在的存储地址为 : LOC(a1), 每个数据元素在计算机的存储器中占 c 个存储单元, 那么由线性表的特性可知, 线性表中第 i 个数据元素在计算机中的存储器中的存储地址为:

        LOC(ai) = LOC(a1) + (i-1)*c


    因此, 一旦线性表的起始地址确定, 每个元素在计算机存储器中所占的存储单元大小确定, 那么就可以计算出线性表中任意数据元素的存储地址。 所以, 线性表的顺序存储结构可以理解为线性表的随机存储结构。
    
    在高级程序设计语言中, 由于数组具有随机存取的特性, 因此人们通常借助于一个数组来描述数据结构中的顺序存储结构, 这样线性表的顺序存储结构的形式定义为:
   

    #define MacLen    <线性表可能的最大长度>
    typedef struct sequenlist
    {
        elementtype elements[MaxLen] ;      //数据元素值得数据类型
        int length ;                        //线性表中当前的元素个数
    }List ;


    其中, elementtype 可以是一个简单的数据类型, 也可以是一个复合的数据类型。
    ①. 简单的数据类型示例:

        char elementtype[128] ;

       
    ②. 复合数据类型的示例:

        typedef struct etype
        {
            char     no[10] ;
            char     name[60] ;
            float     score ;
        }elementtype ;


           
            
六、线性表的链式存储
    链式存储是指在计算机中用一组任意的存储单元(可以是连续的, 也可以是不连续的)存储线性表的数据元素, 链式存储结构域顺序存储结构主要有以下两点不同:
        1>. 两连续元素间的物理位置不必相邻 ;
        2>. 不要求结点在存储单元中的存放次序与线性表顺序一致。也就是说, 在链式存储结构中, 元素所存放的位置可以是任意的。
        
    链式存储结构存储线性表 L = { a, b, c, d, e } 的示意图:


    
    在链式存储结构中仅知道一个元素的位置其他元素的位置是不能再确定的, 为了能够显示每个结点在线性表中的次序以及所在的位置, 除了保存结点的值外, 还必须设有一个指向下一个结点存放地址的信息, 这样每一个结点就分为两个域, 一是存储数据元素信息的域, 称为数据域, 二是存储后继结点所在地址的域, 称为指针域, 指针域中存储的信息称为指针或链。 将 n 个结点链接起来就构成了链表(Linked List)。 链表的结点结构如 图a 所示, 链表的结构如 图b 所示。
   


    像这样, 我们把只包含一个指针域的链表称为单链表。 在该单链表中, 结点值为a的结点为结点值为b的结点的直接前驱结点, 结点值为c的结点为结点值为b的结点的后继结点。 结点值为a的结点没有直接前驱结点, 结点值为e的结点没有直接后继结点。
    
    根据以上说明, 线性表的链式存储结构的形式可定义为:

    typedef struct node
    {
        elementtype data ;        //结点的数据域
        struct node *next ;        //结点的指针域
    }LinkList ;


    这样, 线性表 L = { a0, a1, a2, ..., an } 在上述的存储结构存储的图示如下:


    有时, 人们为了操作方便, 总是在链表的第一个结点之前附设一个结点, 称之为头结点(Head Node)。头结点的数据域可以不存储任何信息, 也可以存储如链表的长度等附加信息, 如图所示:

 



--------------------

转自:http://www.cnblogs.com/mr-wid/archive/2012/12/07/2807817.html

 

img_e00999465d1c2c1b02df587a3ec9c13d.jpg
微信公众号: 猿人谷
如果您认为阅读这篇博客让您有些收获,不妨点击一下右下角的【推荐】
如果您希望与我交流互动,欢迎关注微信公众号
本文版权归作者和博客园共有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文连接。

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
线程池参数简介
线程池参数简介
23 0
面向对象简介|学习笔记
快速学习 面向对象简介
32 0
WTF 简介 | 学习笔记
快速学习 WTF 简介
60 0
常用bat命令简介
echo、@、call、pause、rem(小技巧:用::代替rem)是批处理文件最常用的几个命令,我们就从他们开始学起。 echo 表示显示此命令后的字符 echo off 表示在此语句后所有运行的命令都不显示命令行本身 @与echo off相象,但它是加在每个命令行的最前面,表示运行时不显示这一行的命令行(只能影响当前行)。
1201 0
量子机器学习理论简介
  机器学习machine learning - ML,是最近几年才火起来的一个名次,不过关于它的奋斗史却可以追溯到18世纪。 啥是机器学习呢?简单点说就是让电脑或程序能自己学习! 所以机器学习实际上完全是计算机科学领域相关的?非也! 机器学习涉及生活中各个方面,从农业到建筑。
1287 0
wrk简介
wrk简介 wrk 是一个比较先进的 HTTP 压力测试工具。 测试方法: wrk -t8 -c400 -r10m http://localhost:8080/index.html 原文 http://www.oschina.net/p/wrk
757 0
sscanf用法简介
1.定义函数 int sscanf (const char *str,const char * format,........); 函数说明 sscanf()会将参数str的字符串根据参数format字符串来转换并格式化数据。
668 0
+关注
529
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载