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