《诉苦结构线性表》由会员分享，可在线阅读，更多相关《诉苦结构线性表（27页珍藏版）》请在金锄头文库上搜索。
1、 数据结构 近4周上课内容 第2章线性表第3章栈和队列第4章字符串 线性结构 若结构是非空有限集 则有且仅有一个开始结点和一个终端结点 并且所有结点都最多只有一个直接前趋和一个直接后继 可表示为 a1 a2 an 线性结构的定义 逻辑 存储和运算 线性结构的特点 只有一个首结点和尾结点 除首尾结点外 其他结点只有一个直接前驱和一个直接后继 线性结构表达式 a1 a2 an 线性结构包括线性表 堆栈 队列 字符串 数组 广义表等等 其中 最典型 最常用的是 线性表 简言之 线性结构反映结点间的逻辑关系是一对一的 第2章线性表 1 了解线性结构的特点2 掌握顺序表的定义 查找 插入和删除3 掌握链
2、表的定义 查找 插入和删除4 能够从时间和空间复杂度的角度比较两种存储结构的不同特点及其适用场合 教学目标 2 1线性表的概念 ADT 2 2线性表的顺序表示和实现 顺序表 2 3线性表的链式表示和实现 链表 2 4线性表实现方法的比较 教学内容 a0 a1 ai 1 ai ai 1 an 1 线性表的定义 用数据元素的有限序列表示 n 0时称为 数据元素 线性起点 ai的直接前趋 ai的直接后继 下标 是元素的序号 表示元素在表中的位置 n为元素总个数 即表长 空表 线性终点 2 1线性表的概念2 1 1线性表的抽象数据类型 例1分析26个英文字母组成的英文表 A B C D Z 例2分析学
3、生情况登记表 数据元素都是记录 元素间关系是线性 数据元素都是字母 元素间关系是线性 同一线性表中的元素必定具有相同特性 16 09 templateclasslist 线性表类模板list 模板参数TvoidClear 置空线性表boolisEmpty 线性表为空时 返回trueboolappend constTvalue 尾附函数 在表尾加新元素value 表长加1boolinsert constintp constTvalue 插入函数 在位置p上插入元素value 表长加1booldelete constintp 删除函数 删去位置p上的元素 表长减1boolgetValue cons
4、tintp T 读取 返回位置p的元素值到变量value中boolsetValue 用value修改位置p的元素值boolgetPos 把值为value的元素位置返回到变量p中 线性表的抽象数据类型的定义 模板是C 的软件复用的功能之一 此处定义的是模板类 T通常是代表要处理的数据元素的类型 2 1 2线性表的存储结构 线性表的存储结构主要有两类 1 顺序表 定长存储结构 数组 2 链表 变长存储结构 指针 2 1 3线性表运算分类 1 创建线性表的一个实例 2 线性表的析构函数 list 消除线性表实例并释放所占空间 3 获取有关当前线性表的信息 包括由内容寻找位置 由位置读取元素内容等 不
5、改变线性表的内容 4 访问线性表并改变线性表的内容或结构 例如更新制定元素内容 添加元素 删除元素 清空线性表等 5 辅助管理操作 例如求表的当前长度等 线性表的顺序表示又称为顺序存储结构或顺序映像 简言之 逻辑上相邻 物理上也相邻 顺序存储方法 用一组地址连续的存储单元依次存储线性表的元素 可通过数组a n 来实现 顺序存储定义 把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构 2 2线性表的顺序表示和实现 顺序表 2 2 1顺序表的类定义 16 09 TempateClassarrList publicList private T aList T类型的指针 存储线性表实例int
6、maxSize 实例的最大长度intcurLen 实例的当前长度intposition 当前处理位置public arrList constintsize maxSize size aList newT maxSize curLen position 0 arrList delete aList boolAppend constTvalue aList position value position curLen 顺序表的类定义 2 2 2顺序表的运算实现 查找 又称为检索 根据指定数据查找 返回数据所在的位置 插入 插在第i个结点之前 删除 删除第i个结点 查找 根据指定数据查找 返回数据所
7、在的位置 顺序查找图示 253457164809 012345 data 查找16 i 253457164809 i 253457164809 i 253457164809 i 查找成功 2534571648 01234 data 查找50 i 2534571648 i 2534571648 i 2534571648 i 2534571648 i 查找失败 在顺序表中查找值为value的元素的位置 在表中查找值为value的元素 成功则返回true 并将该元素所在的下标记录在参数p中 失败则返回false templateboolarrList getPos int 查找算法时间效率分析 查找
8、成功的平均比较次数 pi为各项的查找概率 若查找概率相等 则查找不成功数据比较n次 查找算法时间效率分析 251247893614 012345678 25124799893614 99插入 251247893614 251247893614 251247893614 插第3个结点之前 移动6 3次插在第i个结点之前 移动n i次 插入 插在第i个结点之前 1 判断插入位置i是否合法 2 判断顺序表的存储空间是否已满 3 将第n 1至第i位的元素依次向后移动一个位置 空出第i个位置 4 将要插入的新元素e放入第i个位置 5 表长加1 插入成功返回TRUE 插入算法思想 若插入在尾结点之后 则根
9、本无需移动 特别快 若插入在首结点之前 则表中元素全部后移 特别慢 若要考虑在各种位置插入 共n 1种可能 的平均移动次数 该如何计算 算法时间主要耗费在移动元素的操作上 插入算法分析 插入算法描述 算法2 4书P32 251247893614 012345678 2512473614 2512473614 2512473614 删除 删除 删除第i个结点 删除第3个结点 移动6 3 1次删除第i个结点 移动n i 1次 1 判断删除位置i是否合法 合法值为1 i n 2 将欲删除的元素保留在e中 3 将第i 1至第n 1位的元素依次向前移动一个位置 4 表长减1 删除成功返回OK 删除算法思
10、想 若删除尾结点 则根本无需移动 特别快 若删除首结点 则表中n 1个元素全部前移 特别慢 若要考虑在各种位置删除 共n种可能 的平均移动次数 该如何计算 算法时间主要耗费在移动元素的操作上 删除算法分析 删除算法描述 算法2 5书P33 显然 顺序表的空间复杂度S n O 1 没有占用辅助空间 查找 插入 删除算法的平均时间复杂度为O n 1 利用数据元素的存储位置表示线性表中相邻数据元素之间的前后关系 即线性表的逻辑结构与存储结构一致 顺序表 顺序存储结构 的特点 这种存取元素的方法被称为随机存取法 2 在访问线性表时 可以快速地计算出任何一个数据元素的存储地址 因此可以粗略地认为 访问每个元素所花时间相等 顺序表的优缺点 缺点 在插入 删除某一元素时 需要移动大量元素浪费存储空间属于静态存储形式 数据元素的个数不能自由扩充 优点 存储密度大 结点本身所占存储量 结点结构所占存储量 可以随机存取表中任一元素
