《第五部分数组和广义表教学课件》由会员分享，可在线阅读，更多相关《第五部分数组和广义表教学课件（83页珍藏版）》请在金锄头文库上搜索。
1、第五章第五章数组和广义表数组和广义表 数组可以看成是一种特殊的线性表，即线性表中数据元素本身也是一个线性表第第五五章章数数组组和和广广义义表表级棱果萤袱缮钒二婉漓臭胀拓氟宋乞道制婚躯虐搪急疮舞的悟廊圾州哮夸第五部分数组和广义表教学课件第五部分数组和广义表教学课件5.1数组的定义数组的定义5.3矩阵的压缩存储矩阵的压缩存储5.2数组的顺序表示和实现数组的顺序表示和实现5.4广义表的定义广义表的定义5.5 广义表的存储结构广义表的存储结构5.6m元多项式的表示元多项式的表示5.7广义表的递归算法广义表的递归算法第第五五章章数数组组和和广广义义表表亨党粟顺嘲盈踌巳寄侨紊芽荣燥礁俱辫谗郡悲厅守贫佛拘亢
2、五祁鸯签恬茵第五部分数组和广义表教学课件第五部分数组和广义表教学课件5.1 数组的定义数组特点数组特点数组结构固定数组结构固定数据元素同构数据元素同构数组运算数组运算给定一组下标，存取相应的数据元素给定一组下标，存取相应的数据元素给定一组下标，修改数据元素的值给定一组下标，修改数据元素的值( )( )( )( )( )aj = (a0j,a1j, , am-1j)( )( )( )( )ai = (ai0,ai1, , ain-1)数组的定义=m* nAm-1n-1m-1n-2n-1aaaaaa.1111001a00a10am-10斜纯丸惫旧天喂文捆吗舀战付匙馒琉错吓打促卢钥拌舱贝溯竣皱轨敌侍
3、腥第五部分数组和广义表教学课件第五部分数组和广义表教学课件抽象数据类型数组的定义如下：抽象数据类型数组的定义如下：ADT List ADT List 数据对象：数据对象：数据关系：数据关系：D D a a | n(n0) | n(n0)称为数组的维数，称为数组的维数，b bi i是是 数组第数组第i i维的长度，维的长度，j ji i是数组元素的第是数组元素的第i i维维 下标下标a a ElemSet ElemSet ji =0,.,bi -1, i=1,2,.,n j1 1j2 2jn nj1 1j2 2jn nR1R1 | 0 0 j jk k b bk k -1, 1 -1, 1 k
4、k n n 且且k k i, i, 0 0 j ji i b bi i -2, i=2,.,n, 0 -2, i=2,.,n, 0 j ji i b bi i -2, -2,j1 1 ji ijn nj1 1 ji i+1jn n数组的定义茄慎案泻承臻椒稽挨声睁迭蜂秆晶乌齿收逼跪豌尊佃凳伸衙忠灌哭图布樱第五部分数组和广义表教学课件第五部分数组和广义表教学课件数组的定义二维数组的定义二维数组的定义:数据对象数据对象: : D=aij|0ib1-1,0jb2-1数据关系数据关系: : R=ROW,COLROW=|0ib1-2,0jb2-1COL=|0ib1-1,0jb2-2涂酸清召翔傅苑亚氰抑蛊烧
5、奎睹戍惺悬淀彩姻叶频激萎欣碳揽侠谁悔浦震第五部分数组和广义表教学课件第五部分数组和广义表教学课件InitArray(&A,n,bound1,.,boundn)DestroyArray(&A)Value(A,&e,index1,.,indexn)Assign(&A,e,index1,.,indexn)基本操作：基本操作：数组的定义砧励尝疆喳獭讶孤福瓶褂拔讽殆捣净讳徽深察滓刻汝暮曾坑摆绕枉突悠斑第五部分数组和广义表教学课件第五部分数组和广义表教学课件=m* nAm-1n-1m-1n-2n-1aaaaaa.1111001a00a10am-10数组的定义蒲都奶枣帚智睹剔蓬得桥秃度乞堤缴键衙丙筛品涩俺挑
6、诱勾臂舶萧旦豫认第五部分数组和广义表教学课件第五部分数组和广义表教学课件有两种顺序映象的方式有两种顺序映象的方式:n以行序为主序以行序为主序(低下标优先低下标优先)n以列序为主序以列序为主序(高下标优先高下标优先)数数组组的的顺顺序序表表示示和和实实现现5.2 数组的顺序表示和实现 由于计算机的内存结构是一维的，因此用由于计算机的内存结构是一维的，因此用一维内存来表示多维数组，就必须按某种次一维内存来表示多维数组，就必须按某种次序将数组元素排成一列序列，然后将这个线序将数组元素排成一列序列，然后将这个线性序列存放在存储器中。性序列存放在存储器中。劝黄碘禁匙贬沙倒例水蒋寐删荤闽紫蹭肤廉影冈蟹厕几
7、丛专卡盘锁物蕾卤第五部分数组和广义表教学课件第五部分数组和广义表教学课件Loc(aij)=Loc(a00)+i*n+j*l按行序为主序存放按行序为主序存放am-10am-11.am-1n-1a00a01.a0n-1a10a11.a0n-1.n-1am-1n-1.am-10am-10.a1n-1.a11a10a0n-1.a01a0001m*n-1n数数组组的的顺顺序序表表示示和和实实现现醉塌媚河煮跨钝皇芬鸥轨陋薛毒拓铡夹蒋唱侈寨诵纱期尼疆栽繁孔瓷郭厦第五部分数组和广义表教学课件第五部分数组和广义表教学课件按列序为主序存放按列序为主序存放01m-1m*n-1mam-1n-1.a1n-1a0n-1.
8、am-11.a11a01am-10.a10a00a00a01.a0n-1a10a11.a1n-1am-10am-11am-1n-1.Loc(aij)=Loc(a00)+j*m+i*l数数组组的的顺顺序序表表示示和和实实现现妒领精洒诉面厩谅号受值妆做庇孙本曼烘敖姬腔庆插钮艺孽血晋凉衅钵蛤第五部分数组和广义表教学课件第五部分数组和广义表教学课件4.3 矩阵的压缩存储特殊矩阵特殊矩阵 所谓特殊矩阵是指非零元素或零元素的分布所谓特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵，下面我们讨论几种特殊矩阵有一定规律的矩阵，下面我们讨论几种特殊矩阵的压缩存储。的压缩存储。1 1、对称矩阵对称矩阵 在一个在
9、一个n n阶方阵阶方阵A A中，若元素满足下述中，若元素满足下述性质：性质： a aijij=a=ajiji 0i,jn-1 0i,jn-1则称则称A A为对称矩阵。为对称矩阵。矩阵的压缩存储漳吝画鲸留绩代萝糜夕弘宠及蜗宗痢究乒熙狡脊耍供彩刺蔗舵钞秽将掘踌第五部分数组和广义表教学课件第五部分数组和广义表教学课件a00a01.a0n-1a10a11.a1n-1an-10an-11.an-1n-1.元素总数为元素总数为: : n(n+1)/2n(n+1)/2将这些元素存放在一个向量将这些元素存放在一个向量sa0.n(n+1)/2-1sa0.n(n+1)/2-1中中矩阵的压缩存储陆屉看邑放汀处亩淳恳
10、替眼谷砖贫疤肤弃竟馋嚷描癌倍丢唉迷充漏汽归包第五部分数组和广义表教学课件第五部分数组和广义表教学课件a aijij和和saksak之间对应关系之间对应关系ij则则aij在下三角形中。在下三角形中。aij之前的之前的i行（从第行（从第0行到第行到第i-1行）一共有行）一共有1+2+i=i(i+1)/2个元素，个元素，在第在第i行上，行上，aij之前恰有之前恰有j个元素（即个元素（即ai0,ai1,ai2,aij-1），因此有：），因此有：k=i*(i+1)/2+j0kn(n+1)/2a11a21a22a31a32an1ann.k=01234n(n-1)/2n(n+1)/2-1按行序为主序：按行序
11、为主序：矩阵的压缩存储竞汛弥茵何章酣犬跨蕴裹踪叙没拴祟窖垮猴唾拱晓孺履律峭颜推怀擂匙蛋第五部分数组和广义表教学课件第五部分数组和广义表教学课件a11a21a22a31a32an1ann.k=01234n(n-1)/2n(n+1)/2-1按行序为主序：按行序为主序：ij则则aij是在上三角矩阵中。因为是在上三角矩阵中。因为aij=aji，所以，所以只要交换上述对应关系式中的只要交换上述对应关系式中的i和和j即可得到：即可得到：k=j*(j+1)/2+i0k(k-1)/2 i-j(k-1)/2 ，则元素，则元素 a aijij=0=0。 对角矩阵可按行优先顺序或对角线的顺序，对角矩阵可按行优先顺序
12、或对角线的顺序，将其压缩存储到一个向量中，并且也能找到每个将其压缩存储到一个向量中，并且也能找到每个非零元素和向量下标的对应关系。非零元素和向量下标的对应关系。Loc(aij)=Loc(a11)+2(i-1)+(j-1)a11 a12 a21 a22 a23 ann-1 ann .k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1 按行序为主序：矩阵的压缩存储渠巾音船贤呕逮钥红鸭卸阳缘寅嚏受雅耳松隆寺情峻蹈现浙遭寐端暂氨坤第五部分数组和广义表教学课件第五部分数组和广义表教学课件假设 m 行 n 列的矩阵含 t 个非零元素，则称 为稀疏因子稀疏因子。通常认为通常认为 0.05的矩阵为
13、稀疏矩阵。的矩阵为稀疏矩阵。稀疏矩阵稀疏矩阵矩阵的压缩存储绪伶漾娠筋峭失啮驰董消坍禹蟹念紫赵炙牌李斋惊常台政婆坠桂附癣登夹第五部分数组和广义表教学课件第五部分数组和广义表教学课件M由(1,2,12), (1,3,9), (3,1,-3), (3,6,14), (4,3,24), (5,2,18), (6,1,15), (6,4,-7) 和矩阵维数（6,7）唯一确定定义定义：非零元较零元少，且分布没有一定规律的矩阵：非零元较零元少，且分布没有一定规律的矩阵压缩存储原则压缩存储原则：只存矩阵的行列维数和每个非零元的行：只存矩阵的行列维数和每个非零元的行列下标及其值列下标及其值矩阵的压缩存储穴弄揣距
14、妨羔勤豺村家嘿霓棘垢魄艘旭孩觅最婶份苍嘿过匀搓沟企淆熏搓第五部分数组和广义表教学课件第五部分数组和广义表教学课件稀疏矩阵的压缩存储方法稀疏矩阵的压缩存储方法:一、三元组顺序表一、三元组顺序表二、行逻辑联接的顺序表二、行逻辑联接的顺序表三、三、十字链表十字链表矩阵的压缩存储枢渝饯啃褪阅荔氰逸自墓溃去纶玄毙吻酌室旱绕蔬玉朽唬床丛呵吼醇氰绥第五部分数组和广义表教学课件第五部分数组和广义表教学课件三元组表所需存储单元个数为三元组表所需存储单元个数为3(t+1)其中其中t为非零元个数为非零元个数678121213931-3361443245218611564-7maijv012345678ma0.i,m
15、a0.j,ma0.v分别存放分别存放矩阵行列维数和非零元个数矩阵行列维数和非零元个数行列下标行列下标非零元值非零元值三元组顺序表三元组顺序表矩阵的压缩存储颗取圆忱筷肢氰惰龟缄荫康嫡殿利绅眺何轨溪针辛瓢邢寺膘瘤釉芭依补郧第五部分数组和广义表教学课件第五部分数组和广义表教学课件#defineMAXSIZE12500typedefstructinti,j;/该非零元的行下标和列下标该非零元的行下标和列下标ElemTypee;/该非零元的值该非零元的值Triple;/三元组类型三元组类型typedefunionTripledataMAXSIZE+1;intmu,nu,tu;TSMatrix;/稀疏矩阵
16、类型稀疏矩阵类型矩阵的压缩存储惮类绵氖岸穴堡牲洼郸燥离变埋帐编优匪委注掩械察名王乔瘩镁疼申忿恼第五部分数组和广义表教学课件第五部分数组和广义表教学课件求转置矩阵求转置矩阵Y问题描述：已知一个稀疏矩阵的三元组表，问题描述：已知一个稀疏矩阵的三元组表，求该矩阵转置矩阵的三元组表求该矩阵转置矩阵的三元组表Y问题分析问题分析一般矩阵转置算法：一般矩阵转置算法：for(col=0;coln;col+)for(row=0;rowm;row+)ncolrow=mrowcol;T(n)=O(m n)矩阵的压缩存储其时间复杂度为其时间复杂度为:O(munu)繁忿殉肛涩妇背投感搐衍脾芋铜牡胁捶濒瑞丛刷巍什灰忧柒仆
17、淘缺吸篓采第五部分数组和广义表教学课件第五部分数组和广义表教学课件6 7 8 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 i j v012345678mai j v7 6 8 1 3 -3 1 6 15 2 1 12 2 5 18 3 1 9 3 4 24 4 6 -7 6 3 14 012345678mb?矩阵的压缩存储唬鸽娥饶空绢以句浅躬虱绍南荷钞藏绽誊治茎喜件歹狮啸竞邀伟孔贿浅环第五部分数组和广义表教学课件第五部分数组和广义表教学课件解决思路：只要做到解决思路：只要做到 将矩阵行、列维数互换将矩阵行、列维数互换 将每个三元
18、组中的将每个三元组中的i i和和j j相互调换相互调换 重排三元组次序，使重排三元组次序，使mbmb中元素以中元素以N N的行的行(M(M的的列列) )为主序为主序方法一：按方法一：按M的列序转置的列序转置即按即按mb中三元组次序依次在中三元组次序依次在ma中找到相中找到相应的三元组进行转置。应的三元组进行转置。为找到为找到M中每一列所有非零元素，需对其中每一列所有非零元素，需对其三元组表三元组表ma从第一行起扫描一遍。由于从第一行起扫描一遍。由于ma中中以以M行序为主序行序为主序,所以由此得到的恰是所以由此得到的恰是mb中应中应有的顺序有的顺序矩阵的压缩存储描佑焰瞳殉纪演嫩胁趣响吸圃蛊糕沦缨
19、牧爱恭脊凛杉芥厕遗乒箩蚌只昧原第五部分数组和广义表教学课件第五部分数组和广义表教学课件算法分析：T(n)=O(M的列数n非零元个数t) 若 t 与mn同数量级，则矩阵的压缩存储焰词蹄仅添帮哈勘绍舒畜硅应埃框静膛劣徐美哀荚淆疟曙啥街窥穆戚司酿第五部分数组和广义表教学课件第五部分数组和广义表教学课件6 7 8 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 i j v0 1 2 3 4 5 6 7 8ma7 6 8 1 3 -3 1 6 15 2 1 12 2 5 18 3 1 9 3 4 24 4 6 -7 6 3 14 i j v0
20、 1 2 3 4 5 6 7 8mbkppppppppkkkkppppppppcol=1col=2矩阵的压缩存储弯氰当揉赵鸵精交赶皆穴败软姜符汽浇曾讨润北粒涅剪青病奥惠塌犊研命第五部分数组和广义表教学课件第五部分数组和广义表教学课件方法二：快速转置方法二：快速转置 即按即按mama中三元组次序转置，转置结果放入中三元组次序转置，转置结果放入b b中中恰当位置恰当位置 此法关键是要预先确定此法关键是要预先确定M M中每一列第一个非零中每一列第一个非零元在元在mbmb中位置，为确定这些位置，转置前应先求得中位置，为确定这些位置，转置前应先求得M M的每一列中非零元个数的每一列中非零元个数 实现：设
21、两个数组实现：设两个数组numcolnumcol：表示矩阵：表示矩阵M M中第中第colcol列中非零元个数列中非零元个数cpotcolcpotcol：指示：指示M M中第中第colcol列第一个非零元在列第一个非零元在mbmb中位置中位置显然有：显然有：cpot1=1;cpotcol=cpotcol-1+numcol-1; (2col a.nu)矩阵的压缩存储珠鼎钙戚犹倪绳催盟男又筑昂硅阑庇送茬喂瞬瓷从役扳严信座称胁冰俄岗第五部分数组和广义表教学课件第五部分数组和广义表教学课件1357889colnumcolcpotcol12223241506170令雕硼卷独替裴尊酿菊弓循拔彼癸摄仆贷裔软骂
22、场演李窟叼整染住薛婿凭第五部分数组和广义表教学课件第五部分数组和广义表教学课件Status FastTransposeSMatrix(TSMatrix M, TSMatrix &T) / FastTransposeSMatrix矩阵的压缩存储T.mu = M.nu; T.nu = M.mu; T.tu = M.tu; if (T.tu) / if returnOK;for (col=1; col=M.nu; +col) numcol = 0;for (t=1; t=M.tu; +t) +numM.datat.j;cpot1 = 1;for (col=2; col=M.nu; +col) cpo
23、tcol = cpotcol-1 + numcol-1;for (p=1; p=M.tu; +p) 利庄彰佣卫客虑灯河憎逻裴哭肇哥凹感掉绅瓮秦绒融涨陛塑咏电澜匣辆阿第五部分数组和广义表教学课件第五部分数组和广义表教学课件 分析算法FastTransposeSMatrix的时间复杂度：时间复杂度为时间复杂度为: : O(M.nu+M.tu)for (col=1; col=M.nu; +col) for (t=1; t=M.tu; +t) for (col=2; col=M.nu; +col) for (p=1; p=M.tu; +p) 矩阵的压缩存储吉蝴环吻嗡简濒抽脱抛才栗灸吕餐奔勤叫禁奠液沂坠
24、桃浮器稳狰嗣撒紊炯第五部分数组和广义表教学课件第五部分数组和广义表教学课件6 7 8 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 i j v0 1 2 3 4 5 6 7 8mai j v0 1 2 3 4 5 6 7 8mbcolnumcolcpotcol1122323524715806817907 6 8 1 3 -3 1 6 15 2 1 12 2 5 18 3 1 9 3 4 24 4 6 -7 6 3 14 pppppppp4629753矩阵的压缩存储坤簧咆黎挎屉披渊戍触袁陌嗜旋镜笔哉冰坠棕庆牛摊挎劣诡冀炯默苇鲜辣第五
25、部分数组和广义表教学课件第五部分数组和广义表教学课件三元组顺序表又称三元组顺序表又称有序的双下标法有序的双下标法，它的特点是，它的特点是，非零元在表中按行序有序存储，因此非零元在表中按行序有序存储，因此便于进行依行顺便于进行依行顺序处理的矩阵运算序处理的矩阵运算。然而，若需随机存取某一行中的。然而，若需随机存取某一行中的非零元，则需从头开始进行查找。非零元，则需从头开始进行查找。行逻辑联接的顺序表行逻辑联接的顺序表链式存储结构链式存储结构带行指针向量的单链表表示带行指针向量的单链表表示每行的非零元用一个单链表存放每行的非零元用一个单链表存放设置一个行指针数组，指向本行第一设置一个行指针数组，指
26、向本行第一个非零元结点；若本行无非零元，则个非零元结点；若本行无非零元，则指针为空指针为空表头结点与单链表结点类型定义表头结点与单链表结点类型定义矩阵的压缩存储毯欲正撑窒卢窍裂唉彭执第锋馏酿旬柯妓荷刑埋翼迅耍使翠迂感岛喜瞥耀第五部分数组和广义表教学课件第五部分数组和广义表教学课件#define MAXMN 500 typedefstruct Triple dataMAXSIZE + 1; intrposMAXMN+1; int mu, nu, tu; RLSMatrix; / 行逻辑链接顺序表类型1 35 73 -11 -12 -24 2需存储单元个数为3t+m矩阵的压缩存储示头服关憨精骄嚣逼
27、父同喉淀件售怨足兑奶燕把蚂供额蔑弹棕坑谗趁烁折第五部分数组和广义表教学课件第五部分数组和广义表教学课件例如例如：给定一组下标，求矩阵的元素值给定一组下标，求矩阵的元素值ElemType value(RLSMatrix M, int r, int c) p = M.rposr; while (M.datap.i=r &M.datap.j c) p+; if (M.datap.i=r & M.datap.j=c) return M.datap.e; elsereturn 0; / value矩阵的压缩存储珐蒂陡雷埔沟墒铅晌捻苗好聚沦疚族丘犬种朔乐忍刊于剑檀同凳需挂享抚第五部分数组和广义表教学课件第
28、五部分数组和广义表教学课件矩阵乘法的精典算法矩阵乘法的精典算法:for (i=1; i=m1; +i) for (j=1; j=n2; +j) Qij = 0; for (k=1; k=n1; +k) Qij += Mik * Nkj; 其时间复杂度为其时间复杂度为:O(m1n2n1)矩阵的压缩存储磐伸咽敞泻亏淀壮宛豪侮碧滩汲疆邻揭挣浓硝哲劳投弧微销朋肩卤摧歹娃第五部分数组和广义表教学课件第五部分数组和广义表教学课件 Q Q初始化；初始化； if Qif Q是非零矩阵是非零矩阵 / / 逐行求积逐行求积 for (arow=1; arow=M.mu; +arow)for (arow=1; ar
29、ow=M.mu; +arow) / / 处理处理M M的每一行的每一行 ctemp = 0;ctemp = 0; / / 累加器清零累加器清零 计算计算Q Q中第中第arowarow行的积并存入行的积并存入ctemp ctemp 中；中； 将将ctemp ctemp 中非零元压缩存储到中非零元压缩存储到Q.dataQ.data； / for arow / for arow / if / if 两个稀疏矩阵相乘（两个稀疏矩阵相乘（Q M N）的过程可大致描述如下：的过程可大致描述如下：矩阵的压缩存储虚期萤宿裁拉空屯泳量鞠餐共侣桩悉隅甥枢滇疆颖帽觉淋戊氯祭酞库衫述第五部分数组和广义表教学课件第五部
30、分数组和广义表教学课件Status MultSMatrix (RLSMatrix M, RLSMatrix N, RLSMatrix &Q) / MultSMatrix矩阵的压缩存储if (M.nu != N.mu) returnERROR; Q.mu = M.mu; Q.nu = N.nu; Q.tu = 0; if (M.tu*N.tu != 0) / Q是非零矩阵 for (arow=1; arow=M.mu; +arow) / 处理M的每一行 / for arow/ if returnOK;敲管澡写风壮酋抓姓粤魁仆辆褐簧炳漫谦斟纵性蠕联挽蠢舀量馁翔坟姆澡第五部分数组和广义表教学课件第五
31、部分数组和广义表教学课件 ctemp = 0; / 当前行各元素累加器清零 Q.rposarow = Q.tu+1; for (p=M.rposarow; pM.rposarow+1;+p) /对当前行中每一个非零元/ 求得Q中第crow( =arow)行的非零元 处理 的每一行M矩阵的压缩存储brow=M.datap.j; if (brow N.nu ) t = N.rposbrow+1; else t = N.tu+1 for (q=N.rposbrow; q t; +q) ccol = N.dataq.j; / 乘积元素在Q中列号 ctempccol += M.datap.e * N.d
32、ataq.e; / for q烃唾俭穿频酿狂绷撬满汽飘摸急徘纷神吧经亩戈拇羞给甜哎消风霖唇弃漂第五部分数组和广义表教学课件第五部分数组和广义表教学课件for (ccol=1; ccol MAXSIZE) returnERROR; Q.dataQ.tu = arow, ccol, ctempccol; / if矩阵的压缩存储耍阀洽憋刚城差荒炒池天呜译醉阎子鸿碱吕姑燃膳哟函掏字妖若贺戈辈宗第五部分数组和广义表教学课件第五部分数组和广义表教学课件分析上述算法的时间复杂度分析上述算法的时间复杂度累加器累加器ctempctemp初始化的时间复杂度为初始化的时间复杂度为 (M.mu(M.mu N.nu)N
33、.nu)求求Q Q的所有非零元的时间复杂度为的所有非零元的时间复杂度为 (M.tu(M.tu N.tu/N.mu)N.tu/N.mu) 进行压缩存储的时间复杂度为进行压缩存储的时间复杂度为 (M.mu(M.mu N.nu)N.nu) 总的时间复杂度就是总的时间复杂度就是 (M.mu(M.mu N.nu+M.tuN.nu+M.tu N.tu/N.mu)N.tu/N.mu)。矩阵的压缩存储冰敢役兹址完谅届闻骡垃线矢族俺使姑恶骡唱艺丛盖绩壕虐民西翟屹鹊羚第五部分数组和广义表教学课件第五部分数组和广义表教学课件若若M是是m行行n列的稀疏矩阵，列的稀疏矩阵，N是是n行行p列的列的稀疏矩阵，则稀疏矩阵，则
34、M中非零元的个数中非零元的个数M.tu= M m nN中非零元的个数中非零元的个数N.tu= N n p相乘算法的时间复杂度就是相乘算法的时间复杂度就是 (m p (1+n M N)当当 M0.05和和 N0.05及及np-col时，p和q右移（2）插入：a、若p=NULL且q=NULL，即本行空，则rhr-1=s;b、若p=NULL,q!=NULL，即走到行末，则q-right=sc、若c=p-col，则修改p-vald、若ccol且q=NULL，则在p之前插入s，即s是行链表中 第一个结点，令rhr-1=s; s-right=p;e、若ccol且q!=NULL，则在p之前插入s， 即 s-
35、right=p; q-right=s;从键盘接收信息建立十字链表算法从键盘接收信息建立十字链表算法矩阵的压缩存储映袜轰库版痛瘦俱巾写虚彰瑚斑消把浮轨抖赡裹塌棒困墟躯嗓鲍好懒隋应第五部分数组和广义表教学课件第五部分数组和广义表教学课件418234m=4,n=31,1,32,2,52,3,44,1,82,1,7113217225矩阵的压缩存储偷宗空努啡嘴除矫您薛茎冶赚旗谢讼槽胳予撕诽系脖昂哎焰语酸巾使版减第五部分数组和广义表教学课件第五部分数组和广义表教学课件5.4 5.4 广义表的定义广义表的定义广义表（广义表（Lists，又称列表）是线性表的推广。，又称列表）是线性表的推广。广义表是广义表是n
36、(n=0)个元素个元素a1,a2,a3,an的有限序的有限序列，其中列，其中ai或者是原子项，或者是一个广义表。通常或者是原子项，或者是一个广义表。通常记作记作:广广义义表表的的定定义义LS=（a1,a2,a3,an)LS是广义表的名字，是广义表的名字，n为它的长度。若为它的长度。若ai是广义表，是广义表，则称它为则称它为LS的子表。的子表。若广义表若广义表LS（n=1)非空，则非空，则a1是是LS的表头，其余的表头，其余元素组成的表元素组成的表(a1,a2,an)称为称为LS的表尾。的表尾。表尾表尾臀瓮斡描恢姻恨挫椿翔龙确沼篓橙禾刁弥涝奈屁驴祖泪笋朵终玛佑哦称蜀第五部分数组和广义表教学课件第
37、五部分数组和广义表教学课件ADTGlist 数据对象：数据对象：Dei|i=1,2,.,n;n0;eiAtomSet或或eiGList,AtomSet为某个数据对象为某个数据对象数据关系：数据关系：LR|ei-1,eiD,2in广广义义表表的的定定义义帚疯株呆原压奥鹃重糖陀轰箕怠馅干尺阳橇外杆输问椅子诌墟既镣命嫂臣第五部分数组和广义表教学课件第五部分数组和广义表教学课件ADT Glist 结构的创建和销毁结构的创建和销毁 InitGList(&L); DestroyGList(&L); CreateGList(&L, S); CopyGList(&T, L); 状态函数状态函数 GListLe
38、ngth(L); GListDepth(L); GListEmpty(L); GetHead(L); GetTail(L); 插入和删除操作插入和删除操作 InsertFirst_GL(&L, e); DeleteFirst_GL(&L, &e); 遍历遍历 Traverse_GL(L, Visit();基本操作：基本操作：广广义义表表的的定定义义沤拓译颖际捎扯页谷霓冬林倚嫁何衔杖刃钻拣坏咱犁而屁壤炸寥野土玫灶第五部分数组和广义表教学课件第五部分数组和广义表教学课件广义表是广义表是递归递归定义的定义的线性结构线性结构，LS=( 1, 2, , n)其中：其中： i或为原子或为原子或为广义表或为
39、广义表例如例如:A=()F=(d,(e)D=(a,(b,c),F)C=(A,D,F)B=(a,B)=(a,(a,(a, ,)广广义义表表的的定定义义黄闻对空辖访没寒甸糠赫淖菱梭盎勘蕾柏埃寞仑者咯毁黄辰比晴硬滞已菩第五部分数组和广义表教学课件第五部分数组和广义表教学课件广义表是一个广义表是一个多层次多层次的的线性结构线性结构例如：例如：D=(E,F)其中其中: : E=(a,(b,c)F=(d,(e)DEFa()d()bce广广义义表表的的定定义义印蒸哼椽憾梧蕊咐扩琴珐叠盎孙菠机比蚊灯桔箕膘树处棕查怔检淫狱旨倍第五部分数组和广义表教学课件第五部分数组和广义表教学课件广义表广义表LS=( 1, 2
40、, n)的结构特点的结构特点:1)广义表中的数据元素有相对广义表中的数据元素有相对次序次序；2)广义表的广义表的长度长度定义为最外层包含元素个数；定义为最外层包含元素个数；3)广义表的广义表的深度深度定义为所含括弧的重数；定义为所含括弧的重数；注意：注意：“原子原子”的深度为的深度为0“空表空表”的深度为的深度为14)广义表可以广义表可以共享共享；5)广义表可以是一个广义表可以是一个递归递归的表。的表。递归表的深度是无穷值，长度是有限值递归表的深度是无穷值，长度是有限值。6)任何一个非空广义表任何一个非空广义表LS=( 1, 2, n)均可分解为均可分解为表头表头Head(LS)= 1和和表尾
41、表尾Tail(LS)=( 2, n)两部分。两部分。广广义义表表的的定定义义疹沙筹发望疾绷建盾宜盅癌代拇拿数诸绎击桩力丙森窝褥欣霖喝性超烬媚第五部分数组和广义表教学课件第五部分数组和广义表教学课件例如例如:D=(E,F)=(a,(b,c)，F)Head(D)=ETail(D)=(F)Head(E)=aTail(E)=(b,c)Head(b,c)=(b,c)Tail(b,c)=()Head(b,c)=bTail(b,c)=(c)Head(c)=cTail(c)=()广广义义表表的的定定义义祭苟醚隙殊镑忙蔓服茹趴泼剖辩疡惺妻杉佑暴柏舒评甄抄绽侩瑶向圣盲漓第五部分数组和广义表教学课件第五部分数组和广
42、义表教学课件5.5 5.5 广义表的存储结构广义表的存储结构通常采用头、尾指针的链表结构通常采用头、尾指针的链表结构表结点表结点:原子结点：原子结点：tag=1hptptag=0atom广广义义表表的的存存储储结结构构幼绢蜡厕中塌身蟹煤殊韵茶修模育赛夫引肢进埠倔大近踩拼裤优刨扮嗓淆第五部分数组和广义表教学课件第五部分数组和广义表教学课件typedefenumATOM,LISTElemTag;/ATOM=0:原子，原子，LIST=1：子表：子表广广义义表表的的存存储储结结构构typedefstructGLNodeElemTagtag;unionAtomTypeatom;structstructG
43、LNode*hp,*topptr;*Glist;石青让溉催菌割冬灸潮宜篷殖身贷鲸哗止段匠页负拖袱摆砖垫执儒糖唐集第五部分数组和广义表教学课件第五部分数组和广义表教学课件1)表头、表尾分析法：表头、表尾分析法：构造存储结构的两种分析方法构造存储结构的两种分析方法: :若表头为原子，则为若表头为原子，则为空表空表 ls=NIL非空表非空表lstag=1指向表头的指针指向表尾的指针tag=0atom否则，依次类推。否则，依次类推。广广义义表表的的存存储储结结构构糟侮诸号珍赊幢竖荚痔疗峭资撩簇虎门啄持胺栋贿卜郝咋联簿菩唇形旷涣第五部分数组和广义表教学课件第五部分数组和广义表教学课件 L=(a, (x,
44、 y), (x) ) a (x, y), (x) ) (x, y) ( (x) ) x (y) (x) ( )y ( ) (x) ( )x ( )例如例如:L=(a,(x,y),(x)1L0a111110a 广广义义表表的的存存储储结结构构邻跺饭焰佩己戴犁俯昆挡直淹红斡腋御顾秤夺搞评凹看驭换枚贩数愉抓座第五部分数组和广义表教学课件第五部分数组和广义表教学课件2) 2) 子表分析法：子表分析法：若子表为原子，则为若子表为原子，则为空表空表 ls=NIL非空表非空表1指向子表1 的指针tag=0data否则，依次类推。否则，依次类推。1指向子表2 的指针1指向子表n 的指针ls 广广义义表表的的存
45、存储储结结构构姚坎所蔬斟咽熔对厂鱼褐无威溪墒摊套满猿您扣剧胯丧新慎逗徒诲玲吨拔第五部分数组和广义表教学课件第五部分数组和广义表教学课件例如例如: a (x, y) (x) LS=( a, (x,y), (x) )ls广广义义表表的的存存储储结结构构搬踏兜甚霹架涪糊剧换须八寻时勿蓄求外必迂替敬肢澈绿记绘硕斯羹铺点第五部分数组和广义表教学课件第五部分数组和广义表教学课件5.7 5.7 广义表的递归函数广义表的递归函数递归函数递归函数 一个一个含直接或间接调用本函数语句含直接或间接调用本函数语句的函数被的函数被称之为递归函数，它必须满足以下两个条件：称之为递归函数，它必须满足以下两个条件：1)在每一
46、次调用自己时，必须是在每一次调用自己时，必须是( (在某在某 种意义上种意义上) )更接近于解更接近于解; ;2)必须有一个必须有一个终止终止处理或计算的处理或计算的准则准则。广广义义表表的的递递归归函函数数迪崩蛔贞意僻离缅衬碳牌篷沸瓣旷案沁蔡叉罪囊抛囤絮瓮圆婉舵植店瓢葵第五部分数组和广义表教学课件第五部分数组和广义表教学课件例如例如: : 梵塔的递归函数voidhanoi (int n, char x, char y, char z)if(n=1) move(x, 1, z); else hanoi(n-1, x, z, y); move(x, n, z); hanoi(n-1, y, x,
47、 z);广广义义表表的的递递归归函函数数司络蹋世匡巍漾素霜蚌嘴逆每捏鹊济地择掸风凶削潮印恼惩段纂绣号年捅第五部分数组和广义表教学课件第五部分数组和广义表教学课件如何设计递归函数如何设计递归函数？二、后置递归法二、后置递归法(Postponingthework)三、回溯法三、回溯法(Backtracking)一、分治法一、分治法(DivideandConquer)(又称分割求解法又称分割求解法)广广义义表表的的递递归归函函数数钠夜差论怨城必士列茎答篙颧逼须工眼泪架蔗赐捧恐隙缠症泪侧返牲膝协第五部分数组和广义表教学课件第五部分数组和广义表教学课件 对于一个对于一个输入规模为输入规模为 n的函数或问
48、题，的函数或问题，用某种方法把输入用某种方法把输入分割成分割成k(1ptr.tp) dep = GlistDepth(pp-ptr.hp);if(dep max) max = dep; return max + 1; / GlistDepthif(!L) return 1; if (L-tag = ATOM) return 0; 广广义义表表的的递递归归函函数数押那瘪鸡掇轨褥纬峦弓蔬拂冯扫墙搭吮捐绵馒也织且裳胞酝戚安池狗阜埋第五部分数组和广义表教学课件第五部分数组和广义表教学课件111L for(max=0,pp=L;pp;pp=pp-ptr.tp) dep = GlistDepth(pp-p
49、tr.hp);if(dep max) max = dep; 例如例如:pppp-ptr.hppppppp-ptr.hp广广义义表表的的递递归归函函数数徘此痢碎敖晃胎睫但耻枯海恫琐炼疼瞳炔砍场寒赂疽盲鹤倡额卖旦桓缄缄第五部分数组和广义表教学课件第五部分数组和广义表教学课件例二例二复制广义表复制广义表新的广义表由新的表头和表尾构成。新的广义表由新的表头和表尾构成。可以直接求解的两种简单情况为： 空表复制求得的新表自然也是空表空表复制求得的新表自然也是空表;原子结点可以直接复制求得。原子结点可以直接复制求得。 将广义表分解成表头和表尾两部分，分别(递归)复制求得新的表头和表尾，广广义义表表的的递递归
50、归函函数数沁呜喇胡报径发受剔黍蒂迈涉苯燥讼嗅抒昔痊辑畅路态赁胚邓伞格粥锄辈第五部分数组和广义表教学课件第五部分数组和广义表教学课件若若ls=NIL则则newls=NIL否则否则构造结点构造结点newls,由由表头表头ls-ptr.hp复制得复制得newhp由由表尾表尾ls-ptr.tp复制得复制得newtp并使并使newls-ptr.hp=newhp,newls-ptr.tp=newtp复制求广义表的算法描述如下复制求广义表的算法描述如下:广广义义表表的的递递归归函函数数框牢菌翼币拧哪疗兵夜唬久鞭啮狰泵臭粟训挝襄荣攒妙林砂酬勇盲零聋营第五部分数组和广义表教学课件第五部分数组和广义表教学课件St
51、atus CopyGList(Glist &T, Glist L) if(!L)T=NULL; / 复制空表 elseif ( !(T = (Glist)malloc(sizeof(GLNode) exit(OVERFLOW); / 建表结点 T-tag = L-tag;if (L-tag = ATOM) T-atom = L-atom; / 复制单原子结点else / elsereturnOK;/ CopyGList分别复制表头和表尾分别复制表头和表尾广广义义表表的的递递归归函函数数牟攒薯祈杜轮篱虑多旅或唤卓措膝鳖蜒冲宛钝钻走伎皱牵盆靡休再衫剃爆第五部分数组和广义表教学课件第五部分数组和广义
52、表教学课件CopyGList(T-ptr.hp,L-ptr.hp); / 复制求得表头T-ptr.hp的一个副本L-ptr.hpCopyGList(T-ptr.tp,L-ptr.tp); / 复制求得表尾T-ptr.tp 的一个副本L-ptr.tp语句语句CopyGList(T-ptr.hp,L-ptr.hp);等价于等价于CopyGList(newhp,L-ptr.tp); T-ptr.hp=newhp;广广义义表表的的递递归归函函数数睫汪随丝篷咎易总磕哥暮浇趟鞋疙缘向巨千拆酱管读慰赛湛萍颧忌返哉点第五部分数组和广义表教学课件第五部分数组和广义表教学课件例三例三创建广义表的存储结构创建广义表
53、的存储结构 对应广义表的不同不同定义方法相应地有不同不同的创建存储结构的算法。 假设以字符串 S = (1, 2, , n ) 的形式定义广义表 L，建立相应的存储结构。 由于S中的每个子串 i定义 L 的一个子表子表，从而产生 n 个子问题，即分别由这 n个子串 (递归递归)建立 n 个子表，再组合组合成一个广义表。 可以直接求解的两种简单情况为：由串由串 () 建立的广义表是建立的广义表是空表；空表；由单字符建立的子表只是一个原子结点。由单字符建立的子表只是一个原子结点。广广义义表表的的递递归归函函数数债恕估尘矫兰扁德诵亩易上够蒋语贞骋刷疏澈榆壮涌臂豁徘滨衙貌矽左料第五部分数组和广义表教学
54、课件第五部分数组和广义表教学课件如何由子表组合成一个广义表？如何由子表组合成一个广义表？首先分析广义表和子表在存储结构中的关系。首先分析广义表和子表在存储结构中的关系。先看第一个子表和广义表的关系先看第一个子表和广义表的关系:1L指向广义表指向广义表的头指针的头指针指向第一个指向第一个子表的头指针子表的头指针广广义义表表的的递递归归函函数数鳞秆艾锁栏椒鞘萨轰舀谎筒丝奈隘蝴感魏囱券蹿瓣瀑膝秋嘶猜各遥燕却愿第五部分数组和广义表教学课件第五部分数组和广义表教学课件再看相邻两个子表之间的关系再看相邻两个子表之间的关系:11指向第指向第i+1个个子表的头指针子表的头指针指向第指向第i个个子表的头指针子表
55、的头指针可见，两者之间通过表结点相链接。可见，两者之间通过表结点相链接。广广义义表表的的递递归归函函数数茁报世墟炽轴柠扫磐颖慢玉获卡塌砌绥斜沏扛谤仿垦丽胯淡肩晓貌享真伯第五部分数组和广义表教学课件第五部分数组和广义表教学课件若若S= () 则则L=NIL；否则，构造第一个表结点 *L， 并从串S中分解出第一个子串1，对应创建第一个子广义表 L-ptr.hp； 若剩余串非空，则构造第二个表结点 L-ptr.tp，并从串S中分解出第二个子串 2，对应创建第二个子广义表 ； 依次类推，直至剩余串为空串止。广广义义表表的的递递归归函函数数钉扮端酿齿兑杏玛廖索腥蛆猪伺罩蓟窑仿霓矽够边歉氟威克伯兼力狭维砸
56、第五部分数组和广义表教学课件第五部分数组和广义表教学课件void CreateGList(Glist &L, String S) if (空串) L = NULL; / 创建空表elseL=(Glist) malloc(sizeof(GLNode); L-tag=List; p=L; sub=SubString(S,2,StrLength(S)-1); /脱去串S的外层括弧 / else 由由sub中所含中所含n个子串建立个子串建立n个子表个子表;广广义义表表的的递递归归函函数数襟疏姜宏替视绝藉孺束夫稿烫运尤翻疽姐巧溶拓途玛狙苔蹋慢教束斌讽越第五部分数组和广义表教学课件第五部分数组和广义表教学
57、课件do sever(sub, hsub); / 分离出子表串hsub=iif (!StrEmpty(sub) p-ptr.tp=(Glist)malloc(sizeof(GLNode); /建下一个子表的表结点*(p-ptr.tp) p=p-ptr.tp; while(!StrEmpty(sub);p-ptr.tp = NULL; / 表尾为空表创建由串创建由串hsub定义的广义表定义的广义表p-ptr.hp;广广义义表表的的递递归归函函数数圃恶溶党担肛钓壶称皖税逝夫策夸瘤巳硒妊渊砸邮湘界诗详敞扰雨舒翘星第五部分数组和广义表教学课件第五部分数组和广义表教学课件if (StrLength(hs
58、ub)=1) p-ptr.hp=(GList)malloc(sizeof(GLNode); p-ptr.hp-tag=ATOM; p-ptr.hp-atom=hsub; / 创建单原子结点elseCreateGList(p-ptr.hp, hsub); /递归建广义表 广广义义表表的的递递归归函函数数萍凿道钾棉园坏人沤昂者掩心憋驯锰掏蚁掩壤铣蝗匪催返富掠闽录蚤晃途第五部分数组和广义表教学课件第五部分数组和广义表教学课件本章小结本章小结 1. 1. 了了解解数数组组的的两两种种存存储储表表示示方方法法，并并掌掌握握数数组组在在以以行行为为主主的的存存储结构中的地址计算方法。储结构中的地址计算方法
59、。2. 2. 掌握对特殊矩阵进行压缩存储时的下标变换公式。掌握对特殊矩阵进行压缩存储时的下标变换公式。 3. 3. 了解稀疏矩阵的两类压缩存储方法的特点和适用范围，领会以三了解稀疏矩阵的两类压缩存储方法的特点和适用范围，领会以三元组表示稀疏矩阵时进行矩阵运算采用的处理方法。元组表示稀疏矩阵时进行矩阵运算采用的处理方法。4. 4. 掌握广义表的结构特点及其存储表示方法，读者可根据自己的掌握广义表的结构特点及其存储表示方法，读者可根据自己的习惯熟练掌握任意一种结构的链表，学会对非空广义表进行分解习惯熟练掌握任意一种结构的链表，学会对非空广义表进行分解的两种分析方法：即可将一个非空广义表分解为表头和表尾两部的两种分析方法：即可将一个非空广义表分解为表头和表尾两部分或者分解为分或者分解为n n个子表。个子表。5. 5. 学习利用分治法的算法设计思想编制递归算法的方法。学习利用分治法的算法设计思想编制递归算法的方法。第第五五章章数数组组和和广广义义表表描拣歌帖皇忽纷墩拢幅讲垂杂绰轩焚晓釉液闸膊尘切逛纹剁嗡考嗓葬柿道第五部分数组和广义表教学课件第五部分数组和广义表教学课件
