数组梁.ppt

《数组梁.ppt》由会员分享，可在线阅读，更多相关《数组梁.ppt（44页珍藏版）》请在三一文库上搜索。

1、第5章 数组,主讲：梁宝兰,2,第5章 数组,教学要求： 理解和掌握：数组的基本概念，与线性表的区别，定位数组元素的计算公式(按行/列存储)，动态数组类的声明与实现(申请、释放、构造、赋值、重置、下标运算等)，常用特殊矩阵(对称矩阵、上/下三角矩阵)的存储及表示方式，稀疏矩阵的三元组表示方式及转置运算的实现。,3,内容提要,数组的基本概念 动态数组类 特殊矩阵 稀疏矩阵,4,5.1 数组的基本概念,一、数组的定义 数组是n(n1)个相同数据类型的数据元素a0,a1,a2,.,an-1构成的占用一块地址连续的内存单元的有限序列。 数组中任意一个元素可以用该元素在数组中的位置来表示，数组元素的位置

2、通常称作数组的下标。,5,5.1 数组的基本概念,a11 a12 a1n a21 a22 a2n am1 am2 amn,A=,数组示例,二维数组A可以看成是由m个行向量组成的向量，也可以看成是n个列向量组成的向量。 多维数组一旦被定义，它的维数和维界就不再改变。,6,数组和线性表相比： 相同之处: 都是若干个相同数据类型的数据元素 不同之处 （1）元素是否可以再分解； （2）操作不同； （3）存储空间是否连续；,5.1 数组的基本概念,7,a11 a12 a1n a21 a22 a2n am1 am2 amn,A=,数组与线性表区别：,二维数组是数据元素为线性表的线性表。,5.1 数组的基本

3、概念,8,在多维数组中插入（或删除）一个元素有意义吗？,将元素 x 插入 到数组中第1行第2列。,删除数组中 第1行第2列元素。,数组与线性表区别：,5.1 数组的基本概念,9, 取值：给定一组下标，读出对应的数组元素； 赋值：给定一组下标，存储或修改与其相对应的数组元素。 存取和修改操作本质上只对应一种操作寻址,多维数组应该采用何种方式存储？,多维数组没有插入和删除操作，所以，不用预留空间，适合采用顺序存储。,数组与线性表区别：,5.1 数组的基本概念,10,一维数组的存储与寻址 设一维数组每个数组元素占用 c 个存储单元，则其任一元素 ai 的存储地址可由下式确定： Loc(ai)Loc(

4、a0)ic,a0,ai-1,ai, ,an-1,a1, ,二、数组的实现机制,11,二、数组的实现机制,二维数组的存储与寻址,常用的映射方法有两种： 按行优先：先行后列，先存储行号较小的元素，行号相同者先存储列号较小的元素。 按列优先：先列后行，先存储列号较小的元素，列号相同者先存储行号较小的元素。,二维数组 内存 （二维结构） （ 一维结构),12,二、数组的实现机制,0,n-1,0,m-1,(a) 二维数组,aij前面的元素个数 =整行数每行元素个数+本行中 aij前面的元素个数 =i nj,按行优先存储的寻址,Loc(aij)Loc(a00)(i nj )c,i,j,13,二、数组的实现

5、机制,Loc(aijk ) = Loc(a000) +( im2m3 + jm3 + k )c,n（n2）维数组一般也采用按行优先和按列优先两种存储方法。请自行推导任一元素存储地址的计算方法。,多维数组的存储与寻址,14,ADT 数组 数据集合： 数组的数据集合可以表示为a0, a1, a2, ., an-1，每个数据元素的数据类型为抽象数据元素类型DataType。 操作集合： (1)初始化数组 Initiate(D) (2)取数组元素个数 Size(D) (3)存数组元素 Storage(D,i,x) (4)取数组元素 Get(D, i) End ADT,三、数组抽象数据类型,15,一、动

6、态数组的有关概念 动态数组与静态数组的区别： 静态数组在定义时就必须给出数组个数； 动态数组是在具体申请存储单元空间时才给出数组元素的个数。 在C+语言中，动态创建数组的运算符是new，动态撤消组的运算符是delete。,5.2 动态数组类,16,一、动态数组的有关概念 申请数组占用的内存空间 数据类型 *指针名 new 数据类型数组元素个数； 如：int *pa = new int10; 释放数组中占用的内存空间 delete 指针名; 如：delete pa;,5.2 动态数组类,17,typedef int DataType; class Array public: Array(int

7、sz = 100); /构造函数 Array(const Array,二、动态数组类的实现,18,构造函数 Array:Array(int sz) if(sz = 0) cout “无效的数组个数“ endl; exit(0); arr = new DataTypesz; /为数组申请内存空间 size = sz; /置数组个数 ,二、动态数组类的实现,19,拷贝构造函数 Array:Array(const Array /置数组个数 ,二、动态数组类的实现,20,析构函数 Array:Array(void) delete arr; /释放内存空间 取数组元素个数 int Array:Size(

8、void)const return size; ,二、动态数组类的实现,21,赋值运算符重载 void Array:operator=(const Array /置数组个数 ,二、动态数组类的实现,22,下标运算符重载 DataType ,二、动态数组类的实现,23,5.3 特殊矩阵,一、特殊矩阵的定义 特殊矩阵是指有许多值相同的元素或有许多零元素，且值相同的元素或零元素的分布有一定规律的矩阵。 二、几种特殊矩阵的压缩存储 1、n阶对称矩阵 在一个n阶方阵A中，若元素满足下述性质： aij=aji （1i, jn） 则称A为n阶对称矩阵。,24,5.3 特殊矩阵,1、n阶对称矩阵的压缩存储,3

9、 6 4 7 8 6 2 8 4 2 4 8 1 6 9 7 4 6 0 5 8 2 9 5 7,A,对称矩阵特点：aij=aji,如何压缩存储？,只存储下三角部分的元素。,25,5.3 特殊矩阵,1、n阶对称矩阵的压缩存储,(a) 下三角矩阵 (b) 存储说明 (c) 计算方法,阴影部分的面积 = i(i-1)/2+ j 一维数组下标从0开始 按行优先存储，aij在一维数组中的下标 k= i(i-1)/2+ j-1,1 i n,1 j n,每行元素个数,1 2 i+1 n,aij,aij存放位置,26,5.3 特殊矩阵,1、n阶对称矩阵的压缩存储,对于下三角中的元素aij（ij），在数组中的

10、下标k与i、j的关系为：k i(i-1)/2+ j -1。 上三角中的元素aij（ij），因为aijaji，则访问和它对应的元素aji即可，即：k j(j-1)/2+ i-1 。,第2行,第n行,第1行,a11,a21,a22,a31,a32,a33,aij,a n1,an2,ann,第3行,0 1 2 3 4 5 k n(n+1)/2-1,27,2、n阶三角矩阵 以主对角线划分， n阶三角矩阵有n阶上三角矩阵和n阶下三角矩阵两种。 n阶上三角矩阵，它的主对角线下方均为0（或常数）。n阶下三角矩阵正好相反，它的主对角线上方均为0（或常数）。 注：在大多数情况下， n阶三角矩阵常数为零。,5.3

11、 特殊矩阵,28,假设以一维数组va作为n阶下三角矩阵A的压缩存储单元，k为一维数组va的下标序号，aij为n阶下三角矩阵A中i行j列的数据元素(其中1i,jn ），其数学映射关系为：,此时一维数组va的数据元素个数为(n(n+1)/2)+1个，其中数组va的最后一个位置存储A中数值不为0的那个常数。,5.3 特殊矩阵,2、n阶三角矩阵,29,一、稀疏矩阵 矩阵中非零元素的个数远远小于矩阵元素个数。,5.4 稀疏矩阵,在存储稀疏矩阵时，如何只存储非零元素？ 稀疏矩阵中的非零元素的分布没有规律。,30,一、稀疏矩阵,5.4 稀疏矩阵,将稀疏矩阵中的每个非零元素表示为： (行号，列号，非零元素值)

12、三元组,三元组表:=(1,1,15), (2,2,11) , (3,4,6) , (4,4,8) , (5,1,9) ,31,例1：写出下图5.3所示稀疏矩阵的压缩存储形式。 1 2 3 4 5 6 1 2 3 4 5 6,解：用三元组线性表表示： 1,2,12,1,3,9,3,1,-3,3,5,14, 4,3,24,5,2,18,6,1,15,6,4,-7,32,二、稀疏矩阵压缩顺序存储方法,5.4 稀疏矩阵,5（非零元个数）,struct DataType int row, col; /行号，列号 ElemType value; /非零元素值 ;,定义三元组：,33,稀疏矩阵压缩顺序存储类

13、,class SeqSpaMatrix: public SeqList /三元组顺序表类 /SeqSpaMatrix类以public方式继承SeqList类 /输出流重载 friend ostream,34,void CreateMatrix(int r, int c, int d, DataType item) /创建一个有r行、c列和d个非零元的三元组顺序表 /创建的数值来自数组item rows = r; /置行数 cols = c; /置列数 dNum = d; /置非零元个数 for(int i = 0; i d; i+) /依次插入三元组元素 Insert(itemi, i); ,

14、35,void SeqSpaMatrix:Transpose(SeqSpaMatrix ,源程序,36,二、稀疏矩阵压缩单链式存储方法,5.4 稀疏矩阵,结点结构：,头结点结构：,37,三、稀疏矩阵压缩行指针数组结构的三元组链表,5.4 稀疏矩阵,38,*四、稀疏矩阵压缩行三元组十字链表,5.4 稀疏矩阵,39,本章实验预告,利用顺序存储三元组表实现稀疏矩阵的加法运算。 输入稀疏矩阵A的非零元素，然后打印出该矩阵，再输入稀疏矩阵B的非零元素，然后打印出该矩阵，然后求出矩阵A+B的和并输出该矩阵。,40,本章小结,本章主要讲述了数组的基本概念，与线性表的区别，定位数组元素的计算公式(按行/列存储)，动态数组类的声明与实现(申请、释放、构造、赋值、重置、下标运算等)，常用特殊矩阵(对称矩阵、上/下三角矩阵)的存储及表示方式，稀疏矩阵的三元组表示方式(顺序表、带行指针数组的链表、十字链表)及转置运算的实现。,41,练 习 题,P131第1、11题,42,实 验 练 习,P132第17题。,43,进 阶,推导多维数组的按行/列优先存储的定位数组元素的计算公式。 如何实现对称矩阵的乘法运算(P132的第13题)？ 稀疏矩阵除了三元组表示方式以外，还有其它的表示方式吗？,44,课外阅读,1、了解广义表。,