第五章数组PPT讲稿.ppt
第五章数组第五章数组第1页，共22页，编辑于2022年，星期三2数组的定义数组的定义数组结构可以简单地定义为：若线性表中的数数组结构可以简单地定义为：若线性表中的数据元素为非结构的简单元素，则称为一维数组，即据元素为非结构的简单元素，则称为一维数组，即为向量；若一维数组中的数据元素又是一维数组结为向量；若一维数组中的数据元素又是一维数组结构，则称为二维数组；依次类推，若二维数组中的构，则称为二维数组；依次类推，若二维数组中的元素又是一个一维数组结构，则称作三维数组。元素又是一个一维数组结构，则称作三维数组。结论：线性表结构是数组结构的一个特例，而数组结论：线性表结构是数组结构的一个特例，而数组结构又是线性表结构的扩展。结构又是线性表结构的扩展。第2页，共22页，编辑于2022年，星期三3()()()()()()()()()二维数组二维数组数组数组A A可以看成一个线性表：可以看成一个线性表：A=(0A=(0，1 1，.，k)k)（k=m-1k=m-1或或n-1n-1）其中每一个数据元素其中每一个数据元素i i 是由第是由第i i行行元素组成的一维数组，即一个行向量元素组成的一维数组，即一个行向量的线性表。的线性表。i=(ai0 i=(ai0，ai1 ai1，.，ai,n-1)ai,n-1)0im-10im-1或或jj是由第是由第j j列元素组成的一维数组，列元素组成的一维数组，即一个列向量的线性表。即一个列向量的线性表。第3页，共22页，编辑于2022年，星期三4数组的特点及运算数组的特点及运算数组特点数组特点l数组结构固定数组结构固定l数据元素同构数据元素同构数组运算数组运算l给定一组下标，存取相应的数据元素给定一组下标，存取相应的数据元素l给定一组下标，修改数据元素的值给定一组下标，修改数据元素的值l数组一般不做插入或删除操作数组一般不做插入或删除操作第4页，共22页，编辑于2022年，星期三5次序约定次序约定l以行序为主序l以列序为主序a11a12.a1na21a22.a2nam1am2.amn.Loc(aij)=Loc(a11)+(i-1)n+(j-1)*l按行序为主序存放按行序为主序存放amn.am2am1.a2n.a22a21a1n.a12a1101n-1m*n-1n数数组组的的顺顺序序存存储储结结构构按列序为主序存放按列序为主序存放01m-1m*n-1mamn.a2na1n.am2.a22a12am1.a21a11a11a12.a1na21a22.a2nam1am2.amn.Loc(aij)=Loc(a11)+(j-1)m+(i-1)*l第5页，共22页，编辑于2022年，星期三6矩阵的压缩存储方法矩阵的压缩存储方法压缩存储压缩存储是指为多个值相同的元素只分配一个是指为多个值相同的元素只分配一个存储空间；对零元素不分配空间。存储空间；对零元素不分配空间。第6页，共22页，编辑于2022年，星期三7a11a12.a1na21a22.a2nan1an2.ann.a11a21a22a31a32an1ann.k=01234n(n-1)/2n(n+1)/2-1按行序为主序：按行序为主序：对称矩阵的压缩存储方法对称矩阵的压缩存储方法第7页，共22页，编辑于2022年，星期三8a1100.0a21a220.0an1an2an3.ann.0Loc(aij)=Loc(a11)+(+(j-1)*li(i-1)2a11a21a22a31a32an1ann.k=01234n(n-1)/2n(n+1)/2-1按行序为主序：按行序为主序：三角矩阵的压缩存储方法三角矩阵的压缩存储方法第8页，共22页，编辑于2022年，星期三9a11a120.0a21a22a230000an-1,n-2an-1,n-1an-1,n00an,n-1ann.0a32a33a3400Loc(aij)=Loc(a11)+3*(i-1)-1+j-i+1 =Loc(a11)+2(i-1)+(j-1)a11a12a21a22a23ann-1ann.k=01234n(n-1)/2n(n+1)/2-1按行序为主序：按行序为主序：对角矩阵的压缩存储方法对角矩阵的压缩存储方法第9页，共22页，编辑于2022年，星期三10M由由(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）唯一确定）唯一确定定义：定义：非零元较零元少，且分布没有一定规律的矩阵非零元较零元少，且分布没有一定规律的矩阵压缩存储原则：压缩存储原则：只存矩阵的行列维数和每个非零元的行列只存矩阵的行列维数和每个非零元的行列下标及其值下标及其值稀疏矩阵稀疏矩阵第10页，共22页，编辑于2022年，星期三11三元组表所需存储单元个数为3(t+1)其中t为非零元个数678121213931-3361443245218611564-7maijv012345678ma0.i,ma0.j,ma0.v分别存放矩阵行列维数和非零元个数行列下标非零元值稀疏矩阵的三元组表示法#define MAX 10 typedef struct int i,j;elemtype v;node;typedef struct int mu,nu,tu;node dataMAX;mat;mu,nu,tu分别存放矩阵行列维数和非零元个数第11页，共22页，编辑于2022年，星期三12 算法思路：算法思路：将两个矩阵的行数和列数相互交换；将两个矩阵的行数和列数相互交换；将每个三元组中的将每个三元组中的i和和j相互调换；相互调换；重排三元组之间的次序便可实现矩阵的转置，重排三元组之间的次序便可实现矩阵的转置，即使即使b.data中的三元组以中的三元组以B的行（即的行（即A的列）的列）为主序依次排列。为主序依次排列。稀疏矩阵的转置运算稀疏矩阵的转置运算第12页，共22页，编辑于2022年，星期三13 算法实现思想（算法算法实现思想（算法2.16）：）：按照矩阵按照矩阵A的列序来进行转置运算。也就是首先的列序来进行转置运算。也就是首先寻找寻找a.data中的第列的所有三元组，将其中的第列的所有三元组，将其(i,j,v)改为改为(j,i,v)后依次存放到后依次存放到b.data中，作为转置矩阵中，作为转置矩阵B的第行的非零元所对应的三元组。然后在的第行的非零元所对应的三元组。然后在a.data中寻找第列的所有三元组，将其中寻找第列的所有三元组，将其(i,j,v)改改为为(j,i,v)后依次存放在后依次存放在b.data中，作为转置矩阵中，作为转置矩阵B的第行的非零元所对应的三元组，依次类推。的第行的非零元所对应的三元组，依次类推。稀疏矩阵的转置运算的实现稀疏矩阵的转置运算的实现第13页，共22页，编辑于2022年，星期三14678121213931-3361443245218611564-7ijv012345678ma76813-3161521122518319342446-76314ijv012345678mbkppppppppkkkkppppppppcol=1col=2说明：说明：p p是算法中的是算法中的amam，k k是算法中的是算法中的bnbn第14页，共22页，编辑于2022年，星期三15lmat*zzjz(mat*a)lintam.bn.col;lmat*b;/*转置后的矩阵转置后的矩阵b*/lb=(mat*)malloc(sizeof(mat);lb.nu=a.mu;b.mu=a.nu;b.tu=a.tu;/*a,b矩阵行、列交换矩阵行、列交换*/lbn=0;lfor(col=1;col=a.nu;col+)/*按按a的列序转置的列序转置*/lfor(am=1;am=a.tu;am+)/*扫描整个三元组表扫描整个三元组表*/lif(a.dataam.j=col)/*列号为列号为col是转置是转置*/lb.databn.i=a.dataam.j;lb.databn.j=a.dataam.i;lb.databn.v=a.dataam.v;lbn+;/*b.data中的结点序号加中的结点序号加1*/llreturnb;/*返回转置矩阵的指针返回转置矩阵的指针*/l第15页，共22页，编辑于2022年，星期三16算法算法2.16的主要耗费时间是在的主要耗费时间是在col和和am的两重循环中，的两重循环中，所以算法的时间复杂度为所以算法的时间复杂度为O(nu.tu),(nu表示表示a.nu,tu表示表示a.tu),即和即和A的列数与非零元素的个数的乘积成的列数与非零元素的个数的乘积成正比。正比。当非零元个数值当非零元个数值tu=m*n时，（时，（m、n分别表示数组分别表示数组的行列数）算法的行列数）算法2.16的时间复杂度成为的时间复杂度成为O(m*n2)。因此算法因此算法2.16的时间复杂度比的时间复杂度比O(m*n)还差。一般上还差。一般上述转置算法只适用于当述转置算法只适用于当tumu*nu的情况。的情况。稀疏矩阵的转置运算算法分析稀疏矩阵的转置运算算法分析第16页，共22页，编辑于2022年，星期三17十字链表的结点类十字链表的结点类型定义如下：型定义如下：typedefstructnodeinti,j,v;structnode*down,*right;szjd;稀疏矩阵的十字链表表示法第17页，共22页，编辑于2022年，星期三18稀疏矩阵的十字链表表示法（续）第18页，共22页，编辑于2022年，星期三19算法步骤：算法步骤：（1）将行、列指针数组置空。假设）将行、列指针数组置空。假设m,n分别是行指针分别是行指针和列指针数组，和列指针数组，hs,ls是指向存放矩阵行数和列数变是指向存放矩阵行数和列数变量的指针变量。量的指针变量。(2)输入三元组，若行下标或列下标为输入三元组，若行下标或列下标为0时，则表示输时，则表示输入完毕，算法结束，否则生成入完毕，算法结束，否则生成p结点，并把行、列、结点，并把行、列、值域分别置为值域分别置为x,y,z。（3）把）把p结点插入到第结点插入到第x行链表中。行链表中。（4）把）把p结点插入到第结点插入到第y列链表中转向步骤列链表中转向步骤2。十字链表的建立算法第19页，共22页，编辑于2022年，星期三20lszlbcreate(szjd*m,szjd*n,int*hs,int*ls)lintx,y,z,ms,ns;lintk=0;lszjd*p,*q,*s;lms=ns=0;lscanf(“%d,%d”,&ms,&ns);lfor(k=0;kms;i+)lmk=NULL;lfor(;kms)|(yns)lcontinue;ls=(szjd*)malloc(sizeof(szjd);ls-i=x;s-j=y;s-v=z;ls-right=s-down=NULL;lq=NULL;lp=mx-1;lwhile(p!=NULL)&(yp-j)lq=p;p=p-right;lif(p=NULL)lif(q=NULL)mx-1=s;lelseq-right=s;lelseif(y=p-j)lp-v=z;free(s);continue;lelses-right=p;q-right=s;lq=NULL;p=ny-1;lwhile(p!=NULL)&(xp-i)lq=p;p=p-down;lif(p=NULL)lif(q=NULL)lny-1=s;lelseq-down=s;lelses-down=p;q-down=s;ll第20页，共22页，编辑于2022年，星期三第二章第二章 线性表线性表内容提要内容提要 1 1、线性表的定义、逻辑结构特点及基本运算、线性表的定义、逻辑结构特点及基本运算2 2、线性表的顺序存储结构及基本运算、线性表的顺序存储结构及基本运算3 3、线性表的链式存储结构及基本运算线性表的链式存储结构及基本运算4 4、数组的逻辑结构定义及其存储方式数组的逻辑结构定义及其存储方式5 5、线性表的应用示例线性表的应用示例第21页，共22页，编辑于2022年，星期三22l线性表的逻辑结构、物理结构、基本运算及运线性表的逻辑结构、物理结构、基本运算及运算实现的算法。算实现的算法。l顺序表上的插入和删除算法及链表的建立、查顺序表上的插入和删除算法及链表的建立、查找、插入和删除算法。找、插入和删除算法。l线性表的典型算法的应用及解决问题的方线性表的典型算法的应用及解决问题的方法。法。l数组的压缩存储及运算数组的压缩存储及运算本章要点本章要点第22页，共22页，编辑于2022年，星期三
