數(shù)據(jù)結(jié)構(gòu)(第3次)(編輯修改稿)
2025-07-14 06:58 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 if(q!=NULL) { pnext=qnext。 rnext=q。 r=q。 p=pnext。 } } rnext=NULL。 } 解題方案：評(píng)分標(biāo)準(zhǔn)：2. 參考答案：轉(zhuǎn)置可按轉(zhuǎn)置矩陣的三元組表中的元素順序進(jìn)行，即按稀疏矩陣的列序。這種方法時(shí)間復(fù)雜度是O(n*t)，當(dāng)t和m*n同量級(jí)時(shí)，時(shí)間復(fù)雜度為O(n3)。另一種轉(zhuǎn)置方法稱作快速轉(zhuǎn)置，使時(shí)間復(fù)雜度降為O(m*n)。需要求出每列非零元素個(gè)數(shù)和每列第一個(gè)非零元素在轉(zhuǎn)置矩陣三元組表中的位置，因此設(shè)置了兩個(gè)附加向量。下面分別給出兩個(gè)算法。TSMatrixTransMatrix(TSMatrixM,TSMatrix N){∥采用三元組表方式存儲(chǔ)，按列序?qū)崿F(xiàn)矩陣的轉(zhuǎn)置=。 =。 =。 ∥行數(shù)、列數(shù)和非零元素個(gè)數(shù) if(){q＝l。 ∥設(shè)置N中第一個(gè)非零元素從下標(biāo)1開(kāi)始存儲(chǔ)for(j＝1。j＜＝。j++) ∥按列， for(p＝1。p＜＝。 ++p) ∥ if([p].col==j) ∥轉(zhuǎn)置{[q].row=[p].col。[q].col=[p].row。[q].e=[p].e。 q++。 }}return N。}∥TransMatrixTSMatrixFastTransMatrix(TSMatrix M, TSMatrix N){∥三元組表上實(shí)現(xiàn)矩陣的快速轉(zhuǎn)置的算法=。 =。 =。if() {for(j=1。j=。j++) numb[j]=0。 ∥矩陣M每一列非零元初始化為零 for(t=1。t=。t++)numb[[t].col]++。∥求矩陣M每一列得非零元個(gè)數(shù)pos[1]=1。 ∥第1列第一個(gè)非零元在轉(zhuǎn)置后的三元組中下標(biāo)是1 for(j=2。j=。j++) ∥pos[col]=pos[col1]+num[col1]。 for(p=1。p=。p++)∥求轉(zhuǎn)置矩陣N的三元組表 {j=[p].col。 q=pos[j]。[q].row=[p].col。 [q].col=[p].row。[q].e=[p].e。 pos[j]++。 ∥同列下一非零元素位置 } }return N。}解題方案：評(píng)分標(biāo)準(zhǔn)：三、簡(jiǎn)答題（20分，共 4 題，每小題 5 分）1. 參考答案：（1）哈夫曼編碼 [P_47E42CBBE4BEF0B3804EEA501687A04A] 根據(jù)上圖可得編碼表： a:1001 b:01 c:10111 d:1010 e:11 f:10110 g:00 h:10
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1