熱點推薦:
您现在的位置: 電腦知識網 >> 編程 >> 數據結構 >> 正文

數據結構考研分類復習真題 第五章 答案[13]

2013-11-15 15:12:39  來源: 數據結構 

  .()k = (i)  (主對角線左下角即i=j+)

  k = (i)+  (主對角線上即i=j)

  k = (i)+  (主對角線上即i=j)

  由以上三式得 k=(i)+j    (?ij?n; ?k?n)

  (*(*)

   稀疏矩陣A采用二維數組存儲時需要n*n個存儲單元完成求Σaii(<=i<=n)時由於a[i][i]隨機存取速度快但采用三元組表時若非零元素個數為t(t+)個存儲單元(第一個分量中存稀疏矩陣A的行數列數和非零元素個數以後t個分量存各非零元素的行值列值元素值)比二維數組節省存儲單元但在求Σaii(<=i<=n)時要掃描整個三元組表以便找到行列值相等的非零元素求和其時間性能比采用二維數組時差

   特殊矩陣指值相同的元素或零元素在矩陣中的分布有一定規律因此可以對非零元素分配單元(對值相同元素只分配一個單元)將非零元素存儲在向量中元素的下標i和j和該元素在向量中的下標有一定規律可以用簡單公式表示仍具有隨機存取功能而稀疏矩陣是指非零元素和矩陣容量相比很小(t<<m*n)且分布沒有規律用十字鏈表作存儲結構自然失去了隨機存取的功能即使用三元組表的順序存儲結構存取下標為i和j的元素時要掃描三元組表下標不同的元素存取時間也不同最好情況下存取時間為O()最差情況下是O(n)因此也失去了隨機存取的功能

[]  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  


From:http://tw.wingwit.com/Article/program/sjjg/201311/23050.html
    推薦文章
    Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.