数据机构第二章-线性表(严蔚敏).ppt

第二章线性表 2 1 了解线性表的逻辑结构特性是数据元素之间存在着线性关系 2 熟练掌握这两类存储结构 顺序存储结构和链式存储结构的描述方法 链表是本章的重点和难点 扎实的指针操作和内存动态分配的编程技术是学好本章的基本要求 3 熟练掌握线性表在顺序存储结构上实现基本操作 查找 插入和删除的算法 4 熟练掌握在各种链表结构中实现线性表操作的基本方法 能在实际应用中选用适当的链表结构 5 能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合 学习提要 3 在数据元素的非空有限集中 存在唯一的一个被称作 第一个 的数据元素 存在唯一的一个被称作 最后一个 的数据元素 除第一个外 集合中的每个数据元素均只有一个前驱 除最后一个外 集合中的每个数据元素均只有一个后继 线性结构特点 a1 a2 a3 a4 a5 a6 简言之 线性结构反映结点间的逻辑关系是1 1的 线性结构包括 线性表 堆栈 队列 字符串 数组等 其中最典型 最常用的是 线性表 4 a1 a2 ai 1 ai ai 1 an 1 线性表的定义 用数据元素的有限序列表示 n 0时称为 数据元素 线性起点 ai的直接前趋 ai的直接后继 下标 是元素的序号 表示元素在表中的位置 n为元素总个数 即表长 空表 线性终点 2 1线性表的逻辑结构 5 例1 26个英文字母组成的字母表 A B C Z 例2 某校从1978年到1983年各种型号的计算机拥有量的变化情况 6 17 28 50 92 188 6 例3 学生健康情况登记表如下 7 从以上例子可看出线性表的逻辑特征是 在非空的线性表 有且仅有一个开始结点a1 它没有直接前趋 而仅有一个直接后继a2 有且仅有一个终端结点an 它没有直接后继 而仅有一个直接前趋an 1 其余的内部结点ai 2 i n 1 都有且仅有一个直接前趋ai 1和一个直接后继ai 1 a1 a2 ai ai 1 an 8 1 数据结构是指相互之间存在一种或多种关系的数据元素的全体 2 一维向量是线性表 但二维或N维数组不是 3 同一逻辑结构中的所有数据元素都具有相同的特性 是指数据元素所包含的数据项的个数都相等 练 判断下列叙述的正误 9 ADTList 数据对象 D ai ai ElemSet i 1 2 n n 0 数据关系 R ai 1 ai D i 2 n 基本操作 1 结构初始化 InitList L 操作结果 构造一个空的线性表L 2 销毁结构 DestroyList L 初始条件 线性表L已存在 操作结果 销毁线性表L 线性表的抽象数据类型 10 3 引用型操作 ListEmpty L 初始条件 线性表L已存在 操作结果 若L为空表 则返回TRUE 否则FALSEListLength L 初始条件 线性表L已存在 操作结果 返回L中元素个数 PriorElem L cur e pre e 初始条件 线性表L已存在 操作结果 若cur e是L的元素 但不是第一个 则用pre e返回它的前驱 否则操作失败 pre e无定义 NextElem L cur e next e 初始条件 线性表L已存在 操作结果 若cur e是L的元素 但不是最后一个 则用next e返回它的后继 否则操作失败 next e无定义 11 3 引用型操作 续 GetElem L i e 初始条件 线性表L已存在 1 i LengthList L 操作结果 用e返回L中第i个元素的值 LocateElem L e compare 初始条件 线性表L已存在 compare 是元素判定函数 操作结果 返回L中第1个与e满足关系compare 的元素的位序 若这样的元素不存在 则返回值为0 ListTraverse L visit 线性表遍历初始条件 线性表L已存在 操作结果 依次对L的每个元素调用函数visit 一旦visit 失败 则操作失败 12 4 加工型操作ClearList L 初始条件 线性表L已存在 操作结果 将L重置为空表 PutElem L i e 初始条件 线性表L已存在 1 i LengthList L 操作结果 L中第i个元素赋值同e的值 ListInsert L i e 初始条件 线性表L已存在 1 i LengthList L 1操作结果 在L的第i个元素前插入新元素e L长度增1 ListDelete L i e 初始条件 线性表L已存在且非空 1 i LengthList L 操作结果 删除L第i个元素 用e返回其值 L的长度减1 ADTList 13 某数据结构上的基本运算 不是它的全部运算 而是一些常用的基本的运算 而每一个基本运算在实现时也可能根据不同的存储结构派生出一系列相关的运算来 读者掌握了某一数据结构上的基本运算后 其它的运算可以通过基本运算来实现 也可以直接去实现 2 在上面各操作中定义的线性表 仅仅是一个抽象在逻辑结构层次的线性表 尚未涉及到它的存储结构 因此每个操作在逻辑结构层次上尚不能用具体的某种程序语言写出具体的算法 而算法的实现只有在存储结构确立之后 说明 14 假设 有两个集合A和B分别用两个线性表LA和LB表示 即 线性表中的数据元素即为集合中的成员 现要求一个新的集合A A B A 5 3 11 8 B 6 2 8 9 20 15 11 例2 1 15 要求对线性表作如下操作 扩大线性表LA 将存在于线性表LB中而不存在于线性表LA中的数据元素插入到线性表LA中去 上述问题可演绎为 16 1 从线性表LB中依次察看每个数据元素 2 依值在线性表LA中进行查访 3 若不存在 则插入之 GetElem LB i e LocateElem LA e equal ListInsert LA n 1 e 操作步骤 17 GetElem Lb i e 取Lb中第i个数据元素赋给eif LocateElem La e equal ListInsert La La len e La中不存在和e相同的数据元素 则插入之 voidunion List for i 1 i Lb len i union T n O LA length LB length 18 巳知线性表LA和线性表LB中的数据元素按值非递减有序排列 现要求将LA和LB归并为一个新的线性表LC 且LC中的元素仍按值非递减有序排列 求解 设两个指针 i指向LA中的元素a j指向LB中的元素b LC中的元素c a ab LA 3 5 8 11 LB 2 6 8 9 11 15 20 得到LC 2 3 5 6 8 9 11 15 20 例2 2 19 voidMergelist ListLa ListLb List endwhile 20 while i La len Lb为空的情况GetElem La i ai ListInsert Lc k ai while j Lb len La为空的情况GetElem Lb j bj ListInsert Lc k bi T n O LA length LB length 21 2 2线性表的顺序表示和实现 22 用一组地址连续的存储单元依次存放线性表中的数据元素 a1a2 ai 1ai an 线性表的起始地址称作线性表的基地址 顺序存储结构 23 元素地址计算方法 LOC ai LOC a1 i 1 LLOC ai 1 LOC ai L其中 L 一个元素占用的存储单元个数LOC ai 线性表第i个元素的地址特点 实现逻辑上相邻 物理地址相邻实现随机存取实现 可用C语言的一维数组实现 顺序存储结构 24 设有一维数组 下标的范围是 到 每个数组元素用相邻的 个字节存储 存储器按字节编址 设存储数组元素 的第一个字节的地址是 则 的第一个字节的地址是 113 因此 LOC M 3 98 5 3 0 113 解 已知地址计算通式为 LOC ai LOC a1 L i 1 25 顺序表的C语言描述 typedefstruct SqList 俗称顺序表 defineLIST INIT SIZE80 线性表存储空间的初始分配量 defineLISTINCREMENT10 线性表存储空间的分配增量 ElemType elem 存储空间基址 intlength 当前长度 intlistsize 当前分配的存储容量 以sizeof ElemType 为单位 26 线性表的基本操作在顺序表中的实现 InitList L 结构初始化 LocateElem L e compare 查找 ListInsert L i e 插入元素 ListDelete L i 删除元素 注意 C语言中的数组下标从 0 开始 因此 若L是Sqlist类型的顺序表 则表中第i个元素是L elem i 1 27 顺序表的初始化 intInitList Sq SqList 函数调用 main sqlistL InitList Sq L 28 intLocateElem Sq SqListL ElemTypee 在顺序表中查询第一个等于e的数据元素 若存在 则返回它的位序 否则返回0 LocateElem Sq O ListLength L 算法的时间复杂度为 i 1 i的初值为第1元素的位序p L elem p的初值为第1元素的存储位置 while i L length if i L length return0 elsereturni 29 3 插入在线性表的第i个位置前插入一个元素 实现步骤 将第n至第i位的元素向后移动一个位置 将要插入的元素写到第i个位置 表长加1 注意 事先应判断 插入位置i是否合法 表是否已满 长度为n的线性表变为长度为n 1的线性表 a1 a2 ai 1 ai an a1 a2 ai 1 x ai an 30 StatusListInsert Sq SqList L inti ElemTypee 在顺序表L的第i个元素之前插入新的元素e 1 i L length 1 if L length L listsize 当前存储空间已满 增加分配 newbase ElemType realloc L elem L listsize LISTINCREMENT sizeof ElemType if newbase printf 分配空间失败 return 1 L elem newbase 新基址L listsize LISTINCREMENT 增加存储容量 if iL length 1 printf 插入位置错误 return0 31 for j L length 1 j i 1 j L elem j 1 L elem j 插入位置及之后的元素后移L elem i 1 e 插入eL length 表长增1return1 32 考虑移动元素的平均情况 假设在第i个元素之前插入的概率为 则在长度为n的线性表中插入一个元素所需移动元素次数的期望值为 若假定在线性表中任何一个位置上进行插入的概率都是相等的 则移动元素的期望值为 O n 33 实现步骤 将第i 1至第n位的元素向前移动一个位置 表长减1 注意 事先需要判断 删除位置i是否合法 4 删除删除线性表的第i个位置上的元素 使 长度为n的线性表变为长度为n 1的线性表 a1 a2 ai 1 ai ai 1 an a1 a2 ai 1 ai 1 an 34 StatusListDelete Sq SqList L inti ElemType e ListDelete Sq for j i j L Length 1 j L elme j 1 L elem j 被删除元素之后的元素前移 L length 表长减1return1 算法时间复杂度为 O ListLength L e L elem i 1 被删除元素的值赋给e if iL length printf 删除位置错误 return0 35 考虑移动元素的平均情况 假设删除第i个元素的概率为 则在长度为n的线性表中删除一个元素所需移动元素次数的期望值为 若假定在线性表中任何一个位置上进行删除的概率都是相等的 则移动元素的期望值为 O n 36 小结 线性表顺序存储结构特点 逻辑关系上相邻的两个元素在物理存储位置上也相邻 优点 可以随机存取表中任一元素O 1 存储空间使用紧凑缺点 在插入 删除某一元素时 需要移动大量元素O n 预先分配空间需按最大空间分配 利用不充分为克服这一缺点 我们引入另一种存储形式 链式存储结构 见2 3节 37 特点 1 用一组任意的存储单元存储线性表的数据元素 2 利用指针实现了用不相邻的存储单元存放逻辑上相邻的元素 3 每个数据元素ai 除存储本身信息外 还需存储其直接后继的信息 结点数据域 元素本身信息指针域 指示直接后继的存储位置 线性表的链式存储结构 38 data next 结点 p 定义 结点中只含一个指针域的链表 也叫单链表 TypedefstructLNode ElemTypedata structLNode next Lnode LinkList 若声明LNode p 则 p malloc sizeof LNode 表示生成一个新结点 free p 表示系统回收p结点 单链表 39 一个线性表的逻辑结构为 ZHAO QIAN SUN LI ZHOU WU ZHENG WANG 其存储结构用单链表表示如下 请问其头指针的值是多少 例 答 头指针是指向链表中第一个结点的指针 因此关键是要寻找第一个结点的地址 31 头指针的值是31 40 上例链表的逻辑结构示意图有以下两种形式 区别 无头结点 有头结点 41 答 讨论1 在链表中设置头结点有什么好处 讨论2 如何表示空表 头结点即在链表的首元结点之前附设的一个结点 该结点的数据域中不存储线性表的数据元素 其作用是为了对链表进行操作时 可以对空表 非空表的情况以及对首元结点进行统一处理 编程更方便 答 无头结点时 当头指针的值为空时表示空表 有头结点时 当头结点的指针域为空时表示空表 42 头结点 在单链表第一个结点前附设的一个结点 头结点指针域为空表示线性表为空 43 单链表操作的实现 GetElem L i e 取第i个数据元素 ListInsert L i e 插入数据元素 ListDelete L i e 删除数据元素 ClearList L 重置线性表为空表 CreateList L n 生成含n个数据元素的链表 44 1 在链表的头部插入结点建立单链表链表与顺序表不同 它是一种动态管理的存储结构 链表中的每个结点占用的存储空间不是预先分配 而是运行时系统根据需求而生成的 因此建立单链表从空表开始 每读入一个数据元素则申请一个结点 然后插在链表的头部 建立单链表 45 例如 逆位序输入n个数据元素的值 建立带头结点的单链表 操作步骤 一 建立一个 空表 二 输入数据元素an 建立结点并插入 三 输入数据元素an 1 建立结点并插入 an an an 1 四 依次类推 直至输入a1为止 46 intCreateList L LinkList L intn 逆序输入n个数据元素 建立带头结点的单链表 CreateList L 算法的时间复杂度为 O Listlength L L LinkList malloc sizeof LNode L next NULL 先建立一个带头结点的单链表 for i 1 idata 输入元素值p next L next L next p 插入 returnOK 47 在单链表的尾部插入结点建立单链表 以上算法读入的数据元素的顺序与生成的链表中元素的顺序是相反的 若希望次序一致 则用尾插入的方法 因为每次是将新结点插入到链表的尾部 所以需加入一个尾指针r用来始终指向链表中的尾结点 以便能够将新结点插入到链表的尾部 如下图所示 48 在单链表的尾部插入结点建立单链表 操作步骤 一 建立一个 空表 尾指针指向头结点 二 输入数据元素a1 建立结点 插入在尾指针的后面 尾指针指向a1结点 三 输入数据元素a2 建立结点 插入在尾指针的后面 尾指针指向a2结点 四 依次类推 直至输入an为止 voidCreateList L LinkList for依次插入n个数据元素 CreateList L 50 查找操作 1 按序号查找Get Linklist L i 算法思路 从链表的第一个元素结点起 判断当前结点是否是第i个 若是 则返回该结点的指针 否则继续后一个 表结束为止 没有第 个结点时返回空 51 intGetElem L LinkList inti ElemType 52 2 按值查找即定位Locate LinkList L e 算法思路 从链表的第一个元素结点起 判断当前结点其值是否等于e 若是 返回该结点的指针 否则继续后一个 表结束为止 找不到时返回空 算法如下 LNode LocateElem L LinkListL ElemTypee p L next 初始化p指向第一个结点while p 53 插入 1 后插结点 设p指向单链表中某结点 s指向待插入的值为x的新结点 将 s插入到 p的后面 操作如下 s next p next p next s p s 思考 Step1和2能互换么 54 intListInsert L LinkListL inti ElemTypee L为带头结点的单链表的头指针 本算法 在链表中第i个结点之前插入新的元素e LinstInsert L p L j 0 while p i大于表长或者小于1 s LinkList malloc sizeof LNode 生成新结点s data e s next p next p next s 插入returnOK 算法的时间复杂度为 O ListLength L 55 2 前插结点 设 指向链表中某结点 指向待插入的值为x的新结点 将 s插入到 p的前面 q L while q next p q q next s next q next q next s 先找到p的前驱结点再做插入 56 删除设q指向单链表中某结点 删除 q 首先要找到 q的前驱结点 p 然后完成指针的操作即可 操作由下列语句实现 p next q next free q 思考 省略free q 语句行不行 57 StatusListDelete L LinkListL inti ElemType e 删除以L为头指针 带头结点 的单链表中第i个结点 ListDelete L 算法的时间复杂度为 O ListLength L p L j 0 while p next 删除位置不合理 q p next p next q next 删除并释放结点e q data free q returnOK 58 voidClearList ClearList free p 逐个释放每个结点 算法时间复杂度 O ListLength L ClearList 59 链表插入删除实例 两个链表的归并 教材P31例 算法要求 已知 线性表A B 分别由单链表La Lb存储 其中数据元素按值非递减有序排列 要求 将A B归并为一个新的线性表C C的数据元素仍按值非递减排列 设线性表C由单链表Lc存储 假设 A 3 5 8 11 B 2 6 8 9 11 预测 合并后将C 2 3 5 6 8 8 9 11 11 60 链表示意图 头结点 61 算法设计 算法主要包括搜索 比较 插入三个操作 搜索 需要设立三个指针来指向La Lb和Lc链表 比较 比较La和Lb表中结点数据的大小 插入 将La和Lb表中数据较小的结点插入新链表Lc 请注意链表的特点 仅改变指针便可实现数据的移动 即 数据不动 指针动 62 Pa Pb用于搜索La和Lb Pc指向新链表当前结点 归并过程示意如下 63 算法实现 VoidMergeList L LinkList La LinkList Lb LinkList Lc 按值排序的单链表LA LB 归并为LC后也按值排序 free Lb 释放Lb的头结点 MergeList L pc next pa pa pb 插入剩余段 while papb pb next pa La next pb Lb next Lc pc La 初始化 是条件运算符 为真则取第1项 Lc用的是La的头指针 只有Lb头指针空闲 64 思考 1 不用Lc 直接把La表插到Lb表中 或者把Lb表插到La表中 该如何编程 2 要求归并后的表中不能有重复的数据元素 该如何编程 应能完成作业2 23 65 教案浏览或下载请到 数据结构网上课堂 网站 网址是 第2章作业请全体同学周四上课时交 配套习题集的2 2 2 4 2 5 2 6 2 7 2 8 2 9 2 11 2 19 2 212 22题 建议独立完成辅导材料 第2章自测题 66 内容回顾 线性表的逻辑结构顺序表的表示和基本操作的实现单链表的表示和基本操作的实现 67 主要内容 循环链表双向链表链表的典型习题应用 一元多项式的表示及相加 68 讨论1 链表能不能首尾相连 怎样实现 答 能 只要将表中最后一个结点的指针域指向头结点即可 P next head 这种形成环路的链表称为循环链表 其它链表形式 69 循环链表是表中最后一个结点的指针指向头结点 使链表构成环状 特点 从表中任一结点出发均可找到表中其他结点 提高查找效率 循环链表 circularlinkedlist 70 循环链表与单链表循环条件不同 操作与单链表基本一致 循环条件不同 单链表 p next NULL循环链表 p next H 71 循环链表中设立尾指针 找到第一个结点 rear next next 和最后一个结点 rear 均需要常数时间 72 linklistconnect linklist 例 在单循环链表上实现将两个线性表 a1 a2 a3 an 和 b1 b2 b3 bn 链接成一个线性表的运算 73 讨论2 单链表只能查找结点的直接后继 能不能查找直接前驱 如何实现 答 能 只要把单链表再多开一个指针域即可 例如用 next和 prior 这种有两个指针的链表称为双向链表 其特点是可以双向查找表中结点 74 双向循环链表的对称性 P next prior p p prior next 很明显 在双向链表中不仅能直接找到结点的前驱 也能即刻找到结点的后继 75 双向链表的操作特点 查询 和单链表相同 插入 和 删除 时需要同时修改两个方向上的指针 76 双向链表中结点的插入 设p指向双向链表中某结点 s指向待插入的值为x的新结点 将 s插入到 p的前面 操作如下 s prior p prior p prior next s s next p p prior s 77 双向链表中结点的删除 设p指向双向链表中某结点 删除 p 操作如下 p prior next p next p next prior p prior free p 78 链表的运算效率分析 1 查找因线性链表只能顺序存取 即在查找时要从头指针找起 查找的时间复杂度为O n 2 插入和删除因线性链表不需要移动元素 只要修改指针 一般情况下时间复杂度为O 1 但是 如果要在单链表中进行前插或删除操作 由于要从头查找前驱结点 所耗时间复杂度为O n 空间效率分析 链表中每个结点都要增加一个指针空间 相当于总共增加了n个整型变量 空间复杂度为O n 79 例 已知单链表L 写一算法 删除其重复结点 即实现如下图2 23的操作 算法思路 用指针p指向第一个数据结点 从它的后继结点开始到表的结束 找与其值相同的结点并删除之 p指向下一个 依此类推 p指向最后结点时算法结束 80 voidpur LinkList LinkListH LNode p q r p H next p指向第一个结点 if p NULL return while p next q p while q next if q next data p data r q next q next r next free r elseq q next p p next 该算法的时间性能为O n2 算法 81 例 线性表 a1 a2 am b1 b2 bn 改变成 b1 b2 bn a1 a2 am 解题分析 因为对链表来说 插入 和 删除 仅需修改指针即可完成 并且由于前m个元素之间和后n个元素之间的链接关系分别都不需要改变 则算法的实际操作为 1 从链表中删除 a1 a2