《数据结构》--第二章 线性表.ppt

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

1、第第2章章 线性表线性表第第2章章 线性表线性表学习目的要求学习目的要求:1.线性表的定义和线性表的特征。线性表的定义和线性表的特征。2.线性表的顺序存储结构及其算法的实现。线性表的顺序存储结构及其算法的实现。3.线性链表的描述及其算法的实现。线性链表的描述及其算法的实现。4.循环链表和双向循环链表的描述。循环链表和双向循环链表的描述。5.数组的顺序存储和矩阵的压缩存储的描述。数组的顺序存储和矩阵的压缩存储的描述。2.1 线性表的基本概念线性表的基本概念2.2 线性表的顺序存储结构及其算法线性表的顺序存储结构及其算法2.3 线性表的链式存储结构及其运算线性表的链式存储结构及其运算2.4 算法应

2、用举例算法应用举例2.5 数组数组第第2章章 线性表线性表2.1 线性表的基本概念线性表的基本概念 线性表是一种最简单、最基本的数据结构，它的线性表是一种最简单、最基本的数据结构，它的使用非常广泛。这种数据结构的数据元素之间是一对使用非常广泛。这种数据结构的数据元素之间是一对一的关系，即线性关系，故称为线性表。一的关系，即线性关系，故称为线性表。2.1.1 线性表的定义线性表的定义线性表（线性表（linear list）是由）是由 n个数据元素组成的个数据元素组成的有限序列有限序列线性表可以用一个标识符来命名，如果用线性表可以用一个标识符来命名，如果用A来表示线性来表示线性表，则表，则:A=（

3、a1 ，a2 ，ai ，an ）线性表是一种非常典型的线性结构，用二元组可以表线性表是一种非常典型的线性结构，用二元组可以表示成示成:S=（D，R）D=a1，a2，ai，an R=,在线性表中，有且仅有一个开始结点，或称表头结在线性表中，有且仅有一个开始结点，或称表头结点点a1，没有直接前驱，只有一个直接后继，没有直接前驱，只有一个直接后继;有且仅有有且仅有一个终端结点，或称表尾结点一个终端结点，或称表尾结点an，它没有直接后继，它没有直接后继，只有一个直接前驱只有一个直接前驱;其他结点其他结点ai（当（当1 i data。（2）修改有关结点的指针域。修改有关结点的指针域。3.单链表上的插入运

4、算单链表上的插入运算2.3 线性表的链式存储结构及其运算线性表的链式存储结构及其运算3.单链表上的插入运算单链表上的插入运算2.3 线性表的链式存储结构及其运算线性表的链式存储结构及其运算q-data=x;q-next=p-next;p-next=q;4.单链表上的删除运算单链表上的删除运算 删除单向链表中的结点删除单向链表中的结点x，并由系统收回其占用的存储，并由系统收回其占用的存储空间，其过程如下空间，其过程如下:（1）设定两个指针设定两个指针p和和q，p指针指向被删除结点，指针指向被删除结点，q为跟为跟踪指针，踪指针，指向被删除结点的直接前驱结点指向被删除结点的直接前驱结点。（2）p从表

5、头指针从表头指针 head 指向的第一个结点开始依次向后指向的第一个结点开始依次向后搜索。当搜索。当p data 等于等于x时，被删除结点找到。时，被删除结点找到。（3）修改）修改p的前驱结点的前驱结点q的指针域。使的指针域。使p结点被删除，然后结点被删除，然后释放存储空间。释放存储空间。2.3 线性表的链式存储结构及其运算线性表的链式存储结构及其运算4.单链表上的删除运算单链表上的删除运算2.3 线性表的链式存储结构及其运算线性表的链式存储结构及其运算q-next=p-next;free(p);5.输出单链表输出单链表若要将单链表按其逻辑顺序输出，就必须从若要将单链表按其逻辑顺序输出，就必须

6、从头到尾访问单链表中的每一个结点。头到尾访问单链表中的每一个结点。2.3 线性表的链式存储结构及其运算线性表的链式存储结构及其运算如果将单链表最后一个结点的指针指向头结点，使链如果将单链表最后一个结点的指针指向头结点，使链表形成一个环形，此链表就称为表形成一个环形，此链表就称为循环链表（循环链表（Circular Link List）。）。2.3 线性表的链式存储结构及其运算线性表的链式存储结构及其运算2.3.3 循环链表结构循环链表结构循环链表中，循环链表中，*p是最后一个结点的判断条件：是最后一个结点的判断条件：p-next=head在循环链表中，可以从表中任一结点出发找到在循环链表中，可

7、以从表中任一结点出发找到它的直接前驱，而不必从它的直接前驱，而不必从head出发。出发。2.3 线性表的链式存储结构及其运算线性表的链式存储结构及其运算2.3.3 循环链表结构循环链表结构1.双向链表的基本概念双向链表的基本概念 在循环链表的结点中再增加一个指针域，在循环链表的结点中再增加一个指针域，这个指针直接指向该结点的直接前驱。这样，这个指针直接指向该结点的直接前驱。这样，链表中一个结点就有了两个指针域，我们把这链表中一个结点就有了两个指针域，我们把这样的链表称样的链表称为双向链表为双向链表。2.3 线性表的链式存储结构及其运算线性表的链式存储结构及其运算2.3.4 双向链表双向链表结构

8、结构如果每条链都构成一个循环链表，则称这样如果每条链都构成一个循环链表，则称这样的链表为的链表为双向循环链表双向循环链表。2.3 线性表的链式存储结构及其运算线性表的链式存储结构及其运算双向链表的重要特点：双向链表的重要特点：2.3 线性表的链式存储结构及其运算线性表的链式存储结构及其运算(p-next)-prior=p=(p-prior)-nextpriorpnextprior a2nextprior a1nextp-next(p-next)-priorp-prior(p-prior)-next2.插入运算插入运算在双向链表的在双向链表的p结点之后插入新结点结点之后插入新结点q。2.3 线性

9、表的链式存储结构及其运算线性表的链式存储结构及其运算q-prior=p;q-next=p-next;(p-next)-prior=q;p-next=q;3.删除运算删除运算将双向链表中的将双向链表中的 p 结点删除。结点删除。2.3 线性表的链式存储结构及其运算线性表的链式存储结构及其运算(p-prior)-next=p-next;(p-next)-prior=p-prior;free(p);例例2.1 有两个线性表有两个线性表A和和B，都是循环链表存储结构，都是循环链表存储结构，两个链表头指针分别为两个链表头指针分别为 head1和和head2，将，将B链表链表链接到链接到A链表的后面，链表

10、的后面，合并成一个链表。合并成一个链表。2.4 算法应用举例算法应用举例2.4 算法应用举例算法应用举例找到两个找到两个链表的最后链表的最后一个结点一个结点 p-next=head2-next q-next=head1free(head2)数组是线性表的推广，也是一种常用的数据结构。数组是线性表的推广，也是一种常用的数据结构。数组是由一组具有相同特性的数据元素组成的。数组是由一组具有相同特性的数据元素组成的。数据元素在数组中的相对位置是由其下标来确定的。数据元素在数组中的相对位置是由其下标来确定的。一旦定义了数组，它的维数和元素数目也就确定了，一旦定义了数组，它的维数和元素数目也就确定了，而且

11、数据元素的下标具有上下界约束关系，并且是有而且数据元素的下标具有上下界约束关系，并且是有序的。序的。2.5 数组数组2.5.1 数组的定义数组的定义通常数组采用的是通常数组采用的是顺序存储结构顺序存储结构，即把数组元素，即把数组元素顺序地存放在一片地址连续的存储单元中。顺序地存放在一片地址连续的存储单元中。对于二维数组来说，有两种存储方式，一种是对于二维数组来说，有两种存储方式，一种是以以行为主顺序行为主顺序的存储方式的存储方式，即先存储第一行，再存储第，即先存储第一行，再存储第二行，以此类推，每一行元素从左向右顺序存储；另二行，以此类推，每一行元素从左向右顺序存储；另一种是一种是以列为主顺序

12、以列为主顺序的存储方式，即先存储第一列，的存储方式，即先存储第一列，再存储第二列，以此类推，每一列的元素从上到下顺再存储第二列，以此类推，每一列的元素从上到下顺序存储。序存储。2.5 数组数组2.5.2 数组的顺序存储结构数组的顺序存储结构例如，如下的二维数组例如，如下的二维数组a32。2.5 数组数组 a11 a12a32=a21 a22 a31 a32a11a12a21a22a31a32以以行行为主顺序为主顺序a11a21a31a12a22a32以以列列为主顺序为主顺序二维数组存储地址的计算与一维数组存储地址的二维数组存储地址的计算与一维数组存储地址的计算类似。假设给定二维数组计算类似。假

13、设给定二维数组amn 按行为主按行为主顺序顺序存储，则数组中任一元素存储，则数组中任一元素aij 的存储地址计算公式为的存储地址计算公式为 2.5 数组数组LOC(aij)=LOC(a11)+(i-1)n+j-1)L第一个元素第一个元素a11的存储位置的存储位置假设给定二维数组假设给定二维数组amn 按列为主按列为主顺序存储，顺序存储，则数组中任一元素则数组中任一元素aij 的存储地址计算公式？的存储地址计算公式？2.5 数组数组LOC(aij)=LOC(a11)+(j-1)m+i-1)L思思 考考一般将要压缩存储的矩阵分成特殊矩阵和稀疏矩阵。一般将要压缩存储的矩阵分成特殊矩阵和稀疏矩阵。具有

14、相同值的元素和非零元素有一定分布规律的矩阵，具有相同值的元素和非零元素有一定分布规律的矩阵，称为称为特殊矩阵特殊矩阵，如三角矩阵、带状矩阵等。，如三角矩阵、带状矩阵等。零元素远远多于非零元素，并且非零元素的分布没有规零元素远远多于非零元素，并且非零元素的分布没有规律的矩阵称为律的矩阵称为稀疏矩阵稀疏矩阵。2.5 数组数组2.5.3 矩阵的压缩存储矩阵的压缩存储1.三角矩阵三角矩阵以对角线划分，三角矩阵有上三角和下三角两种。以对角线划分，三角矩阵有上三角和下三角两种。下三角矩阵中的任一非零元素下三角矩阵中的任一非零元素aij（ij）的下标和一维）的下标和一维数组数组A的下标的下标K有一个惟一的对

15、应关系，即有一个惟一的对应关系，即 K=i*(i 1)/2+j对于对于n阶上三角矩阵，也可以用类似下三角矩阵的方阶上三角矩阵，也可以用类似下三角矩阵的方法存储，其非零元素和一维数组法存储，其非零元素和一维数组A的下标的下标K的对应关系为的对应关系为:K=(i 1)*n-(i 1)(i 2)/2+(j i+1)2.5 数组数组2.稀疏矩阵稀疏矩阵稀疏矩阵一般都采用压缩存储的方法来存储矩阵稀疏矩阵一般都采用压缩存储的方法来存储矩阵中的元素。中的元素。有两种常用的存储稀疏矩阵的方法有两种常用的存储稀疏矩阵的方法:三元组表法和三元组表法和十字链表法。十字链表法。2.5 数组数组【三元组表法定义三元组表

16、法定义】在压缩存放稀疏矩阵的非零元素时，在压缩存放稀疏矩阵的非零元素时，还要存放此非零元素所在的行号和列号，这种存储方法称还要存放此非零元素所在的行号和列号，这种存储方法称为三元组表法。为三元组表法。它是一种它是一种顺序存储顺序存储，按行优先按行优先顺序存放。一个非零元素顺序存放。一个非零元素有行号、列号和值，为一个三元组。整个稀疏矩阵中非零有行号、列号和值，为一个三元组。整个稀疏矩阵中非零元素的三元组的整体称为三元组表。元素的三元组的整体称为三元组表。2.稀疏矩阵三元组稀疏矩阵三元组2.5 数组数组5 0 0 0 85 0 0 0 80 0 7 0 00 0 7 0 00 0 0 0 00

17、0 0 0 00 3 0 0 00 3 0 0 00 0 0 0 00 0 0 0 07 0 0 9 07 0 0 9 0A=1 11 15 51 15 58 82 23 37 74 42 23 36 61 17 76 64 49 9（a a）稀疏矩阵（b b）三元组表）三元组表图图2.23 2.23 稀疏矩阵的三元组表示稀疏矩阵的三元组表示 row col val2.稀疏矩阵三元组稀疏矩阵三元组2.5 数组数组图图2.24 十字链表的结点结构十字链表的结点结构2.稀疏矩阵十字链表法稀疏矩阵十字链表法2.5 数组 行域行域 列域列域 值域值域 row col val down right 十字

18、链表是稀疏矩阵的十字链表是稀疏矩阵的链式存储链式存储结构。结构。用十字链表作稀疏矩阵存储结构时，每用十字链表作稀疏矩阵存储结构时，每个结点除了存储元素值外，还要存储该非零个结点除了存储元素值外，还要存储该非零元素的行、列的下标和两个指针。元素的行、列的下标和两个指针。图2.23（a）中的稀疏矩阵A对应的十字链表如图2.25所示。用十字链表作稀疏矩阵存储结构时，每个结点除了存储元素值外，还要存储该非零元素的行、列的下标和两个指针。另外还要增设行、列链表表头指针数组。所以只有在矩阵中非零元素少于一定数量时采用十字链表才可能节约存储空间。图图2.25 稀疏矩阵的十字链表稀疏矩阵的十字链表请分别用三元

19、组表和十字链表表示如下矩阵：请分别用三元组表和十字链表表示如下矩阵：0 12 9 0 0 0 0 0 0 0 0 0 0 0 -3 0 0 0 0 14 0 0 0 24 0 0 0 0 0 18 0 0 0 0 0 15 0 0 -7 0 0 0练 习M=三元组表三元组表1 12 212121 13 39 93 31 1-3-33 36 614144 43 324245 52 218186 61 115156 64 4-7-7 row col val十字链表十字链表1.线性表是一种具有一对一的线性关系的特殊数据结构。线性表是一种具有一对一的线性关系的特殊数据结构。线线性表有两种存储方法性表有

20、两种存储方法:用顺序存储方法来表示这种线性关系，用顺序存储方法来表示这种线性关系，得到顺序存储结构（即顺序表）得到顺序存储结构（即顺序表）;用链式存储方式来表示这用链式存储方式来表示这种线性关系，得到线性表的链式存储结构（即链表）。种线性关系，得到线性表的链式存储结构（即链表）。2.线性表的链式存储结构，是通过结点之间的链接而得到的，线性表的链式存储结构，是通过结点之间的链接而得到的，链式存储结构有单链表、双向链表和循环链表等。链式存储结构有单链表、双向链表和循环链表等。3.单链表结点至少有两个域单链表结点至少有两个域:一个数据域和一个指针域。双向一个数据域和一个指针域。双向链表结点至少含有三

21、个域链表结点至少含有三个域:一个数据域和两个指针域。一个数据域和两个指针域。本章小结本章小结4.循环链表不存在空指针，最后一个结点的指针指向表头，循环链表不存在空指针，最后一个结点的指针指向表头，形成一个首尾相接的环。形成一个首尾相接的环。5.为了处理问题方便，在链表中增加一个头结点。为了处理问题方便，在链表中增加一个头结点。6.顺序存储可以提高存储单元的利用率，不便于插入和删除顺序存储可以提高存储单元的利用率，不便于插入和删除运算。链式存储会占用较多的存储空间，可以使用不连续的运算。链式存储会占用较多的存储空间，可以使用不连续的存储单元，插入、删除运算较方便。存储单元，插入、删除运算较方便。本章小结本章小结