数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社专题专题1：线性表的逻辑结构：线性表的逻辑结构12线性表的定义线性表的定义 线性表的逻辑特性线性表的逻辑特性3线性表的抽象数据类型定义线性表的抽象数据类型定义 数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社2.1 2.1 线性表的逻辑结构线性表的逻辑结构线性表的逻辑结构线性表的逻辑结构数据元素之间的关系是什么？数据元素之间的关系是什么？数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社2.1 2.1 线性表的逻辑结构线性表的逻辑结构线性表的逻辑结构线性表的逻辑结构数据元素之间的关系是什么？数据元素之间的关系是什么？现实生活中，许多问题抽象出的数据模型是线性表，如何存现实生活中，许多问题抽象出的数据模型是线性表，如何存储这种线性结构并实现插入、删除、查找等基本操作呢？储这种线性结构并实现插入、删除、查找等基本操作呢？ 数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社p 线性表：线性表：简称表，是简称表，是n（n0）个具有）个具有相同类型相同类型的数的数据元素的据元素的有限序有限序列列。p 线性表的长度：线性表的长度：线性表中数据元素的个数。线性表中数据元素的个数。p 空表：空表：长度等于零的线性表，长度等于零的线性表，记为：记为：L=( )。p 非空表非空表记为：记为：L（a1, a2 , , ai-1, ai , , an)2.1 2.1 线性表的逻辑结构线性表的逻辑结构线性表的逻辑结构线性表的逻辑结构线性表的定义线性表的定义其中，其中，ai（1in）称为数据元素；）称为数据元素；下角标下角标 i 表示该元素在线性表中的位置或序号表示该元素在线性表中的位置或序号 。数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社a1a3a4ana22.1 2.1 线性表的逻辑结构线性表的逻辑结构线性表的逻辑结构线性表的逻辑结构线性表的特性线性表的特性1. 有限性有限性：线性表中数据元素的个数是有穷的。：线性表中数据元素的个数是有穷的。2. 相同性相同性：线性表中数据元素的类型是同一的。：线性表中数据元素的类型是同一的。3. 顺序性顺序性：线性表中相邻的数据元素：线性表中相邻的数据元素ai-1和和ai之间存在之间存在序偶关系序偶关系(ai-1, ai)，即，即ai-1是是ai的前驱，的前驱， ai是是ai-1的后继；的后继；a1无前驱，无前驱，an无后继，其它每个元素有且仅有一个前无后继，其它每个元素有且仅有一个前驱和一个后继。驱和一个后继。 数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社线性表的抽象数据类型定义线性表的抽象数据类型定义ADT ListData 线性表中的数据元素具有相同类型，线性表中的数据元素具有相同类型， 相邻元素具有前驱和后继关系相邻元素具有前驱和后继关系OperationInitList 前置条件前置条件：表不存在：表不存在 输入输入：无：无 功能功能：表的初始化：表的初始化 输出输出： 无无 后置条件后置条件：建一个空表：建一个空表2.1 2.1 线性表的逻辑结构线性表的逻辑结构线性表的逻辑结构线性表的逻辑结构数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社DestroyList 前置条件前置条件：表已存在：表已存在 输入输入：无：无 功能功能：销毁表：销毁表 输出输出：无：无 后置条件后置条件：释放表所占用的存储空间：释放表所占用的存储空间Length 前置条件前置条件：表已存在：表已存在 输入输入：无：无 功能功能：求表的长度：求表的长度 输出输出：表中数据元素的个数：表中数据元素的个数 后置条件后置条件：表不变：表不变2.1 2.1 线性表的逻辑结构线性表的逻辑结构线性表的逻辑结构线性表的逻辑结构线性表的抽象数据类型定义线性表的抽象数据类型定义数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社Get 前置条件前置条件：表已存在：表已存在 输入输入：元素的序号：元素的序号i 功能功能：在表中取序号为：在表中取序号为i的数据元素的数据元素 输出输出：若：若i合法，返回序号为合法，返回序号为i的元素值，否则抛出异常的元素值，否则抛出异常 后置条件后置条件：表不变：表不变Locate 前置条件前置条件：表已存在：表已存在 输入输入：数据元素：数据元素x 功能功能：在线性表中查找值等于：在线性表中查找值等于x的元素的元素 输出输出：若查找成功，返回：若查找成功，返回x在表中的序号，否则返回在表中的序号，否则返回0 后置条件后置条件：表不变：表不变2.1 2.1 线性表的逻辑结构线性表的逻辑结构线性表的逻辑结构线性表的逻辑结构线性表的抽象数据类型定义线性表的抽象数据类型定义数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社Insert前置条件前置条件：表已存在：表已存在输入输入：插入：插入i；待插待插x功能功能：在表的第：在表的第i个位置处插入一个新元素个位置处插入一个新元素x输出输出：若插入不成功，抛出异常：若插入不成功，抛出异常 后置条件后置条件：若插入成功，表中增加一个新元素：若插入成功，表中增加一个新元素Delete前置条件前置条件：表已存在：表已存在输入输入：删除位置：删除位置i功能功能：删除表中的第：删除表中的第i个元素个元素 输出输出：若删除成功，返回被删元素，否则抛出异常：若删除成功，返回被删元素，否则抛出异常 后置条件后置条件：若删除成功，表中减少一个元素：若删除成功，表中减少一个元素2.1 2.1 线性表的逻辑结构线性表的逻辑结构线性表的逻辑结构线性表的逻辑结构线性表的抽象数据类型定义线性表的抽象数据类型定义数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社Empty 前置条件前置条件：表已存在：表已存在 输入输入：无：无 功能功能：判断表是否为空：判断表是否为空 输出输出：若是空表，返回：若是空表，返回1，否则返回，否则返回0 后置条件后置条件：表不变：表不变ADT进一步说明进一步说明: :（1 1）线性表的基本操作根据实际应用是而定；）线性表的基本操作根据实际应用是而定；（2）复杂的操作可以通过基本操作的组合来实现；）复杂的操作可以通过基本操作的组合来实现；（3）对不同的应用，操作的接口可能不同。对不同的应用，操作的接口可能不同。2.1 2.1 线性表的逻辑结构线性表的逻辑结构线性表的逻辑结构线性表的逻辑结构线性表的抽象数据类型定义线性表的抽象数据类型定义