数据结构（c语言版）（夏燕张兴科）pdf幻灯片第6章数组

《数据结构（c语言版）（夏燕张兴科）pdf幻灯片第6章数组》由会员分享，可在线阅读，更多相关《数据结构（c语言版）（夏燕张兴科）pdf幻灯片第6章数组（39页珍藏版）》请在金锄头文库上搜索。

1、第6章 数组、特殊矩阵和广义表, 本章要点 数组的定义及逻辑结构 数组的存储结构 矩阵的压缩存储 稀疏矩阵的概念及应用 本章难点 稀疏矩阵的存储结构,第6章 数组、特殊矩阵和广义表, 本章要点 数组的定义及逻辑结构 数组的存储结构 矩阵的压缩存储 稀疏矩阵的概念及应用 本章难点 稀疏矩阵的存储结构,6.1 数组的基本概念,数组是所有高级编程语言都已实现的固有数据类型，因此凡学习过高级程序设计语言的读者对数组都不陌生。但它和其它诸如整数、实数等原子类型不同，它是一种结构类型。换句话说，“数组”是一种数据结构。 数组可以看成是线性表的一种扩展，表中的元素本身也是一种数据结构，但所有的元素都属于同一

2、类型。, 6.1.1 数组的定义及逻辑结构,数组是由下标和值组成的元素序列的集合。在数组中，一旦给定下标，都存在一个与其对应的值，称为数组元素。 例如：二维数组可以看成“数组元素是一维数组”的一维数组，三维数组可以看成“数组元素是二维数组”的一维数组，依次类推。一个m行n列的二维数组。,数组是一个固定格式和数量的数据有序列，每个数组元素用惟一的一组下标标识。因此，在数组上不能做插入、删除数组元素的操作。 通常在各种高级语言中数组一旦定义，每一维的大小及上下界都不能改变。 在数组中常有的操作： 数组一旦被定义，其维数(N)和每一维的上、下界均不能再变，数组中元素之间的关系也不再改变。因此数组的基

3、本操作除初始化和结构销毁之外，只有通过给定的“一组下标“索引取得元素或修改元素的值。 取值操作：给定一组下标，读其对应的数组元素。 赋值操作：给定一组下标，存储或修改与其相对应的数组元素。, 6.1.1 数组的定义及逻辑结构, 6.1.2 数组的顺序存储结构,由于数组类型不作插入和删除的操作，因此只需要通过“顺序映象”得到它的存储结构，即借助数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系。 对于一维数组按下标顺序分配即可。 对于多维数组的分配，要把它的元素映像在一维存储器中，一般有两种存储方式，即“以行(序)为主(序)”的映象方法和“以列(序)为主(序)”的映象方法。 以图示的二维数

4、组为例，“以行为主”的存储结构是对二维数组进行“按行切分”，即将数组中的数据元素“按行依次排放”在存储器中； “以列为主”的存储结构是对二维数组进行“按列切分”，即将数组中的数据元素“按列依次排放”在存储器中。, 6.1.2 数组的顺序存储结构,(a) 以行为主序,(b) 以列为主序, 6.1.2 数组的顺序存储结构,对于数组，一旦规定了维数和各维的长度，便可分配存储空间，反之，只要给出一组下标，便可求得相应数组元素的存储位置。 假设每个数据元素占L个存储单元。 一维数组A(n) 任意元素ai的存储位置 LOC(ai)=LOC(a0)+i*L /*假设数组下标界从0开始*/, 6.1.2 数组

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

6、*/, 6.1.2 数组的顺序存储结构, 三维数组A(mn p) 一个23 2的三维数组，其逻辑结构和以行为主序的内存映像如下。,a112,a132,a122,a232,以行为主序内存映像,一维,二维,三维, 6.1.2 数组的顺序存储结构,对于多维数组，以行为主序的存储是以低下标优先，即依次存储次序的排列是最先存储最低一位下标不同的元素。 以列为主序的存储是以高下标优先，即依次存储次序的排列是最先存储最高一位下标不同的元素。 假设三维数组 Amnp 中每个数据元素占L个存储地址，并以 LOC(aijk) 表示下标为 (i,j,k) 的数据元素的存储地址，则该数组中任何一对下标 (i,j,k)

7、 对应的数据元素在“以行为主“的顺序映象中的存储地址为： LOC(aijk) = LOC(a111) + (i-1)*n*p+(j-1)*p+k-1)*L /*假设数组下标界从1开始*/ 在C语言中，数组中每一维下标界定义为0，则 LOC(aijk) = LOC(a000) + (i*n*p+j*p+k)*L /*假设数组下标界从0开始*/, 6.1.2 数组的顺序存储结构,例1 试设计算法，在O(n)时间内将数组A1n划分为左右两部分，使得左边的所有元素值均为奇数，右边的所有元素值均为偶数，要求所使用的辅助存储空间大小为O(1)。 算法设计： 用一维数组A1n表示，当Ai是奇数，数组A左边递

8、增，当Ai是偶数，数组A右边递减。, 6.1.2 数组的顺序存储结构,void part(int A, int n) int i=1,j=n,k; while (ij) while (Ai%2 != 0) , 6.1.2 数组的顺序存储结构,例2 设有二维数组a(6,8)，每个元素占6个字节存储，a0,0是起始地址为1000，计算 数组a的存储量。 数组的最后一个元素a5,7的起始地址。 按行优先存放时，元素a1,4的起始地址。 按列优先存放时，元素a4,7的起始地址。, 6.1.2 数组的顺序存储结构,解 数组a的存储量=6*8*6=288 (字节) 最后一个元素按行优先和按列优先地址都相同

9、。 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)=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.1.2 数组的顺序存储结构,例3 已知二维数组Amn，求当m=n

10、时，对角线上所有数组元素的和。 算法设计： 本题中一条对角线是aii，其中(0im-1)，另一条对角线是am-i-1,i ，其中(0im-1)。, 6.1.2 数组的顺序存储结构,A,#define MAX 20 void 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; print

11、f(“m,n=”); scanf(“%d,%d”, , 6.1.2 数组的顺序存储结构, 6.2 矩阵的压缩存储,矩阵是数值程序设计中经常用到的数学模型，是由 m 行和 n 列的数值构成（m=n 时称为方阵）。在用高级语言编制的程序中，通常用二维数组表示矩阵，它使矩阵中的每个元素都可在二维数组中找到相对应的存储位置。然而在数值分析的计算中经常出现一些有下列特性的高阶矩阵，即矩阵中有很多值相同的元或零值元，为了节省存储空间，需要对它们进行“压缩存储”，即不存或少存这些值相同的元或零值元。 如果矩阵中值相同的元素或零元素在矩阵中的分布有一定规律，则称之为“特殊矩阵” 。, 6.2.1 对称矩阵的压

12、缩存储, 对称矩阵 若 n 阶方阵A中的元素满足特性 aij =aji 0i, jn-1 则称为 n 阶对称矩阵。 例如A矩阵是一个5阶对称矩阵。, 对称矩阵的存储 为每一对对称矩阵元素分配一个存储空间，则可以将n2个元素压缩到n(n+1)/2个空间，节约了n(n-1)/2个存储单元。 以行为主序存储下三角对称矩阵（包括对角线） 在下三角矩阵中共有n(n+1)/2个元素，假设以一维数组san(n+1)/2作为n阶对称矩阵A的存储结构，则sak和矩阵元素aij之间存在以下一一对应的关系。, 6.2.1 对称矩阵的压缩存储,i(i+1)/2+j 当ij k= j(j+1)/2+i 当ij,第1行,

13、第2行,第3行,第n行,对于任意给定的一组下标(i,j)，均可以利用对应关系在一维数组sa中找到矩阵元素aij=sak，其中，i j是上三角对称矩阵的对应关系；i j是下三角矩阵的对应关系。 以行为主序存储下三角对称矩阵, 6.2.1 对称矩阵的压缩存储, 6.2.1 对称矩阵的压缩存储,A, 6.2.2 三角矩阵的压缩存储, 三角矩阵 若 n 阶方阵中下(上)三角(不包括对角线)中的元均为常量 c 或 0，则称为上(下)三角矩阵 例如，B矩阵是上三角矩阵；C矩阵是下三角矩阵。, 三角矩阵的存储 除了和对称矩阵一样，只存储矩阵的下（上）三角中元素之外，再加上一个常数c的存储空间即可。, 6.2

14、.2 三角矩阵的压缩存储,44下三角矩阵,44上三角矩阵, 6.2.2 三角矩阵的压缩存储, 下三角矩阵 以行为主序，将nn的下三角矩阵中的元素aij存储到一维数组D中。,aij=D(k)，k=i(i+1)/2+j 例 设有一个44的下三角矩阵，以行为主序，对应到一维数组D，求其元素a32所对应D(k)的k值。 解 a32 =D(k) k=3(3+1)/2+2=8, 上三角矩阵 以行为主序，将nn的上三角矩阵中的元素aij存储到一维数组D中。,aij=D(k)，k=n*i-i(i+1)/2 +j 例 设有一个44的上三角矩阵，以行为主序，对应到一维数组D，求其元素a23所对应D(k)的k值。

15、解 a23 =D(k) k=4*2+3-2(2+1)/2=8, 6.2.2 三角矩阵的压缩存储, 6.3 稀疏矩阵,如果矩阵中只有少量的非零值元，并且这些非零值元在矩阵中的分布没有一定规律，则称为随机稀疏矩阵，简称为稀疏矩阵。至于矩阵中究竟含多少个零值元才被称为是稀疏矩阵，目前还没有一个确切的定义，它只是一个凭人的直觉来了解的概念。假设在 m n 的矩阵中有 t 个非零值元，令 =m/n/t ，称 为矩阵的稀疏因子，则通常认定 0.05的矩阵为稀疏矩阵。, 6.3.1 稀疏矩阵的概念,稀疏矩阵中，0元素分布没有规律，为了能够找到相应的元素，采用三元组存储方法。 三元组 用来记录稀疏矩阵中非零元素的位置和元素值的一种表示方法，即将非0元素所在行、列及它的值构成一个三元组结构体(i,j,v)。 将三元组按行优先，同一行中列号从小到大的规律排成一个线性表，称为三元表。以顺序存储结构作为三元组线性表的存储结构，由此得到的稀疏矩阵的一种压缩存储方法，称之谓三元组顺序表。,稀疏矩阵A,A的三元表组, 6.3.1 稀疏矩阵的概念,稀疏矩阵的三元组类型定义 #define MAX=1024; /*最大非零元素个数*/ typedef struct int i,j; /* 非零元素的行号和列号*/ elemtype v; /* 非零元素的值*/