第二章线性表
1
第二章线性表 线性表的逻辑结构 线性表的顺序存贮结构 线性表的链式存储--线性链表 几种特殊线性链表 线性表应用示例
2 第二章 线性表 • 线性表的逻辑结构 • 线性表的顺序存贮结构 • 线性表的链式存储----线性链表 • 几种特殊线性链表 • 线性表应用示例
§21线性表的逻辑结构 §2.1.1基本概念 线性表( Linear list): 是数据元素的一个有限序列,在这个序列中,每个元素有 个唯一的(直接)前趋和一个唯一的(直接)后继,第一个元 素可以无前趋,而最后一个元素也可以无后继 可记为 (a;,a a3为数据元素,a1称为a的前趋(i≥1),a1称为a1的后继(i≤n), 1.2. n
3 §2.1 线性表的逻辑结构 • 线性表（Linear list）: 是数据元素的一个有限序列，在这个序列中，每个元素有 一个唯一的（直接）前趋和一个唯一的（直接）后继，第一个元 素可以无前趋，而最后一个元素也可以无后继 • 可记为 L = (a1 , a2 , …，an )； ai为数据元素，ai-1称为ai的前趋（i≥1），ai+1称为ai 的后继（i≤n）， i=1, 2, …, n. §2.1.1 基本概念
§21.1基本概念 ·线性表中元素的个数称线性表的长度,n=0时 称为空表,空表长度为0 ·按形式化方法,线性表定义为 LL=(DS) D=al, a2, .. an S={r} r={<a1a|a1∈D,i2,…,n}o
4 §2.1.1 基本概念 • 线性表中元素的个数称线性表的长度，n=0时 称为空表，空表长度为0。 • 按形式化方法，线性表定义为 LL=（D,S） D={a1,a2,…,an} S={r} r= { <ai-1 , ai>｜ai∈D，i=2, …, n}
§2.12基本操作 Init(UL:初始化操作,设定一个空的线性表L,执行该操作后,线 性表L就可用于其它操作 Len(L):求长度函数。函数值为线性表中元素的个数。 Get①,i):取元素函数。函数值为L中的序号为的元素(值或地 址) Set(L,i,x):置值函数。将L中的序号为的元素的值置为x Prior(L,x):求前趋函数。函数值为L中的x的前趋。 Next(L,x):求后继函数。函数值为L中的x的后继 Locate(L,x):查找函数。函数值为L中的元素x的序号,若x不在L 中,则返回特殊标志
5 § 2.1.2 基本操作 • Init(L)：初始化操作，设定一个空的线性表L，执行该操作后，线 性表L就可用于其它操作。 • Len(L)：求长度函数。函数值为线性表中元素的个数。 • Get(L, i)：取元素函数。函数值为L中的序号为i的元素（值或地 址）。 • Set(L, i, x)：置值函数。将L中的序号为i的元素的值置为x. • Prior(L, x): 求前趋函数。函数值为L中的x的前趋。 • Next(L,x)：求后继函数。函数值为L中的x的后继。 • Locate(L,x)：查找函数。函数值为L中的元素x的序号，若x不在L 中，则返回特殊标志