数据结构 数组幻灯片.ppt

《数据结构 数组幻灯片.ppt》由会员分享，可在线阅读，更多相关《数据结构 数组幻灯片.ppt（38页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、数据结构 数组第1页，共38页，编辑于2022年，星期六6.1 6.1 数组的基本概念数组的基本概念数组可以看成是线性表的一种扩展，表中的元素本身也是一种数据结构，但所有的元素都属于同一类型。第2页，共38页，编辑于2022年，星期六 6.1.1 数组的定义及逻辑结构数组的定义及逻辑结构例如：二维数组可以看成例如：二维数组可以看成“数组元素是一维数组数组元素是一维数组”的一维数组，的一维数组，三维数组可以看成三维数组可以看成“数组元素是二维数组数组元素是二维数组”的一维数组，依次类推。的一维数组，依次类推。一个一个m行行n列的二维数组。列的二维数组。a11a12a1na21a22a2nam1a

2、m2amnAmn第3页，共38页，编辑于2022年，星期六数组是一个固定格式和数量的数据有序列，每个数组元素用惟一的一组下标标识。数组的基本操作:取值操作：给定一组下标，读其对应的数组元素。赋值操作：给定一组下标，存储或修改与其相对应的数组元素。6.1.1 数组的定义及逻辑结构数组的定义及逻辑结构第4页，共38页，编辑于2022年，星期六 6.1.2 数组的顺序存储结构数组的顺序存储结构在内存中,数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系。对于一维数组按下标顺序分配即可。对于多维数组的分配，要把它的元素映像在一维存储器中，一般有两种存储方式，即“以行(序)为主(序)”的映象方法和

3、“以列(序)为主(序)”的映象方法。“以行为主”的存储结构:将数组中的数据元素“按行依次排放”在存储器中；“以列为主”的存储结构:将数组中的数据元素“按列依次排放”在存储器中。第5页，共38页，编辑于2022年，星期六 6.1.2 数组的顺序存储结构数组的顺序存储结构LOC(A1(1)=LOC(a11)a11a12a1nLOC(A2(1)=LOC(a21)a21a22a2nLOC(Am(1)=LOC(am1)am1am2amnLOC(A1-(1)=LOC(a11)a11a21am1LOC(A2-(1)=LOC(a12)a12a22am2LOC(An-(1)=LOC(a1n)a1na2namnA

4、1(1)A2(1)Am(1)A1-(1)A2-(1)An-(1)(a)以行为主序以行为主序(b)以列为主序以列为主序第6页，共38页，编辑于2022年，星期六由下标计算数组元素的存储位置由下标计算数组元素的存储位置:假设每个数据元素占L个存储单元 一维数组A(n)任意元素ai的存储位置LOC(ai)=LOC(a0)+i*L/*假设数组下标界从0开始*/第7页，共38页，编辑于2022年，星期六 6.1.2 数组的顺序存储结构数组的顺序存储结构 二维数组二维数组A(mn)一个一个23的二维数组，其逻辑结构和内存映像如下。的二维数组，其逻辑结构和内存映像如下。a11a12a13a21a22a232

5、3数组的逻辑结构数组的逻辑结构a11a12a13a21a22a23a11a21a12a22a13a23以行为主序内存映像以行为主序内存映像以列为主序内存映像以列为主序内存映像第8页，共38页，编辑于2022年，星期六假设二维数组 Amn 中每个数据元素占L个存储地址，并以 LOC(aij)表示下标为(i,j)的数据元素的存储地址，则数据元素在“以行为主”的顺序映象中的存储地址为：LOC(aij)=在C语言中，数组中每一维下标界定义为0，则 LOC(aij)=/*假设数组下标界从0开始*/6.1.2 数组的顺序存储结构数组的顺序存储结构 LOC(a11)+(i-1)*n+j-1)*L/*假设数组

6、下标界从1开始*/LOC(a00)+(i*n+j)*L第9页，共38页，编辑于2022年，星期六2022/10/2练 习 已知二维数组已知二维数组A1.A1.3 3,1.,1.5 5 的存储首地址为的存储首地址为100100，它，它采用采用以行为主以行为主的顺序存储，且每个元素占用的顺序存储，且每个元素占用4 4个个字节字节 LOC(aLOC(a2，4)=)=100+（2-1）*5+4-1*4=132第10页，共38页，编辑于2022年，星期六2022/10/2练 习 已知二维数组已知二维数组A1.A1.3 3,1.,1.5 5 的存储首地址为的存储首地址为100100，它，它采用采用以列为主

7、以列为主的顺序存储，且每个元素占用的顺序存储，且每个元素占用4 4个个字节字节 LOC(aLOC(a2，4)=)=100+（4-1）*3+2-1*4=140第11页，共38页，编辑于2022年，星期六例例 设有二维数组设有二维数组a(6,8)，每个元素占，每个元素占6个字节存储，个字节存储，a0,0起始地址为起始地址为1000，计算，计算 数组数组a的存储量是多少字节。的存储量是多少字节。数组的最后一个元素数组的最后一个元素a5,7的起始地址。的起始地址。按行优先存放时，元素按行优先存放时，元素a1,4的起始地址。的起始地址。按列优先存放时，元素按列优先存放时，元素a4,7的起始地址。的起始地

8、址。练练 习习第12页，共38页，编辑于2022年，星期六解解 数组数组a的存储量的存储量=6*8*6=288(字节字节)最后一个元素按行优先和按列优先地址都相同。最后一个元素按行优先和按列优先地址都相同。LOC(a0,0)=1000,n=8,i=5,j=7,L=6 LOC(a5,7)=LOC(a0,0)+(n*i+j)*L=1000*(8*5+7)*6=1282 按行优先存放时，按行优先存放时，LOC(a0,0)=1000,n=8,i=1,j=4,L=6 LOC(a1,4)=LOC(a0,0)+(n*i+j)*L=1000*(8*1+4)*6=1072 按列优先存放时，按列优先存放时，LOC

9、(a0,0)=1000,m=6,i=4,j=7,L=6 LOC(a4,7)=LOC(a0,0)+(m*j+i)*L=1000*(6*7+4)*6=1276第13页，共38页，编辑于2022年，星期六例 试设计算法，在O(n)时间内将数组A1.n划分为左右两部分，使得左边的所有元素值均为奇数，右边的所有元素值均为偶数，要求所使用的辅助存储空间大小为O(1)。算法设计：用一维数组A1.n表示，从左往右扫描数组A寻找偶数,从右往左扫描数组A寻找奇数,交换这两个数。6.1.2 数组的顺序存储结构数组的顺序存储结构第14页，共38页，编辑于2022年，星期六void part(int A,int n)i

10、nt i=0,j=n-1,k;while(ij)while(Ai%2!=0)&(ij)i=i+1;while(Aj%2!=1)&(ij)j=j-1;if(ij)k=Ai;Ai=Aj;Aj=k;i+;j-;第15页，共38页，编辑于2022年，星期六例例 已知二维数组已知二维数组Amn，求当，求当m=n时，对角线上所有数组元素的和。时，对角线上所有数组元素的和。6.1.2 数组的顺序存储结构数组的顺序存储结构a00a01a02a03a04a10a11a12a13a14a20a21a22a23a24a30a31a32a33a34a40a41a42a43a44A55算法设计：算法设计：本题中一条对角

11、线是本题中一条对角线是aii，其中，其中(0im-1)，另一条对角线是，另一条对角线是am-i-1,i，其中，其中(0im-1)。第16页，共38页，编辑于2022年，星期六#define MAX 20void proc(int A MAX,int m,int n)int i,s;if(m!=n)printf(“mn”);else s=0;for(i=0;im;i+)s=s+Aii;for(i=0;in;i+)s=s+An-i-1i;printf(“s=%4dn”,s);main()int m,n,i,j;int AMAXMAX;printf(“m,n=”);scanf(“%d,%d”,&m,

12、&n);for(i=0;im;i+)for(j=0;jrows=A-cols;B-cols=A-rows;/*A和和B的行列总数互换的行列总数互换*/B-terms=A-terms;if(B.terms)q=1;for(col=1;colcols;col+)/*对对A的每列的每列*/for(p=1;pterms;p+)/*扫描扫描A的三元组表的三元组表*/if(A-datap.j=col)/*找列号为找列号为col的三元组的三元组*/B-dataq.i=A-datap.j;B-dataq.j=A-datap.i;B-dataq.v=A-datap.v;q+;return(B);/*返回转置后矩阵指针返回转置后矩阵指针*/6.3.2 稀疏矩阵的转置稀疏矩阵的转置第37页，共38页，编辑于2022年，星期六数组作为一种数据类型，其特点是一种多维的线性结构，并只进行存取或修改某个元素的值。因此只需采用顺序存储结构。要点：矩阵元素的地址计算公式。一些特殊矩阵的压缩存储方式。稀疏矩阵的三元组表，及相关算法。6.4 6.4 本章小结本章小结本章小结本章小结第38页，共38页，编辑于2022年，星期六