【精品数据结构】线性表3.PPTVIP

第二章 线性表 线性表的逻辑结构 线性表的顺序存贮结构 线性表的链式存储----线性链表 几种特殊线性链表 线性表应用示例 §2.1 线性表的逻辑结构 线性表（Linear list）: 是数据元素的一个有限序列，在这个序列中， 每个元素有一个唯一的（直接）前趋和一个唯一的（直接）后继，第一个元素可以无前趋，而最后一个元素也可以无后继 可记为 L = (a1, a2, …，an)； ai为数据元素，ai-1称为ai的前趋（i≥1），ai+1称为ai 的后继（i≤n），i=1, 2, …, n. 线性表中元素的个数称线性表的长度，n=0时称为空表，空表长度为0。 按形式化方法，线性表定义为 LL=（D,S） D={a1,a2,…,an} S={r} r= { ai-1, ai｜ai∈D，i=2, …, n}。 § 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中，则返回特殊标志。 §2.1.2 基本操作 Insert (L, i ,x)：插入操作。将元素x插入到L中的第i个元素之前，使原第i个元素及其后的各元素的序号分别增1。 l?Deletel (L, i)：删除操作。将L中的第i个元素删除掉，使L 中的元素个数减1，原第i个元素之后的元素的序号分别减1。 l??Empty (L)：判定函数。若L为空表，函数值为“真”，否则为“假”。 l??Clear (L)：置空操作。使L成为空表。 §2.1.2 基本操作 l?? Copy (L1, L2)：复制操作。生成一个名为L2的与L1完全相同的线性表。 l?? Sort ( L, key, type)：排序操作。按线性表中元素的关键字key的递增或递减（由type确定）次序重新排列L中的元素次序。 l?? Merge ( L1, L2, L3 )：合并操作。使L3取L1和L2首尾相连的结果 l?? Split ( L, i, L1, L2)：分拆操作。使L1为L中的前i个元素（含第i个）构成的线性表，L2为剩余部分构成的线性表。 § 2. 1.3 异常处理 异常(Exception)： 是指程序运行中，由于运行环境、数据输入或操作不当而导致程序不能物理地运行的错误 不能通过静程序发现异常（只能估计它的可能性），而只能通过程序的运行发现 §1.2.3 异常处理 在C++中，为程序员提供了良好的处理异常的机制 try----检测/捕获异常； catch----处理try所捕获的异常； throw----生成一个异常，交由try捕获； §2.1.3 异常处理 首先，设立一个表，存储异常代码和用于说明异常的文字信息 struct TErrMessageRec { int no; char msg [CNST_SizeErrMessage ]; }; class TErrMessageList { TErrMessageRec msgList [CNST_MaxNumErrMessage ]; public: int len; ? TErrMessageList() { int i = 0; ? §2.1.3 异常处理 /* 0*/ msgList[i].no=i; strcpy(msgList[i].msg, Unkonwn error); i++; /* 1*/ msgList[i].no=i; strcpy(msgList[i].msg, The parameters Out of range); i++; /* 2*/ msgList[i].no=i; strcpy(msgList[i].msg, The parameters illegal); i++; /* 3*/ msgList[i].no=i; strcpy(msgList[i].msg, The memory space low); i++; /* 4*/ msgList[i].no=i; strcpy(msgList[i]