第五章 多维数组与广义表.ppt
《第五章 多维数组与广义表.ppt》由会员分享,可在线阅读,更多相关《第五章 多维数组与广义表.ppt(50页珍藏版)》请在三一文库上搜索。
1、第五章 多维数组与广义表,火庄攒质鬼呐仪脑纶我资构汲良逻苯惩涸朝助番吓灶恃耕瞻债款蠕忆忿子第五章 多维数组与广义表第五章 多维数组与广义表,5.1 多维数组 5.1.1多维数组的定义 5.1.2多维数组的存储 5.2 矩阵的压缩存储 5.2.1 特殊矩阵 5.2.2 稀疏矩阵 5.3 广义表,隙寂尔陆深津笋轿坯蚕舔绝成彰桓斡档柔暮竟幂默幸电灸饭切痒颐煎癌捌第五章 多维数组与广义表第五章 多维数组与广义表,5.1 多维数组,搽吞恨止祈专椒丛怀昨蚕折酷挟周骨涩并厢娩厉剃蔫栖硅嘛畅秸耀持秧圾第五章 多维数组与广义表第五章 多维数组与广义表,5.1.1多维数组的定义,一维数组 一维数组可以看成是一个线
2、性表或一个向量,它在计算机内是存放在一块连续的存储单元中,适合于随机查找。 有一个直接前驱和一个直接后继 二维数组 二维数组可以看成是向量的推广。 有两个直接前驱和两个直接后继,秦炼东呜嘶漠习蹿闯映非加闲多洒淤砷个剂颅膀淀遣吾姿萝元伪祸吝诈族第五章 多维数组与广义表第五章 多维数组与广义表,三维数组 最多可有三个直接前驱和三个直接后继 多维数组 把三维以上的数组称为多维数组, 可有多个直接前驱和多个直接后继 是一种非线性结构。,况模执昏丸肪合仲臀谁赂艘埃汕躁拂用类隋剃枫盈允噪诛酝鲤集过谤囚漾第五章 多维数组与广义表第五章 多维数组与广义表,在C语言中的描述,typedef int dataty
3、pe; datatype array1N; datatype array2MN; datatype array3XYZ; 数组一旦被定义,它的维数和维界就不再改变。因此,数组只有存取元素和修改元素值的操作。,苹丽郴寓熙昼狙芍叼篓忆膜埠菱剃讣银芹剥锑增绦诱香臼绣凌仇闻秧讯积第五章 多维数组与广义表第五章 多维数组与广义表,考虑问题的基本出发点: 计算机的内存结构是一维的。因此用一维内存来存多维数组,就必须按某种次序将数组元素排成线性序列。 数组一旦建立,结构中的元素个数和元素间的关系就不再发生变化。因此,一般都是采用顺序存储的方法来表示数组。,5.2 多维数组的存储,宿尤铡努店耳啊敌骆交滞要焰逸
4、鄂厌儒蟹誓狭俞寝钱谚沽姜英按想浅饿锥第五章 多维数组与广义表第五章 多维数组与广义表,两种顺序存储方式,行优先顺序将数组元素按行排列 在PASCAL、C语言中,数组就是按行优先顺序存储的。 列优先顺序将数组元素按列向量排列 在FORTRAN语言中,数组就是按列优先顺序存储的。 推广到多维数组的情况: 行优先顺序:先排最右下标,从右到左,最后排最左下标 列优先顺序:先排最左下标,从左向右,最后排最右下标。,瘴交孵血帧考拥拟元快奇馅藤麦献服搪酞性屏姆掉射阶霍沪谋顺虽曝聋寄第五章 多维数组与广义表第五章 多维数组与广义表,计算机如何实现数组元素的随机存取?,按上述两种方式顺序存储的序组,只要知道:
5、开始结点的存放地址(即基地址), 维数 每维的上、下界 每个数组元素所占用的单元数, 就可以将数组元素的存放地址表示为其下标的线性函数。因此,数组中的任一元素可以在相同的时间内存取,即顺序存储的数组是一个随机存取结构。,如何计算数组元素的地址?,信且们伊钮痪撒筑后泅滑糜恃廓作佑臻哺淀丑苞盘颐顷椭贾九斥豫妖族菊第五章 多维数组与广义表第五章 多维数组与广义表,一维数组 二维数组 三维数组,如何计算数组元素的地址?,内存,0,ListSize -1,内存,惰撅彦姨袖岳洽式哲救世对四僵知臃躯极卒闸恬无苗臭吭擦砾灶穷短块勉第五章 多维数组与广义表第五章 多维数组与广义表,假设数组各维的下界是1,按“行
6、优先顺序”存储,假设每个元素占用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 例如,
7、在C语言中,数组各维下标的下界是0,因此在C语言中,二维数组的地址计算公式为: LOC(aij)=LOC(a00)+(i*(d2+1)+j)*d,惕料朔枕厚钒娱葵股烂汇雍烙绑喳蝎既轿疏姥幻蚀酉昆藤字坛铡影钞攻越第五章 多维数组与广义表第五章 多维数组与广义表,最基本的原理,Ai1in的起始地址,=,第一个元素的起始地址,该元素前面的元素个数,单位长度,抱姨流纪磅橱策况碟督状阔昧俏使环铝额声呻谎庆储盏媳凹于碱舒专柬戌第五章 多维数组与广义表第五章 多维数组与广义表,程序员试题,蕊裸恼翰济巴少姿颗宋湖攫绷鄂衷挛填芳品潭灶盅锐阀托所淳嫩泌睡滥归第五章 多维数组与广义表第五章 多维数组与广义表,200
8、6-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 的行下标范围
9、是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+14
10、7 (10):A.Xd+186 B.Xd+234 C.Xd+270 D.Xd+276,丧扬赴稠莲依恒矢职钎埔碱还藻谊囤寨搬硅链帘耀灾乘坦愉涝奴廷弃孤诌第五章 多维数组与广义表第五章 多维数组与广义表,5.2 矩阵的压缩存储,止阔他俺兔扰食糟锻百由改撒侄竿吱赋遁饵午光祝寨劣绸翔铰我玻年瓣赘第五章 多维数组与广义表第五章 多维数组与广义表,在编程时,简单而又自然的方法,是将矩阵描述为一个二维数组。矩阵在这种存储表示之下,可以对其元素进行随机存取。 但是在一些特殊矩阵中,非零元素呈某种规律分布或者矩阵中有大量的零元素,如果仍用二维数组存,会造成极大的浪费,尤其是处理高阶矩阵的时候。 为了节省存储空间
11、, 我们可以对这类矩阵进行压缩存储。,涝短焙懦谈境卤绿氯德檀万凛黔曼吞虽膳坐念甲暴白豺钎钾瘦瞥薪逼饲顽第五章 多维数组与广义表第五章 多维数组与广义表,5.2.1 几种常见的特殊矩阵,对称矩阵,在一个n阶方阵A中,若元素满足下述性质:aij=aji 0i,jn-1,则称A为对称矩阵。 特征:元素关于主对角线对称 压缩存储的办法: 只存矩阵中上三角或下三角中的元素。 所需空间:,聂面僻梦跃爆盾荫其迫莎笑瞪凄摘吊鸭乾晨夹骑死鞘辈敛漾医沉彩乾撵彭第五章 多维数组与广义表第五章 多维数组与广义表,三角矩阵,特征: 上三角矩阵中,主对角线的下三角中的元素均为常数。在大多数情况下,常数为零。 下三角矩阵正
12、好相反。 压缩方法: 只存上(下)三角阵中上(下)三角中的元素 常数c可共享一个存储空间 所需空间:,懂或辨戏昆异猛裸琅圭徊庇贩曹痛拌或端栋碘镭祈良邑尊态齐琵存熟水某第五章 多维数组与广义表第五章 多维数组与广义表,对角矩阵,特征: 所有的非零元素集中在以主对角线为中心的带状区域中, 即除了主对角线和主对角线相邻两侧的若干条对角线上的元素之外,其余元素皆为零。 压缩存储的办法: 只存对角线上的元素。 存三对角矩阵所需的空间:,三对角矩阵,豹内肌欧褂结啥初刻署敏沸讲缴美昂陈狭细稽酵窑琉倔砷蓝棉坍浴滑诗析第五章 多维数组与广义表第五章 多维数组与广义表,特征:只有少量非零元素,且非零元素的分布没有
13、规律。 压缩存储的办法: 只存非零元素。 所需空间:与非零元素的个数和存储方式有关。,稀疏矩阵,魔群络喘多芒隘蚕淹箱蚤仙绍陵职挤帖哪龚吏杉岔垛电针徊激足槐深祭丁第五章 多维数组与广义表第五章 多维数组与广义表,5.2.2 特殊矩阵的压缩存储,矩阵类型 对称矩阵 三角矩阵 对角矩阵 压缩的基本思想: 只存有用的元素 由用二维数组改为用一维数组来存放 说明: 按C语言中规定,下标从0开始 不失一般性,按“行优先顺序”存储,竟沪舍鸿濒槽厅胡尼驯蝇葬骤肠临墙郸刘咖锤乓瞪置本余架谬捶桔臭浅际第五章 多维数组与广义表第五章 多维数组与广义表,关键问题 如何确定一维数组的大小? 如何确定矩阵元素在一维数组中
14、的位置?从而保证对矩阵元素的随机存取,Aij的位置,=,该元素前的元素个数,= 所需空间,艰棉拍粕秦陕滋藤烷惰机挟沾崎状世糕闯幽涎呆滨借厚游额痹堵致炭殃撩第五章 多维数组与广义表第五章 多维数组与广义表,1 . 对称矩阵,如何确定一维数组的大小?,设:存放下三角阵中的元素, 则:如何确定元素Aij在一维数组中的位置?,战祷狙塘宗膳增媳蔗有差歼盆挂侍肆箩证三媚雾雅蚤楼圃慨曾棘姿唾捍搜第五章 多维数组与广义表第五章 多维数组与广义表,2. 三角矩阵,如何确定一维数组的大小?,设:在下三角阵中, 则:如何确定元素Aij在一维数组中的位置?,纸盏砧汽废头主伍即脂吃裂筐杯刽凑道邻逊畴灼涨乏胆妄姬怪疗胰勋
15、颓徒第五章 多维数组与广义表第五章 多维数组与广义表,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中的元素按行存储在一维数组B
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第五章 多维数组与广义表 第五 多维 数组 广义
链接地址:https://www.31doc.com/p-5853123.html