计算机考研.ppt

第 2 章线性表?Brooks/Cole, 2001 线性表的逻辑结构 n(n ≥0)个具有相同特性的数据元素的有限序列(1)n为表的长度,即元素个数(2) n=0 时为空表(3) n>0 时通常记为:(a 1,a 2,…,a i,…,a n) ?Brooks/Cole, 2001 (1)当 1<i<n 时 ai的直接前驱是 a i-1,a 1无直接前驱 ai的直接后继是 a i+1,a n无直接后继(2)元素同构不能出现缺项 ⑴初始化线性表⑵判空⑶求线性表的长度, ⑷读取线性表中第 i个元素⑸查找满足给定条件的数据元素⑹在线性表的第 i个位置之前插入一个新的数据元素⑺删除线性表中的第 i个数据元素⑻表置空⑼查找表中第 i个元素的前驱⑽查找表中第 i个元素的后继⑾按一个或多个数据项值的递增或递减次序重新排列线性表中的数据元素?Brooks/Cole, 2001 线性表的顺序存储结构-顺序表 (1)含义用一组连续的存储单元依次存放线性表的数据元素,简称顺序表(2)特点逻辑上相邻的数据元素,它们的物理位置也是邻接的,即线性关系利用物理上的相邻关系来体现(3)位置确定 Loc(a i)=Loc(a 1)+(i-1) *m (4)顺序表的类型定义(5)顺序表处理若有: sqlist x ; sqlist *L=&x ; 则: 线性表的表长应如何表示? 第i个元素应如何表示? 顺序表的数组实现 1)线性表的初始化(1) 算法实现(2) 时间复杂度 T(n )=O(1) 2)插入运算(1)含义在线性表的第 i个数据元素之前插入一个新的数据元素, 使长度为 n的线性表(a 1, …, a i-1, a i, …, a n) 变为长度为 n+1的线性表(a 1, …, a i-1, x, a i, …, a n)