第三章数组和广义表.pptVIP

3.1 数组 3.1.1数组的定义和基本操作 1.定义 数组可以看成是一种特殊的线性表，即线性表中数据元素本身也是一个线性表 3.1.2 数组的存储结构 一般都是采用顺序存储的方法来表示数组。 1.数组的顺序存储结构 次序约定 以行序为主序－－行优先 如高级语言BASIC、 COBOL、PASCAL、C语言都是以行序为主 以列序为主序－－列优先 如高级语言中的FORTRAN语言就是以列序为主 1.对称矩阵 例题讲解：求矩阵转置 一般矩阵转置算法： ④输出操作 void print(table *T) /*按矩阵格式输出以压缩方式存储的稀疏矩阵*/ {int i,j,k,e; for(i=0; iT-rownum; i++) { for(j=0; jT-colnum; j++) { e = 0; for(k=0;kT-nznum; k++) if(i==T-data[k].ij==T-data[k].j) { e = T-data[k].e; break; } printf(“%4d”,e); } } } 0 1 12 0 2 9 2 0 3 2 5 1 3 2 24 4 1 18 5 0 5 5 3 7 行列下标 非零元值 i j e 0 1 2 3 4 5 6 7 矩阵M的三元组表 void print(table *T) /*按矩阵格式输出以压缩方式存储的稀疏矩阵*/ { int i,j,k; k=0; for(i=0; iT-rownum; i++) { for(j=0; jT-colnum; j++) if(i==T-data[k].ij==T-data[k].j) { printf(“%4d”, T-data[k]. e); k++; } else printf(“%4d”, 0); printf(“\n”); } } 用两层循环改写上面操作 transpose(int **M, int **N, int m, int n) { int row , col; for(col=0;coln;col++) for(row=0;rowm;row++) N[col][row]=M[row][col]; } T(n)=O(m?n) 稀疏矩阵转置：已知一个稀疏矩阵的三元组表，求该矩阵转置矩阵的三元组表 问题分析 ? 0 2 3 0 5 5 1 0 12 1 4 18 2 0 9 2 3 24 3 5 7 5 2 1 0 1 12 0 2 9 2 0 3 2 5 1 3 2 24 4 1 18 5 0 5 5 3 7 i j e 0 1 2 3 4 5 6 7 M.data i j e 0 1 2 3 4 5 6 7 N.data 解决思路：只要做到 ?将矩阵行、列维数互换 ?将每个三元组中的i和j相互调换 ?重排三元组次序，使N中元素以N的行(M的列)为 主 序 方法一：按M的列序转置（即N的行序） 即按N中三元组次序依次在M中找到相应的三元组进行转置。为找到M中每一列所有非零元素，需对其三元组表M从第一行起扫描一遍。由于M中以M行序为主序