资源描述：
《5数组和广义表.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、数据结构5数组和广义表15数组和广义表主要内容数组的类型定义数组的顺序表示和实现矩阵的压缩存储特殊矩阵稀疏矩阵广义表25数组和广义表什么是数组数组连续空间每个单元类型相同静态分配空间数组大小、元素类型在使用前必须先定义一旦确定不得更改01234567单元编号（下标）存储空间35数组和广义表一维数组一维数组线性而非平面声明<数据类型><变量名>[数组大小];intNumberA[10];45数组和广义表一维数组intNumberA[10];int：每个数组单元的类型为整型NumberA：这个数组变量的名字10：
2、这个数组有10个单元NumberA[i]：第i个元素的值C语言下标从0开始数如果int类型是32位（4字节），则整个数组占用空间4*10=40字节变量名NumberA代表了数组的首地址第i个元素的地址=首地址+i*数据类型的大小051321132405-4653788329123下标存储空间55数组和广义表一维数组一维数组在内存中的存放假设NumberA的首地址为12，每个单元的大小是4个字节第i个元素的地址=首地址+i*数据类型的大小下标：0123值：53112地址：12131415161718192021
3、22232425262765数组和广义表二维数组二维数组就像是多层的宿舍楼先说明楼层，再说明在该楼层的宿舍号40140240340440540640740830130230330430530630730820120220320420520620720810110210310410510610710875数组和广义表二维数组声明intData[5][4];int：每个数组单元的类型为整型Data：这个数组变量的名字5：这个数组有5行（0~4）4：这个数组有4列（0~3）Data[i][j]：第i行第j列元素的值
4、0,00,10,20,31,01,11,21,32,02,12,22,33,03,13,23,34,04,14,24,385数组和广义表二维数组如果int类型是32位（4字节），则整个数组占用空间5*4*4=80字节跟一维数组类似，第k个元素的地址=首地址+k*数据类型的大小0,00,10,20,31,01,11,21,32,02,12,22,33,03,13,23,34,04,14,24,395数组和广义表二维数组按照行优先，Data[i][j]是第几个元素？Data[i][j]前面有i行，j列所以Data
5、[i][j]是第“i*列数+j”个元素(从0开始)所以Data[i][j]的地址=首地址+(i*列数+j)*数据类型的大小4,34,24,14,03,33,23,13,02,32,22,12,01,31,21,11,00,30,20,10,0ij105数组和广义表二维数组二维数组在内存中的存放二维数组的“二维”是逻辑上的内存永远是线性编址0,00,10,20,31,01,11,21,32,02,12,22,33,03,13,23,34,04,14,24,30,00,10,20,31,01,11,21,32,0
6、2,1...“二维数组”内存中的存放方式9*4字节X115数组和广义表二维数组二维数组A中任一元素aij在内存中的位置N维数组A中任一元素在内存中的位置125数组和广义表N维数组0,0,00,1,00,2,00,3,01,0,01,1,01,2,01,3,02,0,02,1,02,2,02,3,03,0,03,1,03,2,03,3,04,0,04,1,04,2,04,3,0xyz135数组和广义表矩阵的压缩存储特殊矩阵对称矩阵三角矩阵145数组和广义表矩阵的压缩存储特殊矩阵对称矩阵即aij=aji,1<=i
7、,j<=n可以将n2个单元压缩为n(n+1)/2个：156752896830790415268379041567528968307904155数组和广义表假设矩阵按行优先存放，矩阵元素aij的存放位置k=?（假设下标从1开始）03860864979257511526837904i=3j=2k=4(保存下三角)(保存上三角)165数组和广义表矩阵的压缩存储公式的推导（下三角）矩阵元素aij前面有一个i-1行的完整三角形，共有元素(1+i-1)(i-1)/2=i(i-1)/2个另外，同一行，前面还有j-1个元素所
8、以，k=i(i-1)/2+j-11567528968307904i=3j=2175数组和广义表矩阵的压缩存储三角矩阵压缩方法和对称矩阵完全相同10005200683079041567028900300004下三角上三角185数组和广义表矩阵的压缩存储稀疏矩阵非零元素个数远远少于矩阵元素总数00000000300000000000014000000070000000005000000000000000
