数据结构课程河南师范大学新联学院河南师范大学新联学院河南师范大学新联学院河南师范大学新联学院数据结构第五章第五章数组与广义表数组与广义表栋彤钻敢住凉辞乾脾哆砷缀舵溉块淮裤贺章咯绝聂寡羡肄曙吱掀端指褥刀数组和广义表数组和广义表本章内容5.1 数组的定义5.2 数组的顺序表示和实现5.3 矩阵的压缩存储5.4 广义表的定义5.5 广义表的存储结构潭遗怠洞搔笺韩策仲歧此菇择佬凯弥霞二善吗锰铬熄郸拷饥古春子录青邢数组和广义表数组和广义表新联学院数据结构5-3 通过本章学习，要求掌握如下内容：1多维数组的定义及在计算机中的存储表示；2对称矩阵、三角矩阵、对角矩阵等特殊矩阵在计算机中的压缩存储表示及地址计算公式；3稀疏矩阵的三元组表示及转置算法实现；4稀疏矩阵的十字链表表示及相加算法实现；5广义表存储结构表示及基本运算。重点难点擎扎乍罢村狠沽酿搪川烟角肤哀詹红摄激冻淳荤有赐避臂嵌奇诗老膝阐声数组和广义表数组和广义表新联学院数据结构5-4 数组是我们最熟悉的数据类型，在早期的高级语言中，数组是数组是我们最熟悉的数据类型，在早期的高级语言中，数组是唯一可供使用的数据类型。由于数组中各元素具有统一的类型，唯一可供使用的数据类型。由于数组中各元素具有统一的类型，并且数组元素的下标一般具有固定的上界和下界，并且数组元素的下标一般具有固定的上界和下界，因此，数组的因此，数组的处理比其它复杂的结构更为简单。处理比其它复杂的结构更为简单。多维数组是向量的推广。例如，多维数组是向量的推广。例如，二维数组：二维数组： 5.1 数组的定义Amn=a11 a12 a1na21 a22 a2n am1 am2 amn绿籽蔽恃鬼烯祁笺夷敖洽忽贝舌困嚎代陛挛日支租兆抛阀粪湛剿俯念隐潮数组和广义表数组和广义表新联学院数据结构5-5 5.1 数组的定义 数组可以看成是一种数组可以看成是一种特殊的线性表特殊的线性表，即线性表中数据，即线性表中数据元素本身也是一个线性表。元素本身也是一个线性表。 数组是数组是n（n0）个相同数据类型数据元素构成的）个相同数据类型数据元素构成的有限有限序列。序列。仆舟限古嗡揭毖炙圣寐又侩茸聊蛛塌组吠洒嫌鸯晕组菱单俄逆积潮暗蛤例数组和广义表数组和广义表新联学院数据结构( )( )( )( )( )( )( )( )( )二维数组同样满足数组的定义。二维数组可以看成一个特殊的二维数组同样满足数组的定义。二维数组可以看成一个特殊的一维数组，其中的每个元素又是一个一维数组一维数组，其中的每个元素又是一个一维数组。5.1 数组的定义闻糯轿焰葫浓属须舵棍审练懦渴灾见盔拓旱巨盖浦复汲镜餐上襟纸谁辞砚数组和广义表数组和广义表新联学院数据结构5-7 数组的特点：数组的特点：数组的特点：数组的特点： 数组中的数据元素数目固定数组中的数据元素数目固定数组中的数据元素数目固定数组中的数据元素数目固定( ( ( (结构固定结构固定结构固定结构固定) ) ) )； 数组中的数据元素具有相同的数据类型数组中的数据元素具有相同的数据类型数组中的数据元素具有相同的数据类型数组中的数据元素具有相同的数据类型( ( ( (元素同构元素同构元素同构元素同构) ) ) )； 数组中的每个数据元素都与一组数组中的每个数据元素都与一组数组中的每个数据元素都与一组数组中的每个数据元素都与一组唯一的下标值相对应唯一的下标值相对应唯一的下标值相对应唯一的下标值相对应； 数组是一种数组是一种数组是一种数组是一种随机存取结构随机存取结构随机存取结构随机存取结构。5.1 数组的定义芍随抖涅孔痰津熬颖翅酿锦丘甥哦旗邱辙呢杯态偿犀屁幻瑚疆逢轨犊窃喇数组和广义表数组和广义表新联学院数据结构5.1 数组的抽象数据类型ADT5-8 宾赏漳屑碟茁图此徽吮踪律石楞龄暖铁膀猫钓汽夏鹅冰算堡叶镀恋嘘知疑数组和广义表数组和广义表新联学院数据结构一维数组存储结构示意图存储地址存储地址 内存空间状态内存空间状态 逻辑地址逻辑地址 Loc(a1) a11 Loc(a1)+(2-1)L a2 2 loc(a1)+(i-1)Lai i loc(a1)+(n-1)L an n 地址映像的计算公式：地址映像的计算公式：假设线性表中假设线性表中每个元素占每个元素占L L个单元个单元，第一个元素的地址为第一个元素的地址为loc(loc(a1) )，则第，则第i i个元素的地址为：个元素的地址为： loc(ai) =loc(a1)+(i-1)L 李熟还执篱取药厚赐颁讼幌馅拦幻炙戳至捣噬晚瑟劝怕柱饰钞枉疟斑雁栅数组和广义表数组和广义表新联学院数据结构5.2 数组的顺序表示和实现p问问 题：计算机的存储结构是一维的，而数组一般是多维的，怎样存题：计算机的存储结构是一维的，而数组一般是多维的，怎样存放？放？p解决办法：事先约定按某种次序将数组元素排成一列序列，然后将这解决办法：事先约定按某种次序将数组元素排成一列序列，然后将这个线性序列存入存储器中。个线性序列存入存储器中。p注意：注意：用一组连续的存储单元来表示数组；用一组连续的存储单元来表示数组；若规定好了次序，则数组中任意一个元素的存放地址便有若规定好了次序，则数组中任意一个元素的存放地址便有规律可寻，可形成地址计算公式；规律可寻，可形成地址计算公式；约定的次序不同，则计算元素地址的公式也有所不同；约定的次序不同，则计算元素地址的公式也有所不同；C C和和PASCALPASCAL中一般采用中一般采用行优先行优先顺序；顺序；FORTRANFORTRAN采用采用列优先列优先5-10 邪匝戴挑胸烛也于钵祭掏菌钎悬羹扦淤凰氦工龟饰扼擦磺情控嚼销鸳存薯数组和广义表数组和广义表新联学院数据结构5-11 5.2 数组的顺序表示和实现p设一设一3 3维数组维数组A423A423，存贮，存贮在一个顺序线性表在一个顺序线性表S S中，结构如中，结构如下所示：下所示：A312A311A310A302A301A300A212A211A210A202A201A200A112A111A110A102A101A100A012A011A010A002A001A000A312A311A310A302A301A300A212A211A210A202A201A200A112A111A110A102A101A100A012A011A010A002A001A00001234567.2223A000A001A002A010A011A012A100A101.A311A312傍赘陨荆押带恤箱资遂款杉胡示窗障瘩梅与硫仓斋闷捧恫曹豺啦会柞膝脏数组和广义表数组和广义表新联学院数据结构5.2 数组的顺序表示和实现p 以行为主以行为主:对二维数组进行对二维数组进行“按行切分按行切分”，即将数组中，即将数组中的数据元素的数据元素“按行依次排放按行依次排放”在存储器中；在存储器中；p 以列为主：以列为主：对二维数组进行对二维数组进行“按列切分按列切分”，即将数组中，即将数组中的数据元素的数据元素“按列依次排放按列依次排放”在存储器中。在存储器中。5-12 节漾涝汛鳖惋右畜犁跌臣炼良沾衔场使误谱蜜掘榷醋昏蝇牛狱钎敦墨芹烙数组和广义表数组和广义表新联学院数据结构 按行序为主序存放LOC(i,j)=LOC(0,0)+(i*n+j)*L玩钝硒硷阂频舜瘩妆洁枝脆隋厅材扮搂媚类苞秀蚊烂钧幂辞诲青上证咐误数组和广义表数组和广义表新联学院数据结构 按列序为主序存放LOC(i,j)=LOC(0,0)+(j*m+i)*L捻乌体驴访腋绘壕剧萌黑骆妙亡厅臀蒸邑孺圭缝棍依旷馆释蚜弱劲掉籽堑数组和广义表数组和广义表新联学院数据结构例题 无无论论规规定定行行优优先先或或列列优优先先，只只要要知知道道以以下下三三要要素素便便可可随随时时求求出出任任一元素的地址：一元素的地址：开始结点的存放地址（即基地址）开始结点的存放地址（即基地址）维数和每维的上、下界；维数和每维的上、下界；每个数组元素所占用的单元数每个数组元素所占用的单元数5-15 赡记亦僳逆顾恳耶溜栓己韶蝴官嚷无涪晃秉痹榨肢窗娘谍怜已悦武钓俩爱数组和广义表数组和广义表新联学院数据结构例题【例【例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)+(i*n+j)*L)*L = =1000+(2*4+3)*41000+(2*4+3)*4 = =104410445-16 自耗古赐协倒佳毛疗论再厢戴途熏瘩表涤援氰饮句哭捕耿娄膳鼓险嚎薯舍数组和广义表数组和广义表新联学院数据结构例题p【例【例5-25-2】一个二维数组一个二维数组A，行下标的范围是，行下标的范围是1到到6，列下标的范围是，列下标的范围是0到到7，每个数组元素用相邻的，每个数组元素用相邻的6个字节存储，存储器按字节编址。个字节存储，存储器按字节编址。那么，这个数组的体积是那么，这个数组的体积是 个字节。个字节。 【解】【解】 Volume=m*n*L=(6-1+1)*(7- 0 +1)*6=48*6=288p【例【例5 5-3-3】 设数组设数组a160, 170的基地址为的基地址为2048，每个元素占，每个元素占2个存储单元，若以列序为主序顺序存储，则元素个存储单元，若以列序为主序顺序存储，则元素a32,58的存储地的存储地址为址为 。5-17 根据列优先公式根据列优先公式 Loc(aij)=Loc(a11)+(j-1)*m+(i-1)*L得：得：LOC(a32,58)=2048+(58-1)*60+(32-1)*28950想一想：若数组是想一想：若数组是a059, 069，结果是否仍为结果是否仍为8950？被刮岿妇锈晰酣妓倚差圣篙晴瘟液处竭霜雷呀携葫苫点诡炉晚炳藏攒否劣数组和广义表数组和广义表新联学院数据结构5-18 5.3 矩阵的压缩存储p在高级语言编制程序时，将一个矩阵描述为一个二维数组。在高级语言编制程序时，将一个矩阵描述为一个二维数组。p矩阵在这种存储表示之下，可以对其元素进行随机存取，各种矩阵矩阵在这种存储表示之下，可以对其元素进行随机存取，各种矩阵运算也非常简单，并且存储的密度为运算也非常简单，并且存储的密度为1 1。但是在矩阵中非零元素呈。但是在矩阵中非零元素呈某种规律分布或者矩阵中出现大量的零元素的情况下，看起来存储某种规律分布或者矩阵中出现大量的零元素的情况下，看起来存储密度仍为密度仍为1 1，但实际上占用了许多单元去存储重复的非零元素或零，但实际上占用了许多单元去存储重复的非零元素或零元素，这对高阶矩阵会造成极大的浪费元素，这对高阶矩阵会造成极大的浪费. .倾蓉康被书靶匣熬搔长宣佳舍憋舜贷啼谨视激喜名杏逢曝艾纹蛙揩帚烦忍数组和广义表数组和广义表新联学院数据结构5.3 矩阵的压缩存储5-19 p 压缩存储压缩存储压缩存储压缩存储 为多个值相同的矩阵只分配一个存储空间；为多个值相同的矩阵只分配一个存储空间；为多个值相同的矩阵只分配一个存储空间；为多个值相同的矩阵只分配一个存储空间； 对零元不分配空间。对零元不分配空间。对零元不分配空间。对零元不分配空间。圣熄诈施艇观侣酞酶憨服附奏旁琴奄牵艰瞳彝征酷东叮框给昭哼盐车偏漠数组和广义表数组和广义表新联学院数据结构5-20 5.3 矩阵的压缩存储5.3.1 特殊矩阵特殊矩阵值相同的元素或者值相同的元素或者0 0元素在矩阵中的元素在矩阵中的分布有一定规律分布有一定规律。篙笔产灸侩逗妊厄判典亏失屋怨败灶蓝卵充兹念怒君崩蕉师朱徒贮饲暴鹃数组和广义表数组和广义表新联学院数据结构5-21 5.3 矩阵的压缩存储p对称矩阵对称矩阵 仅存储仅存储下三角下三角涌遗避项赔钢坑岁亲针竹亿帽奴敝狼麻氦催烩琉暮遣陨乎刑吨孝鹿域赤消数组和广义表数组和广义表新联学院数据结构 下三角矩阵下三角矩阵5.3 矩阵的压缩存储浑弛贿树环精截敖公旬往辊址岂紊辱仓诅尘第辊辐搞唆官赛演噶懦圣踌娥数组和广义表数组和广义表新联学院数据结构5.3 矩阵的压缩存储 对角矩阵对角矩阵韶遍鹊根侄择尉烁漆缺熊杖聚刽瑟纳土价述海酷百吐嵌那们俘薄售例卓惑数组和广义表数组和广义表新联学院数据结构5-24 5.3 矩阵的压缩存储5.3.2 稀疏矩阵稀疏矩阵p定义：设矩阵定义：设矩阵A A中有中有t t个非零元素，若个非零元素，若s s远远小于矩阵元素的总数远远小于矩阵元素的总数（即（即smsmn n），则称），则称A A为为稀疏矩阵稀疏矩阵。设在的矩阵设在的矩阵A A中，有中，有t t个非零元素。令个非零元素。令 e=t/(m*n) e=t/(m*n)，称，称e e为矩阵为矩阵的的稀疏因子稀疏因子。通常认为。通常认为e0.05e0.05时称之为时称之为稀疏矩阵稀疏矩阵。以常规方法，即以二维数组表示的高阶的稀疏矩阵时产生的问题：以常规方法，即以二维数组表示的高阶的稀疏矩阵时产生的问题：1.1.零值元素占的空间很大；零值元素占的空间很大；2.2.计算中进行了很多和零值的运算；计算中进行了很多和零值的运算；掏辞哀禽雷犀瓤塔雹糠全圭冀证没堡凯庸共甘疡鬃扶坷丈蛀芝黑姑翠丛董数组和广义表数组和广义表新联学院数据结构5.3 矩阵的压缩存储p解决问题的原则解决问题的原则1. 尽量少存或不存尽量少存或不存0 0元；元；2. 2. 尽量减少没有意义的运算；尽量减少没有意义的运算；3. 3. 运算要方便。运算要方便。 能尽可能快地找到与下标值（能尽可能快地找到与下标值（i i，j j）对应的运算；）对应的运算； 能尽可能快地找到同一行或同一列的非能尽可能快地找到同一行或同一列的非0 0值元。值元。压缩存储方法：压缩存储方法：三元组顺序表三元组顺序表、行逻辑连接行逻辑连接和和十字链表十字链表。5-25 盆拖寥宛哮犁篡破攒处绩沉一斌蚕交舔采肤有双叮梢泌秀贤俩兴伺莎框谓数组和广义表数组和广义表新联学院数据结构 存储特点存储特点2. 三元组顺序表 对于矩阵中每个非对于矩阵中每个非0元素，用它的元素，用它的行号、列号、元素行号、列号、元素值值，即（，即（i, j, aij）表示。）表示。 将表示稀疏矩阵的所有非将表示稀疏矩阵的所有非0元素的三元组按行优先顺元素的三元组按行优先顺序排列，则可得到序排列，则可得到一个其结点均是三元组的线性表一个其结点均是三元组的线性表，称为三元组表。称为三元组表。 以以顺序存储结构顺序存储结构来表示三元组。来表示三元组。 要唯一确定一个稀疏矩阵，还必须要唯一确定一个稀疏矩阵，还必须存储该矩阵的行存储该矩阵的行数和列数数和列数。黔狈努袱拓镜豫丝先裁蓑掩槽侮规搭津裂霉册瞄婉特跑司军锨蠕簧辐臼晓数组和广义表数组和广义表新联学院数据结构5-27 p三元组法存储三元组法存储0 12 9 0 0 00 0 0 0 0 0 -3 0 0 0 14 00 0 24 0 0 00 18 0 0 0 015 0 0 -7 0 0（( 1,2,12)( 1,2,12) ，(1,3,9)(1,3,9)， (3,1,-3) (3,1,-3)， (3,5,14) (3,5,14)， (4,3,24) (4,3,24)， (5,2,18) (5,2,18) ，(6,1,15)(6,1,15)， (6,4,-7) (6,4,-7)6行行6列，列，8个非零元个非零元2. 三元组顺序表略鹰缺岩九峪谍油铂躇井兵轰弗抄讥足堪滔把吗惹胚蔷陪曳金瓤您萧蛛恋数组和广义表数组和广义表新联学院数据结构p三元组法存储三元组法存储5-28 8552635531143742551221datacolrow0 2 0 0 5 00 0 0 7 0 00 0 0 11 5 20 0 0 0 0 00 0 0 0 8 0 2. 三元组顺序表诧张蠕巫匙乱袍抠吊拿花坍触设汰凄颗解坛添只佃京硝票桅户正挫涸猖饮数组和广义表数组和广义表新联学院数据结构 数据类型定义# define MAXSIZE 12500 三元组结点三元组结点：typedef struct int i, j; /行号，列号行号，列号 ElemType e; Triple;稀疏矩阵：稀疏矩阵：typedef struct Triple dataMAXSIZE+1 ; int mu, nu, tu; /*行、列、非零元素个数行、列、非零元素个数*/ TSMatrix ;2. 三元组顺序表彪诞衡御封俐争危虹冈鞠揽撩砌园旺辣妥洲神活易戍膊备豢暇怯快琐袋阿数组和广义表数组和广义表新联学院数据结构5-30 p例子：三元组法表示的矩阵转置例子：三元组法表示的矩阵转置M T0 2 0 0 5 00 0 0 7 0 00 0 0 11 5 20 0 0 0 0 00 0 0 0 8 0 0 0 0 0 02 0 0 0 00 0 0 0 00 7 11 0 050 5 0 80 0 2 0 0 已知一个稀疏矩阵的三元组表，求该矩阵转置矩阵的三元组表。常规算法：常规算法：for(col=1;col=nu;col+) for(row=1;row=mu;row+) Tcolrow=Mrowcol;时间复杂度：时间复杂度：O(munu)2. 三元组顺序表仗歧覆糙戳褂阮市寂亦尤东遣钒皱涂旭沙窘竹丰甘拨灾党清沉狄惶叮尊赡数组和广义表数组和广义表新联学院数据结构5-31 解决思路：解决思路： 将矩阵行、列维数互换；将矩阵行、列维数互换； 将每个三元组中的将每个三元组中的i i和和j j相互调换；相互调换； 重排三元组次序；重排三元组次序；2. 三元组顺序表洒丸吠怠愧贸镐惨痕辫叠固酞遇碟壹憋旬集哭藏姬寅阶擂蚊音观撕波谴彝数组和广义表数组和广义表新联学院数据结构5-32 M.data12315-522-131634841-44570 3 0 0 -50 -1 0 0 06 0 0 8 0-4 0 0 0 7M0 0 6 -43 -1 0 00 0 0 00 0 8 0 -5 0 0 7TT.data2 1 35 1 -52 2 -11 3 64 3 81 4 -45 4 72 1 35 1 -52 2 -15 1 -52. 三元组顺序表冻睹遇帆鼓擞睡辱暇奈废怜谴楼醇绸田赃消讼螺次枫找始脊膛秽微厢庐苞数组和广义表数组和广义表新联学院数据结构5-33 M.data12315-522-131634841-44570 3 0 0 -50 -1 0 0 06 0 0 8 0-4 0 0 0 7M0 0 6 -43 -1 0 00 0 0 00 0 8 0 -5 0 0 7TT.data2 1 35 1 -52 2 -11 3 64 3 81 4 -45 4 72. 三元组顺序表拣旭郭钻散痹均拄击宽组道欧娱服苯砂防缨讳嘉赦惧碱濒酪尾治宋肌泊绍数组和广义表数组和广义表新联学院数据结构5-34 M.data12315-522-131634841-4457T.data2 1 35 1 -52 2 -11 3 64 3 81 4 -45 4 7Col12345NumcPot00000+1+1+1+1+1+1+12. 三元组顺序表皱源污按蛇难匪组乍袒切潘糕善魏湿瑶疼歇踩映营耸挤南昌寐碧诽爪字撩数组和广义表数组和广义表新联学院数据结构5-35 M.data12315-522-131634841-4457T.data2 1 35 1 -52 2 -11 3 64 3 81 4 -45 4 7Col12345Num22012cPot123455672. 三元组顺序表啄什吐纂谆颗仁伍科雍羔任展谅础粱脱椿维漠梅妆洲宴说首瘫督喜雇蛰威数组和广义表数组和广义表新联学院数据结构5-36 2. 三元组顺序表耀色嘉赘隅消耸偶拎属津浦巾淖婴格宁拣板链钙他来壤戍备逐漱脓窝灼狂数组和广义表数组和广义表新联学院数据结构 优点：优点： 非零元在表中按行序有序存储，便于进行非零元在表中按行序有序存储，便于进行依行依行序处理的矩阵运算序处理的矩阵运算。 缺点：缺点： 若需按行号存取某一行的非零元，则需从头开若需按行号存取某一行的非零元，则需从头开始查找。始查找。2. 三元组顺序表坯骡脆烩固束汾懂副赠做舆娇践主胳邦廖析庚柿靶蜂绪咱检乃抑标倦纠涂数组和广义表数组和广义表新联学院数据结构 为了便于随机存储任意一行的非零元，需要知为了便于随机存储任意一行的非零元，需要知道每一行的第一个非零元在三元组表中的位置。道每一行的第一个非零元在三元组表中的位置。3.行逻辑连接的顺序表# define MAXSIZE 12500 三元组结点三元组结点：typedef struct int i, j; ElemType e; Triple;稀疏矩阵：稀疏矩阵：typedef struct Triple dataMAXSIZE+1 ; int rposMAXRC+1; /*各行第一个非零元的位置表各行第一个非零元的位置表 int mu, nu, tu; /*行、列、非零元素个数行、列、非零元素个数*/ TSMatrix ;柜月丰拷著恨帜蜜呐绷热贾竹聋魄壤揉嚎兴偷埂阎反揉诲稽荒填屏坷谷驼数组和广义表数组和广义表新联学院数据结构5-39 3.行逻辑连接的顺序表p带行向量的三元组法的矩阵乘法带行向量的三元组法的矩阵乘法鉴奔窗效薯蹿清跨硅薯递狈质嗡财猪汉焊肪骗源嘉邯诡州澄硒肋与歼棵肮数组和广义表数组和广义表新联学院数据结构5-40 3.行逻辑连接的顺序表0 2 0 0 30 -1 5 0 04 0 0 7 60 0 -3 0 0M(4,5)0 32 41 00 0 0 -2 N(5,2)=4 23 -40 0-3 0 Q(4,2)M.data12215322-123531434735643-3N.data12321222431152-2呀揪庐区酚曾秸竹跟闷嘉部屹灸遵驮乏甥西绢帛坏跋娇刑潦于章梗买铣占数组和广义表数组和广义表新联学院数据结构 问题描述：问题描述：已知两个稀疏矩阵已知两个稀疏矩阵M和和N的三元组表，求两个矩阵的三元组表，求两个矩阵相乘的结果矩阵相乘的结果矩阵Q。常规算法：常规算法：for(i=1;i=m1;i+) for(j=1;j=n2;j+) Qij=0; for(k=1;k=n1;k+) Qij += Mik* Nkj;1 1、只对、只对M M和和N N的非零元进行计算；的非零元进行计算；2 2、M M中列号与中列号与N N中行号相等的非零元相乘即可；中行号相等的非零元相乘即可；3 3、Q Q与与M M的行号对齐的，且的行号对齐的，且QijQij是累加的结果。是累加的结果。3.行逻辑连接的顺序表厦秃浴醇沁桨葛济氦埔陆手椿湾孪斌羹赁艇理景业魂镀泰晴汕盐瘫弟慌些数组和广义表数组和广义表新联学院数据结构3.行逻辑连接的顺序表Q初始化；初始化；if （Q是非零矩阵）是非零矩阵） for(arrow=1;arrow=M.mu;arrow+) ctemp=0; 计算计算Q中第中第arrow行的积并存入行的积并存入ctemp中；中； 将将ctemp中非零元压缩存储到中非零元压缩存储到Q.data； 5-42 忍沾垒瘸涉芳了涣悼懊约轨儿终蚤披借穷样拽缕歹褂备屿您克房府蔡甩获数组和广义表数组和广义表新联学院数据结构处理M的每一行复轴姨牟进有防勤糟诗鹤囚坪柔右咳垂刷锹郎豢仁漆掉剖讫堪芹颧醋翌豁数组和广义表数组和广义表新联学院数据结构分析上述算法的时间复杂度分析上述算法的时间复杂度例子例子: :求矩阵乘法求矩阵乘法1、累加器、累加器ctemp初始化初始化的时间复杂度为的时间复杂度为O(M.muN.nu)2、求、求Q的所有非零元的所有非零元的时间复杂度为的时间复杂度为O(M.tuN.tu/N.mu)3、进行、进行压缩存储压缩存储的时间复杂度为的时间复杂度为O(M.muN.nu)总的时间复杂度总的时间复杂度O(M.muN.nu+M.tuN.tu/N.mu)若若M M是是m m行行n n列的稀疏矩阵，列的稀疏矩阵，N N是是n n行行p p列的稀疏矩阵，则：列的稀疏矩阵，则： M中非零元的个数：中非零元的个数：M.tu=M mn N中非零元的个数：中非零元的个数： M.tu=N np 相乘算法的时间复杂度就是相乘算法的时间复杂度就是O(mn(1+nMN)，当：，当： M 0.05和和N 1000时，时，算法的时间复杂度相当于算法的时间复杂度相当于O(mp)。盼况烧痹挤轩之紧翠此制冰失垦鬼仆膘缨环埂馈水巨释投颅孙旬率棺堆嘉数组和广义表数组和广义表新联学院数据结构 引入原因引入原因4.4. 十字链表十字链表十字链表十字链表 当矩阵的非零元的个数发生变化时，不宜采用三元组当矩阵的非零元的个数发生变化时，不宜采用三元组表。如表。如A=A+B，非零元的插入或删除将会引起，非零元的插入或删除将会引起A.data中的数据移动，这是顺序结构三元组的弱势。中的数据移动，这是顺序结构三元组的弱势。 数据类型定义数据类型定义结点结点：typedef struct OLNode int i, j; ElemType e; struct OLNode *right， *down；/*该非零元所在行的后继链域该非零元所在行的后继链域*/ OLNode; *OLink；稀疏矩阵：稀疏矩阵：typedef struct OLink *rhead，*chead； int mu，nu，tu； Crosslist;ijkdownright柿园汗囚毛秉腆洽厉希旧喜昼瑞综阴坛谩拖肝芍首序磷叶抖突炊棋沸涉灶数组和广义表数组和广义表新联学院数据结构5-46 4. 十字链表p十字链表结点定义：每一个非零元用一个结点表示，结点包括五个十字链表结点定义：每一个非零元用一个结点表示，结点包括五个域：除了表示非零元所在的行、列和值的三元组域：除了表示非零元所在的行、列和值的三元组（i, j, v）外，还需外，还需增加两个链域：行指针域（增加两个链域：行指针域（rightright），用来指向本行中下一个非零），用来指向本行中下一个非零元素；列指针域（元素；列指针域（downdown），用来指向本列中下一个非零元素。），用来指向本列中下一个非零元素。ijrightdownv寒阂孔击碳侩铣开讥卒蜜度哺痢讳阳曙歼弱泛崭攀涌聊姜坟彤杰逐庐祷三数组和广义表数组和广义表新联学院数据结构5-47 4. 十字链表p十字链表法：十字链表法：为稀疏矩阵中的链接存储中的一种较好的存储方法为稀疏矩阵中的链接存储中的一种较好的存储方法稀疏稀疏矩阵矩阵及其及其十字交叉链表十字交叉链表0 12 0 0 00 0 0 0 -40 5 0 0 00 0 3 0 0A=(a) 稀疏稀疏矩阵矩阵(b(b) 稀疏稀疏矩阵的十字交叉链表矩阵的十字交叉链表A.cheadA.rchead 1 2 12 3 2 5 2 5 -4 4 3 3 滦爹义萌义蟹充沛效食鸥狄尼绥陇颠稍酌感嫩乳廷僵鸥笺涧热脸举帘辨诸数组和广义表数组和广义表新联学院数据结构5-48 4. 十字链表p十字链表类型定义十字链表类型定义稀疏矩阵中同一行的非零元通过向右的稀疏矩阵中同一行的非零元通过向右的rightright指针链接成一个指针链接成一个带表头结点的线性链表。同一列的非零元也通过带表头结点的线性链表。同一列的非零元也通过downdown指针链接成一指针链接成一个带表头结点的线性链表。个带表头结点的线性链表。 因此，每个非零元既是第因此，每个非零元既是第i i行循环链表中的一个结点，又是第行循环链表中的一个结点，又是第j j列循环链表中的一个结点，相当于处在一个十字交叉路口，故称链列循环链表中的一个结点，相当于处在一个十字交叉路口，故称链表为十字链表。表为十字链表。可用两个分别存储行链表的头指针和列链表的头指可用两个分别存储行链表的头指针和列链表的头指针的一维数组表示之。针的一维数组表示之。犬仍彤沤皮情沫盖瞪伶胎驳措壁部球絮啦摸谋钉淖燕实浚辟级嫡撑六带苟数组和广义表数组和广义表新联学院数据结构5-49 是线性表的推广是线性表的推广是线性表的推广是线性表的推广，广泛的应用于人工智能等领域。，广泛的应用于人工智能等领域。，广泛的应用于人工智能等领域。，广泛的应用于人工智能等领域。 一般记作一般记作一般记作一般记作LS=LS=LS=LS=（1 1 1 1， 2 2 2 2，, , , , n n n n）(n0)(n0)(n0)(n0)其中其中其中其中i i i i既既既既可以为单个元素也可以为广义表。可以为单个元素也可以为广义表。可以为单个元素也可以为广义表。可以为单个元素也可以为广义表。 名称名称名称名称：LSLSLSLS； 长度长度长度长度：n n n n； 原子原子原子原子： i i i i是单个元素；是单个元素；是单个元素；是单个元素； 子表子表子表子表： i i i i是广义表；是广义表；是广义表；是广义表； 表头表头表头表头(Head)(Head)(Head)(Head)：非空广义表：非空广义表：非空广义表：非空广义表LSLSLSLS的第一个数据元素的第一个数据元素的第一个数据元素的第一个数据元素 1 1 1 1； 表尾表尾表尾表尾(Tail)(Tail)(Tail)(Tail)：非空广义表除第一个数据元素外的其余数据元素：非空广义表除第一个数据元素外的其余数据元素：非空广义表除第一个数据元素外的其余数据元素：非空广义表除第一个数据元素外的其余数据元素构成的广义表构成的广义表构成的广义表构成的广义表( ( 2 2，, , n n）5.4 广义表洛舟廷援院七磐可错袱积谱勿唱谱卜匣穿胎媚呆摔侍摆住屑檀胀杜殷疹抢数组和广义表数组和广义表新联学院数据结构5-50 5.4 广义表p任意一个非空广义表，均可分解为表头和表尾。任意一个非空广义表，均可分解为表头和表尾。p对于一个非空广义表，其表头可能是对于一个非空广义表，其表头可能是原子原子，也可能是，也可能是子表子表；而表尾；而表尾一定是一定是子表子表。pp广义表举例广义表举例广义表举例广义表举例1.A=（）（） / 空表，长度空表，长度n = 02.B=（e） / n=1, 只有一个原子只有一个原子e3.C=（a, (b, c, d) ) / n=2, 有两个元素，分别为原子有两个元素，分别为原子a和子和子表表(b,c,d)4.D=（A，B，C） / n=3,有有3个元素个元素nE= (a , E） / n=2,无限循环列表（递归）无限循环列表（递归）咐夜炯抬斤涨灰跃盐丛伍呢捷站汾粱宦芽氰恒荤煮灰奋略彼踏粕泻凿厩渝数组和广义表数组和广义表新联学院数据结构5-51 5.4 广义表p性质性质n n广义表是一个广义表是一个广义表是一个广义表是一个多层次多层次多层次多层次结构结构结构结构; ;n n广义表的深度广义表的深度广义表的深度广义表的深度 d d 定义为所含括弧的重数（定义为所含括弧的重数（定义为所含括弧的重数（定义为所含括弧的重数（展开后所含展开后所含括号括号括号括号的的层层层层数数数数）; ;l l “ “原子原子原子原子” ”的深度为的深度为的深度为的深度为0 0 ; ;l l “ “空表空表空表空表” ”的深度为的深度为的深度为的深度为1 1n n 广义表可以广义表可以广义表可以广义表可以共享共享共享共享; ;也可以是一个也可以是一个也可以是一个也可以是一个递归递归递归递归的表的表的表的表; ;广广 义义 表表表长表长n表深表深hA=()00B=(e)11C=(a,(b,c,d)22D=(A,B,C)33E=(a,E)2F=()12abecdABCD枯殆藤台蛊骸休碱录肄掐乒掀木延襟臃密婪镇邀缚沃劝蜘骇贫镀绸督称贯数组和广义表数组和广义表新联学院数据结构 广广义义表表有有两两个个重重要要的的基基本本操操作作，即即取取头头操操作作（Head）和和取取尾尾操操作作（Tail）。）。 根根据据广广义义表表的的表表头头、表表尾尾的的定定义义可可知知，对对于于任任意意一一个个非非空空的的列列表表，其其表头可能是单元素也可能是列表，而表尾必为列表。例如：表头可能是单元素也可能是列表，而表尾必为列表。例如：1.B=（e） Head（B） e Tail（B）（）（） 2.C=（a, (b, c, d) ) Head（C） a Tail（C）（）（b，c，d） 3.D=（A，B，C） Head（D） A Tail（D）（）（B，C） 4.E= (a , E）Head（E） a Tail（E）（）（E） 5.F=() Head（F）（）（） Tail（F）（）（） 6.LS= ( (a, b), (a, b), (u, (x, y, z), ( ) ) )，求，求LS的深度的深度5.4 广义表才抵多蓝君匈畏么下剧还嫁畅圃曹仙陀号隶坠耍讨勒瑞菌佩蔽离参猫打跺数组和广义表数组和广义表新联学院数据结构5-53 5.5 广义表的存储结构pp 广义表的表示有两种结构形式广义表的表示有两种结构形式广义表的表示有两种结构形式广义表的表示有两种结构形式 表结点表结点表结点表结点 原子结点原子结点原子结点原子结点 第一种结构形式第一种结构形式第一种结构形式第一种结构形式1LS表头表头表尾表尾LS = NULL 钙曳知五鲸哺盆寡落帆偿糠低贱坯俄隐尽四液缝钧蜡菇过惹衰莎败聪项飞数组和广义表数组和广义表新联学院数据结构5-54 5.5 广义表的存储结构愿空糠穴仰占巳腰耿讨肩殿镜爪好寐腮卑吾轧队脐纯仑协鸿蹿当凑繁归型数组和广义表数组和广义表新联学院数据结构5-55 5.5 广义表的存储结构typedef enumatom,listelemtag;typedef struct GLnode Elemtag tag; unionunion AtomType atom; struct GLnode *hp; /表结点的表头指针 ; struct GLnode *tp; / 指向下一个元素结点 *GListGList;乐舒窟赣翠篱仿踏推涵存孩序钡面湍泰驹舒府斟逝仿族询琉泥距嫁昭三甭数组和广义表数组和广义表新联学院数据结构5-56 5.5 广义表的存储结构p广义表的运算广义表的运算n创建空的广义表创建空的广义表: initGList(&L);n销毁广义表销毁广义表: destroyGList(&L);n复制广义表复制广义表: copyGList(&T, L);n求广义表的长度求广义表的长度: length(L);n求广义表的深度求广义表的深度: depth(L);n求广义表的表头求广义表的表头: getHead(L);n求广义表的表尾求广义表的表尾: getTail(L);n插入一个元素使其成为新的表头插入一个元素使其成为新的表头: insertFirst(&L, e);n删除表头元素删除表头元素: deleteFirst(&L, &e);n判断表是否空判断表是否空: isEmpty(L);证勃庄俊帆该瞅兴雍玖荐窑题哈嗅涅思蜡剪相紊汕谩鞘淹闪肉钵盯考漳沸数组和广义表数组和广义表新联学院数据结构5-57 5.5 广义表的存储结构p广义表作为广义表作为ADTADT Glist 数据对象数据对象: D=ei |i=1,2, n; n 0, ei AtomSet 或或ei Glist 数据关系数据关系: R=(ei-1 , ei ) | ei D 基本操作基本操作: initGList(&L); 操作结果操作结果: 创建空表创建空表; destroyGList(&L); 初始条件初始条件: 广义表广义表L已存在已存在 操作结果操作结果: 销毁广义表销毁广义表 . /Glist;枪穗逻二免企核沏搓独舶浸沽缀梦推弓械检装架吟幢袖拎矾蛤辽蔗奴黍芒数组和广义表数组和广义表新联学院数据结构5-58 5.5 广义表的存储结构p求广义表的深度求广义表的深度设：设：LS = (a1, a2, , an)，例如，对于广义表例如，对于广义表 E ( B (a, b), D ( B (a, b), C (u, (x, y, z), A ( ) ) )按递归算法分析：按递归算法分析： Depth (E) = 1+Max Depth (B), Depth (D) Depth (B) = 1+Max Depth (a), Depth (b) = 1 Depth (D) = 1+Max Depth (B), Depth (C), Depth (A)直涩闪拷淆叭记咬藕杨蛔睹伺卉后乃碉柱裴倡霍径眩囱形破编棠盎粮茶宾数组和广义表数组和广义表新联学院数据结构5-59 5.5 广义表的存储结构Depth (C) = 1+Max Depth (u), Depth (x, y, z) Depth (A) = 1Depth (u) = 0Depth (x, y, z) = 1+Max Depth (x), Depth (y), Depth (z) = 1 Depth (C) = 1+Max Depth (u), Depth (x, y, z) = 1+Max 0, 1 = 2 Depth (D) = 1+Max Depth (B), Depth (C),Depth (A) = 1+Max 1, 2, 1 = 3Depth (E) = 1+Max Depth (B), Depth (D) = 1+Max 1, 3 = 4弥煌馒篷峰牌郭倪洪虚吉捞醋崭猴惨咽秃洼搀浙讣悼郸伍坠蘸桥讹倔谆嚷数组和广义表数组和广义表新联学院数据结构5-60 5.5 广义表的存储结构Int depth ( GList *ls ) /广义表广义表ls 用扩展的线性链表存储，函数返回用扩展的线性链表存储，函数返回ls的深度的深度 if ( ls = NULL ) return 1; /空表空表 GList *temp = ls; int m = 0; /m 表示当前层元素的最大深度表示当前层元素的最大深度 while ( temp != NULL ) /横扫广义表的每个元素横扫广义表的每个元素 if ( temptag = LIST ) /子表深度子表深度 int n = depth ( temphp ); if ( nm ) m = n; /不是子表不加深度不是子表不加深度 temp = temptp; /temp指向下一个元素指向下一个元素 return m+1;耍齐犯哲贴掩蝇诫留梦谊亲崖歹槐愚绸全温倚蚜掐笼膜闹陋协孽咙诊担接数组和广义表数组和广义表新联学院数据结构本章小结数组数组数组数组uu数组的定义和特点数组的定义和特点数组的定义和特点数组的定义和特点uu数组的顺序存储（行优先，列优先）数组的顺序存储（行优先，列优先）数组的顺序存储（行优先，列优先）数组的顺序存储（行优先，列优先）uu逻辑地址逻辑地址逻辑地址逻辑地址 物理地址的计算物理地址的计算物理地址的计算物理地址的计算；矩阵的压缩存储矩阵的压缩存储矩阵的压缩存储矩阵的压缩存储uu对称矩阵、上三角或下三角等特殊矩阵压缩存储时对称矩阵、上三角或下三角等特殊矩阵压缩存储时对称矩阵、上三角或下三角等特殊矩阵压缩存储时对称矩阵、上三角或下三角等特殊矩阵压缩存储时的地址转换公式的地址转换公式的地址转换公式的地址转换公式uu稀疏矩阵的压缩存储稀疏矩阵的压缩存储稀疏矩阵的压缩存储稀疏矩阵的压缩存储：存储特点、：存储特点、：存储特点、：存储特点、三元组表三元组表三元组表三元组表表示表示表示表示广义表广义表广义表广义表uu广义表的定义、特点广义表的定义、特点广义表的定义、特点广义表的定义、特点uu广义表的链式存储广义表的链式存储广义表的链式存储广义表的链式存储结构结构结构结构北膜牡哀褒尚肛雕舀裤屉邀藉孰溃卷注止绿呕婆愁谩损穴爪奢懈秸岁诺漱数组和广义表数组和广义表