2.3 线性表的链式存储结构
• 2.3.1 单向链表
– 对于链式分配线性表，整个链表的存取必须是 从头指针开始，头指针指示链表中第一个结点 的存储位置。同时由于最后一个数据元素，没 有直接后继，则线性链表中最后一个结点的指 针为“空”（null）。 – 在使用单链表结点时，必须完成三步：
• 首先创建一个新结点； • 为该结点赋一个新值；新结点的next域赋值个当前 元素； • 当前结点的前驱的next域要指向新插入的结点。
2.1 线性表类型的定义
• 线性表的离散定义是：B=<A，R>，其中A包含n个结点 （a1，a2……an）， R只包含一个关系。 R={（ai-1，ai） | I=1，2，……n}，线性表中包含的数据元素个数为线性 表的长度。 • 一个数据元素通常包含多个数据项，此时每个数据元素 称为记录，含有大量的记录的线性表称为文件。 • 在稍微复杂的线性表中，一个数据元素可以由若干个数 据项组成。 • 线性表是一个比较灵活的数据结构，它的长度根据需要 增长或缩短，也可以对线性表的数据元素进行不同的操 作（如访问数据元素、插入、删除数据元素等）。
第2章 线性表
2.1 线性表类型的定义 2.2 线性表的顺序表示和实现 2.3 线性表的链式存储结构 2.3.1 单向链表 2.3.2 单链表的基本运算 2.3.3 循环链表 2.3.4 双链表 2.4 链表应用举例 2.5 顺序表和链表的比较
2.1 线性表类型的定义
• 线性表是n个数据元素的有限序列。其一般描述 为： • A=（a1，a2，……an） • 其中A称为线性表的名称， 每个ai（n≥i≥1）称为 线性表的数据元素，具体n的值含义则称为线性 表中包含有数据元素的个数，也称为线性表的长 度；当n的值等于0时，表示该线性表是空表。每 个数据元素的含义在不同情况下各不相同，它们 可能是一个字母、一个数字、也可以是一条记录 等。一般情况下，在线性表中每个ai的描述的是 一组相同属性的数据。
2.3 线性表的链式存储结构
• 2.3.3 循环链表
– 循环线性链表中已知链表中任何结点，可以找到链表中的所有结 点，我们一般还是习惯把头结点作为已知条件，但是如果已知条 件是头结点，将在以下的插入或删除结点时造成不方便： – 删除末尾结点 – 第一个结点前插入新结点 – 在第一种情况下，虽然能够完成删除，但是，需要我们从头结点 开始逐个查找结点直到找到最后一个结点的直接前驱结点，然后 才能够删除，整个算法的时间复杂度是O（n）。 – 在第二种情况下，虽然能够完成插入，但是，需要我们从头结点 开始逐个查找结点直到找到最后一个结点，然后才能够插入，因 为我们需要修改最后一个结点的指针域，整个算法的时间复杂度 是O（n）。•Βιβλιοθήκη 2.3 线性表的链式存储结构
• • 2.3.2 单链表的基本运算
头插入法
– – 如果我们在链表的开始结点之前附加一个结点，并 称它为头结点，那么会带来以下两个优点： 第一，由于开始结点的位置被存放在头结点的指针 域中，所以在链表的第一个位置上的操作就和在表 的其他位置上操作一致，无须进行特殊处理； 第二，无论链表是否为空，其头指针是指向头结点 的非空指针（空表中头结点的指针域空），因此空 表和非空表的处理也就统一了。
2.3 线性表的链式存储结构
• 2.3.1 单向链表
– 任意存储单元存储线性表的数据元素，对于链式存储线 性表时，其特点形式如图所示：
DATA
NEXT
•其中data 是数据域，存放数据元素的值；next是指针 域，存放相邻的下一个结点的地址，单向链表是指结 点中的指针域只有一个的沿着同一个方向表示的链式 存储结构。 •因为结点是一个独立的对象，所以能够实现独立的结 点类。
2.2 线性表的顺序表示和实现
• 线性表的存储结构分为顺序存储和非顺序存储。 其中顺序存储也称为向量存储或一维数组存储。 • （1）顺序表
– 线性表的顺序存储，也称为向量存储，又可以说是一 维数组存储。线性表中结点存放的物理顺序与逻辑顺 序完全一致，它叫向量存储（一般指一维数组存储）， 与此同时对应A=（a1，a2，．．．an ）线性表而言。 – 实际上，数据的存储逻辑位置由数组的下标决定。所 以相邻的元素之间地址的计算公式为（假设每个数据 元素占有c个存储单元）： – LOC（ai+1）=LOC（ai）+ c
2.3 线性表的链式存储结构
• 在单链表中，因为指针是单一方向，结点 的查找只能从前向后查找，不能反向查找， 所以在插入、删除结点时，特别是在某个 结点之前插入，或者删除某个结点时，需 要利用结点的前趋结点的指针，所以在查 找结点时，需要保留结点的直接前趋结点 位置。也因为在单链表中，结点的查找只 能从前向后查找，不能反向查找，所以在 单向链表中，头结点的非常重要，不能丢 失。
2.3 线性表的链式存储结构
• 2.3.3 循环链表
– 以上的两种情况造成无谓的时间开销，为解决这个问 题，我们通常在循环链表以末尾结点指针为已知条件， 这样以上的两种情况，都可以直接完成，因为已知末 尾结点可以直接找到头结点，此时的时间复杂度为O （1），这样在不增加任何开销的情况下，减少了时 间的开销。 – 空的循环线性链表根据定义可以与单向链表相同，也 可以不相同。判断循环链表的末尾结点条件也就不同 于单向链表，不同之处在于是单向链表是判别最后结 点的指针域是否为空，而循环线性链表末尾结点的判 定条件是其指针域的值指向头结点。
2.2 线性表的顺序表示和实现
• （1）顺序表
– 顺序分配的线性表的可以直接使用一维数组描述为： – type arraylist[]；//type的类型根据实际需要确定// – 通常用在数组的元素个数不是很多且可以对数组元素“枚举”的 情况下。也可以使用符合类型数组的动态进行动态定义。 – type arrayname[]； – 该代码只是对应用数组的声明，还没有对该数组分配空间，因此 不能访问数组。只有对数组进行初始化并申请内存资源后，才能 够对数组中元素进行使用和访问。 – arrayname= new type[arraysize]； – 其作用是给名称为arrayname的数组分配arraysize个类型为type 大小的空间；其中arraysize表示数组的长度，它可以是整型的常 量和变量；如果arraysize是常量，则分配固定大小的空间，如果 是变量，则表示根据参数动态分配数组的空间。
–
2.3 线性表的链式存储结构
• ② 查找运算 • 按序号查找： 按序号查找：
– 在链表中，即使知道被访问结点的序号i，也不能像顺 序表中那样直接按序号i访问结点，而只能从链表的头 指针出发，顺着链域next逐个结点往下搜索，直至搜 索到第i个结点为止（一般采用计数器的方式）。链表 不是随机存取结构，只能顺序存取。 – 查找之前首先要做到从头（head）开始，然后再逐个 向后查找，查找过程中，每向后移动依次，计数器增 加1，直到找到第i个结点（查找成功）或找完整个链 表，没有第i个结点（查找失败）。
2.2 线性表的顺序表示和实现
• （2）顺序表基本运算的实现 • 线性表的顺序存储的结构，容易实现线性表的某 些操作，如随机存取第i个数据元素等，但是在插 入或删除数据元素时则是比较烦琐，所以顺序存 储结构比较适合存取数据元素。应该注意java的 数组下标从0开始。下面考虑线性表顺序存储的 插入、删除和排序的实现方法。 • 顺序表的“求表长”和取第i个数据元素的时间复 杂度均为O（1），因为可以直接求出线性表的 长度，顺序存储下可可以实现随机存取，可以直 接取得数据元素，而不需要移动元素。
2.3 线性表的链式存储结构
• ③求链表长度
– 求链表长度基本同按序号查找，从头结点开始顺着链 域扫描，用指针curr指向当前扫描到的结点（原因是 头结点指针不能变），用len作计数器，累计当前扫描 的结点数，直至curr=null，返回长度len就可以了。
• ④ 删除结点
– 删除结点是将表中的某个结点从表中删除，实际上还 是利用查找算法，找到满足条件的将要删除的结点后， 注意删除过程中，使用的指针是被删除结点的直接前 驱结点的指针，直接删除即可。
2.3 线性表的链式存储结构
• 2.3.3 循环链表
– 循环链表又称为循环线性链表，其存储结构基本同单向链表，是 在单向链表的基础上加以改进形成的，它可以解决单向链表中单 方向查找的缺点。因为单向链表只能沿着一个方向，不能反向查 找，并且最后一个结点的指针域的值是null，为解决单向链表的 缺点，可以利用末尾结点的空指针完成前向查找。将单链表的末 尾结点的指针域的null变为指向第一个结点，逻辑上形成一个环 型，该存储结构称之为单向循环链表。 – 相对单链表而言，有以下的优点： – 在不增加任何空间的情况下，能够已知任意结点的地址，可以找 到链表中的所有结点（环向查找）。 – 当然在查找某个结点的前驱结点时，需要增加时间开销完成，查 找的时间复杂度是O（n）。
2.2 线性表的顺序表示和实现
• （1）顺序表
– 对线性表的所有数据元素，假设已知第一个数据元素 a1的地址为d1，每个结点占有c个存储单元， 则第i个 数据元素ai的地址为： – di=d1+（i-1）*c – 线性表的第一个数据元素的位置通常称做起始位置或 基地址。 – 线性表的这种机内表示称做线性表的顺序存储结构或 顺序映象（Sequential mapping），使用这种存储结 构存储的线性表又称做顺序表。其特点是，表中相邻 的元素之间具有相邻的存储位置。 – 在使用一维数组时，数组的下标起始位置根据给定的 问题确定，或者根据实际的高级语言的规定确定。
2.3 线性表的链式存储结构
• 线性表的顺序存储结构的特点是逻辑关系上相邻 的两个元素在物理位置上也相邻，因此随机存取 元素时比较简单，但是这个特点也使得在插入和 删除元素时，造成大量的数据元素移动，同时如 果使用静态分配存储单元，还要预先占用连续的 存储空间，可能造成空间的浪费或空间的溢出。 • 如果采用链式存储，就不要求逻辑上相邻的数据 元素在物理位置上也相邻，因此它没有顺序存储 结构所具有的弱点，但同时也失去了可随机存取 的优点。