朱战立数据结构第05章课件.ppt

1、第第5 5章章 数组数组主要知识点主要知识点数组的基本概念数组的基本概念动态数组动态数组特殊矩阵特殊矩阵稀疏矩阵稀疏矩阵5.1 5.1 数组的基本概念数组的基本概念1.数组的定义数组的定义数组数组是是n( (n1 1) )个相同数据类型的数据元素个相同数据类型的数据元素a0 0, ,a1 1, ,a2 2,.,.,an-1-1构成的占用一块地址连续的内存单元的有构成的占用一块地址连续的内存单元的有限序列。限序列。 数组中任意一个元素可以用该元素在数组中的位置来表示，数组中任意一个元素可以用该元素在数组中的位置来表示，数组元素的位置通常称作数组元素的位置通常称作数组的下标数组的下标。 相同之处是

2、相同之处是它们都是若干个相同数据类型的数据元素它们都是若干个相同数据类型的数据元素a a0 0,a,a1 1,a,a2 2,.,a,.,a0-10-1构成的有限序列。构成的有限序列。不同之处是不同之处是：（1 1）数组要求其元素占用一块地址连续的内存单元空间，而）数组要求其元素占用一块地址连续的内存单元空间，而线性表无此要求；线性表无此要求；（2 2）线性表的元素是逻辑意义上不可再分的元素，而数组中）线性表的元素是逻辑意义上不可再分的元素，而数组中的每个元素还可以是一个数组；的每个元素还可以是一个数组；（3 3）数组的操作主要是向某个下标的数组元素中存数据和取）数组的操作主要是向某个下标的数组

3、元素中存数据和取某个下标的数组元素，这和线性表的插入、删除操作不同。某个下标的数组元素，这和线性表的插入、删除操作不同。数组符合线性结构的定义。数组和数组符合线性结构的定义。数组和线性表相比线性表相比， 线性结构（包括线性表、堆栈、队列、串）的顺序存储结线性结构（包括线性表、堆栈、队列、串）的顺序存储结构实际就是使用数组来存储。可见，数组是其他数据结构实现构实际就是使用数组来存储。可见，数组是其他数据结构实现顺序存储结构的基础，是软件设计中最基础的数据结构。顺序存储结构的基础，是软件设计中最基础的数据结构。 2.数组的实现机制数组的实现机制()、一维数组（一维数组（n个元素）中任一元素个元素）

4、中任一元素ai Loc(ai)=LOC(a)+i*k (0i n)( () )、一个一个m行行n列的二维数组列的二维数组LOC(aij)=LOC(a00)+(i*n+j)*k (0im，0jn)注：注：C C语言中数组元素采用语言中数组元素采用行主序行主序的存放方法，即的存放方法，即行优先行优先顺序。顺序。a的内存单元地址的内存单元地址每个元素所需的字节个数每个元素所需的字节个数每个元素所需的字节个数每个元素所需的字节个数a0 0的内存单元地址的内存单元地址 a0,0 a0,1 a0,n-1 a1,0 a1,1 a1,n-1 am-1,0 am-1,1 am-1,n-1 Amn=一个一个mn的

5、二维数组可以看成是的二维数组可以看成是m行的一维数行的一维数组，或者组，或者n列的一维数组。列的一维数组。3.数组抽象数据类型数组抽象数据类型数据集合数据集合：数组的数据集合可以表示数组的数据集合可以表示为为a0, a1, a2, ., an-1，每个数据元素的每个数据元素的数据类型为数据类型为抽象数据元素类型抽象数据元素类型DataType。操作集合操作集合：( (1)1)求数组元素个数求数组元素个数ArrayLength(D) ( (2 2) )取数组元素取数组元素Get(D, i)( (3)3)存数组元素存数组元素Storage(D, i, x) 例如，例如， int a10; a3 =

6、 a4; /赋值号右边的赋值号右边的a4是取操作，是取操作，取值取值 /赋值号左边的赋值号左边的a3是存操作，是存操作，取地址取地址5.2 5.2 动态数组动态数组 数组有数组有静态存储结构静态存储结构的数组和的数组和动态存储结构动态存储结构的数组两种，它的数组两种，它们的区别在于：们的区别在于：静态数组在定义时就必须给出数组个数；静态数组在定义时就必须给出数组个数；动态数组是在具体申请存储单元空间时才给出数组元素的个数。动态数组是在具体申请存储单元空间时才给出数组元素的个数。 例例5-2 5-2 定义有定义有3 3行、行、4 4列整数类型的二维数组列整数类型的二维数组a a，先逐行分别先逐行

7、分别给数组元素赋数据给数组元素赋数据1 1，2 2，.，1212，然后显示数组中的数值。，然后显示数组中的数值。要求分别把申请二维动态数组的过程和释放二维动态数组要求分别把申请二维动态数组的过程和释放二维动态数组的过程编写成函数。的过程编写成函数。int *Make2DArray(int row, int col) int *a, i; a = (int *)malloc(row * sizeof(int *); for (i = 0; i row; i+) ai = (int *)malloc(col * sizeof(int); return a;void Diliver2DArray(i

8、nt *a, int row) int i; for(i = 0; i row; i+) free(ai); free(a);#include #include #include #include “Array.h”void main(void) int i, j, c;int row = 3, col = 4, *a; a = Make2DArray(row, col); c = 1; for(i = 0; i row; i+) for(j = 0; j col; j+) aij = c; c+; for(i = 0; i row; i+) for(j = 0; j col; j+) pri

9、ntf(%5d, aij); printf(n); Diliver2DArray(a, row);程序运行输出结果如下：程序运行输出结果如下：1 2 3 41 2 3 45 6 7 85 6 7 89 10 11 129 10 11 12123456789101112a00a03a20a23a1a1a3a注意，二维动态数组的全部存储空间不是一次申请的，所以注意，二维动态数组的全部存储空间不是一次申请的，所以二维动态数组的每一维数组在物理上是连续的，而全部二维二维动态数组的每一维数组在物理上是连续的，而全部二维动态数组在物理上不一定是连续的。动态数组在物理上不一定是连续的。5.3 5.3 特殊矩

10、阵特殊矩阵 特殊矩阵特殊矩阵: :指有许多值相同的元素或有许多零元素、且值指有许多值相同的元素或有许多零元素、且值相同的元素或零元素的分布有一定规律的矩阵。相同的元素或零元素的分布有一定规律的矩阵。1.几种特殊矩阵的压缩存储几种特殊矩阵的压缩存储:(1)(1)n阶对称矩阵阶对称矩阵 在一个在一个n阶方阵阶方阵A A中，若元素满足下述性质：中，若元素满足下述性质： aij= =aji （11i, ,jn） 则称则称A为为n阶对称矩阵阶对称矩阵。如图。如图5.1是一个是一个5阶对称矩阵。阶对称矩阵。 1 5 1 3 7 a11 5 0 8 0 0 a21 a22 1 8 9 2 6 a31 a32

11、 a33 3 0 2 5 1 . 7 0 6 1 3 an1 an2 an3 ann n阶对称矩阵中的元素关于主对角线对称，故只要存储矩阵中阶对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三角或下三角中的元素，让每两个对称的元素共享一个存储上三角或下三角中的元素，让每两个对称的元素共享一个存储空间，这样，能节约近一半的存储空间。空间，这样，能节约近一半的存储空间。 在这个下三角矩阵中，第在这个下三角矩阵中，第i行恰有行恰有i个元素，元素总数为个元素，元素总数为n(n+1)/2，这样就可将这样就可将n2个数据元素压缩存储在个数据元素压缩存储在n(n+1)/2个存个存储单元中。储单元中。 假

12、设以一维数组假设以一维数组va作为作为n n阶对称矩阵阶对称矩阵A的压缩存储单元，的压缩存储单元，k为一维数组为一维数组va的下标序号，的下标序号，aij为为n n阶对称矩阵阶对称矩阵A中中i行行j列的数列的数据元素据元素( (其中其中11i, ,jn ），），其数学映射关系为：其数学映射关系为： i(i-1)/2+j-1 当当ij j(j-1)/2+i-1 当当ijk=(2)(2)n n阶三角矩阵阶三角矩阵 以主对角线划分，以主对角线划分， n n阶三角矩阵有阶三角矩阵有n n阶上三角矩阵和阶上三角矩阵和n n阶阶下三角矩阵两种。下三角矩阵两种。 n n阶上三角矩阵如下图阶上三角矩阵如下图

13、( (a)a)所示，它的下三角（不包括所示，它的下三角（不包括主对角线）中的元素均为主对角线）中的元素均为0 0（或常数）。（或常数）。n n阶下三角矩阵正好阶下三角矩阵正好相反，它的主对角线上方均为相反，它的主对角线上方均为0 0（或常数），如下图（或常数），如下图 ( (b)b)所所示。示。 注：在大多数情况下，注：在大多数情况下， n n阶三角矩阵常数为零。阶三角矩阵常数为零。 a11 a12 a 1n a11 c c c a22 a 2n a21 a22 c . c c a nn an1 an2 an n (a)(a)上三角矩阵上三角矩阵 ( (b)b)下三角矩阵下三角矩阵 假设以一维

14、数组假设以一维数组sa作为作为n阶下三角矩阵阶下三角矩阵A的压缩存储单元，的压缩存储单元，k为一维数组为一维数组va的下标序号，的下标序号，aij为为n阶下三角矩阵阶下三角矩阵A中中i行行j列的列的数据元素数据元素( (其中其中11i, ,jn ），），其数学映射关系为：其数学映射关系为： i(i-1)/2+j-1 当当ijn(n+1)/2 （或空）或空） 当当ijk=注：此时一维数组注：此时一维数组sasa的数据元素个数为的数据元素个数为( (n(n+1)/2)+1n(n+1)/2)+1个，个，其中数组其中数组sasa的最后一个位置存储的最后一个位置存储A A中数值不为中数值不为0 0的那个

15、常数。的那个常数。例例5.3 5.3 为节省内存，为节省内存，n n阶对称矩阵采用压缩存储，要求：阶对称矩阵采用压缩存储，要求：（1 1）编写实现）编写实现C = A + BC = A + B操作的函数。设矩阵操作的函数。设矩阵A A、矩阵矩阵B B和矩阵和矩阵C C均采均采用压缩存储方式存储，矩阵元素均为整数类型。用压缩存储方式存储，矩阵元素均为整数类型。（2 2）编写一个采用压缩存储的）编写一个采用压缩存储的n n阶对称矩阵的输出函数，要求阶对称矩阵的输出函数，要求输出显示成矩阵形式，设矩阵元素均为整数类型。输出显示成矩阵形式，设矩阵元素均为整数类型。（3 3）设矩阵）设矩阵A A和矩阵和

16、矩阵B B为如下所示的矩阵，编写一个用矩阵为如下所示的矩阵，编写一个用矩阵A A和和矩阵矩阵B B作为测试例子的测试上述函数的主程序。作为测试例子的测试上述函数的主程序。void Add(int a, int b, int c, int n) int i; for(i = 0; i = n*(n+1)/2-1; i+) ci = ai + bi;void Print(int a, int n) int i, j, k; for(i = 1; i = n; i+) for(j = 1; j = j)k = i * (i - 1) / 2 + j - 1; else k = j * (j - 1)

17、 / 2 + i - 1;printf(%d , ak); printf(n); #include （矩阵加和输出函数同上，省略）矩阵加和输出函数同上，省略）void main(void) int a = 1,2,4,3,5,6, b = 10,20,40,30,50,60,c6; /*注意元素的排列次序注意元素的排列次序*/ int n = 3; Add(a, b, c, n); Print(c, n);5.4 5.4 稀疏矩阵稀疏矩阵 1.概念概念 (1)(1)、稀疏矩阵、稀疏矩阵 矩阵中非零元素的个数远远小于矩阵元素个数。矩阵中非零元素的个数远远小于矩阵元素个数。 (2) 、稠密矩阵、稠

18、密矩阵 一个不稀疏的矩阵。一个不稀疏的矩阵。 (3) 、稀疏矩阵压缩存储方法、稀疏矩阵压缩存储方法 只存储只存储稀疏矩阵中的非零元素，稀疏矩阵中的非零元素，实现方法是实现方法是:将每个非将每个非 零元素用一个零元素用一个三元组三元组（i，j，aij）来表示，则每个来表示，则每个稀疏矩稀疏矩 阵可用一个阵可用一个来表示。来表示。5000000000037000000000190000000000002500017011001,3,11,1,5,17,2,2,25,4,1,19,5,4,37,6,7,50(a)(b)1234567123456列 号行 号稀疏矩阵和对应的三元组线性表稀疏矩阵和对应的

19、三元组线性表 2. 2. 三元组顺序表三元组顺序表 指用顺序表存储的三元组线性表。指用顺序表存储的三元组线性表。 typedef struct int i; int j; elemtype d; DataType; typedef struct int md; int nd; int td; TriType;112456.0123456MaxSize-1.352147.111725193750.Size=6676mdndtdijd3.3.稀疏矩阵的三元组链表稀疏矩阵的三元组链表(1)(1)三元组链表三元组链表 用链表存储的三元组线性表。用链表存储的三元组线性表。(2)(2)行指针数组结构的三元

20、组链表行指针数组结构的三元组链表 把每行非零元素三元组组织成一个单链表，再设计一个指把每行非零元素三元组组织成一个单链表，再设计一个指针类型的数组存储所有单链表的头指针。针类型的数组存储所有单链表的头指针。(3)(3)三元组十字链表三元组十字链表 把非零元素三元组按行和按列组织成单链表，这样稀疏矩把非零元素三元组按行和按列组织成单链表，这样稀疏矩阵中的每个非零元素三元组结点都将既勾链在行单链表上，阵中的每个非零元素三元组结点都将既勾链在行单链表上，又勾链在列单链表上，形成十字形状。又勾链在列单链表上，形成十字形状。三元组链表中每个结点的数据域由稀疏矩阵非零元的行号、三元组链表中每个结点的数据域

21、由稀疏矩阵非零元的行号、列号和元素值组成。稀疏矩阵三元组线性表的带头结点的三列号和元素值组成。稀疏矩阵三元组线性表的带头结点的三元组链表结构如图所示，元组链表结构如图所示，其中头结点的行号域存储了稀疏矩其中头结点的行号域存储了稀疏矩阵的行数，列号域存储了稀疏矩阵的列数。阵的行数，列号域存储了稀疏矩阵的列数。 这种三元组链表的缺点是实现矩阵运算操作算法的时间这种三元组链表的缺点是实现矩阵运算操作算法的时间复杂度高，因为算法中若要访问某行某列中的一个元素时，复杂度高，因为算法中若要访问某行某列中的一个元素时，必须从头指针进入后逐个结点查找。为降低矩阵运算操作算必须从头指针进入后逐个结点查找。为降低

22、矩阵运算操作算法的时间复杂度，提出了法的时间复杂度，提出了行指针数组结构的三元组链表，行指针数组结构的三元组链表，其其结构如图所示：结构如图所示：012345123456517311225119437750 列号非零元素行指针数组行号头指针 行指针数组结构的三元组链表对于从某行进入后找某行指针数组结构的三元组链表对于从某行进入后找某列元素的操作比较容易实现，但对于从某列进入后找某行列元素的操作比较容易实现，但对于从某列进入后找某行元素的操作就不容易实现，为此又提出了元素的操作就不容易实现，为此又提出了三元组十字链表三元组十字链表结构，结构，结构如下：结构如下： 各单链表均各单链表均不带头结点不带头结点。由于每个单链表中的。由于每个单链表中的行号行号域数值均域数值均相同相同，所以单链表中省略了三元组的行号域，所以单链表中省略了三元组的行号域，而把而把行号行号统一统一放在放在了指针数组的了指针数组的行号域中行号域中。 123456 行指针数组行号1117横向头指针19375025 1234567列指针数组列号纵向头指针纵向指针横向指针非零元素1)习题习题5-1，5-2 ，5-3 ，5-4 习题习题5-10，5-11 作业作业