Java版)数据结构与算法第2章.ppt

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