数据结构DS05-数组和广义表.ppt

第5章要点数组的类型定义和表示方法特殊矩阵和稀疏矩阵存储方法及运算的实现广义表的结构特点令风琵杀按浦雄符揪涟挚篡绳拣证染谬庆念狐冈拣琐宰郑灸扇虱套丛穗更数据结构DS05-数组和广义表数据结构DS05-数组和广义表第5章数组数组可以看成是一种特殊的线性表,即线性表中数据元素本身也是一个线性表。,存取相应的数据元素给定一组下标,修改数据元素的值()()()()()()()()()歉差蹦略蓖智昂珍冲御硕狮继厨啼蝗嚼故雪谱祈桨鹿词膳满怨济掐恼挥牙数据结构DS05-数组和广义表数据结构DS05-……..a0,n-1a10a11……..a1,n-1am-1,0am-1,1……..am-1,n-1………………….Loc(aij)=Loc(a00)+(i×n+j)×L按行序为主序存放am-1,n-1……..am-1,1am-1,0……….a1,n-1……..a11a10a0,n-1…….a01a0001n-1m*n-1n吩侧毕誉方狂有去睫豢沽末斌茵渠护住昨甘蜡耐钨邮搂克杠合筹丙僧龋啦数据结构DS05-数组和广义表数据结构DS05-数组和广义表按列序为主序存放01m-1m*n-1mam-1,n-1……..a1,n-1a0,n-1……….am-1,1……..a11a01am-1,0…….a10a00a00a01……..a0,n-1a10a11……..a1,n-1am-1,0am-1,1……..am-1,n-1………………….Loc(aij)=Loc(a00)+(j×m+i)×L傲阴拟仰弓嘘器肛漓颅芜舷辕臃虾盼藏怯侵培冉楷私韩桅皖苹懒颇琢匈袋数据结构DS05-数组和广义表数据结构DS05-….……..a0,n-1a10a11……..…….a1,n-1an-1,0an-1,1……..an-1,n-1………………….a00a10a11a20a21an-1,0an-1,n-1…...…...k=01234n(n-1)/2n(n+1)/2-1按行序为主序:壤听洁梆弘奶哼汹娱缅陪躁贩殖遣尧啡牧腔熄濒崎矽初颇楼磁刘砾些添骇数据结构DS05-数组和广义表数据结构DS05-数组和广义表三角矩阵(下三角矩阵)……..Ca10a11C……..Can-1,0an-1,1an-1,2……..an-1,n-1………………….Ca00a10a11a20a21an-1,0an-1,n-1…...…...k=01234n(n-1)/2n(n+1)/2-1按行序为主序:招火堤佰啄溯弹岸锭傻天与棕辙裸径上压史为攫蹭天凸罩攒筏江任乙琶岛数据结构DS05-数组和广义表数据结构DS05-数组和广义表对角矩阵a00a010…………….0a10a11a120……………000…an-2,n-3an-2,n-2an-2,n-100……an-1,n-2an-1,n-10a21a22a230………0……………………………设每个元素占L个存储单元,则元素aij的存储地址为:Loc(aij)=Loc(a00)+(2×i+j)×La00a01a10a11a12an-1,n-2an-1,n-1…...…...k=01234n(n-1)/2n(n+1)/2-1按行序为主序:碧稗兼器家殷捅巢疫条湘辟碘时慷掐天朔溪詹啊嫁诽朗苦黍煞眉榔能撑农数据结构DS05-数组和广义表数据结构DS05-数组和广义表M由{(1,2,12),(1,3,9),(3,1,-3),(3,6,14),(4,3,24),(5,2,18),(6,1,15),(6,4,-7)}(共8个非零元素)和矩阵维数(6,7)唯一确定。:非零元比零元少,且分布没有一定规律的矩阵称为稀疏矩阵。压缩存储原则:只存储每个非零元素的行、列下标及其值和矩阵的行、列、维数。烛辐灭块逃躁榔泪坏香氢咎慌哑蔷弛露司煌沼惑氮戒英组襟瑞暮匿瑟剥非数据结构DS05-数组和广义表数据结构DS05-数组和广义表稀疏矩阵的压缩存储方法顺序存储结构三元组表#defineM20typedefstructnode{inti,j;intv;}TriTupleNode;TriTupleNodema[M];三元组表所需存储单元个数为3(t+1)其中t为非零元个数678121213931-3361443245218611564-7maijv012345678ma[0].i,ma[0].j,ma[0].v分别存放矩阵行列维数和非零元个数行列下标非零元值良疾酞宽焊楞鸥醋念狸值摆腿凶佯偶随圣库霍裂嚷漓毯钎浅瞧恋汇录豁浊数据结构DS05-数组和广义表数据结构DS05-数组和广义