《线性表顺序表》PPT课件.ppt

第二章 线性表 线性表的逻辑结构 线性表的顺序存储及实现 线性表的链接存储及实现 顺序表和单链表的比较 线性表的其他存储及实现 本章的基本内容是： 学生成绩登记表 2.1 线性表的逻辑结构 姓 名 英语 数据结构 高数 学号 丁一 96 78 87 0101 李二 87 90 78 0102 张三 67 86 86 0103 孙红 69 81 96 0104 王冬 87 74 66 0105 每行是一个数据元素 数据元素之间的关系是 1:1的线性关系 职工工资登记表 2.1 线性表的逻辑结构 姓 名 岗位津贴 基本工资 奖金 职工号 丁一 600 278 200 0101 李二 300 190 100 0102 张三 300 186 100 0103 孙红 500 218 200 0104 王冬 300 190 100 0105 每行是一个数据元素 数据元素之间的关系是 1:1的线性关系 线性表： 简称表，是 n（ n0）个具有 相同类型 的数据 元素的 有序（前后次序）序 列 。 线性表的长度： 线性表中数据元素的个数。 空表： 长度等于零的线性表， 记为： L=( )。 非空表 记为： L（ a1, a2 , , ai-1, ai , , an) 2.1 线性表的逻辑结构 线性表的定义 其中， ai（ 1in）称为数据元素； 下角标 i 表示该元素在线性表中的位置或序号 。 a1 a3 a4 an a2 2.1 线性表的逻辑结构 线性表的图形表示 线性表 （ a1, a2 , , ai-1, ai , , an)的图形表示如下： a1 a3 a4 an a2 2.1 线性表的逻辑结构 线性表的特性 1.有限性：线性表中数据元素的个数是有穷的。 2.相同性：线性表中数据元素的类型是同一的。 3.顺序性：线性表中相邻的数据元素 ai-1和 ai之间存在 序偶关系 ，即 ai-1是 ai的直接前驱， ai是 ai-1的 直接后继； a1 无前驱， an无后继，其它每个元素有且 仅有一个直接前驱和一个直接后继。 线性表的抽象数据类型定义 ADT List Data 线性表中的数据元素具有相同类型， 相邻元素具有前驱和后继关系 Operation InitList 前置条件 ：表不存在 输入 ：无 功能 ：表的初始化 输出 ： 无 后置条件 ：建一个空表 2.1 线性表的逻辑结构 DestroyList 前置条件 ：表已存在 输入 ：无 功能 ：销毁表 输出 ：无 后置条件 ：释放表所占用的存储空间 Length 前置条件 ：表已存在 输入 ：无 功能 ：求表的长度 输出 ：表中数据元素的个数 后置条件 ：表不变 2.1 线性表的逻辑结构 线性表的抽象数据类型定义（续） Get 前置条件 ：表已存在 输入 ：元素的序号 i 功能 ：在表中取序号为 i的数据元素 输出 ：若 i合法，返回序号为 i的元素值，否则抛出异常 后置条件 ：表不变 Locate 前置条件 ：表已存在 输入 ：数据元素 x 功能 ：在线性表中查找值等于 x的元素 输出 ：若查找成功 ， 返回 x在表中的序号 ， 否则返回 0 后置条件 ：表不变 2.1 线性表的逻辑结构 线性表的抽象数据类型定义 Insert 前置条件 ：表已存在 输入 ：插入 i； 待插 x 功能 ：在表的第 i个位置处插入一个新元素 x 输出 ：若插入不成功 ， 抛出异常 后置条件 ：若插入成功 ， 表中增加一个新元素 Delete 前置条件 ：表已存在 输入 ：删除位置 i 功能 ：删除表中的第 i个元素 输出 ：若删除成功，返回被删元素，否则抛出异常 后置条件 ：若删除成功 ， 表中减少一个元素 2.1 线性表的逻辑结构 线性表的抽象数据类型定义 Empty 前置条件 ：表已存在 输入 ：无 功能 ：判断表是否为空 输出 ：若是空表 ， 返回 1， 否则返回 0 后置条件 ：表不变 ADT List 进一步说明 : （ 1）线性表的基本操作根据实际应用而定； （ 2）复杂的操作可以通过基本操作的组合来实现； （ 3） 对不同的应用，操作的接口可能不同。 2.1 线性表的逻辑结构 线性表的抽象数据类型定义 2.2 线性表的顺序存储结构及实现 顺序表 线性表的顺序存储结构 例： （ 34, 23, 67, 43） 34 23 67 43 存储要点 用一段地址 连续 的存储单元 依次 存储线性表中的数据元素 2.2 线性表的顺序存储结构及实现 顺序表 线性表的顺序存储结构 例： （ 34, 23, 67, 43） 34 23 67 43 存储空间 10 用什么属性来描述顺序表？ 顺序表的容量（最大长度） 顺序表的当前长度 4 2.2 线性表的顺序存储结构及实现 顺序表 线性表的顺序存储结构 例： （ 34, 23, 67, 43） 34 23 67 43 10 如何实现顺序表的内存分配？ 顺序表 一维数组和两 个整型变量 4 如何求得任意元素的存储地址？ 0 i-2 i-1 n-1 Max-1 a1 ai-1 ai an 空闲 长度 2.2 线性表的顺序存储结构及实现 顺序表 一般情况下， (a1， a2， , ai-1， ai , , an)的顺序存储： c Loc(ai) Loc(a1) Loc(ai)表示数据元素 ai的地址 0 i-2 i-1 n-1 Max-1 a1 ai-1 ai an 空闲 长度 Loc(ai)=Loc(a1) + (i -1) c 随机存取 ： 在 O(1)时间内存取数据元素 2.2 线性表的顺序存储结构及实现 顺序表 一般情况下， (a1， a2， , ai-1， ai , , an)的顺序存储： c Loc(ai) Loc(a1) 数据元素 ai地址的计算 公式 2.2 线性表的顺序存储结构及实现 存储 结构是数据及其逻辑结构在计算机中的表示； 存取 结构是在一个数据结构上对查找操作的时间性 能的一种描述。 存储结构和存取结构 “顺序表是一种 顺序存储、随机存取 的 存储 结构” 的含义为：在顺序表这种存储结构上进行的查找操 作，其时间性能为 O(1)。 顺 序 表 类 型 的 描 述 顺序表类型的示意图 1 2.2 线性表的顺序存储结构及实现 34 23 67 43 10 4 分析：这是一个结构体类型，由 3个数据成员组成 (1)一维数组，存放线性表的元素 (2)总容量 (数组的数组的长度 )(3)线性表的长度 给出上述顺序表类型的定义： #define MAXSIZE 100 typedef struct list ElemType elemMAXSIZE; /* ElemType 为数据元素类型 */ int listsize; int length; SqList; SqList L,*p= L的数据成员如何表示 （ 1） L.elemi, L.length, L.listsize （ 2） p-elemi, p-length, p-listsize 顺 序 表 类 型 的 描 述 顺序表类型的示意图 2 2.2 线性表的顺序存储结构及实现 分析：这是一个结构体类型，由 3个数据成员组成 (1)指针变量，存放一维数组的首地址 (2)总容量 (数组的长度 ) (3)线性表的长度 34 23 67 43 10 4 给出上述结构体类型的定义： typedef struct list ElemType *elem;/*连续空间的申请由初始化完成 */ int listsize; int length; SqList; 操作接口： int InitSqlist(SqList L.length=0; return 1; 2.2 线性表的顺序存储结构及实现 顺序表的实现 初始化（方案 1） 操作接口： int InitSqlist(SqList if(L.elem=NULL) printf(“空间分配失败” ); exit(0); L.listsize=n; L.length=0; return 1; 2.2 线性表的顺序存储结构及实现 顺序表的实现 初始化（方案 2） 操作接口 int InsertSqlist(SqList 2. 如果元素的插入位置不合理 ， 则抛出 位置 异常 ; 3. 将最后一个元素至第 i个元素分别向后移动一个位置； 4. 将元素 x填入位置 i处； 5. 表长加 1； 算法描述 伪代码 2.2 线性表的顺序存储结构及实现 顺序表的实现 插入 int InsertSqlist(SqList return 0; if (iL.length+1)printf(位置非法 ); return 0; for (j=length; j=i; j-) L.elemj=L.elemj-1; L.elemi-1=x; L.length+; return 1; 算法描述 C描述 2.2 线性表的顺序存储结构及实现 顺序表的实现 插入 基本语句 ？ 最好 情况（ i=n+1）： 基本语句执行 0次，时间复杂度为 O(1)。 最坏 情况（ i=1）： 基本语句执行 n次，时间复杂度为 O(n)。 平均 情况（ 1in+1）： 时间复杂度为 O(n)。 时间性能分析 2.2 线性表的顺序存储结构及实现 顺序表的实现 插入 + - + = 1 1 )= 1 ( n i i i n p + - + + = 1 1 )= 1 ( 1 1 n i i n n 2 n =O(n) 操作接口： int DeleteSqlist(SqList else return -1; 时间复杂度 ？ O(1) 顺序表的实现 按值查找 操作接口： int LocateSqlist(SqList L,ElemType x ) 2.2 线性表的顺序存储结构及实现 5 35 a1 a2 a3 a4 0 1 2 3 4 42 24 12 33 a5 例：在（ 35, 33, 12, 24, 42） 中查找值为 12的元素， 返回在表中的序号。 i i i 注意序号和下标之间的关系 int LocateSqlist(SqList L,ElemType x ) for (i=0; iL.length; i+) if (L.elemi=x) return i+1; return 0; 2.2 线性表的顺序存储结构及实现 顺序表的实现 按值查找 算法描述： 时间复杂度 ？ 最好情况： O(1) 最差情况： O(n) 平均情况： O(n) 顺序表的优缺点 顺序表的优点： 无需为表示表中元素之间的逻辑关系而增加额外的 存储空间； 随机存取：可以快速地存取表中任一位置的元素。 顺序表的缺点： 插入和删除操作需要移动大量元素； 表的容量难以确定，表的容量难以扩充； 2.2 线性表的顺序存储结构及实现