【简答题】特殊矩阵和稀疏矩阵哪一种压缩存储后失去随机存取的功能？为什么？
已帮助 人
回答
共1条回复-
特殊矩阵指值相同的元素或零元素在矩阵中的分布有一定规律,因此可以对非零元素分配单元(对值相同元素只分配一个单元),将非零元素存储在向量中,元素的下标i和j和该元素在向量中的下标有一定规律,可以用简单公式表示,仍具有随机存取功能。而稀疏矩阵是指非零元素和矩阵容量相比很小(t<<m*n),且分布没有规律。用十字链表作存储结构自然失去了随机存取的功能。即使用三元组表的顺序存储结构,存取下标为i和j的元素时,要扫描三元组表,下标不同的元素,存取时间也不同,最好情况下存取时间为O(1),最差情况下是O(n),因此也失去了随机存取的功能。