数据结构第6章数组

1、数据结构第6章数组 本章要点本章要点 数组的定义及逻辑结构数组的定义及逻辑结构 数组的存储结构数组的存储结构 矩阵的压缩存储矩阵的压缩存储 稀疏矩阵的概念及应用稀疏矩阵的概念及应用 本章难点本章难点 稀疏矩阵的存储结构稀疏矩阵的存储结构数据结构第6章数组数组可以看成是线性表的一种扩展，表中的元素本身也是一种数据结构，但所有的元素都属于同一类型。数据结构第6章数组数组的定义及逻辑结构数组的定义及逻辑结构例如：二维数组可以看成例如：二维数组可以看成“数组元素是一维数组数组元素是一维数组”的一维的一维数组，三维数组可以看成数组，三维数组可以看成“数组元素是二维数组数组元素是二维数组”的一维数组，的一

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

3、)为主(序)”的映象方法。 “以行为主”的存储结构: 将数组中的数据元素“按行依次排放”在存储器中；“以列为主”的存储结构: 将数组中的数据元素“按列依次排放”在存储器中。数据结构第6章数组数组的顺序存储结构数组的顺序存储结构A1 (1)A2 (1)Am(1)A1 -(1)A2 -(1)An -(1)(a) 以行为主序以行为主序(b) 以列为主序以列为主序数据结构第6章数组由下标计算数组元素的存储位置由下标计算数组元素的存储位置:假设每个数据元素占L个存储单元 一维数组A(n)任意元素ai的存储位置LOC(ai)=LOC(a0)+i*L/*假设数组下标界从0开始*/数据结构第6章数组数组的顺序

4、存储结构数组的顺序存储结构 二维数组二维数组A(mn)一个一个23的二维数组，其逻辑结构和内存映像如下。的二维数组，其逻辑结构和内存映像如下。 23数组的逻辑结构数组的逻辑结构以行为主序内存映像以行为主序内存映像以列为主序内存映像以列为主序内存映像数据结构第6章数组假设二维数组 Amn 中每个数据元素占L个存储地址，并以 LOC(aij) 表示下标为 (i,j) 的数据元素的存储地址，则数据元素在“以行为主”的顺序映象中的存储地址为：LOC(aij) =在C语言中，数组中每一维下标界定义为0，则 LOC(aij) = /*假设数组下标界从0开始*/数组的顺序存储结构数组的顺序存储结构 LOC(

5、a11) + (i-1)*n+j-1)*L/*假设数组下标界从1开始*/LOC(a00) + (i*n+j)*L数据结构第6章数组2021-7-17练 习 已知二维数组已知二维数组A1.3,1.5A1.3,1.5的存储首地址为的存储首地址为100100，它采用以行为主的顺序存储，且每个元，它采用以行为主的顺序存储，且每个元素占用素占用4 4个字节个字节 LOC (aLOC (a2，4 )= )= 100+（2-1）*5+4-1*4= 132数据结构第6章数组2021-7-17练 习 已知二维数组已知二维数组A1.3,1.5A1.3,1.5的存储首地址为的存储首地址为100100，它采用以列为主

6、的顺序存储，且每个元，它采用以列为主的顺序存储，且每个元素占用素占用4 4个字节个字节 LOC (a LOC (a2，4 )= )= 100+（4-1）*3+2-1*4= 140数据结构第6章数组例例 设有二维数组设有二维数组a(6,8)，每个元素占，每个元素占6个字节存储，个字节存储，a0,0起始地起始地址为址为1000，计算，计算 数组数组a的存储量是多少字节。的存储量是多少字节。 数组的最后一个元素数组的最后一个元素a5,7的起始地址。的起始地址。 按行优先存放时，元素按行优先存放时，元素a1,4的起始地址。的起始地址。 按列优先存放时，元素按列优先存放时，元素a4,7的起始地址。的起始

7、地址。练练 习习数据结构第6章数组解解 数组数组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(a0,0)=

8、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数据结构第6章数组例 试设计算法，在O(n)时间内将数组A1.n划分为左右两部分，使得左边的所有元素值均为奇数，右边的所有元素值均为偶数，要求所使用的辅助存储空间大小为O(1)。算法设计：用一维数组A1.n表示，从左往右扫描数组A寻找偶数,从右往左扫描数组A寻找奇数,交换这两个数 。数组的顺序存储结构数组的顺序存储结构数据结构第6章数组void part(int A, int n) int i=0,j=n-1,k; while (ij) while (A

9、i%2 != 0) & (ij) i=i+1; while (Aj%2 != 1) & (ij) j=j-1; if (ij) k=Ai; Ai=Aj; Aj=k; i+; j-; 数据结构第6章数组例例 已知二维数组已知二维数组Amn，求当，求当m=n时，对角线上所有数组元素时，对角线上所有数组元素的和。的和。数组的顺序存储结构数组的顺序存储结构A55算法设计：算法设计：本题中一条对角线是本题中一条对角线是aii，其中，其中(0im-1)，另一条对角线，另一条对角线是是am-i-1,i ，其中，其中(0im-1)。数据结构第6章数组#define MAX 20void proc(int A

10、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,&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的三元组表的三