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

2 3线性表的链接存储结构及实现 静态存储分配 在编译时为变量分配内存 并且一经分配就始终占有固定的存储单元 直到该变量退出其作用域 动态存储分配 在程序的运行期间根据实际需要随时申请内存 并在不需要时释放 C 中动态存储分配是通过指针实现的 链式存储分配的特点 根据线性表的长度动态的申请存储空间 以解决顺序存储中存在的存储空间难以确定的问题 链式存储结构的实现单链表双向链表循环链表等 单链表 线性表的链接存储结构之一 存储思想 用一组任意的存储单元存放线性表的元素 存储特点 逻辑次序和物理次序不一定相同 2 元素之间的逻辑关系用指针表示 例 a1 a2 a3 a4 的存储示意图 单链表 a10200 a20325 a30300 a4 单链表 单链表是由若干结点构成的 单链表的结点只有一个指针域 data 存储数据元素next 存储后继结点的地址 数据域 指针域 单链表 templatestructNode Tdata Node next 此处也可以省略 如何申请一个结点 单链表 p newNode templatestructNode Tdata Node next 单链表 p newNode 如何引用数据元素 data 如何引用指针域 next p next 区分 指针变量 指针 指针所指结点 结点的值P60 单链表 单链表 重点在数据元素之间的逻辑关系的表示 所以 将实际存储地址抽象 什么是存储结构 单链表 头指针 指向第一个结点的地址 尾标志 终端结点的指针域为空 单链表 空表和非空表不统一 缺点 如何将空表与非空表统一 单链表 头结点 在单链表的第一个元素结点之前附设一个类型相同的结点 以便空表和非空表处理统一 非空表 单链表 templateclassLinkList public LinkList LinkList Ta intn LinkList intLength TGet inti intLocate Tx voidInsert inti Tx TDelete inti voidPrintList private Node first 单链表的头指针 可以省略 单链表类的声明 单链表的实现 按位查找 操作接口TGet inti 查找第i个元素并返回其值 核心操作 关键操作 工作指针后移 从头结点 或开始结点 出发 通过工作指针的反复后移而将整个单链表 审视 一遍的方法称为扫描 或遍历 first a1 a2 an ai 单链表的实现 按位查找 算法描述 伪代码 单链表的实现 按位查找 templateTLinkList Get inti p first next j 1 while p 算法描述 C 描述 18 复杂性分析 templateTLinkList Get inti Node p intj p first next j 1 或p first j 0 while p 查找算法的基本语句是工作指针p后移 该语句执行的次数与被查结点在表中的位置有关 在查找成功的情况下 若查找位置为i 1 i n 则需要执行i 1次 等概率情况下 平均时间性能为O n 单链表是顺序存取结构 19 总结单链表算法的设计模式 1 设工作指针并初始化在单链表中 一般要从头指针出发扫描单链表 由于头指针具有标识单链表的作用 因此 一般不能修改头指针 除非要修改表头 而是设工作指针 如果将工作指针初始化在头结点处 则用p first实现 如果将工作指针p初始化在开始结点处 则用p first next实现 20 总结单链表算法的设计模式 2 通过工作指针的反复后移将整个单链表扫描一遍在单链表类中没有定义表长 因此不能用表长来控制循环 而要用工作指针p来控制 其一般形式为While p NULL p p next 单链表算法的核心操作是 工作指针后移 扫描是单链表的一种常用技术 21 单链表的实现 插入 操作接口voidInsert inti Tx 将值为x的新结点插入到单链表的第i个位置 即将x插入到ai 1和ai之间 如何实现结点ai 1 x和ai之间逻辑关系的变化 算法描述 s newNode s data x s next p next p next s 22 单链表的实现 插入 注意分析边界情况 表头 表尾 first a1 an ai 算法描述 s newNode s data x s next p next p next s 由于单链表带头结点 表头 表中 表尾三种情况的操作语句一致 23 单链表的实现 插入 算法描述 伪代码 1 工作指针p初始化 累加器j初始化 2 查找第i 1个结点并使工作指针p指向该结点 3 若查找不成功 说明插入位置不合理 抛出插入位置异常 否则 3 1生成一个元素值为x的新结点s 3 2将新结点s插入到结点p之后 24 单链表的实现 插入 templatevoidLinkList Insert inti Tx p first j 0 while p 算法描述 C 描述 if p throw 位置 else s newNode s data x s next p next p next s 基本语句 时间复杂度 算法中让p指向第i个结点可以吗 25 单链表的实现 插入 templatevoidLinkList Insert inti Tx if i 1 处理在表头插入的特殊情况 s newNode s data x s next first firs s 不带头结点单链表的插入算法 else 与带头结点的单链表插入操作相同 26 单链表的实现 删除 操作接口TDelete inti 将单链表的第i个结点删去并返回被删元素值 如何实现结点ai 1和ai之间逻辑关系的变化 算法描述 q p next x q data p next q next deleteq 27 单链表的实现 删除 算法描述 q p next x q data p next q next deleteq 注意分析边界情况 表头 表尾 表尾的特殊情况 虽然被删结点不存在 但其前驱结点却存在 p next NULL 28 单链表的实现 删除 算法描述 伪代码 1 工作指针p初始化 累加器j清零 2 查找第i 1个结点并使工作指针p指向该结点 3 若p不存在或p不存在后继结点 则抛出位置异常 否则 3 1暂存被删结点和被删元素值 3 2摘链 将结点p的后继结点从链表上摘下 3 3释放被删结点 3 4返回被删元素值 29 单链表的实现 删除 templateTLinkList Delete inti p first j 0 while p 算法描述 C 描述 if p p next throw 位置 else q p next x q data p next q next deleteq returnx 基本语句 时间复杂度 30 小结 在单链表上实现插入和删除操作 无须移动元素 在将工作指针指向合适的位置后 仅需要修改结点之间链接关系的指针 31 单链表的实现 构造函数 操作接口LinkList Ta intn 生成一个具有n个结点的单链表 其数据元素为数组a n 的各数组元素 头插法 将待插入结点插在头结点的后面 算法描述 first newNode first next NULL 32 单链表的实现 构造函数 头插法 将待插入结点插在头结点的后面 算法描述 s newNode s data a 0 s next first next first next s 插入第一个元素结点 first 操作接口LinkList Ta intn 生成一个具有n个结点的单链表 其数据元素为数组a n 的各数组元素 33 单链表的实现 构造函数 头插法 将待插入结点插在头结点的后面 操作接口LinkList Ta intn 生成一个具有n个结点的单链表 其数据元素为数组a n 的各数组元素 算法描述 s newNode s data a 1 s next first next first next s 依次插入每一个结点 34 单链表的实现 构造函数 templateLinkList LinkList Ta intn first newNode first next NULL 初始化一个空链表for i 0 i s data a i 建立一个结点s next first next first next s 插入到头结点之后 算法描述 35 单链表的实现 构造函数 尾插法 将待插入结点插在终端结点的后面 算法描述 first newNode rear first 操作接口LinkList Ta intn 生成一个具有n个结点的单链表 其数据元素为数组a n 的各数组元素 36 单链表的实现 构造函数 尾插法 将待插入结点插在终端结点的后面 操作接口LinkList Ta intn 生成一个具有n个结点的单链表 其数据元素为数组a n 的各数组元素 算法描述 s newNode s data a 0 rear next s rear s 插入第一个元素结点 37 单链表的实现 构造函数 尾插法 将待插入结点插在终端结点的后面 操作接口LinkList Ta intn 生成一个具有n个结点的单链表 其数据元素为数组a n 的各数组元素 算法描述 s newNode s data a 1 rear next s rear s 依次插入每一个结点 35 38 单链表的实现 构造函数 尾插法 将待插入结点插在终端结点的后面 操作接口LinkList Ta intn 生成一个具有n个结点的单链表 其数据元素为数组a n 的各数组元素 算法描述 rear next NULL 最后一个结点插入后 39 单链表的实现 构造函数 算法描述 templateLinkList LinkList Ta intn first newNode rear first for i 0 i s data a i rear next s rear s rear next NULL 40 单链表的实现 析构函数 析构函数将单链表中所有结点的存储空间释放 操作接口 LinkList first a1 a2 an ai 算法描述 q p p p next Deleteq 注意 保证链表未处理的部分不断开 41 单链表的实现 析构函数 算法描述 1 templateLinkList LinkList p first while p 释放单链表的每一个结点的存储空间 q p 暂存被释放结点p p next 使单链表不断开deleteq 42 单链表的实现 析构函数 算法描述 2 templateLinkList LinkList while first p first q first next deleteq first q 思考 不带头结点的单链表的析构