《数据结构幻灯片ch5》由会员分享，可在线阅读，更多相关《数据结构幻灯片ch5（37页珍藏版）》请在金锄头文库上搜索。
1、1,第五章 数组和广义表,5.1 数组的定义 5.2 数组的顺序表示和实现 5.3 矩阵的压缩存储 5.3.1 特殊矩阵 5.3.2 稀疏矩阵 5.4 广义表的定义 5.5 广义表的存储结构,2,本章主要介绍多维数组的概念及在计算机中的存放，特殊矩阵的压缩存储及相应运算，广义表的概念和存储结构及其相关运算的实现。通过本章学习，要求掌握如下内容： 1多维数组的定义及在计算机中的存储表示； 2对称矩阵、三角矩阵、对角矩阵等特殊矩阵在计算机中的压缩存储表示及地址计算公式； 3稀疏矩阵的三元组表示及转置算法实现； 4稀疏矩阵的十字链表表示及相加算法实现； 5广义表存储结构表示及基本运算。,3,5.1
2、数组的定义,4,数组是大家都已经很熟悉的一种数据类型，几乎所有高级语言程序设计中都设定了数组类型。在此，我们仅简单地讨论数组的逻辑结构及在计算机内的存储方式。 1一维数组 2二维数组 3多维数组,5,一维数组可以看成是一个线性表或一个向量（第2章已经介绍），它在计算机内是存放在一块连续的存储单元中，适合于随机查找。这在第2章的线性表的顺序存储结构中已经介绍。,1一维数组,6,二维数组可以看成是向量的推广。例如，设A是一个有m行n列的二维数组，则A可以表示为：,2二维数组,a00,a10,am-1,0,a01,a11,am-1,1,a0,n-10,a1,n-1,am-1,n-1, ,A=,7,在
3、此， 可以将二维数组A看成是由m个行向量X0，X1， ，Xm-1 组成，其中，Xi=( ai0, ai1, .,ain-1)， 0im-1； 也可以将二维数组A看成是由n个列向量y0, y1, ,yn-1组成，其中 yi=(a0i, a1i, ,am-1i)，0in-1。 由此可知二维数组中的每一个元素最多可有两个直接前驱和两个直接后继（边界除外），故是一种典型的非线性结构。,8,3多维数组,同理，三维数组最多可有三个直接前驱和三个直接后继，三维以上数组可以作类似分析。因此，可以把三维以上的数组称为多维数组，多维数组可有多个直接前驱和多个直接后继，故多维数组是一种非线性结构。,9,数组操作,数
4、组是一个具有固定格式和数量的数据有序集，每一个数据元素有唯一的一组下标来标识，因此，在数组上不能做插入、删除数据元素的操作。通常在各种高级语言中数组一旦被定义，每一维的大小及上下界都不能改变。在数组中通常做下面两种操作： 取值操作：给定一组下标，读其对应的数据元素。 赋值操作：给定一组下标，存储或修改与其相对应的数据元素。,10,抽象数据类型定义,ADT Array 数据对象：D=ai | ai Set,i=1,2,n, n0 数据关系：R= | ai-1 , ai D,i=2,n, n0 基本操作: InitArray( ADT Array,11,5.2 数组的顺序表示和实现,12,2、数组
5、的顺序存储,由于数组一般不作插入或删除操作，也就是说，一旦建立了数组，则结构中的数组元素个数和元素之间的关系就不再发生变动，即它们的逻辑结构就固定下来了，不再发生变化。因此，采用顺序存储结构表示数组是顺理成章的事了。本章中，仅重点讨论二维数组的存储，三维及三维以上的数组可以作类似分析。 多维数组的顺序存储有两种形式。 行优先顺序 列优先顺序,13,行优先顺序,行优先顺序也称为低下标优先或左边下标优先于右边下标。具体实现时，按行号从小到大的顺序，先将第一行中元素全部存放好，再存放第二行元素，第三行元素，依次类推 在BASIC语言、PASCAL语言、C/C+语言等高级语言程序设计中，都是按行优先顺
6、序存放的。例如，对刚才的Amn二维数组，可用如下形式存放到内存：a00，a01,a0n-1，a10，a11，.， a1 n-1，am-1 0 ， am-1 1，am-1 n-1。即二维数组按行优先存放到内存后，变成了一个线性序列（线性表）。 因此，可以得出多维数组按行优先存放到内存的规律：最左边下标变化最慢，最右边下标变化最快，右边下标变化一遍，与之相邻的左边下标才变化一次。因此，在算法中，最左边下标可以看成是外循环，最右边下标可以看成是最内循环。,14,地址计算,由于多维数组在内存中排列成一个线性序列，因此，若知道第一个元素的内存地址，如何求得其他元素的内存地址？我们可以将它们的地址排列看成
7、是一个等差数列，假设每个元素占l个字节，元素aij 的存储地址应为第一个元素的地址加上排在aij 前面的元素所占用的单元数，而aij 的前面有i行(0i-1)共in个元素，而本行前面又有j个元素，故aij的前面一共有in+j个元素，设a00的内存地址为LOC(a00)，则aij的内存地址按等差数列计算为LOC(aij)=LOC(a00)+（in+j）l。 同理，三维数组Amnp按行存放的地址计算公式为：LOC(aijk)=LOC(a000)+(优先inp+jp+k)l。,15,列优先顺序,1存放规则 列优先顺序也称为高下标优先或右边下标优先于左边下标。具体实现时，按列号从小到大的顺序，先将第一
8、列中元素全部存放好，再存放第二列元素，第三列元素，依次类推 在FORTRAN语言程序设计中，数组是按列优先顺序存放的。例如，对前面提到的Amn二维数组，可以按如下的形式存放到内存：a00， a10， am-10， a01，a11， ， am-1 1， a0 m-1，a1m-1，.， am-1 n-1。 即二维数组按列优先存放到内存后，也变成了一个线性序列（线性表）。 因此，可以得出多维数组按列优先存放到内存的规律：最右边下标变化最慢，最左边下标变化最快，左边下标变化一遍，与之相邻的右边下标才变化一次。因此，在算法中，最右边下标可以看成是外循环，最左边下标可以看成是最内循环。,16,5.3 矩阵
9、的压缩存储 5.3.1 特殊矩阵 5.3.2 稀疏矩阵,17,3、矩阵的压缩存储,特殊矩阵 稀疏矩阵,18,矩阵压缩存储,矩阵是一个二维数组，它是很多科学与工程计算问题中研究的数学对象。 矩阵可以用行优先或列优先方法顺序存放到内存中，但是，当矩阵的阶数很大时将会占较多存储单元。 而当里面的元素分布呈现某种规律时，这时，从节约存储单元出发，可考虑若干元素共用一个存储单元，即进行压缩存储。 所谓压缩存储是指：为多个值相同的元素只分配一个存储空间，值为零的元素不分配空间。但是压缩存储时，节约了存储单元，但怎样在压缩后找到某元素呢？因此还必须给出压缩前的下标和压缩后下标之间变换公式，才能使压缩存储变得
10、有意义。,19,特殊矩阵,1对称矩阵 2三角矩阵,20,1对称矩阵,若一个n阶方阵A中元素满足下列条件： aij=aji 其中 0 i, jn-1 ，则称A为对称矩阵。 例如，下图是一个3*3的对称矩阵。,21,上三角矩阵,即矩阵上三角部分元素是随机的，而下三角部分元素全部相同（为某常数C）或全为0，具体形式见图）。,22,下三角矩阵,即矩阵的下三角部分元素是随机的，而上三角部分元素全部相同（为某常数C）或全为0，具体形式见图。,23,对角矩阵,若矩阵中所有非零元素都集中在以主对角线为中心的带状区域中，区域外的值全为0，则称为对角矩阵。常见的有三对角矩阵、五对角矩阵、七对角矩阵等。 图为77的
11、三对角矩阵（即有三条对角线上元素非0）。,24,带状矩阵压缩到一维向量,压缩方法是将带状矩阵压缩到向量C中去，按以行为主序，顺序的存储其非零元素，如图5.10(c)所示，按其压缩规律，找到相应的映象函数。 如当w=3时，映象函数为： k=2*i+j-3,25,稀疏矩阵,在上节提到的特殊矩阵中，元素的分布呈现某种规律，故一定能找到一种合适的方法，将它们进行压缩存放。但是，在实际应用中，我们还经常会遇到一类矩阵：其矩阵阶数很大，非零元个数较少，零元很多，但非零元的排列没有一定规律，我们称这一类矩阵为稀疏矩阵。 很多科学管理及工程计算中，常会遇到阶数很高的大型稀疏矩阵。如果按常规分配方法，顺序分配在
12、计算机内，那将是相当浪费内存的。为此提出另外一种存储方法，仅仅存放非零元素。稀疏矩阵在实际应用中经常出现，因此，为了节省存储空间，有必要研究其存储方法及操作。 按照压缩存储的概念，要存放稀疏矩阵的元素，由于没有某种规律，除存放非零元的值外，还必须存储适当的辅助信息，才能迅速确定一个非零元是矩阵中的哪一个位置上的元素。下面将介绍稀疏矩阵的几种存储方法及一些算法的实现。,26,三元组表,在压缩存放稀疏矩阵的非零元同时，若还存放此非零元所在的行号和列号，则称为三元组表法，即称稀疏矩阵可用三元组表进行压缩存储，但它是一种顺序存储（按行优先顺序存放）。 一个非零元有行号、列号、值，为一个三元组，整个稀疏
13、矩阵中非零元的三元组合起来称为三元组表。,27,三元组表数据类型,数据类型可描述如下： #define MAXSIZE 100 /*定义非零元的最大数目*/ typedef struct node /*定义一个三元组*/ int i , j; /*非零元行、列号*/ int v; /*非零元值*/ Node; struct sparmatrix /*定义稀疏矩阵*/ int rows,cols ; /*稀疏矩阵行、列数*/ int terms; /*稀疏矩阵非零元个数*/ Node data MAXSIZE; /*三元组表*/ ;,28,示例,29,带行指针的链表,把具有相同行号的非零元用一个
14、单链表连接起来，稀疏矩阵中的若干行组成若干个单链表，合起来称为带行指针的链表。,30,行指针示例,31,十字链表,当稀疏矩阵中非零元的位置或个数经常变动时，三元组就不适合于作稀疏矩阵的存储结构，此时，采用链表作为存储结构更为恰当。 十字链表为稀疏矩阵中的链接存储中的一种较好的存储方法，在该方法中，每一个非零元用一个结点表示，结点中除了表示非零元所在的行、列和值的三元组（i,j,v）外，还需增加两个链域：行指针域（rptr），用来指向本行中下一个非零元素；列指针域（cptr），用来指向本列中下一个非零元素。稀疏矩阵中同一行的非零元通过向右的rptr指针链接成一个带表头结点的循环链表。同一列的非零
15、元也通过cptr指针链接成一个带表头结点的循环链表。因此，每个非零元既是第i行循环链表中的一个结点，又是第j列循环链表中的一个结点，相当于处在一个十字交叉路口，故称链表为十字链表。,32,十字链表,另外，为了运算方便，我们规定行、列循环链表的表头结点和表示非零元的结点一样，也定为五个域，且规定行、列、域值为0(因此，为了使表头结点和表示非零元的表结点不发生混淆，三元组中，输入行和列的下标不能从0开始!而必须从1开始)，并且将所有的行、列链表和头结点一起链成一个循环链表。 在行（列）表头结点中，行、列域的值都为0，故两组表头结点可以共用，即第i行链表和第i列链表共用一个表头结点，这些表头结点本身
16、又可以通过V域（非零元值域，但在表头结点中为next，指向下一个表头结点）相链接。另外，再增加一个附加结点（由指针hm指示，行、列域分别为稀疏矩阵的行、列数目），附加结点指向第一个表头结点，则整个十字链表可由hm指针惟一确定。,33,十字链表的数据类型描述,struct linknode int i, j; struct linknode *cptr, *rptr; union vnext /*定义一个共用体*/ int v; /*表结点使用V域,表示非零元值*/ struct linknode *next; /*表头结点使用next域*/ k; ,34,稀疏矩阵的十字链表,35,稀疏矩阵的运算,矩阵加法 矩阵转置 矩阵乘法,36,5.4 广义表的定义,37,5.5 广义表
