资源描述：
《数据结构名师课件2》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第五章数组和广义表5.1数组一、定义——一维数组是相同类型的变量的有限序列。1．一维数组一维数组可以看成是一个线性表或一个向量（第2章已经介绍），它在计算机内是存放在一块连续的存储单元中，适合于随机查找。2．二维数组二维数组可以看成是向量的推广。例如，设A是一个有m行n列的二维数组，则A可以表示为：数组特点数组结构固定数据元素同构数组运算给定一组下标，存取相应的数据元素给定一组下标，修改数据元素的值二、数组的顺序存储结构（1） 按行优先顺序存放（2） 按列优先顺序存放amn……..am2am1……….a2n……..
2、a22a21a1n…….a12a11a11a12……..a1na21a22……..a2nam1am2……..amn………………….loc(aij)=loc(a11)+[(i-1)n+(j-1)]S按行优先顺序存放amn……..a2na1n……….am2……..a22a12am1…….a21a11a11a12……..a1na21a22……..a2nam1am2……..amn………………….loc(aij)=loc(a11)+[(j-1)m+(i-1)]S按列优先顺序存放矩阵是一个二维数组，它是很多科学与工程计算问题中研究的数
3、学对象。矩阵可以用行优先或列优先方法顺序存放到内存中，但是，当矩阵的阶数很大时将会占较多存储单元。而当里面的元素分布呈现某种规律时，这时，从节约存储单元出发，可考虑若干元素共用一个存储单元，即进行压缩存储。所谓压缩存储是指：为多个值相同的元素只分配一个存储空间，值为零的元素不分配空间。但是压缩存储时，节约了存储单元，但怎样在压缩后找到某元素呢？因此还必须给出压缩前的下标和压缩后下标之间变换公式，才能使压缩存储变得有意义。5.2矩阵的压缩存储1．对称矩阵若一个n阶方阵A中元素满足下列条件：aij=aji其中0≤i,j≤n-1
4、，则称A为对称矩阵。例如，下图是一个3*3的对称矩阵。一、特殊矩阵a11a12….……..a1na21a22……..…….a2nan1an2……..ann………………….a11a21a22a31a32an1ann…...…...k=01234n(n-1)/2n(n+1)/2-1按行序为主序：aij的序号k：2．三角矩阵（1）上三角矩阵即矩阵上三角部分元素是随机的，而下三角部分元素全部相同（为某常数C）或全为0。（2）下三角矩阵即矩阵的下三角部分元素是随机的，而上三角部分元素全部相同（为某常数C）或全为0。a1100……..
5、0a21a220……..0an1an2an3……..ann………………….0a11a21a22a31a32an1ann…...…...k=01234n(n-1)/2n(n+1)/2-1按行序为主序：前i-1行非零元素个数元素aij的序号k为地址loc(aij)=loc(k)=loc(a11)+(k-1)*S下三角上三角3．对角矩阵a11a120…………….0a21a22a230……………000…an-1,n-2an-1,n-1an-1,n00……an,n-1ann.0a32a33a340………0……………………………a11
6、a12a21a22a23ann-1ann…...…...k=01234n(n-1)/2n(n+1)/2-1按行序为主序：aij的序号k＝2i＋j－2loc(aij)=loc(a11)+[2(i-1)n+(j-1)]S二、稀疏矩阵的压缩在上节提到的特殊矩阵中，元素的分布呈现某种规律，故一定能找到一种合适的方法，将它们进行压缩存放。但是，在实际应用中，我们还经常会遇到一类矩阵：其矩阵阶数很大，非零元个数较少，零元很多，但非零元的排列没有一定规律，我们称这一类矩阵为稀疏矩阵。按照压缩存储的概念，要存放稀疏矩阵的元素，由于没有某种
7、规律，除存放非零元的值外，还必须存储适当的辅助信息，才能迅速确定一个非零元是矩阵中的哪一个位置上的元素。M由{(1,2,12),(1,3,9),(3,1,-3),(3,6,14),(4,3,24),(5,2,18),(6,1,15),(6,4,-7)}和矩阵维数（6,7）唯一确定定义：非零元较零元少，且分布没有一定规律的矩阵压缩存储原则：只存矩阵的行列维数和每个非零元的行列下标及其值稀疏矩阵的压缩存储方法顺序存储结构(三元组表)#defineM20typedefstructnode{inti,j;intv;}JD;JDma
8、[M];三元组表所需存储单元个数为3(t+1)其中t为非零元个数678121213931-3361443245218611564-7maijv012345678ma[0].i,ma[0].j,ma[0].v分别存放矩阵行列维数和非零元个数行列下标非零元值求转置矩阵问题描述：已知一个稀疏矩阵的三元组表，求
