资源描述：
《数据结构第五章课件数组 和广 义表.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、第5章 数组和广义表5.1数组的定义5.2数组的顺序表示和实现5.3矩阵的压缩存储5.4广义表的定义5.5广义表的存储结构5.1.1数组的定义数组是大家都已经很熟悉的一种数据类型，几乎所有高级语言程序设计中都设定了数组类型。1．一维数组一维数组可以看成是一个线性表或一个向量（第2章已经介绍），它在计算机内是存放在一块连续的存储单元中，适合于随机查找。这在第2章的线性表的顺序存储结构中已经介绍。5.1多维数组的定义2．二维数组二维数组中的每一个元素最多可有两个直接前驱和两个直接后继（边界除外），故是一种典型的非线性结构。
2、例如，设A是一个有m行n列的二维数组，则A可以表示为：二维数组可以看成是这样一个定长的线性表,它的每个数据元素也是一个定长的线性表。二维数组可以看成是一个线性表A=(a0,a1,……,an-1)其中每个数据元素aj是一个列向量形式的线性表A=(a0,a1,……,an-1)或者,可以看成是一个线性表A=(a0,a1,……,am-1)其中每个数据元素aj是一个行向量形式的线性表A=(a0,a1,...am-1)同理，n维数组可以看成是这样一个定长的线性表,它的每个数据元素也是n-1维的数组。n维数组最多可有n个直接前驱和n
3、个直接后继，故n维数组是一种非线性结构。3．n维数组数组的操作数组一旦被定义，它的维数和维界就不再改变，因此，除了结构的初始化和销毁之外，数组只有存取元素和修改元素值的操作。数组宜采用顺序存储结构：由于数组一般不作插入或删除操作，也就是说，一旦建立了数组，则结构中的数组元素个数和元素之间的关系就不再发生变动，即它们的逻辑结构就固定下来了，不再发生变化。本章仅重点讨论二维数组的存储，三维及三维以上的数组可以作类似分析。5.2数组顺序表示和实现由于计算机内存结构是一维的（线性的），因此，用一维内存存放多维数组就必须按某种次
4、序将数组元素排成一个线性序列，然后将这个线性序列顺序存放在存储器中。二维数组的顺序存储有两种形式:怎样将数组中元素存入到计算机内存中呢？1.行优先顺序a00a01……a0,n-1a10a11……a1,n-1am-1,0am-1,1……am-1,n-1……在BASIC语言、PASCAL语言、C/C++语言等高级语言程序设计中，都是按行优先顺序存放的。可以得出多n维数组按行优先存放到内存的规律：最左边下标变化最慢，最右边下标变化最快，右边下标变化一遍，与之相邻的左边下标才变化一次。a0a1am-12.列优先顺序a00a10
5、……am-1,0a01a11……am-1,1a0,n-1a1,n-1……am-1,n-1……在FORTRAN语言程序设计中，数组是按列优先顺序存放的。可以得出n维数组按行优先存放到内存的规律：最左边下标变化最慢，最右边下标变化最快，右边下标变化一遍，与之相邻的左边下标才变化一次。a0a1am-1二维数组元素存储位置的计算设二维数组Am×n的起始地址(基地址),即a00的起始地址为LOC(0,0),每个数据元素占L个存储单元,则A中任一元素aij的起始地址为:行优先顺序:LOC(i,j)=LOC(0,0)+(i*n+j)
6、*L列优先顺序:LOC(i,j)=LOC(0,0)+(j*m+i)*L三维数组元素存储位置的计算设三维数组Am×n×p的起始地址(基地址),即a000的起始地址为LOC(0,0,0),每个数据元素占L个存储单元,则A中任一元素aijk的起始地址为:行优先顺序:LOC(i,j,k)=LOC(0,0,0)+(i*n*p+j*p*k)*L列优先顺序:LOC(i,j,k)=LOC(0,0,0)+(k*m*n+j*m+i)*L所以,数组元素是其下标的线性函数.由于计算各个元素存储位置的时间相等,所以存取数组中任一元素的时间也相等
7、.我们称具有这一特点的存储结构为随机存储结构.矩阵是一个二维数组，它是很多科学与工程计算问题中研究的数学对象。当矩阵的阶数很大时将会占较多存储单元。而当里面的元素分布呈现某种规律时，这时，从节约存储单元出发，可考虑若干元素共用一个存储单元，即进行压缩存储。所谓压缩存储是指：为多个值相同的元素只分配一个存储空间，值为零的元素不分配空间。假若值相同的元素或者零元素在矩阵中的分布有一定规律,则此类矩阵为特殊矩阵;非零元素较零元素少,且分布没有一定规律的矩阵,为稀疏矩阵.5.3矩阵的压缩存储1．对称矩阵若一个n阶方阵A中元素满
8、足下列条件：aij=aji其中1≤i,j≤n，则称A为对称矩阵。例如，下图是一个3*3的对称矩阵。5.3.1特殊矩阵图一个对称矩阵对称矩阵的压缩存储为每一对对称元分配一个存储空间,则可将n2个元压缩存储到n(n+1)/2个元的空间中.以行优先存储其下三角(包括对角线)中的元.假设以一维数组sa[n(n+1)/2]作为n阶对称矩阵A
