线性表(上)

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

Paste_Image.png

  • 俩个强调点:
    • 线性表是一个序列,也就是说,元素之间是有顺序的
    • 线性表是有限的

线性表的抽象数据类型:

  • 对于线性表,添加数据,删除数据,线性表的长度都是基本的操作,所以,线性表的抽象数据类型定义如下:


    Paste_Image.png

    Paste_Image.png
  • 对于不同的应用,线性表的基本操作是不同的.上述操作都是最基本的,对于实际问题中涉及的关于线性表的更复杂操作,完全可以用这些基本操作的组合来实现.
  • 比如,要实现俩个线性表集合A和B的并集操作.其实就是把存在集合B中但不存在集合A中的数据元素插入到A中即可
    Paste_Image.png

    线性表的顺序存储结构

是指用一段地址连续的存储单元依次存储线性表的数据元素

Paste_Image.png

Paste_Image.png

数组长度与线性表长度的区别

  • 数组的长度是存放线性表的存储空间的长度,存储分配后这个量一般是不会变的
  • 线性表的长度是线性表中数据元素的个数,随着线性表插入和删除操作的进行,这个量是变化的.
  • 在任意时刻,线性表的长度都应该小于等于数组的长度

地址计算方法

  • 注意,数组是从0开始第一个下标的
  • 线性表中的第i个元素要存在数组下标为i-1的位置


    Paste_Image.png
  • 其实,内存中的地址,就和图书馆和电影院里的座位一样,都是有编号的.储存器中的每个储存单元都有自己的编号,这个编号称为地址.
  • 当我们占位后,占位的第一个位置确定后,后边的位置是可以计算的.假设占用的是C个储存单元,那么线性表中第i+1个数据元素的存储位置和第i个数据元素的存储位置满足以下关系(LOC表示获得存储位置的函数)
    LOC(a[i+1]) = LOC(a[i])+c
    
  • 所以对于第i个数据元素a[i]的存储位置可以由a1推算得出
    LOC(ai) = LOC(a1) + (i - 1) * c
    
    Paste_Image.png
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 1.线性表的定义 线性表:零个或多个数据元素的有限序列序列:也就是说元素之间是有顺序的,若元素存在多个,则第一个元...
    e40c669177be阅读 2,094评论 6 15
  • 3.2 线性表的定义 线性表,从名字上你就能感觉到,是具有像线一样的性质的表。 零个或多个数据元素的有限序列。 这...
    努力生活的西鱼阅读 945评论 0 1
  • 从数据的逻辑结构来分,数据元素之间存在的关联关系被称为数据的逻辑结构。归纳起来,应用程序中的数据大致哟如下四种基本...
    Jack921阅读 967评论 0 2
  • 一、定义: 线性表是具有像线一样的性质的表,是一个序列,元素间是有顺序的,如果存在多个元素的话,第一个元素无前驱,...
    nuclear阅读 1,135评论 1 0
  • 刚下了简书,想写点什么纪念一下,回忆了一下16年记忆最深刻的事情就是厦门之旅啦!一片漫长的流水账,写的不好大家不要...
    loey咘咘阅读 1,324评论 12 12