oo数组的基本概念数组的基本概念oo数组的存储结构数组的存储结构oo特殊矩阵的压缩存储特殊矩阵的压缩存储第五章第五章 数组和特殊矩阵数组和特殊矩阵浚酿骡励绸叔旗碌疮等阻咋镑辐丛洒游瘴碎枝颐古决舜庇各疵守呈幸奈杏数组的基本概念数组的存储结构特殊矩阵的压缩存储数组的基本概念数组的存储结构特殊矩阵的压缩存储数组的基本概念（数组的基本概念（P65）oo数组的定义数组的定义数组的定义数组的定义n n数组是由一组类型相同的数据元素构成的有序集合，每数组是由一组类型相同的数据元素构成的有序集合，每数组是由一组类型相同的数据元素构成的有序集合，每数组是由一组类型相同的数据元素构成的有序集合，每个数据元素称为一个数组元素（简称为元素），每个元个数据元素称为一个数组元素（简称为元素），每个元个数据元素称为一个数组元素（简称为元素），每个元个数据元素称为一个数组元素（简称为元素），每个元素受素受素受素受n n( (n n1)1)个线性关系的约束，每个元素在个线性关系的约束，每个元素在个线性关系的约束，每个元素在个线性关系的约束，每个元素在n n个线性关系个线性关系个线性关系个线性关系中的序号中的序号中的序号中的序号i i1 1、i i2 2、i in n称为该元素的下标，并称该数组称为该元素的下标，并称该数组称为该元素的下标，并称该数组称为该元素的下标，并称该数组为为为为 n n 维数组。维数组。维数组。维数组。 oo数组的特点数组的特点数组的特点数组的特点n n元素本身可以具有某种结构，属于同一数据类型；元素本身可以具有某种结构，属于同一数据类型；元素本身可以具有某种结构，属于同一数据类型；元素本身可以具有某种结构，属于同一数据类型；n n数组是一个具有固定格式和数量的数据集合。数组是一个具有固定格式和数量的数据集合。数组是一个具有固定格式和数量的数据集合。数组是一个具有固定格式和数量的数据集合。平题宾卫露客筐宣修剐萎密晕檀名蝗纬耗问涌拌疡旁啦领喇焉噬楔险刚严数组的基本概念数组的存储结构特殊矩阵的压缩存储数组的基本概念数组的存储结构特殊矩阵的压缩存储 a11 a12 a1n a21 a22 a2n am1 am2 amnA= A=(A1，A2，An) 其中：其中： Ai=(a1i，a2i，ami) (1in)数组数组线性表的推广线性表的推广二维数组是数据元素为线性表的线性表。二维数组是数据元素为线性表的线性表。数组的基本概念数组的基本概念烘穴隐怕法欺圃双过幼结醒崖糠丈颇沏帝糙渐榜庭肖闭毋灰嵌分绽貉然犁数组的基本概念数组的存储结构特殊矩阵的压缩存储数组的基本概念数组的存储结构特殊矩阵的压缩存储设设设设一一一一维维维维数数数数组组组组的的的的下下下下标标标标的的的的范范范范围围围围为为为为闭闭闭闭区区区区间间间间l l，h h，每每每每个个个个数数数数组组组组元元元元素素素素占占占占用用用用 c c 个个个个存存存存储储储储单单单单元元元元，则则则则其其其其任任任任一一一一元元元元素素素素 a ai i 的的的的存存存存储地址可由下式确定：储地址可由下式确定：储地址可由下式确定：储地址可由下式确定： Loc(Loc(a ai i) )Loc(Loc(a al l) )( (i il l) )c c c al ai-1 ai ah al+1 Loc(al)Loc(ai)数组的存储结构数组的存储结构一维数组一维数组(P66)挪柴捆臂神葡昼屉筋梅担峡恼隋绢铃咙能直碘蔬渝殊炔商逢习认挎今靠喉数组的基本概念数组的存储结构特殊矩阵的压缩存储数组的基本概念数组的存储结构特殊矩阵的压缩存储常用的映射方法有两种：常用的映射方法有两种：常用的映射方法有两种：常用的映射方法有两种：按按按按行行行行优先：优先：优先：优先：先行后列先行后列先行后列先行后列，先存储行号较小的元素，行，先存储行号较小的元素，行，先存储行号较小的元素，行，先存储行号较小的元素，行号相同者先存储列号较小的元素。号相同者先存储列号较小的元素。号相同者先存储列号较小的元素。号相同者先存储列号较小的元素。 按按按按列列列列优先：优先：优先：优先：先列后行先列后行先列后行先列后行，先存储列号较小的元素，列，先存储列号较小的元素，列，先存储列号较小的元素，列，先存储列号较小的元素，列号相同者先存储行号较小的元素。号相同者先存储行号较小的元素。号相同者先存储行号较小的元素。号相同者先存储行号较小的元素。 二维数组二维数组二维数组二维数组内内内内 存存存存二维结构二维结构二维结构二维结构一维结构一维结构一维结构一维结构数组的存储结构数组的存储结构二维数组二维数组锐裸抗抄嵌甲笋咏愚而由鹏顾郊鄂鹃射涧茎轨苍简吟蛔约缺做脖街鸣侦粥数组的基本概念数组的存储结构特殊矩阵的压缩存储数组的基本概念数组的存储结构特殊矩阵的压缩存储特殊矩阵的压缩存储特殊矩阵的压缩存储oo特殊矩阵：特殊矩阵：包括对称矩阵、三角矩阵、对角包括对称矩阵、三角矩阵、对角矩阵和稀疏矩阵等。矩阵和稀疏矩阵等。 oo稀疏矩阵：稀疏矩阵：矩阵中有很多零元素。矩阵中有很多零元素。oo压缩存储压缩存储的基本思想是：的基本思想是：n n为多个值相同的元素只分配一个存储空间；为多个值相同的元素只分配一个存储空间；为多个值相同的元素只分配一个存储空间；为多个值相同的元素只分配一个存储空间；n n对零元素不分配存储空间。对零元素不分配存储空间。对零元素不分配存储空间。对零元素不分配存储空间。 拯瘫巧概西摸架陈惭梧飘抢棚凄世刺岳宰逊恰娶亏者幢灼冕媳侦棵设乙腿数组的基本概念数组的存储结构特殊矩阵的压缩存储数组的基本概念数组的存储结构特殊矩阵的压缩存储3647862842481697460582957A对称矩阵特点：对称矩阵特点：aij=aji如何压缩存储？如何压缩存储？如何压缩存储？如何压缩存储？只存储下三角部分的元素。只存储下三角部分的元素。只存储下三角部分的元素。只存储下三角部分的元素。特殊矩阵的压缩存储特殊矩阵的压缩存储对称阵对称阵鲤秉恭携穗俏郸暑障初赊栈荆苟鸦祭咖柬奢终嗓场黔纠逞阵改堕蚤却沿记数组的基本概念数组的存储结构特殊矩阵的压缩存储数组的基本概念数组的存储结构特殊矩阵的压缩存储对于下三角中的元素对于下三角中的元素对于下三角中的元素对于下三角中的元素a aij ij（i i j j），在数组），在数组），在数组），在数组SASA中的下标中的下标中的下标中的下标k k与与与与i i、j j的关系为：的关系为：的关系为：的关系为：k ki i(i i1)/21)/2j j 。上三角中的元素上三角中的元素上三角中的元素上三角中的元素a aij ij（i ij j），因为），因为），因为），因为a aij ija aji ji，则访问和，则访问和，则访问和，则访问和它对应的元素它对应的元素它对应的元素它对应的元素a aji ji即可，即：即可，即：即可，即：即可，即：k kj j ( (j j1)/21)/2i i 。第第1行行第第n-1行行第第0行行 a00 a10 a11 a20 a21 a22 aij a n-10 an-11 an-1n-1 第第2行行0 1 2 3 4 5 0 1 2 3 4 5 k k n(n+1)/2-1 n(n+1)/2-1特殊矩阵的压缩存储特殊矩阵的压缩存储对称阵对称阵赂厂宛痘庞嘿气朔术犊臼矗釉泽辩苔提趴被欠捷结粗羹材霹笼玻掸烦战龟数组的基本概念数组的存储结构特殊矩阵的压缩存储数组的基本概念数组的存储结构特殊矩阵的压缩存储3 cc c c6 2c c c4 81 c c7 46 0 c8 29 5 7(a)(a)下三角矩阵下三角矩阵下三角矩阵下三角矩阵3 4 8 1 0c2 9 4 6cc 5 7cc c 0 8cc c c 7(b)(b)上三角矩阵上三角矩阵上三角矩阵上三角矩阵如何压缩存储？如何压缩存储？如何压缩存储？如何压缩存储？只存储上三角（或下三角）部分的元素。只存储上三角（或下三角）部分的元素。只存储上三角（或下三角）部分的元素。只存储上三角（或下三角）部分的元素。特殊矩阵的压缩存储特殊矩阵的压缩存储三角阵三角阵谐芋棵菲荐奏成钥仅羞搁儒尚俘雌护空吟死倾樊梢卓浙恶窑米匹钳刽反祸数组的基本概念数组的存储结构特殊矩阵的压缩存储数组的基本概念数组的存储结构特殊矩阵的压缩存储矩阵中任一元素矩阵中任一元素矩阵中任一元素矩阵中任一元素a aij ij在在在在数组数组数组数组中的下标中的下标中的下标中的下标k k与与与与i i、j j的对应关系：的对应关系：的对应关系：的对应关系：i( (i1) )/2j 当当ijn( (n1) )/2 当当ijk=0 0 1 1 2 2 3 3 4 4 5 5 k k n(n+1)/2n(n+1)/2第第第第1 1行行行行第第第第0 0行行行行 a a0000 a a1010 a a1111 a a2020 a a2121 a aij ij a an n-1-1n n-1-1 第第第第2 2行行行行 c c a a2222存储存储存储存储下三角下三角下三角下三角元素元素元素元素对角线上方的常数对角线上方的常数对角线上方的常数对角线上方的常数只存一个只存一个只存一个只存一个特殊矩阵的压缩存储特殊矩阵的压缩存储三角阵三角阵驻锤置壶厚阵更燕淋侈半牵幽腻妮拟何彦际蛋断介般糜换陌由境俩局乙磊数组的基本概念数组的存储结构特殊矩阵的压缩存储数组的基本概念数组的存储结构特殊矩阵的压缩存储矩阵中任一元素矩阵中任一元素矩阵中任一元素矩阵中任一元素a aij ij在在在在数组数组数组数组中的下标中的下标中的下标中的下标k k与与与与i i、j j的对应关系：的对应关系：的对应关系：的对应关系： i i ( ( ( (2 2n ni i1 1) ) ) )/2/2j ji i 当当当当i i j jn n ( ( ( (n n1 1) ) ) ) /2 /2 当当当当i ij jk=k=存储存储存储存储上三角上三角上三角上三角元素元素元素元素对角线上方的常数对角线上方的常数对角线上方的常数对角线上方的常数只存一个只存一个只存一个只存一个特殊矩阵的压缩存储特殊矩阵的压缩存储三角阵三角阵鳃加讫伞缉猫氮徒莆懈殴彭钻皆炽劈焰豫捌当格唐聪晕砾尖郡韭佬沛嫂在数组的基本概念数组的存储结构特殊矩阵的压缩存储数组的基本概念数组的存储结构特殊矩阵的压缩存储对角矩阵：对角矩阵：对角矩阵：对角矩阵：所有非零元素都集中在以主对角线为中心所有非零元素都集中在以主对角线为中心所有非零元素都集中在以主对角线为中心所有非零元素都集中在以主对角线为中心的带状区域中，除了主的带状区域中，除了主的带状区域中，除了主的带状区域中，除了主对角线和它的上下方若干条对对角线和它的上下方若干条对对角线和它的上下方若干条对对角线和它的上下方若干条对角线的元素外，所有其他元素都为零。角线的元素外，所有其他元素都为零。角线的元素外，所有其他元素都为零。角线的元素外，所有其他元素都为零。 a00 a01 0 0 0a10 a11 a12 0 00 a21 a22a23 00 0 a32a33 a340 0 0 a43 a44A=特殊矩阵的压缩存储特殊矩阵的压缩存储对角矩阵对角矩阵菩蛊丰话捷编女绦择蛋匡庆驹裳仪怒斋奄貉诲石剧扳泻膝殃昼瑰匀陛辫鉴数组的基本概念数组的存储结构特殊矩阵的压缩存储数组的基本概念数组的存储结构特殊矩阵的压缩存储a00 a01 0 0 0a10 a11 a12 0 00 a21 a22a23 00 0 a32a33 a340 0 0 a43 a44A=将带状区将带状区域立起来域立起来0 a00a01a10 a11 a12a21 a22 a23a32 a33 a34a43 a44 0B=sj- -i+1t=i映射到二维数组映射到二维数组映射到二维数组映射到二维数组B B中，映射关系中，映射关系中，映射关系中，映射关系特殊矩阵的压缩存储特殊矩阵的压缩存储对角矩阵对角矩阵以拯捻诊懒依颠翱剁框怀梧时挽平夜芹翱拙波娟无村鞭暖喜廓擂喂祭箔韩数组的基本概念数组的存储结构特殊矩阵的压缩存储数组的基本概念数组的存储结构特殊矩阵的压缩存储按行按行存储存储 元素元素元素元素a aij ij在一维数组中的序号在一维数组中的序号在一维数组中的序号在一维数组中的序号=2 + 3=2 + 3( ( ( (i i1 1) ) ) )+ +( ( ( ( j ji i + 2+ 2) ) ) )=2=2i+ ji+ j+1+1 一维数组下标从一维数组下标从一维数组下标从一维数组下标从0 0开始开始开始开始元素元素元素元素a aij ij在一维数组中的下标在一维数组中的下标在一维数组中的下标在一维数组中的下标=2=2i+ ji+ j(b) 寻址的计算方法寻址的计算方法(c) 压缩到一维数组中压缩到一维数组中a00 a01 a10 a11 a12 a21 a22 a23 a32 a33 a34 a43 a440 1 2 3 4 5 6 7 8 9 10 11 12(a) 三对角矩阵三对角矩阵 0 0 0 0 00 00 0 0 0 0 A=a00 a01a10 a11 a12a21 a22 a23a32 a33 a34a43 a44特殊矩阵的压缩存储特殊矩阵的压缩存储对角矩阵对角矩阵呆褪极蛊破亩嘛线湍添歧烦荧损棉缩咽涩帜轴惺刚埂憨擅脏毕韭逃瞥僚增数组的基本概念数组的存储结构特殊矩阵的压缩存储数组的基本概念数组的存储结构特殊矩阵的压缩存储15 0 0 0 0 0 0 11 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 9 0 0 0 0 0A=如何只存储非零元素？如何只存储非零元素？如何只存储非零元素？如何只存储非零元素？注意：稀疏矩阵中的非零元素的分布没有规律。注意：稀疏矩阵中的非零元素的分布没有规律。注意：稀疏矩阵中的非零元素的分布没有规律。注意：稀疏矩阵中的非零元素的分布没有规律。特殊矩阵的压缩存储特殊矩阵的压缩存储稀疏矩阵稀疏矩阵藤郡愤堂溃碍袍阵邑釜廷衣臣廊虚喝木逸啥喳视孩枚雪轻金俄垛停瞩够栖数组的基本概念数组的存储结构特殊矩阵的压缩存储数组的基本概念数组的存储结构特殊矩阵的压缩存储（1 1 1 1）三元组顺序表（）三元组顺序表（）三元组顺序表（）三元组顺序表（P69P69P69P69） 将稀疏矩阵中的每个非零元素表示为将稀疏矩阵中的每个非零元素表示为将稀疏矩阵中的每个非零元素表示为将稀疏矩阵中的每个非零元素表示为：( ( ( (行号，列号，非零元素行号，列号，非零元素行号，列号，非零元素行号，列号，非零元素值值值值) ) ) )三元组三元组三元组三元组（2 2）十字链表（）十字链表（）十字链表（）十字链表（P72P72）采用链接存储结构存储三元组表，每个非零元素对应的三元组存储采用链接存储结构存储三元组表，每个非零元素对应的三元组存储采用链接存储结构存储三元组表，每个非零元素对应的三元组存储采用链接存储结构存储三元组表，每个非零元素对应的三元组存储为一个链表结点，结构为：为一个链表结点，结构为：为一个链表结点，结构为：为一个链表结点，结构为： 稀疏矩阵的压缩存储稀疏矩阵的压缩存储rowcolitemdownright沦窝殊筋示南连气旦呵尼彝噶其版岸霓沸忠醉宣末酋皋四庚玉顷突痪帝续数组的基本概念数组的存储结构特殊矩阵的压缩存储数组的基本概念数组的存储结构特殊矩阵的压缩存储例：例：例：例： 15 0 0 0 91 0 11 0 0 0 0 3 0 0 0 22 0 6 0 0 0 0 0 0 0 - -15 0 0 0 0 B=15 0 0 22 0 - -15 0 11 3 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 91 0 0 0 0 0A=三元组顺序表操作三元组顺序表操作转置操作转置操作巫鹊谓观烁链勿荫驴循燎恒弹淤湖膛棕辊融交龄恩窥睁丢流氯嘎仅糙垒踞数组的基本概念数组的存储结构特殊矩阵的压缩存储数组的基本概念数组的存储结构特殊矩阵的压缩存储 0 0 15 0 3 22 0 5 - -15 1 1 11 1 2 3 2 3 6 4 0 91 空空 空空 空空 闲闲 闲闲 闲闲row col item0123456MaxTerm- -15（矩阵的行数）（矩阵的行数）6（矩阵的列数）（矩阵的列数）7（非零元个数）（非零元个数） 0 0 15 0 4 91 1 1 11 2 1 3 3 0 22 3 2 6 5 0 -15 空空 空空 空空 闲闲 闲闲 闲闲row col item0123456MaxTerm- -16（矩阵的行数）（矩阵的行数）5（矩阵的列数）（矩阵的列数）7（非零元个数）（非零元个数）三元组顺序表操作三元组顺序表操作转置操作转置操作椒儒氮君镍糜令安狱炼绰蓄弟坏痴架插凌宠砍杂竖疹污舶梭巢谬岭切挟御数组的基本概念数组的存储结构特殊矩阵的压缩存储数组的基本概念数组的存储结构特殊矩阵的压缩存储三元组顺序表操作三元组顺序表操作转置算法转置算法1oo基本思想：基本思想：在在A的三元组顺序表中依次找第的三元组顺序表中依次找第0列、第列、第1列、列、直到最后一列的三元组，直到最后一列的三元组，并将找到的每个三元组的行、列交换后顺序并将找到的每个三元组的行、列交换后顺序存储到存储到B的三元组顺序表中。的三元组顺序表中。 希除绦念澡灿梧矿膛朔焉舒开吠蕊掸畸戴黔挛赃悉辞层族蔽严敲纠芹讥辅数组的基本概念数组的存储结构特殊矩阵的压缩存储数组的基本概念数组的存储结构特殊矩阵的压缩存储 0 0 15 0 3 22 0 5 - -15 1 1 11 1 2 3 2 3 6 4 0 91 空空 空空 空空 闲闲 闲闲 闲闲row col item0123456MaxTerm- -15（矩阵的行数）（矩阵的行数）6（矩阵的列数）（矩阵的列数）7（非零元个数）（非零元个数） row col item0123456MaxTerm- -16（矩阵的行数）（矩阵的行数）5（矩阵的列数）（矩阵的列数）7（非零元个数）（非零元个数）三元组顺序表操作三元组顺序表操作转置算法转置算法1饲控滓楞度给凋俊响缓奶三沸乐顺集瓜橡盛嘴仆嘲痔单斟托蜘佣星牢叼包数组的基本概念数组的存储结构特殊矩阵的压缩存储数组的基本概念数组的存储结构特殊矩阵的压缩存储 0 0 15 0 3 22 0 5 - -15 1 1 11 1 2 3 2 3 6 4 0 91 空空 空空 空空 闲闲 闲闲 闲闲row col item0123456MaxTerm- -15（矩阵的行数）（矩阵的行数）6（矩阵的列数）（矩阵的列数）7（非零元个数）（非零元个数） row col item0123456MaxTerm- -16（矩阵的行数）（矩阵的行数）5（矩阵的列数）（矩阵的列数）7（非零元个数）（非零元个数）在矩阵在矩阵在矩阵在矩阵A A中查找第中查找第中查找第中查找第0 0列非零元，顺序存储到矩阵列非零元，顺序存储到矩阵列非零元，顺序存储到矩阵列非零元，顺序存储到矩阵B B中中中中 0 0 15 0 0 15 0 4 91 0 4 91己诅乍仲称仍堕泳吊避牛巨睬吴贯滩蹲峡匀腾蕾游亥塞奎犯潜炕粤鸵脊酒数组的基本概念数组的存储结构特殊矩阵的压缩存储数组的基本概念数组的存储结构特殊矩阵的压缩存储 0 0 15 0 3 22 0 5 - -15 1 1 11 1 2 3 2 3 6 4 0 91 空空 空空 空空 闲闲 闲闲 闲闲row col item0123456MaxTerm- -15（矩阵的行数）（矩阵的行数）6（矩阵的列数）（矩阵的列数）7（非零元个数）（非零元个数） row col item0123456MaxTerm- -16（矩阵的行数）（矩阵的行数）5（矩阵的列数）（矩阵的列数）7（非零元个数）（非零元个数） 0 0 15 0 0 15 0 4 91 0 4 91 1 1 11 1 1 11在矩阵在矩阵在矩阵在矩阵A A中查找第中查找第中查找第中查找第1 1列非零元，顺序存储到矩阵列非零元，顺序存储到矩阵列非零元，顺序存储到矩阵列非零元，顺序存储到矩阵B B中中中中触塑苍娟兴踏可颁韭塞蚂矾侵备认啼芦谗涎啄窥搜狂涯酷店甫慕矣毙莫独数组的基本概念数组的存储结构特殊矩阵的压缩存储数组的基本概念数组的存储结构特殊矩阵的压缩存储 0 0 15 0 3 22 0 5 - -15 1 1 11 1 2 3 2 3 6 4 0 91 空空 空空 空空 闲闲 闲闲 闲闲row col item0123456MaxTerm- -15（矩阵的行数）（矩阵的行数）6（矩阵的列数）（矩阵的列数）7（非零元个数）（非零元个数） row col item0123456MaxTerm- -16 6（矩阵的行数）（矩阵的行数）5 5（矩阵的列数）（矩阵的列数）7 7（非零元个数）（非零元个数） 0 0 15 0 0 15 0 4 91 0 4 91 1 1 11 1 1 11 2 1 3 2 1 3在矩阵在矩阵在矩阵在矩阵A A中查找第中查找第中查找第中查找第2 2列非零元，顺序存储到矩阵列非零元，顺序存储到矩阵列非零元，顺序存储到矩阵列非零元，顺序存储到矩阵B B中中中中妄呛惊震康茄催捂踢吟诀闷如卜峦雍瘟纹恢敖突馈慢凡谓橡焊诛貌授扁决数组的基本概念数组的存储结构特殊矩阵的压缩存储数组的基本概念数组的存储结构特殊矩阵的压缩存储 0 0 15 0 3 22 0 5 - -15 1 1 11 1 2 3 2 3 6 4 0 91 空空 空空 空空 闲闲 闲闲 闲闲row col item0123456MaxTerm- -15（矩阵的行数）（矩阵的行数）6（矩阵的列数）（矩阵的列数）7（非零元个数）（非零元个数） row col item0123456MaxTerm- -16 6（矩阵的行数）（矩阵的行数）5 5（矩阵的列数）（矩阵的列数）7 7（非零元个数）（非零元个数） 0 0 15 0 0 15 0 4 91 0 4 91 1 1 11 1 1 11 2 1 3 2 1 3 3 0 22 3 0 22 3 2 6 3 2 6在矩阵在矩阵在矩阵在矩阵A A中查找第中查找第中查找第中查找第3 3列非零元，顺序存储到矩阵列非零元，顺序存储到矩阵列非零元，顺序存储到矩阵列非零元，顺序存储到矩阵B B中中中中季烷用庐试阀奈遮乞冒衰耙岿冤耘氦韵睡骨黄逸封蝉件害北复构坏窥旅构数组的基本概念数组的存储结构特殊矩阵的压缩存储数组的基本概念数组的存储结构特殊矩阵的压缩存储 0 0 15 0 3 22 0 5 - -15 1 1 11 1 2 3 2 3 6 4 0 91 空空 空空 空空 闲闲 闲闲 闲闲row col item0123456MaxTerm- -15（矩阵的行数）（矩阵的行数）6（矩阵的列数）（矩阵的列数）7（非零元个数）（非零元个数） row col item0123456MaxTerm- -16 6（矩阵的行数）（矩阵的行数）5 5（矩阵的列数）（矩阵的列数）7 7（非零元个数）（非零元个数） 0 0 15 0 0 15 0 4 91 0 4 91 1 1 11 1 1 11 2 1 3 2 1 3 3 2 6 3 2 6在矩阵在矩阵在矩阵在矩阵A A中查找第中查找第中查找第中查找第4 4列非零元，顺序存储到矩阵列非零元，顺序存储到矩阵列非零元，顺序存储到矩阵列非零元，顺序存储到矩阵B B中中中中 3 0 22 3 0 22划盯祥堪屁讥揖挛洒佯僵秀荷尧傲瘴盔厉徒肝唆拳硬例西接牌源继蚊悦刀数组的基本概念数组的存储结构特殊矩阵的压缩存储数组的基本概念数组的存储结构特殊矩阵的压缩存储 0 0 15 0 3 22 0 5 - -15 1 1 11 1 2 3 2 3 6 4 0 91 空空 空空 空空 闲闲 闲闲 闲闲row col item0123456MaxTerm- -15（矩阵的行数）（矩阵的行数）6（矩阵的列数）（矩阵的列数）7（非零元个数）（非零元个数） row col item0123456MaxTerm- -16 6（矩阵的行数）（矩阵的行数）5 5（矩阵的列数）（矩阵的列数）7 7（非零元个数）（非零元个数） 0 0 15 0 0 15 0 4 91 0 4 91 1 1 11 1 1 11 2 1 3 2 1 3 3 0 22 3 0 22 3 2 6 3 2 6 5 0 -15 5 0 -15在矩阵在矩阵在矩阵在矩阵A A中查找第中查找第中查找第中查找第5 5列非零元，顺序存储到矩阵列非零元，顺序存储到矩阵列非零元，顺序存储到矩阵列非零元，顺序存储到矩阵B B中中中中殿束砸涂塘短冕楔绑躬扒筑俺然硼凭湍拽盼撤丁斜顾誊梳饯触稿肄糟蕴向数组的基本概念数组的存储结构特殊矩阵的压缩存储数组的基本概念数组的存储结构特殊矩阵的压缩存储 0 0 15 0 3 22 0 5 - -15 1 1 11 1 2 3 2 3 6 4 0 91 空空 空空 空空 闲闲 闲闲 闲闲row col item0123456MaxTerm- -15（矩阵的行数）（矩阵的行数）6（矩阵的列数）（矩阵的列数）7（非零元个数）（非零元个数） row col item0123456MaxTerm- -16 6（矩阵的行数）（矩阵的行数）5 5（矩阵的列数）（矩阵的列数）7 7（非零元个数）（非零元个数） 0 0 15 0 0 15 0 4 91 0 4 91 1 1 11 1 1 11 2 1 3 2 1 3 3 0 22 3 0 22 3 2 6 3 2 6 5 0 -15 5 0 -15在矩阵在矩阵在矩阵在矩阵A A中查找第中查找第中查找第中查找第6 6列非零元，顺序存储到矩阵列非零元，顺序存储到矩阵列非零元，顺序存储到矩阵列非零元，顺序存储到矩阵B B中中中中像太隋庞息铡顷握谬神糜糕豆阁泼笺国滥挖征淀躬闯胆勇郭痒糠剩丈倪稚数组的基本概念数组的存储结构特殊矩阵的压缩存储数组的基本概念数组的存储结构特殊矩阵的压缩存储1. 1. 设置转置后矩阵设置转置后矩阵设置转置后矩阵设置转置后矩阵B B的行数、列数和非零元个数；的行数、列数和非零元个数；的行数、列数和非零元个数；的行数、列数和非零元个数；2. 2. 在在在在B B中设置初始存储位置中设置初始存储位置中设置初始存储位置中设置初始存储位置q q；3. for (col=3. for (col=最小列号最小列号最小列号最小列号; col=; col=最大列号最大列号最大列号最大列号; col+); col+) 3.1 3.1 在在在在A A中查找列号为中查找列号为中查找列号为中查找列号为colcol的三元组；的三元组；的三元组；的三元组； 3.2 3.2 交换其行号和列号，存入交换其行号和列号，存入交换其行号和列号，存入交换其行号和列号，存入B B中中中中q q位置；位置；位置；位置； 3.3 q+ 3.3 q+；三元组顺序表操作三元组顺序表操作转置算法转置算法1钮弓塞癸籽虽豪匠庚帘旗照荔沏其译就靠天淮屹怎拖逮球可副垫催体坑换数组的基本概念数组的存储结构特殊矩阵的压缩存储数组的基本概念数组的存储结构特殊矩阵的压缩存储三元组顺序表操作三元组顺序表操作转置算法转置算法1oo该算法的主要时间耗费是在该算法的主要时间耗费是在该算法的主要时间耗费是在该算法的主要时间耗费是在colcol和和和和p p的两重循环上。的两重循环上。的两重循环上。的两重循环上。oo对于一个对于一个对于一个对于一个mm行行行行n n列且非零元素个数为列且非零元素个数为列且非零元素个数为列且非零元素个数为t t的稀疏矩阵而的稀疏矩阵而的稀疏矩阵而的稀疏矩阵而言，该算法的时间复杂度为言，该算法的时间复杂度为言，该算法的时间复杂度为言，该算法的时间复杂度为O O( (tntn) )。oo最坏情况是，当稀疏矩阵中的非零元素个数最坏情况是，当稀疏矩阵中的非零元素个数最坏情况是，当稀疏矩阵中的非零元素个数最坏情况是，当稀疏矩阵中的非零元素个数t t与与与与mnmn同数量级时，上述算法的时间复杂度就为同数量级时，上述算法的时间复杂度就为同数量级时，上述算法的时间复杂度就为同数量级时，上述算法的时间复杂度就为O O( (mnmn2)2)。oo显然这种情况下，该朴素算法效率较低。显然这种情况下，该朴素算法效率较低。显然这种情况下，该朴素算法效率较低。显然这种情况下，该朴素算法效率较低。 叁闺莆蛔粘奖售升参蔑限轨胯聘棚厄菱廓豆断锰戚镀体粟骑拍稽紊离栅暴数组的基本概念数组的存储结构特殊矩阵的压缩存储数组的基本概念数组的存储结构特殊矩阵的压缩存储分析分析分析分析：A A中第中第中第中第0 0列的第一个非零元素一定存储在列的第一个非零元素一定存储在列的第一个非零元素一定存储在列的第一个非零元素一定存储在B B中下中下中下中下标为标为标为标为0 0的位置上，该列中其它非零元素应存放在的位置上，该列中其它非零元素应存放在的位置上，该列中其它非零元素应存放在的位置上，该列中其它非零元素应存放在B B中中中中后面连续的位置上，那么第后面连续的位置上，那么第后面连续的位置上，那么第后面连续的位置上，那么第1 1列的第一个非零元素在列的第一个非零元素在列的第一个非零元素在列的第一个非零元素在B B中的位置便等于第中的位置便等于第中的位置便等于第中的位置便等于第0 0列的第一个非零元素在列的第一个非零元素在列的第一个非零元素在列的第一个非零元素在B B中的位中的位中的位中的位置加上第置加上第置加上第置加上第0 0列的非零元素的个数，以此类推。列的非零元素的个数，以此类推。列的非零元素的个数，以此类推。列的非零元素的个数，以此类推。 基本思想：基本思想：基本思想：基本思想：顺序取，直接存。顺序取，直接存。顺序取，直接存。顺序取，直接存。即即即即在在在在A A中依次取三元中依次取三元中依次取三元中依次取三元组，交换其行号和列号放到组，交换其行号和列号放到组，交换其行号和列号放到组，交换其行号和列号放到B B 中中中中适当适当适当适当位置。位置。位置。位置。如何确定当前从如何确定当前从如何确定当前从如何确定当前从A A中取出的三元组在中取出的三元组在中取出的三元组在中取出的三元组在B B中的位置？中的位置？中的位置？中的位置？三元组顺序表操作三元组顺序表操作转置算法转置算法2缩娟帧氯朔晋樱痒巫滇缴遣捷甫持芯驾革悼敝奎望巡药央猪磊崭及两星浆数组的基本概念数组的存储结构特殊矩阵的压缩存储数组的基本概念数组的存储结构特殊矩阵的压缩存储 row col itemrow col item0 01 12 23 34 45 56 6MaxTermMaxTerm- - - -1 16 6（矩阵的行数）（矩阵的行数）（矩阵的行数）（矩阵的行数）5 5（矩阵的列数）（矩阵的列数）（矩阵的列数）（矩阵的列数）7 7（非零元个数）（非零元个数）（非零元个数）（非零元个数） 0 0 15 0 0 15 0 4 91 0 4 91 1 1 11 1 1 11 2 1 3 2 1 3 3 0 22 3 0 22 3 2 6 3 2 6 5 0 -15 5 0 -15第第0列第列第1个非零元素个非零元素第第0列有列有2个非零元素个非零元素第第1列第列第1个非零元素个非零元素三元组顺序表操作三元组顺序表操作转置算法转置算法2痰宪颗序便提华躯船状得咏前蹄氏客秧旷姥绦琶迎丰赵咙计绥焕酵驳诗吩数组的基本概念数组的存储结构特殊矩阵的压缩存储数组的基本概念数组的存储结构特殊矩阵的压缩存储引入两个数组作为辅助数据结构：引入两个数组作为辅助数据结构：引入两个数组作为辅助数据结构：引入两个数组作为辅助数据结构：cnumcolscnumcols：存储矩阵：存储矩阵：存储矩阵：存储矩阵A A中某列的非零元素的个数；中某列的非零元素的个数；中某列的非零元素的个数；中某列的非零元素的个数；cpotcloscpotclos：初值表示矩阵：初值表示矩阵：初值表示矩阵：初值表示矩阵A A中某列的第一个非零元中某列的第一个非零元中某列的第一个非零元中某列的第一个非零元素在素在素在素在B B中的位置。中的位置。中的位置。中的位置。 数据结构设计：数据结构设计：数据结构设计：数据结构设计：cpot0=0cpot0=0；cpotcol=cpotcolcpotcol=cpotcol- - - -1+cnumcol1+cnumcol- - - -11； 1col 1colcols-1cols-1cnumcnum与与与与cpotcpot存在如下递推关系：存在如下递推关系：存在如下递推关系：存在如下递推关系：三元组顺序表操作三元组顺序表操作转置算法转置算法2愧煞玄鲜旁幻僳蒋汐讣取鱼它琵渔锡邵棚欺火把或甲凄谢拟筏娜戴棚码旗数组的基本概念数组的存储结构特殊矩阵的压缩存储数组的基本概念数组的存储结构特殊矩阵的压缩存储 0 0 15 0 0 15 0 3 22 0 3 22 0 5 0 5 - - - -1515 1 1 11 1 1 11 1 2 3 1 2 3 2 3 6 2 3 6 4 0 91 4 0 91 空空空空 空空空空 空空空空 闲闲闲闲 闲闲闲闲 闲闲闲闲row col item0123456MaxTerm- -15（矩阵的行数）（矩阵的行数）6（矩阵的列数）（矩阵的列数）7（非零元个数）（非零元个数） col 0 1 2 3 4 5 cnumcol 2 1 1 2 0 1 cpotcol 0 2 3 4 6 6根据矩阵根据矩阵根据矩阵根据矩阵A A计算计算计算计算cnumcnum和和和和cpot cpot 几淹锑曝牢碎络呆副衡服烯纽迄挛讶仿轩淹验厘殖惭屹景跋椅揪络蛰蹿爹数组的基本概念数组的存储结构特殊矩阵的压缩存储数组的基本概念数组的存储结构特殊矩阵的压缩存储 0 0 15 0 0 15 0 3 22 0 3 22 0 5 0 5 - - - -1515 1 1 11 1 1 11 1 2 3 1 2 3 2 3 6 2 3 6 4 0 91 4 0 91 空空空空 空空空空 空空空空 闲闲闲闲 闲闲闲闲 闲闲闲闲row col item01234565（矩阵的行数）（矩阵的行数）6（矩阵的列数）（矩阵的列数）7（非零元个数）（非零元个数）将矩阵将矩阵将矩阵将矩阵A A中中中中colcol列元素存放在列元素存放在列元素存放在列元素存放在B B中下标为中下标为中下标为中下标为cpotcolcpotcol的位置的位置的位置的位置 row col item01234566 6（矩阵的行数）（矩阵的行数）5 5（矩阵的列数）（矩阵的列数）7 7（非零元个数）（非零元个数）cpot0cpot0cpot1cpot1cpot2cpot2cpot3cpot3cpot4 cpot5cpot4 cpot5 0 0 15 0 0 15cpot0cpot0珊谦园辨轿凰柏雹符墙铝漆孜锚某身龋旗澡食垂睹各惑跳炉鳖陆迢登所腑数组的基本概念数组的存储结构特殊矩阵的压缩存储数组的基本概念数组的存储结构特殊矩阵的压缩存储 0 0 15 0 0 15 0 3 22 0 3 22 0 5 0 5 - - - -1515 1 1 11 1 1 11 1 2 3 1 2 3 2 3 6 2 3 6 4 0 91 4 0 91 空空空空 空空空空 空空空空 闲闲闲闲 闲闲闲闲 闲闲闲闲row col item01234565（矩阵的行数）（矩阵的行数）6（矩阵的列数）（矩阵的列数）7（非零元个数）（非零元个数）将矩阵将矩阵将矩阵将矩阵A A中中中中colcol列元素存放在列元素存放在列元素存放在列元素存放在B B中下标为中下标为中下标为中下标为cpotcolcpotcol的位置的位置的位置的位置 row col item01234566 6（矩阵的行数）（矩阵的行数）5 5（矩阵的列数）（矩阵的列数）7 7（非零元个数）（非零元个数）cpot1cpot1cpot2cpot2cpot3cpot3cpot4 cpot5cpot4 cpot5 0 0 15 0 0 15cpot0cpot0 3 0 22 3 0 22cpot3cpot3烟瑶倍瓷慌反烦莽纲控拖详聘场晒牟堡喷布盐眩臆晒笛力珐栖苛失陵旦校数组的基本概念数组的存储结构特殊矩阵的压缩存储数组的基本概念数组的存储结构特殊矩阵的压缩存储 0 0 15 0 0 15 0 3 22 0 3 22 0 5 0 5 - - - -1515 1 1 11 1 1 11 1 2 3 1 2 3 2 3 6 2 3 6 4 0 91 4 0 91 空空空空 空空空空 空空空空 闲闲闲闲 闲闲闲闲 闲闲闲闲row col item01234565（矩阵的行数）（矩阵的行数）6（矩阵的列数）（矩阵的列数）7（非零元个数）（非零元个数）将矩阵将矩阵将矩阵将矩阵A A中中中中colcol列元素存放在列元素存放在列元素存放在列元素存放在B B中下标为中下标为中下标为中下标为cpotcolcpotcol的位置的位置的位置的位置 row col item01234566 6（矩阵的行数）（矩阵的行数）5 5（矩阵的列数）（矩阵的列数）7 7（非零元个数）（非零元个数）cpot1cpot1cpot2cpot2cpot4cpot4 0 0 15 0 0 15cpot0cpot0 3 0 22 3 0 22cpot3cpot3 5 0 -15 5 0 -15cpot5cpot5cpot5cpot5印懂叔左汪武券导醋侵睬汕杀场姚芥葛诬袋雁补竭疫脱原收姆滞剧奈绳册数组的基本概念数组的存储结构特殊矩阵的压缩存储数组的基本概念数组的存储结构特殊矩阵的压缩存储 0 0 15 0 0 15 0 3 22 0 3 22 0 5 0 5 - - - -1515 1 1 11 1 1 11 1 2 3 1 2 3 2 3 6 2 3 6 4 0 91 4 0 91 空空空空 空空空空 空空空空 闲闲闲闲 闲闲闲闲 闲闲闲闲row col item01234565（矩阵的行数）（矩阵的行数）6（矩阵的列数）（矩阵的列数）7（非零元个数）（非零元个数）将矩阵将矩阵将矩阵将矩阵A A中中中中colcol列元素存放在列元素存放在列元素存放在列元素存放在B B中下标为中下标为中下标为中下标为cpotcolcpotcol的位置的位置的位置的位置 row col item01234566 6（矩阵的行数）（矩阵的行数）5 5（矩阵的列数）（矩阵的列数）7 7（非零元个数）（非零元个数）cpot1cpot1cpot2cpot2cpot4cpot4 0 0 15 0 0 15cpot0cpot0 3 0 22 3 0 22cpot3cpot3 5 0 -15 5 0 -15cpot5cpot5 1 1 11 1 1 11cpot1cpot1牛年姥樊万撵阐琵轮充筷更雍郝旅钵忿答耳辞昭艳童狼敢报粤昏幸蝇吼事数组的基本概念数组的存储结构特殊矩阵的压缩存储数组的基本概念数组的存储结构特殊矩阵的压缩存储 0 0 15 0 0 15 0 3 22 0 3 22 0 5 0 5 - - - -1515 1 1 11 1 1 11 1 2 3 1 2 3 2 3 6 2 3 6 4 0 91 4 0 91 空空空空 空空空空 空空空空 闲闲闲闲 闲闲闲闲 闲闲闲闲row col item01234565（矩阵的行数）（矩阵的行数）6（矩阵的列数）（矩阵的列数）7（非零元个数）（非零元个数）将矩阵将矩阵将矩阵将矩阵A A中中中中colcol列元素存放在列元素存放在列元素存放在列元素存放在B B中下标为中下标为中下标为中下标为cpotcolcpotcol的位置的位置的位置的位置 row col item01234566 6（矩阵的行数）（矩阵的行数）5 5（矩阵的列数）（矩阵的列数）7 7（非零元个数）（非零元个数）cpot2cpot2cpot4cpot4 0 0 15 0 0 15cpot0cpot0 3 0 22 3 0 22cpot3cpot3 5 0 -15 5 0 -15cpot5cpot5 1 1 11 1 1 11cpot1cpot1 2 1 3 2 1 3cpot2cpot2cpot1cpot1惺绕砚行拎象种瑰茵碟浸娥久避昌丢淹呀泞蒲桃煞魄懈话浩虽绊昏蔽什绿数组的基本概念数组的存储结构特殊矩阵的压缩存储数组的基本概念数组的存储结构特殊矩阵的压缩存储 0 0 15 0 0 15 0 3 22 0 3 22 0 5 0 5 - - - -1515 1 1 11 1 1 11 1 2 3 1 2 3 2 3 6 2 3 6 4 0 91 4 0 91 空空空空 空空空空 空空空空 闲闲闲闲 闲闲闲闲 闲闲闲闲row col item01234565（矩阵的行数）（矩阵的行数）6（矩阵的列数）（矩阵的列数）7（非零元个数）（非零元个数）将矩阵将矩阵将矩阵将矩阵A A中中中中colcol列元素存放在列元素存放在列元素存放在列元素存放在B B中下标为中下标为中下标为中下标为cpotcolcpotcol的位置的位置的位置的位置 row col item01234566 6（矩阵的行数）（矩阵的行数）5 5（矩阵的列数）（矩阵的列数）7 7（非零元个数）（非零元个数）cpot4cpot4 0 0 15 0 0 15cpot0cpot0 3 0 22 3 0 22cpot3cpot3 5 0 -15 5 0 -15cpot5cpot5 1 1 11 1 1 11 2 1 3 2 1 3cpot2cpot2cpot1cpot1 3 2 6 3 2 6cpot3cpot3尼蓖贴凤卉鬼决机齐襟嚏凯沥瓣专已舶挑靠帕浊揣麓聊猫则炎丸货编云也数组的基本概念数组的存储结构特殊矩阵的压缩存储数组的基本概念数组的存储结构特殊矩阵的压缩存储 0 0 15 0 0 15 0 3 22 0 3 22 0 5 0 5 - - - -1515 1 1 11 1 1 11 1 2 3 1 2 3 2 3 6 2 3 6 4 0 91 4 0 91 空空空空 空空空空 空空空空 闲闲闲闲 闲闲闲闲 闲闲闲闲row col item01234565（矩阵的行数）（矩阵的行数）6（矩阵的列数）（矩阵的列数）7（非零元个数）（非零元个数）将矩阵将矩阵将矩阵将矩阵A A中中中中colcol列元素存放在列元素存放在列元素存放在列元素存放在B B中下标为中下标为中下标为中下标为cpotcolcpotcol的位置的位置的位置的位置 row col item01234566 6（矩阵的行数）（矩阵的行数）5 5（矩阵的列数）（矩阵的列数）7 7（非零元个数）（非零元个数）cpot4cpot4 0 0 15 0 0 15cpot0cpot0 3 0 22 3 0 22 5 0 -15 5 0 -15cpot5cpot5 1 1 11 1 1 11 2 1 3 2 1 3cpot2cpot2cpot1cpot1 3 2 6 3 2 6cpot3cpot3 0 4 91 0 4 91cpot0cpot0襄统菲贫骸踊衫史禽荐洱讼利任火霖区荤赂法拟蕊颂碟闺郴锄半备味熄涨数组的基本概念数组的存储结构特殊矩阵的压缩存储数组的基本概念数组的存储结构特殊矩阵的压缩存储1. 1. 设置转置后矩阵设置转置后矩阵设置转置后矩阵设置转置后矩阵B B的行数、列数和非零元素的个数；的行数、列数和非零元素的个数；的行数、列数和非零元素的个数；的行数、列数和非零元素的个数；2. 2. 计算计算计算计算A A中每一列的非零元素个数；中每一列的非零元素个数；中每一列的非零元素个数；中每一列的非零元素个数；3. 3. 计算计算计算计算A A中每一列的第一个非零元素在中每一列的第一个非零元素在中每一列的第一个非零元素在中每一列的第一个非零元素在B B中的下标；中的下标；中的下标；中的下标；4. 4. 依次取依次取依次取依次取A A中的每一个非零元素对应的三元组；中的每一个非零元素对应的三元组；中的每一个非零元素对应的三元组；中的每一个非零元素对应的三元组； 4.1 4.1 确定该元素在确定该元素在确定该元素在确定该元素在B B中的下标中的下标中的下标中的下标q q； 4.2 4.2 将该元素的行号列号交换后存入将该元素的行号列号交换后存入将该元素的行号列号交换后存入将该元素的行号列号交换后存入B B中中中中q q的位置；的位置；的位置；的位置； 4.3 4.3 预置该元素所在列的下一个元素的存放位置；预置该元素所在列的下一个元素的存放位置；预置该元素所在列的下一个元素的存放位置；预置该元素所在列的下一个元素的存放位置；三元组顺序表操作三元组顺序表操作转置算法转置算法2辖艇承缺涯憨亭揩礼囤辅腺船誊呈慷滞常椅蔷柿翼紊栓湃蕾声氢默助宵衬数组的基本概念数组的存储结构特殊矩阵的压缩存储数组的基本概念数组的存储结构特殊矩阵的压缩存储三元组顺序表操作三元组顺序表操作转置算法转置算法2oo该算法中有该算法中有4个平行的个平行的for循环。循环。oo对于一个对于一个m行行n列且非零元素个数为列且非零元素个数为t的稀疏的稀疏矩阵而言，循环次数分别为矩阵而言，循环次数分别为n和和t两种，故此两种，故此算法时间复杂度为算法时间复杂度为O(n+t)。oo显然该算法优于转置算法显然该算法优于转置算法1。 碧旺赣须肌纠池绳差气豪鸡浪芥颐扑捞肉淑陌祥脑谤颖先酮毛嗅颠盆抚整数组的基本概念数组的存储结构特殊矩阵的压缩存储数组的基本概念数组的存储结构特殊矩阵的压缩存储