《第五章数组优秀课件.ppt》由会员分享，可在线阅读，更多相关《第五章数组优秀课件.ppt（22页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第五章数组第五章数组第1页，本讲稿共22页2数组的定义数组的定义 数组结构可以简单地定义为：若线性表中的数据元素为非结构的简单元素，则称为一维数组，即为向量；若一维数组中的数据元素又是一维数组结构，则称为二维数组；依次类推，若二维数组中的元素又是一个一维数组结构，则称作三维数组。结论：线性表结构是数组结构的一个特例，而数组结构又是线性表结构的扩展。第2页，本讲稿共22页3()()()()()()()()()二维数组二维数组数组数组A A可以看成一个线性表：可以看成一个线性表：A=(0A=(0，1 1，.，k)k)（k=m-1k=m-1或或n-1n-1）其中每一个数据元素其中每一个数据元素i i
2、 是由第是由第i i行行元素组成的一维数组，即一个行向量元素组成的一维数组，即一个行向量的线性表。的线性表。i=(ai0 i=(ai0，ai1 ai1，.，ai,n-1)ai,n-1)0im-10im-1或或jj是由第是由第j j列元素组成的一维数列元素组成的一维数组，即一个列向量的线性表。组，即一个列向量的线性表。第3页，本讲稿共22页4数组的特点及运算数组特点数组特点l数组结构固定数组结构固定l数据元素同构数据元素同构数组运算数组运算l给定一组下标，存取相应的数据元素给定一组下标，存取相应的数据元素l给定一组下标，修改数据元素的值给定一组下标，修改数据元素的值l数组一般不做插入或删除操作数
3、组一般不做插入或删除操作第4页，本讲稿共22页5次序约定次序约定l以行序为主序l以列序为主序a11a12.a1na21a22.a2nam1am2.amn.Loc(aij)=Loc(a11)+(i-1)n+(j-1)*l 按行序为主序存放按行序为主序存放 amn.am2 am1.a2n.a22 a21 a1n.a12 a1101n-1m*n-1n数组的顺序存储结构按列序为主序存放按列序为主序存放01m-1m*n-1m amn.a2n a1n.am2.a22 a12 am1.a21 a11a11a12.a1na21a22.a2nam1am2.amn.Loc(aij)=Loc(a11)+(j-1)m
4、+(i-1)*l 第5页，本讲稿共22页6矩阵的压缩存储方法 压缩存储是指为多个值相同的元素只分配一个存储空间；对零元素不分配空间。第6页，本讲稿共22页7a11a12.a1na21a22.a2nan1an2.ann.a11 a21 a22 a31 a32 an1 ann.k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1 按行序为主序：对称矩阵的压缩存储方法第7页，本讲稿共22页8a1100.0a21a220.0an1an2an3.ann.0Loc(aij)=Loc(a11)+(+(j-1)*l i(i-1)2a11 a21 a22 a31 a32 an1 ann.k=0 1 2
5、 3 4 n(n-1)/2 n(n+1)/2-1 按行序为主序：三角矩阵的压缩存储方法第8页，本讲稿共22页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)a11 a12 a21 a22 a23 ann-1 ann.k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1 按行序为主序：对角矩阵的压缩存储方法第9页，本讲稿共22页10M由由(1,2,12),(1,3,9),(3,1,-3)
6、,(3,6,14),(4,3,24),(5,2,18),(6,1,15),(6,4,-7)和矩阵维数（和矩阵维数（6,7）唯一确定）唯一确定定义：定义：非零元较零元少，且分布没有一定规律的矩阵非零元较零元少，且分布没有一定规律的矩阵压缩存储原则：压缩存储原则：只存矩阵的行列维数和每个非零元的行列下标只存矩阵的行列维数和每个非零元的行列下标及其值及其值稀疏矩阵稀疏矩阵第10页，本讲稿共22页11三元组表所需存储单元个数为3(t+1)其中t为非零元个数678121213931-3361443245218611564-7mai j v012345678ma0.i,ma0.j,ma0.v分别存放矩阵行
7、列维数和非零元个数行列下标非零元值稀疏矩阵的三元组表示法#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页12 算法思路：算法思路：将两个矩阵的行数和列数相互交换；将两个矩阵的行数和列数相互交换；将每个三元组中的将每个三元组中的i和和j相互调换；相互调换；重排三元组之间的次序便可实现矩阵的重排三元组之间的次序便可实现矩阵的转置，即使转置，即使b.data中的三元组以中的三元组以
8、B的行（即的行（即A的列）为主序依次排列。的列）为主序依次排列。稀疏矩阵的转置运算稀疏矩阵的转置运算第12页，本讲稿共22页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页146 7 8 1
9、2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 i j v012345678ma76813-3161521122518319342446-76314i j v012345678mbkppppppppkkkkppppppppcol=1col=2说明：p是算法中的am，k是算法中的bn第14页，本讲稿共22页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
10、,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页16算法2.16的主
11、要耗费时间是在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页17十字链表的结点类型定义如下：typedef struct node int i,j,v;struct node *down,*right;szjd;稀疏矩阵的
12、十字链表表示法第17页，本讲稿共22页18稀疏矩阵的十字链表表示法（续）第18页，本讲稿共22页19算法步骤：（1）将行、列指针数组置空。假设m,n分别是行指针和列指针数组，hs,ls是指向存放矩阵行数和列数变量的指针变量。(2)输入三元组，若行下标或列下标为0时，则表示输入完毕，算法结束，否则生成p结点，并把行、列、值域分别置为x,y,z。（3）把p结点插入到第x行链表中。（4）把p结点插入到第y列链表中转向步骤2。十字链表的建立算法第19页，本讲稿共22页20lszlbcreate(szjd*m,szjd*n,int*hs,int*ls)lintx,y,z,ms,ns;lintk=0;ls
13、zjd*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
14、;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页第二章第二章 线性表线性表内容提要内容提要 1 1、线性表的定义、逻辑结构特点及基本运算、线性表的定义、逻辑结构特点及基本运算2 2、线性表的顺序存储结构及基本运算、线性表的顺序存储结构及基本运算3 3、线性表的链式存储结构及基本运算线性表的链式存储结构及基本运算4 4、数组的逻辑结构定义及其存储方式数组的逻辑结构定义及其存储方式5 5、线性表的应用示例线性表的应用示例第21页，本讲稿共22页22l 线性表的逻辑结构、物理结构、基本运算及运算实现的算法。l顺序表上的插入和删除算法及链表的建立、查找、插入和删除算法。l线性表的典型算法的应用及解决问题的方法。l数组的压缩存储及运算本章要点第22页，本讲稿共22页