第十二章 数据结构精选文档.ppt

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

1、第十二章 数据结构本讲稿第一页，共九十一页主要内容：主要内容：12.1数据结构的主要研究内容数据结构的主要研究内容12.2数据结构基本概念数据结构基本概念12.3 数据的逻辑结构数据的逻辑结构12.4 线性表及其顺序存储结构线性表及其顺序存储结构12.5栈和队列栈和队列12.6 树与二叉树树与二叉树12.7 查找技术查找技术12.8 排序技术排序技术本讲稿第二页，共九十一页12.1数据结构的主要研究内容数据结构的主要研究内容 12.1数据结构的主要研究内容数据结构的主要研究内容数据结构是相互之间存在一种或多种特定关系的数据元素的集数据结构是相互之间存在一种或多种特定关系的数据元素的集合。数据结

2、构作为计算机的一门学科，主要研究和讨论以下三合。数据结构作为计算机的一门学科，主要研究和讨论以下三个方面的问题：个方面的问题：1数据集合中各数据元素之间所固有的逻辑关系，即数据的数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构。逻辑结构。数据的逻辑结构是从逻辑关系上描述数据，与数据的存储无关，是数据的逻辑结构是从逻辑关系上描述数据，与数据的存储无关，是独立于计算机的。数据的逻辑结构可以看作是从具体问题抽象出来独立于计算机的。数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。数据的逻辑结构包含：的数学模型。数据的逻辑结构包含：（1）表示数据元素的信息；）表示数据元素的信息；（2）表

3、示各数据元素之间的前后件关系。）表示各数据元素之间的前后件关系。本讲稿第三页，共九十一页2各数据元素在计算机中存储关系，即数据的存储结构。各数据元素在计算机中存储关系，即数据的存储结构。数据的存储结构有顺序、链接、索引等。数据的存储结构是数据的存储结构有顺序、链接、索引等。数据的存储结构是逻辑结构用计算机语言的实现（亦称为映象），它依赖于逻辑结构用计算机语言的实现（亦称为映象），它依赖于计算机语言。对机器语言而言，存储结构是具体的。一般计算机语言。对机器语言而言，存储结构是具体的。一般只在高级语言的层次上讨论存储结构。只在高级语言的层次上讨论存储结构。对各种数据结构进行的运算。对各种数据结构进

4、行的运算。3.数据的运算定义在数据的逻辑结构上，每种逻辑结构都有数据的运算定义在数据的逻辑结构上，每种逻辑结构都有一个运算的集合。最常用的检索、插入、删除、更新、排一个运算的集合。最常用的检索、插入、删除、更新、排序等运算实际上只是在抽象的数据上所施加的一系列抽象序等运算实际上只是在抽象的数据上所施加的一系列抽象的操作。所谓抽象的操作，是指只知道这些操作是的操作。所谓抽象的操作，是指只知道这些操作是“做什做什么么”，而无须考虑，而无须考虑“如何做如何做”。只有确定了存储结构之后，。只有确定了存储结构之后，才考虑如何具体实现这些运算。才考虑如何具体实现这些运算。本讲稿第四页，共九十一页12.2数

5、据结构基本概念数据结构基本概念 12.2.1数据数据 数数据据是是指指所所有有能能输输入入到到计计算算机机中中并并被被计计算算机机程程序序处处理理的的符符号号的的总总称称。数数据据是是信信息息的的载载体体，它它能能够够被被计计算算机机识识别别、存存储储和和加加工工处处理理，是是计计算算机机程程序序加加工工的的“原原料料”。随随着着计计算算机机应应用用领领域域的的扩扩大大，数数据据可可以以分分为为两两大大类类：一一类类是是整整数数、实实数数等等数数值值数数据据；另另一一类类是是图图形形、图图像像、声声音音、文文字字等等非非数数值值数数据据。这这里里要要注注意意数数据据并并不等于数字，数字是隶属于

6、数据的。不等于数字，数字是隶属于数据的。本讲稿第五页，共九十一页 12.2.2数据元素与数据项数据元素与数据项 数数据据元元素素也也称称为为元元素素、结结点点、顶顶点点或或记记录录，是是数数据据的的基基本本单单位位，在在计计算算机机程程序序中中通通常常作作为为一一个个整整体体进进行行考考虑虑和和处处理理。一一个个数数据据元元素素可可由由若若干干个个数数据据项项组组成成，数数据据项项是是数数据据的的最最小小单单位位。数数据据元元素素具具有有广广泛泛的的含含义义，一一般般来来说说，现现实实世世界界中中客客观观存存在在的的一一切切个个体体都都可可以以是是数数据据元元素素。例例如如在在表表12-1中中

7、，整整个个表表记记录录的的是是学学生生成成绩绩数数据据，每每个个学学生生的的记记录录行行是是其其中中一一个个数数据据元元素素，即即该该表表由由4个个数数据据元元素素构构成成，而而某某一一个个数数据据元元素素（记记录录行行）又又是是由由5个个数数据据项项组组成成。例例如如语语文文成成绩绩67则则是是表表中中第第一一个个数数据据元元素素（记录行）中的数据项。数据项是不可再分的数据内容。（记录行）中的数据项。数据项是不可再分的数据内容。本讲稿第六页，共九十一页数数据据对对象象是是性性质质相相同同的的数数据据元元素素的的集集合合。如如上上例例中中一一个个班班级级的的成成绩绩表表可可以以看看作作一一个个

8、数数据据对对象象。一一般般来来说说，人人们们不不会会同同时时处处理理特特征征完完全全不不同同且且互互相相之之间间没没有有任任何何关关系系的的各各类类数数据据元元素素，对对于于具具有有不不同同特特征征的的数数据据元元素素总总是是分分别别进行处理。进行处理。学号学号姓名姓名语语文文数学数学英英语语0406010104060101李李丽丽6767878783830406010204060102张鹏张鹏9292828264640406010304060103刘海刘海7878727276760406010404060104金玉金玉565668687171本讲稿第七页，共九十一页 12.2.3数据结构数据

9、结构数据元素都不是孤立存在的，而是在它们之间存在着某种特定的关数据元素都不是孤立存在的，而是在它们之间存在着某种特定的关系，这种数据元素相互之间的关系称为结构。在数据处理领域中，系，这种数据元素相互之间的关系称为结构。在数据处理领域中，通常把数据元素之间这种固有的关系简单地用前后件关系通常把数据元素之间这种固有的关系简单地用前后件关系(或直接前或直接前驱与直接后继关系驱与直接后继关系)来描述。来描述。例如，在考虑一年四个季节的顺序关系时，则例如，在考虑一年四个季节的顺序关系时，则“春春”是是“夏夏”的前件（即直接前驱），而的前件（即直接前驱），而“夏夏”是是“春春”的后件（即直接后的后件（即直

10、接后继）。同样，继）。同样，“夏夏”是是“秋秋”的前件，的前件，“秋秋”是是“夏夏”的后件；的后件；“秋秋”是是“冬冬”的前件，的前件，“冬冬”是是“秋秋”的后件。的后件。前后件关系是数据元素之间的一个基本关系，但前后件关系所前后件关系是数据元素之间的一个基本关系，但前后件关系所表示的实际意义随具体对象的不同而不同。一般来说，数据元表示的实际意义随具体对象的不同而不同。一般来说，数据元素之间的任何关系都可以用前后件关系来描述。素之间的任何关系都可以用前后件关系来描述。本讲稿第八页，共九十一页 12.2.4数据的逻辑结构数据的逻辑结构通俗地说，数据结构是指带有结构的数据元素的集合。在通俗地说，数

11、据结构是指带有结构的数据元素的集合。在此，所谓结构实际上就是指数据元素之间的前后件关系。此，所谓结构实际上就是指数据元素之间的前后件关系。数据元素之间的前后件关系即指它们的逻辑关系，而与它数据元素之间的前后件关系即指它们的逻辑关系，而与它们在计算机中的存储位置无关。所谓数据的逻辑结构，是们在计算机中的存储位置无关。所谓数据的逻辑结构，是指反映数据元素之间逻辑关系的数据结构。指反映数据元素之间逻辑关系的数据结构。图图12-1 12-1 数据的逻辑结构数据的逻辑结构本讲稿第九页，共九十一页表中的每一行是一个数据元素（或记录、结点），它由学号、表中的每一行是一个数据元素（或记录、结点），它由学号、姓

12、名、各科成绩等数据项组成。表中数据元素之间的逻辑关系姓名、各科成绩等数据项组成。表中数据元素之间的逻辑关系是：对表中任一个结点，与它相邻的直接前趋（是：对表中任一个结点，与它相邻的直接前趋（Immediate Predecessor）最多只有一个；与表中任一结点相邻的直接后）最多只有一个；与表中任一结点相邻的直接后继（继（Immediate Successor）也最多只有一个。表中只有第一）也最多只有一个。表中只有第一个结点没有直接前趋，故称为开始结点；也只有最后一个结点个结点没有直接前趋，故称为开始结点；也只有最后一个结点没有直接后继，故称之为终端结点。上述结点间的关系构成了没有直接后继，故

13、称之为终端结点。上述结点间的关系构成了这张学生成绩表的逻辑结构。这张学生成绩表的逻辑结构。逻辑结构主要可分为线性结构（线性表、栈和队列）和非线性结逻辑结构主要可分为线性结构（线性表、栈和队列）和非线性结构（树、图和集合）。如图构（树、图和集合）。如图12-1所示。所示。本讲稿第十页，共九十一页12.2.5数据的存储结构数据的存储结构数据的存储结构又称为物理结构，是数据及其逻辑结构在计算机数据的存储结构又称为物理结构，是数据及其逻辑结构在计算机中的表示。在数据的存储结构中，不仅要存放各数据元素的信息，中的表示。在数据的存储结构中，不仅要存放各数据元素的信息，还存放元素之间的前后件关系的信息。数据

14、的存储结构属于具体还存放元素之间的前后件关系的信息。数据的存储结构属于具体实现的视图，是面向计算机的，其基本目标是将数据及其逻辑关实现的视图，是面向计算机的，其基本目标是将数据及其逻辑关系存储到计算机的内存中。系存储到计算机的内存中。一般来说，一种数据的逻辑结构根据需要可以表示成多种一般来说，一种数据的逻辑结构根据需要可以表示成多种存储结构，常用数据的存储结构有如下存储结构，常用数据的存储结构有如下4种。种。1顺序存储方式顺序存储方式每一个存储结点只含有一个数据元素；所有的存储结点相继每一个存储结点只含有一个数据元素；所有的存储结点相继存储在一个连续的存储区里；用存储结点之间的位置关系表存储在

15、一个连续的存储区里；用存储结点之间的位置关系表示数据元素之间的逻辑关系。示数据元素之间的逻辑关系。本讲稿第十一页，共九十一页2链式存储方式链式存储方式每一个存储结点不仅含有各数据元素，还包括指针。每一个指针每一个存储结点不仅含有各数据元素，还包括指针。每一个指针指向一个与本结点有逻辑关系的结点，即用指针表示逻辑关系。指向一个与本结点有逻辑关系的结点，即用指针表示逻辑关系。3索引存储方式索引存储方式每一个存储结点仅含有一个数据元素，所有的存储结点都连续存放。此每一个存储结点仅含有一个数据元素，所有的存储结点都连续存放。此外，增设一个索引表。外，增设一个索引表。4散列存储方式散列存储方式每一个存储

16、结点仅含有一个数据元素，数据元素按散列函数确定存储位每一个存储结点仅含有一个数据元素，数据元素按散列函数确定存储位置。置。数据的逻辑结构与数据的存储结构不一定相同。一般来说，一数据的逻辑结构与数据的存储结构不一定相同。一般来说，一种数据的逻辑结构根据需要可以表示成多种存储结构。采用不种数据的逻辑结构根据需要可以表示成多种存储结构。采用不同的存储结构，其数据处理的效率是不相同的。同的存储结构，其数据处理的效率是不相同的。本讲稿第十二页，共九十一页数据的逻辑结构有两个要素：一是数据元素的集合；二是各数数据的逻辑结构有两个要素：一是数据元素的集合；二是各数据元素之间的前后件关系。对这两个要素的表示可

17、有两种方式：据元素之间的前后件关系。对这两个要素的表示可有两种方式：一是用二元关系表示；二是直观地用图形表示。一是用二元关系表示；二是直观地用图形表示。在二元关系表示中，将数据元素的集合记为在二元关系表示中，将数据元素的集合记为D，反映，反映D中中各数据元素之间的前后件关系记为各数据元素之间的前后件关系记为R。一个数据结构就可。一个数据结构就可以表示成以表示成B=（D,R）的二元组关系，其中）的二元组关系，其中B表示数据结构。表示数据结构。例如：假设例如：假设a和和b是是D中的两个数据，则二元组中的两个数据，则二元组(a，b)表示表示a是是b的前件，的前件，b是是a的后件。这样，在的后件。这样

18、，在D中的每两个元素之中的每两个元素之间的关系都可以用这种二元组来表示。间的关系都可以用这种二元组来表示。12.3 数据的逻辑结构数据的逻辑结构12.3.1逻辑结构的表现方式逻辑结构的表现方式本讲稿第十三页，共九十一页 在在数数据据结结构构的的图图形形表表示示中中，对对于于数数据据集集合合D中中的的每每一一个个数数据据元元素素用用中中间间标标有有元元素素值值的的方方框框表表示示，一一般般称称之之为为数数据据结结点点，并并简简称称为为结结点点。为为了了进进一一步步表表示示各各数数据据元元素素之之间间的的前前后后件件关关系系，对对于于关关系系R中中的的每每一一个个二二元元组组，用用一一条条有有向向

19、线线段段从从前前件件结结点点指指向向后后件件结结点点。例例如如，一一年年四四季的数据结构可以用如图季的数据结构可以用如图12-2所示的图形来表示。所示的图形来表示。春夏秋冬图12-2 逻辑结构的图形表示本讲稿第十四页，共九十一页1线性结构线性结构如果一个非空的数据结构满足下列两个条件：如果一个非空的数据结构满足下列两个条件：（1）有且只有一个根结点。）有且只有一个根结点。（2）每一个结点最多有一个前件，也最多有一个后件。）每一个结点最多有一个前件，也最多有一个后件。则称该数据结构为线性结构，线性结构又称线性表。则称该数据结构为线性结构，线性结构又称线性表。2线性结构逻辑特征线性结构逻辑特征（1

20、）存在唯一的一个被称作）存在唯一的一个被称作“第一个第一个”的数据元素。的数据元素。（2）存在唯一的一个被称作）存在唯一的一个被称作“最后一个最后一个”的数据元素。的数据元素。（3）除第一个之外，集合中的每个数据元素均只有一个前驱。）除第一个之外，集合中的每个数据元素均只有一个前驱。（4）除最后一个之外，集合中的每个数据元素均只有一个后继。）除最后一个之外，集合中的每个数据元素均只有一个后继。12.3.2 线性逻辑结构线性逻辑结构本讲稿第十五页，共九十一页在线性结构中，各数据元素之间的前后关系是很简单的。在线性结构中，各数据元素之间的前后关系是很简单的。如上述的一年四季这个数据结构，属于线性结

21、构。线性如上述的一年四季这个数据结构，属于线性结构。线性表是一个线性结构。表是一个线性结构。特别需要说明的是在一个线性结构中插入或删除任何一个特别需要说明的是在一个线性结构中插入或删除任何一个结点后还应是线性结构。如果一个数据结构满足上述两个结点后还应是线性结构。如果一个数据结构满足上述两个条件，但当在此数据结构中插入或删除任何一个结点后就条件，但当在此数据结构中插入或删除任何一个结点后就不满足这两个条件，则该数据结构不能称为线性结构。如不满足这两个条件，则该数据结构不能称为线性结构。如果一个数据结构不是线性结构，则称之为非线性结构。果一个数据结构不是线性结构，则称之为非线性结构。本讲稿第十六

22、页，共九十一页 非非线线性性结结构构的的逻逻辑辑特特征征是是一一个个结结点点可可能能有有多多个个直直接接前前驱驱和和直直接接后后继继。例例如如，树树和和图图都都是是非非线线性性结结构构。线线性性结结构构与与非非线线性性结结构构都都可可以以是是空空的的数数据据结结构构。一一个个空空的的数数据据结结构构究究竟竟是是属属于于线线性性结结构构还还是是属属于于非非线线性性结结构构，这这要要根根据据具具体体情情况况来来确确定定。如如果果对对该该数数据据结结构构的的运运算算是是按按线线性性结结构构的的规规则则来来处处理理的的，则则属属于于线线性性结结构构，否否则属于非线性结构。则属于非线性结构。12.3.3

23、非线性逻辑结构非线性逻辑结构本讲稿第十七页，共九十一页线性表是最基本、最简单、也是最常用的一种数据结构。线性表是最基本、最简单、也是最常用的一种数据结构。线性表中数据元素之间的关系是一对一的关系，即除了线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其他数据元素都是首第一个和最后一个数据元素之外，其他数据元素都是首尾相接的。线性表的逻辑结构简单，便于实现和操作。尾相接的。线性表的逻辑结构简单，便于实现和操作。因此，线性表这种数据结构在实际应用中是广泛采用的因此，线性表这种数据结构在实际应用中是广泛采用的一种数据结构。一种数据结构。12.4 线性表及其顺序存储结构线

24、性表及其顺序存储结构12.4.1线性表的基本概念线性表的基本概念本讲稿第十八页，共九十一页线性结构特点如下：线性结构特点如下：1有且仅有一个开始结点有且仅有一个开始结点(表头结点表头结点)，它没有直接前驱，它没有直接前驱，只有一个直接后继。只有一个直接后继。2有且仅有一个终端结点有且仅有一个终端结点(表尾结点表尾结点)，它没有直接后继，只有，它没有直接后继，只有一个直接前驱。一个直接前驱。3其他结点都有一个直接前驱和直接后继。其他结点都有一个直接前驱和直接后继。4元素之间为一对一的线性关系。元素之间为一对一的线性关系。需要注意的是线性表中数据元素的相对位置是确定的，如果需要注意的是线性表中数据

25、元素的相对位置是确定的，如果把一个线性表中的数据元素的位置做改动，那么变动后的线把一个线性表中的数据元素的位置做改动，那么变动后的线性表与原来的线性表是两个不同的线性表。在实现线性表数性表与原来的线性表是两个不同的线性表。在实现线性表数据元素的存储方面，一般可用顺序存储结构和链式存储结构据元素的存储方面，一般可用顺序存储结构和链式存储结构两种方法。两种方法。本讲稿第十九页，共九十一页12.4.2 线性表的顺序存储结构线性表的顺序存储结构 线线性性表表的的顺顺序序存存储储是是指指用用一一组组地地址址连连续续的的存存储储单单元元依依次次存存储储线线性性表表中中的的数数据据元元素素，从从而而使使得得

26、逻逻辑辑上上相相邻邻的的两两个个元元素素在在物物理理位位置置上上也也相相邻邻，如如图图12-3所所示示。在在这这种种存存储储方方式式下下，存存储储逻逻辑辑关关系系无无须须占占用用额额外外的的存存储空间。储空间。a1a2a3an本讲稿第二十页，共九十一页一般地，以一般地，以Loc(a1)表示线性表中第一个元素的存储位置，则在顺序表示线性表中第一个元素的存储位置，则在顺序存储结构中，第存储结构中，第i个元素的存储位置为：个元素的存储位置为：Loc(a1)=Loc(a1)+(i1)L其中其中L是表中每个元素所占空间的大小。根据该计算关系，可随机存取表是表中每个元素所占空间的大小。根据该计算关系，可随

27、机存取表中的任意一个元素。中的任意一个元素。1线性表的顺序存储结构基本特点：线性表的顺序存储结构基本特点：（1）线性表中所有元素所占的存储空间是连续的。）线性表中所有元素所占的存储空间是连续的。（2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。由此可以看出，在线性表的顺序存储结构中，其前后件两个元素在存储空由此可以看出，在线性表的顺序存储结构中，其前后件两个元素在存储空间中是紧邻的，且前件元素一定存储在后件元素的前面。间中是紧邻的，且前件元素一定存储在后件元素的前面。线性表采用顺序存储结构的优点是可以随机存取表中的元素，查找元素

28、的线性表采用顺序存储结构的优点是可以随机存取表中的元素，查找元素的速度很快。速度很快。本讲稿第二十一页，共九十一页2线性表的顺序存储结构存在以下几方面的缺点：线性表的顺序存储结构存在以下几方面的缺点：（1）在一般情况下，要在顺序存储的线性表中插入一个新元素或）在一般情况下，要在顺序存储的线性表中插入一个新元素或删除一个元素时，为了保证插入或删除后的线性表仍然为顺序存删除一个元素时，为了保证插入或删除后的线性表仍然为顺序存储，则在插入或删除过程中需要移动大量的数据元素。因此，对储，则在插入或删除过程中需要移动大量的数据元素。因此，对于大的线性表，特别是元素的插入或删除很频繁的情况下，采用于大的线

29、性表，特别是元素的插入或删除很频繁的情况下，采用顺序存储结构是很不方便的，插入与删除运算的效率都很低。顺序存储结构是很不方便的，插入与删除运算的效率都很低。（2）在顺序存储结构下，线性表的存储空间不便于扩充。）在顺序存储结构下，线性表的存储空间不便于扩充。当为一个线性表分配顺序存储空间后，如果出现线性表的存当为一个线性表分配顺序存储空间后，如果出现线性表的存储空间已满，但还需要插入新的元素时，就会发生储空间已满，但还需要插入新的元素时，就会发生“上溢上溢”错误。在这种情况下，如果在原线性表的存储空间后找不到错误。在这种情况下，如果在原线性表的存储空间后找不到与之连续的可用空间，则会导致运算的失

30、败或中断。与之连续的可用空间，则会导致运算的失败或中断。本讲稿第二十二页，共九十一页（3）线线性性表表的的顺顺序序存存储储结结构构不不便便于于对对存存储储空空间间的的动动态态分分配配。在在实实际际应应用用中中，往往往往是是同同时时有有多多个个线线性性表表共共享享计计算算机机的的存存储储空空间间。如如果果将将存存储储空空间间平平均均分分配配给给各各线线性性表表，则则有有可可能能造造成成有有的的线线性性表表的的空空间间不不够够用用，而而有有的的线线性性表表的的空空间间根根本本用用不不着着或或用用不不满满，这这就就使使得得在在有有的的线线性性表表空空间间无无用用而而处处于于空空闲闲的的情情况况下下，

31、另另外外一一些些线线性性表表的的操操作作由由于于“上上溢溢”而而无无法法进进行行。如如果果对对每每一一个个线线性性表表的的存存储储空空间间进进行行动动态态分分配配，则则为为了了保保证证每每一一个个线线性性表表的的存存储储空空间间连连续续且且顺顺序序分分配配，会会导导致致在在对对某某个个线线性性表表进进行行动动态态分分配配存储空间时，必须要移动其他线性表中的数据元素。存储空间时，必须要移动其他线性表中的数据元素。本讲稿第二十三页，共九十一页 12.4.3 线性表的链式存储结构线性表的链式存储结构1线性链表的基本概念线性链表的基本概念线性表的链式存储结构称为线性链表。为了适应线性表的链式线性表的链

32、式存储结构称为线性链表。为了适应线性表的链式存储结构，计算机存储空间被划分为一个一个小块，每一小块存储结构，计算机存储空间被划分为一个一个小块，每一小块占若干字节，通常称这些小块为存储结点。为了存储线性表中占若干字节，通常称这些小块为存储结点。为了存储线性表中的每一个元素，一方面要存储数据元素的值，另一方面要存储的每一个元素，一方面要存储数据元素的值，另一方面要存储各数据元素之间的前后件关系。为此目的，将存储空间中的每各数据元素之间的前后件关系。为此目的，将存储空间中的每一个存储结点分为两部分：一部分用于存储数据元素的值，称一个存储结点分为两部分：一部分用于存储数据元素的值，称为数据域；另一部

33、分用于存放下一个数据元素的存储序号（存为数据域；另一部分用于存放下一个数据元素的存储序号（存储结点的地址），称为指针域。线性链表的存储结构如图储结点的地址），称为指针域。线性链表的存储结构如图12-4所示。所示。本讲稿第二十四页，共九十一页本讲稿第二十五页，共九十一页HEADHEAD数据数据1 1数据数据2 2数据数据n NULLn NULL图图12-5 12-5 线线性性链链表表的的逻逻辑辑结结构构 一一般般来来说说，在在线线性性表表的的链链式式存存储储结结构构中中，各各数数据据结结点点的的存存储储序序号号是是不不连连续续的的，并并且且各各结结点点在在存存储储空空间间中中的的位位置置关关系系

34、与与逻逻辑辑关关系系也也不不一一致致。线线性性链链表表的的逻逻辑辑结结构构如如图图12-5所所示示。在在线线性性链链表表中中，各各数数据据元元素素之之间间的的前前后后件件关关系系是是由由各各结结点点的的指指针针域域来来指指示示的的。指指向向线线性性表表中中第第一一个个结结点点的的指指针针HEAD称称为为头头指指针针。当当HEAD=NULL（或或0）时时称称为为空空表表。对对于于栈栈和和队队列列，除除了了采采用用顺顺序序存存储储结结构构外外，还可采用链式存储结构。还可采用链式存储结构。本讲稿第二十六页，共九十一页2线性链表及其基本运算线性链表及其基本运算（1）在线性链表中查找指定元素）在线性链表

35、中查找指定元素在非空线性链表中寻找包含指定元素值在非空线性链表中寻找包含指定元素值x的前一个结点的前一个结点p的基本方法如下：从头指针指向的结点开始往后沿指针进的基本方法如下：从头指针指向的结点开始往后沿指针进行扫描，直到后面已没有结点或下一个结点的数据域为行扫描，直到后面已没有结点或下一个结点的数据域为x为。因此，由这种方法找到的结点为。因此，由这种方法找到的结点p有两种可能：当线性有两种可能：当线性链表中存在包含元素链表中存在包含元素x的结点时，则找到的的结点时，则找到的p 为第一次遇为第一次遇到的包含元素到的包含元素x的前一个结点序号；当线性链表中不存在的前一个结点序号；当线性链表中不存

36、在包含元素包含元素x的结点时，则找到的的结点时，则找到的p为线性链表中的最后一为线性链表中的最后一个结点序号。个结点序号。本讲稿第二十七页，共九十一页（2）线性链表的插入）线性链表的插入线性链表的插入是指在链式存储结构下的线性表中插入一个新元素。线性链表的插入是指在链式存储结构下的线性表中插入一个新元素。前面主要讨论了线性表的顺序存储结构。线性表的顺序存储结构具前面主要讨论了线性表的顺序存储结构。线性表的顺序存储结构具有简单、运算方便等优点，特别是对于小线性表或长度固定的线性有简单、运算方便等优点，特别是对于小线性表或长度固定的线性表，采用顺序存储结构的优越性更为突出。但是，线性表的顺序存表，

37、采用顺序存储结构的优越性更为突出。但是，线性表的顺序存储结构在某些情况下显得不那么方便，运算效率不那么高。因此，储结构在某些情况下显得不那么方便，运算效率不那么高。因此，对于大的线性表，特别是元素变动频繁的大线性表不宜采用顺序存对于大的线性表，特别是元素变动频繁的大线性表不宜采用顺序存储结构，而是采用上面介绍的链式存储结构。储结构，而是采用上面介绍的链式存储结构。假设要在线性表的两个数据元素假设要在线性表的两个数据元素a和和b之间插入一个数据元素之间插入一个数据元素x，已知，已知p为为其链表存储结构中指向结点其链表存储结构中指向结点a的指针，如图所示。的指针，如图所示。为插入数据元素为插入数据

38、元素x，首先要生成一个数据域为，首先要生成一个数据域为x的结点，然后插入在链表中。的结点，然后插入在链表中。根据插入操作的逻辑定义，还需要修改结点根据插入操作的逻辑定义，还需要修改结点a中的指针域，令其指向结点中的指针域，令其指向结点x，而结点，而结点x中的指针域应指向结点中的指针域应指向结点b，从而实现，从而实现3个元素个元素a、b和和x之间逻辑关之间逻辑关系的变化。插入后的链表如图所示。系的变化。插入后的链表如图所示。本讲稿第二十八页，共九十一页本讲稿第二十九页，共九十一页反之，如图反之，如图12-7所示，在线性表中删除元素所示，在线性表中删除元素b时，为在链时，为在链表中实现元素表中实现

39、元素a、b和和c之间逻辑关系的变化，仅需修改结之间逻辑关系的变化，仅需修改结点点a中的指针域即可。中的指针域即可。a ap pb bc c图图12-7 12-7 链表的删除操作链表的删除操作本讲稿第三十页，共九十一页线性链表分为单链表、双向链表和循环链表三种类型。在单链表线性链表分为单链表、双向链表和循环链表三种类型。在单链表中，每一个结点只有一个指针域，因此，在这种线性链表中，只中，每一个结点只有一个指针域，因此，在这种线性链表中，只能沿指针向链尾方向进行扫描，这对于某些问题的处理会带来不能沿指针向链尾方向进行扫描，这对于某些问题的处理会带来不便，因为在这种链接方式下，由某一个结点出发，只能

40、找到它的便，因为在这种链接方式下，由某一个结点出发，只能找到它的后件，而为了找出它的前件，必须从头指针开始重新寻找。因此，后件，而为了找出它的前件，必须从头指针开始重新寻找。因此，在某些应用中，对于线性链表中的每个结点设置两个指针，一个在某些应用中，对于线性链表中的每个结点设置两个指针，一个称为左指针称为左指针(Llink)，指向其前件结点；另一个称为右指针，指向其前件结点；另一个称为右指针(Rlink)，指向其后件结点，这种链表称为双向链表。循环链表与，指向其后件结点，这种链表称为双向链表。循环链表与单链表的区别仅仅在于其尾结点的链域值不是空，而是一个指向单链表的区别仅仅在于其尾结点的链域值

41、不是空，而是一个指向头结点的指针。循环链表的主要优点是：从表中任一结点出发都头结点的指针。循环链表的主要优点是：从表中任一结点出发都能通过后移操作而扫描整个循环链表。但对单链表来说，只有从能通过后移操作而扫描整个循环链表。但对单链表来说，只有从头结点开始才能扫描表中全部结点。头结点开始才能扫描表中全部结点。本讲稿第三十一页，共九十一页 12.5.1 12.5.1 栈及其基本运算栈及其基本运算栈及其基本运算栈及其基本运算 栈栈和和队队列列是是两两种种特特殊殊的的线线性性表表，它它们们的的逻逻辑辑结结构构和和线线性性表表相相同同，只只是是其其运运算算规规则则较较线线性性表表有有更更多多的的限限制制

42、，故故又又称称运运算算受受限限的的线线性性表表。栈和队列被广泛应用于各种程序设计中。栈和队列被广泛应用于各种程序设计中。12.5栈和队列栈和队列1栈的基本概念栈的基本概念 栈（栈（Stack）是限制仅在表的一端进行插入和删除运算的线性）是限制仅在表的一端进行插入和删除运算的线性表。表。（1）通常称插入、删除的这一端为栈顶（）通常称插入、删除的这一端为栈顶（Top），另一端称为栈），另一端称为栈底（底（Bottom）。）。（2）当表中没有元素时称为空栈。）当表中没有元素时称为空栈。（3）栈顶元素总是最后被插入的元素，栈底元素总是最先被插入的）栈顶元素总是最后被插入的元素，栈底元素总是最先被插入的

43、元素。元素。（4）栈为后进先出（）栈为后进先出（Last In First Out，简称为，简称为LIFO）或先进后出）或先进后出（First In Last Out，简称为，简称为FILO）的线性表。）的线性表。本讲稿第三十二页，共九十一页栈的修改是按后进先出的原则进行。每次删除（退栈）栈的修改是按后进先出的原则进行。每次删除（退栈）的总是当前栈中的总是当前栈中“最新最新”的元素，即最后插入（进栈）的元素，即最后插入（进栈）的元素，而最先插入的是被放在栈的底部，要到最后才的元素，而最先插入的是被放在栈的底部，要到最后才能删除。例如元素是以，能删除。例如元素是以，的顺序进栈，退栈的次的顺序进栈

44、，退栈的次序却是，序却是，。在顺序存储结构下，对这种类型线性，。在顺序存储结构下，对这种类型线性表的插入与删除运算是不需要移动表中其他数据元素的。表的插入与删除运算是不需要移动表中其他数据元素的。栈的顺序存储结构示意图如图栈的顺序存储结构示意图如图12-8 所示。通常用指针所示。通常用指针top来指示栈顶的位置，用指针来指示栈顶的位置，用指针bottom指向栈底。栈指向栈底。栈中插入一个元素称为入栈运算，从栈中删除一个元素中插入一个元素称为入栈运算，从栈中删除一个元素(即删除栈顶元素即删除栈顶元素)称为退栈运算。栈顶指针称为退栈运算。栈顶指针top动态反动态反映了栈中元素的变化情况。映了栈中元

45、素的变化情况。本讲稿第三十三页，共九十一页与一般的线性表一样，在程序设计语言中，用一维数组与一般的线性表一样，在程序设计语言中，用一维数组S(1：m)作为栈的顺序存储空间，其中作为栈的顺序存储空间，其中m为栈的最大容量。通常，栈为栈的最大容量。通常，栈底指针指向栈空间的低地址一端底指针指向栈空间的低地址一端(即数组的起始地址这一端即数组的起始地址这一端)。在栈的顺序存储空间在栈的顺序存储空间S(1：m)中，中，S(bottom)通常为栈底元素通常为栈底元素(在栈非空的情况下在栈非空的情况下)，S(top)为栈顶元素。为栈顶元素。top=0表示栈空，表示栈空，top=m表示栈满。表示栈满。本讲稿

46、第三十四页，共九十一页2栈的基本运算栈的基本运算 栈具有记忆作用，栈的基本运算主要包括入栈、退栈及读栈顶栈具有记忆作用，栈的基本运算主要包括入栈、退栈及读栈顶元素三种。元素三种。（1）入栈运算：指在栈顶位置插入一个新元素。这个运算有两个）入栈运算：指在栈顶位置插入一个新元素。这个运算有两个基本操作：首先将栈顶指针进一基本操作：首先将栈顶指针进一(即即top加加1)，然后将新元素插入，然后将新元素插入栈顶指针指向的位置。当栈顶指针已经指向存储空间的最后一个栈顶指针指向的位置。当栈顶指针已经指向存储空间的最后一个位置时，说明栈空间已满，不可能再进行入栈操作。这种情况称位置时，说明栈空间已满，不可能

47、再进行入栈操作。这种情况称为栈为栈“上溢上溢”错误。错误。（2）退栈运算：是取出栈顶元素并赋给一个指定的变量。这个）退栈运算：是取出栈顶元素并赋给一个指定的变量。这个运算有两个基本操作：首先将栈顶元素运算有两个基本操作：首先将栈顶元素(栈顶指针指向的元素栈顶指针指向的元素)赋给一个指定的变量，然后将栈顶指针退一赋给一个指定的变量，然后将栈顶指针退一(即即top减减1)。当栈。当栈顶指针为顶指针为O时，说明栈空，不可能进行退栈操作。这种情况称时，说明栈空，不可能进行退栈操作。这种情况称为栈为栈“下溢下溢”错误。错误。本讲稿第三十五页，共九十一页（3）读栈顶元素：是指将栈顶元素赋给一个指定的变量。

48、）读栈顶元素：是指将栈顶元素赋给一个指定的变量。必须注意，这个运算不删除栈顶元素，只是将它的值赋给一必须注意，这个运算不删除栈顶元素，只是将它的值赋给一个变量，因此，在这个运算中，栈顶指针不会改变。当栈顶个变量，因此，在这个运算中，栈顶指针不会改变。当栈顶指针为指针为0时，说明栈空，读不到栈顶元素。时，说明栈空，读不到栈顶元素。图图12-9，图，图12-10，图，图12-11分别表示了栈的初始，入栈及退栈的过程。分别表示了栈的初始，入栈及退栈的过程。图图12-9 栈的初始示意栈的初始示意本讲稿第三十六页，共九十一页图图12-10 入栈操作入栈操作图图12-11 12-11 出栈操作出栈操作本讲

49、稿第三十七页，共九十一页为为了了更更好好的的理理解解入入栈栈与与退退栈栈操操作作，假假设设有有4个个元元素素a,b,c,d依依次次入入栈栈，入入栈栈过过程程中中允允许许出出栈栈，则则所所有有可可能能的的出出栈栈序序列列为为abcd、abdc、acbd、acdb、adcb、bacd、badc、bcad、bcda、bdca、cbad、cbda、cdba、dcba，读者可自行分析其结果。，读者可自行分析其结果。本讲稿第三十八页，共九十一页 12.5.2队列及其基本运算队列及其基本运算1队列的基本概念队列的基本概念 队列（队列（Queue）是只允许在一端进行插入，而在另一端进行删除）是只允许在一端进行

50、插入，而在另一端进行删除的运算受限的线性表。的运算受限的线性表。（1）允许删除的一端称为队头，通常也用一个排头指针）允许删除的一端称为队头，通常也用一个排头指针(front)指向排头元素的前一个位置。指向排头元素的前一个位置。（2）允许插入的一端称为队尾，通常用一个称为尾指针）允许插入的一端称为队尾，通常用一个称为尾指针(rear)的指针指向队尾元素，即尾指针总是指向最后被插入的的指针指向队尾元素，即尾指针总是指向最后被插入的元素。元素。（3）当队列中没有元素时称为空队列。）当队列中没有元素时称为空队列。（4）队列亦称作先进先出（）队列亦称作先进先出（First In First Out）的线