数据结构课件-DS05-数组与广义表

第五章数组数组的类型定义和表示方法特殊矩阵和稀疏矩阵存储方法及运算的实现广义表的结构特点第五章数组数组的类型定义和表示方法15.1.1二维数组的定义定义数组特点数组结构固定数据元素同构数组运算给定一组下标，存取相应的数据元素给定一组下标，修改数据元素的值()()()()()()()()()数组是一组有固定（一旦定义了数组的维数和每一维的上下限个数）的元素的集合。由于这个性质，使得对数组的操作不像对线性表的操作那样可以在表中任意一个合法的位置插入或删除一个元素。对于数组的操作一般只有两类：数组可以看成是一种特殊的线性表，即线性表中数据元素本身也是一个线性表5.1.1二维数组的定义数组特点(2矩阵Am×n看成n个列向量的线性表

矩阵Am×n看成n个列向量的线性表3矩阵Am×n看成m个行向量的线性表矩阵Am×n看成m个行向量的线性表45.1.2数组的顺序存储结构次序约定以行序为主序以列序为主序

a11a12……..a1n

a21a22……..a2n

am1am2……..amn

…………….Loc(aij)=Loc(a11)+[(i-1)n+(j-1)]*l

按行序为主序存放amn

…….

am2

am1……a2n…..

a22a21a1n

……a12

a1101n-1m*n-1n

二维数组按列序为主序存放（下标从1开始）01m-1m*n-1m

amn

……..

a2n

a1n……….am2……..

a22a12am1

…….a21

a11

a11

a12

……..

a1n

a21

a22……..

a2n

am1

am2

……..amn

….Loc(aij)=Loc(a11)+[(j-1)*m+(i-1)]*L

L为每一个数组元素所占的存储单元个数5.1.2数组的顺序存储结构a15

二维数组三维数组行向量下标i页向量下标i列向量下标j行向量下标j

列向量下标k共有120个元素三维数组的逻辑结构图下标从0开始页行列二维数组三维数组行向6三维数组(下标从0开始)

各维元素个数为

m1,m2,m3下标为i1,i2,i3的数组元素的存储地址：（按页/行/列存放）LOC(i1,i2,i3)=a+(i1*m2*m3+i2*m3+i3

)*l

前i1页总元素个数第i1页的前i2行总元素个数三维数组(下标从0开始)各维元素个数为m1,m2,7

n维数组

各维元素个数为

m1,m2,m3,…,mn下标为i1,i2,i3,…,in的数组元素的存储地址：

LOC(i1,i2,…,in)=a+(i1*m2*m3*…*mn+i2*m3*m4*…*mn++……+in-1*mn+in

)*l

n维数组各维元素个数为m1,m2,m3,…,8对称阵下三角矩阵5.2.1特殊矩阵为节约存储，只存对角线及对角线以上的元素，或者只存对角线及对角线以下的元素。前者称为上三角矩阵，后者称为下三角矩阵。对称阵下三角矩阵5.2.1特殊矩阵为节约存储，只存对角线及9对称阵的上三角矩阵把它们按行存放于一个一维数组B中，称之为对称矩阵A的压缩存储方式。数组B共有n+(n-1)++1=

n*(n+1)/2

个元素。A=对称阵的上三角矩阵把它们按行存放于一个一维数组B中，称之10对称矩阵的存储在矩阵中，aij

=aji012345678n(n+1)/2-1Ba00a10a11a20a21a22a30a31a32……an-1n-1

存下三角对称矩阵的存储在矩阵中，aij=aji0111若i<j，数组元素A[i][j]在矩阵的上三角部分,在数组B中没有存放，可以找它的对称元素A[j][i]=j*(j+1)/2+i

若

i

j,数组元素A[i][j]在数组B中的存放位置为1+2++i+j=(i+1)*i/2+j前i行元素总数第i行第j个元素前元素个数若已知某矩阵元素位于数组B的第k个位置，可寻找满足

i(i+1)/2k<(i+1)*(i+2)/2的

i,此即为该元素的行号。

j=k

-i*(i+1)/2此即为该元素的列号。例，当k=8,3*4/2=6k

<4*5/2=10,取i=3。则j=8-3*4/2=2。若i<j，数组元素A[i][j]在矩阵的上三角部12上三角矩阵Ba00a01a02a03a11a12a13a22a23

a33

0123456789若i

j，数组元素A[i][j]在数组B中的存放位置为n+(n-1)+(n-2)++(n-i+1)+j-i前i行元素总数第i行第j个元素前元素个数n=4上三角矩阵Ba00a01a02a03a113

若

ij，数组元素A[i][j]在数组B中的存放位置为

n+(n-1)+(n-2)++(n-i+1)+j-i==(2*n-i+1)*i/2+j-i==

(2*n-i-1)*i/2+j

若i>j，数组元素A[i][j]在矩阵的下三角部分，在数组B中没有存放。因此，找它的对称元素A[j][i]。

A[j][i]在数组B的第

(2*n-j-1)*j/2+i

的位置中找到。对于上三角矩阵若ij，数组元素A[i][j]在数组B中的存14三角矩阵

a11

00

……..0

a21a22

0

……..0

an1an2an3……..ann

….0Loc(aij)=Loc(a11)+[(+(j-1)]*L

i(i-1)2a11a21a22a31a32an1ann

…...…...k=01234n(n-1)/2n(n+1)/2-1按行序为主序：j>i时aij为0一个元素所占字节数下标从1开始三角矩阵a11015三对角矩阵的压缩存储Ba00a01a10a11a12a21a22a23…

an-1n-2an-1n-1

012345678910对角阵的下标从0起存放对角阵元素的一维数组的下标从0起三对角矩阵的压缩存储Ba00a01a10a116三对角矩阵中除主对角线及在主对角线上下最临近的两条对角线上的元素外，所有其它元素均为0。总共有2+3(n-2)+2=3n-2个非零元素。将三对角矩阵A中三条对角线上的元素按行存放在一维数组B中，且a00存放于B[0]。在三条对角线上的元素aij

满足

0

i

n-1,i-1

j

i+1在一维数组B中A[i][j]在第i行，它前面有3*i-1个非零元素,在本行中第j列前面有j-i+1个，所以元素A[i][j]在B中位置为

k=2*i+j三对角矩阵中除主对角线及在主对角线上下最临近的两条对角线上的17若已知三对角矩阵中某元素

A[i][j]

在数组B[]存放于第

k

个位置，则有

i=(k+1)/3

j=k

-2*i例如，当k=8时，

i=(8+1)/3=3,j=8-2*3=2

当k=10时，

i=(10+1)/3=3,j=10-2*3=4不若已知三对角矩阵中某元素A[i][j]在数组B[]18对角矩阵(这是三对角阵，如是K对角则要求K是奇数)

a11

a120

…………….0

a21

a22

a23

0

……………00

0

…an-1,n-2an-1,n-1

an-1,n0

0

……an,n-1ann.

0

a32a33

a34

0

………0……………Loc(aij)=Loc(a11)+[2(i-1)+(j-1)]*L

a11a12a21a22a23ann-1ann

…...…...k=01234n(n-1)/2n(n+1)/2-1按行序为主序：对角阵的下标从1起存放对角阵元素的一维数组的下标从0起对角矩阵(这是三对角阵，如是K对角则要求K是奇数)195.2.2稀疏矩阵定义：非零元较零元少，且分布没有一定规律的矩阵压缩存储原则：只存矩阵的行列维数和每个非零元的行列下标及其值5.2.2稀疏矩阵定义：非零元较零元少，且分布没有一定规20M由{(1,2,12),(1,3,9),(3,1,-3),(3,6,14),(4,3,24),(5,2,18),(6,1,15),(6,4,-7)}和矩阵维数（6,7,8）唯一确定例如：M由{(1,2,12),(1,3,9),(3,1,-3)21稀疏矩阵的压缩存储方法顺序存储结构三元组表#defineM20typedefstructnode

/*三元组表中元素类型*/{inti,j;

/*非零元所在行号和列号*/

intv;

/*非零元素值*/}TriTupleNode;TriTupleNodema[M];maijv012345678稀疏矩阵的压缩存储方法#defineM20m22maijv0123456786

7

8

121213931-3361443245218611564-7maijv01223求转置矩阵问题描述：已知一个稀疏矩阵的三元组表，求该矩阵转置矩阵的三元组表问题分析一般矩阵转置算法：for(col=0;col<n;col++)for(row=0;row<m;row++)B[col][row]=A[row][col];时间复杂度：T(n)=O(mn)求转置矩阵for(col=0;col<n;col++)246

7

8

121213931-3361443245218611564-7ijv012345678maijv7

6

8

13-3161521122518319342446-76314012345678mb?按行序存放6781225解决思路：只要做到

将矩阵行、列维数互换将每个三元组中的i和j相互调换重排三元组次序，使mb中元素以B的行(A的列)为主序算法描述：算法分析：T(n)=O(A的列数n非零元个数t)若t与mn同数量级，则方法一：按原矩阵A的列序转置,来得到A的转置矩阵B

因为在ma是阵A的按行优先存放的三元组表，要想从ma得到mb。即按mb中三元组次序依次在ma中找到相应的三元组进行转置。为找到A中每一列所有非零元素，需对其三元组表ma从第一个元素起扫描一遍。由于ma中以A行序为主序,所以由此得到的恰是mb中应有的顺序解决思路：只要做到算法描述：算法分析：T(n)=O(A的列数26由于我们已按行优先将阵A中的非零元存储到三元组表ma中了，现在的问题就是如何由ma得到mb！

思路是：按ma中三元组次序转置，转置结果放入mb中恰当位置。此法关键是要预先确定原矩阵A中每一列第一个非零元在mb中位置，为确定这些位置，转置前应先求得A的每一列中非零元个数。方法二：按行序转置（快速转置）即如何得到阵A的按列优先排列的非零元三元组表mb?由于我们已按行优先将阵A中的非零元存储到三元27实现：设两个数组num[col]：表示矩阵A中第col列中非零元个数cpot[col]：指示A中第col列第一个非零元在mb中的位置显然有：cpot[1]=1;cpot[col]=cpot[col-1]+num[col-1];(2colma[0].j)1357889colnum[col]cpot[col]12223241506170矩阵A的列数实现：设两个数组cpot[1]=1;1357889colnu28算法描述：算法分析：T(n)=O(A的列数n+非零元个数t)若t与mn同数量级，则T(n)=O(mn)算法描述：算法分析：T(n)=O(A的列数n+非零元个数t)296

7

8

121213931-3361443245218611564-7ijv012345678maijv012345678mbcolnum[col]cpot[col]1122323524715806817907

6

8

13-3161521122518319342446-76314pppppppp46297536781230

7000150

0-40000

-2000021

000-100A=22-4∧∧1515∧∧41-2∧4621∧∧11734-1∧∧^ijedownright希疏矩阵的链式存储结构7000315.3广义表

广义表(Lists)也称为列表，它是线性表的推广。大家知道，线性表是n（n≥0）个元素a1，a2，…，ai，…，an的有限序列。其中，线性表的元素仅限于原子项，所谓原子，指的是结构上不可再分割的一种成分，它可以是一个数，或者是一个结构。如果放松对线性表元素的这种限制，允许它们具有其自身独立的类型结构，那么就产生了广义表的概念。5.3广义表广义表(Lists)也称为列表，它是线32广义表是n(0)个表元素组成的有限序列，记作

LS=(a0,a1,a2,…,an-1)

LS是表名，ai是表元素，它可以是表(称为子表)，可以是数据元素(称为原子)。

n为表的长度。n=0的广义表为空表。n>0时，表的第一个表元素称为广义表的表头(head)，除此之外，其它表元素组成的表称为广义表的表尾(tail)。广义表是n(0)个表元素组成的有33

广义表通常用圆括号括起来，用逗号分隔其中的元素。为区分原子和广义表，用大写字母表示广义表，用小写字母表示原子。表尾一定是子表。但表头可以是原子，也可以是子表。广义表是递归定义的，因为在定义广义表时又用到了广义表的概念。需要注意的是：广义表通常用圆括号括起来，用逗号分隔其中的元素。需要注意34广义表是一个多层次的线性结构。例如:有A、B、C、D、E五个广义表的描述如下：A=

()A是一个空表,它的长度为零B=(e)列表B只有一个原子e,B的长度为1.C=(a,(b,c,d))列表C的长度为2,两个元素分别为原子a和子表(b,c,d)D=(A,B,C)列表D的长度为3,三个元素都是列表,显然,将子表的值代入后,则有D=((),(e),(a,(b,c,d)))E=(a,E)这是一个递归的表,它的长度为2,E相当于一个无限的列表E=(a,(a,(a,...)))广义表是一个多层次的线性结构。例如:有A、B、C、D、E五个351)广义表中的数据元素有相对次序;2)广义表的长度定义为最外层包含的元素个数;3)广义表的深度定义为所含括弧的重数;

注意:“原子”的深度为“0”;“空表”的深度为14)表头可以是原子或列表;表尾必定是列表。5)广义表可以是一个递归的表;递归表的深度是无穷值，长度是有限值。广义表的结构特点:1)广义表中的数据元素有相对次序;广义表的结构特点:366)任何一个非空广义表

LS=(1,2,…,n)均可分解为

表头Head(LS)=1

表尾Tail(LS)=(2,…,n)两部分6)任何一个非空广义表37例如：Head(((b,c)))=(b,c)Tail(((b,c)))=()Head(a,(b,c))=aTail(a,(b,c))=((b,c))Head((c))=(c)Tail((c))=()求出的表头是原样，而求出的表尾要再加上一对园括号才为所求例如：38Head(LS)=ATail(LS)=(D)Head(D)=ETail(D)=(F)Head(E)=aTail(E)=((b,c))Head(((b,c)))=(b,c)Tail(((b,c)))=()Head((b,c))=bTail((b,c))=(c)LS=(A,D)=((),(E,F))=((),(a,(b,c))，F)例如：Head(LS)=ATail39

广义表还可以用图形来形象的表示，下图给出了几个广义表的图形表示，其中的分支结点对应广义表，非分支结点（即叶子）对应原子或者空表。递归表线性表再入表广义表还可以用图形来形象的表示，下图给出了几个广义表的图40与树对应的广义表称为纯表（PureList），这种表中没有共享和递归的成分，即没有任何成分出现多次，它限制了表中成分的共享和递归，例如图中的(a)，(b)，(c)都是纯表；与有向无环图对应的表称为再入表，这种表存在元素共享，在图中表现为存在结点共享，例如图中(d)，子表A是共享结点，它既是C的一个元素，又是子表B的元素；与有回路的有向图对应的表称为递归表，这种表的某个成员内含有广义表自己，例如图(e)中，表D是其自身的子表。与树对应的广义表称为纯表（PureList），这种表中没有41各种表之间的关系满足：递归表再入表纯表线性表各种表之间的关系满足：42广义表的表示只包括整数和字符型数据的广义表的链表表示

表中套表情形下的广义表的链表表示5232436103914list25list11247‘a’‘s’（5,（3,2,（14,9,3）,（）,4）,2,（6,3,10））(5,12,’s’,47,’a’)广义表的表示只包括整数和字符型数据的广义表的链表表示表中套43广义表的基本运算，除包括线性表的基本运算外，还有求深度、取表头、取表尾、遍历等。这些运算中大部分与对应的线性表、树或者图的运算类似，只是取表头和取表尾是广义表特有的运算。

广义表的基本运算，除包括线性表的基本运算外，还有44第五章数组数组的类型定义和表示方法特殊矩阵和稀疏矩阵存储方法及运算的实现广义表的结构特点第五章数组数组的类型定义和表示方法455.1.1二维数组的定义定义数组特点数组结构固定数据元素同构数组运算给定一组下标，存取相应的数据元素给定一组下标，修改数据元素的值()()()()()()()()()数组是一组有固定（一旦定义了数组的维数和每一维的上下限个数）的元素的集合。由于这个性质，使得对数组的操作不像对线性表的操作那样可以在表中任意一个合法的位置插入或删除一个元素。对于数组的操作一般只有两类：数组可以看成是一种特殊的线性表，即线性表中数据元素本身也是一个线性表5.1.1二维数组的定义数组特点(46矩阵Am×n看成n个列向量的线性表

矩阵Am×n看成n个列向量的线性表47矩阵Am×n看成m个行向量的线性表矩阵Am×n看成m个行向量的线性表485.1.2数组的顺序存储结构次序约定以行序为主序以列序为主序

a11a12……..a1n

a21a22……..a2n

am1am2……..amn

…………….Loc(aij)=Loc(a11)+[(i-1)n+(j-1)]*l

按行序为主序存放amn

…….

am2

am1……a2n…..

a22a21a1n

……a12

a1101n-1m*n-1n

二维数组按列序为主序存放（下标从1开始）01m-1m*n-1m

amn

……..

a2n

a1n……….am2……..

a22a12am1

…….a21

a11

a11

a12

……..

a1n

a21

a22……..

a2n

am1

am2

……..amn

….Loc(aij)=Loc(a11)+[(j-1)*m+(i-1)]*L

L为每一个数组元素所占的存储单元个数5.1.2数组的顺序存储结构a149

二维数组三维数组行向量下标i页向量下标i列向量下标j行向量下标j

列向量下标k共有120个元素三维数组的逻辑结构图下标从0开始页行列二维数组三维数组行向50三维数组(下标从0开始)

各维元素个数为

m1,m2,m3下标为i1,i2,i3的数组元素的存储地址：（按页/行/列存放）LOC(i1,i2,i3)=a+(i1*m2*m3+i2*m3+i3

)*l

前i1页总元素个数第i1页的前i2行总元素个数三维数组(下标从0开始)各维元素个数为m1,m2,51

n维数组

各维元素个数为

m1,m2,m3,…,mn下标为i1,i2,i3,…,in的数组元素的存储地址：

LOC(i1,i2,…,in)=a+(i1*m2*m3*…*mn+i2*m3*m4*…*mn++……+in-1*mn+in

)*l

n维数组各维元素个数为m1,m2,m3,…,52对称阵下三角矩阵5.2.1特殊矩阵为节约存储，只存对角线及对角线以上的元素，或者只存对角线及对角线以下的元素。前者称为上三角矩阵，后者称为下三角矩阵。对称阵下三角矩阵5.2.1特殊矩阵为节约存储，只存对角线及53对称阵的上三角矩阵把它们按行存放于一个一维数组B中，称之为对称矩阵A的压缩存储方式。数组B共有n+(n-1)++1=

n*(n+1)/2

个元素。A=对称阵的上三角矩阵把它们按行存放于一个一维数组B中，称之54对称矩阵的存储在矩阵中，aij

=aji012345678n(n+1)/2-1Ba00a10a11a20a21a22a30a31a32……an-1n-1

存下三角对称矩阵的存储在矩阵中，aij=aji0155若i<j，数组元素A[i][j]在矩阵的上三角部分,在数组B中没有存放，可以找它的对称元素A[j][i]=j*(j+1)/2+i

若

i

j,数组元素A[i][j]在数组B中的存放位置为1+2++i+j=(i+1)*i/2+j前i行元素总数第i行第j个元素前元素个数若已知某矩阵元素位于数组B的第k个位置，可寻找满足

i(i+1)/2k<(i+1)*(i+2)/2的

i,此即为该元素的行号。

j=k

-i*(i+1)/2此即为该元素的列号。例，当k=8,3*4/2=6k

<4*5/2=10,取i=3。则j=8-3*4/2=2。若i<j，数组元素A[i][j]在矩阵的上三角部56上三角矩阵Ba00a01a02a03a11a12a13a22a23

a33

0123456789若i

j，数组元素A[i][j]在数组B中的存放位置为n+(n-1)+(n-2)++(n-i+1)+j-i前i行元素总数第i行第j个元素前元素个数n=4上三角矩阵Ba00a01a02a03a157

若

ij，数组元素A[i][j]在数组B中的存放位置为

n+(n-1)+(n-2)++(n-i+1)+j-i==(2*n-i+1)*i/2+j-i==

(2*n-i-1)*i/2+j

若i>j，数组元素A[i][j]在矩阵的下三角部分，在数组B中没有存放。因此，找它的对称元素A[j][i]。

A[j][i]在数组B的第

(2*n-j-1)*j/2+i

的位置中找到。对于上三角矩阵若ij，数组元素A[i][j]在数组B中的存58三角矩阵

a11

00

……..0

a21a22

0

……..0

an1an2an3……..ann

….0Loc(aij)=Loc(a11)+[(+(j-1)]*L

i(i-1)2a11a21a22a31a32an1ann

…...…...k=01234n(n-1)/2n(n+1)/2-1按行序为主序：j>i时aij为0一个元素所占字节数下标从1开始三角矩阵a11059三对角矩阵的压缩存储Ba00a01a10a11a12a21a22a23…

an-1n-2an-1n-1

012345678910对角阵的下标从0起存放对角阵元素的一维数组的下标从0起三对角矩阵的压缩存储Ba00a01a10a160三对角矩阵中除主对角线及在主对角线上下最临近的两条对角线上的元素外，所有其它元素均为0。总共有2+3(n-2)+2=3n-2个非零元素。将三对角矩阵A中三条对角线上的元素按行存放在一维数组B中，且a00存放于B[0]。在三条对角线上的元素aij

满足

0

i

n-1,i-1

j

i+1在一维数组B中A[i][j]在第i行，它前面有3*i-1个非零元素,在本行中第j列前面有j-i+1个，所以元素A[i][j]在B中位置为

k=2*i+j三对角矩阵中除主对角线及在主对角线上下最临近的两条对角线上的61若已知三对角矩阵中某元素

A[i][j]

在数组B[]存放于第

k

个位置，则有

i=(k+1)/3

j=k

-2*i例如，当k=8时，

i=(8+1)/3=3,j=8-2*3=2

当k=10时，

i=(10+1)/3=3,j=10-2*3=4不若已知三对角矩阵中某元素A[i][j]在数组B[]62对角矩阵(这是三对角阵，如是K对角则要求K是奇数)

a11

a120

…………….0

a21

a22

a23

0

……………00

0

…an-1,n-2an-1,n-1

an-1,n0

0

……an,n-1ann.

0

a32a33

a34

0

………0……………Loc(aij)=Loc(a11)+[2(i-1)+(j-1)]*L

a11a12a21a22a23ann-1ann

…...…...k=01234n(n-1)/2n(n+1)/2-1按行序为主序：对角阵的下标从1起存放对角阵元素的一维数组的下标从0起对角矩阵(这是三对角阵，如是K对角则要求K是奇数)635.2.2稀疏矩阵定义：非零元较零元少，且分布没有一定规律的矩阵压缩存储原则：只存矩阵的行列维数和每个非零元的行列下标及其值5.2.2稀疏矩阵定义：非零元较零元少，且分布没有一定规64M由{(1,2,12),(1,3,9),(3,1,-3),(3,6,14),(4,3,24),(5,2,18),(6,1,15),(6,4,-7)}和矩阵维数（6,7,8）唯一确定例如：M由{(1,2,12),(1,3,9),(3,1,-3)65稀疏矩阵的压缩存储方法顺序存储结构三元组表#defineM20typedefstructnode

/*三元组表中元素类型*/{inti,j;

/*非零元所在行号和列号*/

intv;

/*非零元素值*/}TriTupleNode;TriTupleNodema[M];maijv012345678稀疏矩阵的压缩存储方法#defineM20m66maijv0123456786

7

8

121213931-3361443245218611564-7maijv01267求转置矩阵问题描述：已知一个稀疏矩阵的三元组表，求该矩阵转置矩阵的三元组表问题分析一般矩阵转置算法：for(col=0;col<n;col++)for(row=0;row<m;row++)B[col][row]=A[row][col];时间复杂度：T(n)=O(mn)求转置矩阵for(col=0;col<n;col++)686

7

8

121213931-3361443245218611564-7ijv012345678maijv7

6

8

13-3161521122518319342446-76314012345678mb?按行序存放6781269解决思路：只要做到

将矩阵行、列维数互换将每个三元组中的i和j相互调换重排三元组次序，使mb中元素以B的行(A的列)为主序算法描述：算法分析：T(n)=O(A的列数n非零元个数t)若t与mn同数量级，则方法一：按原矩阵A的列序转置,来得到A的转置矩阵B

因为在ma是阵A的按行优先存放的三元组表，要想从ma得到mb。即按mb中三元组次序依次在ma中找到相应的三元组进行转置。为找到A中每一列所有非零元素，需对其三元组表ma从第一个元素起扫描一遍。由于ma中以A行序为主序,所以由此得到的恰是mb中应有的顺序解决思路：只要做到算法描述：算法分析：T(n)=O(A的列数70由于我们已按行优先将阵A中的非零元存储到三元组表ma中了，现在的问题就是如何由ma得到mb！

思路是：按ma中三元组次序转置，转置结果放入mb中恰当位置。此法关键是要预先确定原矩阵A中每一列第一个非零元在mb中位置，为确定这些位置，转置前应先求得A的每一列中非零元个数。方法二：按行序转置（快速转置）即如何得到阵A的按列优先排列的非零元三元组表mb?由于我们已按行优先将阵A中的非零元存储到三元71实现：设两个数组num[col]：表示矩阵A中第col列中非零元个数cpot[col]：指示A中第col列第一个非零元在mb中的位置显然有：cpot[1]=1;cpot[col]=cpot[col-1]+num[col-1];(2colma[0].j)1357889colnum[col]cpot[col]12223241506170矩阵A的列数实现：设两个数组cpot[1]=1;1357889colnu72算法描述：算法分析：T(n)=O(A的列数n+非零元个数t)若t与mn同数量级，则T(n)=O(mn)算法描述：算法分析：T(n)=O(A的列数n+非零元个数t)736

7

8

121213931-3361443245218611564-7ijv012345678maijv012345678mbcolnum[col]cpot[col]1122323524715806817907

6

8

13-3161521122518319342446-76314pppppppp46297536781274

7000150

0-40000

-2000021

000-100A=22-4∧∧1515∧∧41-2∧4621∧∧11734-1∧∧^ijedownright希疏矩阵的链式存储结构7000755.3广义表

广义表(Lists)也称为列表，它是线性表的推广。大家知道，线性表是n（n≥0）个元素a1，a2，…，ai，…，an的有限序列。其中，线性表的元素仅限于原子项，所谓原子，指的是结构上不可再分割的一种成分，它可以是一个数，或者是一个结构。如果放松对线性表元素的这种限制，允许它们具有其自身独立的类型结构，那么就产生了广义表的概念。5.3广义表广义表(Lists)也称为列表，它是线76广义表是n(0)个表元素组成的有限序列，记作

LS=(a0,a1,a2,…,an-1)