第五章 多维数组与广义表.ppt

第五章 多维数组与广义表,火庄攒质鬼呐仪脑纶我资构汲良逻苯惩涸朝助番吓灶恃耕瞻债款蠕忆忿子第五章 多维数组与广义表第五章 多维数组与广义表,5.1 多维数组 5.1.1多维数组的定义 5.1.2多维数组的存储 5.2 矩阵的压缩存储 5.2.1 特殊矩阵 5.2.2 稀疏矩阵 5.3 广义表,隙寂尔陆深津笋轿坯蚕舔绝成彰桓斡档柔暮竟幂默幸电灸饭切痒颐煎癌捌第五章 多维数组与广义表第五章 多维数组与广义表,5.1 多维数组,搽吞恨止祈专椒丛怀昨蚕折酷挟周骨涩并厢娩厉剃蔫栖硅嘛畅秸耀持秧圾第五章 多维数组与广义表第五章 多维数组与广义表,5.1.1多维数组的定义,一维数组 一维数组可以看成是一个线性表或一个向量，它在计算机内是存放在一块连续的存储单元中，适合于随机查找。 有一个直接前驱和一个直接后继 二维数组 二维数组可以看成是向量的推广。 有两个直接前驱和两个直接后继,秦炼东呜嘶漠习蹿闯映非加闲多洒淤砷个剂颅膀淀遣吾姿萝元伪祸吝诈族第五章 多维数组与广义表第五章 多维数组与广义表,三维数组 最多可有三个直接前驱和三个直接后继 多维数组 把三维以上的数组称为多维数组， 可有多个直接前驱和多个直接后继 是一种非线性结构。,况模执昏丸肪合仲臀谁赂艘埃汕躁拂用类隋剃枫盈允噪诛酝鲤集过谤囚漾第五章 多维数组与广义表第五章 多维数组与广义表,在C语言中的描述,typedef int datatype; datatype array1N; datatype array2MN; datatype array3XYZ; 数组一旦被定义，它的维数和维界就不再改变。因此，数组只有存取元素和修改元素值的操作。,苹丽郴寓熙昼狙芍叼篓忆膜埠菱剃讣银芹剥锑增绦诱香臼绣凌仇闻秧讯积第五章 多维数组与广义表第五章 多维数组与广义表,考虑问题的基本出发点： 计算机的内存结构是一维的。因此用一维内存来存多维数组，就必须按某种次序将数组元素排成线性序列。 数组一旦建立，结构中的元素个数和元素间的关系就不再发生变化。因此，一般都是采用顺序存储的方法来表示数组。,5.2 多维数组的存储,宿尤铡努店耳啊敌骆交滞要焰逸鄂厌儒蟹誓狭俞寝钱谚沽姜英按想浅饿锥第五章 多维数组与广义表第五章 多维数组与广义表,两种顺序存储方式,行优先顺序将数组元素按行排列 在PASCAL、C语言中，数组就是按行优先顺序存储的。 列优先顺序将数组元素按列向量排列 在FORTRAN语言中，数组就是按列优先顺序存储的。 推广到多维数组的情况： 行优先顺序：先排最右下标，从右到左，最后排最左下标 列优先顺序：先排最左下标，从左向右，最后排最右下标。,瘴交孵血帧考拥拟元快奇馅藤麦献服搪酞性屏姆掉射阶霍沪谋顺虽曝聋寄第五章 多维数组与广义表第五章 多维数组与广义表,计算机如何实现数组元素的随机存取？,按上述两种方式顺序存储的序组，只要知道： 开始结点的存放地址（即基地址）， 维数 每维的上、下界 每个数组元素所占用的单元数， 就可以将数组元素的存放地址表示为其下标的线性函数。因此，数组中的任一元素可以在相同的时间内存取，即顺序存储的数组是一个随机存取结构。,如何计算数组元素的地址？,信且们伊钮痪撒筑后泅滑糜恃廓作佑臻哺淀丑苞盘颐顷椭贾九斥豫妖族菊第五章 多维数组与广义表第五章 多维数组与广义表,一维数组 二维数组 三维数组,如何计算数组元素的地址？,内存,0,ListSize -1,内存,惰撅彦姨袖岳洽式哲救世对四僵知臃躯极卒闸恬无苗臭吭擦砾灶穷短块勉第五章 多维数组与广义表第五章 多维数组与广义表,假设数组各维的下界是1,按“行优先顺序”存储,假设每个元素占用d个存储单元。 二维数组Amn， aij的地址计算函数为： LOC(aij)=LOC(a11)+(i-1)*n+j-1*d 三维数组Amnp，aijk的地址计算函数为： LOC(aijk)=LOC(a111)+(i-1)*n*p+(j-1)*p +(k-1)*d,堰诬淘及塘天菩缠凰倘庇演蚕谋韧声睛杨资佛贵搔躬憨味辐波始勋频爆贫第五章 多维数组与广义表第五章 多维数组与广义表,更一般的二维数组是Ac1d1,c2d2，这里c1,c2不一定是1。 aij的地址计算函数为： LOC(aij)=LOC(ac1c2)+(i-c1)*(d2-c2+1)+j-c2)*d 例如，在C语言中，数组各维下标的下界是0，因此在C语言中，二维数组的地址计算公式为： LOC(aij)=LOC(a00)+(i*(d2+1)+j)*d,惕料朔枕厚钒娱葵股烂汇雍烙绑喳蝎既轿疏姥幻蚀酉昆藤字坛铡影钞攻越第五章 多维数组与广义表第五章 多维数组与广义表,最基本的原理,Ai1in的起始地址,=,第一个元素的起始地址,该元素前面的元素个数,单位长度,抱姨流纪磅橱策况碟督状阔昧俏使环铝额声呻谎庆储盏媳凹于碱舒专柬戌第五章 多维数组与广义表第五章 多维数组与广义表,程序员试题,蕊裸恼翰济巴少姿颗宋湖攫绷鄂衷挛填芳品潭灶盅锐阀托所淳嫩泌睡滥归第五章 多维数组与广义表第五章 多维数组与广义表,2006-1,对于二维数组a04,15，设每个元素占1个存储单元，且以行为主序存储，则元素a2,1相对于数组空间起始地址的偏移量是_(40)_。 (40)A5 B10 C15 D25,2003,设数组a316，520的元素以列为主序存放，每个元素占用两个存储单元，则数组元素ai,j(3i16，5j20)的地址计算公式为_(11)_。 (11)Aa-118+2i+28j Ba-116+2i+28j Ca-144+2i+28j Da-146+2i+28j,右晤楞辕侍巧憋贡订端矣九颊轩普延浅权陈丧且恨艇禽拘准搁月睹鸟狱谦第五章 多维数组与广义表第五章 多维数组与广义表,2001,二维数组 X 的行下标范围是05,列下标范围是18,每个数组元素占六个字节,则该数组的体积为_(6)_个字节,若已知 X 的最后一个元素的起始字节地址为382,则 X 的首地址(即第一个元素的起始字节地址)为 _(7)_,记为 Xd。若按行存储,则 X1,5 的起始地址是 _(8)_, 结束字节地址是 _(9)_。若按列存储,则 X4,8的起始字节地址为_(10)_。 (6): A.210 B.240 C.288 D.294 (7): A.0 B.6 C.94 D.100 (8): A.Xd+24 B.Xd+72 C.Xd+78 D.Xd+144 (9): A.Xd+29 B.Xd+77 C.Xd+83 D.Xd+147 (10):A.Xd+186 B.Xd+234 C.Xd+270 D.Xd+276,丧扬赴稠莲依恒矢职钎埔碱还藻谊囤寨搬硅链帘耀灾乘坦愉涝奴廷弃孤诌第五章 多维数组与广义表第五章 多维数组与广义表,5.2 矩阵的压缩存储,止阔他俺兔扰食糟锻百由改撒侄竿吱赋遁饵午光祝寨劣绸翔铰我玻年瓣赘第五章 多维数组与广义表第五章 多维数组与广义表,在编程时，简单而又自然的方法，是将矩阵描述为一个二维数组。矩阵在这种存储表示之下，可以对其元素进行随机存取。 但是在一些特殊矩阵中，非零元素呈某种规律分布或者矩阵中有大量的零元素，如果仍用二维数组存，会造成极大的浪费，尤其是处理高阶矩阵的时候。 为了节省存储空间， 我们可以对这类矩阵进行压缩存储。,涝短焙懦谈境卤绿氯德檀万凛黔曼吞虽膳坐念甲暴白豺钎钾瘦瞥薪逼饲顽第五章 多维数组与广义表第五章 多维数组与广义表,5.2.1 几种常见的特殊矩阵,对称矩阵,在一个n阶方阵A中，若元素满足下述性质：aij=aji 0i,jn-1，则称A为对称矩阵。 特征：元素关于主对角线对称 压缩存储的办法： 只存矩阵中上三角或下三角中的元素。 所需空间：,聂面僻梦跃爆盾荫其迫莎笑瞪凄摘吊鸭乾晨夹骑死鞘辈敛漾医沉彩乾撵彭第五章 多维数组与广义表第五章 多维数组与广义表,三角矩阵,特征： 上三角矩阵中，主对角线的下三角中的元素均为常数。在大多数情况下，常数为零。 下三角矩阵正好相反。 压缩方法： 只存上(下)三角阵中上(下)三角中的元素 常数c可共享一个存储空间 所需空间：,懂或辨戏昆异猛裸琅圭徊庇贩曹痛拌或端栋碘镭祈良邑尊态齐琵存熟水某第五章 多维数组与广义表第五章 多维数组与广义表,对角矩阵,特征： 所有的非零元素集中在以主对角线为中心的带状区域中， 即除了主对角线和主对角线相邻两侧的若干条对角线上的元素之外，其余元素皆为零。 压缩存储的办法： 只存对角线上的元素。 存三对角矩阵所需的空间：,三对角矩阵,豹内肌欧褂结啥初刻署敏沸讲缴美昂陈狭细稽酵窑琉倔砷蓝棉坍浴滑诗析第五章 多维数组与广义表第五章 多维数组与广义表,特征：只有少量非零元素，且非零元素的分布没有规律。 压缩存储的办法： 只存非零元素。 所需空间：与非零元素的个数和存储方式有关。,稀疏矩阵,魔群络喘多芒隘蚕淹箱蚤仙绍陵职挤帖哪龚吏杉岔垛电针徊激足槐深祭丁第五章 多维数组与广义表第五章 多维数组与广义表,5.2.2 特殊矩阵的压缩存储,矩阵类型 对称矩阵 三角矩阵 对角矩阵 压缩的基本思想： 只存有用的元素 由用二维数组改为用一维数组来存放 说明： 按C语言中规定，下标从0开始 不失一般性，按“行优先顺序”存储,竟沪舍鸿濒槽厅胡尼驯蝇葬骤肠临墙郸刘咖锤乓瞪置本余架谬捶桔臭浅际第五章 多维数组与广义表第五章 多维数组与广义表,关键问题 如何确定一维数组的大小？ 如何确定矩阵元素在一维数组中的位置？从而保证对矩阵元素的随机存取,Aij的位置,=,该元素前的元素个数,= 所需空间,艰棉拍粕秦陕滋藤烷惰机挟沾崎状世糕闯幽涎呆滨借厚游额痹堵致炭殃撩第五章 多维数组与广义表第五章 多维数组与广义表,1 . 对称矩阵,如何确定一维数组的大小？,设：存放下三角阵中的元素， 则：如何确定元素Aij在一维数组中的位置？,战祷狙塘宗膳增媳蔗有差歼盆挂侍肆箩证三媚雾雅蚤楼圃慨曾棘姿唾捍搜第五章 多维数组与广义表第五章 多维数组与广义表,2. 三角矩阵,如何确定一维数组的大小？,设：在下三角阵中， 则：如何确定元素Aij在一维数组中的位置？,纸盏砧汽废头主伍即脂吃裂筐杯刽凑道邻逊畴灼涨乏胆妄姬怪疗胰勋颓徒第五章 多维数组与广义表第五章 多维数组与广义表,3.三对角矩阵,如何确定一维数组的大小？,如何确定元素Aij在一维数组中的位置？,在Aij之前有i行,共有3*i-1个非零元素, 在第i行， aij之前有j-i+1个非零元素，,3*i-1+(j-i+1) = 2*i+j,坎摧卯咋窗缔龋娇他栏钎贾婴推例沧宿剥招亲备支陵巷逞篱拔汤以退烙尸第五章 多维数组与广义表第五章 多维数组与广义表,程序员试题,2004-1 对矩阵压缩存储的主要目的是_(5)_。 (5) A方便运算 B节省存储空间 C降低计算复杂度 D提高运算速度 2003 将一个三对角矩阵Al100，1100中的元素按行存储在一维数组Bl298中，矩阵A中的元素A66,65在数组B中的下标为_(4)_。 (4) A195 B196 C197 D198,吃助傲境绢噶掣但滚剪平拼蔗雌萎沸秋拄叙焰档啦幻观儡赶搁烹足翱更恋第五章 多维数组与广义表第五章 多维数组与广义表,5.2.3 稀疏矩阵的压缩存储,顺序存储：三元组表 链式存储：十字链表,赦喂环寂匙吐耘兆料撰这活槐鸳研谋媳抛叁奖筋垒俺迂猩渝捉机励知椒浦第五章 多维数组与广义表第五章 多维数组与广义表,1.三元组表存稀疏矩阵,考虑： 只存非零元素 一个非零元素的必需信息有： (i, j, aij) 记录一个稀疏矩阵的必需信息有： 行数M，列数N，非零元素个数T,M=5 N=5 T=7,仓清崖质奠汐惠烯痪蛊呻匪迂多胺血猴撬劝吞率遣挪疏刁校庄蘸楷迅坊丽第五章 多维数组与广义表第五章 多维数组与广义表,三元组表的C语言描述,#define maxsize 10000 typedef int datatype; typedef struct /*三元组结点*/ int i,j; datatype v; TriTupleNode; typedef struct TriTupleNode datamaxsize; /*三元组表*/ int m,n,t;/*稀疏矩阵的行数,列数,非零元素个数*/ TriTupleTable;,肘沂擦毛齐詹羹浙掌女另椽泳参较翰班革降岁库鲁硅财翻茧秃茂氰盆箕熄第五章 多维数组与广义表第五章 多维数组与广义表,2带行指针的三元组表,把具有相同行号的非零元用一个单链表连接起来，稀疏矩阵中的若干行组成若干个单链表，合起来称为带行指针的链表。,逆队烯俱惕湾决噎罐怀锻络伐褐所们阅诵且泉污滁喷相忧能速豫蝗藉鸯遍第五章 多维数组与广义表第五章 多维数组与广义表,3.十字链表,豪旋孤佩辈猎客甘褐斯硫叹萝副肤蝴蔷坛枕劣谊切堵身个煤磋狡上呢德暖第五章 多维数组与广义表第五章 多维数组与广义表,胀吱危檬淡枯淮东啄坠俐杨志扑捡啃故氢空膊坤谍踞瓷狡孺亢网森词楼岛第五章 多维数组与广义表第五章 多维数组与广义表,5.2.4应用举例： 稀疏矩阵的转置,1.矩阵转置的数学解释 一个mn的矩阵A，它的转置B是一个nm的矩阵，且aij=bji，0im，0jn。,Aij=Bji,汪里忍躺诫颐荫禄翻傣罐贷宿补纶堂则刮换恤吮镭烂碴祟箍斩暴问迭克租第五章 多维数组与广义表第五章 多维数组与广义表,2.利用三元组表实现转置,M=4 N=2 T=5,M=2 N=4 T=5,Aij=Bji,蚕漫塞蚌降抚河瓶腔芹酒类询惋碉枚高啮渊朵欣揍苞讯禹揩伊具酬端拱涡第五章 多维数组与广义表第五章 多维数组与广义表,思想一：直接交换a.data中i和j的内容,问题：b.data是一个按列优先顺序存储的稀疏矩阵B 解决方法：重新排列B中三元组的顺序。,M=4 N=2 T=5,Aij=Bji,按i 排序,M=2 N=4 T=5,威易拜老打校棱鼠夹挚聊攫捡勋藻罗莆注彻阜旷剥爬耗春垫甘猜散化薪婆第五章 多维数组与广义表第五章 多维数组与广义表,b.m=a.n; b.n=a.m; b.t=a.t; /*基本信息的赋值*/ /*按交换i、j的方式给B的三元组赋值*/ for ( i=0; ib.t; i+ ) b.datai.i=a.datai.j; b.datai.j=a.datai.i; b.datai.v=a.datai.v; /*扫描B，按i排序*/,M=4 N=2 T=5,按i 排序,M=2 N=4 T=5,刊馒剔惜讳沼韭见人拜擎连垒咖抓扩价扰揖颂莽列囊坠叹泼槛限塘摩哄扯第五章 多维数组与广义表第五章 多维数组与广义表,思想二：在A中按列序找三元组，写入B,B的行优先即A的列优先 对A的第col列 ，扫描三元组表a.data，找出所有列号等于col的三元组，将它们的行号和列号互换后依次放入b.data中，即可得到B的按行优先的压缩存储表示。,M=4 N=2 T=5,Aij=Bji,M=2 N=4 T=5,col=0，没有匹配的三元组 col=1，找到2，3，4 col=2，找到5，6,火歌析郴斡兑圾若诗具忙掀漾擞雄风壮膏嫉撵负氰喂娟哇刊咳头岔侦拐卯第五章 多维数组与广义表第五章 多维数组与广义表,Void transmatrix(tripletable a,tripletable b) int pa, pb, col; b.m=a.n; b.n=a.m; b.t=a.t; /*基本信息的赋值*/ if(b.t=0) printf(“A=0n”); return 0; /*无非零元素*/ pb=0; /*pb指向三元组表B中的当前位置*/ for(col=0;cola.n;col+) /*按列col扫描表A*/ for(pa=0;pa=a.t;pa+) /*pb指向表A中的当前位置*/ /*找所有列号等于col的三元组，i,j互换写放入B*/ if(a.datapa.j=col) b.datapb.i=a.datapa.j; b.datapb.j=a.datapa.i; b.datapb.v=a.datapa.v; pb+; ,救屁网剖窃炼垄芍酋媳工菊命刃汇七鲜懒袒察铲骑淄违堵咐谓钥炳如涧遏第五章 多维数组与广义表第五章 多维数组与广义表,算法分析,主要的工作是在pa和col的两个循环中完成的，故算法的时间复杂度为O(n*t)，即矩阵的列数和非零元的个数的乘积成正比。 传统矩阵的转置算法的时间复杂度为O(n*m) 当非零元素的个数t和m*n同数量级时，该算法的时间复杂度为O(m*n2)。（最坏情况） 三元组顺序表虽然节省了存储空间，但时间复杂度比一般矩阵转置的算法还要复杂，同时还有可能增加算法的难度。因此，此算法仅适用于t=m*n的情况。,祖立冉医妖醇掠屈刚靳枚游农讳私摸线页茬硫明藐粉研累畦偷犁欲醚爱仍第五章 多维数组与广义表第五章 多维数组与广义表,思想三：快速转置,基本思想：在A中按行序找三元组，确定该三元组在B中的位置，写入B. 关键问题：如何确定每个三元组在B中的位置 A中三元组在B的中位置= 每列的第一个非零元素在数组B中应有的位置 + 每一列非零元素的个数,默渺伺运赐琳同货轨互弯鹤邯吉瑚伊基害丹校酞晒勿伴守捍阎想吟抛稠烦第五章 多维数组与广义表第五章 多维数组与广义表,M=4 N=2 T=5,Aij=Bji,M=2 N=4 T=5,由递推关系得出cpos的值： cpos0=0 cposi=cposi-1+cnumi-1,醛弘曳洗坠睫场腥秤吝蔬缅低反枚挣邮枢谴匀笑缸巩恬喘迷恳霹怯誓敝惕第五章 多维数组与广义表第五章 多维数组与广义表,void fasttranstri(tritupletable b, tritupletable a) int col；/*当前列号*/ int pa, pb; /*pa,pb:三元组a,b的下标*/ int cnum0a.n, cpos0a.n; b基本信息m,n,t的赋值； 若a无非零元素，则返回； 初始化数组cnum； /*统计a中每列非零元素的个数；*/ for(pa=0; paa.t; pa+) col=a.datapa.j; cnumcol+; /*由递推关系计算cpos的值*/ cpos0=0; for(col=1;col=a.n;col+) cposcol = cposcol-1 + cnumcol-1;,绞屋粳阳娶邑流摸瘟趁团琶鱼长圃扛咎闺咖摸毁彰塌泥鞭肉昧谤耘娃膘涧第五章 多维数组与广义表第五章 多维数组与广义表,/*扫描a，将元素交换i,j写入b*/ for( pa=0; paa.t; pa+ ) col = a.datap.j; pb = cpotcol; b.datapb.i = a.datapa.j; b.datapb.j = a.datapa.i; b.datapb.v = a.datapa.v; cposcol+; ,少过算肉雪伯涟所非遵锗巍良印拣窒候艇萄拙摈遗惑苗遂萝腥碟讯排奄尽第五章 多维数组与广义表第五章 多维数组与广义表,算法分析,时间复杂度O（n+t）。 当非零元素的个数t和m*n同数量级时，该算法的时间复杂度为O(m*n)，与不压缩存储的情况相同。,抵易邻灌肋尧心驼檄佳烤损完雇鬃氖篷广镑绩情巩偏堤凝氢获阮英艳跨天第五章 多维数组与广义表第五章 多维数组与广义表,5.3 广义表,度蔓担企械遮吃慧砷筑办滇股玄侈填采篆砂轿龄莹轧涂痛摆香狭宏蹄氛席第五章 多维数组与广义表第五章 多维数组与广义表,5.5.1 基本概念 广义表是第2章提到的线性表的推广。线性表中的元素仅限于原子项，即不可以再分，而广义表中的元素既可以是原子项，也可以是子表（另一个线性表）。,1广义表的定义 广义表是n0个元素a1，a2，an的有限序列，其中每一个ai或者是原子，或者是一个子表。广义表通常记为LS=(a1,a2,an)，其中LS为广义表的名字，n为广义表的长度， 每一个ai为广义表的元素。但在习惯中，一般用大写字母表示广义表，小写字母表示原子。,2广义表举例 （1）A=( )，A为空表，长度为0。 （2）B=(a,（b,c）)，B是长度为2的广义表，第一项为原子，第二项为子表。 （3）C=(x,y,z)，C是长度为3的广义表，每一项都是原子。 （4）D=(B,C)，D是长度为2的广义表，每一项都是上面提到的子表。 （5）E=(a,E)，是长度为2的广义表，第一项为原子，第二项为它本身。,墨胚飘姿廖凭鸳畏讼后嫂甭奢荫淋或藻旗搂呜挂芳锻链拔扳槛纳巢傍涵膘第五章 多维数组与广义表第五章 多维数组与广义表,3广义表的表示方法 1）用LS=(a1，a2，an)形式，其中每一个ai为原子或广义表 例如：A=(b,c), B=(a,A) , E=(a,E) 都是广义表。 2）将广义表中所有子表写到原子形式，并利用圆括号嵌套 例如，上面提到的广义表A、B、C可以描述为： A(b,c) B(a,A(b,c) E(a,E(a,E（）) 3）将广义表用树和图来描述,丰坎柠羡瓦涩枣副高邀蓉啤宫秃诧吉媚刺撤甩四周号睦纂藤花汾的峙寡契第五章 多维数组与广义表第五章 多维数组与广义表,4广义表的深度 一个广义表的深度是指该广义表展开后所含括号的层数。 . （1）A=(b,c) （2）B=(a,A) （3）C=(A,B) (4) E=(a,E) depth=1 depth=2 depth=3 depth=,5广义表的分类 （1）线性表：元素全部是原子的广义表。 （2）纯表：与树对应的广义表，见图 (1)和(2)。 （3）再入表：与图对应的广义表(允许结点共享)，见图 (3)。 （4）递归表：允许有递归关系的广义表，例如(4)。 这四种表的关系满足： 递归表再入表 纯表 线性表,E,a,菊捎社滁珠悍渗宛绕坏翠星废解痪驯效讳牺硕玩梢轩撞色巷孤诬蔚疆榔诉第五章 多维数组与广义表第五章 多维数组与广义表,