第二章线性表
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∈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 中，则返回特殊标志
52.1.2基本操作 ● Insert(L,i,x):插入操作。将元素x插入到L中的第诠个元素之前, 使原第i个元素及其后的各元素的序号分别增1 ● Deletel(,i):删除操作。将L中的第个元素删除掉,使L中的元 素个数减1,原第个元素之后的元素的序号分别减1。 Empty(L):判定函数。若L为空表,函数值为“真”,否则为 假 Clear(L):置空操作。使L成为空表
6 §2.1.2 基本操作 ⚫ Insert (L, i ,x)：插入操作。将元素x插入到L中的第i个元素之前， 使原第i个元素及其后的各元素的序号分别增1。 ⚫ Deletel (L, i)：删除操作。将L中的第i个元素删除掉，使L 中的元 素个数减1，原第i个元素之后的元素的序号分别减1。 ⚫ Empty (L)：判定函数。若L为空表，函数值为“真” ，否则为 “假”。 ⚫ Clear (L)：置空操作。使L成为空表
52.1.2基本操作 y(L,L2):复制操作。生成一个名为L2的与L完全相同的线 key,type):排序操作。按线性表中元素的关键字key的递 增或递减(由type确定)次序重新排列L中的元素次序。 ● Merge(L1,L2,L3):合并操作。使L3取L1和L2首尾相连的结果 ● Split(L,i,L1,L2):分拆操作。使Ll为L中的前i个元素(含第i个) 构成的线性表,L2为剩余部分构成的线性表
7 §2.1.2 基本操作 ⚫ Copy (L1, L2)：复制操作。生成一个名为L2的与L1完全相同的线 性表。 ⚫ Sort ( L, key, type)：排序操作。按线性表中元素的关键字key的递 增或递减（由type确定）次序重新排列L中的元素次序。 ⚫ Merge ( L1, L2, L3 )：合并操作。使L3取L1和L2首尾相连的结果 ⚫ Split ( L, i, L1, L2)：分拆操作。使L1为L中的前i个元素（含第i个） 构成的线性表，L2为剩余部分构成的线性表
§2.13异常处理 异常( Exception 是指程序运行中,由于运行环境、数据 输入或操作不当而导致程序不能物理地运行的 错误 不能通过静程序发现异常(只能估计它的可能 性),而只能通过程序的运行发现
8 § 2. 1.3 异常处理 • 异常(Exception)： 是指程序运行中，由于运行环境、数据 输入或操作不当而导致程序不能物理地运行的 错误 • 不能通过静程序发现异常（只能估计它的可能 性），而只能通过程序的运行发现
51.2.3异常处理 在C+中,为程序员提供了良好的处理异常的 机制 try-检测/捕获异常; catch-处理try所捕获的异常; hrow-生成一个异常,交由try捕获
9 §1.2.3 异常处理 • 在C++中，为程序员提供了良好的处理异常的 机制 – try----检测/捕获异常； – catch----处理try所捕获的异常； – throw----生成一个异常，交由try捕获；
52.1.3异常处理 首先,设立一个表,存储异常代码和用于说明异常的文字信息 struct TErrMessageRec int no char msg cnst size errMessage class TErrMessagelist TErrMessageRec msglist [CNST MaxNumErrMessage ublic int len TErr Messagelist
10 §2.1.3 异常处理 • 首先，设立一个表，存储异常代码和用于说明异常的文字信息 struct TErrMessageRec { int no; char msg [CNST_SizeErrMessage ]; }; class TErrMessageList { TErrMessageRec msgList [CNST_MaxNumErrMessage ]; public: int len; TErrMessageList() { int i = 0;