第6章 多维数组和广义表
知识点分析
1. 多维数组概念
多维数组是向量的推广，对于二维数组A axn既可以看成m行向量组成的向量，也可以 看成
n行向量组成的向量。多维数组在计算机中有两种存储形式：按行优先顺序存储和按列 优先顺序
存储。
2. 多维数组的存储
二维数组 aij的地址为：LOC(a.j) = LOC(aoo) + ( iXn + j ) X d 的语言)
(0 下标起始
三维数组 am的地址为:LOC(aljk)=LOC(a0co) + ( (iXnXp+ jXp +k) Xd (0 下标起始 的语言)
d为每个数据元素占有的字节数。 ? ??
3. 特殊矩阵
在矩阵中非篆元素或篆元素的分布有一定规律的矩阵称为特殊矩阵，如三角矩阵、对称 矩阵、稀疏矩阵等。当矩阵的阶数很大时，用普通的二维数组存储这些特殊矩阵将会占用很 多的存储单元。从节约存储空间的角度考虑，以下特殊矩阵的存储方法。
(1) 对称矩阵
对称矩阵是一种特殊矩阵，n阶方阵的元素满足性质：a：产a.\。对 称矩阵是关于主对角线的对称，因此只需存储上三角或下三角部分的数据即可。
(2) 三角矩阵
三角矩阵的特殊性是以主对角线划分矩阵。下三角矩阵，主对角线以上均为同一个常数; 上三角矩阵，主对角线以下均为同一个常数，可以采用压缩存储。
(3) 稀疏矩阵
在的矩阵中有t个非篆元素，且t远小于mxn,这样的矩阵称稀疏矩阵。为了节 约存储空间，稀疏矩阵中零元素无需存储，只需存储矩阵中的非零元素。稀疏矩阵常用的有： 三元组表存储、带行指针的链表存储、十字链表存储等存储方法。
4. 广义表
广义表是n (n^O)个数据元素的有序序列，广义表的元素可以是单元素，也可以是一 个广义表。由于广义表的元素有两种形式，所以其结点的存储形式也有两种：
(1) 表结点由标志域、表头指针域、表尾指针域组成。 (2) 原子结点由标志域和值域组成。 5. 广义表与线性表的区别和联系
线性表是具有相同类型的n个数据元素的有限序列，记为勿、生、a：u……、a“广义 表也是n个数据元素的有限序列，记为a“ a2.念、……、％。线性表中的元素必须具有相 同的类型，而广义表中的成员，既可以是单个元素(原子)，也可以是一个广义表(子表)。 当广义表中的每一个①元素都是数据元素，且具有相同类型时，则它就是一个线性表，因 此可以说广义表是线性表的一种推广，或者说线性表是广义表的一个特例。
典型习题分析
【例1】设二维数组A5X6的每个元素占4个字节，存储器按字节编址。已知A的起 始地址为
2000,计算：
(1) 数组的大小
(2) A的终端结点a付的存储地址 (3) 按行优先顺序存储时，825的存储地址 (4) 按列优先顺序存储时，a25的存储地址
答：
(1) 数组的大小(即数组A共占多少字节)：5X6X4=120Bo
(2) —个结点釦的存储地址是该结点所占用的存储空间的第1个字节的地址(即起始地址), 它
等于：基地址+排在弧之前的结点个数X每个结点所占用的字节数。
ai5的起始地址:LOC(a<5) =2000+ (4X 6+5) X 4=2116
(3) 在按行优先顺序存储时，排在a。之前的结点的个数为：在前i行(即0~i-1行)上共
有ixn个结点，在第i行上an之前有j个结点(O'j-1列)。所以按行优先存储的地址计 算公式为：
L0C(ai.i)= L0C(aco) + (iXn+j)xd LOC (a25)= 2000+(2x6+5)x4=2068
(4) 在按列优先顺序存储时，排在8口之前的结点的个数为：在前j列(即0~j-l列)上共
有jxm个结点，在第j列上am之前有i个结点(O'i-1行)。所以按列优先存储的地址计 算公式为：
LOC(au)= LOC(aoo) + (jXm+i)xd LOC(325)=2000+ (5 x 5+2) x 4=2108
【例2]特殊矩阵和稀疏矩阵哪一种压缩存储后会失去随机存储功能为什么
答：对于像三角矩阵等特殊矩阵由于压缩存储时将其存储在一个线性数组向量中，矩阵元 素8订的下标i, j与它在向量中的对应元素bk下标k有一对应关系，故不会失去随机存储功 能。而像稀疏矩阵，其压缩存储的方式是将其非零元素存储在一个三元组中，以三元组数组 a[k]形式存储，矩阵元素酮下标i, j与数组中对应元素a[k]行下标k无对应关系，故失 去随机存储功能。
【例3】求矩阵的转置矩阵
分析：对于一个nixn的矩阵心 其转置矩阵是一个nxm的矩阵B心KB[i] [j]=A[ j] [i],
OWi n, OWi mo其函数如下：
void trs (A,B)
maxix A.B； (int i,j;
for (i=0；i for (j=0；j B[j][i]=A[i][j]; } 【例4】求两个矩阵的乘 分析：设两个矩阵相乘：C=AXB, 其中A是一个mxn的矩阵，B是一个nxk的矩阵，则C为一个mXk的矩阵。其函数如下: void mut(C,A,B) maxix At B,C; { int i,j,k； for (i=0；i〈m；i++) for (j=0；j ' { C[i][j]=O； for (k=0；k C[i][j]=C[i][j]+A[i][k]*B[k][j]; } ) 【例5】若矩阵扎\中存在一个元素a,满足ax是第i行最小的元素，且是第j列最大的 元素，则称是矩阵A的鞍点，请编写一个算法，找出矩阵A的所有鞍点。 分析：找矩阵A的所有鞍点的基本思想是：先逐行找出本行值最小的元素.确定其所在的列, 并在此列中选值最大的元素，若两者值相等，即选中一个鞍点。 void Spoint(int *at int m,int n) $ { int i,j,k t c.max.min,r=0； for (i=0；i 五.编程题答案 (1)【程序代码】 tfinclude ^define ERROR - 99999 typedef struct { int row； int col； int data； $ }Triple； int MDSum(Triple *a) { int i; int sum-0； if (a[0]. row!=a[0]. col)
数据结构答案-第6章-多维数组和广义表学习指导
