资源描述：
《java数据结构第五章数组和广义表》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第五章数组和广义表广义线性表多维数组广义表逻辑结构存储结构逻辑结构存储结构⑴数组的定义(2)ADT定义(3)基本操作顺序存储压缩存储特殊矩阵·对称矩阵·三角矩阵·对角矩阵稀疏矩阵按行优先按列优先寻址的计算方法⑴基本概念·广义表定义·表头、表尾·长度、深度⑵ADT定义链接存储头尾表示法转置算法线性表——具有相同类型的数据元素的有限序列。限制插入、删除位置线性表——具有相同类型的数据元素的有限序列。限制元素类型为字符栈——仅在表尾进行插入和删除操作的线性表。队列——在一端进行插入操作，而另一端进行删除操作的线性表。
2、串——零个或多个字符组成的有限序列。特殊线性表线性表——具有相同类型的数据元素的有限序列。将元素的类型进行扩充广义线性表（多维）数组——线性表中的数据元素可以是线性表，但所有元素的类型相同。广义表——线性表中的数据元素可以是线性表，且元素的类型可以不相同。4.2数组数组（array）：是n(n>=0)个相同数据类型的数据元素（a1,a2,a3,…,an）构成的有限线性序列。n为数组长度或数组大小。n=0为空数组。多维数组：一个m(m>=2)维数组，其每个数据元素是一个m-1维的数组。且每个元素都对应于一组下标（
3、j1,j2,…,jm）,每个下标的取值范围是ci≤ji≤di,di-ci+1称为第i维的长度(i=1,2,…,n),m为数组的维数。数组的特点：①数组中各元素具有统一的类型；②数组元素的下标一般具有固定的上界和下界。③数组的基本操作比较简单，除了结构的初始化和销毁之外，只有存取元素和修改元素值的操作。④数组有顺序存储和链式存储两种方式。一维数组的特点：1个下标，a2是a3的直接前驱，a4是a3的直接后继。注：一维数组的顺序存储常称为向量。一维数组存储结构与寻址设一维数组的下标的范围为闭区间［l，h］，每个数组元
4、素占用c个存储单元，则其任一元素ai的存储地址可由下式确定：Loc(ai)＝Loc(al)＋(i－l)×ccalai-1ai……ahal+1……Loc(al)Loc(ai)二维数组的特点：2个下标，每个元素ai,j受到两个关系（行关系和列关系）的约束：a11a12…a1na21a22…a2n………… am1am2…amnAmn=一个m×n的二维数组可以看成是m行的一维数组，或者n列的一维数组。例如，元素a22受两个线性关系的约束，在行上有一个行前驱a21和一个行后继a23，在列上有一个列前驱a12和和一个列后继
5、a32。a11a12…a1na21a22…a2n…………am1am2…amnA=A=(A1，A2，……，An)其中：Ai=(a1i，a2i，……，ami)(1≤i≤n)二维数组是数据元素为一维数组（线性表）的线性表。m维数组的特点：m个下标，每个元素受到m个关系约束。一个m维数组可以看成是由若干个m－1维数组组成的线性表。问题：计算机的存储结构是一维的，而数组一般是多维的，怎样存放？解决办法：事先约定按某种次序将数组元素排成一列序列，然后将这个线性序列存入存储器中。例如：在二维数组中，我们既可以规定按行存储，也
6、可以规定按列存储。注意：若规定好了次序，则数组中任意一个元素的存放地址便有规律可寻，可形成地址计算公式；约定的次序不同，则计算元素地址的公式也有所不同；常用的映射方法有两种：按行优先：先行后列，先存储行号较小的元素，行号相同者先存储列号较小的元素。按列优先：先列后行，先存储列号较小的元素，列号相同者先存储行号较小的元素。2、二维数组的存储结构与寻址二维数组内存二维结构一维结构0n-10m-1(a)二维数组aij按行优先存储的寻址a0,1…a0,n-1…aij… am-1,0…am-1,n-1Amn=数组大小：（
7、m-1-0+1）*（n-1-0+1）=m*n;设二维数组A[m][n]的首地址A[0][0]为p,每个元素占L个存储单元。若已知a[i][j]是数组的第k个元素，则可得：Loc(i,j)=p+k*L;目标：求a[i][j]是数组的第几个元素。0n-10m-1(a)二维数组本行中aij前面的元素个数每行元素个数整行数aij按行优先存储的寻址aij前面的元素个数=阴影部分的面积=整行数×每行元素个数+本行中aij前面的元素个数=(i-0)×(n-1-0＋1)＋(j-0)LOC(aij)=LOC(a00)+[i*n+
8、j]*Lc2b2c1b1(a)二维数组aij前面的元素个数=阴影部分的面积=整行数×每行元素个数+本行中aij前面的元素个数=(i-c1)×(b2-c2＋1)＋(j-c2)本行中aij前面的元素个数每行元素个数整行数aij通用按行优先存储的寻址公式：数组大小：（b1-c1+1）*（b2-c2+1）;计算二维数组元素地址的通式设一般的二维数组是A[c1..d1,c2..d2]，这里c1,
