《数组数据结构 严蔚敏.pptx》由会员分享，可在线阅读，更多相关《数组数据结构 严蔚敏.pptx（24页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数组的数组的ADT定义定义ADTArray数据对象：数据对象：ji=0,bi-1,i=1,2,nD=aj1j2jn|n称为数组的维数称为数组的维数,bi是数组第是数组第i维的长度维的长度,ji是数组元素的第是数组元素的第i维下标，维下标，aj1j2jnElemSetR=R1,R2,Rn/每个元素受到每个元素受到n个关系的约束个关系的约束Ri=|0jkbk-1,1kn且且ki0jibi-2,aj1jijn,aj1,ji+1jnD,i=2,nP:InitArray(&A,n,bound1,boundn)DestoryArray(&A)Value(A,&e,index1,indexn)/取出元素值取
2、出元素值Assign(&A,e,index1,indexn)/给元素赋值给元素赋值ADTArray第1页/共24页数组的数组的ADT定义定义n维数组中含有 个数据元素，每个元素受到n个关系的约束，且这n个关系都是线性关系。当n=1时，n维数组就退化为定长的线性表。反之，n维数组也可以看成是线性表的推广数组中的每个元素都对应于一组下标(j1,jk)，每个下表的取值范围是0 ji bi-1,bi称为第i维的长度数组一旦被定义，它的维数和维界就不再改变数组结构操作初始化、销毁、元素的存取和修改不过，数组多用于静态数据处理，一般不作插入和删除操作第2页/共24页数组特点数组特点数组中各元素都具有统一的
3、类型d维数组的非边界元素具有d个直接前趋和d个直接后继数组维数确定后，数据元素个数和元素之间的关系不再发生改变，适合于顺序存储每组有定义的下标都存在一个与其相对应的值第3页/共24页数组的顺序表示数组的顺序表示数组通常采用顺序存储方式来实现n维数组的数据元素的存储问题必须约定存放次序因为存储单元是一维的，而数组是多维的存储方案以行序为主序，如C,Pascal,Basic等语言采用以列序为主序，如Fortran语言采用数组一旦定义了维数和各维长度，便可为其分配存储空间只要给出一组下标便可求得相应元素的存储位置a11a12.a1na21a22.a2nam1am2.amn.Loc(aij)=Loc(
4、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+(i-1)*l第4页/共24页数据元素的存储问题数据元素的存储问题一维数组为例如 int Ab1,共占用b1个整型存储单元给定下标值i，求对应元素的存储位置Loc(i)=Loc(0)
5、+i*L数组数组基址基址元素所占存元素所占存储单元大小储单元大小ALoc(0)01ib1-1LA0A1AiAb1-1第5页/共24页数据元素的存储问题数据元素的存储问题二维数组为例如 int Ab1,b2,共占用b1*b2个整型存储单元如 行序为主序的存储方式(图a)给定下标值i,j，求对应元素的存储位置Loc(i,j)=Loc(0,0)+(b2*i+j)*LALoc(0,0)A0,0A0,1A0,b2-1A1,0A1,1A1,b2-1Ab1-1,0Ab1-1,1Ab1-1,b2-1第6页/共24页n维数组为例如 int Ab1,b2,bn,共占用b1*b2*bn个整型存储单元行序为主序的存储
6、方式给定下标值j1,j2,jn,求对应元素的存储位置 Loc(j1,j2,jn)=Loc(0,0,0)+L*(b2*.*bn*j1+b3*bn*j2+bn*jn-1+jn)考虑3维数组的情形?数据元素的存储问题数据元素的存储问题第7页/共24页矩阵矩阵通常使用二维数组来存储矩阵元素矩阵的常见操作转置、相乘等void TransposeMatrix(int T,int M,mu,nu)/矩阵转置 for(col=1;col=nu;+col)for(row=1;row=mu;+row)Tcolrow=Mrowcol;第8页/共24页void ProductMartrix(int Q,int M,i
7、nt N,m1,n1,n2)/矩阵相乘 Qm1*n2=Mm1*n1*Nm2*n2,n1=m2 for(i=1;i=m1;+i)for(j=1;j=n2;+j)Qij=0;for(k=1;k=n1;+k)Qij+=Mik*Nkj;矩阵第9页/共24页矩阵的压缩存储矩阵的压缩存储特殊矩阵值相同的元素或零元素在矩阵中的分布有规律如对称矩阵，三角矩阵等稀疏矩阵值相同的元素或零元素在矩阵中的分布无规律，且非零元素个数/矩阵所有元素个数=j k=j(j-1)/2+i 1 当 i j a11 a12 a1na21 a22 a2n an1 an2 annAa11a12a1na21a22aijan1an2ann
8、0(n-1)*(n-1)saa11a21a31a32a33aijanna220n*(n-1)/2-1k(i-1)*n+j第12页/共24页特殊矩阵的压缩存储特殊矩阵的压缩存储如3*3对称矩阵未压缩时，用二维数组存放，占用9个单元压缩存放时，用一维数组存放，只需6个单元如a32存放在sa4中a11 a12 a13a21 a22 a23a31 a32 a33a11a21a31a32a33a2205saaij=aji第13页/共24页特殊矩阵的压缩存储特殊矩阵的压缩存储三角矩阵下(上)三角矩阵是指矩阵的上(下)三角(不包括对角线)中的元均为常数c或零的n阶矩阵三角矩阵的压缩存储只存储下(上)三角中的
9、元素，再加一个存储常数c的空间即可第14页/共24页特殊矩阵的压缩存储特殊矩阵的压缩存储对角矩阵所有非零元素都集中在以主对角线为中心的带状区域中对角矩阵的压缩存储可按照某原则(或以行为主，或以对角线的顺序)将其压缩到一维数组中第15页/共24页特殊矩阵的压缩存储特殊矩阵的压缩存储小结特殊矩阵(如对称矩阵、三角矩阵、对角矩阵等)中，非零元素的分布有明显的规律，因此我们可以将其压缩存储到一维数组中，并找到每个非零元素在一维数组中的对应关系第16页/共24页稀疏矩阵的压缩存储稀疏矩阵的压缩存储稀疏矩阵值相同的元素或零元素在矩阵中的分布无规律，且非零元素个数/矩阵所有元素个数=0.05原理只需存储矩阵
10、中的非零元素所在的行号、列号和值方法三元组顺序表(*)行逻辑联接顺序表十字链表第17页/共24页稀疏矩阵的压缩存储稀疏矩阵的压缩存储三元组顺序表以顺序结构存储三元组表#define MAXSIZE 12500/假设非零元素个数的最大值typedef struct int i,j;/行号,列号 ElemType e;/元素值Triple;/三元组typedef struct Triple dataMAXSIZE+1;/非零元素三元组表，data0未用 int mu,nu,tu;/行数，列数，非零元素个数TSMatrix;/三元组顺序表TSMatrix M;/矩阵M第18页/共24页稀疏矩阵的压缩
11、存储稀疏矩阵的压缩存储如稀疏矩阵采用三元组法压缩存储稀疏矩阵按行号排序不支持随机存取，对某行某非零元素访问时，可能需要扫描整个顺序表M=0 12 9 0 0 0 0 0 0 0 0 0 0 0-3 0 0 0 0 14 0 0 0 24 0 0 0 0 0 18 0 0 0 0 015 0 0 -7 0 0 01 2 121 3 93 1 -33 6 144 3 245 2 186 1 156 4 -7i j eM.data:M.mu=6M.nu=7M.tu=8第19页/共24页采用三元组顺序表存储的矩阵的转置算法Status TransposeSMatrix(TSMatrix M,TSMat
12、rix&T)T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu)/有非零元素，转置 q=1;/非零元素计数器 for(col=1;col=M.mu;+col)/按列 for(p=1;p=M.tu;+p)/在三元组中找 if(M.datap.j=col)T.dataq.i=M.datap.j;T.dataq.j=M.datap.i;T.dataq.e=M.datap.e;+q;return OK;第20页/共24页1 2 121 3 93 1 -33 6 144 3 245 2 186 1 156 4 -7i j eM.data:M.mu=6M.nu=7M.tu=8转置1
13、 3 -31 6 152 1 123 1 93 4 244 6 -76 3 142 5 18i j eT.data:T.mu=7T.nu=6T.tu=8采用三元组顺序表存储的矩阵的转置算法采用三元组顺序表存储的矩阵的转置算法第21页/共24页作业作业用以行序为主序和以列序为主序分别写出三维数组A234的元素在内存中的存储次序对上（下）三角矩阵，若采用以行序为主序的原则用一维数组顺序存储其所有非零元素，试找出每个非零元素aij在一维数组中的对应关系第22页/共24页思考题思考题若在m*n的矩阵中存在一个元素Ai,j，并满足：Ai,j是第i行元素中的最小值，且是第j列元素中的最大值，则称矩阵A有鞍点。试写一个算法，找出矩阵A的一个鞍点，若不存在鞍点，则返回某种信息第23页/共24页感谢您的观看。第24页/共24页