《高级线性表》ppt课件

《《高级线性表》ppt课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第十一章高级线性表任课教员：张铭http://db.pku.edu.cn/mzhang/DS/mzhang@db.pku.edu.cn北京大学信息科学与技术学院网络与信息系统研究所版权所有，转载或翻印必究主要内容11.1多维数组11.2广义表11.3存储管理技术北京大学信息学院版权所有，转载或翻印必究Page11.1多维数组数组（Array）是数量和元素类型固定的有序序列静态数组必须在定义它的时候指定其大小和类型动态数组可以在程序运行才分配内存空间多维数组（Multi-array）是向量的扩充向量的向量就组成了多维数组可以表示为：ELEMA[c1..d1][c2..d2]…[cn..dn]

2、ci和di是各维下标的下界和上界。所以其元素个数为：北京大学信息学院版权所有，转载或翻印必究Page数组的空间结构左边是二维数组的空间结构，右边是三维数组的空间结构，d1[1..3],d2[1..5],d3[1..5]分别为3个维。北京大学信息学院版权所有，转载或翻印必究Page数组的存储内存是一维的，所以数组的存储也只能是一维的以行为主序（也称为“行优先”）以列为主序（也称为“列优先”）一个3×3的数组X的行优先表示：内存中的存放是：1，2，3，4，5，6，7，8，9北京大学信息学院版权所有，转载或翻印必究Page数组的存储（续）一个二维m×n数组中元素X[i][j]（第i行第j列元素

3、）的内存地址可以这样来计算：X[0][0]（数组首地址）+（n×i+j）×元素的长度（如C++中int型为4字节）例如，我们已知一个数组的A[0][0]元素在内存的644的位置，假设元素的长度为8，那么我们就可以求得其他任意元素A[x][y]的位置，为644+len×(n×x+y)。例如，n=m=3，由上面公式得到A[2][3]元素的地址：644+8×（3×2+2）=708北京大学信息学院版权所有，转载或翻印必究PagePascal语言的存储实现是按行优先处理的，先排最右的下标，从右向左，最后最左的下标。例如对于三维数组a[1..k,1..m,1..n]的元素axyz可以如下排列：北京大学信

4、息学院版权所有，转载或翻印必究PagePascal语言的行优先存储a111a112a113…a11na121a122a123…a12n…………………………a1m1a1m2a1m3…a1mna211a212a213…a21na221a222a223…a22n…………………………a2m1a2m2a2m3…a2mn┇ak11ak12ak13…ak1nak21ak22ak23…ak2n…………………………akm1akm2akm3…akmn北京大学信息学院版权所有，转载或翻印必究PageFORTRAN语言采用列优先存储。先排最左的下标，从左向右，最后最右的下标。例如对于三维数组a[1..k,1..m

5、,1..n]的元素axyz可以如下排列：北京大学信息学院版权所有，转载或翻印必究PageFORTRAN语言的列优先存储a111a211a311…ak11a121a221a321…ak21…………………………a1m1a2m1a3m1…akm1a112a212a312…ak12a122a222a322…ak22…………………………a1m2a2m2a3m2…akm2┇a11na21na31n…ak1na12na22na32n…ak2n…………………………a1mna2mna3mn…akmn北京大学信息学院版权所有，转载或翻印必究Page行优先存储公式设数组元素占d个存储单元,3维矩阵行优先存储公式

6、为：北京大学信息学院版权所有，转载或翻印必究Pagen维矩阵行优先存储公式为：北京大学信息学院版权所有，转载或翻印必究PageC++多维数组ELEMA[d1][d2]…[dn];北京大学信息学院版权所有，转载或翻印必究Page数组的声明在编译的时候如果已经知道数组每一维的大小：声明一个10×10的整型数组：intnum[10][10];只知道数组一个维的大小，那么也可以动态地创建一个二维数组。例如我们只要一个组有10个整数，但是不知道有多少个组：int(*num)[10];最后在程序运行的时候，可以计算出或者由用户指定它的第一个维数是n：num=newint[n][10];北京大学信息学

7、院版权所有，转载或翻印必究Page数组的声明:动态的声明int**X;introw=3;intcol=3;try{//创建行指针，即指向整型的指针X=newint*[row];//然后再为每一行分配地址for(inti=0;i