数据结构线性表课件.ppt

1 第二章线性表 线性结构的特点 在数据元素的非空有限集中 1 存在唯一的一个被称为 第一个 的数据元素2 存在唯一的一个被称为 最后一个 的数据元素3 除第一个之外 集合中的每个数据元素均只有一个前驱4 除最后一个之外 集合中的每个数据元素均只有一个后继 2 第二章线性表 重点 理解线性表的逻辑结构特性熟练掌握线性表的顺序存储结构的描述方法 以及在该存储结构下的基本操作熟练掌握线性表的链式存储结构的描述方法 灵活使用单链表 学会在相应存储结构下实现其各种基本算法及相关的时间性能分析 3 第二章线性表 难点 能够从时间复杂度的角度综合比较线性表两种存储结构的不同特点及其应用场合使用本章所学的基本知识设计有效算法 解决与线性表相关的应用问题 4 第二章线性表 线性结构的特点 在数据元素的非空有限集中 1 存在唯一的一个被称为 第一个 的数据元素2 存在唯一的一个被称为 最后一个 的数据元素3 除第一个之外 集合中的每个数据元素均只有一个前驱4 除最后一个之外 集合中的每个数据元素均只有一个后继 5 第二章线性表 2 1线性表的类型定义2 2线性表的顺序表示和实现2 3线性表的链式表示和实现2 3 1线性链表2 3 2循环链表2 3 3双向链表 6 一 定义1 线性表 linear list 定义 简称为表 是n个元素的有限序列 通常可以表示成 a1 a2 an n 0 表的长度 表中所含元素的个数n 空表 长度为零的表表项 表中的元素ai位序 数据元素ai在线性表中的位置 2 1线性表的类型定义 7 1 线性表 线性表中的数据元素在不同的情况下可以有不同的具体含义 它可以是一个数 一个符号 也可是其它更复杂的信息例1 26个字母 A B Z 例2 班级人数 33 32 35 30 例3 学生情况登记表 数据元素为记录 有若干个数据项组成 如姓名 学号 性别 年龄 p18图2 1 2 1线性表的类型定义 8 2 线性表的特点 线性表中的数据元素是各种各样的 但同一线性表中的元素必定具有相同特性 即属于同一数据对象相邻数据元素之间存在序偶关系 a1 a2 ai 1 ai ai 1 an ai 1是ai的直接前驱元素 ai 1是ai的直接后继元素相当灵活 长度可以增长或缩短 2 1线性表的类型定义 9 3 线性表的基本运算在线性表中插入一个元素 在线性表中删除某个元素 在线性表中查找某个特定元素 在线性表中查找某个元素的后继元素 在线性表中查找某个元素的前驱元素 创建空线性表 判别一个线性表是否为空表 由基本运算可以构成其它较为复杂的运算 2 1线性表的类型定义 10 二 抽象数据类型线性表的定义 P19 ADTList 数据对象 D ai ai ElemSet i 1 2 n n 0 数据关系 R1 ai 1 ai D i 2 n 基本操作 InitList L 操作结果 构造一个空的线性表LDestroyList L 初始条件 线性表L已存在操作结果 销毁线性表 2 1线性表的类型定义 11 二 抽象数据类型线性表的定义 P19 ClearList L 初始条件 线性表L已存在操作结果 将线性表L重置为空表ListEmpty L 初始条件 线性表L已存在操作结果 若L为空表 则返回TRUE 否则返回FALSEListLength L 初始条件 线性表L已存在操作结果 返回L中数据元素个数 2 1线性表的类型定义 12 二 抽象数据类型线性表的定义 P19 GetElem L i e 初始条件 线性表L已存在 1 i LengthList L 操作结果 用e返回L中第i个元素的值LocateElem L e compare 初始条件 线性表L已存在 compare 是元素判定函数操作结果 返回L中第1个与e满足关系compare 的元素的位序 若这样的元素不存在 则返回值为0PriorElem L cur e pre e 初始条件 线性表L已存在操作结果 若cur e是L的元素 但不是第一个 则用pre e返回它的前驱 否则操作失败 pre e无定义 2 1线性表的类型定义 13 二 抽象数据类型线性表的定义 P19 NextElem L cur e next e 初始条件 线性表L已存在操作结果 若cur e是L的元素 但不是最后一个 则用next e返回它的后继 否则操作失败 next e无定义ListTraverse L visit 初始条件 线性表L已存在操作结果 依次对L的每个元素调用函数visit 一旦visit 失败 则操作失败PutElem L i e 初始条件 线性表L已存在 1 i LengthList L 操作结果 L中第i个元素赋值同e的值 2 1线性表的类型定义 14 二 抽象数据类型线性表的定义 P19 ListInsert L i e 初始条件 线性表L已存在 1 i LengthList L 1操作结果 在L的第i个元素之前插入新的元素e L的长度增1ListDelete L i e 初始条件 线性表L已存在且非空 1 i LengthList L 操作结果 删除L的第i个元素 并用e返回其值 L的长度减1 ADTList 2 1线性表的类型定义 15 三 应用例2 1假设利用两个线性表LA和LB分别表示两个集合A和B 即 线性表中的数据元素即为集合中的成员 现要求一个新的集合A A B 上述问题等价于 要求对线性表作如下操作 扩大线性表LA 将存在于线性表LB中而不存在于线性表LA中的数据元素插入到线性表LA中去 P20算法2 1分下列三步进行 1 从线性表LB中依次取得每个数据元素 2 依值在线性表LA中进行查访 3 若不存在 则插入之 2 1线性表的类型定义 16 例2 2归并两个 其数据元素按值非递减有序排列的 线性表LA和LB 求得线性表LC也具有同样特性voidMergeList ListLa ListLb List 2 1线性表的类型定义 17 if ai bj ListInsert Lc k ai i else ListInsert Lc k bj j while i La len GetElem La i ai ListInsert Lc k ai while j Lb len GetElem Lb j bj ListInsert Lc k bj merge list算法2 2 2 1线性表的类型定义 18 算法2 1的时间复杂度为O ListLength LA ListLength LB 算法2 2的时间复杂度为O ListLength LA ListLength LB 例 清华大学1998年试题线性表是具有n个 的有限序列 1 表元素 2 字符 3 数据元素 4 数据项 2 1线性表的类型定义 19 一 线性表的顺序表示 以元素在计算机内存中的 物理位置相邻 来表示线性表中数据元素之间的逻辑关系 如下所示 Locate ai 1 Locate ai lLocate ai Locate a1 l i 1 只要确定了首地址 线性表中任意数据元素都可以随机存取称第一个数据元素的存储地址为线性表的起始地址 称作线性表的基地址 2 2线性表的顺序表示和实现 20 2 2线性表的顺序表示和实现 二 顺序表的定义 在C语言中可以用一维数组表示 defineLIST INIT SIZE100 表初始分配空间 defineLISTINCREMENT10 空间分配增量基址typedefstruct ElemType elem 存储空间intlength 当前长度intlistsize 当前存储容量 SqList 21 2 2线性表的顺序表示和实现 三 应用1 初始化线性表StatusInitList Sq SqList InitList Sq时间复杂度O 1 22 2 2线性表的顺序表示和实现 2 插入元素StatusListInsert Sq SqList 23 2 2线性表的顺序表示和实现 q ListInsert Sq在最坏情况下 即插入在第一个元素之前 所需移动元素数为L length 时间复杂度为O ListLength L 24 2 2线性表的顺序表示和实现 3 删除元素StatusListDelete Sq SqList ListDelete Sq在最坏情况下 即删除第一个元素 所需移动个数为L length 1 时间复杂度近似为O ListLength L 25 2 2线性表的顺序表示和实现 插入元素时的时间效率 设pi是在第i个元素之前插入一个元素的概率 则在长度为n的线性表中插入一个元素时所需移动元素的次数的期望值 平均次数 为 设 则有 26 2 2线性表的顺序表示和实现 删除元素时的时间效率 设qi是删除第i个元素的概率 则在长度为n的线性表中删除一个元素时所需移动元素的次数的期望值 平均次数 为 设 则有 27 2 2线性表的顺序表示和实现 4 两个顺序表的合并voidMergeList Sq SqListla SqListlb SqList 28 2 2线性表的顺序表示和实现 while pa pa last 插入lb的剩余元素 EndofMergeList Sq 29 2 2线性表的顺序表示和实现 例 顺序表第一个元素的存储地址是100 每个元素的长度是2 则第5个元素的地址是 A110B108C100D120例 若长度为n的线性表采用顺序存储结构 在其第i个位置插入一个新元素的算法的时间复杂度为 1 i n 1 AO 0 BO 1 CO n DO n2 30 2 3线性表的链式表示及实现 一 定义顺序表的缺陷 插入 删除耗费大量时间线性链表 用一组任意单元表示数据元素和数据元素之间的关系 这些单元可以是连续的 也可以是不连续的 其结点由两部分信息组成 1 数据域 存储数据元素信息 2 指针域 存储直接后继的存储位置 地址 31 2 3线性表的链式表示及实现 2 3 1单链表 存储地址数据域指针域1Li437Qian1313Sun119WangNULL25Wu3731Zhao737Zheng1943Zhou25 32 2 3线性表的链式表示及实现 单链表 线性链表的逻辑状态 33 2 3线性表的链式表示及实现 单链表 非空表 空表 34 二 线性链表的定义typedefintDataType 定义元素类型为整型 也可定义为其他类型 structLNode 单链表结点类型 typedefstructLNode PNode 结点指针类型 structLNode 单链表结点结构 ElemTypedata LNode next 2 3线性表的链式表示及实现 35 2 3线性表的链式表示及实现 基本操作 1 取元素StatusGetElem L LinkListL inti ElemType GetElem L 36 单链表结点插入和删除时的情形 2 3线性表的链式表示及实现 单链表 s next p next 注 顺序不能反单链表插入结点时的情况 p next p next next 单链表删除结点时的情况 p next s 37 2 3线性表的链式表示及实现 2 插入元素StatusListInsert L LinkList ListInsert L 38 2 3线性表的链式表示及实现 3 删除元素StatusListDelete L LinkList ListDelete L 39 2 3线性表的链式表示及实现 4 创建链表VoidCreateList L LinkList CreateList L 40 5 将两个有序链表归并为一个新的有序链表 分析 有两个非递减有序链表La Lb 现归并La Lb得到Lc 其条件为大于前者 不小于后者VoidMergeList L LinkList 2 3线性表的链式表示及实现 41 while pa MergeList L时间复杂度分析 O n 2 3线性表的链式表示及实现 42 单链表与顺序表的比较 单链表的存储密度比顺序表低 它多占用了存储空间 但在许多情况下 链式的分配比顺序分配有效 顺序表必须分配足够大的连续的存储空间 而链表可以利用零星的存储单元 在单链表里进行插入 删除运算比在顺序表里容易得多对于顺序表 可随机访问任一个元素 而在单链表中 需要顺着链逐个进行查找 因此单链表适合于在成批地 顺序地处理线性表中的元素时采用 2 3线性表的链式表示及实现 43 2 3 2循环链表最后一个结点的指针域的指针又指回第一个结点操作与线性链表基本一致循环条件 p next p head表空条件 p head next p head 2 3线性表的链式表示及实现 空循环链表 非空循环链表 44 2 3 3双向链表可以在单链表的每一个结点里再增加一个指向其前趋和后继的指针域 这样链表中有两条不同方向的链优点 既可以找前驱 也可以找后继 2 3线性表的链式表示及实现 空双向链表 非空双向链表 45 双向链表存储结构 typedefstructDuLNode ElemTypedata structDuLNode prior structDuLNode next DuLNode DuLinkList 2 3线性表的链式表示及实现 46 双向循环链表 2 3线性表的链式表示及实现 空双向循环链表 非空双向循环链表 47 双向 循环 链表 2 3线性表的链式表示及实现 删除双向链表的结点p prior next p next p next prior p prior 往双向链表中插入结点s prior p prior p prior next s s next p p prior s 48 双向循环链表的插入算法 StatusListInsert Dul DuLinkList ListInsert Dul 2 3线性表的链式表示及实现 49 双向循环链表的删除算法 StatusListDelete Dul DuLinkList ListDelete Dul 2 3线性表的链式表示及实现 50 线性链表与顺序表的比较 线性链表优点 空间的合理利用 插入和删除时不需要移动缺点 实现基本操作 如求表长 不如顺序表数据元素的 位序 概念被淡化很多场合下 是线性表的首选存储结构 2 3线性表的链式表示及实现 51 一个带头结点的线性链表类型 P37 38 2 3线性表的链式表示及实现 52 小结 了解线性表的逻辑结构特征熟悉掌握顺序表和链表的描述方法 特点及有关概念重点掌握顺序表上的插入和删除算法重点掌握链表的建立 查找 插入和删除算法掌握从时间和空间的角度综合比较顺序表以及链表的不同特点及其适用场合 53 作业 在顺序存储结构的线性表中 写出在第三个元素前插入一个数据元素和删除第二个数据元素的操作 并绘图表示 在单链表中 假设head为队首指针 请