第5章----数组和广义表课件

第第5 5章章 数组和广义表数组和广义表本章主题：本章主题：本章主题：本章主题：多维数组、特殊矩阵和广义表多维数组、特殊矩阵和广义表多维数组、特殊矩阵和广义表多维数组、特殊矩阵和广义表 教学目的：教学目的：教学目的：教学目的：掌握掌握掌握掌握数组和广义表数组和广义表数组和广义表数组和广义表的的的的定义、运算及存储结构定义、运算及存储结构定义、运算及存储结构定义、运算及存储结构教学难点：教学难点：教学难点：教学难点：矩阵的压缩存储矩阵的压缩存储矩阵的压缩存储矩阵的压缩存储2024/7/121 本本本本章章章章主主主主要要要要介介介介绍绍绍绍数数数数组组组组的的的的概概概概念念念念及及及及多多多多维维维维数数数数组组组组在在在在计计计计算算算算机机机机中中中中的的的的存存存存放放放放，特特特特殊殊殊殊矩矩矩矩阵阵阵阵的的的的压压压压缩缩缩缩存存存存储储储储及及及及相相相相应应应应运运运运算算算算，广广广广义义义义表表表表的的的的概概概概念念念念和和和和存存存存储储储储结结结结构构构构及及及及其相关运算的实现。通过本章学习，要求掌握如下内容：其相关运算的实现。通过本章学习，要求掌握如下内容：其相关运算的实现。通过本章学习，要求掌握如下内容：其相关运算的实现。通过本章学习，要求掌握如下内容：1 1多维数组的定义及在计算机中的存储表示；多维数组的定义及在计算机中的存储表示；多维数组的定义及在计算机中的存储表示；多维数组的定义及在计算机中的存储表示；2 2对对对对称称称称矩矩矩矩阵阵阵阵、三三三三角角角角矩矩矩矩阵阵阵阵、对对对对角角角角矩矩矩矩阵阵阵阵等等等等特特特特殊殊殊殊矩矩矩矩阵阵阵阵在在在在计计计计算算算算机机机机中中中中的的的的压缩存储表示及地址计算公式；压缩存储表示及地址计算公式；压缩存储表示及地址计算公式；压缩存储表示及地址计算公式；3 3稀疏矩阵的三元组表示及转置算法实现；稀疏矩阵的三元组表示及转置算法实现；稀疏矩阵的三元组表示及转置算法实现；稀疏矩阵的三元组表示及转置算法实现；4 4稀疏矩阵的十字链表表示及相加算法实现；稀疏矩阵的十字链表表示及相加算法实现；稀疏矩阵的十字链表表示及相加算法实现；稀疏矩阵的十字链表表示及相加算法实现；5 5广义表存储结构表示及基本运算。广义表存储结构表示及基本运算。广义表存储结构表示及基本运算。广义表存储结构表示及基本运算。本章学习导读本章学习导读本章学习导读本章学习导读 2024/7/122 数组和广义表可看成是一种特殊的线性表，其特殊在于，数组和广义表可看成是一种特殊的线性表，其特殊在于，数组和广义表可看成是一种特殊的线性表，其特殊在于，数组和广义表可看成是一种特殊的线性表，其特殊在于，表中的数所元素本身也是一种线性表。表中的数所元素本身也是一种线性表。表中的数所元素本身也是一种线性表。表中的数所元素本身也是一种线性表。5 5.1.1 .1.1 数组的定义数组的定义数组的定义数组的定义 数组是大家都已经很熟悉的一种数据类型，几乎所有高级语数组是大家都已经很熟悉的一种数据类型，几乎所有高级语言程序设计中都设定了数组类型。言程序设计中都设定了数组类型。数组数组（ArrayArray）是由是由n(n1)个个相同类型数据元素相同类型数据元素a0，al，ai，an-1构成的构成的有限序列有限序列。n是数组的长度。其中数组中的数据元素是数组的长度。其中数组中的数据元素ai是一个数据结构，即是一个数据结构，即ai可以是线性表中的一个元素，本身也可以是可以是线性表中的一个元素，本身也可以是一个线性表一个线性表，而线性子表中的每一个数据元素还可以再分解，而线性子表中的每一个数据元素还可以再分解。根据数组元素。根据数组元素ai的组织形式不同，数组可以分为一维数组、二维的组织形式不同，数组可以分为一维数组、二维数组以及多维（数组以及多维（n维）数组。维）数组。5 5.1 .1 数数数数 组组组组2024/7/123 有时也把有时也把有时也把有时也把一维数组一维数组一维数组一维数组称为称为称为称为向量向量向量向量，二维数组二维数组二维数组二维数组称为称为称为称为矩阵矩阵矩阵矩阵。在二。在二。在二。在二维或多维数组中，每个数组元素都受到维或多维数组中，每个数组元素都受到维或多维数组中，每个数组元素都受到维或多维数组中，每个数组元素都受到2 2个或个或个或个或n n个关系的约束。个关系的约束。个关系的约束。个关系的约束。当数组为当数组为当数组为当数组为n n维时，其对应线性表中的每个元素又是一个线性维时，其对应线性表中的每个元素又是一个线性维时，其对应线性表中的每个元素又是一个线性维时，其对应线性表中的每个元素又是一个线性表。在每个关系中，每个元素都有一个直接后继。因此，就表。在每个关系中，每个元素都有一个直接后继。因此，就表。在每个关系中，每个元素都有一个直接后继。因此，就表。在每个关系中，每个元素都有一个直接后继。因此，就其单个关系而言，这其单个关系而言，这其单个关系而言，这其单个关系而言，这n n个关系中的每一个仍然是一种线性关个关系中的每一个仍然是一种线性关个关系中的每一个仍然是一种线性关个关系中的每一个仍然是一种线性关系。系。系。系。数数数数组组组组中中中中每每每每个个个个元元元元素素素素都都都都是是是是由由由由一一一一个个个个值值值值和和和和一一一一组组组组下下下下标标标标来来来来确确确确定定定定的的的的。同同同同线线线线性性性性表表表表一一一一样样样样，数数数数组组组组中中中中的的的的所所所所有有有有数数数数据据据据元元元元素素素素都都都都必必必必须须须须属属属属于于于于同同同同一一一一数数数数据据据据类类类类型型型型。元元元元素素素素下下下下标标标标的的的的个个个个数数数数被被被被称称称称为为为为数数数数组组组组的的的的维维维维数数数数。显显显显然然然然，当当当当维维维维数数数数为为为为1 1 1 1时时时时，数组就退化为定长的线性表。数组就退化为定长的线性表。数组就退化为定长的线性表。数组就退化为定长的线性表。2024/7/1241一维数组一维数组 一一维维数数组组可可以以看看成成是是一一个个线线性性表表或或一一个个向向量量，它它在在计计算算机机内内是是存放在一块连续的存储单元中，适合于随机查找。存放在一块连续的存储单元中，适合于随机查找。一维数组记为一维数组记为一维数组记为一维数组记为AnAnAnAn或或或或A=(aA=(aA=(aA=(a0 0 0 0，a a a al l l l，a a a ai i i i，a a a an-1n-1n-1n-1)一一维维数数组组中中，一一旦旦a0的的存存储储地地址址、一一个个数数据据元元素素所所占占存存储储单单元元数数k确定，则确定，则ai的存储地址的存储地址LOC(ai)就可求出：就可求出：LOC(ai)=LOC(a0)+i*k (0in)2二维数组二维数组 二二维维数数组组，又又称称矩矩阵阵(matrix)。二二维维数数组组中中的的每每一一个个元元素素又又是是一一个个定定长长的的线线性性表表（一一维维数数组组），都都要要受受到到两两个个关关系系即即行行关关系系和和列列关关系系的的约约束束，也也就就是是每每个个元元素素都都同同属属于于两两个个线线性性表表。例例如如，设设A是是一个有一个有m行行n列的二维数组，则列的二维数组，则A可以表示为：可以表示为：2024/7/125 可可以以看看成成由由m m个个行行向向量量组组成成的的向向量量，也也可可以以看看由由n n个个列列向向量量组组成成的向量。的向量。数数组组中中的的每每个个元元素素由由元元素素值值a aijij及及一一组组下下标标（i i，j j）来来确确定定。a aijij既属于第既属于第i i行的行向量，又属于第行的行向量，又属于第j j列的列向量。列的列向量。其中，其中，a ai i=(=(a ai i,0,0 a ai i,1,1 a ai i,n-1,n-1)(0)(0i in)n)可以认为可以认为A Am*nm*n=A=A，A A是这样的一维数组：是这样的一维数组：A=(aA=(a0 0，a al l，a ai i，a am-1m-1)2024/7/126 显显然然，二二维维数数组组同同样样满满足足数数组组的的定定义义。一一个个二二维维数数组组可可以以看看作作是是每每个个数数据据元元素素都都是是相相同同类类型型的的一一维维数数组组。以以此此类类推推，任任何何多多维维数数组组都都可可以以看看作作一一个个线线性性表表，这这时时线线性性表表中中的的每每个个数数据据元元素素也也是一个线性表。多维数组是特殊的线性表，是线性表的推广。是一个线性表。多维数组是特殊的线性表，是线性表的推广。数组的性质：数组的性质：(1)(1)数数组组中中的的数数据据元元素素数数目目固固定定。一一旦旦定定义义了了一一个个数数组组，其其数数据据元素数目不再有增减变化。它属于静态分配存储空间的数据结构。元素数目不再有增减变化。它属于静态分配存储空间的数据结构。(2)(2)数组中的数据元素必须具有相同的数据类型。数组中的数据元素必须具有相同的数据类型。(3)(3)数组中的每个数据元素都有一组唯一的下标值。数组中的每个数据元素都有一组唯一的下标值。(4)(4)数数组组是是一一种种随随机机存存储储结结构构。可可随随机机存存取取数数组组中中的的任任意意数数据据元素。元素。2024/7/1275.1.2 5.1.2 数组的基本操作数组的基本操作数组的基本操作数组的基本操作 数组一旦被定义，它的维数和维界就不再改变。因此，除了结数组一旦被定义，它的维数和维界就不再改变。因此，除了结构的初始化和销毁之外，构的初始化和销毁之外，数组的基本操作一般不会含有元素的插入数组的基本操作一般不会含有元素的插入或删除等操作或删除等操作,数组只有数组只有访问数组元素访问数组元素和修改元素值的操作。和修改元素值的操作。(1)(1)value(Avalue(A，indexindexl l，indexindex2 2，indexindexd d)：A A是已存在的是已存在的d d维维数组，数组，indexindexl l，indexindex2 2，indexindexd d是指定的是指定的d d个下标值，且这些下个下标值，且这些下标均不超过对应维的上界。其运算结果是返回由下标指定的标均不超过对应维的上界。其运算结果是返回由下标指定的A A中的对中的对应元素的值。应元素的值。(2)(2)assign(Aassign(A，e e，indexindexl l，indexindex2 2，indexindexd d)：A A是是已已存存在在的的d d维维数数组组，e e为为元元素素变变量量，indexindexl l，indexindex2 2，indexindexd d是是指指定定的的d d个个下下标标值值，且且这这些些下下标标均均未未越越界界。其其运运算算结结果果是是将将e e的的值值赋赋给给由由下下标标指指定定的的A A中的对应元素。中的对应元素。2024/7/128(3)(3)dispdisp(A)(A)：输出数组输出数组A A的所有元素。的所有元素。在大多数程序设计语言中，取数组元素值操作在大多数程序设计语言中，取数组元素值操作value(Avalue(A，indexindexl l，indexindex2 2，indexindexd d)通常直接写作通常直接写作AAindexindexl l index index2 2 indexindexd d，而对数组元素的赋值操作而对数组元素的赋值操作assign(Aassign(A，e e，indexindexl l，indexindex2 2，indexindexd d)写作写作e=Ae=Aindexindexl l index index2 2 indexindexd d，或者类似的形式。或者类似的形式。2024/7/129 5.1.3 5.1.3 数组的存储结构数组的存储结构数组的存储结构数组的存储结构 由于数组一般不作删除或插入运算，所以一旦数组被定义后，由于数组一般不作删除或插入运算，所以一旦数组被定义后，数组中的元素个数和元素之间的关系就不再变动。通常采用顺序存数组中的元素个数和元素之间的关系就不再变动。通常采用顺序存储结构表示数组。储结构表示数组。对于一维数组，数组的存储结构关系为对于一维数组，数组的存储结构关系为:LOC(ai)=LOC(a0)+i*k (0in)对于二维数组，由于计算机的存储单元是一维线性结构，如何对于二维数组，由于计算机的存储单元是一维线性结构，如何用线性的存储结构存放二维数组元素就有行用线性的存储结构存放二维数组元素就有行/列次序问题。常用两列次序问题。常用两种存储方法：以行序种存储方法：以行序(row major order)row major order)为主序的存储方式和以列为主序的存储方式和以列序序(column major order)column major order)为主序的存储方式。为主序的存储方式。2024/7/1210 行优先顺序行优先顺序将数组元素按行排列，第将数组元素按行排列，第i+1i+1个行向量个行向量紧接在第紧接在第i i个行向量后面。以二维数组为例，按行优先顺序个行向量后面。以二维数组为例，按行优先顺序存储的线性序列为：存储的线性序列为：a a1111,a,a1212,a,a1n1n,a,a2121,a,a2222,a a2n2n,a,am1m1,a,am2m2,a amnmn 在在PASCALPASCAL、C C语言中，数组就是按行优先顺序存储的。语言中，数组就是按行优先顺序存储的。列优先顺序列优先顺序将数组元素按列向量排列，第将数组元素按列向量排列，第j+1j+1个列个列向量紧接在第向量紧接在第j j个列向量之后，个列向量之后，A A的的m*nm*n个元素按列优先顺序个元素按列优先顺序存储的线性序列为：存储的线性序列为：a a1111,a,a2121,a,am1m1,a,a1212,a,a2222,a am2m2,a,an1n1,a,an2n2,a anmnm 在在FORTRANFORTRAN语言中，数组就是按列优先顺序存储的。语言中，数组就是按列优先顺序存储的。2024/7/1211 图图 5-1 二维数组的两种存储结构二维数组的两种存储结构 对对一一个个以以行行序序为为主主序序的的计计算算机机系系统统，当当二二维维数数组组第第一一个个数数据据元元素素a a0,00,0的的存存储储地地址址LOC(aLOC(a0,00,0)以以及及每每个个数数据据元元素素所所占占用用的的存存储储单单元元k k确确定定后，该二维数组中任一数据元素后，该二维数组中任一数据元素a ai i,j,j的存储地址可由下式确定的存储地址可由下式确定:LOC(LOC(a ai i,j,j)=LOC(a)=LOC(a0,00,0)+(i)+(in+jn+j)k)k其中其中n为每行中的列数。为每行中的列数。2024/7/1212 图图 5-1 二维数组的两种存储结构二维数组的两种存储结构 对对一一个个以以行行序序为为主主序序的的计计算算机机系系统统，当当二二维维数数组组第第一一个个数数据据元元素素a a0,00,0的的存存储储地地址址LOC(aLOC(a0,00,0)以以及及每每个个数数据据元元素素所所占占用用的的存存储储单单元元k k确确定定后，该二维数组中任一数据元素后，该二维数组中任一数据元素a ai i,j,j的存储地址可由下式确定的存储地址可由下式确定:LOC(LOC(a ai i,j,j)=LOC(a)=LOC(a0,00,0)+(i)+(in+jn+j)k)k其中其中n为每行中的列数。为每行中的列数。2024/7/1213 【例【例5-15-1】对于给定的二维数组】对于给定的二维数组float a34float a34，计算：计算：(1)(1)数组数组a a中的数组元素数目；中的数组元素数目；(2)(2)若若数数组组a a的的起起始始地地址址为为10001000，且且每每个个数数组组元元素素长长度度为为3232位位(即即4 4个字节个字节)，数组元素，数组元素a23a23的内存地址。的内存地址。【解解】(1)(1)由由于于C C语语言言中中数数组组的的行行、列列下下标标值值的的下下界界均均为为0 0，该该数数组组行行上上界界为为3-1=23-1=2，列列上上界界为为4-1=34-1=3，所所以以该该数数组组的的元元素素数数目目共共有有3*4=123*4=12个。个。(2)(2)由于由于C C语言采用行序为主序的存储方式，有：语言采用行序为主序的存储方式，有：LOC(aLOC(a2,32,3)=LOC(a)=LOC(a0,00,0)+(i*n+j)*k)+(i*n+j)*k =1000+(2*4+3)*4 =1000+(2*4+3)*4 =1044 =10442024/7/1214 【例例5-25-2】有有m m名名学学生生，每每人人考考n n门门功功课课，试试写写出出求求任任一一学学生生总总分分数数和任一课程总分数的数据结构和算法。和任一课程总分数的数据结构和算法。【解解】把把学学生生的的考考试试成成绩绩存存放放在在m m行行n n列列的的二二维维数数组组中中，则则第第i(0i(0im)im)行行第第j(0j(0jn)jn)列列中中存存放放了了第第i i个个学学生生的的第第j j门门课课程程考考试试成成绩。即数据结构为：绩。即数据结构为：#define M 10 /假设假设为为1010人人#define N 3 /假设假设为为3 3int scoreMN;/学生成绩二维数组学生成绩二维数组求第求第i i名学生总分数的算法为：名学生总分数的算法为：int student_sum(int scoreMN,int i)int j,sum=0;for(j=0;jN;j+)sum=sum+scoreij;return(sum);2024/7/1215 求第求第j j门课程总分数的算法为：门课程总分数的算法为：int course_sum(int scoreMN,int j)int i,sum=0;for(i=0;iM;i+)sum=sum+scoreij;return(sum);2024/7/1216 矩阵是数值计算程序设计中经常用到的数学模型，它是矩阵是数值计算程序设计中经常用到的数学模型，它是由由 m m 行和行和 n n 列的数值构成（当列的数值构成（当m=n m=n 时称为方阵）。时称为方阵）。在高在高级程序程序设计语言中言中，通常用，通常用二维数组二维数组二维数组二维数组表示矩阵。然而表示矩阵。然而在数在数值分分析析过程中程中经常遇到一些比常遇到一些比较特殊的矩特殊的矩阵，它，它们的的阶数很高，数很高，矩阵中元素数量很大，而且有很多元素的值相同或零值元素，矩阵中元素数量很大，而且有很多元素的值相同或零值元素，如如对称矩称矩阵、三角矩三角矩阵、带状矩状矩阵和和稀疏矩稀疏矩阵等。等。为了节省为了节省存储空间并且加快处理速度，需要对存储空间并且加快处理速度，需要对这类矩矩阵进行压缩存储，进行压缩存储，压缩存储的原则压缩存储的原则是：是：不重复存储相同元素；不存储零值元素不重复存储相同元素；不存储零值元素不重复存储相同元素；不存储零值元素不重复存储相同元素；不存储零值元素。5 5.2 2 矩阵的压缩存储矩阵的压缩存储矩阵的压缩存储矩阵的压缩存储 2024/7/1217 5.2.1 5.2.1 特殊矩阵的压缩存储方法特殊矩阵的压缩存储方法特特特特殊殊殊殊矩矩矩矩阵阵阵阵是是是是指指指指非非非非零零零零元元元元素素素素或或或或零零零零元元元元素素素素的的的的分分分分布布布布有有有有一一一一定定定定规规规规律律律律的的的的矩矩矩矩阵阵阵阵。主要形式有对称矩阵、三角矩阵、对角矩阵等主要形式有对称矩阵、三角矩阵、对角矩阵等主要形式有对称矩阵、三角矩阵、对角矩阵等主要形式有对称矩阵、三角矩阵、对角矩阵等。1 1 1 1对称矩阵的压缩存储对称矩阵的压缩存储对称矩阵的压缩存储对称矩阵的压缩存储 对称矩阵是一个对称矩阵是一个n n阶方阵。若一个方阵。若一个n n阶矩阵阶矩阵A A中的元素满足中的元素满足:a ai i,j,j=a aj j,I,I(0i(0i，jn-1)jn-1)，则称则称A A为为n 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 对称矩阵对称矩阵2024/7/1218 在这个下三角矩阵中，第在这个下三角矩阵中，第i i行恰有行恰有i+1i+1个元素，元素总数为：个元素，元素总数为：(i+1)=n(n+1)/2i+1)=n(n+1)/2 由于对称矩阵中的元素关于主对角线对称，因此由于对称矩阵中的元素关于主对角线对称，因此可以可以为每一每一对对称的矩称的矩阵元素分配元素分配 1 1 个存个存储空空间，n n阶矩矩阵中的中的n nn n个元素个元素就可以被就可以被压缩到到 n(n+1)/2n(n+1)/2 个元素的存个元素的存储空空间中去。中去。称一维数组称一维数组sa0.n(n+1)/2 为为n 阶对称矩阵阶对称矩阵A的压缩存储。的压缩存储。其存储对应关系如上图其存储对应关系如上图:对称矩阵的压缩存储对称矩阵的压缩存储 2024/7/1219 2 2 2 2三角矩阵的压缩存储三角矩阵的压缩存储三角矩阵的压缩存储三角矩阵的压缩存储三三三三角角角角矩矩矩矩阵阵阵阵也也也也是是是是一一一一个个个个n n n n阶阶方方方方阵阵阵阵，有有有有上上上上三三三三角角角角和和和和下下下下三三三三角角角角矩矩矩矩阵阵。下下下下(上上上上)三三三三角角角角矩矩矩矩阵阵是是是是主主主主对对角角角角线线以以以以上上上上（下下下下）元元元元素素素素均均均均为为零零零零的的的的n n n n阶阶矩矩矩矩阵阵。设设设设以以以以一一一一维维维维数数数数组组组组sbsbsbsb0.n(n+1)/20.n(n+1)/20.n(n+1)/20.n(n+1)/2作作作作为为为为n n n n阶阶阶阶三三三三角角角角矩矩矩矩阵阵阵阵B B B B的的的的存存存存储储储储结结结结构构构构，仍仍仍仍采采采采用用用用按按按按行行行行存存存存储储储储方案，则方案，则方案，则方案，则B B B B中任一元素中任一元素中任一元素中任一元素b b b bi,ji,ji,ji,j和和和和sbsbsbsbkkkk之间存在着如下对应关系：之间存在着如下对应关系：之间存在着如下对应关系：之间存在着如下对应关系：其中，其中，sbn(n+1)/2中存放常数中存放常数c或或0。2024/7/1220 3 3对角矩阵的压缩存储对角矩阵的压缩存储对角矩阵的压缩存储对角矩阵的压缩存储 对对对对角角角角方方方方阵阵阵阵(或或或或称称称称带带带带状状状状矩矩矩矩阵阵阵阵)是是是是指指指指所所所所有有有有的的的的非非非非零零零零元元元元素素素素(简简简简称称称称非非非非零零零零元元元元)都都都都集集集集中中中中在在在在以以以以主主主主对对对对角角角角线线线线为为为为中中中中心心心心的的的的带带带带状状状状区区区区域域域域中中中中，即即即即除除除除了了了了主主主主对对对对角角角角线线线线上上上上和和和和紧紧紧紧靠靠靠靠着着着着主主主主对对对对角角角角线线线线上上上上下下下下方方方方若若若若干干干干条条条条对对对对角角角角线线线线上上上上的的的的元元元元素素素素外外外外，所所所所有有有有其其其其它它它它元元元元素素素素皆皆皆皆为为为为零零零零的的的的矩矩矩矩阵阵阵阵。常常见见的的有有三三对对角角矩矩阵阵、五五对对角角矩矩阵阵、七七对对角角矩矩阵阵等等。下图是一个具有下图是一个具有下图是一个具有下图是一个具有3(13(1mmn)n)条非零元素带的条非零元素带的条非零元素带的条非零元素带的n n阶对角矩阵。阶对角矩阵。阶对角矩阵。阶对角矩阵。具有具有3条非零对角线的对角矩阵条非零对角线的对角矩阵 2024/7/1221 对对对对于于于于n n n n阶阶阶阶有有有有m m m m(m(m(m(m必必必必为为为为奇奇奇奇数数数数，因因因因为为为为副副副副对对对对角角角角线线线线关关关关于于于于主主主主对对对对角角角角线线线线对对对对称称称称)条条条条非非非非零元素带的对角矩阵，只需存放对角区域内的所有非零元素即可。零元素带的对角矩阵，只需存放对角区域内的所有非零元素即可。零元素带的对角矩阵，只需存放对角区域内的所有非零元素即可。零元素带的对角矩阵，只需存放对角区域内的所有非零元素即可。在在在在n n n n阶阶阶阶对对对对角角角角矩矩矩矩阵阵阵阵A A A A中中中中，主主主主对对对对角角角角线线线线元元元元素素素素数数数数最最最最多多多多（n n n n个个个个），然然然然后后后后向向向向两两两两边边边边依依依依次次次次减减减减少少少少，每每每每隔隔隔隔一一一一条条条条元元元元素素素素带带带带元元元元素素素素数数数数就就就就减减减减少少少少1 1 1 1个个个个，最最最最外外外外端端端端的的的的对对对对角角角角线线线线有有有有n-n-n-n-(m-1)/2(m-1)/2(m-1)/2(m-1)/2个元素，所以非零元素总数个元素，所以非零元素总数个元素，所以非零元素总数个元素，所以非零元素总数u u u u为：为：为：为：u=mu=mu=mu=mn-2n-2n-2n-2(m-1)/2+(m-1)/2-1)+(m-1)/2+(m-1)/2-1)+(m-1)/2+(m-1)/2-1)+(m-1)/2+(m-1)/2-1)+l+l+l+l=m=mn-(mn-(m2 2-1)/4-1)/4 设设设设以以以以一一一一维维维维数数数数组组组组sasasasau+lu+lu+lu+l为为为为对对对对角角角角矩矩矩矩阵阵阵阵A A A A的的的的存存存存储储储储结结结结构构构构，若若若若按按按按行行行行存存存存储储储储非非非非零零零零元，则元，则元，则元，则A A A A中任一元素中任一元素中任一元素中任一元素a a a ai i i i,j,j,j,j和和和和sasasasakkkk之间存在着如下对应关系：之间存在着如下对应关系：之间存在着如下对应关系：之间存在着如下对应关系：结论结论结论结论：对特殊矩阵的压缩存储实质上就是将二维矩阵中的部分：对特殊矩阵的压缩存储实质上就是将二维矩阵中的部分元素按照某种方案排列到一维数组中，不同的排列方案也就对应元素按照某种方案排列到一维数组中，不同的排列方案也就对应不同的存储方案。不同的存储方案。2024/7/1222 5.2.2 稀疏矩阵的压缩存储方法稀疏矩阵的压缩存储方法 如果一个矩阵中有很多元素的值为零，即零元素的个数远远如果一个矩阵中有很多元素的值为零，即零元素的个数远远大于非零元素的个数时，称该矩阵为稀疏矩阵。大于非零元素的个数时，称该矩阵为稀疏矩阵。根据存储时所附加信息的不同，稀疏矩阵的顺序存储方法包根据存储时所附加信息的不同，稀疏矩阵的顺序存储方法包括：三元组表示法、带辅助行向量的二元组表示法和伪地址表示括：三元组表示法、带辅助行向量的二元组表示法和伪地址表示法，其中以三元组表示法最常用。法，其中以三元组表示法最常用。三元组表示法就是在存储非零元的同时，存储该元素所对应三元组表示法就是在存储非零元的同时，存储该元素所对应的行下标和列下标。稀疏矩阵中的每一个非零元素由一个三元组的行下标和列下标。稀疏矩阵中的每一个非零元素由一个三元组(i i，j j，a aijij)唯一确定。矩阵中所有非零元素存放在由三元组组成唯一确定。矩阵中所有非零元素存放在由三元组组成的数组中。的数组中。由由线性表的两种不同存性表的两种不同存储结构可以得到稀疏矩构可以得到稀疏矩阵压缩的不同的不同的存的存储方法。方法。2024/7/1223 假设有一个假设有一个6 67 7阶稀疏矩阵阶稀疏矩阵A A，其元素情况以及非零元对应其元素情况以及非零元对应的三元组表（以行序为主序）如图所示。的三元组表（以行序为主序）如图所示。(a)稀疏矩阵稀疏矩阵 (b)三元组表三元组表示示 三元组表中的第一行分别表示稀疏矩阵三元组表中的第一行分别表示稀疏矩阵A A的行数、列数和非零的行数、列数和非零元的个数。元的个数。显然，非零元素的三元然，非零元素的三元组是按行号是按行号递增的增的顺序、相同序、相同行号的三元行号的三元组按列号按列号递增的增的顺序排列的。序排列的。2024/7/1224 1 1三元组顺序表三元组顺序表 假假设设以以行行序序为为主主序序，且且以以一一维维数数组组作作为为三三元元组组表表的的存存储储结结构构，可可以以得得到到稀稀疏疏矩矩阵阵的的一一种种压压缩缩存存储储方方法法，称称为为三三元元组组顺顺序序表表。三三元组顺序表的数据结构定义如下：元组顺序表的数据结构定义如下：#define NUM 100 /矩阵中非零元素最大个数矩阵中非零元素最大个数typedef struct /三元组结构三元组结构 int r,c;/行行(列列)号号 ElemType d;/元素值元素值 tupletype;/三元组定义三元组定义typedef struct int rows;/矩阵行数值矩阵行数值 int cols;/矩阵列数值矩阵列数值 int nums;/非零元素个数非零元素个数 tupletype dataNUM;/三元组表三元组表 table;/三元组顺序表定义三元组顺序表定义 2024/7/1225 1稀疏矩阵的转置运算稀疏矩阵的转置运算 转置是矩阵中最简单的一种运算。转置是矩阵中最简单的一种运算。对于一个对于一个m mn n的矩阵其转置矩阵是一个的矩阵其转置矩阵是一个n nm m的矩阵，设为的矩阵，设为B Bn nm m 且满足且满足a ai i,j,j=b bj j,i,i 即：即：aij=bjiaij=bji，其中：其中：00im-1im-1，0jn-10jn-1 即即A A的行是的行是B B的列，的列，A A的列是的列是B B的行。的行。稀疏矩阵的三元组表稀疏矩阵的三元组表2024/7/1226 三元组表示的稀疏矩阵的转置常用的算法有以下两种：三元组表示的稀疏矩阵的转置常用的算法有以下两种：1 1）矩阵的列序转置）矩阵的列序转置（传统的转置算法）（传统的转置算法）矩矩阵阵A是是按按行行序序为为主主序序存存储储的的，若若按按列列序序为为主主序序进进行行转转置置就就可可以以得得到到A阵阵的的转转置置矩矩阵阵B。假假设设矩矩阵阵A的的三三元元组组存存入入一一维维数数组组中中，只只要要在在数数组组中中按按三三元元组组的的列列域域cols的的值值开开始始扫扫描描，从从第第0列列至至第第n-1列列，依依序序将将三三元元组组列列域域与与行行域域之之值值对对换换，并并顺顺次次存存人人数数组组mb中中。算算法法如下：如下：int transpose(table ma,table mb)int i,j,k=0,n,t;if(ma.nums=0)return(0)；/矩阵中无非零元素矩阵中无非零元素 m=ma.rows;/m为矩阵为矩阵A的列数的列数 n=ma.cols;/n为矩阵为矩阵A的行数的行数 t=ma.nums;/为矩阵中非零元素个数为矩阵中非零元素个数 mb.rows=n;/转置矩阵转置矩阵B的列数的列数 mb.cols;/转置矩阵转置矩阵B的行数的行数 mb.nums=t;/转置矩阵中的非零元素个数转置矩阵中的非零元素个数 for(i=0;in;i+)/按矩阵按矩阵A的列序扫描的列序扫描 2024/7/1227 for(j=0;jt;j+)if(ma.dataj.c=i)/判断第判断第j个三元组是不是第个三元组是不是第i列的列的 mb.datak.r=ma.dataj.c;mb.datak.c=ma.dataj.r;mb.datak+.d=ma.dataj.d;return(1);/成功完成矩阵转置成功完成矩阵转置 以以上上算算法法的的时时间间复复杂杂度度分分析析：若若n n为为转转置置矩矩阵阵的的列列数数，t t为为矩矩阵阵中中非非零零元元素素个个数数，则则算算法法的的时时间间花花费费主主要要在在两两个个循循环环上上，所所以以若若时时间间复复杂杂度度为为O(nO(nt)t)。也也就就是是说说，时时间间的的花花费费和和矩矩阵阵A A的的列列数数和和非非零零元元素素个个数数的的乘乘积积成成正正比比。若若用用m mn n的的二二维维数数组组表表示示矩矩阵阵，则则相相应应的的矩矩阵转置算法的循环为：阵转置算法的循环为：for (i=0for (i=0；i in n；i+)i+)for (j=0 for (j=0；j jm m；j+j+bij=aji bij=aji；此时，时间复杂度为此时，时间复杂度为O(mn)。2024/7/1228 2 2）快速转置算法：）快速转置算法：三元组顺序表虽然节省了存储空间，但时间复杂度比三元组顺序表虽然节省了存储空间，但时间复杂度比一般矩阵转置的算法还要复杂，同时还有可能增加算是法一般矩阵转置的算法还要复杂，同时还有可能增加算是法的难度。因此，此算法仅适用于的难度。因此，此算法仅适用于t=m*nt=m*n的情况。的情况。其算法思想为：对其算法思想为：对A A扫描一次，按扫描一次，按A A第二列提供的列号一第二列提供的列号一次确定位置装入次确定位置装入B B的一个三元组。具体实施如下：一遍扫描的一个三元组。具体实施如下：一遍扫描先确定三元组的位置关系，二次扫描由位置关系装入三元先确定三元组的位置关系，二次扫描由位置关系装入三元组。可见，位置关系是此种算法的关键。组。可见，位置关系是此种算法的关键。为为了了预预先先确确定定矩矩阵阵M M中中的的每每一一列列的的第第一一个个非非零零元元素素在在数数组组T T中中应应有有的的位位置置，需需要要先先求求得得矩矩阵阵M M中中的的每每一一列列中中非非零零元元素素的的个个数数。因因为为矩矩阵阵M M中中第第一一列列的的第第一一个个非非零零元元素素在在数数组组T T中中应应有有的的位位置置等等于于前一列第一个非零元素的位置加上前列非零元素的个数。前一列第一个非零元素的位置加上前列非零元素的个数。2024/7/1229 为此，需要设置两个一维数组为此，需要设置两个一维数组num0.nnum0.n和和rposrpos0.n0.n：num0.nnum0.n：统计统计M M中每列非零元素的个数。中每列非零元素的个数。rposrpos0.n0.n：M M中的每列第一个非零元素在中的每列第一个非零元素在T T中的位置。中的位置。算法通过算法通过rposrpos数组建立位置对应关系：数组建立位置对应关系：rposrpos0=0 0=0 ；rpos rpos colcol=rposrpos colcol-1+num-1+numcolcol-1 0-1 0colcolM.rowsM.rows；例例如如图图5-4(5-4(a)a)所所示示的的稀稀疏疏矩矩阵阵的的三三元元组组表表对对应应的的num0.n-1num0.n-1和和rposrpos0.n-10.n-1如图如图5-55-5所示。所示。（算法见教科书）（算法见教科书）图图5-5 5-5 矩阵的矩阵的numnum和和rpos rpos 数组值数组值2024/7/1230 快速转置算法如下：快速转置算法如下：void fasttranstri(tritupletable b,tritupletable a)int p,q,col,k;int num0.a.n,copt0.a.n;b.m=a.n;b.n=a.m;b.t=a.t;if(b.t=0)printf(“a=0”n);for(col=1;col=a.u;+col)numcol=0;for(k=1;k=a.t;+k)+numa.datak.j;cpot0=1;for(col=2;col=a.t;+col)cpotcol=cpotcol-1+numcol-1;for(p=1;p=a.t;+p)col=a.datap.j;q=cpotcol;b.dataq.i=a.datap.j;b.dataq.j=a.datap.i;b.dataq.v=a.datap.v;+cpotcol;2024/7/1231 2 2行逻辑链接的顺序表行逻辑链接的顺序表行逻辑链接的顺序表行逻辑链接的顺序表(带行表的三元组带行表的三元组)有有时时为为了了方方便便某某些些矩矩阵阵运运算算，在在按按行行优优先先存存储储的的三三元元组组中中，加加入入一一个个行行表表来来记记录录稀稀疏疏矩矩阵阵中中每每行行的的非非零零元元素素在在三三元元组组表表中中的的起起始始位位置置。当当将将行行表表作作为为三三元元组组表表的的一一个个新新增增属属性性加加以以描描述述时时，就就得得到到了了稀稀疏疏矩矩阵阵的的另另一一种种顺顺序序存存储储结结构构：带带行行表表的的三三元元组组表表。称称这这种种“带带行行链链接接信信息息”的的三三元元组组表表为为行行逻逻辑辑链接的顺序表。链接的顺序表。其类型描述如下：其类型描述如下：#definedefine maxrow maxrow 100 100 typedef struct typedef struct triple data triple datamaxsizemaxsize;int rpos int rpos maxrowmaxrow;int int n,m,t;n,m,t;rtripletable rtripletable 2024/7/1232 下面讨论两个稀疏矩阵相乘的例子，容易看出这种表示下面讨论两个稀疏矩阵相乘的例子，容易看出这种表示方法的优越性：方法的优越性：若设若设 Q=M*N 其中，其中，M是是m1*n1矩阵，矩阵，N是是m2*n2矩阵。矩阵。当当n1=m2时有：时有：for(i=1;i=m1;+i)for(j=1;j=n2;+j)qij=0 for(k=1;k(N)?(M)：(N)/矩阵行列较大者矩阵行列较大者typedef struct mtxn int row；int col；struct mtxn*right，*down；union int value；struct mtxn*next；tag；MatNode；2024/7/12415 5.3 3 广义表的定义广义表的定义广义表的定义广义表的定义 5.3.1 5.3.1 广义表的定义广义表的定义广义表的定义广义表的定义1 1广义表的定义广义表的定义广义表的定义广义表的定义广广义义表表也也是是线线性性表表的的推推广广，是是一一种种多多层层次次的的线线性性结结构构，线线性性表表中的元素仅限于原子项，即不可以再分；中的元素仅限于原子项，即不可以再分；而而广广义义表表中中的的元元素素既既可可以以是是原原子子项项，也也可可以以是是子子表表（另另一一个个线线性表）。性表）。主要用于人工智能领域的表处理语言主要用于人工智能领域的表处理语言LISPLISP语言。语言。广广义义表表是是n0个个元元素素a1，a2，an的的有有限限序序列列，其其中中每每一一个个ai或或者者是是原原子子，或或者者是是一一个个子子表表。广广义义表表通通常常记记为为LS=(a1,a2,an)，其其中中LS为为广广义义表表的的名名字字，n为为广广义义表表的的长长度度，每每一一个个ai为为广广义义表表的的元元素素。但但在在习习惯惯中中，一一般般用用大大写写字字母母表表示示广广义义表表，小小写写字字母表示原子。母表示原子。若若n=0n=0时为空表。记作：时为空表。记作：L=()L=()。2024/7/1242 当广当广义表表L L非空非空(n n0)0)时，第一个数据元素，第一个数据元素a a0 0被称为广义表的表被称为广义表的表头头(head)head)，其余数据元素组成的表其余数据元素组成的表(a a1 1，a an-1n-1)被称为广义表被称为广义表L L的的表尾表尾(tail)tail)，分别记为分别记为head(A)=ahead(A)=a0 0，tail=(atail=(a1 1，a an-1n-1)。因此：一个广义表是由表头和表尾构成的。因此：一个广义表是由表头和表尾构成的。2 2广义表举例广义表举例广义表举例广义表举例 1）A=()A=()A为空表，长度为为空表，长度为0。2 2）B=(e)B=(e)B B是一个只含有原子是一个只含有原子e e的表，其长度为的表，其长度为l l；。3 3）C=(aC=(a，(b(b，c c，d)d)C是长度为是长度为2的广义表，第一项为原子，第二项为子表。的广义表，第一项为原子，第二项为子表。4 4）D=(AD=(A，B B，C)=()C)=()，(e)(e)，(a(a，(b(b，c c，d)d)5 5）E=(E=(a a，(a a，b b)，(a(a(a(a，b)b)b)b)，c c c c)E E 中只含有一个元素，该元素是一个表，中只含有一个元素，该元素是一个表，E E的长度为的长度为l l。6 6）F=(aF=(a，F)=(aF)=(a，(a(a，(a(a，.).)F F是长度为是长度为2的广义表，第一项为原子，第二项为它本身。的广义表，第一项为原子，第二项为它本身。2024/7/12433广义表的表示方法（用广义表的表示方法（用次序关系和层次关系表示）次序关系和层次关系表示）（1）用）用L=(a1，a2，an)形式，其中每一个形式，其中每一个ai为原子或广义表为原子或广义表 例如：例如：A=(b,c)B=(a,A)E=(a,E)都是广义表。都是广义表。（2）将广义表中所有子表写成原子形式，并利用圆括号嵌套）将广义表中所有子表写成原子形式，并利用圆括号嵌套例如，广义表例如，广义表A、B、C可以描述为：可以描述为：A(b,c)B(a,A(b,c)E(a,E(a,E（）)（3）将广义表用树和图来描述将广义表用树和图来描述 （层次关系）层次关系）上面提到的广义表上面提到的广义表A、B、C的描述见图的描述见图5-8。（次序关系）（次序关系）2024/7/1244 广义表中数据元素的最大层次为表的深度。数据元素的层次广义表中数据元素的最大层次为表的深度。数据元素的层次就是包括该元素韵括号对就是包括该元素韵括号对 的数目。例如广义表的数目。例如广义表G=(a，b，(c，(d)中，数据元素中，数据元素a，b在第一层，数据元素在第一层，数据元素c在第二层，数据元在第二层，数据元素素d在第三层，广义表在第三层，广义表G的深度为的深度为3。（次序关系）（次序关系）图图 5-8 广义表的图形表示广义表的图形表示 从图从图5-8可以看出：广义表的图形表示像倒着画的一棵树，可以看出：广义表的图形表示像倒着画的一棵树，树根结点代表整个广义表，各层树枝结点代表相应的子表，树叶树根结点代表整个广义表，各层树枝结点代表相应的子表，树叶结点代表单元素或空表（如结点代表单元素或空表（如A表）。表）。2024/7/1245 4 4广义表的深度广义表的深度广义表的深度广义表的深度 一个广义表的深度是指该广义表一个广义表的深度是指该广义表展开后所含展开后所含括号括号括号括号的的层数层数层数层数。例如，例如，A=(b,c)的深度为的深度为1，B=(A,d)的深度为的深度为2，C=(f,B,h)的深度为的深度为3;广义表兼有线性结构和层次结构的特性，归纳如下：广义表兼有线性结构和层次结构的特性，归纳如下：(1)(1)广义表中的数据元素有固定的相对次序；广义表中的数据元素有固定的相对次序；(2)(2)广义表的长度定义为最外层括弧中包含的数据元素个数；广义表的长度定义为最外层括弧中包含的数据元素个数；(3)(3)广广义义表表的的深深度度定定义义为为广广义义表表书书写写形形式式中中括括弧弧的的最最大大重重数数，因因此此空空表表的的深深度度为为1 1，因因为为一一个个单单元元素素不不是是广广义义表表，所所以以从从定定义义上上讲讲没没有有深深度可言，但可以认为它的深度为度可言，但可以认为它的深度为0 0；(4)(4)广广义义表表可可被被其其它它广广义义表表所所共共享享。例例如如上上述述例例子子中中广广义义表表B B同同时时也也是广义表是广义表 D D 中的一个子表；中的一个子表；(5)广广义义表表可可以以是是一一个个自自递递归归的的表表。例例如如上上述述例例子子中中的的广广义义表表 F，自递归的广义表的长度是个有限值，而深度为无限值。自递归的广义表的长度是个有限值，而深度为无限值。2024/7/1246 5广义表的分类广义表的分类（1）线性表：元素全部是原子的广义表。）线性表：元素全部是原子的广义表。（2）纯表：与树对应的广义表，见图）纯表：与树对应的广义表，见图5-8的的(c)、(d)、(e)。（3）再入表：与图对应的广义表再入表：与图对应的广义表(允许结点共享允许结点共享)，（4）递归表：允许有递归关系的广义表，例如递归表：允许有递归关系的广义表，例如E=(a,E)。这四种表的关系满足：递归表这四种表的关系满足：递归表 再入表再入表 纯表纯表 线性表线性表 再入表再入表2024/7/1247 5.3.2 广义表的存储结构由由于于广广义义表表的的元元素素类类型型不不一一定定相相同同，表表中中的的数数据据元元素素可可以以是是单单元元素素（原原子子项项），也也可可以以是是广广义义表表，因因此此，难难以以用用顺顺序序结结构构存存储储表表中中元元素素，通通常常采采用用链链接接存存储储方方法法来来存存储储广广义义表表中中元元素素，并并称称之之为为广广义义链链表。表。需要两种结构的结点：需要两种结构的结点：(1)(1)表表结结点点：用用以以表表示示广广义义表表。由由三三个个域域组组成成：标标志志域域tagtag、指指向向表表头头的的指指针针域域sublistsublist和和指指向向下下一一个个结结点点的的指指针针域域linklink。如如图图5-9(5-9(a)a)所示。所示。(2)原原子子结结点点：用用以以表表示示原原子子项项。由由三三个个域域组组成成：标标志志域域tag、值值域域data和指向下一个元素结点的指针域和指向下一个元素结点的指针域link。如图如图5-9(b)所示。所示。2024/7/1248 每每个个数数据据元元素素都都可可用用表表结结点点或或原原子子结结点点表表示示。它它们们的的主主要要区区别别在于从不同的角度反映广义表的构成。在于从不同的角度反映广义表的构成。例如，广义表例如，广义表C的链表存储结构如图的链表存储结构如图5-10所示。所示。图图 5-10 广义表广义表(a,(b,c,d)的链表存储结构的链表存储结构图图 二叉树二叉树2024/7/1249广义表的链式结构描述如下：广义表的链式结构描述如下：typedef char ElemType;typedef struct glnode int tag;union ElemType data;struct glnode*sublist;val;struct glnode*link;GListNode;可将一个广义表看成一棵树，为了方便存储，通常将其转换可将一个广义表看成一棵树，为了方便存储，通常将其转换成一棵二叉树成一棵二叉树。广义表广义表C转换成二叉树过程转换成二叉树过程 如图如图5-11所示：所示：2024/7/1250广义表广义表C C图图5-11 广义表的转换过程广义表的转换过程 2024/7/12515.3.3 5.3.3 广义表的基本操作广义表的基本操作广义表的基本操作广义表的基本操作 广义表的基本操作主要有：广义表的基本操作主要有：求广义表的长度和深度、向广求广义表的长度和深度、向广义表插入元素和从广义表中查找或删除元素、建立广义表的存储义表插入元素和从广义表中查找或删除元素、建立广义表的存储结构、输出广义表和复制广义表等。结构、