第五章数组和广义表PPT课件

1、浙江传媒学院浙江传媒学院All rights reserved. 胡智文胡智文, Ph.D, IEEE member第五章第五章 数组和广义表数组和广义表数据结构数据结构 DATA STRUCTURES2第五章第五章 数组和广义表数组和广义表本章要求本章要求了解数组的存储结构，并掌握数组在以行为主的了解数组的存储结构，并掌握数组在以行为主的存储结构中的地址计算方法；存储结构中的地址计算方法；掌握对特殊矩阵进行压缩存储时下标变换公式；掌握对特殊矩阵进行压缩存储时下标变换公式；了解稀疏矩阵的三类压缩存储方法的特点和适用了解稀疏矩阵的三类压缩存储方法的特点和适用范围，掌握以三元组顺序表表示稀疏矩阵时

2、进行范围，掌握以三元组顺序表表示稀疏矩阵时进行矩阵运算采用的处理方法；矩阵运算采用的处理方法；了解广义表的结构特点及其存储表示方法。了解广义表的结构特点及其存储表示方法。重点和难点重点和难点掌握数组及广义表的结构特点及存储表示掌握数组及广义表的结构特点及存储表示3第五章第五章 数组和广义表数组和广义表数组的定义和运算数组的定义和运算数组的顺序存储和实现数组的顺序存储和实现特殊矩阵的压缩存储特殊矩阵的压缩存储三角矩阵三角矩阵带状矩阵带状矩阵稀疏矩阵稀疏矩阵稀疏矩阵稀疏矩阵广义表广义表要点小结要点小结参考书目及网络资源参考书目及网络资源讨论时间讨论时间4第五章第五章 数组和广义表数组和广义表数组的

3、定义和运算数组的定义和运算数组的顺序存储和实现数组的顺序存储和实现特殊矩阵的压缩存储特殊矩阵的压缩存储三角矩阵三角矩阵带状矩阵带状矩阵稀疏矩阵稀疏矩阵稀疏矩阵稀疏矩阵广义表广义表要点小结要点小结参考书目及网络资源参考书目及网络资源讨论时间讨论时间5知识回顾知识回顾-数组数组数组在内存中占用一片连续的存储单元，最低地址数组在内存中占用一片连续的存储单元，最低地址对应于数组的第一个元素，最高地址对应于最后一对应于数组的第一个元素，最高地址对应于最后一个元素，数组可以是一维的，也可以是多维的。个元素，数组可以是一维的，也可以是多维的。 单精度型单精度型双精度型双精度型 整型整型字符型字符型实型（浮点

4、型）实型（浮点型）枚举型枚举型数组类型数组类型共用体类型共用体类型结构体类型结构体类型数据类型数据类型基本类型基本类型构造类型构造类型指针类型指针类型空类型空类型6数组的定义和运算数组的定义和运算数组数组是一种数据类型。从逻辑结构上看，数组是一种数据类型。从逻辑结构上看，数组可以看成是可以看成是一般线性表的扩充一般线性表的扩充。7数组的定义和运算数组的定义和运算某家公司有五位业务人员，于某家公司有五位业务人员，于2007年一至六月年一至六月个人月绩如下表个人月绩如下表:2001 年年 一至六月一至六月 (单位单位 : 百万元百万元 )Sales ASales BSales CSales DSa

5、les EMonth 1120931359987Month 2102115180154118Month 31141259112770Month 410815015366123Month 57910310511598Month 6971101121011358数组的定义和运算数组的定义和运算9数组的定义和运算数组的定义和运算二维数组可以看成是二维数组可以看成是线性表的线性表线性表的线性表。 10数组的定义和运算数组的定义和运算数组的结构特性，实际上数组的结构特性，实际上数组是一组有固定个数组是一组有固定个数的元素的集合数的元素的集合。获得特定位置的元素值获得特定位置的元素值修改特定位置的元素值修

6、改特定位置的元素值数组中每一个元素由一个值和一组下标来描述。数组中每一个元素由一个值和一组下标来描述。“值值”代表数组中元素的数据信息，一组下标代表数组中元素的数据信息，一组下标用来描述该元素在数组中的相对位置信息。用来描述该元素在数组中的相对位置信息。x100 x101x102x103x110 x111x112 x11 3x120 x121x122 x12 3 x000 x001x002x003x010 x011x012 x01 3x020 x021x022 x02 3 11数组的抽象数据类型定义数组的抽象数据类型定义ADT Array数据对象数据对象:D=aj1j2jn|n0，称为数组的维

7、数，称为数组的维数，ji是数组的第是数组的第i维维下标，下标，1jibi，bi为数组第为数组第i维的长度，维的长度，aj1j2jn ElementSet数据关系数据关系: R=R1,R2,Rn,Ri=| 1jkbk,1kn 且且ki,1jibi-1, aj1jijn, aj1ji+1jn D,i=1,n基本操作：基本操作：(1) InitArray(A,n,bound1,boundn):若维数若维数n和各维的长度合和各维的长度合法法,则构造相应的数组则构造相应的数组A,并返回并返回TRUE；(2) DestroyArray(A): 销毁数组销毁数组A；(3) GetValue(A,e,inde

8、x1,indexn): 若下标合法，用若下标合法，用e返回数组返回数组A中由中由index1, ,indexn所指定的元素的值。所指定的元素的值。(4) SetValue(A,e,index1,indexn): 若下标合法，则将数组若下标合法，则将数组A中中由由index1, ,indexn所指定的元素的值置为所指定的元素的值置为e。ADT Array12第五章第五章 数组和广义表数组和广义表数组的定义和运算数组的定义和运算数组的顺序存储和实现数组的顺序存储和实现特殊矩阵的压缩存储特殊矩阵的压缩存储三角矩阵三角矩阵带状矩阵带状矩阵稀疏矩阵稀疏矩阵稀疏矩阵稀疏矩阵广义表广义表要点小结要点小结参考

9、书目及网络资源参考书目及网络资源讨论时间讨论时间13内存储器的结构是一维的内存储器的结构是一维的地地 址址 2001 20022003 3000 内存单元的内容内存单元的内容00100011 000111011100110000110011 CPUBUS14数组的顺序存储和实现数组的顺序存储和实现数组的顺序存储结构有两种：数组的顺序存储结构有两种：按行序存储按行序存储高级语言高级语言BASIC、COBOL、和、和PASCAL语言语言都是以行序为主。都是以行序为主。按列序存储按列序存储高级语言中的高级语言中的FORTRAN语言就是以列序为主。语言就是以列序为主。在高级语言的应用层上，一般不会涉及

10、到在高级语言的应用层上，一般不会涉及到数组的计数组的计算公式算公式。计算内存地址的任务是由高级语言的编译。计算内存地址的任务是由高级语言的编译系统来完成的。在使用时，只需给出数组的下标范系统来完成的。在使用时，只需给出数组的下标范围，编译系统根据用户提供的必要参数，进行地址围，编译系统根据用户提供的必要参数，进行地址分配，用户则不必考虑其内存情况。分配，用户则不必考虑其内存情况。15第五章第五章 数组和广义表数组和广义表数组的定义和运算数组的定义和运算数组的顺序存储和实现数组的顺序存储和实现特殊矩阵的压缩存储特殊矩阵的压缩存储三角矩阵三角矩阵(Triangular Matrices)带状矩阵带

11、状矩阵(Band Matrices)稀疏矩阵稀疏矩阵(Sparse Matrices)稀疏矩阵稀疏矩阵广义表广义表要点小结要点小结参考书目及网络资源参考书目及网络资源讨论时间讨论时间16矩阵的应用矩阵的应用rowscolumnstest1test2test3test4Student0Student1Student2Student3191221912121299122191920201917矩阵的应用矩阵的应用四种食品在三家商店中，单价可用下表给出：四种食品在三家商店中，单价可用下表给出： Food1 Food2 Food3 Food4 Shop1 1717 7 7 1111 2121 Shop

12、2 1515 9 9 1313 1919 Shop3 1818 8 8 1515 1919 =191581819139152111717)(ijbB18特殊矩阵的压缩存储特殊矩阵的压缩存储矩阵矩阵是科学计算、工程数学等，尤其是数值分是科学计算、工程数学等，尤其是数值分析经常研究的对象。析经常研究的对象。在计算机高级语言中，矩阵通常可以采用在计算机高级语言中，矩阵通常可以采用二维二维数组数组的形式来描述。的形式来描述。特殊矩阵压缩原则是：特殊矩阵压缩原则是：对有规律的元素和值相同对有规律的元素和值相同 的元素只分配一个存储的元素只分配一个存储 空间空间对于零元素不分配空间对于零元素不分配空间 1

13、9特殊矩阵的压缩存储特殊矩阵的压缩存储规律分布的特殊矩阵规律分布的特殊矩阵上三角阵上三角阵(upper triangular matrix): 非零元非零元素只出现在对角线及其上方。素只出现在对角线及其上方。-=3000070040100731U20=750013000L特殊矩阵的压缩存储特殊矩阵的压缩存储规律分布的特殊矩阵规律分布的特殊矩阵下三角阵下三角阵(lower triangular matrix): 非零元非零元素只出现在对角线及其下方。素只出现在对角线及其下方。21特殊矩阵的压缩存储特殊矩阵的压缩存储规律分布的特殊矩阵规律分布的特殊矩阵对角阵对角阵(diagonal matrix)

14、：既是上三角阵又：既是上三角阵又是下三角阵。是下三角阵。 -=100030002D22特殊矩阵的压缩存储特殊矩阵的压缩存储带状矩阵：在矩阵中的所有非零元素都集中在带状矩阵：在矩阵中的所有非零元素都集中在以主对角线为中心的带状区域中。其中最常见以主对角线为中心的带状区域中。其中最常见的是三对角带状矩阵。的是三对角带状矩阵。主对角线主对角线b对角线对角线23特殊矩阵的压缩存储特殊矩阵的压缩存储三对角带状矩阵的压缩存储，以行序为主序进三对角带状矩阵的压缩存储，以行序为主序进行存储，并且只存储非零元素。行存储，并且只存储非零元素。确定存储该矩阵所需的一维向量空间的大小确定存储该矩阵所需的一维向量空间的

15、大小从三对角带状矩阵中可看出：除第一行和最后从三对角带状矩阵中可看出：除第一行和最后一行只有两个元素外，其余各行均有一行只有两个元素外，其余各行均有3个非零元个非零元素。由此可得到一维向量所需的空间大小为：素。由此可得到一维向量所需的空间大小为：2+2+3(n-2)=3n-2确定非零元素在一维数组空间中的位置确定非零元素在一维数组空间中的位置Loci, j = Loc1,1+3(i-1)-1+j-i+1 = Loc1,1+2(i-1)+j-124稀疏矩阵稀疏矩阵(Sparse Matrices)25稀疏矩阵稀疏矩阵(Sparse Matrices)稀疏矩阵：矩阵中大多数元素为零的矩阵。稀疏矩阵

16、：矩阵中大多数元素为零的矩阵。 - - -0002800000009100000000600000031101502200158/66=25%(非零元素只占矩阵元素非零元素只占矩阵元素25%30%)26第五章第五章 数组和广义表数组和广义表数组的定义和运算数组的定义和运算数组的顺序存储和实现数组的顺序存储和实现特殊矩阵的压缩存储特殊矩阵的压缩存储稀疏矩阵稀疏矩阵(Sparse Matrices)稀疏矩阵的三元组表表示法稀疏矩阵的三元组表表示法稀疏矩阵的链式存储结构：十字链表稀疏矩阵的链式存储结构：十字链表广义表广义表要点小结要点小结参考书目及网络资源参考书目及网络资源讨论时间讨论时间27稀疏矩

17、阵稀疏矩阵(Sparse Matrices)稀疏矩阵的三元组表表示法稀疏矩阵的三元组表表示法由于稀疏矩阵中非零元素的分布一般是没有规律由于稀疏矩阵中非零元素的分布一般是没有规律的，因此对于稀疏矩阵的压缩存储要求在存储的，因此对于稀疏矩阵的压缩存储要求在存储非非零元素零元素的同时，还必须存储该的同时，还必须存储该非零元素非零元素在矩阵中在矩阵中所处的所处的行号和列号行号和列号。rowcole该非零元该非零元素所在的素所在的行号行号 该非零元该非零元素所在的素所在的列号列号 该非零元该非零元素的值素的值28稀疏矩阵的三元组表表示稀疏矩阵的三元组表表示下标下标行号行号列号列号元素值元素值112122

18、139331-343614553246521876115864-7 - - -0007001500000180000024000140000300000000000912029稀疏矩阵的三元组表表示稀疏矩阵的三元组表表示稀疏矩阵的三元组表示法虽然节约了存储空间，稀疏矩阵的三元组表示法虽然节约了存储空间，但比起矩阵正常的存储方式来讲，其实现相同但比起矩阵正常的存储方式来讲，其实现相同操作要耗费较多的时间即以耗费更多时间为代操作要耗费较多的时间即以耗费更多时间为代价来换取空间的节省。价来换取空间的节省。 同时，也增加了算法同时，也增加了算法的难度。的难度。常常算法的执行时间上的节省一定是以增常常算

19、法的执行时间上的节省一定是以增加空间存储为代价的，反之亦然。加空间存储为代价的，反之亦然。30稀疏矩阵的三元组表表示稀疏矩阵的三元组表表示三元组表的类型说明如下三元组表的类型说明如下#define MAXSIZE 1000/*非零元素个数最多为非零元素个数最多为1000*/typedef struct int row,col; /*该非零元素的行下标和列下标该非零元素的行下标和列下标*/ ElementType e; /*该非零元素的值该非零元素的值*/ Triple;typedef struct Triple dataMAXSIZE+1;/*三元组表。三元组表。data0未未用用*/ int

20、 m,n,len; /*矩阵的行数、列数和非零元素个数矩阵的行数、列数和非零元素个数*/ TSMatrix；31用三元组表实现稀疏矩阵的转置运算用三元组表实现稀疏矩阵的转置运算矩阵转置：指变换元素的位置，把位于（矩阵转置：指变换元素的位置，把位于（row，col）位置上的元素换到（位置上的元素换到（col ，row）位置上，也就是说，）位置上，也就是说，把元素的行列互换。把元素的行列互换。采用矩阵的正常存储方式采用矩阵的正常存储方式(二维数组二维数组)时，实现矩阵转时，实现矩阵转置的经典算法置的经典算法 void TransMatrix(ElementType sourcemn, Elemen

21、tType destnm)/*source和和dest分别为被转置的矩阵和转置后的矩阵（用分别为被转置的矩阵和转置后的矩阵（用二维数组表示）二维数组表示）*/ int i, j; for(i=0;im;i+) for (j=0;jm= A.n; B-n= A.m; B-len= A.len; If (B-len0) j=1; /j为辅助计数器，记录转置后的三元组在三元组表为辅助计数器，记录转置后的三元组在三元组表B中的下标值中的下标值 for(k=1; k=A.n; k+) /扫描三元组表扫描三元组表A共共A.n次，每次寻找列值为次，每次寻找列值为k的三的三元组进行转置元组进行转置 for(i

22、=1; idataj.row=A.datai.col; B-dataj.col=A.datai.row; B-dataj.e=A.datai.e; j+; /计数器计数器j加加1，指向本行下一个转置后元素的位置下标，指向本行下一个转置后元素的位置下标 /内循环中内循环中if结束结束 / if (B-len0)结束结束 /end of TransposeTSMatrix42稀疏矩阵稀疏矩阵“列序列序”递增转置算法递增转置算法算法分析算法分析u算法的时间耗费主要是在双重循环中，算法的时间耗费主要是在双重循环中，其时间复杂度为其时间复杂度为O(A.nA.len)。u最坏情况下，当最坏情况下，当A.l

23、en=A.mA.n时时(即矩即矩阵中全部是非零元素阵中全部是非零元素)，时间复杂度为，时间复杂度为O(A.mA.n2) ，若采用正常方式经典算法，若采用正常方式经典算法实现矩阵转置的算法时间复杂度为实现矩阵转置的算法时间复杂度为O(A.mA.n) 。因此，三元组表法仅适用。因此，三元组表法仅适用于存储表示稀疏矩阵。于存储表示稀疏矩阵。43稀疏矩阵稀疏矩阵“一次定位快速转置一次定位快速转置”算法算法依次按三元组表依次按三元组表A的次序进行转置，转置后直的次序进行转置，转置后直接放到三元组表接放到三元组表B的正确位置上。这种转置算的正确位置上。这种转置算法称为法称为快速转置算法快速转置算法。需要预

24、先计算以下数据：。需要预先计算以下数据：待转置矩阵待转置矩阵source每一列中非零元素的个数每一列中非零元素的个数。（即转置后矩阵（即转置后矩阵dest每一行中非零元素的个数）。每一行中非零元素的个数）。待转置矩阵待转置矩阵source每一列中第一个非零元素在三每一列中第一个非零元素在三元组元组B中的正确位置（即转置后矩阵中的正确位置（即转置后矩阵dest每一行中每一行中第一个非零元素在三元组第一个非零元素在三元组B中的正确位置）中的正确位置） 。为此，需要设两个数组为此，需要设两个数组num 和和position 。使。使positioncol始终指向三元组始终指向三元组A中第中第col列

25、中下一个列中下一个非零元素的正确位置。非零元素的正确位置。44稀疏矩阵稀疏矩阵“一次定位快速转置一次定位快速转置”算法算法col列列numcolpositionnumnumcol用来用来存放三元组存放三元组A中第中第col列中列中非零元素个数非零元素个数(三元组三元组B中第中第col行非零元行非零元素的个数素的个数)。positioncol用来存放转置用来存放转置前三元组前三元组A中中第第col列列(转置转置后三元组后三元组B中中第第col行行)中第中第一个非零元素一个非零元素在三元组在三元组B中中的正确位置。的正确位置。12223241506170 - - -0007001500000180

26、000024000140000300000000000912045稀疏矩阵稀疏矩阵“一次定位快速转置一次定位快速转置”算法算法col列列numcolpositionnumnumcol用来用来存放三元组存放三元组A中第中第col列中列中非零元素个数非零元素个数(三元组三元组B中第中第col行非零元行非零元素的个数素的个数)。positioncol用来存放转置用来存放转置前三元组前三元组A中中第第col列列(转置转置后三元组后三元组B中中第第col行行)中第中第一个非零元素一个非零元素在三元组在三元组B中中的正确位置。的正确位置。121223241506170 - - -0007001500000

27、180000024000140000300000000000912046稀疏矩阵稀疏矩阵“一次定位快速转置一次定位快速转置”算法算法col列列numcolpositionnumnumcol用来用来存放三元组存放三元组A中第中第col列中列中非零元素个数非零元素个数(三元组三元组B中第中第col行非零元行非零元素的个数素的个数)。positioncol用来存放转置用来存放转置前三元组前三元组A中中第第col列列(转置转置后三元组后三元组B中中第第col行行)中第中第一个非零元素一个非零元素在三元组在三元组B中中的正确位置。的正确位置。121222+1=33241506170 - - -00070

28、01500000180000024000140000300000000000912047稀疏矩阵稀疏矩阵“一次定位快速转置一次定位快速转置”算法算法col列列numcolpositionnumnumcol用来用来存放三元组存放三元组A中第中第col列中列中非零元素个数非零元素个数(三元组三元组B中第中第col行非零元行非零元素的个数素的个数)。positioncol用来存放转置用来存放转置前三元组前三元组A中中第第col列列(转置转置后三元组后三元组B中中第第col行行)中第中第一个非零元素一个非零元素在三元组在三元组B中中的正确位置。的正确位置。121222+1=3322+3=5415061

29、70 - - -0007001500000180000024000140000300000000000912048稀疏矩阵稀疏矩阵“一次定位快速转置一次定位快速转置”算法算法col列列numcolpositionnumnumcol用来用来存放三元组存放三元组A中第中第col列中列中非零元素个数非零元素个数(三元组三元组B中第中第col行非零元行非零元素的个数素的个数)。positioncol用来存放转置用来存放转置前三元组前三元组A中中第第col列列(转置转置后三元组后三元组B中中第第col行行)中第中第一个非零元素一个非零元素在三元组在三元组B中中的正确位置。的正确位置。121222+1=3

30、322+3=5412+5=7506170 - - -0007001500000180000024000140000300000000000912049稀疏矩阵稀疏矩阵“一次定位快速转置一次定位快速转置”算法算法col列列numcolpositionnumnumcol用来用来存放三元组存放三元组A中第中第col列中列中非零元素个数非零元素个数(三元组三元组B中第中第col行非零元行非零元素的个数素的个数)。positioncol用来存放转置用来存放转置前三元组前三元组A中中第第col列列(转置转置后三元组后三元组B中中第第col行行)中第中第一个非零元素一个非零元素在三元组在三元组B中中的正确位

31、置。的正确位置。121222+1=3322+3=5412+5=7501+7=86170 - - -0007001500000180000024000140000300000000000912050稀疏矩阵稀疏矩阵“一次定位快速转置一次定位快速转置”算法算法col列列numcolpositionnumnumcol用来用来存放三元组存放三元组A中第中第col列中列中非零元素个数非零元素个数(三元组三元组B中第中第col行非零元行非零元素的个数素的个数)。positioncol用来存放转置用来存放转置前三元组前三元组A中中第第col列列(转置转置后三元组后三元组B中中第第col行行)中第中第一个非零

32、元素一个非零元素在三元组在三元组B中中的正确位置。的正确位置。121222+1=3322+3=5412+5=7501+7=8610+8=870 - - -0007001500000180000024000140000300000000000912051稀疏矩阵稀疏矩阵“一次定位快速转置一次定位快速转置”算法算法col列列numcolpositionnumnumcol用来用来存放三元组存放三元组A中第中第col列中列中非零元素个数非零元素个数(三元组三元组B中第中第col行非零元行非零元素的个数素的个数)。positioncol用来存放转置用来存放转置前三元组前三元组A中中第第col列列(转置转

33、置后三元组后三元组B中中第第col行行)中第中第一个非零元素一个非零元素在三元组在三元组B中中的正确位置。的正确位置。121222+1=3322+3=5412+5=7501+7=8610+8=8701+8=9 - - -0007001500000180000024000140000300000000000912052稀疏矩阵稀疏矩阵“一次定位快速转置一次定位快速转置”算法算法FastTransposeTSMatrix (TSMatrix A, TSMatrix *B)/基于矩阵的三元组表示，采用快速转置法，将矩阵基于矩阵的三元组表示，采用快速转置法，将矩阵A转置为转置为B所指的矩阵所指的矩阵i

34、nt col,t,p,q;int numMAXSIZE, positionMAXSIZE;B-len=A.len; B-n= A.m; B-m= A.n;if(B-len)for(col=1;col=A.n;col+) numcol=0; for(t=1;t=A.len;t+) numA.datat.col+; /计算每一列非零元素的个数计算每一列非零元素的个数 position1=1; /三元组表三元组表A，列值为，列值为1的第一个元素在三元组表的第一个元素在三元组表B的下标值的下标值 /求求col列中第一个非零元素在列中第一个非零元素在B.data 中正确位置中正确位置 for(col=2

35、;colA.n;col+) positioncol=positioncol-1+numcol-1; for(p=1;pdataq.row=A.datap.col; /行列互换，元素赋值行列互换，元素赋值 B-dataq.col=A.datap.row; B-dataq.e=A.datap.e positioncol+; /指向下一个列号为指向下一个列号为col的非零元素在三元组表的非零元素在三元组表B的位置的位置53稀疏矩阵稀疏矩阵“一次定位快速转置一次定位快速转置”算法算法u快速转置算法的时间，主要耗费在四个并列的快速转置算法的时间，主要耗费在四个并列的单循环上，这四个并列的单循环分别执行了

36、单循环上，这四个并列的单循环分别执行了A.n、A.len、A.n-1、A.len次，因而总的时间复杂度为次，因而总的时间复杂度为O(A.n)+O(A.len)+ O(A.n)+ O(A.len)，即为，即为O(A.n +A.len)，当待转置矩阵中非零元素个数接近于，当待转置矩阵中非零元素个数接近于A.mA.n时，其时间复杂度接近于经典算法的时时，其时间复杂度接近于经典算法的时间复杂度间复杂度O(A.mA.n)。u快速转置算法在空间耗费上，除了三元组表所快速转置算法在空间耗费上，除了三元组表所占用的空间外，还需要两个辅助向量空间，即占用的空间外，还需要两个辅助向量空间，即num1. A.n，p

37、osition1. A.n。可见，算法在时。可见，算法在时间上的节省，是以更多的存储空间为代价的。间上的节省，是以更多的存储空间为代价的。54第五章第五章 数组和广义表数组和广义表数组的定义和运算数组的定义和运算数组的顺序存储和实现数组的顺序存储和实现特殊矩阵的压缩存储特殊矩阵的压缩存储稀疏矩阵稀疏矩阵(Sparse Matrices)稀疏矩阵的三元组表表示法稀疏矩阵的三元组表表示法稀疏矩阵的链式存储结构：十字链表稀疏矩阵的链式存储结构：十字链表广义表广义表要点小结要点小结参考书目及网络资源参考书目及网络资源讨论时间讨论时间55稀疏矩阵的链式存储：十字链表稀疏矩阵的链式存储：十字链表用三元组表

38、法比起用二维数组存储，节约了空用三元组表法比起用二维数组存储，节约了空间，并且使得矩阵某些运算的运算时间比经典间，并且使得矩阵某些运算的运算时间比经典算法还少。但是，在进行矩阵加法、减法和乘算法还少。但是，在进行矩阵加法、减法和乘法等运算时，有时矩阵中的非零元素的位置和法等运算时，有时矩阵中的非零元素的位置和个数会发生很大的变化，势必会为了保持三元个数会发生很大的变化，势必会为了保持三元组表组表“以行序为主序以行序为主序”，而大量移动元素。，而大量移动元素。十字链表十字链表(Orthogonal Linked-List)的存储表示，的存储表示，能够灵活地插入因矩阵运算而产生的新的非零能够灵活地

39、插入因矩阵运算而产生的新的非零元素、删除因运算而产生的新的零元素，实现元素、删除因运算而产生的新的零元素，实现矩阵的各种运算。矩阵的各种运算。56十字链表十字链表(Orthogonal Linked-List)在十字链表中，矩阵的每一个非零元素用一个结点在十字链表中，矩阵的每一个非零元素用一个结点表示，该结点除了（表示，该结点除了（row，col，value）以外，还要）以外，还要有以下两个链域：有以下两个链域：down： 用于链接同一行中的下一个非零元素用于链接同一行中的下一个非零元素next：用以链接同一列中的下一个非零元素：用以链接同一列中的下一个非零元素矩阵中任一非零元素矩阵中任一非零

40、元素Mij所对应的结点既处在第所对应的结点既处在第i行的行的行链表上，又处在第行链表上，又处在第j列的列链表上，这好像是处在列的列链表上，这好像是处在一个十字交叉路口上，所以称其为一个十字交叉路口上，所以称其为十字链表十字链表。downnextRowColValue57十字链表的类型定义十字链表的类型定义typedef struct OLNode int row, col; /*非零元素的行和列下标非零元素的行和列下标*/ ElementType value; struct OLNode *right,*down; /*非零元素所在行表列非零元素所在行表列表的后继链域表的后继链域*/ OLNo

41、de; *OLink;typedef struct OLink *row_head, *col_head; /*行、列链表的头指行、列链表的头指针向量针向量*/ int m, n, len; /*稀疏矩阵的行数、列数、非零元素稀疏矩阵的行数、列数、非零元素的个数的个数*/ CrossList; 58十字链表十字链表(Orthogonal Linked-List)Row lists 00620000000750040300downnextRowColValue59十字链表十字链表(Orthogonal Linked-List)Column Lists 00620000000750040300do

42、wnnextRowColValue60十字链表十字链表(Orthogonal Linked-List)Orthogonal Lists 00620000000750040300downnextRowColValue61建立稀疏矩阵的十字链表建立稀疏矩阵的十字链表CreateCrossList (CrossList *M) /*采用十字链表存储结构，创建稀疏矩阵采用十字链表存储结构，创建稀疏矩阵M*/ if(M!=NULL) free(M); scanf(&m,&n,&t); /*输入输入M的行数的行数,列数和非零元素的个数列数和非零元素的个数*/ M-m=m;M-n=n

43、;M-len=t;if(!(M-row_head=(Olink*)malloc(m+1)sizeof(OLink) exit(OVERFLOW); if(!(M-col_head=(OLink *)malloc(n+1)sizeof(OLink) exit(OVERFLOW);M-row_head =M-col_head =NULL; /*初始化行、列头指初始化行、列头指针向量，各行、列链表为空的链表针向量，各行、列链表为空的链表*/ for(scanf(&i,&j,&e);i!=0; scanf(&i,&j,&e) if(!(p=(OLNode

44、 *) malloc(sizeof(OLNode) exit(OVERFLOW); p-row=i;p-col=j;p-value=e; /*生成结点生成结点*/62建立稀疏矩阵的十字链表建立稀疏矩阵的十字链表if(M-row_headi=NULL) M-row_headi=p; else /*寻找行表中的插入位置寻找行表中的插入位置*/ for(q=M-row_headi;q-right&q-right-colright); /空循环体空循环体 p-right=q-right; q-right=p; /*完成插入完成插入*/ if(M-col_headj=NULL) M-col_he

45、adj=p; else /*寻找列表中的插入位置寻找列表中的插入位置*/ for(q=M-col_headj; q-down&q-down-rowdown); /空循环体空循环体 p-down=q-down; q-down=p; /*完成插入完成插入*/ /*for*/ /*CreateCrossList*/63第五章第五章 数组和广义表数组和广义表数组的定义和运算数组的定义和运算数组的顺序存储和实现数组的顺序存储和实现特殊矩阵的压缩存储特殊矩阵的压缩存储稀疏矩阵稀疏矩阵(Sparse Matrices)广义表广义表广义表的概念广义表的概念广义表的存储结构广义表的存储结构广义表的操作实

46、现广义表的操作实现要点小结要点小结参考书目及网络资源参考书目及网络资源讨论时间讨论时间64LISP语言发明人语言发明人-John McCarthyJohn McCarthy (1927.9.4-, USA) LISP, Time-sharing, AI, Algol, Nonmonotonic logicTuring Award(1971)65LISP语言发明人语言发明人-John McCarthy除了获得计算机先驱奖外，还在除了获得计算机先驱奖外，还在1971年获得年获得ACM图图灵奖，灵奖，1988年获得由日本年获得由日本INAMORI基金会所设立的基金会所设立的KYOTO奖。奖。1990

47、年获得美国年获得美国National Medal of Science。1958年年，与与L. Minsky(1995年计算机先驱奖获得者年计算机先驱奖获得者)一起组建了世界上第一个人工智能实验室，并第一一起组建了世界上第一个人工智能实验室，并第一个提出了将计算机的批处理方式改造成为能同时允个提出了将计算机的批处理方式改造成为能同时允许许多多用户使用的分时方式用户使用的分时方式(time-sharing)的建议，并的建议，并推动推动MIT成立组织开展研究。其结果就是实现了世成立组织开展研究。其结果就是实现了世界上最早的分时系统界上最早的分时系统基于基于IBM 7094的的CTSS和其和其后的后

48、的MULTICS。66LISP语言发明人语言发明人-John McCarthy1959年，基于年，基于Alonzo Church的的-演算和演算和H.A. Simon 、A. Newell首创的首创的“表结构表结构”，开发了著名的，开发了著名的LISP语语言言(LISt Processing language)，成为人工智能界第一，成为人工智能界第一个最广泛流行的语言。它和后来由英国伦敦大学的个最广泛流行的语言。它和后来由英国伦敦大学的青年学生青年学生 R. Kowaliski提出、由法国马赛大学的提出、由法国马赛大学的AColmerauer所领导的研究小组于所领导的研究小组于1973年首先实

49、现年首先实现的逻辑式语言的逻辑式语言PROLOG (PROgrammingin LOGic)并并称为人工智能的两大语言。称为人工智能的两大语言。67线性结构分类线性结构分类68广义表广义表(Generalized lists)广义表是线性表的一种推广。它被广泛的应用广义表是线性表的一种推广。它被广泛的应用于人工智能等领域的表处理语言于人工智能等领域的表处理语言LISP(LISt Processing，即表处理，即表处理)语言中。在语言中。在LISP语言语言中，广义表是一种最基本的数据结构，就连中，广义表是一种最基本的数据结构，就连LISP 语言的程序也表示为一系列的广义表。语言的程序也表示为一

50、系列的广义表。LISP语言是由语言是由John McCarthy在在1959年在年在MIT创造创造的一种基于的一种基于演算的函数式编程语言，最初的目的是演算的函数式编程语言，最初的目的是用于人工智能用于人工智能(Artificial Intelligence)和符号运算和符号运算(Symbolic Computation)。被誉为语言中的。被誉为语言中的“常青常青树树”的的LISP语言，主要现代版本包括语言，主要现代版本包括Common Lisp和和Scheme。 69广义表广义表(Generalized lists)例如，中国举办的某体育项目国际邀请赛，参例如，中国举办的某体育项目国际邀请赛

51、，参赛队清单可采用如下的表示形式：赛队清单可采用如下的表示形式：（俄罗斯，巴西，（国家，河北，四川），古（俄罗斯，巴西，（国家，河北，四川），古巴，美国，（），日本）巴，美国，（），日本）在这个拓宽了的线性表中，韩国队应排在美国在这个拓宽了的线性表中，韩国队应排在美国队的后面，但由于某种原因未参加，成为空表。队的后面，但由于某种原因未参加，成为空表。国家队、河北队、四川队均作为东道主的参赛国家队、河北队、四川队均作为东道主的参赛队参加，构成一个小的线性表，成为原线性表队参加，构成一个小的线性表，成为原线性表的一个数据项。这种拓宽了的线性表就是广义的一个数据项。这种拓宽了的线性表就是广义表。表。

52、70广义表广义表(Generalized lists)广义表是广义表是n个数据元素个数据元素(d1,d2,d3,dn)的有限序的有限序列，列，di既可以是单个元素，还可以是一个广义既可以是单个元素，还可以是一个广义表，因此广义表的定义是递归定义的。通常记表，因此广义表的定义是递归定义的。通常记作作: GL= (d1,d2,d3,dn) 。GL是广义表的名字，通常广义表的名字用大写字是广义表的名字，通常广义表的名字用大写字母表示。母表示。 n是是广义表的长度广义表的长度。d1是广义表是广义表GL的的表头表头，而广义表，而广义表GL其余部分组其余部分组成的表（成的表（d2，d3，dn）称为广义表的

53、）称为广义表的表尾表尾。 若其中若其中di是一个广义表，则称是一个广义表，则称di是广义表是广义表GL的子的子表表。71广义表广义表(Generalized lists)D=()空表；其长度为零。空表；其长度为零。A=(a,(b,c)表长度为表长度为2的广义表，其中第一个的广义表，其中第一个元素是单个数据元素是单个数据a，第二个元素是一个子表，第二个元素是一个子表(b,c)。head(A)=a，表，表A的表头是的表头是a。tail(A)=(b,c) ，表，表A的表尾是的表尾是(b，c) 。B=(A,A,D）长度为）长度为3的广义表，其前两个元素的广义表，其前两个元素为表为表A，第三个元素为空表

54、，第三个元素为空表D。C=(a,C)长度为长度为2递归定义的广义表，递归定义的广义表，C相当于相当于无穷表无穷表C=(a,(a,(a,()。72小小 结结广义表的定义是递归定义的。广义表的定义是递归定义的。广义表的元素可以是子表，而子表还可广义表的元素可以是子表，而子表还可以是子表以是子表，由此可见，广义表是一，由此可见，广义表是一个多层的结构。个多层的结构。 广义表可以被其它广义表共享。广义表可以被其它广义表共享。 广义表具有递归性。广义表具有递归性。 广义表的表尾一定是一个表。广义表的表尾一定是一个表。 73第五章第五章 数组和广义表数组和广义表数组的定义和运算数组的定义和运算数组的顺序存

55、储和实现数组的顺序存储和实现特殊矩阵的压缩存储特殊矩阵的压缩存储稀疏矩阵稀疏矩阵(Sparse Matrices)广义表广义表广义表的概念广义表的概念广义表的存储结构广义表的存储结构广义表的操作实现广义表的操作实现要点小结要点小结参考书目及网络资源参考书目及网络资源讨论时间讨论时间74广义表的头尾链表存储结构广义表的头尾链表存储结构由于广义表由于广义表GL= (d1,d2,d3,dn)中的数据元素中的数据元素既可以是单个元素，也可以是子表，因此广义既可以是单个元素，也可以是子表，因此广义表难以用顺序存储结构来表示它，通常用链式表难以用顺序存储结构来表示它，通常用链式存储结构来表示。存储结构来表

56、示。由于任何一个非空的广义表都可以将其分解成由于任何一个非空的广义表都可以将其分解成表头和表尾两部分，反之，一对确定的表头和表头和表尾两部分，反之，一对确定的表头和表尾可以唯一地确定一个广义表。广义表中有表尾可以唯一地确定一个广义表。广义表中有两类结点：两类结点：单个元素结点单个元素结点子表结点子表结点75广义表的头尾链表存储结构广义表的头尾链表存储结构一个一个表结点表结点可由三可由三个域构成：个域构成：标志域标志域指向表头的指针指向表头的指针域域指向表尾的指针指向表尾的指针域域一个一个元素结点元素结点(原原子结点子结点)可由两个可由两个域构成：域构成：标志域标志域值域值域tag=0atomt

57、ag=1hptp表结点表结点原子结点原子结点76广义表的头尾链表存储结构类型定义广义表的头尾链表存储结构类型定义typedef enumATOM, LISTElemTag; /*ATOM0,表示原子表示原子;LIST1,表示子表表示子表*/typedef struct GLNodeElemTag tag;/*tag用来区别原子结点和表结点用来区别原子结点和表结点*/*atom_htp是原子结点的值域是原子结点的值域atom和表结点的指针域和表结点的指针域htp的联合体域的联合体域*/ union AtomType atom; /*原子结点的值域原子结点的值域atom*/ struct stru

58、ct GLNode *hp, *tp;htp; /*表结点的表结点的指针域指针域htp,包括表头指针域包括表头指针域hp和表尾指针域和表尾指针域tp*/ atom_htp; GLNode, *GList；77广义表的头尾链表存储结构广义表的头尾链表存储结构0a1DA1110b0c1B111C10a78广义表的扩展线性链表存储结构广义表的扩展线性链表存储结构无论是单元素结点，还是子表结点均由三个域无论是单元素结点，还是子表结点均由三个域构成。构成。tag=1hptp表结点表结点原子结点原子结点tag=0atomtp79扩展线性链表存储结构类型定义扩展线性链表存储结构类型定义typedef enu

59、mATOM, LISTElemTag; /*ATOM0,表示原子表示原子;LIST1,表示子表表示子表*/typedef struct GLNodeElemTag tag;/*tag用来区别原子结点和表结点用来区别原子结点和表结点*/*atom_htp是原子结点的值域是原子结点的值域atom和表结点的头指针和表结点的头指针域域hp的联合体域的联合体域*/ union AtomType atom; /*原子结点的值域原子结点的值域atom*/ struct GLNode *hp; atom_htp; struct GLNode *tp; GLNode, *GList；800a0b10a广义表的扩

60、展线性链表存储结构广义表的扩展线性链表存储结构DA11B111C110c181第五章第五章 数组和广义表数组和广义表数组的定义和运算数组的定义和运算数组的顺序存储和实现数组的顺序存储和实现特殊矩阵的压缩存储特殊矩阵的压缩存储稀疏矩阵稀疏矩阵(Sparse Matrices)广义表广义表广义表的概念广义表的概念广义表的存储结构广义表的存储结构广义表的操作实现广义表的操作实现要点小结要点小结参考书目及网络资源参考书目及网络资源讨论时间讨论时间82广义表的操作实现广义表的操作实现下面以下面以广义表的头尾链表存储结构广义表的头尾链表存储结构为例，介绍为例，介绍几个基本操作。几个基本操作。Head():求广义表求广义表L的表头，并返回表头指针的表头，并返回表头指针Tail(): 求广义表求广义表