数组、特殊矩阵和广义表课件

4.1数组（重点）4.2特殊矩阵的压缩存储4.3广义表

小结数组、特殊矩阵和广义表12七月2024第1页4.1数组

4.1.1数组的基本概念

数组作为一种数据结构其特点是结构中的元素本身可以是具有某种结构的数据，但属于同一数据类型，比如：一维数组可以看作一个线性表，二维数组可以看作“数据元素是一维数组”的一维数组，三维数组可以看作“数据元素是二维数组”的一维数组，依此类推。数组的定义：

数组（array）是由下标（index）和值（value）组成的序对集合。

在C语言中，一维数组定义为：ElemTypearrayname[MAXSIZE];

12七月2024第2页

下图一个m行n列的二维数组。它可以看成是由行向量组成的向量，也可以看成是由列向量组成的向量。在数组中通常做下面两种操作：(1)取值操作：给定一组下标，读其对应的数据元素。(2)赋值操作：给定一组下标，存储或修改与其相对应的数据元素。a00a01…a0,n-1a10a11…a1,n-1…

…

…

aij

………am-1,0am-1,1…am-1,n-1A=

m行n列的二维数组与线性表的区别：在数组中不能进行插入、删除数据元素的操作。

12七月2024第3页

4.1.2数组的存储结构

一维数组在计算机内是存放在一组连续的存储单元中。因此，数组中任一元素A[i]的存储位置可用下列公式计算：LOC（A[i]）=LOC（A[0]）+(i)×L

其中L是每个数据元素所占存储单元的个数。对于一维数组按下标顺序分配即可。a00a01…a0,n-1a10a11…a1,n-1…

…

…

aij

………am-1,0am-1,1…am-1,n-1A=

m行n列的二维数组二维数组的存储器，一般有两种存储方式：一是以行为主序的顺序存放，如BASIC、C等程序设计语言，即一行分配完了接着分配下一行。12七月2024第4页

C语言中，数组就是按行优先顺序存储的。如，一个2×3的二维数组A2×3，以行为主序的分配顺序为：a00，a01，a02，a10，a11，a12。以列为主序分配顺序为：a00,a10,a01,a11,a02,a12a00a01a02a10a11a12A2×3=

2×3的二维数组a00a01a02a10a11a12a00a10a01a11a02a12以行为主序以列为主序12七月2024第5页在C语言中，二维数组定义为：

ElemTypearrayname[m][n];数组中任一元素A[i][j]的存储位置可用下列公式计算：LOC(A[i][j])=LOC(A[0][0])+(i×n+j)×L

这是因为数组元素A[i][j]的前面有i行，每一行的元素个数为n，在第i行中A[i][j]的前面还有j个数组元素。L仍然是每个数据元素所占存储单元的个数。例如2×3二维数组：LOC(a12)=LOC(a00)+[(1)*3+2]*La00a01a02a10a11a12A=12七月2024第6页

【例4-1】选择题。设二维数组M的每个数据元素占6个存储单元，行下标i的范围从0到8，列下标j的范围从1到10，则存放M至少需要(Ⅰ)个字节；若M按行优先方式存储，元素M[8][5]的起始地址与当M按列优先方式存储时的(Ⅱ)元素的起始地址一致。

(Ⅰ)A.90B.180C.240D.540(Ⅱ)A.M[8][5]B.M[3][10]C.M[5][8]D.M[0][9]

(1)二维数组M共有(8-0+1)×(10-1+1)=90个数据元素，所以共占90×6=540个字节，即(Ⅰ)选D.(2)M[8][5]的存储位置为：LOC(M[8][5])=LOC(M[0][1])+504在(Ⅱ)中只有B.有表达是：LOC(M[3][10])=LOC(M[0][1])+504,因此(Ⅱ)选B.12七月2024第7页在科学与工程计算问题中，矩阵中非零元素呈某种规律分布或者矩阵中出现大量的零元素的情况，比如常见的一些特殊矩阵，如三角矩阵、对称矩阵、带状矩阵、稀疏矩阵等。4.2.1对称矩阵

4.2特殊矩阵的压缩存储

在一个n阶方阵中，对称矩阵的特点是：若数据元素满足下列性质：36285198603６896２5885169860A=A[i][j]=A[j][i]（0≤i,j≤n-1）

12七月2024第8页A[i][j]和SA[k]之间对应关系:

若i≥j，则A[i][j]在下三角矩阵中，A[i][j]之前的i行一共有1+2+…+i=i×(i+1)/2个元素，在第i行上，A[i][j]之前有j个元素，因此有：k=i×(i+1)/2+j

若i<j，则A[i][j]在上三角矩阵中。因为A[i][j]=A[j][i],所以只要交换上述对应关系式中的i和j即可得到：

k=j×(j+1)/2+i(０≤k<n×(n+1)/2)

若令I=max(i,j)，J=min(i,j)，得到：

k=I×(I+1)/2+J(０≤k<n×(n+1)/2)

因此：LOC(A[i][j])=LOC(SA[k])=LOC(SA[0])+k×L

=LOC(SA[0])+[I×(I+1)/2+J]×La00a10a11a20a21a22…对于一个n阶对称矩阵，第i行（0≤i＜n）只需要存储i+1个元素，元素总数为：=

n(n+1)/212七月2024第9页4.2.2三角矩阵

以主对角线划分，三角矩阵有上三角和下三角两种。上三角矩阵如图所示，它的下三角（不包括主对角线）中的元素均为常数。下三角矩阵正好相反，它的主对角线上方均为常数，如图所示。在大多数情况下，三角矩阵常数为零。a00c……ca10a11

c…c……………an-1,0an-1,1…an-1,n-1下三角矩阵a00a01…a0,n-1ca11…a1,n-1……………cc…an-1,n-1

上三角矩阵12七月2024第10页三角矩阵中的重复元素c可共享一个存储空间，其余的元素正好有n×(n+1)/2个，因此，三角矩阵可压缩存储到向量SA[0..n(n+1)/2]中，其中c存放在最后一个分量中。

例1：

10

ccc

89cc

5

67c

1234A1=a21（=6）对应的k=i(i+1)/2+j=4

a00c……ca10a11

c…c……………an-1,0an-1,1…an-1,n-1下三角矩阵k=i*(i+1)/2+j

当i≥jn*(n+1)/2

当i<j(常数c的存储位置)12七月2024第11页以行为主序顺序存储上三角部分，最后存储对角线下方的常量。对于第0行，存储n个元素，第1行存储n-1个元素，…，第p行存储(n-p)个元素，A[i][j]的前面有i行，共存储S个元素：

a00a01…a0,n-1ca11…a1,n-1……………cc…an-1,n-1

上三角矩阵

S=n+(n-1)+…+(n-i+1)==i×(2n-i+1)/2而A[i][j]是它所在的行中要存储的第(j-i)个，所以，它是上三角存储顺序中的第i×(2n-i+1)/2+(j-i)个，因此它在SA中的下标为：k=i×(2n-i+1)/2+j-i12七月2024第12页SA[k]与A[i][j]的对应关系为：k=i×(2n-i+1)/2+j-i当i≤jn×(n+1)/2当i>j4.2.3对角矩阵

在n阶对角矩阵A中，所有的非零元素集中在以主对角线为中心的带状区域中，显然,当∣i-j∣>1时，元素向量A[i][j]=0(或同一个常数c)。a00

a010…0a10a11

a120…00

a21a22

a230…0………………00…

an-1,n-2an-1,n-1A=12七月2024第13页

an-1,n-1

an-1n-2……a21a12a11a10a01

a00K=012345……3n-23n-3三对角矩阵可按行优先顺序将其压缩存储到一维向量M[0‥3n-3]中，M[k]和对角矩阵非零元素A[i][j]之间的对应关系为：这是因为第i行前有i行，共3×i-1个数据元素；第j列前有j-(i-1)个数据元素，所以k=3×i-1+j-(i-1)=2×i+j∣i-j∣>1

k=2×i+j

例如，A[2][5]=0，这是因为∣i-j∣=∣2-5∣>1；A[2][3]对应M[7]，这是因为k=2×i+j=2×2+3=7。12七月2024第14页4.2.4稀疏矩阵

设m×n矩阵中有t个非零元素，若且t<<m×n，这样的矩阵称为稀疏矩阵。

1600220-1508300000060000000068000000000190稀疏矩阵M

M=1600068008000003000022060000000019-1500000M的转置矩阵NN=将三元组按行优先的顺序，同一行中列号从小到大的规律排列成一个线性表，得到一个其结点均是三元组的线性表。

12七月2024第15页ijv1111621422316-154228523363467516886519

三元组表Aijv11116215683228432354122643675619861-15

三元组表BtypedefintElemType;typedefstruct

{inti,j;

ElemTypev;}SPNode;typedefstruct

{intmu,nu,tu;

SPNodedata[MAXSIZE+1];}SPMatrix;

SPMatrixA，B;矩阵元素的行、列下标从（1，1）开始。将矩阵的总行数、总列数及非零元素的总数均作为三元组表的属性进行描述。12七月2024第16页(1)按照矩阵M的列序进行转置

一个m×n的矩阵A，它的转置B是一个n×m的矩阵，且a[i][j]=b[j][i]，1≦i≦m，1≦j≦n，即A的行是B的列，A的列是B的行。转置结果为下。

1.按A的列序转置:将A转置为B，就是将A的三元组表a.elem置换为表B的三元组表b.elem，由于A的列是B的行，因此，按a.elem的列序转置，所得到的转置矩阵B的三元组表b.elem必定是按行优先存放的。

i

jv121213925831-34324

i

jv13-321123193424528矩阵a转置矩阵b1234512七月2024第17页【算法4.1】稀疏矩阵转置。SPMatrix*Transpose(SPMatrix*A){SPMatrix*B;

intp,q,col;B->mu=A->nu;B->nu=A->mu;B->tu=A->tu;

if(B->tu>0)

{q=1;

for(col=1;col<=(A->nu);col++)

for(p=1;p<=(A->tu);p++)

if(A->data[p].j==col)

{B->data[q].i=A->data[p].j;B->data[q].j=A->data[p].i;B->data[q].v=A->data[p].v;q++;}/*if*/}/*if(B->tu>0)*/returnB;

/*返回的是转置矩阵的指针*/}/*Transpose*/

i

jv121213925831-34324

i

jv13-32112319342452812七月2024第18页分析该算法，其时间主要耗费在for的二重循环上，所以时间复杂性为O(n×t)，即与A的列数和非零元素个数的乘积成正比。而通常用二维数组表示矩阵转置算法的执行时间是0(m×n)，它正比于行数和列数的乘积。当上述稀疏矩阵非零元素的个数t大于行数时，算法的时间复杂度大于通常的转置算法的时间。(2)按照三元组的次序进行转置

首先要知道A->data中的元素在B->data中的存储位置。这就要预先确定矩阵M中每一列的第一个非零元素在B->data中应有的位置。为此，需设置两个数组num[1..n]和cpot[1..n]，分别存放在矩阵M中每一列的非零元素个数和每一列第1个非零元素在B->data中的位置:12七月2024第19页

num[col]表示矩阵M中第col列中非零元素个数；cpot[col]的初值表示M中第col列的第1个非零元素在B->data中的位置。显然有

基本思想：先求出三元组表A中每一列的非零元素个数填入num[1..n]数组中；

cpot[1]=1;cpot[col]=pot[col-1]+num[col-1](1≤col≤n)表4-1三元组表A的num与pot值col123456num[col]211211cpot[col]13457812七月2024第20页【算法4.2】稀疏矩阵转置的改进算法。SPMatrix*TransM2(SPMatrix*A){SPMatrix*B;intp,q,col,k;intnum[A->nu+1],cpot[A->nu+1];B->mu=A->nu;B->nu=A->mu;B->tu=A->tu;

if(B->tu>0)

{for(col=1;col<=A->nu;col++)num[col]=0;for(k=1;k<=A->tu;k++)

num[A->data[k].j]++;

然后求出cpot[1..n]各数据值；最后依次扫描A->data，当扫描到一个col列元素时，直接将其存放在B->data的cpot[col]位置上，cpot[col]加１，cpot[col]中始终是下一个col列元素在B.data中的位置。

12七月2024第21页cpot[1]=1;for(col=2;col<=A->nu;col++)

cpot[col]=cpot[col-1]+num[col-1];for(p=1;p<=A->tu;p++)

{col=A->data[p].j;

q=cpot[col];

B->data[q].i=A->data[p].j;B->data[q].j=A->data[p].i;B->data[q].v=A->data[p].v;

cpot[col]++;}/*for*/}returnB;

}col12345num[col]11201cpot[col]0124482524439131212-331v

j

iB的形成顺序41253A2434-3138529311221v

j

i12七月2024第22页算法复杂度分析：这个算法中有四个循环，分别执行n，t，n-1，t次，因此总的计算量是O(n+t)，当t和m×n等数量级时，该算法执行的时间是O（m×n）；存储空间比前一个算法多了两个向量：num[1..n]和

cpot[1..n]。2．稀疏矩阵的十字链表存储(1)十字链表的组成

rowcolvdownright∧311541213-122∧∧∧∧∧∧M.cheadM.rhead

30050-1002000

M=例M矩阵是稀疏矩阵：十字链表如右图12七月2024第23页∧311541213-122∧∧∧∧∧∧M.cheadM.rheadvcolrowdownrighttypedefstruct{QLNode*rhead[MAXSIZE+1],*chead[MAXSIZE+1];

intmu,nu,tu;}CrossList;

结点的结构定义如下:

typedefstructQLnode{introw,col;

intv;

structQLnode*right,*down;/*该非零元所在行、列表的后继链域*/}QLNode;12七月2024第24页2．建立稀疏矩阵M的十字链表

首先输入的信息是：m（M的行数），n（M的列数），t（非零元素的数目），紧跟着输入的是t个形如（i，j，v）的三元组。

算法的设计思想是：首先建立每行和每列只有头结点的空链表，然后每输入一个三元组（i，j，v），将其结点按其列号的大小插入到第i个行链表中去，同时也按其行号的大小将该结点插入到第j个列链表中去。【算法4.4】建立稀疏矩阵的十字链表。CrossList*CreateSMatrix_OL(){CrossList*M;

printf("pleaseinputmu,nu,tu\n");12七月2024第25页scanf("%d%d%d",&m,&n,&t);

M->mu=m;M->nu=n;M->tu=t;

for(k=1;k<=m;k++)M->rhead[k]=NULL;

for(k=1;k<=n;k++)M->chead[k]=NULL;

printf("pleaseinputrow,col,v");

scanf("%d%d%d",&i,&j,&e);/*输入矩阵的值*/

while(i!=0)

{p=(QLNode*)malloc(sizeof(QLNode));

p->row=i;p->col=j;p->v=e;p->right=p->down=NULL;

if(M->rhead[i]==NULL)M->rhead[i]=p;

else{q=M->rhead[i];

while((q->right)&&(q->right->col<j))

q=q->right;

p->right=q->right;q->right=p;/*插入第i行*/

}

12七月2024第26页

if(M->chead[j]==NULL)M->chead[j]=p;

else{

q=M->chead[j];

while((q->down)&&(q->down->row<i))

q=q->down;/*插入第j行*/

p->down=q->down;q->down=p;

}

printf("pleaseinputrow,

col,v");

scanf("%d%d%d",&i,&j,&e);}

returnM;

}/*CreateSMatrix_OL*/

对于m行n列且有t个非零元的稀疏矩阵，算法中，初始化各行链表或列链表的时间复杂度为O(S)，其中S=MAX{m，n}；插入每个结点到相应的行链表和列链表的时间复杂度是O(t×S)，所以总的时间复杂度为O(t×S)。12七月2024第27页4.3广义表

4.3.1广义表的定义和性质

1．广义表的定义广义表是n（n≥0）个数据元素a1，a2，…，ai，…，an的有序序列，一般记作：LS＝（a1，a2，…，ai，…，an）其中：LS是广义表的名称，n是它的长度。每个ai（1≤i≤n）是LS的成员，它可以是单个元素，也可以是一个广义表。显然，广义表的定义是递归的。如果ai是单元素，用小写字母表示，并称为原子；如果ai是广义表，用大写字母表示，称为子表。12七月2024第28页A＝（）——空表。B＝（b，c，d）——B是长度为3的广义表，它的两个元素都是单元素，即是一个线性表。C＝（a，B）=（a，（b，c，d））——是长度为2的广义表，第一个元素是单元素，第二个元素是子表B。D＝（B，y）——长度为2，第一个元素是子表B，第二个元素是单元素。E＝（A，B，C）——长度为3，三个元素都是子表。F＝（F，a）——长度为2，第一个元素是F