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

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

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

  .(    (     ()i=j=即A[

       . k=i(i)/+j

   稀疏矩陣A有t個非零元素加上行數mu列數nu和非零元素個數tu(也算一個三元組)共占用三元組表LTMA的(t+)個存儲單元用二維數組存儲時占用m*n個單元只有當(t+)<m*n時用LTMA表示A才有意義解不等式得t<m*n/

  .參見

   題中矩陣非零元素用三元組表存儲查找某非零元素時按常規要從第一個元素開始查找屬於順序查找時間復雜度為O(n)若使查找時間得到改善可以建立索引將各行行號及各行第一個非零元素在數組B中的位置(下標)偶對放入一向量C中若查找非零元素可先在數組C中用折半查找到該非零元素的行號並取出該行第一個非零元素在B中的位置再到B中順序(或折半)查找該元素這時時間復雜度為O(logn)

  .(      (     (

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


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