北京理工大学数据结构课件线性表顺序表.ppt

1 第二章线性表 2 本章内容 2 1线性表的类型定义2 2线性表类型的实现 顺序映象2 3线性表类型的实现 链式映象 3 2 2 1顺序表示及其特点 2 2 2数据结构定义2 2 3顺序表的初始化操作2 2 4顺序表的插入操作2 2 5顺序表的删除操作2 2 6用顺序表实现合并操作LC LA LB 4 2 2 1顺序表示及其特点 顺序映象 以x的存储位置和y的存储位置之间某种关系表示逻辑关系 最简单的一种顺序映象方法是 用一组地址连续的存储单元依次存放线性表中的数据元素 5 2 2 1顺序表示及其特点 以 存储位置相邻 表示有序对即 LOC ai LOC ai 1 CC是一个数据元素所占存储量所有数据元素的存储位置均取决于第一个数据元素的存储位置LOC ai LOC a1 i 1 C 小结 顺序表的特点 用连续的存储单元存放线性表的元素 采用一维数组存放 元素存储顺序与元素的逻辑顺序一致 读写元素方便 通过下标即可指定位置 6 7 2 2 2顺序表数据结构定义 defineLIST INIT SIZE80 线性表存储空间的初始分配量 defineLISTINCREMENT10 线性表存储空间的分配增量 typedefstruct ElemType elem 存储空间基址intlength 当前长度intlistsize 当前分配的存储容量 以sizeof ElemType 为单位 SqList 俗称顺序表 8 01 i 2i 1 n 1 顺序表 L 注意 由于数组的下标从 0 开始 表中第i个元素是L elem i 1 typedefstruct ElemType elem intlength intlistsize SqList 顺序表 SqListL 9 2 2 3顺序表的初始化操作 StatusInitList Sq SqList InitList Sq typedefstruct ElemType elem intlength intlistsize SqList 顺序表 10 2 2 4顺序表的插入操作 ListInsert L i e 插入元素在顺序表L的第i个元素之前插入新的元素e 把e插入到第i个元素的位置i的合法范围为1 i L length 1 01 i 2i 1 n 1 e 11 操作的过程 ListInsert L 6 30 12 操作的过程 ListInsert L 6 30 q p 1 p p p 1 p q e p q 插入操作 13 操作步骤判断插入位置是否合法 1 i L length 1初始化指针循环 从表尾开始 依次将第i 1个元素之后的元素顺序后移一位将新元素e写入到第i个位置将表的长度加1 14 StatusListInsert Sq SqList ListInsert Sq 算法时间复杂度取决于 移动元素的次数 15 插入操作的算法复杂度 考虑移动元素的平均情况 假设在第i个元素之前插入的概率为pi 则在长度为n的线性表中插入一个元素所需移动元素次数的期望值为 若假定在线性表中任何一个位置上进行插入的概率都是相等的 则移动元素的期望值为 算法时间复杂度为 O n 16 if L length L listsize 当前存储空间已满 增加分配newbase ElemType realloc L elem L listsize LISTINCREMENT sizeof ElemType if newbase exit OVERFLOW 存储分配失败L elem newbase 新基址L listsize LISTINCREMENT 增加存储容量 如果存储空间已满怎么办 17 程序设计方法的两点说明 先考虑一般情况 后考虑特殊情况一般不用基本操作实现其他基本操作 18 两个实际问题 错误的类型 正常处理的错误 是一些常见 合理的错误 如 用户输入的错误 通过错误代码返回 意外错误 抛出Exception 通过try catch扑捉 初始化问题 数据结构没有初始化就使用往往也是错误 但无法判定 在C 和Java中通过构造函数解决 19 2 2 5顺序表的删除操作 ListDelete L i e 删除元素删除线性表中第i个元素 并将删除的元素方在e中i的合法范围为1 i L length 删除操作 20 操作的过程 ListDelete L 5 e p e p p p 1 p p L elem L length 1 p p 1 p 21 操作步骤判断插入位置是否合法 1 i L length初始化指针将第i个元素的值赋给变量e循环 从第i 1个元素开始 依次将后面的元素顺序前移一位将表的长度减1 22 StatusListDelete Sq SqList ListDelete Sq 算法时间复杂度取决于 移动元素的次数 23 删除操作的算法复杂度 考虑移动元素的平均情况 假设在删除第i个元素的概率为pi 则在长度为n的线性表中删除一个元素所需移动元素次数的期望值为 若假定在线性表中任何一个位置上进行删除的概率都是相等的 则移动元素的期望值为 算法时间复杂度为 O n 24 LocateElem Sq SqListL ElemTypee Status compare ElemType ElemType e 38 i 1 2 3 4 1 8 50 基本操作 将顺序表中的元素逐个和给定值e相比较 2 2 6定位操作 循环结束标志 找到e或者p超过表尾的地址 25 2 2 6定位操作 请大家写出顺序表的定位操作的操作步骤和程序要求 在顺序表中查询第一个满足判定条件的数据元素 若存在 则返回它的位序 否则返回0 算法时间复杂度为 O n 小结 顺序表的优缺点 优点不需要附加空间随机存取任一个元素 根据下标 缺点很难估计所需空间的大小开始就要分配足够大的一片连续的内存空间更新操作代价大 26 27 END