【精品数据结构课件】数组.ppt

《【精品数据结构课件】数组.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第5章数组和广义表本章主题：多维数组、特殊矩阵和广义表教学目的：掌握数组和广义表的定义、运算及存储结构教学难点：矩阵的压缩存储2021/7/241本章主要介绍数组的概念及多维数组在计算机中的存放，特殊矩阵的压缩存储及相应运算，广义表的概念和存储结构及其相关运算的实现。通过本章学习，要求掌握如下内容：1．多维数组的定义及在计算机中的存储表示；2．对称矩阵、三角矩阵、对角矩阵等特殊矩阵在计算机中的压缩存储表示及地址计算公式；3．稀疏矩阵的三元组表示及转置算法实现；4．稀疏矩阵的十字链表表示及相加算法实现；5．广义表存储结构表示及基本运算。本章学习导读2021/7/24

2、2数组和广义表可看成是一种特殊的线性表，其特殊在于，表中的数所元素本身也是一种线性表。5.1.1数组的定义数组是大家都已经很熟悉的一种数据类型，几乎所有高级语言程序设计中都设定了数组类型。数组（Array）是由n(n>1)个相同类型数据元素a0，al，…ai…，an-1构成的有限序列。n是数组的长度。其中数组中的数据元素ai是一个数据结构，即ai可以是线性表中的一个元素，本身也可以是一个线性表，而线性子表中的每一个数据元素还可以再分解……。根据数组元素ai的组织形式不同，数组可以分为一维数组、二维数组以及多维（n维）数组。5.1数组2021/7/243有时也把一维

3、数组称为向量，二维数组称为矩阵。在二维或多维数组中，每个数组元素都受到2个或n个关系的约束。当数组为n维时，其对应线性表中的每个元素又是一个线性表。在每个关系中，每个元素都有一个直接后继。因此，就其单个关系而言，这n个关系中的每一个仍然是一种线性关系。数组中每个元素都是由一个值和一组下标来确定的。同线性表一样，数组中的所有数据元素都必须属于同一数据类型。元素下标的个数被称为数组的维数。显然，当维数为1时，数组就退化为定长的线性表。2021/7/2441．一维数组一维数组可以看成是一个线性表或一个向量，它在计算机内是存放在一块连续的存储单元中，适合于随机查找。一维数

4、组记为A[n]或A=(a0，al，…ai，…，an-1)一维数组中，一旦a0的存储地址、一个数据元素所占存储单元数k确定，则ai的存储地址LOC(ai)就可求出：LOC(ai)=LOC(a0)+i*k(0≤i

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

6、据结构。(2)数组中的数据元素必须具有相同的数据类型。(3)数组中的每个数据元素都有一组唯一的下标值。(4)数组是一种随机存储结构。可随机存取数组中的任意数据元素。2021/7/2475.1.2数组的基本操作数组一旦被定义，它的维数和维界就不再改变。因此，除了结构的初始化和销毁之外，数组的基本操作一般不会含有元素的插入或删除等操作,数组只有访问数组元素和修改元素值的操作。(1)value(A，indexl，index2，…，indexd)：A是已存在的d维数组，indexl，index2，…，indexd是指定的d个下标值，且这些下标均不超过对应维的上界。其运算结

7、果是返回由下标指定的A中的对应元素的值。(2)assign(A，e，indexl，index2，…，indexd)：A是已存在的d维数组，e为元素变量，indexl，index2，…，indexd是指定的d个下标值，且这些下标均未越界。其运算结果是将e的值赋给由下标指定的A中的对应元素。2021/7/248(3)disp(A)：输出数组A的所有元素。在大多数程序设计语言中，取数组元素值操作value(A，indexl，index2，…，indexd)通常直接写作A[indexl][index2]…[indexd]，而对数组元素的赋值操作assign(A，e，ind

8、exl，i