数据结构与算法分析 第2章.ppt

《数据结构与算法分析 第2章.ppt》由会员分享，可在线阅读，更多相关《数据结构与算法分析 第2章.ppt（32页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第2 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 2.1 线性表类型的定义线性表类型的定义 线性表是n个数据元素的有限序列。其一般描述为：A=（a1，a2，an）其中A称为线性表的名称，每个ai（ni1）称为线性表的数据元素，具体n的值含义则称为线性表中包含有数据元素的个数，也称为线性表的长度；当n的值等于0时，表示该线性表是空表。每个数据元

2、素的含义在不同情况下各不相同，它们可能是一个字母、一个数字、也可以是一条记录等。一般情况下，在线性表中每个ai的描述的是一组相同属性的数据。2.1 2.1 线性表类型的定义线性表类型的定义线性表的离散定义是：B=，其中A包含n个结点（a1，a2an），R只包含一个关系。R=（ai-1，ai）|I=1，2，n，线性表中包含的数据元素个数为线性表的长度。一个数据元素通常包含多个数据项，此时每个数据元素称为记录，含有大量的记录的线性表称为文件。在稍微复杂的线性表中，一个数据元素可以由若干个数据项组成。线性表是一个比较灵活的数据结构，它的长度根据需要增长或缩短，也可以对线性表的数据元素进行不同的操作（

3、如访问数据元素、插入、删除数据元素等）。2.1 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 2.2 线性表的顺序表示和实现线性表的顺序表示和实现 线性表的存储结构分为顺序存储和非顺序存储。其中顺序存储也称为向量存储或一维数组存储。（1）顺序表 线性表的顺序存储，也称为向量存储，又可以说是一维数组存储。线性表中结点存放的物理顺序与逻辑顺序完全一

4、致，它叫向量存储（一般指一维数组存储），与此同时对应A=（a1，a2，an）线性表而言。实际上，数据的存储逻辑位置由数组的下标决定。所以相邻的元素之间地址的计算公式为（假设每个数据元素占有c个存储单元）：LOC（ai+1）=LOC（ai）+c2.2 2.2 线性表的顺序表示和实现线性表的顺序表示和实现（1）顺序表 对线性表的所有数据元素，假设已知第一个数据元素a1的地址为d1，每个结点占有c个存储单元，则第i个数据元素ai的地址为：di=d1+（i-1）*c线性表的第一个数据元素的位置通常称做起始位置或基地址。线性表的这种机内表示称做线性表的顺序存储结构或顺序映象（Sequential map

5、ping），使用这种存储结构存储的线性表又称做顺序表。其特点是，表中相邻的元素之间具有相邻的存储位置。在使用一维数组时，数组的下标起始位置根据给定的问题确定，或者根据实际的高级语言的规定确定。2.2 2.2 线性表的顺序表示和实现线性表的顺序表示和实现（1）顺序表 顺序分配的线性表的可以直接使用一维数组描述为：type arraylist；/type的类型根据实际需要确定/通常用在数组的元素个数不是很多且可以对数组元素“枚举”的情况下。也可以使用符合类型数组的动态进行动态定义。type arrayname；该代码只是对应用数组的声明，还没有对该数组分配空间，因此不能访问数组。只有对数组进行初始

6、化并申请内存资源后，才能够对数组中元素进行使用和访问。arrayname=new typearraysize；其作用是给名称为arrayname的数组分配arraysize个类型为type大小的空间；其中arraysize表示数组的长度，它可以是整型的常量和变量；如果arraysize是常量，则分配固定大小的空间，如果是变量，则表示根据参数动态分配数组的空间。2.2 2.2 线性表的顺序表示和实现线性表的顺序表示和实现（2）顺序表基本运算的实现 线性表的顺序存储的结构，容易实现线性表的某些操作，如随机存取第i个数据元素等，但是在插入或删除数据元素时则是比较烦琐，所以顺序存储结构比较适合存取数据

7、元素。应该注意java的数组下标从0开始。下面考虑线性表顺序存储的插入、删除和排序的实现方法。顺序表的“求表长”和取第i个数据元素的时间复杂度均为O（1），因为可以直接求出线性表的长度，顺序存储下可可以实现随机存取，可以直接取得数据元素，而不需要移动元素。2.3 2.3 线性表的链式存储结构线性表的链式存储结构 线性表的顺序存储结构的特点是逻辑关系上相邻的两个元素在物理位置上也相邻，因此随机存取元素时比较简单，但是这个特点也使得在插入和删除元素时，造成大量的数据元素移动，同时如果使用静态分配存储单元，还要预先占用连续的存储空间，可能造成空间的浪费或空间的溢出。如果采用链式存储，就不要求逻辑上相

8、邻的数据元素在物理位置上也相邻，因此它没有顺序存储结构所具有的弱点，但同时也失去了可随机存取的优点。2.3 2.3 线性表的链式存储结构线性表的链式存储结构2.3.1 单向链表任意存储单元存储线性表的数据元素，对于链式存储线性表时，其特点形式如图所示：DATANEXT其中data 是数据域，存放数据元素的值；next是指针域，存放相邻的下一个结点的地址，单向链表是指结点中的指针域只有一个的沿着同一个方向表示的链式存储结构。因为结点是一个独立的对象，所以能够实现独立的结点类。2.3 2.3 线性表的链式存储结构线性表的链式存储结构2.3.1 单向链表对于链式分配线性表，整个链表的存取必须是从头指

9、针开始，头指针指示链表中第一个结点的存储位置。同时由于最后一个数据元素，没有直接后继，则线性链表中最后一个结点的指针为“空”（null）。在使用单链表结点时，必须完成三步：首先创建一个新结点；为该结点赋一个新值；新结点的next域赋值个当前元素；当前结点的前驱的next域要指向新插入的结点。2.3 2.3 线性表的链式存储结构线性表的链式存储结构2.3.2 单链表的基本运算单链表的基本运算 建立链表建立链表 因为单向链表的长度不固定，所以应采用动态建立单向链表的方法。动态地建立单向链表的常用方法有如下两种：尾插入法尾插入法该方法是将新结点插到当前链表的表尾上，为此必须增加一个尾指针tail的开

10、销，使其始终指向当前链表的尾结点；或者增加一个循环用来查找链表的末尾结点，然后将新结点插入到链表的末尾。此方法的优点是，在固定head头指针后，该指针就不能再变了。不会因为不断修改头指针，造成头指针的丢失。实际上动态建立链表的过程，就是不断插入新结点的过程；2.3 2.3 线性表的链式存储结构线性表的链式存储结构2.3.2 单链表的基本运算单链表的基本运算头插入法头插入法如果我们在链表的开始结点之前附加一个结点，并称它为头结点，那么会带来以下两个优点：第一，由于开始结点的位置被存放在头结点的指针域中，所以在链表的第一个位置上的操作就和在表的其他位置上操作一致，无须进行特殊处理；第二，无论链表是

11、否为空，其头指针是指向头结点的非空指针（空表中头结点的指针域空），因此空表和非空表的处理也就统一了。2.3 2.3 线性表的链式存储结构线性表的链式存储结构 查找运算查找运算按序号查找：按序号查找：在链表中，即使知道被访问结点的序号i，也不能像顺序表中那样直接按序号i访问结点，而只能从链表的头指针出发，顺着链域next逐个结点往下搜索，直至搜索到第i个结点为止（一般采用计数器的方式）。链表不是随机存取结构，只能顺序存取。查找之前首先要做到从头（head）开始，然后再逐个向后查找，查找过程中，每向后移动依次，计数器增加1，直到找到第i个结点（查找成功）或找完整个链表，没有第i个结点（查找失败）。

12、2.3 2.3 线性表的链式存储结构线性表的链式存储结构 查找运算查找运算按数值查找按数值查找 查找结点有时可以按数值查找，按值查找是在链表中，查找是否有结点值等于给定值key的结点，若有的话，则返回首次找到的其值为key的结点的存储位置；否则返回null。查找过程从开始结点出发，顺着链域逐个将结点的值和给定值key作比较，有两种情况，curr.val=key（查找成功）；curr=null也没有出现curr.val=key的条件（查找失败）。2.3 2.3 线性表的链式存储结构线性表的链式存储结构求链表长度求链表长度求链表长度基本同按序号查找，从头结点开始顺着链域扫描，用指针curr指向当前

13、扫描到的结点（原因是头结点指针不能变），用len作计数器，累计当前扫描的结点数，直至curr=null，返回长度len就可以了。删除结点删除结点删除结点是将表中的某个结点从表中删除，实际上还是利用查找算法，找到满足条件的将要删除的结点后，注意删除过程中，使用的指针是被删除结点的直接前驱结点的指针，直接删除即可。2.3 2.3 线性表的链式存储结构线性表的链式存储结构 打印链表的所有元素打印链表的所有元素 打印链表的所有结点的数值，与求链表的长度的方法基本类同，只是在找到每个结点的后面，增加一条打印命令，去掉计数命令，在次方法中需要特别处理的是链表为空时的情况。在整个单向链表的所有操作中，只要做

14、到单向链表的初始化后，剩下比较重要的算法是对链表的插入、删除和查询操作，只要比较灵活地掌握插入、删除和查询三个基本的操作，其它的大部分操作可以利用以上的三种基本操作组合实现。2.3 2.3 线性表的链式存储结构线性表的链式存储结构在单链表中，因为指针是单一方向，结点的查找只能从前向后查找，不能反向查找，所以在插入、删除结点时，特别是在某个结点之前插入，或者删除某个结点时，需要利用结点的前趋结点的指针，所以在查找结点时，需要保留结点的直接前趋结点位置。也因为在单链表中，结点的查找只能从前向后查找，不能反向查找，所以在单向链表中，头结点的非常重要，不能丢失。2.3 2.3 线性表的链式存储结构线性

15、表的链式存储结构2.3.3 循环链表循环链表 循环链表又称为循环线性链表，其存储结构基本同单向链表，是在单向链表的基础上加以改进形成的，它可以解决单向链表中单方向查找的缺点。因为单向链表只能沿着一个方向，不能反向查找，并且最后一个结点的指针域的值是null，为解决单向链表的缺点，可以利用末尾结点的空指针完成前向查找。将单链表的末尾结点的指针域的null变为指向第一个结点，逻辑上形成一个环型，该存储结构称之为单向循环链表。相对单链表而言，有以下的优点：在不增加任何空间的情况下，能够已知任意结点的地址，可以找到链表中的所有结点（环向查找）。当然在查找某个结点的前驱结点时，需要增加时间开销完成，查找

16、的时间复杂度是O（n）。2.3 2.3 线性表的链式存储结构线性表的链式存储结构2.3.3 循环链表循环链表 循环线性链表中已知链表中任何结点，可以找到链表中的所有结点，我们一般还是习惯把头结点作为已知条件，但是如果已知条件是头结点，将在以下的插入或删除结点时造成不方便：删除末尾结点第一个结点前插入新结点在第一种情况下，虽然能够完成删除，但是，需要我们从头结点开始逐个查找结点直到找到最后一个结点的直接前驱结点，然后才能够删除，整个算法的时间复杂度是O（n）。在第二种情况下，虽然能够完成插入，但是，需要我们从头结点开始逐个查找结点直到找到最后一个结点，然后才能够插入，因为我们需要修改最后一个结点

17、的指针域，整个算法的时间复杂度是O（n）。2.3 2.3 线性表的链式存储结构线性表的链式存储结构2.3.3 循环链表循环链表以上的两种情况造成无谓的时间开销，为解决这个问题，我们通常在循环链表以末尾结点指针为已知条件，这样以上的两种情况，都可以直接完成，因为已知末尾结点可以直接找到头结点，此时的时间复杂度为O（1），这样在不增加任何开销的情况下，减少了时间的开销。空的循环线性链表根据定义可以与单向链表相同，也可以不相同。判断循环链表的末尾结点条件也就不同于单向链表，不同之处在于是单向链表是判别最后结点的指针域是否为空，而循环线性链表末尾结点的判定条件是其指针域的值指向头结点。2.3 2.3

18、线性表的链式存储结构线性表的链式存储结构2.3.3 循环链表循环链表循环链表的插入、删除运算基本同单向链表，只是查找时判别条件不同而已；但是这种循环链表实现各种运算时的危险之处在于：链表没有明显的尾端，可能使算法进入死循环，所以判断条件应该用curr.next()!=head替换单向链表的curr.next()!=null完成遍历所有结点。2.3 2.3 线性表的链式存储结构线性表的链式存储结构2.3.4 双链表双链表 单循环链表中，虽然从任一已知结点出发能找到其直接前趋结点，但时间耗费是O（n）。若希望从表中快速确定一个结点的直接前趋，可以在单链表的每个结点里再增加一个指向其直接前趋的指针域

19、prior。这样形成的链表中有两条方向不同的链，故称之为双（向）链表。双向链表的运算类似单向链表的运算，主要包括插入结点、删除结点、查询结点等运算。2.3 2.3 线性表的链式存储结构线性表的链式存储结构2.3.4 双链表双链表 双链表的插入结点双链表的插入结点 双向链表的插入结点的实现比较简单，基本同单向链表，只不过在某个结点前或后插入新的结点时，只要找到该结点就可以了。另外在第一个结点之前插入时同单向链表插入结点，需要单独处理。在插入过程中和单向链表的主要的不同点是修改的指针的个数不同。单向链表修改两个指针；双向链表需要修改四个指针。2.3 2.3 线性表的链式存储结构线性表的链式存储结构

20、2.3.4 双链表双链表 双链表的插入结点双链表的插入结点插入结点应分为以下几个步骤：申请新结点，同时给新结点的数据域、两个指针域赋值；将当前结点的next域指向新结点；将当前结点的直接后继的前驱指针指向新结点。2.3 2.3 线性表的链式存储结构线性表的链式存储结构2.3.4 双链表双链表 双向链表的删除结点双向链表的删除结点 双向链表的删除结点的实现基本同单向链表，只不过在某个结点前或后删除新的结点时，只要找到该结点就可以了，不需要保留前驱结点。另外在删除第一个结点时同单向链表删除头结点，需要单独处理。在删除过程中和单向链表的主要的不同点是修改的指针的个数不同。单向链表修改一个指针；双向链

21、表需要修改两个指针。2.3 2.3 线性表的链式存储结构线性表的链式存储结构2.3.4 双链表双链表 双向链表的删除结点双向链表的删除结点 删除双向链表的结点步骤有：修改当前结点的next域修改当前结点的后继结点前驱结点指针 双向链表的查询结点双向链表的查询结点 双向链表的查询结点的实现基本同单向链表，只要按照next的方向找到该结点就可以了，不需要保留前驱结点。如果找到，返回结点位置，否则返回null。查找结点的步骤是：从头结点开始，直到找到该结点或是查找失败。2.4 2.4 链表应用举例链表应用举例例1 链式存储下的一元多项式加法例2Josephus问题 例3：使用迭代器编写一个将链接线性

22、表逆序打印的算法。2.5 2.5 顺序表和链表的比较顺序表和链表的比较 线性表的存储有两种：顺序存储表和链式存储表。具体存储方式可根据具体问题的要求和性质来决定。根据线性表定长与不定长确定：顺序存储结构一般要求数据存放的物理和逻辑地址连续；而链式存储结构数据存放地址可连续可不连续，在线性表长度没有确定的情况下，一般采用链式存储结构比较好，反之应以顺序存储为主。2.5 2.5 顺序表和链表的比较顺序表和链表的比较一般选择存储结构时可以主要从以下两个方面考虑：（1）基于空间的考虑顺序表的存储空间是静态分配的，在程序执行之前一般必须明确规定它的存储规模。若线性表的长度n变化较大，则存储规模难于预先确

23、定（定义太大可能浪费空间，定义太小又可能不够用）。因此，当线性表的长度变化较大，难以估计其存储规模时，以采用动态链表作为存储结构为好。反之如果存储规模比较小，并且线性表的长度一般固定时，可使用顺序存储。存储密度=（结点数据本身所占的存储量）/（结点结构所占的存储总量）一般地，存储密度越大，存储空间的利用率就越高。顺序表的存储密度为1，而链表的存储密度小于1。由此可知，当线性表的长度变化不大，易于事知确定其大小时，为了节约存储空间，宜采用顺序表作为存储结构。2.5 2.5 顺序表和链表的比较顺序表和链表的比较（2）基于时间的考虑顺序表是由向量实现的，它是一种随机存取结构，对表中任一结点都可在O（1）时间内直接地存取，而链表中的结点，需顺序存取，应从头指针起顺着链指针扫描结点才能获得。因此，若对线性表的操作主要是进行查找，很少做插入和删除操作时，采用顺序表的存储结构比较好。反之，如果在线性表中需要做较多的插入和删除，如果采用顺序存取，可能造成大量的数据移动，在时间上的开销较大，而采用链式存储时，只需要修改相应地指针就可以了。2.5 2.5 顺序表和链表的比较顺序表和链表的比较如果比较偏重线性表的查找，通常很少对线性表进行插入删除操作时，因为顺序存储结构为随机存取（存取速度快），而链式存储结构为顺序存取（相对较慢），此时应所以应采用顺序存储结构较好。