《数据结构线性表》PPT课件.ppt

第二章线性表 陈守孔孟佳娜陈卓 2020 3 23 2 本章目录 2 1线性表的类型定义2 1 1线性表的概念2 1 2线性表的抽象数据类型2 2线性表的顺序表示和实现2 2 1线性表的顺序表示2 2 2顺序表上基本运算的实现2 3线性表的链式表示和实现2 3 1单链表的表示2 3 2单链表操作的实现2 4线性表实现方法的比较2 5循环链表2 6双链表2 7静态链表 2 8算法设计举例 2020 3 23 3 主要内容 知识点线性表的定义顺序表单链表双链表静态链表重点难点顺序表操作的实现单链表操作的实现顺序表和链表操作时间复杂度的分析静态链表 2020 3 23 4 线性结构 在数据元素的非空的有限集合中 存在唯一的一个被称为 第一个 的数据元素 存在唯一的一个被称为 最后一个 的数据元素 除第一个元素外 集合中每个元素都有且仅有一个前驱 除最后一个元素外 集合中每个元素都有且仅有一个后继 2020 3 23 5 线性表 LinearList 定义 定义 n个具有相同特性的数据元素组成的有限序列 表示 a1 ai 1 ai ai 1 an ai必须具有相同特性 即属于同一数据对象ai 1是ai的直接前驱元素 ai 1是ai的直接后继元素数据元素ai在线性表中有确定的位置i i称为位序线性表中数据元素的个数n称为线性表的长度 n 0时 线性表称为空表 2020 3 23 6 抽象数据类型定义 ADTList 数据对象 D ai ai ElemSet i 1 2 n n 0 数据关系 R ai ai 1 D i 2 n 基本操作 ListInit L ListLength L ListGet L i ListLocate L x ListClear L ListEmpty L ListPrior L e ListNext L e ListInsert L i e ListDelete L i ADTList 2020 3 23 7 例如2 1遍历线性表L ListTraverse ListL visit 遍历线性表if ListEmpty L printf 空表 n elsefor i 1 i ListLength L i visit ListGet L i 2020 3 23 8 例2 2合并线性表 ListListMerge ListLa ListLb La和Lb是两个非递减有序的线性表 将线性表La和Lb合并成一个新的线性表Lc Lc也非递减有序 ListInit Lc i j 1 k 0 La len ListLength La Lb len ListLength Lb while i La len 接下页 2020 3 23 9 接上页 while i La len Lb已空 将La表的剩余部分复制到新表ai ListGet La i ListInsert Lc k ai while j Lb len La已空 将Lb表的剩余部分复制到新表bj ListGet Lb j ListInsert Lc k bj return Lc ListMerge 例2 2合并线性表 2020 3 23 10 逻辑结构是本质 通过上面两个例子可以看出 逻辑结构是数据组织的某种 本质性 的东西 1 逻辑结构与数据元素本身的形式 内容无关 2 逻辑结构与数据元素的相对位置无关 3 逻辑结构与所含数据元素的个数无关 算法的设计取决于选定的逻辑结构 而算法的实现依赖于采用的存储结构 2020 3 23 11 线性表的顺序表示和实现 线性表的顺序表示 线性表的顺序存储是指在内存中用地址连续的一块存储空间顺序存放线性表的各元素 用这种存储形式存储的线性表称为顺序表 设a 的存储地址为Loc a 每个数据元素占L个存储单元 则第i个数据元素的地址为 Loc ai Loc a1 i 1 L1 i n 顺序存储结构的线性表的类型定义如下 defineMAXSIZE100 顺序表的最大容量typedefstruct ElemTypedata MAXSIZE 存放线性表的数组intlast last是线性表的长度 SeqList 2020 3 23 12 顺序表上基本运算的实现 1 SeqListSeqListInit SeqListL 构造一个空的顺序表L length 0 初始化顺序表为空表returnL 顺序表的初始化 2020 3 23 13 顺序表上基本运算的实现 2 插入运算 在第i个位置 插入元素e思想 把从第i个位置开始的元素 依次后移步骤 1 当前表是否已经满 2 输入是否有效 3 插入元素 2020 3 23 14 顺序表上基本运算的实现 2 SeqListSeqListInsert SeqListL inti ElemTypex 在顺序表中的第i个位置插入元素xif L Last MAXSIZE printf 表满 n exit 0 表满 退出if iL Last 1 printf 插入位置错 n exit 0 插入位置错 退出for j L Last 1 j i 1 j L data j 1 L data j 第i个位置后的数组元素逐一后移L data i 1 x 新元素插入到第i个位置L Last 顺序表长度增1return L 返回插入元素后的顺序表 2020 3 23 15 顺序表插入元素算法分析 插入运算的基本操作是移动数据 在第i 1 i n 1 个位置上插入x 需要移动n i 1个元素 设在第i个位置上作插入的概率为pi 则平均移动数据元素的次数 期望值 为设 pi 1 n 1 即为等概率情况 则 pi n 2 约需移动表中一半的数据元素 时间复杂度 O n 2020 3 23 16 顺序表上基本运算的实现 3 删除运算 删除第i个元素e思想 把第i 1个位置开始的元素 依次前移步骤 1 要检查删除位置的有效性 2 依次移动元素 3 长度减1 2020 3 23 17 顺序表上基本运算的实现 3 voidSeqListDelete SeqListL inti 删除顺序表中的第i个元素if iL last printf 位置非法 exit 0 检查空表及删除位置的合法性for j i j L last 1 j L data j 1 L data j 向上移动L last 顺序表长度减1 时间复杂度 O n 删除元素 2020 3 23 18 顺序表删除元素算法分析 主要操作是移动元素 删除第i个元素时 向前移动n i个元素平均移动元素次数的期望值 在等概率情况下 pi 1 n 则 Edel n 1 2 所以顺序表上的删除运算约需要移动表中一半的元素 时间复杂度 O n 2020 3 23 19 顺序表上基本运算的实现 4 intSeqListLocate SeqListL ElemTypex 在顺序表L中查找第一个与x值相等的元素 若查找成功 则返回它在顺序表中的位序 否则 返回0 i 1 while i L last 查找失败 按值查找 2020 3 23 20 顺序表算法举例 顺序结构线性表LA与LB的结点关键字为整数 LA与LB的元素按非递减有序 线性表空间足够大 试用类C语言给出一种高效算法 将LB中元素合到LA中 使新的LA的元素仍保持非递减有序 高效指最大限度的避免移动元素 2020 3 23 21 顺序表算法举例 续 voidUnion SeqListLA LB LA和LB是顺序存储的线性表 元素按非递减有序排列 本算法将LB合并到LA中 元素仍非递减有序 m LA last n LB last m n分别为线性表LA和LB的长度 k m n 1 k为结果线性表的工作指针 下标 i m 1 j n 1 i j分别为线性表LA和LB的工作指针 下标 while i 0 2020 3 23 22 顺序表算法举例 续 请写一个算法将顺序表 a1 an 逆置为 an a1 voidSeqInvert ElemTypea intn a是具有n个元素的顺序表 本算法将其逆置 for i 0 i n 1 2 i t a i a i a n 1 i a n 1 i t 算法结束算法中循环控制变量的初值和终值是关键 C中数组从下标0开始 第n个元素的下标是n 1 因为首尾对称交换 所以控制变量的终值是线性表长度的一半 2020 3 23 23 线性表的链式表示和实现 以链式结构存储的线性表称之为线性链表 线性表中的数据元素可以用任意的存储单元来存储 逻辑相邻的两元素的存储空间可以是不连续的 为表示逻辑上的顺序关系 对表的每个数据元素除存储本身的信息之外 还需存储其后继的地址 即用指针表示逻辑关系 这两部分信息组成数据元素的存储映象 称为结点 2020 3 23 24 可以认为利用小的零散空间 串 起来 表示线性表 即把线性表的元素分散插入到系统所控制的零散空间中 然后用 指针 串起来 组成一个有序的线性表 用指针表示数据元素的逻辑关系 元素的存储 可以是连续的 也可以不是连续的 结点至少包括数据元素和指针两个区域 线性表的链式表示 2020 3 23 25 单链表结构图示 链表 结点ai 2020 3 23 26 单链表结构图示 单链表的头指针为H LinkedListH 2020 3 23 27 单链表结点的类型定义 结点定义 typedefstructNode ElemTypedata structNode next LNode LinkedList 几个概念 结点 首元结点 第一元素结点 头结点 指针 头指针 2020 3 23 28 带头结点的单链表 通常情况下 为了运算的统一 常在第一个结点前附设一个结点 称为 头结点 头指针具有标识作用 因而 常用作链表的名字 LNode p p LNode malloc sizeof LNode 则完成了申请一块LNode类型的存储单元的操作 并将其地址赋值给变量p 2020 3 23 29 线性链表操作的实现 1 LinkedListLinkedListInit 建立一个空的单链表L LNode malloc sizeof LNode if L null printf 无内存空间可分配 exit 0 L next NULL returnL 带头结点的单链表的初始化 2020 3 23 30 线性链表操作的实现 2 intLinkedListLength LinkedListL 求带头结点的单链表的长度p L next p指向第一结点j 0 while p j p p next 移动p指向下一结点returnj 求表长 2020 3 23 31 线性链表操作的实现 3 LinkedListLinkedListGet LinkedListL inti 在单链表L中查找第i个元素结点 返回该结点 否则返回空if inext j 1 while p NULL 取第i个元素 2020 3 23 32 线性链表操作的实现 4 LinkedListLinkedListLocate LinkedListL ElemTypex 在单链表L中查找值为x的结点 找到后返回其指针 否则返回空p L next while p NULL 按值查找 2020 3 23 33 线性链表操作的实现 5 LinkedListLinkedListLocate LinkedListL LNode p 在单链表L中求p指向的结点 假定存在 的前驱if L next p printf p指向第一元素结点 无前驱 exit 0 pre L while pre NULL 查找结点的前驱 2020 3 23 34 线性链表操作的实现 6 LinkedListLinkedListLocate LinkedListL LNode p 在单链表L中求p指向的结点 假定存在 的后继pre L while pre NULL 查找结点的后继 2020 3 23 35 线性链表操作的实现 7 p表示当前结点 pre表示前一个结点 的指针 在p前插入元素ss next pre next pre next s 插入元素 2020 3 23 36 线性链表操作的实现 7 插入算法 voidLinkedListInsert LinkedListL LNode p ElemTypex 在结点p之前插入元素为x的结点pre L while pre NULL 插入新结点 2020 3 23 37 线性链表操作的实现 8 p表示当前结点 pre表示前一个结点 pre next p next free p p pre next 删除元素 2020 3 23 38 线性链表操作的实现 8 删除元素 voidLinkedListDel LinkedListL inti 删除单链表L上的第i个结点if inext 释放被删除结点 2020 3 23 39 线性链表操作的实现 9 建立单链表 头插法 2020 3 23 40 线性链表操作的实现 9 LinkedListLinkedListCreat1 用头插法建立带头结点的单链表LinkedListL L LNode malloc sizeof LNode L next NULL 初始化一个空链表 L为头指针scanf 头插法建立单链表算法 2020 3 23 41 线性链表操作的实现 10 建立单链表 尾插法 2020 3 23 42 线性链表操作的实现 10 LinkedListLinkedListCreat3 用尾插法建立带头结点的单链表LinkedListL L LNode malloc sizeof LNode L next NULL r L scanf 尾插法建立单链表算法 2020 3 23 43 链表的遍历 voidprint LinkedListla 非递归 LinkedListp la next while p printf c p data p p next voidout LinkedListp 递归 if p out p next printf c p data 2020 3 23 44 链表算法举例合并单链表 LinkedListUnion LinkedListla LinkedListlb 将非递减有序的单链表la和lb合并成新的非递减有序单链表lc 并要求利用原表空间lc LNode malloc sizeof LNode 申请结点lc next NULL 初始化链表lcpa la next pa是链表la的工作指针pb lb next pb是链表lb的工作指针pc lc pc是链表lc的工作指针while pa la中元素插入lc 2020 3 23 45 链表算法举例 接上页 else pc next pb pc pb pb pb next lb中元素插入lcif pa pc next pa 若pa未到尾 将pc指向paelsepc next pb 若pb未到尾 将pc指向pbreturn lc Union 2020 3 23 46 链式结构的特点 非随机存贮结构 所以取表元素要慢于顺序表 节约了内存适合于插入和删除操作实际上用空间换取了时间 结点中加入了指针 使得这两种操作转换为指针操作 2020 3 23 47 线性表实现方法的比较 实现不同顺序表方法简单 各种高级语言中都有数组类型 容易实现 链表的操作是基于指针的 相对来讲复杂些 存储空间的占用和分配不同从存储的角度考虑 顺序表的存储空间是静态分配的 在程序执行之前必须明确规定它的存储规模 也就是说事先对 MAXSIZE 要有合适的设定 过大造成浪费 过小造成溢出 而链表是动态分配存储空间的 不用事先估计存储规模 可见对线性表的长度或存储规模难以估计时 采用链表 线性表运算的实现不同按序号访问数据元素 使用顺序表优于链表 插入删除操作 使用链表优于顺序表 2020 3 23 48 循环链表 单循环链表 循环链表 链表尾结点的指针域指向头结点 这样形成的链表我们叫做循环链表 循环链表往往只设尾指针 2020 3 23 49 连接两个只设尾指针的单循环链表L1和L2 语句段如下 p R1 next 保存L1的头结点指针R1 next R2 next next 头尾连接free R2 next 释放第二个表的头结点R2 next p 2020 3 23 50 双链表 如果希望查找前驱的时间复杂度达到O 1 我们可以用空间换时间 每个结点再加一个指向前驱的指针域 使链表可以进行双方向查找 用这种结点结构组成的链表称为双向链表 结点的结构图 2020 3 23 51 双向链表的逻辑表示 L L 2020 3 23 52 双向链表的类型定义 typedefstructDLNode ElemTypedata structDLNode prior next DLNode DLinkedList 双向链表结点的类型定义如下 2020 3 23 53 双向链表的插入 p s p prior s 1 2 s prior p prior p prior next s s next p 3 4 2020 3 23 54 双向链表的删除 p 1 2 p prior next p next P next prior p prior free p 2020 3 23 55 循环链表算法举例 1 假设一个单循环链表 其结点含有三个域pre data link 其中data为数据域 pre为指针域 它的值为空指针 null link为指针域 它指向后继结点 请设计算法 将此表改成双向循环链表 voidSToDouble LinkedListla while la link pre null la link pre la 将结点la后继的pre指针指向lala la link la指针后移 算法结束 2020 3 23 56 循环链表算法举例 2 已知一双向循环链表 从第二个结点至表尾递增有序 设a1 x an 如下图 试编写程序 将第一个结点删除并插入表中适当位置 使整个链表递增有序 L 2020 3 23 57 循环链表算法举例 2 voidDInsert DLinkedListL s L s暂存第一结点的指针p L next 将第一结点从链表上摘下p prior L prior p prior next p while p datanext 查插入位置s next p s prior p prior 插入原第一结点sp prior next s p prior s 算法结束 2020 3 23 58 链表算法举例 3 L1与L2分别为两单链表头结点地址指针 且两表中数据结点的数据域均为一个字母 设计把L1中与L2中数据相同的连续结点顺序完全倒置的算法 2020 3 23 59 链表算法举例 3 LinkedListPatternInvert LinkedListL1 L2 p L1 p是每趟匹配时L1中的起始结点前驱的指针q L1 next q是L1中的工作指针 s L2 next s是L2中的工作指针 while p null 对应字母相等 指针后移 else p p next q p next s L2 next 失配时L1起始结点后移 L2从首结点开始 接下页 2020 3 23 60 链表算法举例 接上页 if s NULL 匹配成功 这时p为L1中与L2中首字母结点相同数据域结点的前驱 q为L1中与L2最后一个结点相同数据域结点的后继 r p next r为L1的工作指针 初始指向匹配的首字母结点 p next q 将p与q结点的链接 while r q 逐结点倒置 s r next 暂存r的后继 r next p next 将r所指结点倒置 p next r r s 恢复r为当前结点 elseprintf L2并未在L1中出现 算法结束 2020 3 23 61 静态链表 有些高级程序设计语言并没有指针类型 如FORTRAN和JAVA 我们可以用数组来表示和实现一个链表 称为静态链表 可定义如下 defineMAXSIZE1000 最多元素个数typedefstruct ElemTypedata 数据元素intnext 指向后继元素在数组中的位置 SLinkedList MAXSIZE 2020 3 23 62 静态链表图示 线性表L 2 3 4 6 8 9 的静态链表图示 2020 3 23 63 静态链表与动态链表 静态链表的操作和动态链表相似 只是以整型游标代替动态指针 设以Sa表示静态链表 通常可把Sa 0 理解为 头结点 第1个元素的位置由Sa 0 next指出 用全局整型变量av指出可利用空间的下标 初始时将整个静态链表看作一个 空表 操作中用GetNode 和FreeNode 函数模拟C中的malloc 和free 函数 以下是初始化 取结点和释放结点3个函数 2020 3 23 64 静态链表的初始化 intInitilize 初始可利用空间表 inti for i 0 i maxsize 1 i 链成可利用空间表Sa i next i 1 Sa maxsize 1 next 1 链表尾 av 1 returnav 返回可利用空间表的下标 2020 3 23 65 静态链表的申请结点空间 intGetNode 取结点 if av 1 1表示无空间 p av av Sa av next p为可利用空间的下标 returnp 2020 3 23 66 静态链表的释放结点空间 intFreeNode intp 将p归还到可利用空间表中 Sa p