1、第5章 数组,主要知识点,数组的基本概念 动态数组 特殊矩阵 稀疏矩阵,5.1 数组的基本概念,1.数组的定义,数组是n(n1)个相同数据类型的数据元素a0,a1,a2,.,an-1构成的占用一块地址连续的内存单元的有限序列。,数组中任意一个元素可以用该元素在数组中的位置来表示，数组元素的位置通常称作数组的下标。,相同之处是它们都是若干个相同数据类型的数据元素a0,a1,a2,.,a0-1构成的有限序列。 不同之处是： （1）数组要求其元素占用一块地址连续的内存单元空间，而线性表无此要求； （2）线性表的元素是逻辑意义上不可再分的元素，而数组中的每个元素还可以是一个数组； （3）数组的操作主要
2、是向某个下标的数组元素中存数据和取某个下标的数组元素，这和线性表的插入、删除操作不同。,数组符合线性结构的定义。数组和线性表相比，,线性结构（包括线性表、堆栈、队列、串）的顺序存储结构实际就是使用数组来存储。可见，数组是其他数据结构实现顺序存储结构的基础，是软件设计中最基础的数据结构。,2.数组的实现机制,()、一维数组（n个元素）中任一元素ai的内存单元地址Loc(ai)=LOC(a)+i*k (0i n)()、一个m行n列的二维数组LOC(aij)=LOC(a00)+(i*n+j)*k (0im，0jn)注：C语言中数组元素采用行主序的存放方法，即行优先顺序。,a的内存单元地址,每个元素所
3、需的字节个数,每个元素所需的字节个数,a0的内存单元地址,一个mn的二维数组可以看成是m行的一维数组，或者n列的一维数组。,3.数组抽象数据类型,数据集合： 数组的数据集合可以表示为a0, a1, a2, ., an-1，每个数据元素的数据类型为抽象数据元素类型DataType。 操作集合： (1)求数组元素个数ArrayLength(D) (2)取数组元素Get(D, i) (3)存数组元素Storage(D, i, x),例如， int a10;a3 = a4; /赋值号右边的a4是取操作，取值/赋值号左边的a3是存操作，取地址,5.2 动态数组,数组有静态存储结构的数组和动态存储结构的数
4、组两种，它们的区别在于： 静态数组在定义时就必须给出数组个数； 动态数组是在具体申请存储单元空间时才给出数组元素的个数。,例5-2 定义有3行、4列整数类型的二维数组a，先逐行分别给数组元素赋数据1，2，.，12，然后显示数组中的数值。要求分别把申请二维动态数组的过程和释放二维动态数组的过程编写成函数。,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);retur
5、n a; ,void Diliver2DArray(int *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+)
6、 for(j = 0; j col; j+)printf(“%5d“, aij);printf(“n“); Diliver2DArray(a, row); ,程序运行输出结果如下：1 2 3 45 6 7 89 10 11 12,注意，二维动态数组的全部存储空间不是一次申请的，所以二维动态数组的每一维数组在物理上是连续的，而全部二维动态数组在物理上不一定是连续的。,5.3 特殊矩阵,特殊矩阵:指有许多值相同的元素或有许多零元素、且值相同的元素或零元素的分布有一定规律的矩阵。,1.几种特殊矩阵的压缩存储:,(1)n阶对称矩阵 在一个n阶方阵A中，若元素满足下述性质：aij=aji （1i,jn）
7、,则称A为n阶对称矩阵。如图5.1是一个5阶对称矩阵。1 5 1 3 7 a115 0 8 0 0 a21 a221 8 9 2 6 a31 a32 a333 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个存储单元中。假设以一维数组va作为n阶对称矩阵A的压缩存储单元，k为一维数组va的下标序号，aij为n阶对
8、称矩阵A中i行j列的数据元素(其中1i,jn ），其数学映射关系为：,i(i-1)/2+j-1 当ijj(j-1)/2+i-1 当ij,k=,(2)n阶三角矩阵以主对角线划分， n阶三角矩阵有n阶上三角矩阵和n阶下三角矩阵两种。n阶上三角矩阵如下图 (a)所示，它的下三角（不包括主对角线）中的元素均为0（或常数）。n阶下三角矩阵正好相反，它的主对角线上方均为0（或常数），如下图 (b)所示。注：在大多数情况下， n阶三角矩阵常数为零。,a11 a12 a 1n a11 c cc a22 a 2n a21 a22 c. c c a nn an1 an2 an n (a)上三角矩阵 (b)下三角矩
9、阵,假设以一维数组sa作为n阶下三角矩阵A的压缩存储单元，k为一维数组va的下标序号，aij为n阶下三角矩阵A中i行j列的数据元素(其中1i,jn ），其数学映射关系为：,i(i-1)/2+j-1 当ij n(n+1)/2 （或空） 当ij,k=,注：此时一维数组sa的数据元素个数为(n(n+1)/2)+1个，其中数组sa的最后一个位置存储A中数值不为0的那个常数。,例5.3 为节省内存，n阶对称矩阵采用压缩存储，要求： （1）编写实现C = A + B操作的函数。设矩阵A、矩阵B和矩阵C均采 用压缩存储方式存储，矩阵元素均为整数类型。 （2）编写一个采用压缩存储的n阶对称矩阵的输出函数，要求
10、输出显示成矩阵形式，设矩阵元素均为整数类型。 （3）设矩阵A和矩阵B为如下所示的矩阵，编写一个用矩阵A和矩阵B作为测试例子的测试上述函数的主程序。,void Add(int a, int b, int c, int n) int i;for(i = 0; i = j)k = i * (i - 1) / 2 + j - 1;else k = j * (j - 1) / 2 + i - 1;printf(“%d “, ak);printf(“n“); ,#include （矩阵加和输出函数同上，省略） void main(void) int a = 1,2,4,3,5,6, b = 10,20,4
11、0,30,50,60,c6;/*注意元素的排列次序*/ int n = 3;Add(a, b, c, n);Print(c, n); ,5.4 稀疏矩阵,1.概念(1)、稀疏矩阵矩阵中非零元素的个数远远小于矩阵元素个数。(2) 、稠密矩阵一个不稀疏的矩阵。(3) 、稀疏矩阵压缩存储方法 只存储稀疏矩阵中的非零元素，实现方法是:将每个非 零元素用一个三元组（i，j，aij）来表示，则每个稀疏矩 阵可用一个三元组线性表来表示。,稀疏矩阵和对应的三元组线性表,2. 三元组顺序表,指用顺序表存储的三元组线性表。typedef structint i; int j;elemtype d; DataTyp
12、e;typedef structint md; int nd; int td; TriType;,3.稀疏矩阵的三元组链表,(1)三元组链表用链表存储的三元组线性表。 (2)行指针数组结构的三元组链表把每行非零元素三元组组织成一个单链表，再设计一个指针类型的数组存储所有单链表的头指针。 (3)三元组十字链表把非零元素三元组按行和按列组织成单链表，这样稀疏矩阵中的每个非零元素三元组结点都将既勾链在行单链表上，又勾链在列单链表上，形成十字形状。,三元组链表中每个结点的数据域由稀疏矩阵非零元的行号、列号和元素值组成。稀疏矩阵三元组线性表的带头结点的三元组链表结构如图所示，其中头结点的行号域存储了稀疏
13、矩阵的行数，列号域存储了稀疏矩阵的列数。,这种三元组链表的缺点是实现矩阵运算操作算法的时间复杂度高，因为算法中若要访问某行某列中的一个元素时，必须从头指针进入后逐个结点查找。为降低矩阵运算操作算法的时间复杂度，提出了行指针数组结构的三元组链表，其结构如图所示：,行指针数组结构的三元组链表对于从某行进入后找某列元素的操作比较容易实现，但对于从某列进入后找某行元素的操作就不容易实现，为此又提出了三元组十字链表结构，结构如下：,各单链表均不带头结点。由于每个单链表中的行号域数值均相同，所以单链表中省略了三元组的行号域，而把行号统一放在了指针数组的行号域中。,1)习题5-1，5-2 ，5-3 ，5-4习题5-10，5-11,作业,
