第五章 数组3.20.ppt

5 数组和广义表 主要内容 数组的基本概念 数组的存储结构 矩阵的压缩存储 特殊矩阵 稀疏矩阵 数组的基本概念 数组的定义 数组是下标与值组成的偶对的有穷集合。 数组的基本操作 给定一组下标，存取或修改相应元素的值。 给定一组下标，检索相应的数组元素。 对数组元素进行排序。 数组的存储结构 一维数组A[1:n] A[1..n] = (a1,a2,a3,…,an-1,an) 一维数组的特点 给定一组下标，存取或修改相应元素的值。除了第一个元素外，其他每个元素有且仅有一个直接前驱。 除了最后那个元素外，其他每个元素有且仅有一个直接后继元素。 一维数组的存储 LOC(ai) = LOC(a1) + (i-1) ? k 数组的存储结构 二维数组A[1:m,1:n] 二维数组在内存中的存放 二维数组的“二维”是逻辑上的 内存永远是线性编址 数组的存储结构 二维数组的存储 行序为主序分配方式 特殊矩阵 对称矩阵（即aij=aji,1=i,j=n） k的含义：按行优先，是第k个（从0开始） 三角矩阵 压缩方法和对称矩阵完全相同 稀疏矩阵的顺序存储 三元组(triple)顺序表 #define smax 16 //非0元素个数 typedef struct { int i,j; //行下标、列下标 datatype v; //元素的值 }node; 关键：希望对原三元组表只需扫描一遍 问题：原三元组表中的一个三元组应该放在结果三元组表中的什么位置呢？ 分析：原矩阵第1列只有一条记录，而三元组1是第一个遇到的来自第2列的非零元素，应该放在结果三元组表中的第2个位置 类似的：第1列非零元素有1个，第2列非零元素有2个，而三元组2是第一个遇到的来自第3列的记录，应该放在结果三元组表中的第4个位置 快速转置算法 M 6 6 5 18 2 5 24 3 4 14 6 3 -3 1 3 9 3 1 12 2 1 T 3.让col取M的每一列: for(col=1; col=M.n; col++) 4.让p扫描三元组M的每一条记录: for (p=1; p=M.t; p++) 6 5 6 q col = 1 p M 6 6 5 18 2 5 24 3 4 14 6 3 -3 1 3 9 3 1 12 2 1 T 6 5 6 q col = 1 p 5.如果p指向的记录的j下标与col相等: if (M.data[p].j == col) e j i M 6 6 5 18 2 5 24 3 4 14 6 3 -3 1 3 9 3 1 12 2 1 T 6 5 6 q col = 1 p 6.把M中的记录p复制到T中的记录q: T.data[q].i = M.data[p].j; T.data[q].j = M.data[p].i; T.data[q].v = M.data[p].v; 7.让q下移: q++; 1 3 -3 M 6 6 5 18 2 5 24 3 4 14 6 3 -3 1 3 9 3 1 12 2 1 T 6 5 6 q col = 2 p 1 3 -3 2 1 12 2 5 18 M 6 6 5 18 2 5 24 3 4 14 6 3 -3 1 3 9 3 1 12 2 1 T 6 5 6 q col = 3 p 1 3 -3 2 1 12 2 5 18 3 1 9 3 4 24 …… M 6 6 5 18 2 5 24 3 4 14 6 3 -3 1 3 9 3 1 12 2 1 T 6 5 6 q col = 6 p 1 3 -3 2 1 12 2 5 18 3 1 9 3 4 24 6 3 14 求稀疏矩阵M的转置矩阵T的算法 int TransposeSMatrix(TSMatrix M, TSMatrix *T) { int p, q, col; T-m=M.n; T-n=M.m; T-t=M.t; if(T-t) { q=1; for (col=1;col=M.n;col++) for (p=1;p=M.t;p++) if(M.data[p].j==col) { T-data[q].i=M.data[p].j; T-data[q].j=M.data[p].i; T-data[q].v=M.data[p].v;