数据结构第2章线性表.ppt

数据结构与算法 第二讲 线性表 一 内容提要 线性表的定义和基本操作线性表的顺序存储结构线性表的链式存储结构 单链表 21 03 2020 2 什么叫线性表 21 03 2020 3 线性表的定义和基本操作 线性表的定义线性表是由n n 0 个类型相同的数据元素组成的有限序列 通常表示成下列形式 L a1 a2 ai 1 ai ai 1 an 其中 L为线性表名称 习惯用大写书写 ai为组成该线性表的数据元素 习惯用小写书写 线性表中数据元素的个数被称为线性表的长度 当n 0时 线性表为空 又称为空线性表 21 03 2020 4 线性表的结构分析 21 03 2020 5 线性表特性 线性表中元素之间的关系是线性关系 存在唯一的第一个元素 存在唯一的最后一个元素 除第一个元素之外 每个元素均只有一个直接前驱 除最后一个元素之外 每个元素均只有一个直接后继 21 03 2020 6 现实生活中的线性表 思考 下列哪些关系属于线性关系呢 家族的亲戚关系 同学之间的友谊 恋人之间的爱情 班级同学的名册 食堂窗口前排队 自习教室里占座 21 03 2020 7 线性表中的元素类型 原子类型 如整数 字符等 结构类型 如表示一个学生信息的数据元素 包含学号 姓名 性别等数据项 21 03 2020 8 线性表举例 La 34 89 765 12 90 34 22 数据元素类型为int Ls Hello World China Welcome 数据元素类型为string Lb book1 book2 book100 数据元素类型为下列所示的结构类型 21 03 2020 9 structbookinfo intNo 图书编号char name 图书名称char auther 作者名称 抽象数据类型线性表定义 ADTList 数据对象 D ai ai ElemSet i 1 2 n n 0 数据关系 R ai ai 1 D i 1 2 n n 0 基本操作 InitList L 初始化操作 建立一个空的线性表LDestroyList L 销毁已存在的线性表LClearList L 将线性表清空ListInsert L i e 在线性表L中第i个位置插入新元素eListDelete L i e 删除线性表L中第i个位置元素 并用e返回其值IsEmpty L 若线性表为空 返回true 否则返回falseListLength L 返回线性表L的元素个数LocateElem L e 将线性表L中查找与给定值e相等的元素 若成功返回该 元素在表中的序号 否则返回0GetElem L i e 将线性表L中的第i个位置元素返回给e ADTList 21 03 2020 10 改进型操作 引用型操作 实现两个线性集合的并集 21 03 2020 11 将所有的在线性表Lb中但不在La中的数据元素插入到La中 voidListUnion List 插入 线性表怎么在计算机里存储 21 03 2020 12 内容提要 线性表的定义和基本操作线性表的顺序存储结构线性表的链式存储结构 单链表 21 03 2020 13 线性表的顺序存储结构 用一组连续的存储单元依次存储线性表中的每个数据元素 21 03 2020 14 a1 a2 ai ai 1 an 内容 地址 元素在表中的位序 1 2 i i 1 n L b LOC a1 b b L b b i 1 L b b n 1 L b b maxLen 1 L 空闲区 注意 L为每个数据元素占据的存储单元数目 LOC ai 为数据元素ai的地址则LOC ai 1 LOC ai LLOC ai LOC a1 i 1 L 线性表的顺序存储结构例题 例 一个一维数组 下标的范围是 到 每个数组元素用相邻的 个字节存储 存储器按字节编址 设存储数组元素 的第一个字节的地址是98 则 的第一个字节的地址是 21 03 2020 15 解 地址计算通式为 LOC ai LOC a1 L i 1 因此 LOC M 3 98 5 4 1 113 顺序存储结构的特点 存储单元地址连续 需要一段连续空间 逻辑上相邻的数据元素其物理位置也相邻 存储密度大 100 随机存取 知道地址即可直接访问 21 03 2020 16 怎样用C语言实现线性表的顺序存储结构 21 03 2020 17 线性表顺序存储类型的C语言定义 21 03 2020 18 defineLIST MAX LENGTH100 线性表的最大长度typedefstruct ElemType elem 指向存放线性表中数据元素的基地址intlength 线性表的当前长度 SQ LIST 函数结果状态代码 defineTRUE1 defineFALSE0 defineOK1 defineERROR0 defineINFEASIBLE 1 defineOVERFLOW 2 Status是函数的类型 其值是函数结果状态代码typedefintStatus 注意 随后的程序我们需要使用下列预定义常量和类型 length elem SQ LIST 线性表顺序存储类型的基本操作 1 构造一个空的线性表LInitList L 2 销毁已存在的线性表LDestoryList L 3 清空已存在的线性表LClearList L 4 求线性表L的长度ListLength L 5 判断线性表L是否为空IsEmpty L 6 获取线性表L中的某个数据元素内容GetElem L i e 7 检索值为e的数据元素LocateElem L e 8 在线性表L中插入一个数据元素ListInsert L i e 9 删除线性表L中第i个数据元素ListDelete L i e 21 03 2020 19 注意 4 5 6 7属于引用型操作 即线性表本身不被修改 而1 2 3 8 9属于改进型操作 即线性表本身将被修改 线性表顺序结构的算法实现 1 21 03 2020 20 StatusInitList SQ LIST L L elem ElemType malloc LIST MAX LENGTH sizeof ElemType 分配空间if L elem NULL returnERROR 若分配空间不成功 返回ERRORL length 0 将当前线性表长度置0returnOK 成功返回OK 1 初始化线性表L 注意 线性表长度和数组长度的区别 数组长度一般是所分配空间的最大长度 一般是不变的 线性表长度是当前数据元素的数目 一开始为零 且随着数据的插入删除而变化 length 0 elem L sizeof ElemType LIST MAX LENGTH 线性表顺序结构的算法实现 2 2 销毁线性表L 21 03 2020 21 voidDestroyList SQ LIST L if L elem free L elem 释放线性表占据的所有存储空间 voidClearList SQ LIST L L length 0 将线性表的长度置为0 3 清空线性表L length 9 elem L length 9 elem L length 0 线性表顺序结构的算法实现 3 21 03 2020 22 4 求线性表L的长度 intGetLength SQ LISTL return L length 5 判断线性表L是否为空 intIsEmpty SQ LISTL if L length 0 returnTRUE elsereturnFALSE 线性表顺序结构的算法实现 4 21 03 2020 23 6 获取线性表L中的某个数据元素的内容 intGetElem SQ LISTL inti ElemType e if iL length returnERROR 判断i值是否合理 若不合理 返回ERROR e L elem i 1 数组中第i 1的单元存储着线性表中第i个数据元素的内容returnOK 注意 现实中的例子 还记得周星星的电影吗 9527 出来 线性表顺序结构的算法实现 5 21 03 2020 24 7 在线性表L中检索值为e的数据元素 intLocateElem SQ LISTL ElemTypee 算法2 6 for i 0 i L length i if L elem i e 如果第i个元素与检索值相等returni 1 return0 A B C D E F G H 空闲空间 一队嫌疑人 就是你 抓起来 线性表顺序结构的算法实现 6 21 03 2020 25 8 在线性表L中第i个数据元素之前插入数据元素e StatusListInsert SQ LIST L inti ElemTypee 算法2 4 if L length LIST MAX LENGTH returnERROR 检查是否有剩余空间if iL length 1 returnERROR 检查i值是否合理for j L length 1 j i i 将线性表第i个元素之后的所有元素向后移动 L elem j L elem j 1 L elem i 1 e 将新元素的内容放入线性表的第i个位置L length 线性表的长度加一returnOK 线性表顺序结构的算法实现 6续 21 03 2020 26 A B C D E F G H 空闲空间 插队前 大哥 求求你 A B C D E F G H 空闲空间 插队后 大哥 谢谢你 加塞的出去 插入算法的分析 时间复杂度从算法流程上看 查找插入位置 插入元素的时间花费是常数级 而算法执行时间主要消耗在插入前元素的移动上 而移动元素的个数与插入位置i有关 最好情况 在表尾插入 不移动元素 T n O 1 最坏情况 在表头插入 移动n个元素 T n O n 平均复杂度 设pi为在第i个元素之前插入一个元素的概率 且P1 P2 Pi Pn 1 n 1 则平均移动次数为 即T n O n 空间复杂度不需要额外空间 S n O 1 21 03 2020 27 线性表顺序结构的算法实现 7 9 将线性表L中第i个数据元素删除 21 03 2020 28 StatusListDelete SQ LIST L inti ElemType e 算法2 5 if IsEmpty L returnERROR 检测线性表是否为空if iL length returnERROR 检查i值是否合理 e L elem i 1 将欲删除的数据元素内容保留在e所指示的存储 单元中for j i jlength 1 j 将线性表第i 1个元素之后的所有元素向前移动 L elem j 1 L elem j L length returnOK 线性表顺序结构的算法实现 7续 21 03 2020 29 A B C D E F G H 空闲空间 逃离后 A B C D E F G H 空闲空间 逃离前 骗子 还我钱 删除算法的分析 时间复杂度在进行删除操作时 若假定删除每个元素的可能性均等 则平均移动元素的个数为 分析结论顺序存储结构表示的线性表 在做插入或删除操作时 平均需要移动大约一半的数据元素 当线性表的数据元素量较大 并且经常要对其做插入或删除操作时 这一点需要值得考虑 21 03 2020 30 顺序结构总结 顺序表的优缺点优点 利用存储顺序表示相应的逻辑顺序 不需要额外的存储空间来表示元素间的逻辑关系 可以快速地存取表中的任意一个元素 缺点 插入和删除元素时要移动大量的元素 对于长度变化较大的线性表 要一次性地分配足够的存储空间 但这些空间常常又得不到充分的利用 容易造成存储空间的 碎片 顺序表的基本运算的复杂度插入T n O n S n O 1 删除T n O n S n O 1 21 03 2020 31 怎么应对线性表顺序存储结构的缺点 21 03 2020 32 内容提要 线性表的定义和基本操作线性表的顺序存储结构线性表的链式存储结构 单链表 21 03 2020 33 线性表的链式存储结构 线性表的链式存储结构是指用一组任意的存储单元 可以连续 也可以不连续 存储线性表中的数据元素 为了反映数据元素之间的逻辑关系 对于每个数据元素不仅要表示它的具体内容 还要附加一个表示它的直接后继元素存储位置的信息 假设有一个线性表 a b c d 可用下图所示的形式存储 21 03 2020 34 链式存储结构的特点 线性表中的数据元素在存储单元中的存放顺序与逻辑顺序不一定一致 在对线性表操作时 只能通过头指针进入链表 并通过每个结点的指针域向后扫描其余结点 这样就会造成寻找第一个结点和寻找最后一个结点所花费的时间不等 具有这种特点的存取方式被称为顺序存取方式 21 03 2020 35 注意 和随机存取方式的不同 想想单线联系的地下党组织 线性表链式存储结构的结点 术语表示每个数据元素的两部分信息组合在一起被称为结点 其中表示数据元素内容的部分被称为数据域 data 表示直接后继元素存储地址的部分被称为指针或指针域 next 单链表简化的描述形式 21 03 2020 36 head a b c d 其中 head是头指针 它指向单链表中的第一个结点 这是单链表操作的入口点 由于最后一个结点没有直接后继结点 所以 它的指针域放入一个特殊的值NULL NULL值在图示中常用 符号表示 带头结点的单链表 head a b c d 我们为了更方便地对链表进行操作 会在单链表的第一个结点前附设一个结点 成为头结点 头结点的数据域可以不存储任何信息 或者存储如线性表的长度等附加信息 头结点的指针域存储指向第一个结点的指针 线性表链式存储结构的结点 续 21 03 2020 37 head a b c d head a b c d 线性表的链式存储结构的类型定义 C语言 21 03 2020 38 typedefstructnode 结点类型 ElemTypedata structnode next NODE typedefstructlink list 链表类型 NODE head LINK LIST data next NODE head LINK LIST 线性表链式存储类型的基本操作 1 构造一个空的线性表LInitList L 2 求线性表L的长度ListLength L 3 判断线性表L是否为空IsEmpty L 4 获取线性表L中的某个数据元素内容GetElem L i e 5 检索值为e的数据元素LocateELem L e 6 返回线性表L中e的直接前驱元素PriorElem L e 7 返回线性表L中e的直接后继元素NextElem L e 8 在线性表L中插入一个数据元素ListInsert L i e 9 删除线性表L中第i个数据元素ListDelete L i e 10 销毁已存在的线性表LDestoryList L 11 清空已存在的线性表LClearList L 21 03 2020 39 线性表链式结构的算法实现 1 1 初始化链表L 21 03 2020 40 intInitList LINK LIST L L head NODE malloc sizeof NODE 为头结点分配存储单元if L head L head next NULL returnOK elsereturnERROR NULL next head L head 线性表链式结构的算法实现 2 21 03 2020 41 2 求链表L的长度 intListLength LINK LISTL NODE p intlen for p L head len 0 p next NULL p p next len return len NULL next head L data1 next data2 next returnlen 线性表链式结构的算法实现 3 21 03 2020 42 3 判链表L空否 intIsEmpty LINK LISTL if L head next NULL returnTRUE elsereturnFALSE NULL next head L returnTRUE 线性表链式结构的算法实现 4 21 03 2020 43 4 通过e返回链表L中第i个数据元素的内容 voidGetElem LINK LISTL inti ElemType e NODE p intj if iListLength L 检测i值的合理性exitERROR for p L head j 0 j i p p next j 找到第i个结点 e p data 将第i个结点的内容赋给e指针所指向的存储单元中 NULL next head L data1 next data2 next 假设 i 2 e p data 线性表链式结构的算法实现 5 21 03 2020 44 5 在链表L中检索值为e的数据元素 NODE LocateElem LINK LISTL ElemTypee NODE p for p L head next p NULL next head L data1 next e next P P returnp 线性表链式结构的算法实现 6 21 03 2020 45 6 返回链表L中结点e的直接前驱结点 NODE PriorElem LINK LISTL NODE e NODE p if L head next e 检测第一个结点returnNULL for p L head p next NULL next head L data1 next data2 next P data3 next e P returnp P 线性表链式结构的算法实现 7 21 03 2020 46 7 返回链表L中结点e的直接后继结点 NODE NextElem LINK LISTL NODE e NODE p for p L head next p NULL next head L data1 next data2 next P data3 next P returnp e P 线性表链式结构的算法实现 8 21 03 2020 47 8 在链表L中第i个数据元素之前插入数据域为e的元素 intListInsert LINK LIST L inti ElemTypee NODE p s intj if iListLength L 1 returnERROR s NODE malloc sizeof NODE line 7 10 创建数据域为e的元素if s NULL returnERROR s data e for p L head j 0 p 线性表链式结构的算法实现 8续 21 03 2020 48 8 在链表L中第i个数据元素之前插入数据域为e的元素 intListInsert LINK LIST L inti ElemTypee NODE p s 0 检查i是否在合理范围内 1 创建数据域为e的元素 此时s指向被创建的新数据元素 2 寻找第i 1个结点 此时p指向第i 1个结点s next p next p next s 3 将s结点插入returnOK datai 1 datai P datas next S next next next next 线性表链式结构的算法实现 9 21 03 2020 49 9 将链表L中第i个数据元素删除 并将其内容保存在e中 intListDelete LINK LIST L inti ElemType e NODE p s intj if iListLength L 检查i值的合理性returnERROR for p L head j 0 jnext j 寻找第i 1个结点s p next 用s指向将要删除的结点 e s data p next s next 删除s指针所指向的结点free s returnOK 线性表链式结构的算法实现 9续 21 03 2020 50 9 将链表L中第i个数据元素删除 并将其内容保存在e中 intListDelete LINK LIST L inti ElemType e NODE p s 0 检查i值的合理性 1 寻找第i 1个结点 p指向第i 1个结点s p next 2 用s指向将要删除的结点 e s data 3 将要删除的内容保存在e中p next s next 4 删除s指针所指向的结点free s returnOK datai 1 datai 1 next next datai next P S e s data 线性表链式结构的算法实现 10 10 销毁链表L 21 03 2020 51 voidDestoryList LINK LIST L NODE p while L head 依次删除链表中的所有结点 p L head L head L head next free p NULL head L data next P P 线性表链式结构的算法实现 11 21 03 2020 52 11 清空链表L voidClearList LINK LIST L NODE p while L head next p L head next p指向链表中头结点后面的第一个结点L head next p next 删除p结点free p 释放p结点占据的存储空间 NULL L data2 next P P next head data1 单链表结构和顺序存储结构的对比 21 03 2020 53 思考 游戏设计中 存储用户注册信息用什么结构 存储玩家的装备或武器列表用什么结构 用类C语言实现单链表结构的归并算法 21 03 2020 54 voidMergeList L LinkList MergeList L 用类C语言实现顺序存储结构的归并算法 21 03 2020 55 voidMergeList SqListLa SqListLb SqList 插入Lb的剩余元素