笔记

深浅模式

线性结构 ​

基本概念 ​

线性结构是一种最简单且常用的数据结构。线性结构的基本特点是节点之间满足线性关系。本章讨论的动态数组、链表、栈、队列都属于线性结构。他们的共同之处，是节点中有且只有一个开始节点和终端节点。按这种关系，可以把它们的所有节点排列成一个线性序列。但是，他们分别属于几种不同的抽象数据类型实现，它们之间的区别，主要就是操作的不同。

线性表是零个或者多个数据元素的有限序列，

例：先来看一个大家感兴趣的话题，一年里的星座列表，是不是线性表呢？如图所示：

线性表的抽象数据类型定义

c
ADT线性表（List）
Data

线性表的数据对象集合为{ a1, a2, ……, an }，每个元素的类型均为DataType。其中，除第一个元素a1外，每个元素有且只有一个直接前驱元素，除了最后一个元素an外，每个元素有且只有一个直接后继元素。数据元素之间的关系是一一对应的。

线性表的性质 ​

  • a0 为线性表的第一个元素，只有一个后继
  • an 为线性表的最后一个元素，只有一个前驱
  • 除 a0 和 an 外的其它元素 ai，既有前驱，又有后继
  • 线性表能够逐项访问和顺序存取。

应具备的接口 ​

线性表应该具备的接口，或者说是应该提供的操作（Operation）

c
// 初始化，建立一个空的线性表L。
InitList(*L);

// 在线性表L中的第i个位置插入新元素e
ListInsert(*L, i, e);

// 若线性表为空，返回true，否则返回false
ListEmpty(L);

// 将线性表清空
ClearList(*L);

// 将线性表L中的第i个位置的元素返回给e
GetElem(L, i, *e);

// 删除线性表L中的第i个位置元素，并用e返回其值
ListDelete(*L, i, *e);

// 返回线性表L的元素个数
ListLength(L);

// 销毁线性表
DestroyList(*L);

线性结构的分类 ​

通常线性表可以采用顺序存储和链式存储。

常见的线性表有：

  • 顺序表
  • 链表
  • 栈
  • 队列
  • 哈希表（散列表）