合取警院 第3章链表及其应用 HEFEI UNIVERSITY 回顾 顺序表的特点：逻辑关系上相邻的两个元素在物理存储位置上也 相邻： 优点：可以随机存取表中任一元素O(1；存储空间使用紧凑 缺点：在插入，删除某一元素时，需要移动大量元素O():预先 分配空间需按最大空间分配，利用不充分：表容量难以扩充。 讨论：在线性排列的一组数据元素中插入和删除数据元 素时可不可以不移动元素？ 答：可以！引入另一种数据结构一链表。 合肥学院计算机科学与技术系“数据结构与算法”课程建设组(200711一20)
第3章 链表及其应用 1 回顾： 顺序表的特点：逻辑关系上相邻的两个元素在物理存储位置上也 相邻； 优点：可以随机存取表中任一元素O(1)；存储空间使用紧凑 缺点：在插入，删除某一元素时，需要移动大量元素O(n);预先 分配空间需按最大空间分配，利用不充分;表容量难以扩充。 讨论：在线性排列的一组数据元素中插入和删除数据元 素时可不可以不移动元素？ 答：可以！引入另一种数据结构——链表
⑧合取学院 第3章链表及其应用 HEFEI UNIVERSITY 第3章 链表及其应用 m3.1链表的基本概念 3.2单链表的数据结构 3.3单链表的基本运算实现 3.4循环链表 3.5链表的应用 合肥学院计算机科学与技术系“数据结构与算法”课程建设组(20071山20)
第3章 链表及其应用 2 第3章 链表及其应用 ☞ 3.1 链表的基本概念 3.2 单链表的数据结构 3.3 单链表的基本运算实现 3.4 循环链表 3.5 链表的应用
⑧合取学院 第3章链表及其应用 HEFEI UNIVERSITY 3.1链表的基本概念 m3.1.1什么是链表 3.1.2链表的逻辑结构 3.1.3链表的存储结构 3.1.4静态链表和动态链表 3.1.5链表的基本运算 合肥学院计算机科学与技术系“数据结构与算法”课程建设组(200711一20)
第3章 链表及其应用 3 3.1 链表的基本概念 ☞ 3.1.1 什么是链表 3.1.2 链表的逻辑结构 3.1.3 链表的存储结构 3.1.4 静态链表和动态链表 3.1.5 链表的基本运算
合取学院 第3章链表及其应用 HEFEI UNIVERSITY 什么是链表 链表是满足下列条件的一种数据结构： ()是有限个具有相同数据类型的数据元素的集合， D={a:|i=1,2,,n,n20,a:为数 据元素 (2)数据元素之间的关系R={|a-1 a:∈D i=2,3,,n,n20}: (3)数据元素a1-1、a;(i=2,3,,n,n20) 在存储器中占用任意的、连续或不连续物理存储区 域。 合肥学院计算机科学与技术系“数据结构与算法”课程建设组(2007-1120)
第3章 链表及其应用 4 ☻ 什么是链表 ☞ 链表是满足下列条件的一种数据结构： ⑴ 是有限个具有相同数据类型的数据元素的集合， D = { ai | i=1，2，…，n，n≥0 ，ai为数 据元素 ⑵ 数据元素之间的关系R = {| ai-1, ai∈D i=2，3，…，n，n≥0}； ⑶ 数据元素ai-1、 ai（i=2，3，…，n，n≥0） 在存储器中占用任意的、连续或不连续物理存储区 域
⊙合雕学院 第3章链表及其应用 HEFEI UNIVERSITY 3.1链表的基本概念 3.1.1什么是链表 r3.1.2链表的逻辑结构 3.1.3链表的存储结构 3.1.4静态链表和动态链表 3.1.5链表的基本运算 合肥学院计算机科学与技术系“数据结构与算法”课程建设组(20071山20)
第3章 链表及其应用 5 3.1 链表的基本概念 3.1.1 什么是链表 ☞ 3.1.2 链表的逻辑结构 3.1.3 链表的存储结构 3.1.4 静态链表和动态链表 3.1.5 链表的基本运算
⑧合取学院 第3章链表及其应用 HEFEI UNIVERSITY ◆ 链表的逻辑结构 ▣同一链表中所有数据元素的数据类型必须相 同。 r 链表中相邻的元素a-1a间存在序偶关系 即对于非空的链表，a-1是a:的唯一直接前驱， a+1是a的唯一直接后继；而a无前驱，an无 后继 ▣链表属于线性逻辑结构。 合肥学院计算机科学与技术系“数据结构与算法”课程建设组(200711一20)
第3章 链表及其应用 6 ♣ 链表的逻辑结构 ☞ 同一链表中所有数据元素的数据类型必须相 同。 ☞ 链表中相邻的元素ai-1、ai间存在序偶关系， 即对于非空的链表，ai-1是ai的唯一直接前驱， ai＋1是ai的唯一直接后继；而a1无前驱，an无 后继 ☞ 链表属于线性逻辑结构
)合取学院 第3章链表及其应用 HEFEI UNIVERSITY 3.1链表的基本概念 3.1.1什么是链表 3.1.2链表的逻辑结构 r3.1.3链表的存储结构 3.1.4静态链表和动态链表 3.1.5链表的基本运算 合肥学院计算机科学与技术系“数据结构与算法”课程建设组(2007-1120)
第3章 链表及其应用 7 3.1 链表的基本概念 3.1.1 什么是链表 3.1.2 链表的逻辑结构 ☞ 3.1.3 链表的存储结构 3.1.4 静态链表和动态链表 3.1.5 链表的基本运算
⑧合取学院 第3章链表及其应用 HEFEI UNIVERSITY ·链表的存储结构 ▣用一组任意的存储单元来存放表中的元素， 这使得链表中数据元素的逻辑顺序与其物理存 储顺序不一定相同， 为确保表中数据元素间的线性逻辑关系，在 存储每一个数据元素的同时，存储其逻辑后继 的存储地址： 合肥学院计算机科学与技术系“数据结构与算法”课程建设组(20071山20)
第3章 链表及其应用 8 ♣ 链表的存储结构 ☞ 用一组任意的存储单元来存放表中的元素， 这使得链表中数据元素的逻辑顺序与其物理存 储顺序不一定相同； ☞ 为确保表中数据元素间的线性逻辑关系，在 存储每一个数据元素的同时，存储其逻辑后继 的存储地址；
⑧合取学院 第3章链表及其应用 HEFEI UNIVERSITY ·链表的存储结构 ra:的值与a:+1的存储地址共同组成了链表中 的一个结点： data next 其中：data域是数据域，用来存放数据元素a的值 next域是指针域，用来存放a的直接后继a:+的 存储地址 r链表正是通过每个结点的指针域将表中个数据元素 按其逻辑顺序链接在一起的。 合肥学院计算机科学与技术系“数据结构与算法”课程建设组(2007-1120)
第3章 链表及其应用 9 ♣ 链表的存储结构 …… ☞ ai的值与ai＋1的存储地址共同组成了链表中 的一个结点：data next 其中：data域是数据域，用来存放数据元素ai的值； next域是指针域，用来存放ai的直接后继ai＋1的 存储地址。 ☞ 链表正是通过每个结点的指针域将表中n个数据元素 按其逻辑顺序链接在一起的
合取警院 第3章链表及其应用 HEFEI UNIVERSITY 【例】设有一组线性排列的数据元素(zhao,qian,sun,li, zhou,wu,zheng,wang),其链接存储形式如图所示： 存储地址 数据域 指针域 100 wang N 160 i 310 170 zhao 320 : 200 wu 220 210 sun 160 220 zheng 100 310 zhou 200 320 qian 210 合肥学院计算机科学与技术系“数据结构与算法”课程建设组(20071120) 10
第3章 链表及其应用 10 【例】设有一组线性排列的数据元素（zhao, qian, sun, li, zhou, wu, zheng, wang），其链接存储形式如图所示： 存储地址 数据域 指针域 … … … … … … … … … … … … … … … zhao li zhou zheng qian 100 wang sun wu 160 170 200 210 220 310 320 320 210 160 310 200 220 100 ∧