西南科技大学：《数据结构》课程教学资源（PPT课件讲稿）第四章 链式存储结构的表、堆栈和队列

链式存储结构的表、堆栈和队列 Ds-41链式存储结构 4.2单链表 计算机学 4.3单循环链表 4.4双向循环链表 院45链式堆栈 息■46链式队列 教研室 4.,7链式存储结构的特点 4.8应用问题的面向对象程序设计方法

链式存储结构的表、堆栈和队列 ◼ 4.1 链式存储结构 ◼ 4.2 单链表 ◼ 4.3 单循环链表 ◼ 4.4 双向循环链表 ◼ 4.5 链式堆栈 ◼ 4.6 链式队列 ◼ 4.7 链式存储结构的特点 ◼ 4.8 应用问题的面向对象程序设计方法 计 算 机 学 院 信 息 教 研 室 DS

4.1链式存储结构 DS 链式存储结构:初始时为空链,每当 有新的数据元素需要存储时,用户 机向系统动态申请所需的存储空间插 学入链中 申请: 数名字指针=new类型明(初始化值) 研释放: Delete名字指针 室

4.1链式存储结构 链式存储结构：初始时为空链，每当 有新的数据元素需要存储时，用户 向系统动态申请所需的存储空间插 入链中。 申请： 名字指针=new 类型明（初始化值） 释放： Delete 名字指针 计 算 机 学 院 信 息 教 研 室 DS

4.1链式存储结构 DS ◆特点:任意两个在逻辑上相邻的数据元 素在物理上不一定相邻。其逻辑顺序是 算 通过链中的指针来实现的。 学◆为了能正确表示结点间的逻辑关系,在 信示其后继结点的地址(或位置)信息, 教 这个信息称为指针( pointer)或链ink) 研 室

4.1链式存储结构 特点：任意两个在逻辑上相邻的数据元 素在物理上不一定相邻。其逻辑顺序是 通过链中的指针来实现的。 为了能正确表示结点间的逻辑关系，在 存储每个结点值的同时，还必须存储指 示其后继结点的地址（或位置）信息， 这个信息称为指针(pointer)或链(link)。 计 算 机 学 院 信 息 教 研 室 DS

4.1链式存储结构 DS 链式存储结构数据元素集合的方法是 计算机学院信 用结点(Node)构造链 data next 息其中:data域是数据域,用来存放结点的值。 next是指针城(亦称链域),用来存放结点 研的直接后继的地址(或位置

4.1链式存储结构 链式存储结构数据元素集合的方法是 计 算 用结点（Node）构造链。 机 学 院 信 息 教 研 室 DS data next 其中：data域是数据域，用来存放结点的值。 next是指针域（亦称链域），用来存放结点 的直接后继的地址（或位置）

4.1链式存储结构 DS ◆头结点是指头指针所指的不存放数据元 计素的结点。 算◆其中,带头结点的链式结构在表的存储 机学院 中更为常见。不带头结点的链式结构在 栈和队列的存储中更为常见 信◆空指针在算法描述中用NULL来表示,空 息指针是一个特殊的标识,用来表识链的 教研 结束 室

4.1链式存储结构 头结点是指头指针所指的不存放数据元 素的结点。 其中，带头结点的链式结构在表的存储 中更为常见。不带头结点的链式结构在 栈和队列的存储中更为常见。 空指针在算法描述中用NULL来表示，空 指针是一个特殊的标识，用来表识链的 结束。 计 算 机 学 院 信 息 教 研 室 DS

42单链表( Single Linked) DS链表正是通过每个结点的链域将线性表的n个结 点按其逻辑次序链接在一起的。由于上述链表 算的每一个结点只有一个链城,故将这种链表称 机为单链表( single Linked)。 院例1、线性表:(bat,cat,eat,fat,hat,jat, 信at,mat) 自 教head 研室 bat cat eat …恤ma

4.2 单链表（Single Linked) 链表正是通过每个结点的链域将线性表的n个结 点按其逻辑次序链接在一起的。由于上述链表 的每一个结点只有一个链域，故将这种链表称 为单链表（Single Linked)。 例1、线性表:(bat，cat，eat，fat，hat，jat， lat，mat) 计 算 机 学 院 信 息 教 研 室 DS bat cat eat … mat ^ head

单链表( Singly Linked List, ◆特点 每个元素(表项)由结点(Wde)构成。 计 算 data next 机◆线性结构 学 院head 信 a0+al an∧ 息■结点可以不连续存储 教 研 表可扩充 室

单链表 (Singly Linked List) 特点 ◼ 每个元素(表项)由结点(Node)构成。 线性结构 ◼ 结点可以不连续存储 ◼ 表可扩充 计 算 机 学 院 信 息 教 研 室 a0 a1 … an ^ head data next

单链表的存储映像 计算机学院信息教研室 (a)可用存储空间 ree 0 绕2 3 first free b)经过一段运行后的单链表结构ast

单链表的存储映像 计 算 机 学 院 信 息 教 研 室

单链表的类模板 DS ◆类模板将类的数据成员和成员函 计算机学院信息教研 数设计得更完整、更灵活。 ◆类模板更易于复用 ◆在单链表的类模板定义中,增加 了表头结点。 室

单链表的类模板 计 算 机 学 院 信 息 教 研 室 DS 类模板将类的数据成员和成员函 数设计得更完整、更灵活。 类模板更易于复用。 在单链表的类模板定义中，增加 了表头结点

head d+anal+.an DS 由图分析:单链表的基本组成部分是结点 个单链表可用该单链表的头指针来表 计算机学院信 示。(用类的组合来实现) ◆先设计结点类 data next ◆定义单链表类 自 教head 0 l…一m 研 室

由图分析：单链表的基本组成部分是结点， 一个单链表可用该单链表的头指针来表 示。（用类的组合来实现） 先设计结点类 定义单链表类 计 算 机 学 院 信 息 教 研 室 DS a0 a1 … an ^ head data next a0 a1 … an ^ head