多维数组和广义表.ppt

1、第五章 多维数组和广义表,一、课程内容 5.1 多维数组 5.2 矩阵的压缩存储 5.3 广义表的概念 二、学习目的与要求 本章的目的是介绍多维数组的逻辑结构特征及其存储方式，特殊矩阵和稀疏矩阵的压缩存储方法及广义表的概念。本章重点是熟悉多维数组的存储方式、矩阵的压缩存储方式、广义表的定义及其求表头和表尾的运算，难点是稀疏矩阵的压缩存储表示下实现的算法。,5.1 多维数组,1. 数组的定义 数组是由一组类型相同的数据元素构造而成的。数组元素在数组中的相对位置是由下标确定的。 一维数组、二维数组。 二维数组可称为矩阵。 a11 a12 a1n Amn= a21 a22 a2n am1 am2 a

2、mn 图51 二维数组结构,m维数组An1n2nm的每个元素ai1i2im都属于m个向量，最多可以有m个直接前趋和m个直接后继。 如把数据元素的下标顺序变成线性表的序号，则一维数组就是一个线性表。 数组虽然是线性表的特例,但关于数组的运算与一般线性表的运算不同，数组的主要运算有两种： （1）给定一组下标，存取相应的数据元素； （2）给定一组下标，修改相应的数据元素。,2. 数组的顺序存储结构 数组的顺序存储结构指的是用一组连续的存储单元依次存放数组元素。 (1) 行优先顺序 行优先顺序：将数组元素按行向量排列，行优先顺序规定为先排最右的下标，从右向左，最后排最左下标。 例：写出A34、A234

3、元素按行优先顺序。 (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是

4、Aij的存储位置。这个式子确定了C语言的二维数组元素的位置和下标的关系。 例：int a35; 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-

5、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.十字链表 稀疏矩阵的链接存储是一种既带行指针又带列指针的链接存储结构。 对稀疏矩阵的链接存储就是对其相应的三元组线性表进行链接存储，链接表中的每一个结点表示一个非零元素的三元组，第一个结点既处于同一行的单链表中，又处于同一列的单链表中，即处于所在行的单链表和所在列的单链表的交点处，整个稀疏矩阵由十字交叉链表结构组成，故称十字链表。,还需设置两个指针型

6、数组，一个用来存放行链表的表头指针，另一个用来存放列链表的表头指针，这样对矩阵非零元素的访问，既可在行链表上访问，又可在列链表上访问。,只有当矩阵非零元素少于总元素个数的20%时，采用十字链表才有可能节省存储空间。,5.3 广义表的概念,1. 广义表的定义 广义表（Lists）又称列表，是线性表的推广。广义表是n(n0)个元素的有限序列，通常记作 LS=（a1,a2,an） 其中LS是广义表的名字，n为它的长度，ai是原子或者是一个广义表。若ai是广义表，则称它为LS的子表。 为了区分原子和广义表，书写时用大写字母表示广义表，用小写字母表示原子。 若广义表LS非空（n1），则a1是LS的表头，

7、其余元素组成的表（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)=A=(x,(a,b) GetTail(B)=(y) Length(B)=2,（5）C=(A,B)=(x,(a,b),(x,(a,b),y)