數(shù)據(jù)結構第五講數(shù)組

2023/3/7數(shù)據(jù)結構1稀疏矩陣

一、概念1、稀疏矩陣矩陣中非零元素的個數(shù)較少（一般小于5%）.2、稀疏矩陣壓縮存儲方法：如果只存儲稀疏矩陣中的非零元素，那這些元素的位置信息該如何表示？實現(xiàn)方法：將每個非零元素用一個三元組（i，j，aij）來表示，則每個稀疏矩陣可用一個三元組線性表來表示。2023/3/7數(shù)據(jù)結構2例1：寫出下圖所示稀疏矩陣的壓縮存儲形式。

123456

123456

解：用三元組線性表表示：

{{1,2,12},{1,3,9},{3,1,-3},{3,5,14},{4,3,24},{5,2,18},{6,1,15},{6,4,-7}}再加上一個表示矩陣M的行數(shù)、列數(shù)及非零元素的個數(shù)的特殊三元組（6，6，8）0

1290000

00000-30001400

0240000

18000015

00-7002023/3/7數(shù)據(jù)結構3三元組順序表1、存儲定義:#defineSMAX100/*允許的最大非零元素個數(shù)*/typedefstruct{inti,j;/*非零元素的行號和列號*/elementypev;/*非零元素的值*/}triple;typedefstruct{intmu,nu,tu;tripledata[SMAX];}spmatrix;2023/3/7數(shù)據(jù)結構40022015011300000060000000091000000028000150009100110000030002822060000000001500000MN668111514221615221123334651916328(a)矩陣M的三元組順序表(b)轉置矩陣N的三元組順序

6681115159122113233628412243661152023/3/7數(shù)據(jù)結構5（1）按b.data中三元組的次序進行轉置。也就是說，按照矩陣M的列序進行轉置。a和b分別表示稀疏矩陣M和N，N是M的轉置矩陣?，F(xiàn)在問題實際上是已知a，求b。假設t為矩陣中非零元素個數(shù)，p指示a.data中三元組的序號的變化，q指示b.data中三元組的序號的變化，其變化范圍均從1至t，col指示M的列號既然已經用三元組保存了稀疏矩陣，節(jié)省了空間，那么用三元組來存儲稀疏矩陣就會流行起來，但是，我現(xiàn)在要對剛才那個稀疏矩陣做轉置運算，請想個簡單的辦法。干嗎不直接轉置，直接將三元組中行列數(shù)字換位？2023/3/7數(shù)據(jù)結構6inttransmat(spmatrixa;spmatrix&b){intp,q,col;b.mu=a.nu;b.nu=a.mu;b.tu=a.tu;t=a.tu;if(t){

q=1;for(col=1;col<=a.nu;col++)for(p=1;p<=t;p++)

if(a.data[p].j==col)

/*按a列號由小到大的順序進行轉置*/{b.data[q].j=a.data[p].i；

b.data[q].i=a.data[p].j；

b.data[q].v=a.data[p].v；

q++;}}return(1);}算法的執(zhí)行時間為O(n×t)當非零元素個數(shù)t的量級為m×n時，其執(zhí)行時間便成為O(m×n2)2023/3/7數(shù)據(jù)結構7(2)按照a.data中三元組的次序進行轉置。轉置后的元素不連續(xù)存放，直接放到b.data中最終的位置上。

需設置兩個數(shù)組num[n]和pot[n]num[col]表示矩陣M中第col列中非零元素的個數(shù)；

pot[col]初值表示M中第col列的第1個非零元素在b.data中的位置。

pot[1]=1pot[col]=pot[col-1]+num[col-1]M矩陣的num和pot值col123456num[col]212201pot[col]1346882023/3/7數(shù)據(jù)結構8intfasttran(spmatrixa，spmatrix&b){intnum[a.nu+1]，pot[a.nu+1]；/*num[0]和pot[0]未被使用*/

intt,p,q,col,k；

b.mu=a.nu;b.nu=a.mu;b.tu=a.tu;t=a.tu;if(t){for(col=1;col<=a.nu;col++)num[col]=0;

/*初始化*/for(k=1;k<=t;k++)

/*求M每一列的非零元素的個數(shù)*/num[a.data[k].j]++;pot[1]=1;2023/3/7數(shù)據(jù)結構9for(col=2;col<=a.nu;col++)/*求第col列中第一個非零元素的在b.data中的序號*/pot[col]=pot[col-1]+num[col-1];for(p=1;p<=t;p++)/*轉置*/{col=a.data[p].j;q=pot[col];b.data[q].j=a.data[p].i；

b.data[q].i=a.data[p].j；

b.data[q].v=a.data[p].v；

pot[col]++；

}}renturn(1);}算法的執(zhí)行時間為O(n+t)

2023/3/7數(shù)據(jù)結構10

若采用三元組壓縮技術存儲稀疏矩陣，只要把每個元素的行下標和列下標互換，就完成了對該矩陣的轉置運算，這種說法正確嗎？

提問：思考2023/3/7數(shù)據(jù)結構11答：肯定不正確！除了：（1）每個元素的行下標和列下標互換（即三元組中的i和j互換）；還需要：（2）T的總行數(shù)md和總列數(shù)nd也要互換；（3）重排三元組內各元素順序，使轉置后的三元組也按行（或列）為主序有規(guī)律的排列。上述（1）和（2）容易實現(xiàn)，難點在（3）。2023/3/7數(shù)據(jù)結構12

自己構造兩個稀疏矩陣，并用三元組表達，請寫出利用三元組實現(xiàn)稀疏矩陣和的算法。想一想：三元組a,三元組b，誰和誰相加？假如生成的矩陣還用三元組表示，這個三元組多大？2023/3/7數(shù)據(jù)結構132.數(shù)組的鏈式存儲結構1、三元組順序表的不足在進行加法、減法、乘法等運算時，不僅矩陣中非零元素的位置會發(fā)生變化，其個數(shù)也經常改變，所以，這種表示稀疏矩陣的順序存入方案，與其他順序分配一樣，有其固有的缺點，2023/3/7數(shù)據(jù)結構142、十字鏈表結構(orthogonallist)（1）稀疏矩陣的每一行用一個鏈表表示，每一列也用一個鏈表表示。行鏈表和列鏈表呈十字交叉狀，故起名十字鏈表。（2）在鏈表中除表頭結點外，每個結點都表示矩陣中的一個非零元素。（3）十字鏈表中每個結點都由5個域組成：行域(row)，列域(col)，值域(val)，向下域(down)和向右域(right)。2023/3/7數(shù)據(jù)結構15十字鏈表結點結構的描述如下：

typedefstructolnode/*定義結點結構*/{introw,col;/*非零元素的行和列*/elementypeval;/*非零元素的值*/structolnode*right,*down;/*行和列鏈表的指針*/}olnode,*olink;typedefstructcrosslist/*定義十字鏈表結構*/{intmu,nu,count;/*定義數(shù)組的行數(shù)、列數(shù)和非零元素的個數(shù)*/structolnode*rowheat[],*colheat[];/*行頭指針數(shù)組和列頭指針數(shù)組*/}crosslist;

對于下面的3×4的稀疏矩陣MM=2500640-80020000列頭指針數(shù)組行

頭指針數(shù)組1125120∧

∧2-8∧

∧464∧

∧

∧2023/3/7數(shù)據(jù)結構17

（１）數(shù)組在高級程序設計語言中表示一種數(shù)據(jù)類型。高級語言中的數(shù)組在計算機內是用一批連續(xù)的存儲單元來表示的，稱為數(shù)組的順序存儲結構；（２）在數(shù)據(jù)結構中討論的是數(shù)組的邏輯結構和存儲結構，用戶完全可以根據(jù)需要選擇數(shù)組的其他存儲方式。小結：2023/3/7數(shù)據(jù)結構18（3）各種語言中數(shù)組的表示和下標的設置有一些區(qū)別，尋址公式也不完全相同,務必弄清計