重庆大学数据结构第二章线性表.ppt

第二章线性表 2 1线性表的类型定义线性表 是一种最简单的线性结构 线性结构是一个数据元素的有序 次序 集合 它有四个基本特征 1 集合中必存在唯一的一个 第一元素 2 集合中必存在唯一的一个 最后元素 3 除最后元素之外 其它数据元素均有唯一的 后继 4 除第一元素之外 其它数据元素均有唯一的 前驱 例1 26个英文字母组成的字母表 A B C Z 例2 某校从1978年到1983年各种型号的计算机拥有量的变化情况 6 17 28 50 92 188 例3 学生健康情况登记表如下 例4 一副扑克的点数 2 3 4 J Q K A 2 1 1抽象数据类型线性表的定义通常以下列 n个数据元素的序列 表示线性表 Linear List a1 a2 ai an 表长 序列中数据元素的个数n 空表 n 0时的线性表 位序 称i为ai在线性表中的位序 线性表的抽象数据类型的定义如下 ADTList 数据对象 D ai ai ElemSet i 1 2 n n 0 线性表中的数据元素可以是各种各样的 只要是属于同一个集合即可 数据关系 R1 ai 1 ai D i 2 n 序偶表示ai 1是ai的直接前驱 反之 ai是ai 1的直接后继 基本操作 p 19 ADTList 2 1 2线性表类型的应用例2 1已知集合A和B 求两个集合的并集 使A A B 且B不再单独存在 上述集合求并的问题可演绎为 扩大线性表LA 将存在于线性表LB中而不存在于线性表LA中的数据元素插入到线性表LA中去 具体操作步骤为 1 从线性表LB中取出一个数据元素 2 依值在线性表LA中进行查询 3 若不存在 则将它插入到LA中 重复上述三步直至LB为空表止 容易看出 上述的每一步恰好对应线性表的一个基本操作 1 ListDelete LB 1 e 2 LocateElem LA e equal 3 ListInsert LA n 1 e 算法2 1voidunion List 销毁线性表LB union 例2 2已知一个 非纯集合 B 试构造一个集合A 使A中只包含B中所有值各不相同的数据元素 与上例相比 不同之处仅仅在于两点 1 例2 1的算法中LA是已知的 而在此例算法中的LA是待新建的 2 例2 1在求得并集之后 原来的两个集合不再保留 而在此例中构建新的集合A的同时 原来的集合B不变 算法2 2voidpurge List 当LA中不存在和e值相同的数据元素时进行插入 for purge 例2 3判别两个集合是否相等 两个集合相等的充分必要条件是 它们具有相同的元素 但相同的数据元素在各自的线性表中的 位序 不一定相同 算法的基本思想为 1 首先判别两者的表长是否相等 2 在表长相等的前提下 如果对于一个表中的所有元素 都能在另一个表中找到和它相等的元素的话 便可得到 两个线性表表示的集合相等 的结论 反之 只要有一个元素在另一个表中不能找到相等元素时 便可得出 不等 的结论 算法2 3boolisEqual ListLA ListLB 若线性表LA和LB不仅长度相等 且所含数据元素也相同 则返回TRUE 否则返回FALSE La len Listlength LA Lb len Listlength LB if La len Lb len returnFALSE 两表的长度不等else i 1 found TRUE while i La len else isEqual 2 2线性表的顺序表示和实现2 2 1顺序表顺序表是线性表的顺序存储表示的简称 它指的是 用一组地址连续的存储单元依次存放线性表中的数据元素 即以 存储位置相邻 表示 位序相继的两个数据元素之间的前驱和后继的关系 有序对 并以表中第一个元素的存储位置作为线性表的起始地址 称作线性表的基地址 如下图所示 不失一般性 假设每个数据元素占据的存储量是一个常量C 则后继元素的存储地址和其前驱元素相隔一个常量 即 LOC ai LOC ai 1 C 一个数据元素所占存储量所有数据元素的存储位置均可由第一个数据元素的存储位置得到LOC ai LOC a1 i 1 C 基地址 用C语言描述的顺序表类型如下所示 存储结构 defineLIST INIT SIZE100 预设的存储空间初始分配量 defineLISTINCREMENT10 分配增量typedefstruct ElemType elem 存储空间基址intlength 当前长度intlistsize 允许的最大存储容量 以sizeof ElemType 为单位 SqList 2 2 2顺序表中基本操作的实现一 初始化操作算法2 4voidInitList SqList 初始存储容量 InitList此算法的时间复杂度为O 1 二 元素定位操作算法2 5动画intLocateElem SqListL ElemTypee void compare ElemType ElemType 在顺序表L中查找第1个值与e满足判定条件compare 的元素 若找到 则返回其在L中的位序 否则返回0 i 1 i的初值为第1元素的位序p L elem p的初值为第1元素的存储位置while i L length 该线性表中不存在满足判定的数据元素 LocateElem此算法的时间复杂度为 O ListLength L 三 插入元素操作演示算法2 6boolListInsert SqList ListInsert此算法的时间复杂度为 O ListLength L 算法演示 四 删除元素操作演示算法2 7boolListDelete SqList ListDelete算法演示此算法的时间复杂度为 O ListLength L 五 销毁结构操作算法2 8voidDestroyList SqList DestroyList Sq此算法的时间复杂度为 O 1 六 插入和删除操作的性能分析在第i个位置上插入一个结点的移动次数为n i 1 删除表中第i个结点的移动次数为n i 在等概率假设的情况下 在长度为n的顺序表中进行一次插入 删除操作时所需进行 移动 元素个数的期望值 即平均移动个数 分别为 插入 Eis n 2 删除 Edl n 1 2因此 顺序存储表示仅适用于不常进行插入和删除操作 表中元素相对稳定的线性表 2 2 3顺序表其它算法举例例2 4试编写算法 比较 两个顺序表的大小 算法2 9intcompare SqListA SqListB 若AB 则返回1j 0 while jB elem j return 1 elsej if A length B length return 0 elseif A length B length return 1 elsereturn 1 compare上述算法中只有一个while循环 它的执行次数依赖于待比较的顺序表的表长 因此 算法2 9的时间复杂度为O Min A length B length 例2 5试设计一个算法 用尽可能少的辅助空间将顺序表中前m个元素和后n个元素进行互换 即将线性表 a1 a2 am b1 b2 bn 改变成 b1 b2 bn a1 a2 am 方法1 演示方法2 演示算法2 10voidinvert ElemType for invert 算法2 11voidexchange SqList exchange 例2 6编写算法删除顺序表中 多余 的数据元素 即使操作之后的顺序表中所有元素的值都不相同 方法1 演示方法2 演示算法2 12voidpurge Sq SqList 修改表长 purge Sq此算法的时间复杂度为O ListLength2 L 分析 从这个题的算法可以得到一些有益的启示 某种情况下 删除 操作也可利用 插入 来实现 2 3线性表的链式表示和实现2 3 1单链表和指针线性表的链式存储表示的特点是用一组任意的存储单元存储线性表的数据元素 这组存储单元可以是连续的 也可以是不连续的 数据域data指针域next其中 data域是数据域 用来存放结点的值 next是指针域 亦称链域 用来存放结点的直接后继的地址 或位置 显然 单链表中每个结点的存储地址是存放在其前趋结点next域中 而开始结点无前趋 故应设头指针head指向开始结点 同时 由于终端结点无后继 故终端结点的指针域为空 即null 图示中也可用 表示 例1 线性表 bat cat eat fat hat jat lat mat 的单链表示意图如下 110 130135 160头指针head165170 200205 可以用C语言中的 结构指针 来描述链表结构 typedefstructLNode ElemTypedata structLNode next LNode LinkList 若设LNode p q LinkListH 则p q和H均为以上定义的指针型变量 2 3 2单链表中基本操作的实现一 初始化操作初始化建一个空的链表即为建立一个只有头结点的链表 算法2 13voidInitList LinkList InitList算法的时间复杂度为O 1 二 销毁结构操作算法2 14voidDestroyList LinkList while DestroyList算法的时间复杂度为O Listlength L 三 存取元素操作演示算法2 15boolGetElem LinkListL intpos ElemType GetElem算法的时间复杂度为O ListLength L 四 插入元素操作演示算法2 16boolListInsert LinkList ListInsert算法时间复杂度为O ListLength L 五 删除元素操作演示算法2 17boolListDelete LinkList ListDelete L算法时间复杂度为O ListLength L 2 3 3单链表其它算法举例例2 7逆序创建链表假设线性表 a1 a2 an 的数据元素存储在一维数组A n 中 则从数组的最后一个分量起 依次生成结点 并逐个插入到一个初始为 空 的链表中 算法2 19动画voidCreateList L LinkList 插入在头结点之后 for CreateList L算法的时间复杂度为O ListLength L 例2 8以链表作存储结构解例2 5的问题 即将线性表 a1 a2 am b1 b2 bn 改变成 b1 b2 bn a1 a2 am 演示算法2 20voidexchange L LinkList 将a1结点链接到bn结点之后 if p if m exchange L算法的时间复杂度为O ListLength L 例2 9编写算法删除单链表中 多余 的数据元素 即使操作之后的单链表中所有元素的值都不相同 算法2 21voidpurge L LinkList for purge L此算法的时间复杂度为O ListLength2 L 链式存储结构的优势 1 能有效利用存储空间 2 用 指针 指示数据元素之间的后继关系 便于进行 插入 删除 等操作 链式存储结构的劣势 1 不能随机存取数据元素 2 丢失了一些顺序表有的长处 如线性表的 表长 和数据元素在线性表中的 位序 在上述的单链表中都看不见了 3 不便于在表尾插入元素 需遍历整个表才能找到插入的位置 2 3 4循环链表循环链表 CircularLinkedList 是线性表的另一种形式的链式存储表示 循环链表的操作和单链表基本一致 差别仅在于 判别链表中最后一个结点的条件不再是 后继是否为空 而是 后继是否为头结点 2 3 5双向链表顾名思义 双向链表 DoubleLinkedList 的特点是其结点结构中含有两个指针域 其一指向数据元素的 直接后继 另一指向数据元素的 直接前驱 用C语言描述如下 typedefstructDuLNode ElemTypedata structDuLNode prior structDuLNode next DuLNode DuLinkList 在双向链表上进行插入和删除时必须同时修改两个方向上的指针 插入 算法2 22动画voidListInsert DuL DuLinkList ListInsert DuL 删除 算法2 23动画voidListDelete DuL DuLinkList ListDelete DuL 2 4一元多项式的表示及相加P 39 本章小结本章介绍了线性表的抽象数据类型的定义以及它的两种存储结构的实现 线性表是n n 0 个数据元素的序列 通常写成 a1 a2 an 线性表中除了第一个和最后一个元素之外都只有一个前驱和一个后继 线性表中每个元素都有自己确定的位置 即 位序 n 0时的线性表称为 空表 它是线性表的一种特殊状态 因此在写线性表的操作算法时一定要考虑你的算法对空表的情况是否也正确 顺序表是线性表的顺序存储结构的一种别称 它的特点是以 存储位置相邻 表示两个元素之间的前驱后继关系 因此 顺序表的优点是可以随机存取表中任意一个元素 其缺点是每作一次插入或删除操作时 平均来说必须移动表中一半元素 常应用于主要是为查询而很少作插入和删除操作 表长变化不大的线性表 链表是线性表的链式存储结构的别称 它的特点是以 指针 指示后继元素 因此线性表的元素可以存储在存储器中任意一组存储单元中 它的优点是便于进行插入和删除操作 但不能进行随机存取 为取得表中任意一个数据元素都必须从第一个数据元素起查询 由于它是一种动态分配的结构 结点的存储空间可以随用随取 并在删除结点时随时释放 以便系统资源更有效地被利用