数据结构——线性表杂记


什么是线性表

线性表是一种常用的数据结构,表示元素之间一对一的相邻关系。在实际应用中,线性表都是以栈、队列、字符串、数组等特殊线性表的形式来使用的。

线性表是具有相同数据类型的n (n>=0)个数据元素的有限序列。其中n为表长,当n=0 时该线性表是一个空表。若用L命名线性表,则其一般表示如下: L=(a1, a2, …, ai, ai+1, …, an)

其中,a1是唯一的“第一个”数据元素,又称为表头元素;an是唯一的“最后一个”数据元素,又称为表尾元素。除第一个元素外,每个元素有且仅有一个直接前驱。除最后一个元素外,每个元素有且仅有一个直接后继。以上就是线性表的逻辑特性,这种线性有序的逻辑结构正是线性表名字的由来。

由此,我们得出线性表的特点如下:

  • 表中元素的个数有限。
  • 表中元素具有逻辑上的顺序性,在序列中各元素排序有其先后次序。
  • 表中元素都是数据元素,每一个表元素都是单个元素。
  • 表中元素的数据类型都相同。这意味着每一个表元素占有相同数量的存储空间。
  • 表中元素具有抽象性。就是说,仅讨论表元素之间的逻辑关系,不考虑元素究竟表示什么内容。

三种特殊线性表

  1. 队列

从数据结构角度看,栈和队列是操作受限的线性表,它们的逻辑结构相同

串是重要的非数值处理对象,它是以字符作为数据元素的线性表

//这里我们主要讨论下栈与队列概念/区别

  • 栈(Stack)是限定只能在表的一端进行插入和删除操作的线性表。

如:在建筑工地上,使用的砖块从底层一层一层向上放,使用时从最上面一层一层的拿。所以为后进先出。

  • 队列(Queue)是限定只能在表的一端进行插入和在另一端进行删除操作的线性表。

如:在生活中排队上车,排队的规则是不允许插队,后来的人需要站在队尾,每次总是对头先上车。所以为先进先出。

栈和队列是在程序设计中被广泛使用的两种线性数据结构,它们的特点在于基本操作的特殊性,必须按后进先出的规则进行操作,而队列必须按先进先出的规则进行操作。和线性表相比,它们的插入和删除操作受更多的约束和限定,故又称为限定性的线性表结构。可将线性表和栈及队列的插入和删除操作对比如下:

线性表

如线性表允许在表内任一位置进行插入和删除

而栈只允许在表尾一端进行插入和删除

队列

队列只允许在表尾一端进行插入,在表头一端进行删除

END

学习哇

参考: 百度/谷歌 (ง •̀_•́)ง