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

1二維數(shù)組()()()()()()()()()數(shù)組A可看成一個線性表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ù)組的順序存儲結(jié)構(gòu)次序約定以行序為主序以列序為主序

a11a12……..a1n

a21a22……..a2n

am1am2……..amn

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

按行序為主序存放amn

……..

am2am1

……….a2n

……..

a22a21a1n

…….a12

a1101n-1m*n-1n

按列序為主序01m-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矩陣的壓縮存儲方法壓縮存儲為多個值相同的元素只分配一個存儲空間對零元素不分配空間4

a11

a12

….

……..a1n

a21

a22

……..…….a2n

an1

an2

……..ann

….a11a21a22a31a32an1ann

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

按行序為主序：對稱矩陣的壓縮存儲方法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按行序為主序：三角矩陣的壓縮存儲方法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按行序為主序：對角矩陣的壓縮存儲方法7稀疏矩陣定義非零元較零元少，且分布沒有一定規(guī)律的矩陣壓縮存儲原則只存矩陣的行列維數(shù)和每個非零元的行列下標及其值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三元組表所需存儲單元個數(shù)為3(t+1)其中t為非零元個數(shù)6

7

8

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

7

8

121213931-3361443245218611564-7ijv01234567810稀疏矩陣轉(zhuǎn)置算法二算法思想按矩陣A的列序進行轉(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)置算法分析算法的主要耗費時間是在col和p的兩重循環(huán)中，所以算法的時間復(fù)雜度為O(nu*tu)即和(A的列數(shù)與非零元素的個數(shù)的乘積)成正比當非零元個數(shù)值tu->m*n時(m、n分別表示數(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中恰當位置此法關(guān)鍵是要預(yù)先確定M中每一列第一個非零元在mb中位置,

即轉(zhuǎn)置前應(yīng)先求得M的每一列中非零元個數(shù)實現(xiàn)：設(shè)兩個數(shù)組num[col]：表示矩陣M中第col列中非零元個數(shù)cpot[col]：指示M中第col列第一個非零元在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;