第6章 数组和特殊矩阵.pptx

第6章 数组和特殊矩阵喜欢老家的坝坝宴，接地气而实惠，最主要的是能吃到小时候的味道。每回，好吃的作者在开席前都要跑到厨房去瞅瞅，丰富的菜品一排一列摆得整整齐齐真壮观！真诱人！这是数组，这是矩阵啊！本章讲解数组和特殊矩阵。要求理解数组和特殊矩阵的概念；掌握数组的存储结构和基本操作算法；理解特殊矩阵的压缩存储算法；灵活应用数组，了解特殊矩阵的应用。提纲6.1 数组基本概念6.2 数组存储结构6.3 数组基本操作6.4 数组应用6.5 特殊矩阵基本概念6.6 特殊矩阵压缩存储6.7 特殊矩阵应用6.8 数组和特殊矩阵学习总结6.1 数组基本概念?数组是由相同类型元素构成的有限集合。是一个二元组（idx，value）的集合，对每个下标idx，都有一个value值与之对应，下标含有d（）个整数称为维数是d。6.1 数组基本概念数组分为1维数组、2维数组和多维数组。2维数组可以看作其元素是1维数组构成的数组，3维数组可以看作其元素是2维数组构成的数组，依此类推。6.2 数组存储结构1维数组的存储结构1维数组所有元素依逻辑次序存放在一片连续的内存单元中，其起始地址为第1个元素a0的地址记为LOC(a0)，假设每个元素占用k个存储单元，则元素ai的存储地址LOC(ai)可由以下公式求出：LOC(ai)=LOC(a0)+i×k （1≤in）由此可见，1维数组具有随机存取特点。6.2 数组存储结构2.2维数组的存储结构2维数组的存储可以分为按行优先存储和按列优先存储。6.2 数组存储结构（1）按行优先存储按行优先存储是指2维数组中的元素按照从左到右、从上到下的顺序进行存储：a0,0 a0,1 ...a0,n-1 a1,0 a1,1 ...a1,n-1 ...am-1,0 am-1,1 ...am-1,n-1。元素ai,j的存储地址LOC(ai,j)可由以下公式求出：LOC(ai,j)=LOC(a0,0) + (i×n + j)×k（ai,j元素前面有i行（0到i-1））n列，第i行中其前面有j（0到j-1）个元素）6.2 数组存储结构（2）按列优先存储按列优先存储是指2维数组中的元素按照从上到下、从左到右的顺序进行存储：a0,0 a1,0 ...am-1,0 a0,1 a1,1 ...am-1,1 ...a0,n-1 a1,n-1 ...am-1,n-1。元素ai,j的存储地址LOC(ai,j)可由以下公式求出：LOC(ai,j)=LOC(a0,0) + (j×m + i)×k（ai,j元素前面有j列（0到j-1））m行，第j列中其上面有i（0到i-1）个元素）6.3 数组基本操作数组的操作包含创建、初始化、插入、查找、更新、删除、清空、判空等操作，同顺序表的操作，详见第2章2.2.2顺序表类SeqList和算法2.1至2.4。6.4 数组应用【例6.1】求含有n个元素的1维整型数组a中任意2个元素差的绝对值的最小值。思路：（1）将数组a的所有元素递增排序；（2）求两两元素差的绝对值； （3）比较这些绝对值，输出最小的绝对值。代码见应用6.16.4 数组应用【进一步思考】例6.1算法若不使用排序，其实现思路是什么。答：（1）求出所有差值的绝对值，当计算出来是0时直接返回输出，否则执行（2）；（2）将这些绝对值放到另1个数组中；（3）求这个数组的最小元素并输出之。6.4 数组应用【例6.2】将1个n阶2维整型数组a的所有元素转置。思路：以2维数组的主对角线为中心线，交换两边的对称元素，即交换a[i][j]和a[j][i]。代码见应用6.26.4 数组应用?【进一步思考】例6.2算法，若2维数组中已经有些元素关于主对角线对称，请说说例6.2算法的改进思路。答：在交换之前做个条件判断，若，再做交换。6.4 数组应用?【例6.3】求2维数组A[n,n]2条对角线元素之和。思路：（1）先求主对角线元素累加之和sum1，再求副对角线元素累加之和sum2；（2）求；（3）若n为奇数，从sum中减掉主对角线和副对角线重复的元素值；（4）返回sum。代码见应用6.36.4 数组应用?【进一步思考】例6.3算法若用递归算法求解，请写出递归模型？答：设f(A,n)表示2维数组A[n][n]返回主对角线和副对角线元素之和的函数，递归模型如下：（其中A为除掉A的第1行和第1列的2维数组）6.4 数组应用?【例6.4】用递归算法求整数数组a[0...n-1]中的最大值。思路：设f(a,i)表示求数组a[0...i]中的最大值函数，建立递归模型如下：代码见应用6.46.4 数组应用【进一步思考】例6.4算法改成求最小值，代码如何修改？答：将Math类中的max函数换成min函数。6.5 特殊矩阵基本概念?上三角部分，主对角线部分，下三角部分。6.5 特殊矩阵基本概念各种特殊矩