多维数组和广义表.pptVIP

本章的目的是介绍多维数组的逻辑结构特征及其存储方式，特殊矩阵和稀疏矩阵的压缩存储方法及广义表的概念。本章重点是熟悉多维数组的存储方式、矩阵的压缩存储方式、广义表的定义及其求表头和表尾的运算，难点是稀疏矩阵的压缩存储表示下实现的算法。学习目的与要求课程内容多维数组矩阵的压缩存储广义表的概念第五章多维数组和广义表5.1多维数组1.数组的定义数组是由一组类型相同的数据元素构造而成的。数组元素在数组中的相对位置是由下标确定的。一维数组、二维数组。二维数组可称为矩阵。a11a12…a1nAmn=a21a22…a2n…………am1am2…amn图5－1二维数组结构m维数组An1n2…nm的每个元素ai1i2…im都属于m个向量，最多可以有m个直接前趋和m个直接后继。如把数据元素的下标顺序变成线性表的序号，则一维数组就是一个线性表。数组虽然是线性表的特例,但关于数组的运算与一般线性表的运算不同，数组的主要运算有两种：给定一组下标，存取相应的数据元素；给定一组下标，修改相应的数据元素。010302数组的顺序存储结构2.数组的顺序存储结构数组的顺序存储结构指的是用一组连续的存储单元依次存放数组元素。(1)行优先顺序行优先顺序：将数组元素按行向量排列，行优先顺序规定为先排最右的下标，从右向左，最后排最左下标。例：写出A[3][4]、A[2][3][4]元素按行优先顺序。(2)列优先顺序列优先顺序：将数组元素按列向量排列，列优先顺序规定为先排最左下标，从左向右，最后排最右下标。二维数组Amn按“行优先顺序”存储在内存中，假设每个元素占d个存储单元，则aij的地址计算函数为：LOC(aij)=LOC(a11)+[(i-1)×n+j-1]×d对应C语言的二维数组：DataTypeA[m][n];

数组A[m][n]的两个下标的下界均为0，上界分别为m-1、n-1，每个数据元素占k个存储单元，二维数组中任一元素a[i,j]的存储位置可由下列公式确定。loc[i,j]=loc[0,0]+(i*n+j)*k

其中，loc[0,0]是A[0][0]的存储位置，loc[i,j]是A[i][j]的存储位置。这个式子确定了C语言的二维数组元素的位置和下标的关系。例：inta[3][5];a[2][3]=举例：举例：1.给定整型数组b[3][5]，b[0][0]的存储地址为1200,试求在行序为主的存储方式下：(1)b[2][4]的存储地址；(2)该数组占用的字节数。2.二维数组A[-1..2,3..6]共含有多少个元素？三维数组R[c1..d1,c2..d2,c3..d3]共含有多少个元素？3.数组中B[1..10,-2..6,2..8]以行优先顺序存储，设第一个元素的首地址是100,每个元素点3个存储长度的存储空间，则元素Ｂ[5,0,7]的存储地址是多少？5.2矩阵的压缩存储对于矩阵，关心的是如何存储它的元素，使矩阵的各种运算能有效地进行。对于阶数很高的矩阵，同时在矩阵中有许多值相同的元素或者零元素，为了节省存储，可对这类矩阵进行压缩存储。压缩存储：即为多个相同的非零元素只分配一个存储空间，对零元素不分配空间。010302所谓特殊矩阵（SpecialMatrices）是指非零元素或零元素的分布有一定规律的矩阵。5.2.1特殊矩阵01在一个n阶方阵A中，若元素满足下述性质：

aij=aji0≤i，j≤n-1

则称A为对称矩阵。如图所示：怎样存储该矩阵的元素？1.对称矩阵02存储元素为：{1,5,0,1,8,9,3,0,2,5,7,0,6,1,3}，共15个。将这些元素存放在一个向量sa[0…n(n+1)/2-1]中。怎样通过元素下标在sa中找到该元素的值？aij和sa[k]的对应关系：若i=j,则aij在下三角矩阵中，之前的i行（第0行到第i-1行）共有1+2+..+i=i*(i+1)/2个元素，在第i行上，aij前有j个元素，因此：k=i*(i+1)/2+j(0=kn*(n+1)/2)若ij，则aij在上三角矩阵中，aij=aji则：k=j*(j+1