数据结构(c描述)电子教案第5章

1、第5章多维数组和广义表 数据结构（C+描述） 漫蔡辫忠录晨棺务颓劝渝寐门婚罪喝州奥庚署隔拿驼辈疑宰迂湘匿宗么咆数据结构(C+描述)电子教案第5章数据结构(C+描述)电子教案第5章5.5 广义表5.3 特殊矩阵及其压缩存储5.4 稀疏矩阵退出目录计许帕病膏骚练扮韦游乳埠糜韶剐庸龟瞄命鳖斗暮彝挤覆面戎驮皆箭涛毋数据结构(C+描述)电子教案第5章数据结构(C+描述)电子教案第5章5.1多维数组 5.1.1多维数组的概念 1一维数组一维数组可以看成是一个线性表或一个向量（第二章已经介绍），它在计算机内是存放在一块连续的存储单元中，适合于随机查找。这在第二章的线性表的顺序存储结构中已经介绍。2二维数组二

2、维数组可以看成是向量的推广。 边举迫疏伍铡斧萨惊灾轴哪液盐啊劲绝涧飞仁席熏申徘触慌畸攘谍徒潜玩数据结构(C+描述)电子教案第5章数据结构(C+描述)电子教案第5章例如，设A是一个有m行n列的二维数组，则A可以表示为：在此，可以将二维数组A看成是由m个行向量X0，X1， ，Xm-1T组成，其中，Xi=( ai0, ai1, .,ain-1)， 0im-1；也可以将二维数组A看成是由n个列向量y0, y1, ,yn-1组成，其中 yi=(a0i, a1i, .,am-1i)， 0in-1。 厉珊斡枉锰享移通腿钧厅唐件缘私屹扩体蹈芍寄语缝苗哼票想鄙犯珠妊覆数据结构(C+描述)电子教案第5章数据结构(

3、C+描述)电子教案第5章由此可知二维数组中的每一个元素 最多可有二个直接前驱和两个直接后继（边界除外），故是一种典型的非线性结构。3多维数组同理，三维数组最多可有三个直接前驱和三个直接后继，三维以上数组可以作类似分析。因此，可以把三维以上的数组称为多维数组，多维数组可有多个直接前驱和多个直接后继，故多维数组是一种非线性结构。缺黎塔障戊衫臭秆谋证吾汹不鹏或猪躲哈垮补苔傀夺骄笔菏挪流眷糖楼扶数据结构(C+描述)电子教案第5章数据结构(C+描述)电子教案第5章5.1.2 多维数组在计算机内的存放怎样将多维数组中元素存入到计算机内存中呢？由于计算机内存结构是一维的（线性的），因此，用一维内存存放多维数

4、组就必须按某种次序将数组元素排成一个线性序列，然后将这个线性序列顺序存放在存储器中 由于数组一般不作插入或删除操作，也就是说，一旦建立了数组，则结构中的数组元素个数和元素之间的关系就不再发生变动，即它们的逻辑结构就固定下来了，不再发生变化。因此，采用顺序存储结构表示数组是顺理成章的事了。本章中，仅重点讨论二维数组的存储，三维及三维以上的数组可以作类似分析。翌放傻店淬尖豁旅斩荫妊蝴壕茸稗羞蚁悼柠薯纪金义烧嚼露防焕频蠢钦嗡数据结构(C+描述)电子教案第5章数据结构(C+描述)电子教案第5章多维数组的顺序存储有两种形式：5.2.1 行优先顺序1存放规则 行优先顺序也称为低下标优先或左边下标优先于右边

5、下标。具体实现时，按行号从小到大的顺序，先将第一行中元素全部存放好，再存放第二行元素，第三行元素，依次类推 在BASIC语言、 PASCAL语言、 C/C+语言等高级语言程序设计中，都是按行优先顺序存放的。例如，对刚才的Amn二维数组，可用如下形式存放到内存：a00， a01, a0n-1，a10，a11，.， a1 n-1，am-1 0 ， am-1 1，am-1 n-1。即二维数组按行优先存放到内存后，变成了一个线性序列（线性表）。暂央虱尹皮骗啡吃甩贯分乱缝位牙告腆斩羽哟孪石席动抵室建豪毒球孔捣数据结构(C+描述)电子教案第5章数据结构(C+描述)电子教案第5章因此，可以得出多维数组按行优

6、先存放到内存的规律：最左边下标变化最慢，最右边下标变化最快，右边下标变化一遍，与之相邻的左边下标才变化一次。因此，在算法中，最左边下标可以看成是外循环，最右边下标可以看成是最内循环。 2地址计算 由于多维数组在内存中排列成一个线性序列，因此，若知道第一个元素的内存地址，如何求得其它元素的内存地址？我们可以将它们的地址排列看成是一个等差数列，假设每个元素占l个字节，元素aij 的存储地址应为第一个元素的地址加上排在aij 前面的元素所占用的单元数，而aij 的前面有i行(0i-1)共in个元素，而本行前面又有j个元素，故aij的前面一共有in+j个元素，设a00的内存地址为LOC(a00)，则a

7、ij的内存地址按等差数列计算为LOC(aij)=LOC(a00)+（in+j）l。同理，三维数组Amnp按行优先存放的地址计算公式为：LOC(aijk)=LOC(a000)+(inp+jp+k)l。许两民曙盯糕跃亭少痘蒜累荣仓海洋救禁婉使皂揪抑礼圃归鲤片漓唆熄钱数据结构(C+描述)电子教案第5章数据结构(C+描述)电子教案第5章5.2.2 列优先顺序1存放规则列优先顺序也称为高下标优先或右边下标优先于左边下标。具体实现时，按列号从小到大的顺序，先将第一列中元素全部存放好，再存放第二列元素，第三列元素，依次类推 在FORTRAN语言程序设计中，数组是按列优先顺序存放的。例如，对前面提到的Amn二

8、维数组，可以按如下的形式存放到内存：a00， a10， am-10， a01，a11， ， am-1 1， a0 m-1，a1m-1，.， am-1 n-1。 即二维数组按列优先存放到内存后，也变成了一个线性序列（线性表）。防轿株缄挣抉姜违反般夕卵叶砒蛾嘛沟囱锅雨故岩免暇避特丑江宇孺鼓券数据结构(C+描述)电子教案第5章数据结构(C+描述)电子教案第5章因此，可以得出多维数组按列优先存放到内存的规律：最右边下标变化最慢，最左边下标变化最快，左边下标变化一遍，与之相邻的右边下标才变化一次。因此，在算法中，最右边下标可以看成是外循环，最左边下标可以看成是最内循环。2地址计算 同样与行优先存放类似，

9、若知道第一个元素的内存地址，则同样可以求得按列优存放的某一元素aij的地址。对二维数组有：LOC(aij)=LOC(a00)+(jm+i)l对三维数组有： LOC(aijk)=LOC(a000)+(kmn+jm+i)l劣全追懈嫉侣给卑练佑丑蚊引善籍膨燕殆尺疥兴厚例扎纤件猫吃瞎过热毡数据结构(C+描述)电子教案第5章数据结构(C+描述)电子教案第5章5.3 特殊矩阵及其压缩存储 5.3.1 特殊矩阵 若一个n阶方阵A中元素满足下列条件： aij=aji 其中 0 i, jn-1 ， 则称A为对称矩阵。例如，图5-1是一个3*3的对称矩阵。1对称矩阵 寿脑雪抽垣疼弱蒸册锐言胯钦俄亮杜末讽旅碘疽趁舅

10、阵悸憎效将歌蘸院皆数据结构(C+描述)电子教案第5章数据结构(C+描述)电子教案第5章2三角矩阵 （1）上三角矩阵即矩阵上三角部分元素是随机的，而下三角部分元素全部相同（为某常数C）或全为0，具体形式见图5-2(a)。 （2）下三角矩阵即矩阵的下三角部分元素是随机的，而上三角部分元素全部相同（为某常数C）或全为0，具体形式见图5-2(b)。 湛逞汰楞砌镁垄喇燃魔粮撬唯茹礼烯吩溃旧凡沾觉疲食眷受魏粹洼哇陪汇数据结构(C+描述)电子教案第5章数据结构(C+描述)电子教案第5章3对角矩阵 若矩阵中所有非零元素都集中在以主对角线为中心的带状区域中，区域外的值全为0，则称为对角矩阵。常见的有三对角矩阵、

11、五对角矩阵、七对角矩阵等。例如，图5-3为77的三对角矩阵（即有三条对角线上元素非0）。 登傣悄媳纯刀俞渔榔桔樊槛龄汇苏识辙伟澡三拔氖吊啸巍腑巨凝炒皿敞谜数据结构(C+描述)电子教案第5章数据结构(C+描述)电子教案第5章5.3.2 压缩存储1对称矩阵 若矩阵Ann是对称的，对称的两个元素可以共用一个存储单元，这样，原来n 阶方阵需 n2个存储单元，若采用压缩存储，仅需 n(n+1)/2个存贮单元，将近节约一半存贮单元，这就是实现压缩的好处。但是，将n阶对称方阵存放到一个向量空间s0到s -1 中，我们怎样找到sk与aij的一一对称应关系呢？使我们在sk中直接找到aij。我们仅以行优先存放分两

12、种方式讨论：述欢珍艳厦茹审嫌苑锗疽液甸测诲御做隙茸触对浸察敬砾逐殿府雹嘲僧喀数据结构(C+描述)电子教案第5章数据结构(C+描述)电子教案第5章（1）只存放下三角部分由于对称矩阵关于主对角线对称，故我们只需存放主对角线及主对角线以下的元素。这时， a00存入s0，a10 存入s1，a11存入 s2，具体参见图5-4。这时sk与aij的对应关系为： i(i+1)/2+j 当 ij k= j(j+1)/2+i 当 ij 上面的对应关系读者很容易推出：当ij 时，aij在下三角部分中，aij前面有i行，共有1+2+3+i个元素，而aij是第i行的第j个元素，即有k=1+2+3+i+j=i(i+1)/

13、2+j；当ij时，交换i与j即可。故sk与aij的对应关系为： i*n- +j-i 当ij k= j*n- +i-j 当ij虞肩稀溶缝钩柔李肮训巡翠萨殴第屉搀千崖尼瞻佃诣观畅涪益会刨雕铝淖数据结构(C+描述)电子教案第5章数据结构(C+描述)电子教案第5章呈垫忱宗委亨绷因迢钉库钥泅欧馆纲手是认盆醋轰论刹秃墩吠菲捻恫戌垃数据结构(C+描述)电子教案第5章数据结构(C+描述)电子教案第5章2三角矩阵 （1）下三角矩阵下三角矩阵的压缩存放与对称矩阵用下三角形式存放类似，但必须多一个存储单元存放上三角部分元素，使用的存储单元数目为n(n+1)/2+1。故可以将nn的下三角矩阵压缩存放到只有n(n+1)

14、/2+1个存储单元的向量中，假设仍按行优先存放，这时sk与aij的对应关系为： i(i+1)/2+j ij k= n(n+1)/2 ij 林山力将殉找密升贾循列炽孟烹暴妥超军娃吁译圈墨汹番逮孺萨蛮轩脑茬数据结构(C+描述)电子教案第5章数据结构(C+描述)电子教案第5章3对角矩阵我们仅讨论三对角矩阵的压缩存贮，五对角矩阵，七对角矩阵等读者可以作类似分析。在一个nn的三对角矩阵中，只有n+n-1+n-1个非零元素，故只需3n-2个存储单元即可，零元已不占用存储单元。故可将nn三对角矩阵A压缩存放到只有3n-2个存储单元的s向量中，假设仍按行优先顺序存放，则：sk与aij的对应关系为： 3i-1

15、当 i=j+1k= 3i 当i=j 3i+1 当i=j-1旅侣贿馆所卉婴放所洒皱掷娜撵养拷腆钱适窖犹贿漫采腿鹤寨湘楷荫妒祥数据结构(C+描述)电子教案第5章数据结构(C+描述)电子教案第5章5.4 稀疏矩阵在上节提到的特殊矩阵中，元素的分布呈现某种规律，故一定能找到一种合适的方法，将它们进行压缩存放。但是，在实际应用中，我们还经常会遇到一类矩阵：其矩阵阶数很大，非零元个数较少，零元很多，但非零元的排列没有一定规律，我们称这一类矩阵为稀疏矩阵。按照压缩存储的概念，要存放稀疏矩阵的元素，由于没有某种规律，除存放非零元的值外，还必须存贮适当的辅助信息，才能迅速确定一个非零元是矩阵中的哪一个位置上的元

16、素。下面将介绍稀疏矩阵的几种存储方法及一些算法的实现。 泣浴力谈泉毙两已鲸采熟局绸陀峭绞视次偿纵刷逐春缉估茅棵崇壤再疾虱数据结构(C+描述)电子教案第5章数据结构(C+描述)电子教案第5章5.4.1 稀疏矩阵的存储 1三元组表在压缩存放稀疏矩阵的非零元同时，若还存放此非零元所在的行号和列号，则称为三元组表法，即称稀疏矩阵可用三元组表进行压缩存储，但它是一种顺序存贮（按行优先顺序存放）。一个非零元有行号、列号、值，为一个三元组，整个稀疏矩阵中非零元的三元组合起来称为三元组表。唾氧概量衬瓦蜒骂呸桓赘布谅隅蹬垦撅骋疗玉园座缮冤莹陛悠段旁吗泥枫数据结构(C+描述)电子教案第5章数据结构(C+描述)电子

17、教案第5章此时，数据类型可描述如下：const int maxsize=100;/定义非零元的最大数目struct node /定义一个三元组 int i , j; /非零元行、列号int v; /非零元值; struct sparmatrix /定义稀疏矩阵 int rows,cols ; /稀疏矩阵行、列数int terms; /稀疏矩阵非零元个数node data maxsize; /三元组表;暗肌励慨问巾害省陵姚藉甥粟尊栅痉旨浊钓竖缩铀擦竿犹厘协竞橇巾招稿数据结构(C+描述)电子教案第5章数据结构(C+描述)电子教案第5章稀疏矩阵M和N的三元组表见图5-8。 倡腰捕乙戴旧也岳啃姿邵琉藻

18、央邱氨水均母肋求若矽榔窿辽腻程漱怖卡崭数据结构(C+描述)电子教案第5章数据结构(C+描述)电子教案第5章2带行指针的链表 把具有相同行号的非零元用一个单链表连接起来，稀疏矩阵中的若干行组成若干个单链表，合起来称为带行指针的链表。例如，图5-6 的稀疏矩阵M的带行指针的链表描述形式见图5-9。 猿豌宣旬忱隅霸除际矩林庶滨盒阀恍漳终镐峭都奖蚜卢渊冰塘欣盆树丝郑数据结构(C+描述)电子教案第5章数据结构(C+描述)电子教案第5章3十字链表 当稀疏矩阵中非零元的位置或个数经常变动时，三元组就不适合于作稀疏矩阵的存储结构，此时，采用链表作为存储结构更为恰当。十字链表为稀疏矩阵中的链接存储中的一种较好的

19、存储方法，在该方法中，每一个非零元用一个结点表示，结点中除了表示非零元所在的行、列和值的三元组(i,j,v)外，还需增加两个链域：行指针域(rptr)，用来指向本行中下一个非零元素；列指针域(cptr) ，用来指向本列中下一个非零元素。稀疏矩阵中同一行的非零元通过向右的rptr指针链接成一个带表头结点的循环链表。同一列的非零元也通过cptr指针链接成一个带表头结点的循链链表。因此，每个非零元既是第i行循环链表中的一个结点，又是第j列循环链表中的一个结点，相当于处在一个十字交叉路口，故称链表为十字链表。迸熊且县音廉瓜碘廉谦绷县栖笔策项骄邓蓬排皇筹脏搐生掠宛走鹊铲昧挪数据结构(C+描述)电子教案第

20、5章数据结构(C+描述)电子教案第5章另外，为了运算方便，我们规定行、列循环链表的表头结点和表示非零元的结点一样，也定为五个域，且规定行、列、域值为0，并且将所有的行、列链表和头结点一起链成一个循环链表。在行(列)表头结点中，行、列域的值都为0，故两组表头结点可以共用，即第i行链表和第i列链表共用一个表头结点，这些表头结点本身又可以通过V域(非零元值域，但在表头结点中为next，指向下一个表头结点)相链接。另外，再增加一个附加结点(由指针hm指示，行、列域分别为稀疏矩阵的行、列数目)，附加结点指向第一个表头结点，则整个十字链表可由hm指针唯一确定。蹿续踞钝却匈葫唆琵歇阜诚缴芽钨愈怎徒冶塌橡找澳

21、吝疟佬派醉木萨扬摇数据结构(C+描述)电子教案第5章数据结构(C+描述)电子教案第5章十字链表的数据类型描述如下：struct linknode int i, j;linknode *cptr, *rptr;union vnext /定义一个共用体 int v; /表结点使用V域,表示非零元值linknode *next; / /表头结点使用next域 k; 例如，图5-6 的稀疏矩阵M的十字链表描述形式见图5-10。 简嗣概甭捡悸颊蛮妆凶纺劳泽险歧袋著腐帅颅鼎丰弟弃艳蛰奔续露驴韧险数据结构(C+描述)电子教案第5章数据结构(C+描述)电子教案第5章屠棵骄瑚瓦镰峰交筋眺型锗椿趟拳培狠侦共纫竣悦

22、裔武颖祖悟秃夸骇软钾数据结构(C+描述)电子教案第5章数据结构(C+描述)电子教案第5章5.4.2 稀疏矩阵的运算 1稀疏矩阵的转置运算 转置是矩阵中最简单的一种运算。对于一个mn的矩阵A，它的转置B是一个nm 的，且Bij=Aji，0in,0j0)int bno=0;for (int col=0; cola.cols; col+)/按列号扫描 for(int ano=0;anoa.terms;ano+)/对三元组表扫描if (a.dataano.j=col) /进行转置 b.databno.j=a.dataano.i;b.databno.i=a.dataano.j;b.databno.v=a

23、.dataano.v;bno+;纵衫赤堤戳议探衡娠昨蛇搜都献袋隐镁滨膨裤陪磷壶壕纵矣猴壤赚蛾栽井数据结构(C+描述)电子教案第5章数据结构(C+描述)电子教案第5章分析这个算法，主要工作在col和ano二重循环上，故算法的时间复杂度为 O(a.cols*a.terms)。而通常的mn阶矩阵转置算法可描述为：for(col=0; coln; col+)for (row=0;rowm;row+)bcolrow=arowcol;它的时间复杂度为o(mn)。而一般的稀疏矩阵中非零元个数a.terms远大于行数 m，故压缩存贮时，进行转置运算，虽然节省了存贮单元，但增大了时间复杂度，故此算法仅适应于a.

24、ternsa.rows a.cols的情形。抿磺好蛾潞亏斧憾蓖鞘蠢洼蒜云速悬窘雌神臂魔除菱呆御紊嘱碑摧讨麻绸数据结构(C+描述)电子教案第5章数据结构(C+描述)电子教案第5章（2）按照A的行序进行转置即按a.data中三元组的次序进行转置，并将转置后的三元组放入b中恰当的位置。若能在转置前求出矩阵A的每一列col(即B中每一行)的第一个非零元转置后在b.data中的正确位置potcol(0cola.cols)，那么在对a.data的三元组依次作转置时，只要将三元组按列号col放置到b.datapotcol中，之后将potcol内容加1，以指示第col列的下一个非零元的正确位置。为了求得位置向

25、量pot，只要先求出A的每一列中非零元个数numcol，然后利用下面公式： pot0=0 potcol=potcol-1+numcol-1 当1col0) for(col=0;cola.cols;col+) potcol=0;for(int t=0;ta.terms;t+) /求出每一列的非零元个数 col=a.datat.j; potcol+1=potcol+1+; pot0=0;for(col=1;cola.cols;col+) /求出每一列的第一个非零元在转置后的位置potcol=potcol-1+potcol;喜玻拱夷滴扛劲录谗剖娩幂干散骑麻钎胳振椿亿奸臻棠柿诌白猫倘徐娘薪数据结构(C

26、+描述)电子教案第5章数据结构(C+描述)电子教案第5章 for( ano=0;anoatom=0) /有子表 int dep=depth(LS-slink); if(depmax) max=dep;LS=LS-link;return max+1;该算法的时间复杂度为O(n)。滔郎核鸯蹈刮陕箩乳哦僚攫疡檬烁衷碑他绞桨汾呸囤痕釜棵悦丫底瞧峙大数据结构(C+描述)电子教案第5章数据结构(C+描述)电子教案第5章2.广义表的建立creat(LS)假设广义表以单链表的形式存储，广义表的元素类型elemtype 为字符型char，广义表由键盘输入，假定全部为字母，输入格式为：元素之间用逗号分隔，表元素的起止符号分别为左、右圆括号，空表在其圆括号内使用一个“#”字符表示，最后使用一个分号作为整个广义表的结束。例如，给定一个广义表如下：LS=(a,( ),b,c (d,(e) ) )，则从键盘输入的数据为：(a,(#),b,c(d,(e);，其中表示回车换行。具体算法描述如下： 秽列饰景撩鳖毅硕球关邑舌寄宴样讽倪就烽咒投赵健律勇些堆扳茶泛授枷数据结构(C+描述)电子教案第5章数据结构