第二章_线性表

第二章线性表 数据结构课程的内容 逻辑结构唯一存储结构不唯一运算的实现依赖于存储结构 线性表的逻辑结构线性表的顺序存储及实现线性表的链接存储及实现顺序表和单链表的比较线性表的其他存储及实现 本章的基本内容是 a1 a2 ai 1 ai ai 1 an 1 线性表的定义 n n 0 个相同类型数据元素的有限序列 n 0时称为 数据元素 线性起点 ai的直接前趋 ai的直接后继 下标 是元素的序号 表示元素在表中的位置 n为元素总个数 即表长 空表 线性终点 2 1线性表的逻辑结构 例1分析26个英文字母组成的英文表 A B C D Z 例2分析学生情况登记表 数据元素都是记录 元素间关系是线性 数据元素都是字母 元素间关系是线性的 2 线性表的特性 1 有限性 线性表中数据元素的个数是有穷的 2 相同性 线性表中数据元素的类型是同一的 3 顺序性 线性表中相邻的数据元素ai 1和ai之间存在序偶关系 即ai 1是ai的前驱 ai是ai 1的后继 a1无前驱 an无后继 其它每个元素有且仅有一个前驱和一个后继 练 判断下列叙述的正误 1 数据的逻辑结构是指数据元素之间的逻辑关系 是用户按使用需要建立的 2 线性表的逻辑结构定义是唯一的 不依赖于计算机 线性结构反映结点间的逻辑关系是一对一的 一维向量是线性表 但二维或N维数组不是 5 同一数据逻辑结构中的所有数据元素都具有相同的特性 是指数据元素所包含的数据项的个数都相等 3 线性表的抽象数据类型定义 ADTseqListisData线性表的长度 若干数据元素 线性表中的数据元素具有相同类型 相邻元素具有前驱和后继关系OperationseqList初始化值 无动作 置顺序表的长度为0 BACK Clear输入 无前置条件 无功能 清空顺序表输出 无后置条件 表的长度是0Length输入 无前置条件 表已存在功能 求表的长度输出 返回表的长度 即表中数据元素的个数后置条件 表不变 BACK Get输入 元素的序号i前置条件 表已存在 i合法功能 在表中取序号为i的数据元素输出 若i合法 返回序号为i的元素值 否则抛出异常后置条件 表不变Locate输入 数据元素item前置条件 表已存在功能 在线性表中查找值等于item的元素输出 若查找成功 返回x在表中的序号 否则返回0后置条件 表不变 BACK Insert输入 插入位置i 待插元素item前置条件 表已存在 i合法功能 在表的第i个位置处插入一个新元素x输出 若插入不成功 抛出异常后置条件 若插入成功 表中增加一个新元素Delete输入 删除位置i前置条件 表已存在功能 删除表中的第i个元素输出 若删除成功 返回被删元素 否则抛出异常后置条件 若删除成功 表中减少一个元素 BACK Empty输入 无前置条件 表已存在功能 判断表是否为空输出 若是空表 返回1 否则返回0后置条件 表不变endADTseqList 进一步说明 1 线性表的基本操作根据实际应用而定 2 复杂的操作可以通过基本操作的组合来实现 3 对不同的应用 操作的接口可能不同 BACK 2 2线性表的顺序存储和实现 2 2 1顺序表的顺序存储表示2 2 2顺序表的实现2 2 3顺序表的算法效率分析 2 2 1顺序表的顺序存储表示 用一组地址连续的存储单元依次存储线性表的元素 可通过静态数组V n 或动态数组来实现 把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构 线性表的顺序表示又称为顺序存储结构或顺序映像 顺序存储定义 顺序存储方法 简言之 逻辑上相邻 物理上也相邻 顺序表是一种随机存取的存储结构 的含义为 查找操作 其时间性能为O 1 线性表顺序存储特点 1 逻辑上相邻的数据元素 其物理上也相邻 2 若已知表中首元素在存储器中的位置 则其他元素存放位置亦可求出 利用数组下标 计算方法是 参见存储结构示意图 设首元素a1的存放地址为LOC a1 称为首地址 设每个元素占用存储空间 地址长度 为L字节 则表中任一数据元素的存放地址为 LOC ai LOC a1 L i 1 LOC ai 1 LOC ai L 注意 C 语言中的数组的下标从0开始 即 V n 的有效范围是V 0 V n 1 线性表的顺序存储结构示意图 地址内容元素在表中的位序 1 i 2 n 空闲区 i 1 L b LOC a1 b L b i 1 L b n 1 L b max 1 L 一个一维数组 下标的范围是 到 每个数组元素用相邻的 个字节存储 存储器按字节编址 设存储数组元素 的第一个字节的地址是 则 的第一个字节的地址是 113 例3 因此 LOC M 3 98 5 3 0 113 解 地址计算通式为 LOC ai LOC a0 L i 0 2 2 2顺序表的实现 1 顺序表的存储结构定义 即顺序表类的声明 constintMaxSize 100 template 定义模板类SeqListclassSeqList public SeqList 无参构造函数SeqList datatypea intn 有参构造函数 SeqList 析构函数为空intLength 求线性表的长度datatypeGet inti 按位查找 取线性表的第i个元素intLocate datatypeitem 查找元素itemvoidInsert inti datatypeitem 在第i个位置插入元素itemdatatypeDelete inti 删除线性表的第i个元素voiddisplay 遍历线性表 按序号依次输出各元素private datatypedata MaxSize 存放数据元素的数组intlength 线性表的长度 操作接口 SeqList 算法描述 templateSeqList SeqList length 0 1 无参构造函数实现 0 2 顺序表的操作实现 即顺序表类的定义实现 操作接口 SeqList datatypea intn 2 有参构造函数实现 5 35 12 24 33 42 算法描述 templateSeqList SeqList datatypea intn if n MaxSize throw 数组元素个数不合法 for inti 0 i n i data i a i length n 操作接口 voidInsert inti datatypeitem 在线性表中第i个位置插入值为item的元素插入前 a1 ai 1 ai an 插入后 a1 ai 1 item ai an 3 插入操作实现 ai 1和ai之间的逻辑关系发生了变化 顺序存储要求存储位置反映逻辑关系 存储位置要反映这个变化 例如 35 12 24 42 在i 2的位置上插入33 表满 length MaxSize合理的插入位置 1 i length 1 i指的是元素的序号 4 35 12 24 42 a1 a2 a3 a4 01234 42 24 12 33 什么时候不能插入 插入算法 在线性表的第i个位置插入一个元素 实现步骤 将第n至第i位的元素向后移动一个位置 将要插入的元素写到第i个位置 表长加1 注意 事先应判断 插入位置i是否合法 表是否已满 应当有1 i length 1或i 1 length 1 for j length j i j data j data j 1 data i 1 item length 元素后移一个位置 插入item 表长加1 核心语句 C 具体实现 templatevoidSeqList Insert inti datatypeitem intj if length MaxSize throw 溢出 if ilength 1 throw i不合法 for j length j i j data j data j 1 data i 1 item length 操作接口 templatedatatypeSeqList Delete inti 删除前 a1 ai 1 ai ai 1 an 删除后 a1 ai 1 ai 1 an 4 操作实现 ai 1和ai之间的逻辑关系发生了变化 顺序存储要求存储位置反映逻辑关系 存储位置要反映这个变化 例 35 33 12 24 42 删除i 2的数据元素 5 35 a1 a2 a3 a4 01234 42 24 12 33 a5 12 24 42 表空 length 0合理的删除位置 1 i length i指的是元素的序号 什么时候不能删除 实现步骤 获得第i个要删除的元素值 将第i 1至第n位的元素向前移动一个位置 表长减1 注意 事先需要判断 删除位置i是否合法 应当有1 i length或i 1 length 删除删除线性表的第i个位置上的元素 for j i j length j data j 1 data j length 元素前移一个位置 表长减1 核心语句 C 具体实现 templatedatatypeSeqList Delete inti intitem j if length 0 throw 表为空 无法删除元素 if ilength throw i不合法 item data i 1 获得要删除的元素值for j i j length j data j 1 data j 注意数组下标从0记length returnitem 5 按位查找实现 操作接口 templatedatatypeSeqList Get inti 0 i 2i 1 n 1Max 1 a1 ai 1 ai an 空闲 n 算法描述 templatedatatypeSeqList Get inti if ilength throw i不合法 elsereturndata i 1 时间复杂度 O 1 6 按值查找 操作接口 templateintSeqList Locate datatypeitem 5 35 a1 a2 a3 a4 01234 42 24 12 33 a5 例 在 35 33 12 24 42 中查找值为12的元素 返回在表中的序号 templateintSeqList Locate datatypeitem for inti 0 i length i if data i item returni 1 下标为i的元素等于item 返回其序号i 1return0 查找失败 算法描述 时间复杂度 平均查找的时间复杂度为O n 2 2 2 3顺序表的算法效率分析 插入 删除算法时间主要耗费在移动元素的操作T n O 移动元素次数 移动元素的次数取决于插入或删除元素的位置 讨论1 若在长度为n的线性表的第i位前插入一元素 则向后移动元素的次数f n 为 f n n i 1 时间效率分析 最好情况 i n 1 移动元素次数0次 时间复杂度为O 1 最坏情况 i 1 移动元素次数n次 时间复杂度为O n 平均情况 1 i n 1 时间复杂度为O n 讨论2 若在长度为n的线性表上删除第i位元素 向前移动元素的次数f n 为 f n n i 讨论3 顺序表的插入 删除操作算法空间复杂度S n O 1 最好情况 i n 移动元素次数0次 时间复杂度为O 1 最坏情况 i 1 移动元素次数n 1次 时间复杂度为O n 平均情况 1 i n 时间复杂度为O n 本节小结 线性表顺序存储结构特点 逻辑关系上相邻的两个元素在物理存储位置上也相邻 优点 可以随机存取表中任一元素 缺点 1 在插入 删除某一元素时 平均要移动一半元素 平均时间复杂度O n 表的容量难以确定 表的容量难以扩充 易造成存储空间的碎片 为克服这些缺点 我们引入另一种存储形式 链式存储 2 3线性表的链式存储和实现 2 3 1链表的存储表示2 3 2链表的操作实现2 3 3链表的算法效率分析 链表 线性表的链接存储结构 存储思想 用一组任意的存储单元存放线性表的元素 2 3 1链表的存储表示 存储特点 逻辑次序和物理次序不一定相同 2 元素之间的逻辑关系用指针表示 例 a1 a2 a3 a4 的存储示意图 1 链表的存储特点 a10200 a20325 a30300 a4 链表是由若干结点构成的 每个结点结构有两个部分组成 数据域 指针域 data 存储数据元素next 存储指向后继结点的地址 2 有关的术语 1 结点 数据元素的存储映像 由数据域和指针域两部分组成 2 链表 n个结点由指针链组成一个链表 它是线性表的链式存储映像 称为线性表的链式存储结构 3 单链表 双链表 多链表 循环链表 结点只有一个指针域的链表 称为单链表或线性链表 有两个指针域的链表 称为双链表 有多个指针域的链表 称为多链表 首尾相接的链表称为循环链表 头指针是指向链表中第一个结点 或为头结点或为首元结点 的指针 头结点是在链表的首元结点之前附设的一个结点 数据域内只放空表标志或表长等信息 首元结点是指链表中存储线性表第一个数据元素a1 4 头指针 头结点和首结点 上例链表的逻辑结构示意图有以下两种形式 a1 a2 a4 a3 H a1 a2 a4 a3 H 区别 无头结点 链式队列 链栈常用 有头结点 链表常用 答 讨论1 在链表中设置头结点有什么好处 讨论2 如何表示空表 头结点即在链表的首元结点之前附设的一个结点 该结点的数据域中不存储线性表的数据元素 其作用是为了对链表进行操作时 可以对空表 非空表的情况以及对首元结点进行统一处理 编程更方便 答 无头结点时 当头指针的值为空时表示空表 有头结点时 当头结点的指针域为空时表示空表 h NULL h next NULL templateclassLinkList 前视定义 便于使用友元templateclassNode friendclassLinkList 友元类private datatypedata Node next 此处也可以省略 3 单链表的存储结构定义 重点及难点 1 单链表的结点结构定义 如何申请一个结点 Nodehead head newNode templateclassLinkList templateclassNode friendclassLinkList private datatypedata Node next head data next head newNode head 如何引用数据元素 data 如何引用指针域 next 单链表的存储结构定义 类声明 templateclassLinkList public LinkList 建立只有头结点的空链表LinkList datatypea intn 建立有n个元素的单链表 LinkList 析构函数 释放整个链表空间intLength 求单链表的长度datatypeGet inti 取单链表中第i个结点的元素值intLocate datatypex 求单链表中值为x的元素序号voidInsert inti datatypex 在单链表中第i个位置插入元素值为x的结点datatypeDelete inti 在单链表中删除第i个结点voidPrintList 遍历单链表 按序号依次输出各元素private Node head 单链表的头指针 单链表的抽象数据类型描述参见书p65 2 3 2单链表的操作实现 1 单链表的建立和输出2 单链表的查找3 单链表的插入4 单链表的删除5 其它操作实现6 应用举例 1 单链表的建立和输出 1 带头结点单链表的初始化创建一个带头结点的空的单链表 操作接口 templateLinkList LinkList 构造函数基本步骤 申请头结点 并让头指针指向头结点 修改头结点 使其指针域为NULL 算法实现 templateLinkList LinkList head newNode head next NULL 空表 head 2 带头结点单链表的输出操作接口 templatevoidLinkList PrintList 基本步骤 从首结点开始 一个一个输出至尾结点 算法实现 templatevoidLinkList PrintList Node p p head next 指向着结点while p 不为空时 coutdatanext head a1 a2 an ai P NULL时结束 a1 a2 ai an 单链表的查找按位查找实现 操作接口 templatedatatypeLinkList Get inti 核心操作 关键操作 P指针后移 从首结点出发 通过 指针的反复后移而将整个单链表 审视 一遍的方法称为扫描 或遍历 思考 按值查找如何实现 略 head a1 a2 an ai 顺藤摸瓜 a1 a2 p next p 按位查找算法实现 templatedatatypeLinkList Get inti Node p intj 计数器p head next j 1 或p head j 0 while p 3 单链表插入 操作接口 templatevoidLinkList Insert inti datatypex 在第i个元素之前插入新元素x 如何实现结点ai 1 x和ai之间逻辑关系的变化 s newNode s data x Step1 s next p next Step2 p next s 插入步骤 即核心语句 思考 步骤1和2能互换么 不能互换 注意分析边界情况 表头 表尾 head a1 an ai 核心语句 Step1 s newNode s data x s next p next Step2 p next s 由于单链表带头结点 表头 表中 表尾三种情况的操作语句一致 算法 在带头结点的单链表L中第i个位置之前插入元素e 基本思想 1 新建插入结点 2 找到插入点 指针p将指向第i 1个结点 平均时间复杂度为O n 判i的合法性 i 1 i 链表表长加1 3 修改相应结点的指针域 实现插入 其时间复杂度为O 1 注 先修改新结点的指针域 再修改链表的指针域 templatevoidLinkList Insert inti datatypex Node p intj p head j 0 指针p初始化while p 找插入点 插入算法实现 if p throw i不合法 else Node s s newNode s data x s next p next p next s 基本语句 时间复杂度 单链表的删除 操作接口 templatedatatypeLinkList Delete inti 如何实现结点ai 1和ai之间逻辑关系的变化 head a1 ai 1 ai 1 删除步骤 即核心语句 q p next x q data p next q next deleteq 思考 省略deleteq 语句行不行 不行 核心语句 q p next x q data p next q next deleteq 注意分析边界情况 表头 表尾 head 算法 在带头结点的单链表L中删除第i个结点 并返回该结点的值 基本思想 1 找到删除点 指针p将指向第i 1个结点 平均查找时间复杂度为O n 判i的合法性 i 1 i 链表表长 指针p初始化 累加器j清零 2 修改相应结点的指针域 实现删除 注 先保护要删除的结点 将其值取出 再修改链表指针域 3 释放第i个结点的空间 templatedatatypeLinkList Delete inti Node p intj p head j 0 while p 找到第i 1个结点 链表删除算法实现 if p p next throw i不合法 else q p next x q data p next q next deleteq returnx 5 其它操作函数实现 带参数构造函数实现操作接口 templateLinkList LinkList datatypea intn 头插法 将待插入结点插在头结点的后面 核心算法描述 head newNode head next NULL 算法描述 s newNode s data a 0 s next head next head next s 插入第一个元素结点 head 算法描述 s newNode s data a 1 s next head next head next s 依次插入每一个结点 templateLinkList LinkList datatypea intn inti Node s head newNode head next NULL for i 0 i s data a i s next head next head next s 算法实现 2 尾插法 将待插入结点插在终端结点的后面 核心语句 head newNode rear head 核心算法描述 s newNode s data a 0 s next NULL rear next s rear rear next 插入第一个元素结点 核心算法描述 s newNode s data a 1 s next NULL rear next s rear rear next 依次插入每一个结点 35 templateLinkList LinkList datatypea intn Node rear s inti head newNode rear head for i 0 i s data a i s next NULL rear next s rear rear next 算法实现 单链表析构函数的实现 析构函数将单链表中所有结点的存储空间释放 操作接口 templateLinkList LinkList head a1 a2 an ai 算法描述 q p p p next Deleteq 注意 保证链表未处理的部分不断开 templateLinkList LinkList Node p q p head while p q p p p next deleteq 算法实现 单链表求表长函数的实现 操作接口 templateintLinkList Length 基本思想 边遍历边计数 算法实现 templateintLinkList Length Node p head next inti 0 while p p p next i returni 2 4顺序表和单链表的比较 存储分配方式比较 顺序表采用顺序存储结构 即用一段地址连续的存储单元依次存储线性表的数据元素 数据元素之间的逻辑关系通过存储位置来实现 单链表采用链式存储结构 即用一组任意的存储单元存放线性表的元素 用指针来反映数据元素之间的逻辑关系 时间性能比较 时间性能是指实现基于某种存储结构的基本操作 即算法 的时间复杂度 按位查找 顺序表的时间为 1 是随机存取 单链表的时间为 n 是顺序存取 插入和删除 顺序表平均需移动表长一半的元素 时间为 n 单链表不需要移动元素 在给出某个合适位置的指针后 插入和删除操作所需的时间仅为 1 空间性能比较 空间性能是指某种存储结构所占用的存储空间的大小 定义结点的存储密度 空间性能比较 结点的存储密度 顺序表中每个结点的存储密度为1 只存储数据元素 没有浪费空间 单链表的每个结点的存储密度 1 包括数据域和指针域 有指针的结构性开销 整体结构 顺序表需要预分配存储空间 如果预分配得过大 造成浪费 若估计得过小 又将发生上溢 单链表不需要预分配空间 只要有内存空间可以分配 单链表中的元素个数就没有限制 结论 若线性表需频繁查找却很少进行插入和删除操作 或其操作与位置密切相关时 宜采用顺序表作为存储结构 若线性表需频繁插入和删除时 则宜采用单链表做存储结构 当线性表中元素个数变化较大或者未知时 最好使用单链表实现 而如果用户事先知道线性表的大致长度 使用顺序表的空间效率会更高 总之 根据实际问题的具体需要 加以综合平衡 才能终选定比较适宜的实现方法 2 5线性表的其他存储及实现 特点 1 尾结点的指针域指向头结点 2 从任一结点出发均可找到表中其他结点 3 操作时仅循环条件与单链表不同 判表空 单链表用p NULL 不带头结点 或p next NULL 带头结点 循环链表用p head 不带头结点 或p next head 带头结点 从单链表中某结点p出发如何找到其前驱 讨论1 如 带头结点的空循环链表样式 注 将单链表的首尾相接 将终端结点的指针域由空指针改为指向头结点 构成单循环链表 简称循环链表 结点结构定义 未变templateclassXLinkList 前视定义 便于使用友元templateclassNode friendclassLinkList 友元类private datatypedata Node next head a1 ai 1 an ai 循环链表 插入 核心算法描述 s newNode s data x s next p next p next s templatevoidXLinkList Insert inti datatypex Node p intj p head j 0 while p next head if j i 1 throw i不合法 else Node s s newNode s data x s next p next p next s 循环链表 插入实现 与单链表的插入操作相比 差别是什么 循环条件 p NULL p headp next NULL p next head 注 templatevoidXLinkList PrintList Node p p head next while p head coutdatanext 循环链表 遍历算法实现 O n 开始结点 rear next next终端结点 rear 其它形式的循环链表如 带尾指针的循环链表 一个存储结构设计得是否合理 取决于基于该存储结构的运算是否方便 时间性能是否提高 如何求结点p的直接前驱 时间性能 如何快速求得结点p的后继 如何快速求得结点p的前驱 讨论2 p next 引入一个辅助指针变量q 从首结点开始遍历 至q next p找到直接前驱结点 双向链表 在单链表的每个结点中再设置一个指向其前驱结点的指针域 templateclassDLinkList templateclassNode friendclassDLinkList private typedata Node next prior 双向链表 启示 时空权衡 空间换取时间 结点结构定义 类的声明 常用双向循环链表 如空的双向循环链表为 双向链表的操作 插入实现 ai 1 ai 操作接口 templatevoidDLinkList Insert inti typex 注意指针修改的相对顺序 核心语句 DNode s s newDNode s data x s prior p s next p next p next prior s p next s 双向链表的操作 删除实现 操作接口 templatetypeDLinkList Delete inti ai 1 ai ai 结点q的指针是否需要修改 deleteq DNode q intx q p next x q data p next q next q next prior p deleteq 不需要 答 能 用数组来表示单链表 用数组元素的下标来模拟单链表的指针 称为静态链表 数据元素由数据域和指示域组成 注 数据域含义与前面相同 指示域相当于前面的指针域 静态链表的插入与删除操作与普通链表一样 不需要移动元素 只需修改指示器就可以了参考p79 讨论3 用一维向量也能实现链表结构吗 数据域 指示域 例如 线性表 张 王 李 赵