数组数据结构严蔚敏学习教案.pptx
数组数据结构数组数据结构(sh j ji u)严蔚敏严蔚敏第一页，共24页。数组的ADT定义(dngy)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)/取出元素值取出元素值Assign(&A,e,index1,indexn)/给元素赋值给元素赋值ADTArray第1页/共24页第二页，共24页。数组的ADT定义(dngy)n n维数组中含有维数组中含有 个数据元素个数据元素(yun s)(yun s)，每个元素，每个元素(yun(yun s)s)受到受到n n个关系的约束，且这个关系的约束，且这n n个关系都是线性关系。当个关系都是线性关系。当n=1n=1时，时，n n维数组就退化为定长的线性表。反之，维数组就退化为定长的线性表。反之，n n维数组也可以维数组也可以看成是线性表的推广看成是线性表的推广数组中的每个元素数组中的每个元素(yun s)(yun s)都对应于一组下标都对应于一组下标(j1,jk)(j1,jk)，每，每个下表的取值范围是个下表的取值范围是0 ji bi-1,bi0 ji bi-1,bi称为第称为第i i维的长度维的长度数组一旦被定义，它的维数和维界就不再改变数组一旦被定义，它的维数和维界就不再改变数组结构操作数组结构操作初始化、销毁、元素初始化、销毁、元素(yun s)(yun s)的存取和修改的存取和修改不过，数组多用于静态数据处理，一般不作插入和删除操作不过，数组多用于静态数据处理，一般不作插入和删除操作第2页/共24页第三页，共24页。数组特点(tdin)l l数组中各元素都具有统一的类型数组中各元素都具有统一的类型l ld d维数组的非边界元素具有维数组的非边界元素具有d d个直接前趋和个直接前趋和d d个直接后继个直接后继(huj)(huj)数组维数组维数确定后，数据元素个数和元素之间的关系不再发生改变，适合于顺数确定后，数据元素个数和元素之间的关系不再发生改变，适合于顺序存储序存储l l每组有定义的下标都存在一个与其相对应的值每组有定义的下标都存在一个与其相对应的值第3页/共24页第四页，共24页。数组的顺序(shnx)表示数组通常采用顺序存储方式来实现数组通常采用顺序存储方式来实现n n维数组的数据维数组的数据(shj)(shj)元素的存储问题元素的存储问题必须约定存放次序必须约定存放次序因为存储单元是一维的，而数组是多维的因为存储单元是一维的，而数组是多维的存储方案存储方案以行序为主序，如以行序为主序，如C,Pascal,BasicC,Pascal,Basic等语言采用等语言采用以列序为主序，如以列序为主序，如FortranFortran语言采用语言采用数组一旦定义了维数和各维长度，便可为其分配存储空数组一旦定义了维数和各维长度，便可为其分配存储空间间只要给出一组下标便可求得相应元素的存储位置只要给出一组下标便可求得相应元素的存储位置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+(i-1)*l第4页/共24页第五页，共24页。数据元素的存储(cn ch)问题一维数组为例如 int Ab1,共占用b1个整型存储单元给定下标值i，求对应元素(yun s)的存储位置Loc(i)=Loc(0)+i*L数组数组基址基址(j zh)元素所占存储单元素所占存储单元大小元大小ALoc(0)01ib1-1LA0A1AiAb1-1第5页/共24页第六页，共24页。数据(shj)元素的存储问题二维数组为例如 int Ab1,b2,共占用b1*b2个整型存储(cn ch)单元如 行序为主序的存储(cn ch)方式(图a)给定下标值i,j，求对应元素的存储(cn ch)位置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页第七页，共24页。n n维数组为例维数组为例如如 int Ab1,b2,bn,int Ab1,b2,bn,共占用共占用b1*b2*bnb1*b2*bn个整型存储单个整型存储单元元行序为主序的存储方式行序为主序的存储方式(fngsh)(fngsh)给定下标值给定下标值j1,j2,jn,j1,j2,jn,求对应元素的存储位置求对应元素的存储位置 Loc(j1,j2,jn)=Loc(0,0,0)+L*Loc(j1,j2,jn)=Loc(0,0,0)+L*(b2*.*bn*j1+(b2*.*bn*j1+b3*bn*j2+b3*bn*j2+bn*jn-1+bn*jn-1+jn)jn)考虑考虑3 3维数组的情形维数组的情形?数据元素(yun s)的存储问题第7页/共24页第八页，共24页。矩阵(j zhn)通常(tngchng)使用二维数组来存储矩阵元素矩阵的常见操作转置、相乘等void TransposeMatrix(int T,int M,mu,nu)/矩阵(j zhn)转置 for(col=1;col=nu;+col)for(row=1;row=mu;+row)Tcolrow=Mrowcol;第8页/共24页第九页，共24页。void ProductMartrix(int Q,int M,int N,m1,n1,n2)/矩阵(j zhn)相乘 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;矩阵(j zhn)第9页/共24页第十页，共24页。矩阵(j zhn)的压缩存储特殊矩阵特殊矩阵值相同的元素或零元素在矩阵中的分布有规律值相同的元素或零元素在矩阵中的分布有规律如对称矩阵，三角矩阵等如对称矩阵，三角矩阵等稀疏矩阵稀疏矩阵值相同的元素或零元素在矩阵中的分布无规律，且值相同的元素或零元素在矩阵中的分布无规律，且非零元素个数非零元素个数/矩阵所有元素个数矩阵所有元素个数=0.05=j i=j k=k=j(j-1)/2+i 1 j(j-1)/2+i 1 当当 i j i j a11 a12 a1na21 a22 a2n an1 an2 annAa11a12a1na21a22aijan1an2ann0(n-1)*(n-1)saa11a21a31a32a33aijanna220n*(n-1)/2-1k(i-1)*n+j第12页/共24页第十三页，共24页。特殊矩阵的压缩(y su)存储如3*3对称矩阵未压缩(y su)时，用二维数组存放，占用9个单元压缩(y su)存放时，用一维数组存放，只需6个单元如a32存放在sa4中a11 a12 a13a21 a22 a23a31 a32 a33a11a21a31a32a33a2205saaij=aji第13页/共24页第十四页，共24页。特殊(tsh)矩阵的压缩存储三角矩阵下(上)三角矩阵是指矩阵的上(下)三角(不包括对角线)中的元均为常数c或零的n阶矩阵三角矩阵的压缩存储只存储下(上)三角中的元素，再加一个(y)存储常数c的空间即可第14页/共24页第十五页，共24页。特殊(tsh)矩阵的压缩存储对角矩阵所有非零元素都集中在以主对角线为中心(zhngxn)的带状区域中对角矩阵的压缩存储可按照某原则(或以行为主，或以对角线的顺序)将其压缩到一维数组中第15页/共24页第十六页，共24页。特殊矩阵(j zhn)的压缩存储小结特殊矩阵(如对称矩阵、三角矩阵、对角矩阵等)中，非零元素的分布有明显(mngxin)的规律，因此我们可以将其压缩存储到一维数组中，并找到每个非零元素在一维数组中的对应关系第16页/共24页第十七页，共24页。稀疏(xsh)矩阵的压缩存储稀疏矩阵稀疏矩阵值相同的元素或零元素在矩阵中的分布无规律，且值相同的元素或零元素在矩阵中的分布无规律，且非零元素个数非零元素个数/矩阵所有元素个数矩阵所有元素个数=0.05=0.05原理原理只需存储只需存储(cn ch)(cn ch)矩阵中的非零元素所在的行号、列号和值矩阵中的非零元素所在的行号、列号和值方法方法三元组顺序表三元组顺序表(*)(*)行逻辑联接顺序表行逻辑联接顺序表十字链表十字链表第17页/共24页第十八页，共24页。稀疏矩阵的压缩(y su)存储三元组顺序表以顺序结构(jigu)存储三元组表#define MAXSIZE 12500/假设非零元素(yun s)个数的最大值typedef struct int i,j;/行号,列号 ElemType e;/元素(yun s)值Triple;/三元组typedef struct Triple dataMAXSIZE+1;/非零元素(yun s)三元组表，data0未用 int mu,nu,tu;/行数，列数，非零元素(yun s)个数TSMatrix;/三元组顺序表TSMatrix M;/矩阵M第18页/共24页第十九页，共24页。稀疏矩阵(j zhn)的压缩存储如稀疏矩阵采用三元组法压缩存储(cn ch)稀疏矩阵按行号排序不支持随机存取，对某行某非零元素访问时，可能需要扫描整个顺序表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页第二十页，共24页。采用三元组顺序采用三元组顺序(shnx)(shnx)表存储的矩阵的转置表存储的矩阵的转置算法算法Status TransposeSMatrix(TSMatrix M,TSMatrix&T)T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu)/有非零元素(yun s)，转置 q=1;/非零元素(yun s)计数器 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页第二十一页，共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转置(zhun zh)1 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采用三元组顺序表存储采用三元组顺序表存储(cn ch)的矩阵的转置算法的矩阵的转置算法第21页/共24页第二十二页，共24页。作业(zuy)l l用以行序为主序和以列序为主序分别(fnbi)写出三维数组A234的元素在内存中的存储次序l l对上（下）三角矩阵，若采用以行序为主序的原则用一维数组顺序存储其所有非零元素，试找出每个非零元素aij在一维数组中的对应关系第22页/共24页第二十三页，共24页。思考题若在m*n的矩阵中存在一个元素Ai,j，并满足：Ai,j是第i行元素中的最小值，且是第j列元素中的最大值，则称矩阵A有鞍点。试写一个算法(sun f)，找出矩阵A的一个鞍点，若不存在鞍点，则返回某种信息第23页/共24页第二十四页，共24页。
