【2.1】线性表

一、线性表的概念

线性表简称表,是零个或多个元素的有穷序列,通常可 以表示成 k0,k1, …,kn-1(n ≥ 1)

  • 表目:线性表中的元素(可包含多个数据项,记录)
  • 索引(下标):i 称为表目 ki 的“索引”或“下标”
  • 表的长度:线性表中所含元素的个数 n
  • 空表:长度为零的线性表 ( n = 0 )

线性表特点:

  • 操作灵活,其长度可以增长、缩短

二、线性结构

二元组𝐵 = (𝐾,𝑅) 𝐾 = {𝑎0,𝑎1,…,𝑎𝑛−1} 𝑅 = {𝑟}

  • 有一个唯一的开始结点,它没有前驱,有一个唯一的直接后继

  • 一个唯一的终止结点,它有一个唯一的直接前驱,而没有后继

  • 其它的结点皆称为 内部结点,每一个内部结点都有且仅有一个唯一的直 接有前驱,也有一个唯一的直接后继

    < 𝑎𝑖, 𝑎𝑖+1 > 𝑎𝑖是𝑎𝑖+1的前驱,𝑎𝑖+1是𝑎𝑖的后继

  • 前驱/后继关系r,具有 反对称性 和 传递性

特点:

  • 均匀性:虽然不同线性表的数据元素可以是各种各样 的,但对于同一线性表的各数据元素必定具有相同的 数据类型和长度
  • 有序性:各数据元素在线性表中都有自己的位置,且 数据元素之间的相对位置是线性的

按复杂程度划分:

  • 简单的:线性表、栈、队列、散列表
  • 高级的:广义表、多维数组、文件……

按访问方式划分

  • 直接访问型 (direct access)
  • 顺序访问型 (sequential access)
  • 目录索引型 (directory access)

按操作划分(详见后)L

  • 线性表
  • 所有表目都是同一类型结点的线性表
  • 不限制操作形式
  • 根据存储的不同分为:顺序表,链表
  • 栈 (LIFO, Last In First Out)
  • 插入和删除操作都限制在表的同一端进行
  • 队列 (FIFO, First In First Out)
  • 插入操作在表的一端, 删除操作在另一端

三、线性表的逻辑结构

主要属性包括

  • 线性表的长度
  • 表头 (head)
  • 表尾 (tail)
  • 当前位置 (current position)

四、线性表分类

4.1 线性表分类(按存储)

线性表

  • 所有表目都是同一类型结点的线性表
  • 不限制操作形式
  • 根据存储的不同分为:顺序表,链表

4.2 线性表分类(按操作)

  • 线性表 – 不限制操作
  • 栈 – 在同一端操作
  • 队列 – 在两端操作

栈 (LIFO, Last In First Out) – 插入和删除操作都限制在表的同一端进行

队列 (FIFO, First In First Out) – 插入操作在表的一端, 删除操作在另一端

五、线性表的运算

  • 建立线性表
  • 清除线性表
  • 插入一个新元素
  • 删除某个元素
  • 修改某个元素
  • 排序
  • 检索

线性表类模板:

六、讨论

  • 线性表有哪些分类方式?
  • 各种线性表名称中,哪些跟存储结构相关?哪些跟运算相关?

参考资料

北京大学 《数据结构与算法》 张铭、赵海燕、宋国杰、黄骏、邹磊、陈斌、王腾蛟

药企,独角兽,苏州。团队长期招人,感兴趣的都可以发邮件聊聊:tiehan@sina.cn
个人公众号,比较懒,很少更新,可以在上面提问题,如果回复不及时,可发邮件给我: tiehan@sina.cn