《《数据结构（C语言版）》电子教案－赵坚 数据结构05》由会员分享，可在线阅读，更多相关《《数据结构（C语言版）》电子教案－赵坚 数据结构05（64页珍藏版）》请在金锄头文库上搜索。
1、2019/5/25,1,第5章 数组和广义表,本章主题：多维数组、特殊矩阵和广义表 教学目的：掌握数组和广义表的定义、运算及存储结构 教学难点：矩阵的压缩存储,2019/5/25,2,本章主要介绍数组的概念及多维数组在计算机中的存放，特殊矩阵的压缩存储及相应运算，广义表的概念和存储结构及其相关运算的实现。通过本章学习，要求掌握如下内容： 1多维数组的定义及在计算机中的存储表示； 2对称矩阵、三角矩阵、对角矩阵等特殊矩阵在计算机中的压缩存储表示及地址计算公式； 3稀疏矩阵的三元组表示及转置算法实现； 4稀疏矩阵的十字链表表示及相加算法实现； 5广义表存储结构表示及基本运算。,本章学习导读,201
2、9/5/25,3,数组和广义表可看成是一种特殊的线性表，其特殊在于，表中的数所元素本身也是一种线性表。 5.1 .1 数组的定义 数组是大家都已经很熟悉的一种数据类型，几乎所有高级语言程序设计中都设定了数组类型。 数组（Array）是由n(n1)个相同类型数据元素a0，al，ai，an-1构成的有限序列。n是数组的长度。其中数组中的数据元素ai是一个数据结构，即ai可以是线性表中的一个元素，本身也可以是一个线性表，而线性子表中的每一个数据元素还可以再分解 。根据数组元素ai的组织形式不同，数组可以分为一维数组、二维数组以及多维（n维）数组。,5.1 数 组,2019/5/25,4,有时也把一维
3、数组称为向量，二维数组称为矩阵。在二维或多维数组中，每个数组元素都受到2个或n个关系的约束。当数组为n维时，其对应线性表中的每个元素又是一个线性表。在每个关系中，每个元素都有一个直接后继。因此，就其单个关系而言，这n个关系中的每一个仍然是一种线性关系。 数组中每个元素都是由一个值和一组下标来确定的。同线性表一样，数组中的所有数据元素都必须属于同一数据类型。元素下标的个数被称为数组的维数。显然，当维数为1时，数组就退化为定长的线性表。,2019/5/25,5,1一维数组 一维数组可以看成是一个线性表或一个向量，它在计算机内是存放在一块连续的存储单元中，适合于随机查找。 一维数组记为An或A=(
4、a0，al，ai，an-1) 一维数组中，一旦a0的存储地址、一个数据元素所占存储单元数k确定，则ai的存储地址LOC(ai)就可求出： LOC(ai)=LOC(a0)+i*k (0in) 2二维数组 二维数组，又称矩阵(matrix)。二维数组中的每一个元素又是一个定长的线性表（一维数组），都要受到两个关系即行关系和列关系的约束，也就是每个元素都同属于两个线性表。例如，设A是一个有m行n列的二维数组，则A可以表示为：,2019/5/25,6,可以看成由m个行向量组成的向量，也可以看由n个列向量组成的向量。 数组中的每个元素由元素值aij及一组下标（i，j）来确定。aij既属于第i行的行向量，
5、又属于第j列的列向量。 其中，ai=( ai,0 ai,1 ai,n-1) (0in) 可以认为Am*n=A，A是这样的一维数组： A=( a0，al，ai，am-1),2019/5/25,7,显然，二维数组同样满足数组的定义。一个二维数组可以看作是每个数据元素都是相同类型的一维数组。以此类推，任何多维数组都可以看作一个线性表，这时线性表中的每个数据元素也是一个线性表。多维数组是特殊的线性表，是线性表的推广。 数组的性质： (1) 数组中的数据元素数目固定。一旦定义了一个数组，其数据元素数目不再有增减变化。它属于静态分配存储空间的数据结构。 (2) 数组中的数据元素必须具有相同的数据类型。 (
6、3) 数组中的每个数据元素都有一组唯一的下标值。 (4) 数组是一种随机存储结构。可随机存取数组中的任意数据元素。,2019/5/25,8,5.1.2 数组的基本操作 数组一旦被定义，它的维数和维界就不再改变。因此，除了结构的初始化和销毁之外，数组的基本操作一般不会含有元素的插入或删除等操作,数组只有访问数组元素和修改元素值的操作。 (1) value(A，indexl，index2，indexd)：A是已存在的d维数组，indexl，index2，indexd是指定的d个下标值，且这些下标均不超过对应维的上界。其运算结果是返回由下标指定的A中的对应元素的值。 (2) assign(A，e，i
7、ndexl，index2，indexd)：A是已存在的d维数组，e为元素变量，indexl，index2，indexd是指定的d个下标值，且这些下标均未越界。其运算结果是将e的值赋给由下标指定的A中的对应元素。,2019/5/25,9,(3) disp(A)：输出数组A的所有元素。 在大多数程序设计语言中，取数组元素值操作value(A，indexl，index2，indexd) 通常直接写作Aindexl index2indexd，而对数组元素的赋值操作assign(A，e，indexl，index2，indexd)写作e= Aindexl index2indexd，或者类似的形式。,201
8、9/5/25,10,5.1.3 数组的存储结构 由于数组一般不作删除或插入运算，所以一旦数组被定义后，数组中的元素个数和元素之间的关系就不再变动。通常采用顺序存储结构表示数组。 对于一维数组，数组的存储结构关系为: LOC(ai)=LOC(a0)+i * k (0in) 对于二维数组，由于计算机的存储单元是一维线性结构，如何用线性的存储结构存放二维数组元素就有行/列次序问题。常用两种存储方法：以行序(row major order)为主序的存储方式和以列序(column major order)为主序的存储方式。,2019/5/25,11,行优先顺序将数组元素按行排列，第i+1个行向量紧接在第
9、i个行向量后面。以二维数组为例，按行优先顺序存储的线性序列为： a11,a12,a1n,a21,a22,a2n,am1,am2,amn 在PASCAL、C语言中，数组就是按行优先顺序存储的。 列优先顺序将数组元素按列向量排列，第j+1个列向量紧接在第j个列向量之后，A的m*n个元素按列优先顺序存储的线性序列为： a11,a21,am1,a12,a22,am2,an1,an2,anm 在FORTRAN语言中，数组就是按列优先顺序存储的。,2019/5/25,12,图 5-1 二维数组的两种存储结构,对一个以行序为主序的计算机系统，当二维数组第一个数据元素a0,0的存储地址LOC(a0,0)以及每
10、个数据元素所占用的存储单元k确定后，该二维数组中任一数据元素ai,j的存储地址可由下式确定: LOC(ai,j)=LOC(a0,0)+(in+j) k 其中n为每行中的列数。,2019/5/25,13,图 5-1 二维数组的两种存储结构,对一个以行序为主序的计算机系统，当二维数组第一个数据元素a0,0的存储地址LOC(a0,0)以及每个数据元素所占用的存储单元k确定后，该二维数组中任一数据元素ai,j的存储地址可由下式确定: LOC(ai,j)=LOC(a0,0)+(in+j) k 其中n为每行中的列数。,2019/5/25,14,【例5-1】对于给定的二维数组float a34，计算： (1
11、) 数组a中的数组元素数目； (2) 若数组a的起始地址为1000，且每个数组元素长度为32位(即4个字节)，数组元素a23的内存地址。 【解】(1)由于C语言中数组的行、列下标值的下界均为0，该数组行上界为3-1=2，列上界为4-1=3，所以该数组的元素数目共有3*4=12个。 (2)由于C语言采用行序为主序的存储方式，有： LOC(a2,3)=LOC(a0,0)+(i*n+j)*k =1000+(2*4+3)*4 =1044,2019/5/25,15,【例5-2】有m名学生，每人考n门功课，试写出求任一学生总分数和任一课程总分数的数据结构和算法。 【解】把学生的考试成绩存放在m行n列的二维
12、数组中，则第i(0i为10人 #define N 3 /假设为3 int scoreMN; /学生成绩二维数组 求第i名学生总分数的算法为： int student_sum(int scoreMN,int i) int j,sum=0; for(j=0;jN;j+) sum=sum+scoreij; return(sum); ,2019/5/25,16,求第j门课程总分数的算法为： int course_sum(int scoreMN,int j) int i,sum=0; for(i=0;iM;i+) sum=sum+scoreij; return(sum); ,2019/5/25,17,矩
13、阵是数值计算程序设计中经常用到的数学模型，它是由 m 行和 n 列的数值构成（当m=n 时称为方阵）。在高级程序设计语言中，通常用二维数组表示矩阵。然而在数值分析过程中经常遇到一些比较特殊的矩阵，它们的阶数很高，矩阵中元素数量很大，而且有很多元素的值相同或零值元素，如对称矩阵、三角矩阵、带状矩阵和稀疏矩阵等。为了节省存储空间并且加快处理速度，需要对这类矩阵进行压缩存储，压缩存储的原则是：不重复存储相同元素；不存储零值元素。,5.2 矩阵的压缩存储,2019/5/25,18,5.2.1 特殊矩阵的压缩存储方法 特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵。主要形式有对称矩阵、三角矩阵、对角
14、矩阵等。 1对称矩阵的压缩存储 对称矩阵是一个n阶方阵。若一个n阶矩阵A中的元素满足: ai,j=aj,I (0i，jn-1)，则称A为n阶对称矩阵。,1 5 1 3 7 a00 5 0 8 0 0 a10 a 11 1 8 9 2 6 a20 a21 a23 3 0 2 5 1 7 0 6 1 3 an-1 0 a n-1 1 a n-1 2 a n-1 n-1,对称矩阵,2019/5/25,19,在这个下三角矩阵中，第i行恰有i+1个元素，元素总数为： (i+1)=n(n+1)/2 由于对称矩阵中的元素关于主对角线对称，因此可以为每一对对称的矩阵元素分配 1 个存储空间，n阶矩阵中的nn个
15、元素就可以被压缩到 n(n+1)/2 个元素的存储空间中去。,称一维数组sa0n(n+1)/2 为n 阶对称矩阵A的压缩存储。其存储对应关系如上图 :,对称矩阵的压缩存储,2019/5/25,20,2三角矩阵的压缩存储 三角矩阵也是一个n阶方阵，有上三角和下三角矩阵。下(上)三角矩阵是主对角线以上（下）元素均为零的n阶矩阵。设以一维数组sb0n(n+1)/2作为n阶三角矩阵B的存储结构，仍采用按行存储方案，则B中任一元素bi,j和sbk之间存在着如下对应关系：,其中，sbn(n+1)/2中存放常数c或0。,2019/5/25,21,3对角矩阵的压缩存储 对角方阵(或称带状矩阵)是指所有的非零元素(简称非零元)都集中在以主对角线为中心的带状区域中，即除了主对角线上和紧靠着主对角线上下方若干条对角线上的元素外，所有其它元素皆为零的矩阵。常见的有三对角矩阵、五对角矩阵、七对角矩阵等。下图是一个具有3(1mn)条非零元素带的n阶对角矩阵。,具有3条非零对角线的对角矩阵,2019/5/25,22,对于n阶有m (m必为奇数，因为副对角线关于主对角线对称) 条非零元素带的对角矩阵，只需存放对角区域内的所有非零元素即可。 在n阶对角矩阵A中，主对角线元素数最多（n个），然后向两边依次减少，每隔一条元
