数组寻址与特殊矩阵压缩

考点定位

本课深化 数组寻址与特殊矩阵压缩。408作答必须同时给出数据结构表示、算法过程、不变量、复杂度和边界条件。

结构与取舍

多维数组地址由存储次序和各维跨度决定；对称、三角、带状和稀疏矩阵的压缩公式不同，先画出被保存区域。

算法推演

下三角矩阵按行压缩、0下标时，i≥j元素a[i,j]的位置k=i(i+1)/2+j；上三角或列优先必须重新推导。

把算法写成“初始化—循环条件—状态更新—终止输出”。若使用递归、队列、堆或并查集，要指出其中保存的状态及何时失效。

正确性不变量

压缩位置编号在每行起点连续，并且最后一个保存位置等于元素总数减一。

初始化时不变量成立；一次迭代保持它；循环结束时它与终止条件共同推出答案。这是算法题证明的最短主线。

复杂度与边界

时间复杂度必须按输入规模和存储结构计算，不能只报结论。严格边界：行优先与列优先公式不能仅交换字母后机械套用。

随课应用

下三角矩阵按行压缩并从0编号，元素a[4,2]的压缩下标是多少？

先独立计算或编码，再完成单选与多选。代码题从标准输入读取并写到标准输出，不得硬编码样例；数值题需写出中间状态。