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

　　（）k=(nj+)(j)/+ij+    （當i≥j時本題n=）

　　k=(ni+)(i)/+ji+    （當i<j時本題n=）

　　（）稀疏矩陣的三元組表為s=(()()()()()()()其中第一個三元組是稀疏矩陣行數列數和非零元素個數其它三元組均為非零元素行值列值和元素值

　　（）k=（i）+j  （≤ij≤n|ij|≤）

　　i=floor（k/）+   // floor（a）是取小於等於a的最大整數

　　j=k（i）

　　推導過程見上面第題

　　（）行邏輯鏈接順序表是稀梳矩陣壓縮存儲的一種形式為了隨機存取任意一行的非零元需要知道每一行第一個非零元在三元組表中的位置為此除非零元的三元組表外還需要一個向量其元素值是每行第一個非零元在三元組表中的位置其類型定義如下

　　typedef struct
　　{ int munutu;       //稀梳矩陣的行數列數和非零元素個數
　　int rpos[maxrow+];  //行向量其元素值是每行第一個非零元在三元組表中的位置
　　Triple data[maxsize];
　　}SparsMatrix;

　　因篇幅所限不再畫出行邏輯鏈接順序表

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

From:http://tw.wingwit.com/Article/program/sjjg/201311/23057.html