第五讲数组和广义表

《第五讲数组和广义表》由会员分享，可在线阅读，更多相关《第五讲数组和广义表（111页珍藏版）》请在金锄头文库上搜索。

1、第五章第五章 数组和广义表数组和广义表 数组和广义表可看成是一种特殊的线数组和广义表可看成是一种特殊的线性表，其特殊在于性表，其特殊在于:表中的数据元素本表中的数据元素本身也是一种线性表身也是一种线性表饮夹饿富寐吉糠糖逞卜闹埂兵弦护郴做锦香嘶滞工算徊睁伤颜杉徒露脆咨第五讲数组和广义表第五讲数组和广义表 5.1 数组的定义 数组是我们最熟悉的数据类型，在早期的高级语言中，数组是唯一可供使用的数据类型。由于数组中各元素具有统一的类型，并且数组元素的下标一般具有固定的上界和下界，因此，数组的处理比其它复杂的结构更为简单。多维数组是向量的推广。例如，二维数组： a11 a12 a1n a21 a22

2、a2n am1 am2 amn Amn=海成灶膳验护匠祭少悄枯率饯锻固逗藐线锐猾还去贺忠撰茄弛糙七大莎得第五讲数组和广义表第五讲数组和广义表 可以看成是可以看成是m m由个行向量组成的向量，也由个行向量组成的向量，也可以看成是可以看成是n n个列向量组成的向量。个列向量组成的向量。 数组一旦被定义，它的维数和维界就数组一旦被定义，它的维数和维界就不再改变。因此，除了结构的初始化和不再改变。因此，除了结构的初始化和销毁之外，数组只有存取元素和修改元销毁之外，数组只有存取元素和修改元素值的操作素值的操作。取普垒完纪超扒舵齿矛逸敷瘫躇推颅垂凉逼戳快汾涅前媚稀盛名厌逊齐摈第五讲数组和广义表第五讲数组和

3、广义表 5.2 数组的顺序表示和实现 由于计算机的内存储结构是一维的，因此用一维内存来表示多维数组，就必须按某种次序将数组元素排成一列序列，然后将这个线性序列存放在存储器中。 又由于对数组一般不做插入和删除操作，也就是说，数组一旦建立，结构中的元素个数和元素间的关系就不再发生变化。因此，一般都是采用顺序存储的方法来表示数组。 胞拌瞩提女艇林娟区聊忍陋挝亮乞县位仍疹肛湿乱簧墓涧受竭荚孽拔旅颠第五讲数组和广义表第五讲数组和广义表5.1 数组的类型定义数组的类型定义5.3 稀疏矩阵的压缩存储稀疏矩阵的压缩存储 5.2 数组的顺序表示和实现数组的顺序表示和实现5.4 广义表的类型定义广义表的类型定义5

4、.5 广义表的表示方法广义表的表示方法5.6 广义表操作的递归函数广义表操作的递归函数井及猪宴恬绦佐欣直拔赴躬枝堡袖唇蛛懂盗谎个韵猪普赤募睫虏映个雾铡第五讲数组和广义表第五讲数组和广义表5.1 数组的类型定义数组的类型定义ADT Array 数据对象数据对象： Daj1,j2, .,ji,jn| ji =0,.,bi -1, i=1,2,.,n 数据关系数据关系： RR1, R2, ., Rn Ri | 0 jk bk -1, 1 k n 且k i, 0 ji bi -2, i=2,.,n ADT Array 基本操作基本操作:推糯梧岗有杭虹弹奈债凤挚烬锅蹬吻瞩握涣锨脉鲤堪债宝阑译絮恋谊梁孪第

5、五讲数组和广义表第五讲数组和广义表二维数组的定义二维数组的定义:数据对象数据对象: : D = aij | 0ib1-1, 0 jb2-1数据关系数据关系: : R = ROW, COL ROW = | 0ib1-2, 0jb2-1 COL = | 0ib1-1, 0 jb2-2宛悸渍盈嗽思莲瞻豹萤姿撇瞅揣芒撞瘤秤炎端贩蔷囱驴汇涂颗暮画含庙肃第五讲数组和广义表第五讲数组和广义表基本操作基本操作：InitArray(&A, n, bound1, ., boundn)DestroyArray(&A)Value(A, &e, index1, ., indexn)Assign(&A, e, index

6、1, ., indexn)莆已捌纪丈枣臃沧离祥惠膝李广激置器诬竖俭抗葵妈喀侧提宾亏遂闯囤饿第五讲数组和广义表第五讲数组和广义表 InitArray(&A, n, bound1, ., boundn) 操作结果：操作结果：若维数 n 和各维长度合法， 则构造相应的数组A，并 返回OK。掠符檬运悯竣猴禽帘奢蓟睫蓬镇血惕赐镍巧欺魏脯哪署柑锡盅潜敢赁忙饶第五讲数组和广义表第五讲数组和广义表 DestroyArray(&A) 操作结果：操作结果：销毁数组A。奋噪驾病龋谣车弹丢膳芥腺永挺昨淬薯蒸买抛黎窥捎除考闷赖笔呀札轧搬第五讲数组和广义表第五讲数组和广义表 Value(A, &e, index1, .,

7、 indexn) 初始条件：初始条件：A是n维数组，e为元素变量， 随后是n 个下标值。 操作结果：操作结果：若各下标不超界，则e赋值为 所指定的A 的元素值，并返 回OK。园抗还私痞子攫至虹蒜龄皇涡卑钟势吾蓖殿态缺崖雇猖街桶季翰淫瞄秆剑第五讲数组和广义表第五讲数组和广义表 Assign(&A, e, index1, ., indexn) 初始条件：初始条件：A是n维数组，e为元素变量， 随后是n 个下标值。 操作结果：操作结果：若下标不超界，则将e的值赋 给所指定的A的元素，并返回 OK。雷朽邢飞闭掣御附力雅邢成琉却靳冤鸯州逝佛拷佃羹槛筒蒋他个呐国育唱第五讲数组和广义表第五讲数组和广义表5.

8、2 数组的顺序表示和实现数组的顺序表示和实现 类型特点类型特点:1) 只有引用型操作，没有加工型操作；2) 数组是多维的结构，而存储空间是 一个一维的结构。 有两种顺序映象的方式有两种顺序映象的方式:1)以行序为主序(低下标优先)；2)以列序为主序(高下标优先)。伞括子圣尹靶究甘裴庐辱框钎倒捣制福吹贫瞻呕讳咒挪缝来涅皿日鸣琅在第五讲数组和广义表第五讲数组和广义表例如：例如： 称为基地址基地址或基址。以以“行序为主序行序为主序”的存储映象的存储映象二维数组A中任一元素ai,j 的存储位置 LOC(i,j) = LOC(0,0) + (b2ij)a0,1a0,0a0,2a1,0a1,1a1,2a0

9、,1a0,0a0,2a1,0a1,1a1,2L L 摆焕庚揖徒瓤箩则柠沉谚雍欧娶妄童苦肆脸撞诈麓奖厉受了颊瞎廷宣攫氰第五讲数组和广义表第五讲数组和广义表推广到一般情况，可得到 n 维数组数据元素存储位置的映象关系 称为 n 维数组的映象函数。数组元素数组元素的存储位置是其下标的线性函数。的存储位置是其下标的线性函数。其中 cn = L，ci-1 = bi ci , 1 i n。LOC(j1, j2, ., jn ) = LOC(0,0,.,0) + ci ji i=1n铺针滓两尊犁监章雁惊萍杨邮热竣雪拟审冠诈翻虑丹枝菜颠梦腹全釉闸渣第五讲数组和广义表第五讲数组和广义表假设 m 行 n 列的矩阵

10、含 t 个非零元素，则称 为稀疏因子稀疏因子。通常认为通常认为 0.05 的矩阵为稀疏矩阵。的矩阵为稀疏矩阵。5.3 稀疏矩阵的压缩存储稀疏矩阵的压缩存储何谓稀疏矩阵？部官抱吹魏匀咽笋弥均影龋媚含膛恫赶筋下薄谨哟请帘沥材庶初痰摧玄门第五讲数组和广义表第五讲数组和广义表 以常规方法，即以二维数组表示高阶的稀疏矩阵时产生的问题问题:1) 零值元素占了很大空间零值元素占了很大空间;2) 计算中进行了很多和零值的运算，计算中进行了很多和零值的运算， 遇除法，还需判别除数是否为零遇除法，还需判别除数是否为零。翠防绸箔帕曲号菱诈肃疥鸥渴醋鼓咐佬绸仟匙主丫慨煽吻蹄碱怖幅辙臀盈第五讲数组和广义表第五讲数组和广

11、义表1) 尽可能少存或不存零值元素；解决问题的原则解决问题的原则:2) 尽可能减少没有实际意义的运算；3) 操作方便。 即： 能尽可能快地找到与 下标值(i，j)对应的元素， 能尽可能快地找到同 一行或同一列的非零值元。倒盆回仇矮糖盏夜嘘蓄讼辟妈兽度盐编东闰辈捡顺摧奎侧邀师棉锅家允守第五讲数组和广义表第五讲数组和广义表1) 特殊矩阵特殊矩阵 非零元在矩阵中的分布有一定规则 例如: 三角矩阵 对角矩阵2) 随机稀疏矩阵随机稀疏矩阵 非零元在矩阵中随机出现有两类稀疏矩阵有两类稀疏矩阵：坏抗茬生诬念项庙库窍球悬感俞葡候藩怎含钥滨袱呸移料兜也叭壳苍饮扛第五讲数组和广义表第五讲数组和广义表5.3.1特殊

12、矩阵 所谓特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵，下面我们讨论几种特殊矩阵的压缩存储。1、对称矩阵 在一个n阶方阵A中，若元素满足下述性质： aij=aji 0i,jn-1则称A为对称矩阵。如图5.1便是一个5阶对称矩阵。 对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三角或下三角中的元素，让每两个对称的元素共享一个存储空间，这样，能节约近一半的存储空间。不失一般性，我们按“行优先据摄载鸥瞎箩申涝晌功渐啊承抿裁娄柠述隘灭瞩临汤污孜耘汤钥绍惹翅非第五讲数组和广义表第五讲数组和广义表顺序”存储主对角线（包括对角线）以下的元素，其存储形式如图所示： 1 5 1 3 7 a00 5

13、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 图 5.1 对称矩阵 在这个下三角矩阵中，第i行恰有i+1个元素，元素总数为： n(n+1)/2 因此，我们可以按图中箭头所指的次序将这些元素存放在一个向量sa0.n(n+1)/2-1中。为了便于访问对称矩阵A中的元素，我们必须在aij和sak 衅丰囱畔啄词绕荤腕釉搂奖猜号农秃蹋峡胆耐着烤固潭津实休真病社巩瞩第五讲数组和广义表第五讲数组和广义表之间找一个对应关系。 若ij，则ai j在下三角形中。 ai j之

14、前的i行（从第0行到第i-1行）一共有1+2+i=i(i+1)/2个元素，在第i行上， ai j之前恰有j个元素（即ai0,ai1,ai2,aij-1），因此有： k=i*(i+1)/2+j 0kn(n+1)/2 若ij，则aij是在上三角矩阵中。因为aij=aji，所以只要交换上述对应关系式中的i和j即可得到： k=j*(j+1)/2+i 0 kn(n+1)/2 令 I=max(i,j)， J=min(i,j)，则k和 i, j的对应关系可统一为： k=I*(I+1)/2+J 0 kn(n+1)/2 曙椭塞绒厩痞耍兆嗓边酪搂肠寒凌癸料逝彤膳孩移掺菠拨创醇铆巨迷烫岗第五讲数组和广义表第五讲数组

15、和广义表因此，aij的地址可用下列式计算： LOC(aij)=LOC(sak) =LOC(sa0)+k*d=LOC(sa0+I*(I+1)/2+J*d 有了上述的下标交换关系，对于任意给定一组下标(i，j)，均可在sak中找到矩阵元素aij，反之，对所有的k=0,1,2,n(n-1)/2-1，都能确定sak中的元素在矩阵中的位置(i,j)。由此，称san(n+1)/2为阶对称矩阵A的压缩存储，见下图：k=0 1 2 3 n(n-1)/2 n(n+1)/2-1例如a21和a12均存储在 sa4中，这是因为 k=I*(I+1)/2+J=2*(2+1)/2+1=4a00a10a11a20an-1 0

16、 an-1,n-1峰炔菊严垒壳帅撞椎撑桑坍坝皑狮遂戏噶后市港咸渊陆始仆匡织疤奉砰牙第五讲数组和广义表第五讲数组和广义表2、三角矩阵 以主对角线划分，三角矩阵有上三角和下三角两种。上三角矩阵如图所示，它的下三角（不包括主对角线）中的元素均为常数。下三角矩阵正好相反，它的主对角线上方均为常数，如图所示。在大多数情况下，三角矩阵常数为零。 a00 a01 a 0 n-1 a00 c c c a11 a 1 n-1 a10 a11 c . . c c a n-1 n-1 an-1 0 an-1 1 an-1 n-1 (a)上三角矩阵 (b)下三角矩阵 图5.2 三角矩阵重仁肄垣浦发构锅充缆牡利害届甜稚

17、纤木垄痢舅灶竖枣父皖疚戌遁峨棘楞第五讲数组和广义表第五讲数组和广义表 三角矩阵中的重复元素c可共享一个存储空间，其余的元素正好有n(n+1)/2个，因此，三角矩阵可压缩存储到向量sa0.n(n+1)/2中，其中c存放在向量的最后一个分量中， 上三角矩阵中，主对角线之上的第p行(0pjk=晴龟硒搂喝爪毁季地翘钞臣社殿艳烁贝辊汰缀厢气描轮今叔霹人戍怠宪岗第五讲数组和广义表第五讲数组和广义表 下三角矩阵的存储和对称矩阵类似，sak和aij对应关系是： i(i+1)/2+j ij n(n+1)/2 ij 3、对角矩阵 对角矩阵中，所有的非零元素集中在以主对角线为了中心的带状区域中，即除了主对角线和主对

18、角线相邻两侧的若干条对角线上的元素之外，其余元素皆为零。下图给出了一个三对角矩阵， a00 a01 a10 a11 a12 a21 a22 a23 . . . 图5.3 对角矩阵 an-2 n-3 an-2 n-2 an-2 n-1 an-1 n-2 an-1 n-1k=玩癌壳取燃是钱畜甲宁柞酞顷硅坐寞蛮风吐拂罐捣捍已岛坛捣入蚌馁娥佰第五讲数组和广义表第五讲数组和广义表非零元素仅出现在主对角(aii,0in-1上，紧邻主对角线上面的那条对角线上(aii+1,0in-2)和紧邻主对角线下面的那条对角线上(ai+1 i,0in-2)。显然，当i-j1时，元素aij=0。由此可知，一个k对角矩阵(k

19、为奇数)A是满足下述条件的矩阵：若i-j(k-1)/2 ，则元素 aij=0。 对角矩阵可按行优先顺序或对角线的顺序，将其压缩存储到一个向量中，并且也能找到每个非零元素和向量下标的对应关系。 涎州枝爹孔土形雅凿蠕唤暗记皖邑颓尚妈勾譬电性煤钟倡怂讣轿面皆季踌第五讲数组和广义表第五讲数组和广义表 在三对角矩阵里附满足条件i=0，j=0、1，或i=n-1j=n-2、n-1或1in-1,j=i-1、i、i+1的元素aij外，其余元素都是零。 对这种矩阵，我们也可按行优序为主序来存储。除第0行和第n-1行是2个元素外，每行的非零元素都要是3个，因此，需存储的元素个数为3n-2。a00a01 a10a11

20、a12a21 a n-1 n-2a n-1 n-1K=0 1 2 3 4 5 3n-2 3n-1 数组sa中的元素sak与三对角带状矩阵中的元素aij存在一一对应关系，在aij之前有i行,共有3*i-1个非零元素，在第i行，有j-i+1个非零元素，这样，非零元素aij的地址为： 牙炭报点队且猛庭敛玩约妨饵貉樱雾省摊戚摹贮坚填注盎喘屏釉堵鼎熊鞋第五讲数组和广义表第五讲数组和广义表 LOC(i,j)=LOC(0,0)+3*i-1+(j-i+1)*d =LOC(0,0)+(2i+j)*d 上例中，a34对应着sa10。 k=2*i+j=2*3+4=10 a21对应着sa5 k=2*2+1=5由此，我

21、们称sa0.3*n-2是阶三对角带状矩阵A的压缩存储表示。伍椅巫秒隋矽淄衫锥内攒咕窗暗盟妨侗赠窒荷暇吗曲妻田持创府庞举枪级第五讲数组和广义表第五讲数组和广义表上述的各种特殊矩阵，其非零元素的分布都是有规律的，因此总能找到一种方法将它们压缩存储到一个向量中，并且一般都能找到矩阵中的元素与该向量的对应关系，通过这个关系，仍能对矩阵的元素进行随机存取。 5.3.2 稀疏矩阵。派享倾疚专匈镀桶攘幂聚根珠廊递延椎集舵并沦扦磊脂写岸梧姻葛翼机玖第五讲数组和广义表第五讲数组和广义表随机稀疏矩阵的压缩存储方法随机稀疏矩阵的压缩存储方法:一、三元组顺序表一、三元组顺序表二、行逻辑联接的顺序表二、行逻辑联接的顺序

22、表三、三、 十字链表十字链表购腮匙醉晃烽北怕谢萨邵慰酒湛庸绦狗鞋埃钡府占茅遥枷阿饺粟暮氢蛇郑第五讲数组和广义表第五讲数组和广义表 #define MAXSIZE 12500 typedef struct int i, j; /该非零元的行下标和列下标 ElemType e; / 该非零元的值 Triple; / 三元组类型三元组类型一、三元组顺序表一、三元组顺序表typedef union Triple dataMAXSIZE + 1; int mu, nu, tu; TSMatrix; / 稀疏矩阵类型稀疏矩阵类型梧彭厩疥浩滔释押坯捌广额懦孺量怯拂彭匹属抖矽坛栅辆朵芍膝你槐馅进第五讲数组和广

23、义表第五讲数组和广义表如何求转置矩阵？如何求转置矩阵？胁肩栅涛涵耿侄蠢鹤辑厄于滴获蜗吃燥笛硬称柔卵借郴蛆远汲矽汇人宛惕第五讲数组和广义表第五讲数组和广义表用常规的二维数组表示时的算法 其时间复杂度为其时间复杂度为: O(munu) for (col=1; col=nu; +col) for (row=1; row=mu; +row) Tcolrow = Mrowcol;扁船迟搂闽磐滥荒竣伙球广膊赴戚疏走密庶俘蔑推式坯练蹭企钒虑馋考妙第五讲数组和广义表第五讲数组和广义表用“三元组”表示时如何实现？1 2 141 5 -52 2 -73 1 363 4 282 1 145 1 -52 2 -71

24、3 364 3 28归免虞倘鸭芥答辫山屠蛆藩慕贩曰浅谨吊叙半妮雍攀糙考酣瓢菇瞧坟挛脑第五讲数组和广义表第五讲数组和广义表 首先应该确定每一行的第一个非零元在三元组中的位置。 cpot1 = 1; for (col=2; col=M.nu; +col) cpotcol = cpotcol-1 + numcol-1;睡莱谁朱基样馋僻褐亿耙杀损记噬剑道桥别苑教馅浇惯勋锦弱疟牡酿性雕第五讲数组和广义表第五讲数组和广义表Status FastTransposeSMatrix(TSMatrix M, TSMatrix &T) T.mu = M.nu; T.nu = M.mu; T.tu = M.tu; i

25、f (T.tu) 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) cpotcol = cpotcol-1 + numcol-1; for (p=1; p=M.tu; +p) / if return OK; / FastTransposeSMatrix 转置矩阵元素褥绣奖鼻邵辉停涯绒普成蓝锨宇涧岭践仔醚睫橱哈三镣井拱重伪孔征淮匙第五讲数组和广义表第五讲数组和广义表Col = M.datap.j;q = cpotco

26、l;T.dataq.i = M.datap.j;T.dataq.j = M.datap.i;T.dataq.e = M.datap.e;+cpotcol肺闺本萤槛帽非软制帘压墟讽吊乔掘堰檄无力函薛簇作脂瞩熙网氏鹊丁明第五讲数组和广义表第五讲数组和广义表 分析算法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) 期窖任簿峙锗凌韶邪仗撂殆则鹿

27、倍痈树南和疚草漳爪啮尧俊玻漏呐晴半哄第五讲数组和广义表第五讲数组和广义表 三元组顺序表又称有序的双下标有序的双下标法法，它的特点是，非零元在表中按行序有序存储，因此便于进行依行顺序便于进行依行顺序处理的矩阵运算处理的矩阵运算。然而，若需随机存取某一行中的非零元，则需从头开始进行查找。二、行逻辑联接的顺序表二、行逻辑联接的顺序表泥靶含搅惺快腻竹菊浚洋粉燎最于禄镜壹炳涉衰杠舌脐铃刻栏盂钠拆低鲁第五讲数组和广义表第五讲数组和广义表 #define MAXMN 500 typedef struct Triple dataMAXSIZE + 1; int rposMAXMN + 1; int mu, n

28、u, tu; RLSMatrix; / 行逻辑链接顺序表类型 修改前述的稀疏矩阵的结构定义，增加一个数据成员rpos，其值在稀疏矩阵的初始化函数中确定。撰两疫新暂诫试族训怜浮蝇礁陷侦却洽裳购澡预歧萤助兰镑苯坐菇众冶联第五讲数组和广义表第五讲数组和广义表例如：给定一组下标，求矩阵的元素值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; else return 0; /

29、 value碑皋酝胖会贡连父伙管镶坊边壶季隅人惕医缠问闪察努充迹针剂著确纲狐第五讲数组和广义表第五讲数组和广义表矩阵乘法的精典算法矩阵乘法的精典算法: 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初始化； if Q是非零矩阵 / 逐行求积 for (arow=1; arow=M.mu; +arow) / 处理M的每

30、一行 ctemp = 0; / 累加器清零 计算Q中第arow行的积并存入ctemp 中； 将ctemp 中非零元压缩存储到Q.data； / for arow / if 两个稀疏矩阵相乘（两个稀疏矩阵相乘（Q M N） 的过程可大致描述如下：的过程可大致描述如下：其非慧白炼灌券圆赤富锑牢僳犹酸瞩昂吵悟勋恳纫两家疫政梗乎尖娃淘予第五讲数组和广义表第五讲数组和广义表 Status MultSMatrix (RLSMatrix M, RLSMatrix N, RLSMatrix &Q) if (M.nu != N.mu) return ERROR; Q.mu = M.mu; Q.nu = N.nu

31、; Q.tu = 0; if (M.tu*N.tu != 0) / Q是非零矩阵 for (arow=1; arow=M.mu; +arow) / 处理M的每一行 / for arow / if return OK; / MultSMatrix毫世炽蓝歇员掺蹦济龋望数安缨党匡沈邯牲炉光董椽讶事韭振敖梳紧辛窜第五讲数组和广义表第五讲数组和广义表 ctemp = 0; / 当前行各元素累加器清零 Q.rposarow = Q.tu+1; for (p=M.rposarow; pM.rposarow+1;+p) /对当前行中每一个非零元 brow=M.datap.j; if (brow N.nu )

32、 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.dataq.e; / for q / 求得Q中第crow( =arow)行的非零元 for (ccol=1; ccol MAXSIZE) return ERROR; Q.dataQ.tu = arow, ccol, ctempccol; / if处理 的每一行M抬挪声涂允膝弦姻酵黎绚雨淫龙烧锦怯捆妻香龋料产漠腥评岳相舵结碾寺第五讲数组和广义表第五讲数组和广义

33、表分析上述算法的时间复杂度分析上述算法的时间复杂度累加器ctemp初始化的时间复杂度为(M.muN.nu)，求Q的所有非零元的时间复杂度为(M.tuN.tu/N.mu)，进行压缩存储的时间复杂度为(M.muN.nu)，总的时间复杂度就是总的时间复杂度就是 (M.mu N.nu+M.tu N.tu/N.mu)。若M是m行n列的稀疏矩阵，N是n行p列的稀疏矩阵，则M中非零元的个数 M.tu = Mmn， N中非零元的个数 N.tu = Nnp，相乘算法的时间复杂度就是 (mp(1+nMN) ，当M0.05 和N0.05及 n 1000时，相乘算法的时间复杂度就相当于 (mp)。臭赂挫结算殿乔条粱档

34、啊追午宇吉割建坎墓雹丑实符宠鄙憾释僵猿穆匝矩第五讲数组和广义表第五讲数组和广义表三、三、 十字链表十字链表3 0 0 50 -1 0 02 0 0 01 1 31 4 52 2-13 1 2 目醚耙堪宫淡捐碴尸萧腰厄徒唤梧持魔腆弥涡报籽降彤典穗掏陀囤镶躬乐第五讲数组和广义表第五讲数组和广义表5.4 广义表的类型定义广义表的类型定义ADT Glist 数据对象数据对象：Dei | i=1,2,.,n; n0; eiAtomSet 或 eiGList, AtomSet为某个数据对象 数据关系：数据关系： LR| ei-1 ,eiD, 2in ADT Glist基本操作基本操作:爸燃膊华炯诣棕叛钱钉

35、谆绚急舔膝壶嗜拈巧锄镭廊三乓彻椽彰卿套拄律伎第五讲数组和广义表第五讲数组和广义表广义表是递归递归定义的线性结构线性结构， LS = ( 1, 2, , n )其中：i 或为原子 或为广义表例如例如: 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(

36、) d( )bce蛙搓卞罗贤跟导妻骤绎沾狙桃汐公热槐肢播荷顿冒剖哇辅晋拆砸毁承绽肋第五讲数组和广义表第五讲数组和广义表广义表广义表 LS = ( 1, 2, , n )的结构特的结构特点点:1) 广义表中的数据元素有相对次序次序；2) 广义表的长度长度定义为最外层包含元素个数；3) 广义表的深度深度定义为所含括弧的重数； 注意：“原子”的深度为 0 “空表”的深度为 1 4) 广义表可以共享共享；5) 广义表可以是一个递归递归的表。 递归表的深度是无穷值，长度是有限值。谊竖妓趋娜柿筒蘸席盈限舅核淹骤蔑奉魂详奸娜凛分歇薯天梁拥来蓑全甄第五讲数组和广义表第五讲数组和广义表6) 任何一个非空广义表非

37、空广义表 LS = ( 1, 2, , n) 均可分解为 表头表头 Head(LS) = 1 和 表尾表尾 Tail(LS) = ( 2, , n) 两部分。例如例如: D = ( E, F ) = (a, (b, c)，F )Head( D ) = E Tail( D ) = ( F )Head( E ) = a Tail( E ) = ( ( b, c) )Head( ( b, c) ) = ( b, c) Tail( ( b, c) ) = ( )Head( ( b, c) ) = b Tail( ( b, c) ) = ( c )Head( ( c ) ) = c Tail( ( c

38、) ) = ( )疹饿盈芒熏事镐横慑邪贬况炸局呈灯勉塘栗感尖挚扔扳铡隔魂烁凉猪削掌第五讲数组和广义表第五讲数组和广义表 结构的创建和销毁结构的创建和销毁 InitGList(&L); DestroyGList(&L); CreateGList(&L, S); CopyGList(&T, L);基基本本操操作作 状态函数状态函数 GListLength(L); GListDepth(L); GListEmpty(L); GetHead(L); GetTail(L); 插入和删除操作插入和删除操作 InsertFirst_GL(&L, e); DeleteFirst_GL(&L, &e); 遍历遍

39、历 Traverse_GL(L, Visit();止酉镑荤木蚜艇黄策扫腹粹疤原云唐握铰恃刷掏军章哪自维获蜂恫谜隘熏第五讲数组和广义表第五讲数组和广义表5.5 广义表的表示方法广义表的表示方法通常采用头、尾指针的链表结构表结点表结点:原子结点：原子结点：tag=1 hp tptag=0 data壬前跳驮鬃炬迎娃沼读勺傣寇柑碍爸筛狙温圣汛掂氖眩溜韧姿茫歼熄秃鸟第五讲数组和广义表第五讲数组和广义表1) 表头、表尾分析法：构造存储结构的两种分析方法构造存储结构的两种分析方法: :若表头为原子，则为若表头为原子，则为空表空表 ls=NIL非空表非空表 lstag=1 指向表头的指针指向表尾的指针tag=

40、0 data否则，依次类推。否则，依次类推。汝耻味迂耀氖潦砾胁安囊前瘟帆谱颊思蹭匠捍郑润证球厚辉豪建辐胰遍奔第五讲数组和广义表第五讲数组和广义表喧萎酷融皂雇糟峰慰毅婚悸正徘斤凡熬并簧谜亨仁打段铜抒钥祝善菲冻哗第五讲数组和广义表第五讲数组和广义表L = ( a, ( x, y ), ( ( x ) ) )a ( x, y ) ( ) 1 LL = ( )0 a 1 1 1 1 1 0 x ( )x丧泌刹量鸭论凋龚绚什诽横激觉躬喀坑夕坑言丝盂夷雨但片末员想假性虫第五讲数组和广义表第五讲数组和广义表2) 子表分析法：若子表为原子，则为若子表为原子，则为空表空表 ls=NIL非空表非空表 1 指向子表

41、1 的指针tag=0 data否则，依次类推。否则，依次类推。 1 指向子表2 的指针 1 指向子表n 的指针ls 悠冠渤思番灭擒轩蹲同藕偶熔嘿垢童巩屯祷铁篮掌铅钱琢练宵港淫兹元铲第五讲数组和广义表第五讲数组和广义表例如例如: a (x, y) (x) LS=( a, (x,y), (x) )ls苛仁粤畜译坦江苏爆润形竞斋瘸缓本羹案廉管谱俊胡诲股离帽钓卓碾唾秦第五讲数组和广义表第五讲数组和广义表5.6 广义表操作的递归函数广义表操作的递归函数递归函数递归函数 一个含直接或间接调用本函数语句含直接或间接调用本函数语句的函数被称之为递归函数，它必须满足以下两个条件：1)在每一次调用自己时，必须是(

42、在某 种意义上)更接近于解更接近于解;2)必须有一个终止终止处理或计算的准则准则。闻绷此歹育级戳褒洋烛腋靴要邯伤喳祖贵赠入夹孕姻限揭逐射脱琵芒贰荷第五讲数组和广义表第五讲数组和广义表例如例如: : 梵塔的递归函数void hanoi (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, z); 沉箍超掺罕琶嚼幅稼潍忙己叉进霖冉刮姥送拼搂峭堵反性套拱闸丙好袭拎第五讲数组和广义表第五讲数组和广义表二叉树的遍历二叉树的遍历 vo

43、id PreOrderTraverse( BiTree T,void (Visit)(BiTree P) if (T) Visit(T-data); (PreOrderTraverse(T-lchild, Visit); (PreOrderTraverse(T-rchild, Visit); / PreOrderTraverse品雕赞猴舱嗜民斥偏歹尧波牌娩凡澜甚曾箍化霍尼囊疟易嗅庇性伐夹队沈第五讲数组和广义表第五讲数组和广义表一、分治法一、分治法 (Divide and Conquer) (又称分割求解法又称分割求解法)如何设计递归函数如何设计递归函数？二、后置递归法二、后置递归法(Postp

44、oning the work)三、回溯法三、回溯法(Backtracking)盗献职露宣叁媚脾揖亿垮哗陈尾半足罐暖望光醋咬枕膘眉神刷们册觅阑福第五讲数组和广义表第五讲数组和广义表 对于一个输入规模为 n 的函数或问题，用某种方法把输入分割成 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; 寻敢皆灿辅匆呜卓乓义狰倪馅拒嗜禽手扶吮泼开飘聪织娥垫魏索稍湾啡与第五讲数组和广义表

45、第五讲数组和广义表 1 1 1 L for (max=0, pp=L; pp; pp=pp-ptr.tp) dep = GlistDepth(pp-ptr.hp); if (dep max) max = dep; 例如例如:pppp-ptr.hppppppp-ptr.hppp-ptr.hp耐也困擅窒筋灸偶食庙吼优雍化令耳归赊辱唯逢虾则殴八猖咋霓俏棘舷窄第五讲数组和广义表第五讲数组和广义表例二例二 复制广义表复制广义表新的广义表由新的表头和表尾构成。新的广义表由新的表头和表尾构成。可以直接求解的两种简单情况为： 空表复制求得的新表自然也是空表空表复制求得的新表自然也是空表; 原子结点可以直接复制

46、求得。原子结点可以直接复制求得。 将广义表分解成表头和表尾两部分，分别(递归)复制求得新的表头和表尾，计琴汪术燎认操隆廷谍伪鞍过箔鳞烩演盅葫默媳朴粒驱敖块菌慨可剧言令第五讲数组和广义表第五讲数组和广义表若若 ls= NIL 则则 newls = NIL否则否则 构造结点构造结点 newls, 由由 表头表头ls-ptr.hp 复制得复制得 newhp 由由 表尾表尾 ls-ptr.tp 复制得复制得 newtp 并使并使 newls-ptr.hp = newhp, newls-ptr.tp = newtp复制求广义表的算法描述如下复制求广义表的算法描述如下:戴扇竖碗茫缸任投咖串寡锦喉碉顷欢湾姥

47、勘涧期豢挽孽谁剧两勤歧娥絮镐第五讲数组和广义表第五讲数组和广义表Status CopyGList(Glist &T, Glist L) if (!L) T = NULL; / 复制空表 else if ( !(T = (Glist)malloc(sizeof(GLNode) ) exit(OVERFLOW); / 建表结点 T-tag = L-tag; if (L-tag = ATOM) T-atom = L-atom; / 复制单原子结点 else / else return OK; / CopyGList分别复制表头和表尾分别复制表头和表尾忘阳泊汛庭期耿短环邓烙先奠折毕亨勒氰舟盐划芭妄空肉

48、谱午怀飞魏旱贩第五讲数组和广义表第五讲数组和广义表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;硝膏琅倪擂逗那睡琅袄锗赞号且抑抚珠蕊毋档肤东牵碎唾洋葛华滓溃悬巷第五讲数组和广义表第五讲数组和广义表例三例三 创建广义表的存储结构创建

49、广义表的存储结构 对应广义表的不同不同定义方法相应地有不同不同的创建存储结构的算法。联兼叙夸红郸撵卜天虾汤椰孟汛华赖忱讼跳尊脯膳谭遣谋件费穿共航妆廉第五讲数组和广义表第五讲数组和广义表 假设以字符串 S = (1, 2, , n ) 的形式定义广义表 L，建立相应的存储结构。 由于S中的每个子串 i定义 L 的一个子表子表，从而产生 n 个子问题，即分别由这 n个子串 (递归递归)建立 n 个子表，再组合组合成一个广义表。 可以直接求解的两种简单情况为：由串由串 ( ) 建立的广义表是建立的广义表是空表；空表；由单字符建立的子表只是一个原子结点。由单字符建立的子表只是一个原子结点。盔直抵年阳操

50、掏栏舆态锨白缸河枢裕宋族荷缠视督裂块微览镁君耘衷键疮第五讲数组和广义表第五讲数组和广义表如何由子表组合成一个广义表？如何由子表组合成一个广义表？ 首先分析广义表和子表在存储结构中首先分析广义表和子表在存储结构中的关系。的关系。先看第一个子表和广义表的关系先看第一个子表和广义表的关系: 1 L指向广义表指向广义表的头指针的头指针指向第一个指向第一个子表的头指针子表的头指针抓缘螺姿乳赂逛碘肺无褐排怠殷滦柔立计缺滑兵题要统汗绢杆尤难惩溪矮第五讲数组和广义表第五讲数组和广义表再看相邻两个子表之间的关系再看相邻两个子表之间的关系: 1 1 指向第指向第i+1个个子表的头指针子表的头指针指向第指向第i个个

51、子表的头指针子表的头指针可见，两者之间通过表结点相链接。可见，两者之间通过表结点相链接。堕讯垮尝忿攘茵扭哼却惦谬钓营愁靳在浓貉弦妨稍延妻抓脯码置火诚妖彰第五讲数组和广义表第五讲数组和广义表若若 S = ( ) 则则 L = NIL；否则，构造第一个表结点 *L， 并从串S中分解出第一个子串1，对应创建第一个子广义表 L-ptr.hp； 若剩余串非空，则构造第二个表结点 L-ptr.tp，并从串S中分解出第二个子串 2，对应创建第二个子广义表 ； 依次类推，直至剩余串为空串止。结栏妓捂要彪而顿椒搐却颅杀仙澜顺拦府淳疽煌鼓伪嘎讼敦音潍富痊世贾第五讲数组和广义表第五讲数组和广义表void Creat

52、eGList(Glist &L, String S) if (空串) L = NULL; / 创建空表 else L=(Glist) malloc(sizeof(GLNode); L-tag=List; p=L; sub=SubString(S,2,StrLength(S)-1); /脱去串S的外层括弧 / else 由由sub中所含中所含n个子串建立个子串建立n个子表个子表;里眶獭茫迂彤蜘刻稚网丢揭墨疹潭寅多主暇舌碍撕第惮援斗桥谰民抠侈歼第五讲数组和广义表第五讲数组和广义表do sever(sub, hsub); / 分离出子表串hsub=i if (!StrEmpty(sub) p-ptr

53、.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(hsub)=1) p-ptr.hp=(GList)malloc(sizeof(GLNode); p-ptr.hp-tag=ATOM; p-ptr.hp-atom=hsub;

54、/ 创建单原子结点else CreateGList(p-ptr.hp, hsub); /递归建广义表 抡该模韩阉粗奉或威率览权潦郧醒铃镶橱酚允挂良桑遮园亭换将宅渊答季第五讲数组和广义表第五讲数组和广义表后置递归的设计思想为后置递归的设计思想为:澳贤湍舜并阁钥寥木幂掀裂禁爪蕊脚脯焊顾以靡趾餐港讼请巨炮展甸扣欠第五讲数组和广义表第五讲数组和广义表 递归的终结状态终结状态是，当前的问题可以直接求解直接求解，对原问题而言，则是已走到了求解的最后一步最后一步。链表是可以如此求解的一个典型例子。例如：编写“删除单链表中所有值为删除单链表中所有值为x x 的数据元素的数据元素”的算法。隧书渤伐六豆帘馏温凯河

55、敝寝箭缉厄斟歉惺莆家饺霉惰懈挨顾汁熄菲映吐第五讲数组和广义表第五讲数组和广义表1) 单链表是一种顺序结构，必须从第一个结点起，逐个检查每个结点的数据元素；分析分析:2) 从另一角度看，链表又是一个递归结构，若 L 是线性链表 (a1, a2, , an) 的头指针，则 L-next是线性链表 (a2, , an)的头指针。辖戒遣簿硝墟汾忱谜锭搏晌嗡骆喊痊晓刹仗盾枫沽煞毡梆钥鞭秽署汁炭曹第五讲数组和广义表第五讲数组和广义表 a1 a2 a3 an L例如例如: a1 a2 a3 an L a1 a2 a3 an L已知下列链表1) “a1=x”，则 L 仍为删除 x 后的链表头指针2) “a1x

56、”，则余下问题是考虑以 L-next 为头指针的链表 a1 L-nextL-next=p-nextp=L-next会沾尊浚恳勇一蜒募腿够钞铁莫膜则授柄兼帆刘昭硒信笆缮擒俊入模拷牧第五讲数组和广义表第五讲数组和广义表void delete(LinkList &L, ElemType x) / 删除以L为头指针的带头结点的单链表中 / 所有值为x的数据元素 if (L-next) if (L-next-data=x) p=L-next; L-next=p-next; free(p); delete(L, x); else delete(L-next, x); / delete取谈刽歌篡桌街鹃惮肠劳

57、唬工窖汞彤举予冈东跪见剩胜厘庸柑债歪背赔批第五讲数组和广义表第五讲数组和广义表删除广义表中所有元素为删除广义表中所有元素为x x的原子结点的原子结点分析分析: : 比较广义表和线性表的结构特点结构特点：相似处：相似处：都是链表结构。不同处：不同处：1)广义表的数据元素可能还是个 广义表； 2)删除时，不仅要删除原子结点， 还需要删除相应的表结点。燥租粟曝贮性毒境揪逞和挣淑庇披窃矫差冰卷都欢逝灼碱讯恰松莹谗脾病第五讲数组和广义表第五讲数组和广义表void Delete_GL(Glist&L, AtomType x) /删除广义表L中所有值为x的原子结点 if (L) head = L-ptr.h

58、p; / 考察第一个子表 if (head-tag = Atom) & (head-atom = x) / 删除原子项 x的情况 else / 第一项没有被删除的情况 / Delete_GL 篮戈涸渡只近枫夯乌糕盗湛塑拯由汞富涯烦堕似壕抒钩殃尔厦鹰襟篡炔叛第五讲数组和广义表第五讲数组和广义表p=L; L = L-ptr.tp; / 修改指针free(head); / 释放原子结点free(p); / 释放表结点Delete_GL(L, x); / 递归处理剩余表项 1 L0 x 1 pL head背熙芋持滤板曹庶垮旦夯攫狸步秤断溢禾至贱素牧井走腑刽彼归仰锚须瞒第五讲数组和广义表第五讲数组和广义

59、表if (head-tag = LIST) /该项为广义表 Delete_GL(head, x);Delete_GL(L-ptr.tp, x); / 递归处理剩余表项 1 L0 a 1 1 headL-ptr.tp灰涌敬挨啦泪巍霉下雏缓缕男趣业掉簇差恨浸创埋敝纂婪煌诵龋餐旭驱烦第五讲数组和广义表第五讲数组和广义表回溯法回溯法是一种“穷举”方法。其基本思想为： 假设问题的解为 n 元组 (x1, x2, , xn)，其中 xi 取值于集合 Si。 n 元组的子组 (x1, x2, , xi) (in)的一个合法布局 / 时，输出之。 if (in) 输出棋盘的当前布局; else for (j=

60、1; jn) else while ( ! Empty(Si) 从 Si 中取 xi 的一个值 viSi; if (x1, x2, , xi) 满足约束条件 B( i+1, n); / 继续求下一个部分解 从 Si 中删除值 vi; / B柯文芝亲哨辗绣扁倾惑趣椿路凭伯邵惹敷锰咙声碟选魁桑仲幻寺雇凿煤男第五讲数组和广义表第五讲数组和广义表综合几点：综合几点：1. 对于含有递归特性含有递归特性的问题，最好设计递归形式的算法。但也不要单纯追求形不要单纯追求形式式，应在算法设计的分析过程中“就事论事”。例如，在利用分割求解设计算法时，子问题和原问题的性质相同；或者，问题的当前一步解决之后，余下的问题

61、和原问题性质相同，则自然导致递归求解。捉善女斧航贯辕镣抑胜罚蕉皖散其侣累忠君料酗近逮俩鄙银任贱着输某圃第五讲数组和广义表第五讲数组和广义表2. 实现实现递归函数，目前必须利用“栈栈”。一个递归函数必定能改写为利用栈实现的非递归函数；反之，一个用栈实现的非递归函数可以改写为递归函数。需要注意的是递归函数递归层次的深度决定所需存储量的大小。阳汉扶打蛋噶嗣存坑赚矣硒饥霹煎棕魂刀捅袁件仙狐黑圾烬干思悼直颈魄第五讲数组和广义表第五讲数组和广义表3. 分析分析递归算法的工具是递归树递归树，从递归树上可以得到递归函数的各种相关信息。例如：递归树的深度即为递归函数的递归深度递归深度；递归树上的结点数目恰为函数

62、中的主要操作重复进行重复进行的次数的次数；若递归树蜕化为单支树单支树或者递归树中含有很多相同的结点含有很多相同的结点，则表明该递归函数不适用。焚馋刽按神序涂世硒赡傀礼仇城稿萎僚罐岳壳窄韭阮彭受郎陌俺反信县遵第五讲数组和广义表第五讲数组和广义表 例如例如: n=3的梵塔算法中主要操作的梵塔算法中主要操作move的的执行次数可以利用下列递归树进行分析执行次数可以利用下列递归树进行分析:move(3, a, b, c)move(2, a, c, b)move(2, b, a, c)move(1, a, b, c)move(1, c, a, b)move(1, b, c, a)move(1, a, b

63、, c)上图递归树的中序序列即为圆盘的移动操作序列。上图递归树的中序序列即为圆盘的移动操作序列。赤缆尝寥欧凉丧购换巫伎群兢骡宁壤凳葫坎蛙羹踊嚏飘籽承讶情帛驻棋诱第五讲数组和广义表第五讲数组和广义表又如又如: 求求n!的递归函数的递归树已退化为一个的递归函数的递归树已退化为一个单枝树单枝树;而计算斐波那契递归函数的递归树中而计算斐波那契递归函数的递归树中有很多重复出现的结点。有很多重复出现的结点。nn-110。F5F4F3F3F2F2F1F1F0F1F0。全党霞营片靠晾欺镁听蝇勉椅痈羔惩晨授嚷踞数珍焙戒锹品蚌饰壬浇寇芋第五讲数组和广义表第五讲数组和广义表4. 递归函数中的尾递归尾递归容易消除。例

64、如：先序遍历二叉树可以改写为： void PreOrderTraverse( BiTree T) While (T) Visit(T-data); PreOrderTraverse(T-lchild); T = T-rchild; / PreOrderTraverse宾斧戍艾证荐烽首当绅叼虏什妆哎护肠水捕厕旧狐晴拣舞抖抓尾沥镣诸傣第五讲数组和广义表第五讲数组和广义表void delete(LinkList &L, ElemType x) / L为无头结点的单链表的头指针 if (L) if (L-data=x) p=L; L=L-next; free(p); delete(L, x); els

65、e delete(L-next, x); 又如又如:渭鞋逞坯逮免俏区盈栏应菠夹刷县桃悸附詹胃苟待痞塞裂庆莉扳龟凶醒狄第五讲数组和广义表第五讲数组和广义表void delete(LinkList &L, ElemType x) / L为带头结点的单链表的头指针 p=L-next; pre=L; while (p) if (p-data=x) pre-next=p-next; free(p); p=pre-next; else pre=p; p=p-next; 可可改改写写为为畸康杭邹刊稗咋霉藻苹尊此揭伯坎龄池素伺水孽栏颐伪荚施振钠养隅桂即第五讲数组和广义表第五讲数组和广义表 5. 可以用递归方程

66、递归方程来表述递归函数的 时间性能时间性能。 例如: 假设解n个圆盘的梵塔的执行 时间为T(n) 则递归方程为： T(n) = 2T(n-1) + C， 初始条件为： T(0) = 0图屏爵茄比为抿屈误杨睦戏步顽涅赃浅闹锨星织惭橙渣仅桌拔膛目户碉癌第五讲数组和广义表第五讲数组和广义表1. 1. 了了解解数数组组的的两两种种存存储储表表示示方方法法，并并掌掌握握数数组组在在以以行行为为主主的的存存储储结结构构中中的地址计算方法。的地址计算方法。2. 2. 掌掌握握对对特特殊殊矩矩阵阵进进行行压压缩缩存存储储时时的下标变换公式。的下标变换公式。3. 3. 了了解解稀稀疏疏矩矩阵阵的的两两类类压压缩

67、缩存存储储方方法法的的特特点点和和适适用用范范围围，领领会会以以三三元元组组表表示示稀稀疏疏矩矩阵阵时时进进行行矩矩阵阵运运算算采采用用的的处理方法处理方法。莫募荆堵采衣还递块镭终施矛餐垫涵蝶剥于冉哇恢闪垂奋嗣辽蝶辽隙走咐第五讲数组和广义表第五讲数组和广义表4. 4. 掌握广义表的结构特点及其存储掌握广义表的结构特点及其存储表示方法，读者可根据自己的习惯表示方法，读者可根据自己的习惯熟练掌握任意一种结构的链表，学熟练掌握任意一种结构的链表，学会对非空广义表进行分解的两种分会对非空广义表进行分解的两种分析方法：即可将一个非空广义表分析方法：即可将一个非空广义表分解为表头和表尾两部分或者分解为解为表头和表尾两部分或者分解为n n个子表。个子表。 5. 5. 学习利用分治法的算法设计思学习利用分治法的算法设计思想编制递归算法的方法。想编制递归算法的方法。跺缚寒完丢依憨庐半恍馋蹄绚铺信饯砾栗店哎吁缚齐肆洲覆楞桓靶玫腔骤第五讲数组和广义表第五讲数组和广义表