C語言基礎(chǔ)課件1第4章 數(shù)組

1二維數(shù)組()()()()()()()()()數(shù)組A可看成一個(gè)線性表A=(a0，a1

，...，ak)

k=m-1或n-1ai

或者是行向量ai=(ai0

，ai1

，...，ai,n-1)0≤i≤m-1aj或者是列向量aj=(a0j

，a1j

，...，am-1,j)0≤j≤n-124.1.2數(shù)組的順序存儲(chǔ)結(jié)構(gòu)次序約定以行序?yàn)橹餍蛞粤行驗(yàn)橹餍?/p>

a11a12……..a1n

a21a22……..a2n

am1am2……..amn

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

按行序?yàn)橹餍虼娣臿mn

……..

am2am1

……….a2n

……..

a22a21a1n

…….a12

a1101n-1m*n-1n

按列序?yàn)橹餍?1m-1m*n-1mamn

……..

a2na1n

……….am2

……..

a22a12am1

…….a21

a11

a11

a12

……..

a1n

a21

a22……..

a2n

am1

am2

……..amn

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

34.1.3矩陣的壓縮存儲(chǔ)方法壓縮存儲(chǔ)為多個(gè)值相同的元素只分配一個(gè)存儲(chǔ)空間對(duì)零元素不分配空間4

a11

a12

….

……..a1n

a21

a22

……..…….a2n

an1

an2

……..ann

….a11a21a22a31a32an1ann

…...…...k=01234n(n-1)/2n(n+1)/2-1

按行序?yàn)橹餍颍簩?duì)稱矩陣的壓縮存儲(chǔ)方法5

a11

00

……..0

a21

a22

0

……..0

an1

an2

an3……..ann

….

0Loc(aij)=Loc(a11)+[(+(j-1)]*l

i(i-1)2a11a21a22a31a32an1ann

…...…...k=01234n(n-1)/2n(n+1)/2-1按行序?yàn)橹餍颍喝蔷仃嚨膲嚎s存儲(chǔ)方法6

a11

a12

0

…………….0

a21

a22

a23

0

……………0

0

0

…an-1,n-2

an-1,n-1

an-1,n

0

0

……an,n-1

ann.

0

a32

a33

a34

0

………0……………Loc(aij)=Loc(a11)+3*(i-1)-1+j-i+1=Loc(a11)+2(i-1)+(j-1)

a11a12a21a22a23ann-1ann

…...…...k=01234n(n-1)/2n(n+1)/2-1按行序?yàn)橹餍颍簩?duì)角矩陣的壓縮存儲(chǔ)方法7稀疏矩陣定義非零元較零元少，且分布沒有一定規(guī)律的矩陣壓縮存儲(chǔ)原則只存矩陣的行列維數(shù)和每個(gè)非零元的行列下標(biāo)及其值M由{(1,2,12),(1,3,9),(3,1,-3),(3,6,14),(4,3,24),(5,2,18),(6,1,15),(6,4,-7)}和矩陣維數(shù)(6,7)唯一確定8三元組表所需存儲(chǔ)單元個(gè)數(shù)為3(t+1)其中t為非零元個(gè)數(shù)6

7

8

121213931-3361443245218611564-7maijv012345678ma.data[0]中分別存放矩陣行列維數(shù)和非零元個(gè)數(shù)行列下標(biāo)非零元值稀疏矩陣的三元組表示法#defineMAX10typedefstruct{inti,j;elemtypev;}node;typedefstruct{intmu,nu,tu;nodedata[MAX];}mat;matma;mu,nu,tu分別存放矩陣行列維數(shù)和非零元個(gè)數(shù)9稀疏矩陣轉(zhuǎn)置算法一算法思想將矩陣A的行數(shù)和列數(shù)互換=>矩陣B將每個(gè)三元組的i和j互換=>矩陣B對(duì)三元組表B，按其行序進(jìn)行排序轉(zhuǎn)置后的三元組B以行（即A的列）為主序排列6

7

8

121213931-3361443245218611564-7ijv01234567810稀疏矩陣轉(zhuǎn)置算法二算法思想按矩陣A的列序進(jìn)行轉(zhuǎn)置首先尋找矩陣A的第1列的所有三元組，將其(i,j,v)改為(j,i,v)后依次存放到矩陣B的三元組表中然后中尋找矩陣A第2列的所有三元組，將其(i,j,v)改為(j,i,v)后依次存放到矩陣B的三元組表中依次類推轉(zhuǎn)置后的三元組B以行（即A的列）為主序排列11678121213931-3361443245218611564-7ijv012345678ma76813-3161521122518319342446-76314ijv012345678mbkppppppppkkkkppppppppcol=1col=212稀疏矩陣的轉(zhuǎn)置算法分析算法的主要耗費(fèi)時(shí)間是在col和p的兩重循環(huán)中，所以算法的時(shí)間復(fù)雜度為O(nu*tu)即和(A的列數(shù)與非零元素的個(gè)數(shù)的乘積)成正比當(dāng)非零元個(gè)數(shù)值tu->m*n時(shí)(m、n分別表示數(shù)組的行列數(shù)),算法的時(shí)間復(fù)雜度成為O(m*n2)上述轉(zhuǎn)置算法只適用于:tu<<m*n的情況13cpot[1]=1;cpot[col]=cpot[col-1]+num[col-1];(2colma[0].j)1357889快速轉(zhuǎn)置:即按ma中三元組次序轉(zhuǎn)置，轉(zhuǎn)置結(jié)果放入b中恰當(dāng)位置此法關(guān)鍵是要預(yù)先確定M中每一列第一個(gè)非零元在mb中位置,

即轉(zhuǎn)置前應(yīng)先求得M的每一列中非零元個(gè)數(shù)實(shí)現(xiàn)：設(shè)兩個(gè)數(shù)組num[col]：表示矩陣M中第col列中非零元個(gè)數(shù)cpot[col]：指示M中第col列第一個(gè)非零元在mb中位置,顯然:colnum[col]cpot[col]1222324150617014678121213931-3361443245218611564-7ijv012345678maijv012345678mbcolnum[col]cpot[col]11223235247158068179076813-3161521122518319342446-76314pppppppp462975315快速轉(zhuǎn)置算法如下：voidfasttrans(matb,mata){intp,q,col,k;intnum[a.n+1],cpot[a.n+1];b.m=a.n;b.n=a.m;b.t=a.t;if(b.t<=0)printf(“a=0”\n);for(col=1;col<=a.n;++col)num[col]=0;for(k=1;k<=a.t;++k)++num[a.data[k].j];cpot[1]=1;for(col=2;col<=a.n;