三角矩阵存储优化与数组特性分析

"三角矩阵-数据结构课件" 在数据结构中，三角矩阵是一种特殊类型的矩阵，其特点是除了对角线及其上方（或下方）的数据元素外，其他位置的元素都为常数c。这种矩阵在存储时可以利用这个特性来节省空间。通常，三角矩阵的存储方式是重复元素c只占用一个存储空间，因此总共需要n(n+1)/2+1个元素空间。存储布局可以表示为： ``` a11 0 0 …….. 0 a21 a22 0 …….. 0 an1 an2 an3…….. ann …………………. 0 ``` 其中，`Loc(aij)` 表示元素 `aij` 的位置，计算公式为 `Loc(a11)+[(i-1)(i-2)/2+(j-1)]*l`。这里的 `l` 是每个元素的大小，对于整型数据通常是1。 数组是数据结构中的基础概念，可以视为一种特殊的线性表，其中每个元素本身也是一个线性表。数组有以下几个特点： 1. 数组的维数确定后，数据元素的数量和它们之间的相对位置固定不变。 2. 所有元素具有相同的类型，即数据元素同构。 3. 主要的运算包括通过下标访问元素和修改元素的值。 数组的顺序存储结构是指数组在内存中的连续存储，常见的有行序为主序和列序为主序两种存储方式。行序为主序意味着按照从左到右、从上到下的顺序存储，而列序为主序则是先存储所有第一列的元素，再存储第二列，以此类推。 例如，一个m×n的矩阵按照行序为主序存储时，元素 `aij` 的位置可以由公式 `Loc(aij)=Loc(a11)+(i-1)*n+(j-1)` 计算得到。而按照列序为主序，元素的位置则变为 `Loc(aij)=Loc(a11)+(j-1)*m+(i-1)`。 在不同的编程语言中，如BASIC、PASCAL、COBOL、C等，通常采用行序为主序分配，而FORTRAN则使用列序为主序。 在算法设计中，例如寻找矩阵的鞍点（一个元素既是其行的最小值又是其列的最大值），可以采用遍历每行并找到最小值，然后检查该最小值是否也是其列的最大值的方法。以下是一个简单的算法示例： ```c void saddle(int A[][], int m, int n) { int i, j, min; for (i = 0; i < m; i++) { min = A[i][0]; for (j = 1; j < n; j++) { if (A[i][j] < min) { min = A[i][j]; } } // 检查min是否是列的最大值 for (j = 0; j < n; j++) { if (A[j][i] == min && A[j][i] > A[i][j]) { printf("鞍点: %d, 位置 (%d,%d)\n", min, i, j); } } } } ``` 这个算法首先遍历矩阵的每一行，找到每行的最小值，然后检查这个最小值是否大于同一列的其他元素，如果满足条件，则找到了一个鞍点。