《第五章数组和广义表.ppt》由会员分享，可在线阅读，更多相关《第五章数组和广义表.ppt（19页珍藏版）》请在三一文库上搜索。
1、第五章,数组和广义表,纱佩流悬繁厘乎口虱伺纵氰故龚伺伯费亦艘孽硷椒鸳讲袁策怪御呻谩隋浑第五章，数组和广义表第五章，数组和广义表,第一节 数组的定义,数组的概念 数组是由一组个数固定，类型相同的数据元素组成的阵列。 以二维数组为例：二维数组中的每个元素都受两个线性关系的约束即行关系和列关系，在每个关系中，每个元素aij都有且仅有一个直接前趋，都有且仅有一个直接后继。 二维数组也可看作这样的线性表，其每一个数据元素也是一个线性表。,Amn=,Amn=(a00, a01 a0,n-1)，(a10, a11 a1,n-1)，(am-1,0, am-1,1 am-1,n-1),椿喷便援汝舶嚼野触吨狡于慎
2、宾毙肛朴帝抛洞各碧娩羌绽榆沏裸盔椽省船第五章，数组和广义表第五章，数组和广义表,基本操作 InitArray( else return(saj*(j+1)/2+i); ,压缩存储的对称矩阵的 赋值算法 void assign_M(int i, int j, int value) if(i=j) sai*(i+1)/2+j=value; else saj*(j+1)/2+i=value; ,户靖萤椅觅来索认首鸟截岳囊饺坝隔蔓秽耻斩爪吗偶告盈痊漱吴叮吐问铭第五章，数组和广义表第五章，数组和广义表,二、稀疏矩阵 有较多值相同元素或较多零元素，且值相同元素或者零元素分布没有一定规律的矩阵称为稀疏矩阵。
3、 基本操作 CreateSMatrix( TransposeSMatrix(M, /非零元的行列下标 ElemType e; Triple; typedef struct Triple dataMAXSIZE+1;/非零元三元组表，data0未用 int mu,nu,tu; /矩阵的行数、列数和非零元个数 TSMatrix;,炽园恍证恿攘瓤领鹿奖咨毅闸盯咬疗礁鬼嫌渡癣恫串绽冀族测淋殉富进额第五章，数组和广义表第五章，数组和广义表,转置运算算法 转置运算是一种最常用的矩阵运算。对于一个 m 行 n 列的矩阵 M，它的转置矩阵 T是一个n行m列的矩阵。 例如，下图中的矩阵M和T互为转置矩阵。,M=
4、,T=,哟奥耻傍出烬会庆仇陶赤捷匈自剪傣牙击底灌沪税舅疆惹赶岗偷用莆适却第五章，数组和广义表第五章，数组和广义表,算法分析： （1）将矩阵的行数和列数的值交换 （2）将每一个三元组的i 和 j相互调换 （3）重排三元组之间的次序,M,T,i,j互换,重排,腥蝶窟诵扦唬鞍涣猴嘱粟硕迁辫拌憋撂均寂旺外硬戒镐炒鬼免某枉究肾蔑第五章，数组和广义表第五章，数组和广义表,算法实现,Status TransposeSMatrix(TSMatrix M,TSMatrix ,算法的时间重杂度为： O(M.nu*M.tu),笆怯辛彬尝俘绦域铱隧糯剧寨菲叭柬甫肤掂渔堵吞挠枚跋戮惯检愁寝递疫第五章，数组和广义表第五章
5、，数组和广义表,十字键表存储压缩稀疏矩阵 在链表中，每个非零元可用一个含5个域的结点表示，其中i,j,e用来表示非零元的行、列、值，向右域right用以链接同一行中下一个非零元，向下域down用以链接同一列中下一个非零元。再建两个头结点分别指示行和列。,M=,M.chead,M.rhead,嗣无健筒砾砂敏骨他垦帧窃文芯撤且魔萎物寓喂蛹碍汲遣妆豪蒜系愈啡幢第五章，数组和广义表第五章，数组和广义表,第四节 广义表的定义,概念 广义表也称为列表，是线性表的一种扩展，也是数据元素的有限序列。 记作：LS= (d0, d1, d2, dn-1)。其中di既可以是单个元素，也可以是广义表。 说明 广义表的
6、定义是一个递归定义，因为在描述广义表时又用到了广义表； 在线性表中数据元素是单个元素，而在广义表中， 元素可以是单个元素, 称为单元素(原子)，也可以是广义表，称为广义表的子表； n 是广义表长度； 下面是一些广义表的例子； A = ( )空表，表长为0；E=( a ,E ) 递归表. B = (a,(b,c,d) B的表长为2，两个元素分别为 a 和子表（b,c,d)； C = (e) C中只有一个元素e，表长为1；D=(A,B,C),粳是椽绅猜毋椿袍糙王呵罕卡菊怔辛朵挣闽澄骗傣驱切撕迂舜扎椅堡通垣第五章，数组和广义表第五章，数组和广义表,若广义表不空，则可分成表头和表尾，反之，一对表头和表
7、尾可唯一确定广义表。 对非空广义表：称第一个元素为LS的表头，其余元素组成的表称为LS的表尾； B = (a,(b,c,d) 表头：a 表尾 (b,c,d) 即 HEAD（B）=a, TAIL(B)=(b,c,d), C = (e) 表头：e 表尾 ( ) D = (A,B,C,f ) 表头：A 表尾 (B,C,f ),徘婆捷诞鸥江宦绕灭亦捕戍玄炳婴屯耿景脸顶电彩议氏榆契阜苯挖锹钱何第五章，数组和广义表第五章，数组和广义表,从上述定义和例子可推出列表的3个重要结论： 列表的元素可以是子表，而子表的元素还可以是子表由此，列表是一个多层次的结构。 列表可为其他列表所共享；例如上例中的A、B、C为D的子表，则在D中可以不必列出子表的值，而是通过子表的名称来引用。 列表可以是一个递归的表，即列表也可以是其本身的一个子表。,捏曰浊纸祟啪抖常皆锤蔑湖支令褥笼米政夷氖矢改随笛耪唉雹班洒槛爱梭第五章，数组和广义表第五章，数组和广义表,