數(shù)組、特殊矩陣和廣義表課件

4.1數(shù)組（重點）4.2特殊矩陣的壓縮存儲4.3廣義表

小結(jié)數(shù)組、特殊矩陣和廣義表12七月2024第1頁4.1數(shù)組

4.1.1數(shù)組的基本概念

數(shù)組作為一種數(shù)據(jù)結(jié)構(gòu)其特點是結(jié)構(gòu)中的元素本身可以是具有某種結(jié)構(gòu)的數(shù)據(jù)，但屬于同一數(shù)據(jù)類型，比如：一維數(shù)組可以看作一個線性表，二維數(shù)組可以看作“數(shù)據(jù)元素是一維數(shù)組”的一維數(shù)組，三維數(shù)組可以看作“數(shù)據(jù)元素是二維數(shù)組”的一維數(shù)組，依此類推。數(shù)組的定義：

數(shù)組（array）是由下標（index）和值（value）組成的序?qū)稀?/p>

在C語言中，一維數(shù)組定義為：ElemTypearrayname[MAXSIZE];

12七月2024第2頁

下圖一個m行n列的二維數(shù)組。它可以看成是由行向量組成的向量，也可以看成是由列向量組成的向量。在數(shù)組中通常做下面兩種操作：(1)取值操作：給定一組下標，讀其對應(yīng)的數(shù)據(jù)元素。(2)賦值操作：給定一組下標，存儲或修改與其相對應(yīng)的數(shù)據(jù)元素。a00a01…a0,n-1a10a11…a1,n-1…

…

…

aij

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

m行n列的二維數(shù)組與線性表的區(qū)別：在數(shù)組中不能進行插入、刪除數(shù)據(jù)元素的操作。

12七月2024第3頁

4.1.2數(shù)組的存儲結(jié)構(gòu)

一維數(shù)組在計算機內(nèi)是存放在一組連續(xù)的存儲單元中。因此，數(shù)組中任一元素A[i]的存儲位置可用下列公式計算：LOC（A[i]）=LOC（A[0]）+(i)×L

其中L是每個數(shù)據(jù)元素所占存儲單元的個數(shù)。對于一維數(shù)組按下標順序分配即可。a00a01…a0,n-1a10a11…a1,n-1…

…

…

aij

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

m行n列的二維數(shù)組二維數(shù)組的存儲器，一般有兩種存儲方式：一是以行為主序的順序存放，如BASIC、C等程序設(shè)計語言，即一行分配完了接著分配下一行。12七月2024第4頁

C語言中，數(shù)組就是按行優(yōu)先順序存儲的。如，一個2×3的二維數(shù)組A2×3，以行為主序的分配順序為：a00，a01，a02，a10，a11，a12。以列為主序分配順序為：a00,a10,a01,a11,a02,a12a00a01a02a10a11a12A2×3=

2×3的二維數(shù)組a00a01a02a10a11a12a00a10a01a11a02a12以行為主序以列為主序12七月2024第5頁在C語言中，二維數(shù)組定義為：

ElemTypearrayname[m][n];數(shù)組中任一元素A[i][j]的存儲位置可用下列公式計算：LOC(A[i][j])=LOC(A[0][0])+(i×n+j)×L

這是因為數(shù)組元素A[i][j]的前面有i行，每一行的元素個數(shù)為n，在第i行中A[i][j]的前面還有j個數(shù)組元素。L仍然是每個數(shù)據(jù)元素所占存儲單元的個數(shù)。例如2×3二維數(shù)組：LOC(a12)=LOC(a00)+[(1)*3+2]*La00a01a02a10a11a12A=12七月2024第6頁

【例4-1】選擇題。設(shè)二維數(shù)組M的每個數(shù)據(jù)元素占6個存儲單元，行下標i的范圍從0到8，列下標j的范圍從1到10，則存放M至少需要(Ⅰ)個字節(jié)；若M按行優(yōu)先方式存儲，元素M[8][5]的起始地址與當M按列優(yōu)先方式存儲時的(Ⅱ)元素的起始地址一致。

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

(1)二維數(shù)組M共有(8-0+1)×(10-1+1)=90個數(shù)據(jù)元素，所以共占90×6=540個字節(jié)，即(Ⅰ)選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頁在科學與工程計算問題中，矩陣中非零元素呈某種規(guī)律分布或者矩陣中出現(xiàn)大量的零元素的情況，比如常見的一些特殊矩陣，如三角矩陣、對稱矩陣、帶狀矩陣、稀疏矩陣等。4.2.1對稱矩陣

4.2特殊矩陣的壓縮存儲

在一個n階方陣中，對稱矩陣的特點是：若數(shù)據(jù)元素滿足下列性質(zhì)：36285198603６896２5885169860A=A[i][j]=A[j][i]（0≤i,j≤n-1）

12七月2024第8頁A[i][j]和SA[k]之間對應(yīng)關(guān)系:

若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],所以只要交換上述對應(yīng)關(guān)系式中的i和j即可得到：

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

若令I(lǐng)=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個元素，元素總數(shù)為：=

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

以主對角線劃分，三角矩陣有上三角和下三角兩種。上三角矩陣如圖所示，它的下三角（不包括主對角線）中的元素均為常數(shù)。下三角矩陣正好相反，它的主對角線上方均為常數(shù)，如圖所示。在大多數(shù)情況下，三角矩陣常數(shù)為零。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頁三角矩陣中的重復(fù)元素c可共享一個存儲空間，其余的元素正好有n×(n+1)/2個，因此，三角矩陣可壓縮存儲到向量SA[0..n(n+1)/2]中，其中c存放在最后一個分量中。

例1：

10

ccc

89cc

5

67c

1234A1=a21（=6）對應(yīng)的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(常數(shù)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]的對應(yīng)關(guān)系為：k=i×(2n-i+1)/2+j-i當i≤jn×(n+1)/2當i>j4.2.3對角矩陣

在n階對角矩陣A中，所有的非零元素集中在以主對角線為中心的帶狀區(qū)域中，顯然,當∣i-j∣>1時，元素向量A[i][j]=0(或同一個常數(shù)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三對角矩陣可按行優(yōu)先順序?qū)⑵鋲嚎s存儲到一維向量M[0‥3n-3]中，M[k]和對角矩陣非零元素A[i][j]之間的對應(yīng)關(guān)系為：這是因為第i行前有i行，共3×i-1個數(shù)據(jù)元素；第j列前有j-(i-1)個數(shù)據(jù)元素，所以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]對應(yīng)M[7]，這是因為k=2×i+j=2×2+3=7。12七月2024第14頁4.2.4稀疏矩陣

設(shè)m×n矩陣中有t個非零元素，若且t<<m×n，這樣的矩陣稱為稀疏矩陣。

1600220-1508300000060000000068000000000190稀疏矩陣M

M=1600068008000003000022060000000019-1500000M的轉(zhuǎn)置矩陣NN=將三元組按行優(yōu)先的順序，同一行中列號從小到大的規(guī)律排列成一個線性表，得到一個其結(jié)點均是三元組的線性表。

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）開始。將矩陣的總行數(shù)、總列數(shù)及非零元素的總數(shù)均作為三元組表的屬性進行描述。12七月2024第16頁(1)按照矩陣M的列序進行轉(zhuǎn)置

一個m×n的矩陣A，它的轉(zhuǎn)置B是一個n×m的矩陣，且a[i][j]=b[j][i]，1≦i≦m，1≦j≦n，即A的行是B的列，A的列是B的行。轉(zhuǎn)置結(jié)果為下。

1.按A的列序轉(zhuǎn)置:將A轉(zhuǎn)置為B，就是將A的三元組表a.elem置換為表B的三元組表b.elem，由于A的列是B的行，因此，按a.elem的列序轉(zhuǎn)置，所得到的轉(zhuǎn)置矩陣B的三元組表b.elem必定是按行優(yōu)先存放的。

i

jv121213925831-34324

i

jv13-321123193424528矩陣a轉(zhuǎn)置矩陣b1234512七月2024第17頁【算法4.1】稀疏矩陣轉(zhuǎn)置。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;

/*返回的是轉(zhuǎn)置矩陣的指針*/}/*Transpose*/

i

jv121213925831-34324

i

jv13-32112319342452812七月2024第18頁分析該算法，其時間主要耗費在for的二重循環(huán)上，所以時間復(fù)雜性為O(n×t)，即與A的列數(shù)和非零元素個數(shù)的乘積成正比。而通常用二維數(shù)組表示矩陣轉(zhuǎn)置算法的執(zhí)行時間是0(m×n)，它正比于行數(shù)和列數(shù)的乘積。當上述稀疏矩陣非零元素的個數(shù)t大于行數(shù)時，算法的時間復(fù)雜度大于通常的轉(zhuǎn)置算法的時間。(2)按照三元組的次序進行轉(zhuǎn)置

首先要知道A->data中的元素在B->data中的存儲位置。這就要預(yù)先確定矩陣M中每一列的第一個非零元素在B->data中應(yīng)有的位置。為此，需設(shè)置兩個數(shù)組num[1..n]和cpot[1..n]，分別存放在矩陣M中每一列的非零元素個數(shù)和每一列第1個非零元素在B->data中的位置:12七月2024第19頁

num[col]表示矩陣M中第col列中非零元素個數(shù)；cpot[col]的初值表示M中第col列的第1個非零元素在B->data中的位置。顯然有

基本思想：先求出三元組表A中每一列的非零元素個數(shù)填入num[1..n]數(shù)組中；

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】稀疏矩陣轉(zhuǎn)置的改進算法。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]各數(shù)據(jù)值；最后依次掃描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頁算法復(fù)雜度分析：這個算法中有四個循環(huán)，分別執(zhí)行n，t，n-1，t次，因此總的計算量是O(n+t)，當t和m×n等數(shù)量級時，該算法執(zhí)行的時間是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;

結(jié)點的結(jié)構(gòu)定義如下:

typedefstructQLnode{introw,col;

intv;

structQLnode*right,*down;/*該非零元所在行、列表的后繼鏈域*/}QLNode;12七月2024第24頁2．建立稀疏矩陣M的十字鏈表

首先輸入的信息是：m（M的行數(shù)），n（M的列數(shù)），t（非零元素的數(shù)目），緊跟著輸入的是t個形如（i，j，v）的三元組。

算法的設(shè)計思想是：首先建立每行和每列只有頭結(jié)點的空鏈表，然后每輸入一個三元組（i，j，v），將其結(jié)點按其列號的大小插入到第i個行鏈表中去，同時也按其行號的大小將該結(jié)點插入到第j個列鏈表中去?！舅惴?.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個非零元的稀疏矩陣，算法中，初始化各行鏈表或列鏈表的時間復(fù)雜度為O(S)，其中S=MAX{m，n}；插入每個結(jié)點到相應(yīng)的行鏈表和列鏈表的時間復(fù)雜度是O(t×S)，所以總的時間復(fù)雜度為O(t×S)。12七月2024第27頁4.3廣義表

4.3.1廣義表的定義和性質(zhì)

1．廣義表的定義廣義表是n（n≥0）個數(shù)據(jù)元素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