716-本章导读 数组是一种常用的数据结构。数组分为静态存储结构的数组.ppt

第5章 数组 5.1 数组的基本概念 １、一维数组（n个元素）中任一元素ai的内存单元地址 　　 Loc(ai)=LOC(a０)+i*k (0≤i n) ２、一个m行n列的二维数组 　　LOC(aij)=LOC(a00)+(i*n+j)*k (0≤im，0≤jn) 注：C++语言中数组元素采用行主序的存放方法，即行优先顺序。 5.2 动态数组类 void main(void) { Arrayint a(10); int n = 10; for(int i = 0; i n; i++) a[i] = i + 1; cout a[6] = a[6] endl; cout Size of a = a.Size( ) endl; Arrayint b = a; cout b[6] = b[6] endl; cout Size of b = b.Size( ) endl; a.Resize(40); a[21] = 21; cout a[21] = a[21] endl; cout Size of a = a.Size( ) endl; Arrayint c(a); cout c[21] = c[21] endl; cout Size of c = c.Size( ) endl; } 5.3 特殊矩阵 5.4 稀疏矩阵 2. 三元组顺序表类 (1)三元组顺序表 指用顺序表存储的三元组线性表。 把三元组定义成顺序表的数据元素： struct DataType { int row; //行号 int col; //列号 ElemType value; //元素值 } ; ostream operator (ostream out, const SeqSynmeMatrix a) //输出流运算符重载 { cout 对称矩阵阶数为： a.n endl; cout 矩阵元素为： endl; ? int i, j, k = 0, n = a.n; for(i = 1; i = n; i++) { for(j = 1; j = n; j++) if(i = j) { k = i * (i - 1) / 2 + j - 1; cout setw(5) a.list[k]; } else { k = j * (j - 1) / 2 + i - 1; cout setw(5) a.list[k]; } cout endl; } return out; } 例5-3 设计一个测试n阶对称矩阵顺序表类的测试程序。 #include iostream.h #include iomanip.h//包含setw() #include stdlib.h typedef int DataType; #include SeqSynmeMatrix.h void main(void) { SeqSynmeMatrix matrixA(10), matrixB(10); DataType a[] = {1,4,7,4,5,8,7,8,9}; DataType b[] = {2,4,3,4,5,6,3,6,9}; int n = 3; matrixA.CreateMatrix(n, a); matrixB.CreateMatrix(n, b); matrixA.Add(matrixB); cout matrixA; } 代码 1.概念 1、稀疏矩阵 矩阵中非零元素的个数远远小于矩阵元素个数。 2、稠密矩阵 一个不稀疏的矩阵。 3、稀疏矩阵压缩存储方法 只存储稀疏矩阵中的非零元素，实现方法是:将每个非零元素用一个三元组（i，j，aij）来表示，则每个稀疏矩阵可用一个三元组线性表来表示。 例1：写出下图5.3所示稀疏矩阵的压缩存储形式。 1 2 3 4 5 6 1 2 3 4 5 6 解：用三元组线性表表示： {{1,2,12},{1,3,9},{3,1,-3},{3,5,14}, {4,3,24},