23线性表链表.ppt

北京化工大学信息学院 数据结构 数据结构 北京化工大学 信息科学与技术学院 刘勇 qq:417041890 lyong@mail.buct.edu.cn 第二章 线性表 线性表 顺序表 链表 顺序表与链表的比较 链表（Linked List） 链接表是线性表的链接存储表示 单链表 静态链表 循环链表 双向链表 单链表 (Singly Linked List) 特点 每个元素(表项)由结点(Node)构成。 线性结构 结点可以连续，可以不连续存储 结点的逻辑顺序与物理顺序可以不一致 表可扩充 单链表的定义 单链表中的插入与删除 插入 第一种情况：在第一个结点前插入 newnode-next = first; first = newnode; 第二种情况：在链表中间插入 newnode-next = p-next; p-next = newnode； 第三种情况：在链表末尾插入 newnode-next = p-next; p-next = newnode； 删除 第一种情况: 删除表中第一个元素 第二种情况: 删除表中或表尾元素 带表头结点的单链表 表头结点位于表的最前端，本身不带数据，仅标志表头。 设置表头结点的目的是 统一空表与非空表的操作 简化链表操作的实现。 前插法建立单链表 从一个空表开始，重复读入数据： 生成新结点 将读入数据存放到新结点的数据域中 将该新结点插入到链表的前端 直到读入结束符为止。 后插法建立单链表 每次将新结点加在链表的表尾； 设置一个尾指针 r，总是指向表中最后一个结点，新结点插在它的后面； 尾指针 r 初始时置为指向表头结点地址。 单链表清空 在单链表中删除一个结点 在单链表中删除一个结点 循环链表 (Circular List) 循环链表是单链表的变形。 循环链表最后一个结点的 link 指针不 为NULL，而是指向了表的前端。 为简化操作，在循环链表中往往加入表头结点。 循环链表的特点是：只要知道表中某一结点的地址，就可搜寻到所有其他结点的地址。 循环链表的示例 带表头结点的循环链表 双向链表 (Doubly Linked List) 双向链表是指在前驱和后继方向都能游历(遍历)的线性链表。 双向链表每个结点结构： 双向链表通常采用带表头结点的循环链表形式。 结点指向p == p-prior-next == p-next-prior 顺序表与链表的比较 基于空间的比较 存储分配的方式 顺序表的存储空间是静态分配的 链表的存储空间是动态分配的 存储密度 = 结点数据本身所占的存储量/结点结构所占的存储总量 顺序表的存储密度 = 1 链表的存储密度 1 顺序表与链表的比较 基于时间的比较 存取方式 顺序表可以随机存取，也可以顺序存取 链表是顺序存取的 插入/删除时移动元素个数 顺序表平均需要移动近一半元素 链表不需要移动元素，只需要修改指针 若插入/删除仅发生在表的两端，宜采用带尾指针的循环链表 习题 习题答案 a0 a1 a2 an-1 first an-1 first a1 a0 first (空表) (非空表) 查找成功 查找不成功 循环链表的查找 first first 31 31 48 48 15 15 57 57 查找15 ? ? ? 查找25 ? ? ? ? p p p p p p p p 前驱方向 ? ? 后继方向 prior data next 非空表 空表 p-prior p-next p prior next first first 查找成功 查找不成功 双向循环链表的查找 first first 31 31 48 48 15 15 57 57 查找15 ? ? ? 查找25 ? ? ? ? 双向循环链表的插入 (非空表) first first 31 48 15 在结点 *p 后插入25 p p 31 48 25 15 q-prior = p; q-next = p-next; p-next = q; q-next-prior = q; q 双向循环链表的插入 (空表) first 在结点 *p 后插入25 p q 25 q-prior = p; q-next = p-next; ( = first ) p-next = q; q-next-prior = q; ( first-prior = q ) first p 删除48 双向循环链表的删除 first first 非空表 31 48 15 p 31 15