題目 1694:
數(shù)據(jù)結(jié)構(gòu)-行邏輯鏈接的矩陣乘法
時(shí)間限制: 2s
內(nèi)存限制: 96MB 提交: 99 解決: 54
題目描述
對(duì)于一個(gè)稀疏矩陣，當(dāng)需要頻繁的隨機(jī)存取任意一行的非零元時(shí)，則需要知道每一行的第一個(gè)非零元在三元組表中的位置。為此，可以將算法5.2中用來(lái)指示“行”信息的輔助數(shù)組cpot固定在稀疏矩陣的存儲(chǔ)結(jié)構(gòu)中。這種“帶行鏈接信息”的三元組表即為行邏輯鏈接的順序表。其類型描述如下：
針對(duì)存儲(chǔ)于行邏輯鏈接順序表的稀疏矩陣，其矩陣相乘的算法與經(jīng)典算法有所不同。因此，對(duì)于兩個(gè)稀疏矩陣相乘(Q=M×N)的過(guò)程可以大致描述如下：
請(qǐng)使用行邏輯鏈接的順序表實(shí)現(xiàn)兩個(gè)稀疏矩陣的乘法。
輸入格式
輸入的第一行是兩個(gè)整數(shù)r1和c1（r1<200, c1<200, r1*c1 <= 12500），分別表示一個(gè)包含很多0的稀疏矩陣的行數(shù)和列數(shù)。接下來(lái)有r1行，每行有c1個(gè)整數(shù)，用空格隔開(kāi)，表示第一個(gè)稀疏矩陣的各個(gè)元素。
之后的一行有兩個(gè)整數(shù)r2和c2（c1=r2<200, c2<200, r2*c2 <= 12500），分別表示一個(gè)包含很多0的稀疏矩陣的行數(shù)和列數(shù)。接下來(lái)有r2行，每行有c2個(gè)整數(shù)，用空格隔開(kāi)，表示第二個(gè)稀疏矩陣的各個(gè)元素。
輸出格式
輸出兩個(gè)矩陣的乘積。輸出共有r1行，每行有c2個(gè)整數(shù)，每個(gè)整數(shù)后輸出一個(gè)空格。請(qǐng)注意行尾輸出換行。
樣例輸入
4 5 0 0 0 69 78 0 0 5 0 0 0 0 0 0 0 0 91 2 0 82 5 6 0 18 0 0 0 0 0 0 67 0 0 0 0 0 0 0 0 41 0 0 47 62 0 0 0 0 0 0 0 35
樣例輸出
0 0 3243 4278 0 2730 0 0 0 0 0 205 0 0 0 0 0 0 0 0 6097 0 0 2952
提示
零基礎(chǔ)同學(xué)可以先學(xué)習(xí)視頻課程，包含C/C++、Python、百練、藍(lán)橋杯輔導(dǎo)、算法數(shù)據(jù)結(jié)構(gòu)等課程，提供視頻講解以及配套習(xí)題，還有老師答疑，點(diǎn)擊這里了解課程詳情