《多维数组和广义表》PPT课件.ppt

第五章 多维数组和广义表,一、课程内容 5.1 多维数组 5.2 矩阵的压缩存储 5.3 广义表的概念 二、学习目的与要求 本章的目的是介绍多维数组的逻辑结构特征及其存储方式，特殊矩阵和稀疏矩阵的压缩存储方法及广义表的概念。本章重点是熟悉多维数组的存储方式、矩阵的压缩存储方式、广义表的定义及其求表头和表尾的运算，难点是稀疏矩阵的压缩存储表示下实现的算法。,5.1 多维数组,1. 数组的定义 数组是由一组类型相同的数据元素构造而成的。数组元素在数组中的相对位置是由下标确定的。 一维数组、二维数组。 二维数组可称为矩阵。 a11 a12 a1n Amn= a21 a22 a2n am1 am2 amn 图51 二维数组结构,m维数组An1n2nm的每个元素ai1i2im都属于m个向量，最多可以有m个直接前趋和m个直接后继。 如把数据元素的下标顺序变成线性表的序号，则一维数组就是一个线性表。 数组虽然是线性表的特例,但关于数组的运算与一般线性表的运算不同，数组的主要运算有两种： （1）给定一组下标，存取相应的数据元素； （2）给定一组下标，修改相应的数据元素。,2. 数组的顺序存储结构 数组的顺序存储结构指的是用一组连续的存储单元依次存放数组元素。 (1) 行优先顺序 行优先顺序：将数组元素按行向量排列，行优先顺序规定为先排最右的下标，从右向左，最后排最左下标。 例：写出A34、A234元素按行优先顺序。 (2) 列优先顺序 列优先顺序：将数组元素按列向量排列，列优先顺序规定为先排最左下标，从左向右，最后 排最右下标。,二维数组Amn按“行优先顺序”存储在内存中，假设每个元素占d个存储单元，则aij的地址计算函数为：LOC(aij)=LOC(a11)+(i-1)n+j-1d 对应C语言的二维数组：DataType Amn; 数组Amn的两个下标的下界均为0，上界分别为m-1、n-1，每个数据元素占k个存储单元，二维数组中任一元素ai,j的存储位置可由下列公式确定。 loci,j=loc0,0+(i* n + j ) * k 其中，loc0,0是A00的存储位置，loci,j是Aij的存储位置。这个式子确定了C语言的二维数组元素的位置和下标的关系。 例：int a35; &a23=,举例： 1. 给定整型数组b35，b00的存储地址为1200,试求在行序为主的存储方式下： (1)b24的存储地址； (2)该数组占用的字节数。 2. 二维数组A-12,36共含有多少个元素？ 三维数组Rc1d1,c2d2,c3d3共含有多少个元素？ 3. 数组中B110,-26,28以行优先顺序存储，设第一个元素的首地址是100,每个元素点3个存储长度的存储空间，则元素5,0,7的存储地址是多少？,5.2 矩阵的压缩存储,对于矩阵，关心的是如何存储它的元素，使矩阵的各种运算能有效地进行。 对于阶数很高的矩阵，同时在矩阵中有许多值相同的元素或者零元素，为了节省存储，可对这类矩阵进行压缩存储。 压缩存储：即为多个相同的非零元素只分配一个存储空间，对零元素不分配空间。,5.2.1 特殊矩阵 所谓特殊矩阵（Special Matrices）是指非零元素或零元素的分布有一定规律的矩阵。 1.对称矩阵 在一个n阶方阵A中，若元素满足下述性质： aij=aji 0i，jn-1 则称A为对称矩阵。如图所示：,怎样存储该矩阵的元素？,存储元素为：1,5,0,1,8,9,3,0,2,5,7,0,6,1,3，共15个。将这些元素存放在一个向量sa0n(n+1)/2-1中。 怎样通过元素下标在sa中找到该元素的值？,aij和sak的对应关系： 若i=j,则aij在下三角矩阵中，之前的i行（第0行到第i-1行）共有1+2+i=i*(i+1)/2个元素，在第i行上， aij前有j个元素，因此： k=i*(i+1)/2+j (0=kn*(n+1)/2) 若ij，则aij在上三角矩阵中， aij=aji则： k=j*(j+1)/2+i (0=kn*(n+1)/2),令I=max(i,j)，J=min(i,j)，则k和i，j的对应关系为： k=I(I+1)/2+J 0kn(n+1)/2 aij的地址计算公式： LOC(aij)=LOC(sa0)+I(I+1)/2+Jd 举例： 是4*4的对称阵，采用压缩存储方式存储，已知00 的存储地址为1,求32的存储地址。,2. 三角矩阵 以主对角线划分，三角矩阵有上三角和下三角两种。上三角矩阵的下三角（不包括主角线）中的元素均为常数c。下三角矩阵正好相反，它的主对角线上方均为常数c。在多数情况下，三角矩阵的常数c为零。 上三角矩阵 下三角矩阵,上三角矩阵中，sak和aij的对应关系是： 下三角矩阵中，sak和aij的对应关系是：,3. 对角矩阵 对角矩阵中，所有的非零元素集中在以主对角线为中心的带状区域中，即除了主对角线和主对角线相邻两侧的若干条对角线上的元素之外，其余元素皆为零。如图所示： 对角矩阵可按行优先顺序或对角线的顺序，将其压缩存储到一个向量中，并且也能找到每个非零元素和向量下标的对应关系。,5.2.2 稀疏矩阵,设矩阵Amn中有s个非零元素，若s远远小于矩阵元素的总数（即smn），则称A为稀疏矩阵。 当用三元组来表示非零元时，对稀疏矩阵进行压缩存储通常有两类方法：顺序存储和链式存储。 1.三元组表 若将表示稀疏矩阵的非零元素的三元组按行优先（或列优先）的顺序排列（跳过零元素），则得到一个其结点均是三元组的线性表，我们将该线性表的顺序存储结构称为三元组表。 （见图56）,图56 稀疏矩阵的三元组表,三元组表类型描述： #define MaxSize 10000 typedef int DataType; typedef struct int i,j; /非零元素的行、列号 DataType v; /非零元素的值 TriTupleNode; typedef struct TriTupleNode dataMaxSize; int m,n,t; /矩阵的行数、列数及非零元素个数 TriTupleTable;,矩阵转置运算的算法5-2： void TransMatrix(TriTupleTable *b,TriTupleTable *a) int p,q,col; b-m=a-n; b-n=a-m; b-t=a-t; if(b-tn;col+) for(p=0;pt;p+) if(a-datap.j=col) b-dataq.v=a-datap.v; b-dataq.i=a-datap=j; b-dataq.j=a-datap=i; q+; ,2.十字链表 稀疏矩阵的链接存储是一种既带行指针又带列指针的链接存储结构。 对稀疏矩阵的链接存储就是对其相应的三元组线性表进行链接存储，链接表中的每一个结点表示一个非零元素的三元组，第一个结点既处于同一行的单链表中，又处于同一列的单链表中，即处于所在行的单链表和所在列的单链表的交点处，整个稀疏矩阵由十字交叉链表结构组成，故称十字链表。,还需设置两个指针型数组，一个用来存放行链表的表头指针，另一个用来存放列链表的表头指针，这样对矩阵非零元素的访问，既可在行链表上访问，又可在列链表上访问。,只有当矩阵非零元素少于总元素个数的20%时，采用十字链表才有可能节省存储空间。,5.3 广义表的概念,1. 广义表的定义 广义表（Lists）又称列表，是线性表的推广。广义表是n(n0)个元素的有限序列，通常记作 LS=（a1,a2,an） 其中LS是广义表的名字，n为它的长度，ai是原子或者是一个广义表。若ai是广义表，则称它为LS的子表。 为了区分原子和广义表，书写时用大写字母表示广义表，用小写字母表示原子。 若广义表LS非空（n1），则a1是LS的表头，其余元素组成的表（a2,a3,an）称为LS的表尾。 广义表是递归定义的，广义表中可以包含广义表。 一个表的“深度（Depth）”是指表展开后所含括号的层数。,通常把与树对应的广义表称为纯表，它限制了表中成分的共享和递归；把允许结点共享的表称为再入表；而把允许递归的表称为递归表。它们之间的关系满足：递归表 再入表 纯表 线性表。 广义表三个特殊的基本运算：取表头GetHead(LS)、取表尾GetTail(LS)和表长Length(LS)。 根据表头、表尾的定义可知：任何一个非空广义表的表头是表中第一个元素，它可以是原子，也可以是子表，而其表尾必定是子表。 2. 广义表的举例 （1）E=( ) GetHead(E)=空 GetTail(E)=( ) Length(E)=0,（2）L=(a,b) GetHead(L)=a GetTail(L)=(b) Length(L)=2 （3） A=(x,L)=(x,(a,b) GetHead(A)=x GetTail(A)=(L)=(a,b) Length(A)=2 （4） B=(A,y)=(x,(a,b),y) GetHead(B