数据结构第九讲.ppt

《数据结构第九讲.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第九讲数组和广义表数组1数组的定义和基本运算数组的特点是每个数据元素可以又是一个线性表结构。因此，数组结构可以简单地定义为：若线性表中的数据元素为非结构的简单元素，则称为一维数组，即为向量；若一维数组中的数据元素又是一维数组结构，则称为二维数组；依次类推，若二维数组中的元素又是一个一维数组结构，则称作三维数组。结论：线性表结构是数组结构的一个特例，而数组结构又是线性表结构的扩展。举例：其中，A是数组结构的名称，整个数组元素可以看成是由m个行向量和n个列向量组成，其元素总数为m×n。在C语言中，二维数组

2、中的数据元素可以表示成a[表达式1][表达式2]，表达式1和表达式2被称为下标表达式，比如，a[i][j]。数组结构在创建时就确定了组成该结构的行向量数目和列向量数目，因此，在数组结构中不存在插入、删除元素的操作。二维数组结构的基本操作：（1）给定一组下标，修改该位置元素的内容Assign(A,item,index1,index2)（2）给定一组下标，返回该位置的元素内容Value(A,item,index1,index2)2数组的存储结构从理论上讲，数组结构也可以使用两种存储结构，即顺序存储结构和链

3、式存储结构。然而，由于数组结构没有插入、删除元素的操作，所以使用顺序存储结构更为适宜。换句话说，一般的数组结构不使用链式存储结构。组成数组结构的元素可以是多维的，但存储数据元素的内存单元地址是一维的，因此，在存储数组结构之前，需要解决将多维关系映射到一维关系的问题。举例：假设每个元素占L个存储单元，下面求地址公式第0行第1行第m-1行第0列第1列第m-1列LOC(i,j)=LOC(0,0)+(n*i+j)*LLOC(i,j)=LOC(0,0)+(m*j+i)*L3．矩阵的压缩存储矩阵是在很多科学与工程

4、计算中遇到的数学模型。在数学上，矩阵是这样定义的：它是一个由m×n个元素排成的m行（横向）n列（纵向）的表。下面就是一个矩阵：m×n的矩阵4特殊矩阵所谓特殊矩阵就是元素值的排列具有一定规律的矩阵。常见的这类矩阵有：对称矩阵、下（上）三角矩阵、对角线矩阵等等。对称矩阵的特点是aij=aji，比如，下面就是一个对称矩阵：下（上）三角矩阵的特点是以主对角线为界的上（下）半部分是一个固定的值，下（上）半部分的元素值没有任何规律。比如，下面是一个下三角矩阵：对角矩阵的特点是所有的非零元素都集中在以主对角线为中心

5、的带状区域中。比如，下面就是一个3阶对角矩阵：压缩：为多个值相同的元只分配一个存储空间，对零元不分配空间.对于这些特殊矩阵，应该充分利用元素值的分布规律，将其进行压缩存储。选择压缩存储的方法应遵循两条原则：一是尽可能地压缩数据量，二是压缩后仍然可以比较容易地进行各项基本操作。三种特殊矩阵的压缩方法：（1）对称矩阵对称矩阵的特点是aij=aji。一个n×n的方阵，共有n2个元素，而实际上在对称矩阵中有n(n-1)/2个元素可以通过其他元素获得。压缩的方法是首先将二维关系映射成一维关系，并只存储其中必要的

6、n(n+1)/2个（主对角线和下三角）元素内容，这些元素的存储顺序以行为主序。举例：假设定义一个数组型变量：intA[10];设k是对称矩阵位于（i，j）位置的元素在一维数组中的存放位置。注意第一元素放在a[0]。A[i,j],前i-1行元素的个数为i(i-1)/2,在第i行为第j个的次序为j，而A[1,1]放在a[0],所以k=i(i-1)/2+j-1,(i>=j),A[i,j],当i

7、/2+i-1,(i

8、位置存放数值0。下面我们讨论一下对于任意给定的（i，j），求得在一维数组中存储位置k的方法。注：该矩阵除第一行和最后一行外，每行有3个元素。前i-1行元素的个数：3*(i-1)-1;第i行，第j个位置在第i行的次序为：j-i+2故：k=3*(i-1)-1+j-i+2=3*(i-1)+j-i+1,当i-1<=j<=i+12.稀疏矩阵的压缩存储若一个m×n的矩阵含有t个非零元素，且t远远小于m*n，则我们将这个矩阵称为稀疏矩阵。举例：注：通常：t/(m*n)