数据结构之线性表2 内容提要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 fir