第6章 数组和特殊矩阵

第6章数组和特殊矩阵本章讲解数组和特殊矩阵。要求理解数组和特殊矩阵的概念；掌握数组的存储结构和基本操作算法；理解特殊矩阵的压缩存储算法；灵活应用数组，了解特殊矩阵的应用。喜欢老家的坝坝宴，接地气而实惠，最主要的是能吃到小时候的味道。每回，好吃的作者在开席前都要跑到厨房去瞅瞅，丰富的菜品一排一列摆得整整齐齐真壮观！真诱人！这是数组，这是矩阵啊！提纲6.1数组基本概念6.2数组存储结构6.3数组基本操作6.4数组应用6.5特殊矩阵基本概念6.6特殊矩阵压缩存储6.7特殊矩阵应用6.8数组和特殊矩阵学习总结6.1数组基本概念

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≤i<n）由此可见，1维数组具有随机存取特点。6.2数组存储结构2.2维数组的存储结构2维数组的存储可以分为按行优先存储和按列优先存储。6.2数组存储结构（1）按行优先存储按行优先存储是指2维数组中的元素按照从左到右、从上到下的顺序进行存储：a0,0a0,1...a0,n-1a1,0a1,1...a1,n-1...am-1,0am-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,0a1,0...am-1,0a0,1a1,1...am-1,1...a0,n-1a1,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.4数组应用

6.4数组应用

6.4数组应用

6.4数组应用【进一步思考】例6.4算法改成求最小值，代码如何修改？答：将Math类中的max函数换成min函数。6.5特殊矩阵基本概念

6.5特殊矩阵基本概念各种特殊矩阵举例：6.6特殊矩阵压缩存储对于上述的特殊矩阵，在计算机中又是如何存储的呢？这里先要搞清楚2个问题：第1，它们都是非线性结构，如何存储呢？第2，它们的特点是否决定了不必存储所有的元素？对于第1个问题，我们可以将这些矩阵线性化，再进行存储；对于第2个问题，答案是肯定的，即我们可以通过压缩算法对这些矩阵进行压缩存储以节省空间。6.6.1对称矩阵压缩存储对称矩阵的压缩存储是指通过压缩算法将1个对称矩阵A存储到1个1维数组B中，存储的元素是上/下三角部分加主对角线上的元素。6.6.1对称矩阵压缩存储

6.6.2三角矩阵压缩存储三角矩阵的压缩存储是指通过压缩算法将1个三角矩阵A存储到1个1维数组B中，存储的元素是上/下三角部分加主对角线上的元素和常量C。6.6.2三角矩阵压缩存储

6.6.3对角矩阵压缩存储对角矩阵的压缩存储是指通过压缩算法将1个对角矩阵A存储到1个1维数组B中，存储的元素是非0元素。6.6.3对角矩阵压缩存储

6.6.4稀疏矩阵压缩存储3元组稀疏矩阵的3元组存储方式是将矩阵中的非0元素的行号、列号及元素值存入到1个3元组（i,j,ai,j）中。6.6.4稀疏矩阵压缩存储2.十字链表稀疏矩阵的十字链表存储方式是稀疏矩阵的链式存储方式。（1）十字链表中结点的相对位置同对应的矩阵；（2）down和right指针，若向下和向右无非零元素，则回指向头结点，否则指向所在列和行的元素；（3）行和列皆为循环单链表结构。6.7特殊矩阵应用【例6.6】求1个3元组表示为a的稀疏矩阵的转置矩阵的3元组表示b。思路：（1）按列号顺序遍历a，构造行/列号相反顺序的3元组元素；（2）将该元素添加到b的3元组集合中；（3）