数据结构课件第五章数组和广义表.ppt

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

1、第五章数组和广义表5.1数组的定义5.2数组的顺序表示和实现5.3矩阵的压缩存储5.4广义表的定义5.5广义表的存储结构5.1数组的定义数组是大家都已经很熟悉的一种数据类型，几乎所有高级语言程序设计中都设定了数组类型。本章，我们仅简单地讨论数组的逻辑结构及在计算机内的存储方式。1.一维数组一维数组可以看成是一个线性表，它在计算机内是存放在一块连续的存储单元中，适合于随机查找。5.1数组的定义2．二维数组如下图中，A是一个m行n列的二维数组.二维数组也可以看成是一个定长的线性表.a00a01…a0,n-1a10a11…a1,n-1A=am-1,0a…am

2、-1,1m-1,n-1…………5.1数组的定义则A可以表示为这样一个线性表：A=(a0,a1,…,an-1)其中每个数据元素aj可以是一个列向量形式的线性表:aj=(a0j,a1j,…,am-1,j)(0≤j≤n-1）5.1数组的定义或者A可以表示为这样一个线性表：A=(a0,a1,…,am-1)其中，每个数据元素ai是一个行向量形式的线性表:ai=(ai0,ai1,ai2,…,ai,n-1)(0≤i≤m-1）3.多维数组同理,三维及以上的多维数组也可作类似分析。5.1数组的定义数组的基本操作数组一旦被定义，它的维数和维界就不能再改变，因此，数组的基本

3、操作只能是初始化、存取元素、修改元素的值,而不能够有插入、删除等操作。因此，数组总是采用顺序存储结构。由于存储单元是一维的，那么二维的数组元素怎样存储到一维的内存中？有两种存储方式：一是以行序为主序的存储方式；二是以列序为主序的存储方式。5.2数组的顺序表示和实现例如二维数组A[m][n]按行优先方式存储：a00，a01,…,a0,n-1，a10，a11，...，a1,n-1，…,am-1,0,am-1,1,…,am-1,n-1a00a01…a0,n-1a10a11…a1,n-1A=am-1,0a…am-1,1m-1,n-1…………a00a01…a0,

4、n-1a10a1,n-1a11……5.2数组的顺序表示和实现二维数组A[m][n]按列优先方式存储：a00，a10,…,am-1,0,a01，a11，...，am-1,1，…,a0,n-1,a1,n-1,…,am-1,n-1a00a01…a0,n-1a10a11…a1,n-1A=am-1,0a…am-1,1m-1,n-1…………a00a10…am-1,0a01am-1,1a11……5.2数组的顺序表示和实现由于二维数组的每个元素在内存中是顺序存储的，因此，只要知道第一个元素的存储地址，就可以求得其它元素的地址，如何求？以行优先存储为例，假设设a00的内

5、存地址为LOC(a00)，每个元素占用t个字节，则元素aij的存储地址应为第一个元素的地址加上排在aij前面的元素所占用的字节数，而aij的前面有i行(0~i-1)共i×n个元素，而本行前面又有j个元素，故aij的前面一共有i×n+j个元素。则aij的内存地址按等差数列计算为：LOC(aij)=LOC(a00)+（i×n+j）×t5.3矩阵的压缩存储矩阵是它是很多科学与工程计算问题中研究的数学对象。高级语言中一般都用二维数组存储矩阵，但有时候，对于一些阶数很高的矩阵，如果在矩阵中有许多值相同的元素或者是零元素，则会浪费存储空间。为了节省存储空间，可以对

6、这类矩阵进行压缩存储。所谓压缩存储是指：为多个值相同的元素只分配一个存储空间，值为零的元素不分配空间。特殊矩阵：值相同的元素或者零元素在矩阵中的分布有一定规律。稀疏矩阵：元素分布无规律，零元素较多。5.3.1特殊矩阵1.对称矩阵若一个n阶方阵A中元素满足下列条件：aij=aji其中1≤i,j≤n，则称A为对称矩阵。如：对称矩阵只需存储它的下三角元素或上三角元素。一共只用存储n(n+1)/2个元素即可。5.3.1特殊矩阵假设以一维数组sa[0…n(n+1)/2]（图示）作为n阶对称矩阵A的存储结构，将矩阵的下三角元素按行序存储到sa[]数组中.a11……

7、an,n-2an,n-1an,n0123……2)1(+nn-32)1(+nn-22)1(+nn-1a21a22a31则矩阵元aij存储在sa[]数组中下标为多少(设为k)的位置上呢？5.3.1特殊矩阵有如下关系：i(i-1)/2+j－1当i>=jj(j-1)/2+i－1当i

8、形式如下：221n1211..................nnacccaacaaa2n压缩