第五章多维数组和广义表
多维数组
一般用顺序存储的方式表示数组常用方式有)行优先顺序将数组元素按行向量排列;)列优先顺序将数组元素按列向量排列
计算地址的函数LOC(Aij)=LOC(Acc)+((ic)*(dc+)+jc)*d
矩阵的压缩存储
为多个非零元素分配一个存储空间;对零元素不分配存储空间
对称矩阵
在一个n阶的方阵A中元素满足Aij=Aji <=ij<=n;称为对称矩阵
元素的总数为n(n+)/;
设I=i或j中大的一个数;J=i或j中小的一个数;
则k=I*(I+)/+J;
地址计算LOC(Aij)=LOC(sa[k])=LOC(sa[])+k*d= LOC(sa[])+ (I*(I+)/+J )*d
三角矩阵
以主对角线划分三角矩阵有上三角和下三角;上三角的主对角线下元素均为常数c;下三角的主对角线上元素均为常数c
元素总数为(n(n+)/)+;
以行优先顺序存放的Aij与SA[k]的关系
上三角阵k=i*(ni+)/+ji;
下三角阵k=i*(i+)/+j;
对角矩阵
所有的非零元素集中在以主对角线为中心的带状区域相邻两侧元素均为零|ij|>(k)/
以行优先顺序存放的Aij与SA[k]的关系k=i+j;
稀疏矩阵
当矩阵A中有非零元素S个且S远小于元素总数时称为稀疏矩阵对其压缩的方法有顺序存储和链式存储
三元组表
将表示稀疏矩阵的非零元素的三元组(行号列号值)按行或列优先的顺序排列得到的一个结点均是三元组的线性表将该表的线性存储结构称为三元组表其类型定义
#define maxsize
typedef int datatype;
typedef struct{
int ij;
datatype v;
}trituplenode;
typedef struct{
trituplenode data[maxsize];
int mnt;
}tritupletable;
带行表的三元组表
在按行优先存储的三元组表中加入一个行表记录每行的非零元素在三元组表中的起始位置类型定义
#define maxrow
typedef struct{
tritulpenode data[maxsize];
int rowtab[maxrow];
int m n t;
}rtritulpetable;
广义表的概念
广义表是线性表的推广广义表是n个元素的有限序列元素可以是原子或一个广义表记为LS
若元素是广义表称它为LS的子表若广义表非空则第一个元素称表头其余元素称表尾
表的深度是指表展开后所含括号的层数
把与树对应的广义表称为纯表它限制了表中成分的共享和递归;
允许结点共享的表称为再入表;
允许递归的表称为递归表;
相互关系线性表∈纯表∈再入表∈递归表;
广义表的特殊运算)取表头head(LS);)取表尾tail(LS);
附二:
第五章多维数组和广义表
**************************************************************************************
数组一般用顺序存储的方式表示存储的方式有 ·行优先顺序也就是把数组逐行依次排列PASCALC
·列优先顺序就是把数组逐列依次排列FORTRAN
**************************************************************************************
地址的计算方法 ·按行优先顺序排列的数组LOCa(ij)=LOCa()+((i)*n+(j))*d
·按列优先顺序排列的数组LOCa(ij)=LOCa()+((j)*n+(i))*d
**************************************************************************************
矩阵的压缩存储为多个相同的非零元素分配一个存储空间;对零元素不分配空间
特殊矩阵的概念所谓特殊矩阵是指非零元素或零元素分布有一定规律的矩阵
稀疏矩阵的概念一个矩阵中若其非零元素的个数远远小于零元素的个数则该矩阵称为稀疏矩阵
*************************************************************************************
特殊矩阵的类型 ·对称矩阵满足a(ij)=a(ji)元素总数n(n+)/I=max(ij)J=min(ij)LOCa(ij)=LOC(sa[])+(I*(I+)/+J)*d
·三角矩阵 ·上三角阵k=i*(ni+)/+jiLOCa(ij)=LOC(sa[])+k*d
·下三角阵k=i*(i+)/+jLOCa(ij)=LOC(sa[])+k*d
·对角矩阵k=i+jLOCa(ij)=LOC(sa[])+k*d
*************************************************************************************
稀疏矩阵的压缩存储方式用三元组表把非零元素的值和它所在的行号列号做为一个结点存放在一起用这些结点组成的一个线性表来表示但这种压缩存储方式将失去随机存储功能加入行表记录每行的非零元素在三元组表中的起始位置即带行表的三元组表
************************************************************************
广义表是n(n≥)个元素的有限序列其中的元素是原子或者是一个广义表
广义表表头和表尾的概念 ·若广义表LS非空(n≥)则这个广义表的第一个元素就是表头
·其余的元素组成的表称为LS的表尾所以表尾必是一个子表
广义表有两种表示法一种是括号表示法一种是图形表示法
广义表与树(形结构)相对应这个广义表就是纯表
如果一个广义表的结点又可以被其他结点所共享则这个表称为再入表
允许递归的表称为递归表
线性表∈纯表(树)∈再入表∈递归表 可见广义表是对线性表和树的推广
广义表有两个特殊的基本运算 ·取表头head(LS)取表中的第一个数据元素不能对空表操作
·取表尾tail(LS);取除表头外其余数据元素构成的子表不能对空表操作
