数据结构05数组和广义表11

《数据结构05数组和广义表11》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2021/8/261本章主要介绍数组的概念及多维数组在计算机中的存放，特殊矩阵的压缩存储及相应运算，广义表的概念和存储结构及其相关运算的实现。通过本章学习，要求掌握如下内容：1．多维数组的定义及在计算机中的存储表示；2．对称矩阵、三角矩阵、对角矩阵等特殊矩阵在计算机中的压缩存储表示及地址计算公式；3．稀疏矩阵的三元组表示及转置算法实现；4．稀疏矩阵的十字链表表示及相加算法实现；5．广义表存储结构表示及基本运算。本章学习导读2021/8/262数组和广义表可看成是一种特殊的线性表，其特殊在于，表中的数据元素本身也是一种线性表。5.1.1数组的定义数组是

2、大家都已经很熟悉的一种数据类型，几乎所有高级语言程序设计中都设定了数组类型。数组（Array）是由n(n>1)个相同类型数据元素a0，al，…ai…，an-1构成的有限序列。n是数组的长度。其中数组中的数据元素ai是一个数据结构，即ai可以是线性表中的一个元素，本身也可以是一个线性表，而线性子表中的每一个数据元素还可以再分解……。根据数组元素ai的组织形式不同，数组可以分为一维数组、二维数组以及多维（n维）数组。5.1数组2021/8/263有时也把一维数组称为向量，二维数组称为矩阵。在二维或多维数组中，每个数组元素都受到2个或n个关系的约束。当数组

3、为n维时，其对应线性表中的每个元素又是一个线性表。在每个关系中，每个元素都有一个直接后继。因此，就其单个关系而言，这n个关系中的每一个仍然是一种线性关系。数组中每个元素都是由一个值和一组下标来确定的。同线性表一样，数组中的所有数据元素都必须属于同一数据类型。元素下标的个数被称为数组的维数。显然，当维数为1时，数组就退化为定长的线性表。2021/8/2641．一维数组一维数组可以看成是一个线性表或一个向量，它在计算机内是存放在一块连续的存储单元中，适合于随机查找。一维数组记为A[n]或A=(a0，al，…ai，…，an-1)一维数组中，一旦a0的存储地

4、址、一个数据元素所占存储单元数L确定，则ai的存储地址LOC(ai)就可求出：LOC(ai)=LOC(a0)+i*L(0≤i

5、中，ai=(ai,0ai,1…ai,n-1)(0≤i＜n)可以认为Am*n=A，A是这样的一维数组：A=(a0，al，…，ai，…，am-1)2021/8/266显然，二维数组同样满足数组的定义。一个二维数组可以看作是每个数据元素都是相同类型的一维数组。以此类推，任何多维数组都可以看作一个线性表，这时线性表中的每个数据元素也是一个线性表。多维数组是特殊的线性表，是线性表的推广。数组的性质：(1)数组中的数据元素数目固定。一旦定义了一个数组，其数据元素数目不再有增减变化。它属于静态分配存储空间的数据结构。(2)数组中的数据元素必须具有相同的数据类型。(

6、3)数组中的每个数据元素都有一组唯一的下标值。(4)数组是一种随机存储结构。可随机存取数组中的任意数据元素。2021/8/267对于多维数组，有两种存储方式：Am,n以行序为主序的顺序存储；数组元素按行向量排列，即第i+1个行向量紧接在第i个行向量之后,把所有数组元素顺序存放在一块连续的存储单元中。任一数据元素的存储地址可由公式算出：Loc(ai,j)=loc(a0,0)+(i*n+j)*L以列序为主序的顺序存储在以列序为主序的存储方式中，数组元素按列向量排列，即第j+1个列向量紧接在第j个列向量之后,把所有数组元素顺序存放在一块连续的存储单元中。任

7、一数据元素的存储地址可由公式算出Loc(ai,,j)=loc(a0,,0)+(j*m+i)*L2021/8/268推广到一般设二维数组行下界为c1,行上界为d1,列下界为c2，列上界为d2,即数组A[c1…d1,c2…d2].-则以行序为主序的求元素地址公式可以为：Loc(ai,j)=loc(ac1,c2)+[(i-c1)*(d2-c2+1)+(j-c2)]*L则以列序为主序的求元素地址公式可以为：Loc(ai,j)=loc(ac1,c2)+[(j-c1)*(d1-c1+1)+(i-c1)]*L2021/8/2695.1.2数组的基本操作数组一旦被定

8、义，它的维数和维界就不再改变。因此，除了结构的初始化和销毁之外，数组的基本操作一般不会含有元素的插入或删除等