高中信息技術(shù)競(jìng)賽班數(shù)據(jù)結(jié)構(gòu)專項(xiàng)培訓(xùn)教程05矩陣的壓縮存儲(chǔ)教案-人教版高中全冊(cè)信息技術(shù)教案

§5矩陣的壓縮儲(chǔ)存5.1特別矩陣三角矩陣與對(duì)稱矩陣設(shè)有矩陣A:array[1..n,1..n]ofAtype三角矩陣：若A的對(duì)角線以上（或以下）的元素均為零。對(duì)稱矩陣：若A中的元素知足：aij=aji（1≤i，≤n），則稱為n階對(duì)稱矩陣。為了節(jié)儉儲(chǔ)存空間，三角矩陣和對(duì)稱矩陣都不需儲(chǔ)存對(duì)角線以上（或以下）的元素，一般采納一維數(shù)組的構(gòu)造。

a110000a21a22000；aa00313233上三角矩陣a11a12a13a14a15a21a22a23a24a25a31a32a33a34a35對(duì)稱矩陣V：12345678910aa21aa31aa33a41aa43a1122324244此時(shí)需要個(gè)元素的儲(chǔ)存空間。若將上三角矩陣中的元素按行次序儲(chǔ)存到V中，則V[k]與A[i,j]的對(duì)應(yīng)關(guān)系是：k=①若將下三角矩陣中的元素按行次序儲(chǔ)存到V中，則V[k]與A[i,j]的對(duì)應(yīng)關(guān)系是：a11a12a13a14a150aaaa2223242500a33a34a35下三角矩陣k=②帶狀矩陣在n×n的矩陣中，若全部非零元素均集中在以對(duì)角線為中的帶狀區(qū)中，該帶狀區(qū)包含主對(duì)角線上邊和下邊各k條對(duì)角線以及主對(duì)角線上的元素，這類矩陣稱帶狀矩陣。條對(duì)角線1123000條對(duì)角線主對(duì)角線

421013005127680201791115k=2的帶狀矩陣在帶狀矩陣A中，i–j>k或③時(shí)，A[i,j]=0。關(guān)于帶狀區(qū)之外的0元素可不用儲(chǔ)存，而只儲(chǔ)存帶狀區(qū)中的元素。帶狀區(qū)中有④個(gè)元素，但為了方便起見，每行看作2k+1個(gè)元向來存儲(chǔ)，此時(shí)儲(chǔ)存的元素個(gè)數(shù)為(2k+1)×n個(gè)?！緟⒄沾鸢浮浚篿×(i-1)/2+j(n+(n-i+1))×(i-1)+(j-i+1)j-i>k④n×n–(n-k)×(n–k–1)§5.2稀少矩陣大部分元素的值為零的矩陣稱為稀少矩陣，為了節(jié)儉儲(chǔ)存空間，能夠采納三元組或十字鏈表等方法來儲(chǔ)存。§三元組表示法三元組表示法是用三元組（i,j,v）表示矩陣的每個(gè)非零元素。第一行的i,j,v分別表示矩陣A的行數(shù)、列數(shù)、非零元素個(gè)數(shù)，第二行開始的i,j,v分別表示矩陣A中每個(gè)非零元素的行下標(biāo)、列下標(biāo)、元素的值。【例5.2_1】1500220－6681511150113000A=000－6001422T=00000016-15910000022110028000233§三元組矩陣轉(zhuǎn)置對(duì)矩陣的運(yùn)算有很多，如兩個(gè)矩陣相加、相乘、轉(zhuǎn)置等。轉(zhuǎn)置是一種簡(jiǎn)單的矩陣運(yùn)算，關(guān)于一個(gè)m×n的矩陣M，它的轉(zhuǎn)置矩陣N是一個(gè)n×m的矩陣，且M（i,j）＝N（j,i）。【例5.2_2】14Ｍ＝123N＝25這里只議論三元組的轉(zhuǎn)置算法。三元組的轉(zhuǎn)置只要做到：1）將三元組中的隊(duì)列值互相互換；2）將i、j互相調(diào)動(dòng)；3）重排三元組中的序次便可實(shí)現(xiàn)三元組的矩陣轉(zhuǎn)置。這里重點(diǎn)是怎樣重排三元組里的序次。668668668111511151115142241221591T==>B=16-1561-152211221122113232333233628矩陣相乘兩個(gè)矩陣相乘是另一種常用的矩陣運(yùn)算。設(shè)：C＝A×BA=(aij)為m×s的矩陣，B=(bij)是s×n的矩陣，則矩陣A與矩陣B相乘將獲得一個(gè)m×n的矩陣C=(cij)，此中cij＝ai1b1j+ai2b2j++aisbsj（i=1,2,,mj=1,2,,n）關(guān)于非壓縮矩陣，算法以下：fori:=1tomdoforj:=1tondobeginC[i,j]:=0；fork:=1tosdoC[i,j]:=C[i,j]+A[i,k]*B[k,j]；end；當(dāng)A和B是稀少矩陣，并分別用三元組M、N儲(chǔ)存時(shí)，應(yīng)怎樣辦理？注意1：兩個(gè)稀少矩陣相乘的積不必定是稀少矩陣；2：即便cij＝ai1b1j+ai2b2j++aisbsj中的每個(gè)分項(xiàng)aikbkj均不為零，其累加值Cij也有可能為零。【練習(xí)】輸入M、N兩個(gè)三元組，分別表示A、B兩個(gè)稀少矩陣，請(qǐng)計(jì)算A、B的乘積C，輸出C的（壓縮儲(chǔ)存）三元組Y。輸入格式：（輸入文件syz.in）第1行：i1j1v1(分別表示A的行數(shù)、列數(shù)、非零元素個(gè)數(shù))第2至v1+1行：aiajav(行下標(biāo)、列下標(biāo)、元素的值)第v1+2行：i2j2v2(B的行數(shù)、列數(shù)