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

第2章线性表,第2章线性表,学习目的要求:,线性表的定义和线性表的特征。线性表的顺序存储结构及其算法的实现。线性链表的描述及其算法的实现。循环链表和双向循环链表的描述。数组的顺序存储和矩阵的压缩存储的描述。,2.1线性表的基本概念,2.2线性表的顺序存储结构及其算法,2.3线性表的链式存储结构及其运算,2.4算法应用举例,2.5数组,第2章线性表,2.1线性表的基本概念,线性表是一种最简单、最基本的数据结构，它的使用非常广泛。这种数据结构的数据元素之间是一对一的关系，即线性关系，故称为线性表。,2.1.1线性表的定义,线性表（linearlist）是由n个数据元素组成的有限序列,线性表可以用一个标识符来命名，如果用A来表示线性表，则:A=（a1，a2，ai，an）,线性表是一种非常典型的线性结构，用二元组可以表示成:S=（D，R）D=a1，a2，ai，anR=,在线性表中，有且仅有一个开始结点，或称表头结点a1，没有直接前驱，只有一个直接后继;有且仅有一个终端结点，或称表尾结点an，它没有直接后继，只有一个直接前驱;其他结点ai（当1data=x;q-next=p-next;p-next=q;,4.单链表上的删除运算,删除单向链表中的结点x，并由系统收回其占用的存储空间，其过程如下:（1）设定两个指针p和q，p指针指向被删除结点，q为跟踪指针，指向被删除结点的直接前驱结点。（2）p从表头指针head指向的第一个结点开始依次向后搜索。当pdata等于x时，被删除结点找到。（3）修改p的前驱结点q的指针域。使p结点被删除，然后释放存储空间。,2.3线性表的链式存储结构及其运算,4.单链表上的删除运算,2.3线性表的链式存储结构及其运算,q-next=p-next;free(p);,5.输出单链表,若要将单链表按其逻辑顺序输出，就必须从头到尾访问单链表中的每一个结点。,2.3线性表的链式存储结构及其运算,如果将单链表最后一个结点的指针指向头结点，使链表形成一个环形，此链表就称为循环链表（CircularLinkList）。,2.3线性表的链式存储结构及其运算,2.3.3循环链表结构,循环链表中，*p是最后一个结点的判断条件：p-next=head在循环链表中，可以从表中任一结点出发找到它的直接前驱，而不必从head出发。,2.3线性表的链式存储结构及其运算,2.3.3循环链表结构,1.双向链表的基本概念,在循环链表的结点中再增加一个指针域，这个指针直接指向该结点的直接前驱。这样，链表中一个结点就有了两个指针域，我们把这样的链表称为双向链表。,2.3线性表的链式存储结构及其运算,2.3.4双向链表结构,如果每条链都构成一个循环链表，则称这样的链表为双向循环链表。,2.3线性表的链式存储结构及其运算,双向链表的重要特点：,2.3线性表的链式存储结构及其运算,(p-next)-prior=p=(p-prior)-next,p-next,(p-next)-prior,p-prior,(p-prior)-next,2.插入运算,在双向链表的p结点之后插入新结点q。,2.3线性表的链式存储结构及其运算,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链表的后面，合并成一个链表。,2.4算法应用举例,2.4算法应用举例,找到两个链表的最后一个结点,p-next=head2-next,q-next=head1,free(head2),例2.2一元多项式的加法运算。设有两个一元多项式分别为:An（x）=a0+a1x+a2x2+anxnBm（x）=b0+b1x+b2x2+bmxm,多项式中每个非零项的系数用一个结点来表示，结点中含有两个数据域和一个指针域，两个数据域分别存放非零项的系数和指数。,typedefstructpnodeintcoef;/*系数以整型为例*/intexp;/*指数*/structpnode*next;PNODE;,2.4算法应用举例,设有多项式A（x）=1+2x+4x3（1）B（x）=2-2x+3x2（2）,2.4算法应用举例,多项式（1）加多项式（2）的和为多项式（3）:R（x）=3+3x2+4x3（3）,2.4算法应用举例,=,x!=0,系数相加(x),1、p结点的系数域存放x的值2、s后移，p后移3、u=q4、q重新赋值为u的直接后继结点5、释放u,1、s后移2、p后移,1、u指向q的直接后继结点2、将q的直接后继设为p3、将s的直接后继设置为q4、s后移到q5、q后移到u,否,是,是,否,是,否,指数比较，分相等、大于、小于三种情况,1、s指向p的下一个结点2、释放p3、p重新赋值为s的直接后继结点4、u=q5、q重新赋值为u的直接后继结点6、释放u,2.4算法应用举例,指数相等，系数相加不为0时：,A（x）=1+2x+4x3,B（x）=2-2x+3x2,2,0,next,0,next,s,p,q,p-coef=x;,x:1+2=3,1,2.4算法应用举例,指数相等，系数相加不为0时：,A（x）=1+2x+4x3,B（x）=2-2x+3x2,2,0,next,3,0,next,s,p,q,p-coef=x;,x:1+2=3,s=p;,s,p,p=s-next;,u=q;,u,q=q-next;,q,2.4算法应用举例,指数相等，系数相加不为0时：,A（x）=1+2x+4x3,B（x）=2-2x+3x2,3,0,next,p-coef=x;,x:1+2=3,s=p;,s,p,p=s-next;,u=q;,q=q-next;,q,free(u);,2.4算法应用举例,指数相等，系数相加为0时：,A（x）=1+2x+4x3,B（x）=2-2x+3x2,-2,1,next,s,q,s-next=p-next;,x:2-2=0,free(p);,p,p=s-next;,u=q;,q=q-next;,free(u);,u,q,2.4算法应用举例,指数相等，系数相加为0时：,A（x）=1+2x+4x3,B（x）=2-2x+3x2,s-next=p-next;,x:2-2=0,free(p);,p,p=s-next;,u=q;,q=q-next;,free(u);,q,s,2.4算法应用举例,A多项式中某项指数大于时：,A（x）=1+2x+4x3,B（x）=2-2x+3x2,3,2,next,s,q,u=q-next;,q-next=p;,s-next=q;,s=q;,q=u;,u,指数:32,s,q,数组是线性表的推广，也是一种常用的数据结构。,数组是由一组具有相同特性的数据元素组成的。,数据元素在数组中的相对位置是由其下标来确定的。,一旦定义了数组，它的维数和元素数目也就确定了，而且数据元素的下标具有上下界约束关系，并且是有序的。,2.5数组,2.5.1数组的定义,通常数组采用的是顺序存储结构，即把数组元素顺序地存放在一片地址连续的存储单元中。,对于二维数组来说，有两种存储方式，一种是以行为主顺序的存储方式，即先存储第一行，再存储第二行，以此类推，每一行元素从左向右顺序存储；另一种是以列为主顺序的存储方式，即先存储第一列，再存储第二列，以此类推，每一列的元素从上到下顺序存储。,2.5数组,2.5.2数组的顺序存储结构,例如，如下的二维数组a32。,2.5数组,以行为主顺序,以列为主顺序,二维数组存储地址的计算与一维数组存储地址的计算类似。假设给定二维数组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,思考,一般将要压缩存储的矩阵分成特殊矩阵和稀疏矩阵。,具有相同值的元素和非零元素有一定分布规律的矩阵，称为特殊矩阵，如三角矩阵、带状矩阵等。零元素远远多于非零元素，并且非零元素的分布没有规律的矩阵称为稀疏矩阵。,2.5数组,2.5.3矩阵的压缩存储,1.三角矩阵,以对角线划分，三角矩阵有上三角和下三角两种。,下三角矩阵中的任一非零元素aij（ij）的下标和一维数组A的下标K有一个惟一的对应关系，即K=i*(i1)/2+j对于n阶上三角矩阵，也可以用类似下三角矩阵的方法存储，其非零元素和一维数组A的下标K的对应关系为:K=(i1)*n-(i1)(i2)/2+(ji+1),2.5数组,2.稀疏矩阵,稀疏矩阵一般都采用压缩存储的方法来存储矩阵中的元素。有两种常用的存储稀疏矩阵的方法:三元组表法和十字链表法。,2.5数组,【三元组表法定义】在压缩存放稀疏矩阵的非零元素时，还要存放此非零元素所在的行号和列号，这种存储方法称为三元组表法。它是一种顺序存储，按行优先顺序存放。一个非零元素有行号、列号和值，为一个三元组。整个稀疏矩阵中非零元素的三元组的整体称为三元组表。,2.稀疏矩阵三元组,2.5数组,500080070000000030000000070090,A=,（a）稀疏矩阵,（b）三元组表,图2.23稀疏矩阵的三元组表示,rowcolval,2.稀疏矩阵三元组,2.5数组,图2.24十字链表的结点结构,2.稀疏矩阵十字链表法,2.5数组,十字链表是稀疏矩阵的链式存储结构。用十字链表作稀疏矩阵存储结构时，每个结点除了存储元素值外，还要存储该非零元素的行、列的下标和两个指针。,图2.23（a）中的稀疏矩阵A对应的十字链表如图2.25所示。用十字链表作稀疏矩阵存储结构时，每个结点除了存储元素值外，还要存储该非零元素的行、列的下标和两个指针。另外还要增设行、列链表表头指针数组。所以只有在矩阵中非零元素少于一定数量时采用十字链表才可能节约存储空间。,图2.25稀疏矩阵的十字链表,在链表中，每个非零元素可用一个含5个域的结点表示，其中row、col和val分别表示该非零元素所在行、列和值，向右域right用以链接稀疏矩阵同一行中的非零元素，向下域down用以链接稀疏矩阵同一列中下一个非零元素。同一行的非零元素通过right域链接成一个线性链表，同一列的非零元素通过down域链成一个线性链表，每个非零元素既是某个行链表中的一个结点，又是某个列链表中的一个结点。整个稀疏矩阵构成一个十字交叉链表，故称这样的存储结构为十字链表。,2.5数组,请分别用三元组表和十字链表表示如下矩阵：012900000000000-3000014000240000018000001500-7000,练习,M=,三元组表,rowcolval,十字链表,线性表是一种具有一对一的线性关系的特殊数据结构。线性表有两种存储方法:用顺序存储方法来表示这种线性关系，得到顺序存储结构（即顺序表）;用链式存储方式来表示这种线性关系，得到线性表的链式存储结构