数据结构之线性表(ppt 76页).ppt

第二章线性表 DATASTRUCTURE 数据结构 引言线性表是一种线性数据结构 其用途非常广泛 用于信息检索 存储管理 模拟技术 通信等领域 内容提要1 定义线性表抽象数据类型 2 讨论线性表的顺序存储表示方法 3 讨论单链表 循环链表等链接存储表示方法 4 线性表的应用实例 多项式的算术运算 2 1线性表抽象数据类型 课堂提要第2章线性表2 1线性表ADT2 2线性表的顺序表示2 3线性表的链接表示2 4多项式的算术运算 1 线性表举例 线性表是n 0 个元素a0 a1 an 1的有序集合 记为 a0 a1 an 1 其中 n是线性表中元素的个数 称为线性表的长度 n 0时称为空表 设ai是线性表 a0 a1 an 1 中第i个元素 i 0 1 n 1 则称ai是ai 1的直接前驱元素 ai 1是ai的直接后继元素 线性表是动态数据结构 它的表长可以改变 2 线性表的定义 ADT2 1线性表抽象数据类型ADTLinearList Data 零个或多个元素的有序集合 Operations Create 创建一个空线性表 Destroy 撤消一个线性表 IsEmpty 若线性表空 则返回true 否则返回false Length 返回表中元素个数 Find i x 在x中返回表中下标为i的元素ai 即表中第i 1个元素 如果不存在 则返回false 否则返回true Search x 返回x在表中的下标 若x不在表中 则返回 1 Insert i x 在元素ai之后插入x 若i 1 则x插在第一个元素a0前 插入成功返回true 否则返回false Delete i 删除元素ai 删除成功返回true 否则返回false Update i x 将元素ai的值修改为x 修改成功返回true 否则返回false Output out 把表送至输出流 3 线性表抽象数据类型 4 线性表的C 模板抽象类 程序2 1线性表的C 类templateclassLinearList public virtualboolIsEmpty const 0 virtualintLength const 0 virtualboolFind inti T 2 2线性表的顺序表示 1 线性表的两种存储表示法 1 顺序表示法 2 链接表示法2 线性表的顺序表示法是用一组地址连续的存储单元依次存储线性表中元素 顺序表示的线性表程为顺序表 存储结构是逻辑结构在机内的映象 包括 元素和关系 课堂提要第2章线性表2 1线性表ADT2 2线性表的顺序表示2 3线性表的链接表示2 4多项式的算术运算 1 线性表的顺序表示法 若已知顺序表示的线性表中每个元素占k个存储单元 第一个元素a0在计算机内存中的地址是loc a0 则表中任意一个元素ai在内存中的存储地址loc ai 为loc ai loc a0 i k只要给定loc a0 和k 就可以确定线性表中任意一个元素的存储地址 换句话说 顺序表是一种随机存取结构 2 地址计算公式 3 顺序表类 程序2 1线性表的C 类templateclassLinearList public virtualboolIsEmpty const 0 virtualintLength const 0 virtualboolFind inti T templateclassSeqList publicLinearList public SeqList intmSize SeqList Delete elements boolIsEmpty const intLength const boolFind inti T SeqListL 5 定义了一个有5个整型值的顺序表对象 程序2 2线性表的顺序表实现 classSeqList publicLinearList public SeqList intmSize private intmaxLength T elements 动态一维数组的指针 4 动态一维数组描述顺序表 顺序表在一维数组中的存储 1 构造函数 创建一个顺序表templateSeqList SeqList intmSize maxLength mSize elements newT maxLength n 0 2 析构函数 撤消一个顺序表templateSeqList SeqList delete elements 1 查找下标为i的元素aiFind i x 在x中返回表中下标为i的元素ai 即表中第i 1个元素 如果不存在 则返回false 否则返回true x elements i 渐近时间复杂度 O 1 5 在顺序存储表示下实现线性表上定义的操作 templateboolSeqList Find inti T 渐近时间复杂度 O 1 2 插入操作Insert i x 在表中下标为i的元素ai后插入x 若i 1 则将新元素x插在最前面 若插入成功 返回true 后移n i 1个元素 01 ii 1i 2 n 1 maxLength 1 a0a1 ai 插入操作 an 1 x ai 1 插入操作算法 templateboolSeqList Insert inti Tx if in 1 couti j elements j 1 elements j elements i 1 x n returntrue 分析 设顺序表长度为n 则在位置i i 1 0 n 1 后插入一个元素要移动n i 1个元素 设共有n 1个可插入元素的位置 并设在各位置处插入元素的概率是相等的 即Pi 1 n 1 则平均情况下在表中插入元素需要移动元素的个数为 渐近时间复杂度 O n ai a0 ai 1 3 删除操作Delete i 删除元素ai 0 i 1ii 1i 2 n 1 maxLength 1 删除操作 an 1 ai 1 删除操作算法 templateboolSeqList Delete inti if n coutn 1 cout OutOfBounds endl returnfalse for intj i 1 j n j elements j 1 elements j n returntrue 分析 设顺序表长度为n 则删除元素ai i 0 n 1 要移动n i 1元素 若删除表中每个元素的概率是相等的 即Qi 1 n 则平均情况下从表中删除一个元素需要移动元素的个数为 渐近时间复杂度 O n 4 顺序表的应用 集合求 并 求集合A和B的并 两集合求并的算法思想是 置i 0 若i小于集合LB的元素个数 则做 否则转 取出集合LB中i位置的元素x 若x不在集合LA中 则将其插入集合LA的最后位置 i 转 继续 结束 求集合A和B的并 求集合A和B的并 例2 1求集合A和B的并A 分析 集合可以看成是线性表 用顺序表LA和LB分别表示集合A和B 并 的结果放在LA中 用顺序表类SeqList实现集合 并 算法的程序 存入头文件seqlistu h中 include seqlist h templatevoidUnion SeqList 其插入集合LA中 include seqlistu h constintSIZE 20 voidmain SeqListLA SIZE 定义顺序表对象LA 表示集合ASeqListLB SIZE 定义顺序表对象LB 表示集合Bfor inti 0 i 5 i 插入元素0 4 构造集合LA 0 1 2 3 4 LA Insert i 1 i for i 5 i 10 i 插入5 9 构造集合B 5 6 7 8 9 LB Insert i 6 i LB Insert 1 0 LB中插入0 LB 0 5 6 7 8 9 LB Insert 3 2 LB中插入2 LB 0 5 6 7 2 8 9 LB Insert LB Length 1 4 LB中插入4 LB 0 5 6 7 2 8 9 4 Union LA LB 两集合并 结果放入LA中LA Output cout 输出最终结果LA 0 1 2 3 4 5 6 7 8 9 6 线性表的顺序存储表示的优缺点 1 优点 随机存取 存储空间利用率高 2 缺点 插入 删除效率低 必须按事先估计的最大元素个数分配连续的存储空间 难以临时扩大 2 3线性表的链接表示 1 线性表的链接存储表示法 1 单链表 2 带表头结点的链表 3 循环链表 4 双向链表 课堂提要第2章线性表2 1线性表ADT2 2线性表的顺序表示2 3线性表的链接表示2 3 1单链表2 3 2带表头结点的单链表2 3 3循环链表2 3 4双向链表2 4多项式的算术运算 2 3 1单链表 1 单链表存储表示法 1 单链表的结点结构 课堂提要第2章线性表2 1线性表ADT2 2线性表的顺序表示2 3线性表的链接表示2 3 1单链表2 3 2带表头结点的单链表2 3 3单循环链表2 3 4双向链表2 4多项式的算术运算 单链表在内存中的示意图 2 单链表结构 注意 单链表头指针first不能少 最后一个结点的指针域为 逻辑上相邻的元素在物理上不一定相邻 不能出现 断链 现象 first 顺序表类SeqList 单链表类SingleList和作为基类的线性表类LinearList三者的结构 图2 6SeqList SingleList和LinearList三者的结构关系 2 单链表结点类 程序2 3线性表的单链表实现 include linearlist h templateclassSingleList templateclassNode private Telement Node link friendclassSingleList 3 单链表类程序2 3线性表的单链表实现 templateclassSingleList publicLinearList public SingleList first NULL n 0 构造函数 SingleList boolIsEmpty const intLength const boolFind inti T 析构函数templateSingleList SingleList Node p while first p first link deletefirst first p 单链表 p first 4 在单链表上实现线性表上定义的操作 1 查找第k个元素 2 插入操作 3 删除操作 1 查找元素ai 由于链表失去了随机查找元素的特性 所以必须从头指针开始沿链逐个计数查找 查找元素ai的算法templateboolSingleList Find inti T 渐近时间复杂度 O n 2 插入操作 在给定元素ai之后插入值为x的元素 插入算法步骤为 生成数据域为x的新结点 q指向新结点 从first开始找第i 1个结点 p指向该结点 将q插入p之后 表长加1 a0 a1 ai ai 1 an 1 即在此处插入x q 插入时只要修改二个指针 q link p linkp link q 能否对调上述2语句的执行顺序 不能 会 断链 现象 ai ai 1 x p 将q插入p之后 templateboolSingleList Insert inti Tx if in 1 cout q newNode q element x 生成新结点qNode p first for intj 0 jlink if i 1 q link p link p link q 在p之后插入q else q link first first q 插字第一个元素之前 n returntrue 渐近时间复杂度 O n 3 删除操作 删除元素ai a0 a1 ai an 1 即删除该元素 删除算法步骤为 从first开始找第i 1个结点 p指向该结点 q指向p之前驱结点 从单链表中删除p 释放p之空间 表长减1 ai ai 1 ai 1 q p 删除时只要修改一个指针 q link p link 删除p templateboolSingleList Delete inti if n coutn 1 cout p first q first for intj 0 jlink if i 0 first first link else p q link q link p link deletep n returntrue 渐近时间复杂度 O n 5 单链表的应用 集合求 交 求集合A和B的并 两集合求交的算法思想是 置i 0 若i小于集合LA中当前元素的个数 则做 否则转 取出集合LA中i位置的元素x 若x不在集合LB中 则将其从集合LA中删除 否则i 转 继续 结束 求集合A和B的并 例2 2求集合A和B的交A 分析 集合可以看成是线性表 用单链表LA和LB分别表示集合A和B 交 的结果放在LA中 include singlelist h templatevoidIntersection SingleList 否则i 2 3 2带表头结点的单链表 上一节介绍的单链表在做插入和删除运算时 要考虑一般情况和特殊情况 用带表头结点的单链表可以简化上述两种算法 课堂提要第2章线性表2 1线性表ADT2 2线性表的顺序表示2 3线性表的链接表示2 3 1单链表2 3 2带表头结点的单链表2 3 3单循环链表2 3 4双向链表2 4多项式的算术运算 1 带表头结点的单链表 a0 a1 ai an 1 在原单链表中增加一个结点 但它的element域中不存放线性表中的任何元素 称该结点为表头结点 2 带表头结点单链表的构造 插入和删除 1 构造函数 SingleList SingleList first NULL n 0 HeaderList HeaderList Node first newNode first link NULL n 0 2 插入操作templateboolHeaderList Insert inti Tx if in 1 cout p first for intj 0 jlink Node q newNode q element x q link p link p link q n returntrue 3 删除操作templateboolHeaderList Delete inti if n coutn 1 cout q first p for intj 0 jlink p q link q link p link deletep n returntrue q p 例如删除a2 2 3 3单循环链表 1 单循环链表 单循环链表可以从表中任一结点出发访问表中所有结点 课堂提要第2章线性表2 1线性表ADT2 2线性表的顺序表示2 3线性表的链接表示2 3 1单链表2 3 2带表头结点的单链表2 3 3单循环链表2 3 4双向链表2 4多项式的算术运算 带表头结点的单循环链表 不带表头结点的单循环链表 非空表 a0 a1 a2 an 1 first 非空表 2 3 4双向链表 1 双向链表 1 双向链表的结点结构 课堂提要第2章线性表2 1线性表ADT2 2线性表的顺序表示2 3线性表的链接表示2 3 1单链表2 3 2带表头结点的单链表2 3 3单循环链表2 3 4双向链表2 4多项式的算术运算 2 带表头结点的双向循环链表 2 双向链表的插入 插入操作的核心步骤是 1 DNode q newDNode q data x 2 q llink p llink q rlink p p llink rlink q p llink q 能否颠倒顺序 2 双向链表的删除 删除操作的核心步骤是 1 p llink rlink p rlink p rlink llink p llink 能否颠倒顺序 2 deletep 2 4多项式的算术运算 线性表是一种最简单 最基本 也是最常用的数据结构 其用途十分广泛 作为线性表应用的一个例子 下面讨论一元整系数多项式的算术运算 从该例中 要学会如何分析元素间的关系 结构的描述 存储方式的选择 如何描述和实现算法 课堂提要第2章线性表2 1线性表ADT2 2线性表的顺序表示2 3线性表的链接表示2 4多项式的算术运算 一元整系数多项式p x 3x14 8x8 6x2 2要求 1 按降幂排列 2 做q x q x p x 1 数据元素该多项式是由一项一项组成的 我们忽略掉各项具体数字的细节 即每一项就是由系数 coef 和指数 exp 组成的 coef xexp 每一项就是一个要处理的数据元素 即 coef exp 分析 2 元素间的逻辑关系由于多项式按降幂排列 因此每一项都有一个指数比它高的项 有一个比它低的项 除了最高项没有比它高的项 最后一项没有比它低的项外 这样 多项式组成了一个线性表 线性表中的每个数据元素是多项式的一项 coef exp 因此 一元整系数多项式可以视为线性表 3 存储表示 用顺序存储 q x 线性表有顺序和链接存储 q x 2x10 8x8 4x2 3 p x 3x14 8x8 6x2 2做q x p x q x 结果为 q x 3x14 2x10 10 x2 5 p x 结果q x 从结果中可以发现 在q x 上做了插入和删除运算 因此不宜采用顺序存储 p x 3x14 8x8 6x2 2 用带表头结点的单循环链表表示一元多项式 多项式的项coef xexp结点结构 2 4 1项结点的C 类 1 项结点的C 类 classTerm 2 多项式的C 类 classPolynominal 3 类Polynominal是类Term的友元类 课堂提要第2章线性表2 1线性表ADT2 2线性表的顺序表示2 3线性表的链接表示2 4多项式的算术运算2 4 1项结点的C 类2 4 2多项式的C 类2 4 3多项式的实现 程序2 6多项式项结点的C 类classPolynominal classTerm public Term intc inte Term intc inte Term nxt Term InsertAfter intc inte 在this指 针指示的项后插入新项private intcoef intexp Term link friendostream 项结点类的两种构造函数Term Term intc inte coef c exp e link 0 Term Term intc inte Term nxt coef c exp e link nxt 项结点类的InsertAfter函数Term Term InsertAfter intc inte 为新项申请结点 并用Term函数将 c e和this link的值填入新结点的相应域link newTerm c e link returnlink 关于项结点类的InsertAfter函数的执行过程 申请新项结点存储单元 新项结点 执行q1 InsertAfter 3 14 Term Term InsertAfter intc inte link returnlink 这里要搞清楚一个问题 上述函数中 link是指哪个结点的指针域 314 new Term c e link q1的指针域 也就是指向q1后继的q 关于项结点类的InsertAfter函数的执行过程 q 210 1 q1 qx 新项结点 执行q1 InsertAfter 3 14 Term Term InsertAfter intc inte link returnlink 314 new Term c e link 再做Term 3 14 q Term Term intc inte Term nxt coef c exp e link nxt 同样的问题 这里的coef exp和link是指哪个结点的三个域 新项结点的三个域 最后执行赋值运算 新项结点的地址赋值给q1的指针域 重载输出操作符 ostream 用 4x 2表示 4x2 2 4 2多项式的C 类 1 多项式类的成员函数 1 AddTerms函数 通过输入流in 输入多项式的各项 c e 构造一个多项式 2 Output函数 将多项式的每一项按降幂方式送输出流 3 PolyAdd函数 实现将多项式r加到指针this指示的多项式上 课堂提要第2章线性表2 1线性表ADT2 2线性表的顺序表示2 3线性表的链接表示2 4多项式的算术运算2 4 1项结点的C 类2 4 2多项式的C 类2 4 3多项式的实现 程序2 7多项式的C 类classPolynominal public Polynominal Polynom