当前位置：文档之家 › 数据结构第5章 数组和广义表

数据结构第5章 数组和广义表

  • 格式：ppt
  • 大小：558.50 KB
  • 文档页数：82

下载文档原格式

  / 82

合集下载

数据结构——用C语言描述(第3版)教学课件第5章 数组与广义表

数据结构——用C语言描述(第3版)教学课件第5章 数组与广义表
第5章 数组和广义表
5.1 数组的定义和运算 5.2 数组的顺序存储和实现 5.3 特殊矩阵的压缩存储
5.3.1 三角矩阵 5.3.2 带状矩阵 5.3.3 稀疏矩阵 5.4 广义表 5.5 总结与提高
5.1 数组的定义和运算
数组是一种数据类型。从逻辑结构上看，数组可以 看成是一般线性表的扩充。二维数组可以看成是线 性表的线性表。例如：
Am×n=
a12 a12 ┅
a1j
┅ a1n
a21 a22 ┅
a2j
┅ a2n
┇┇
ai1 ai2 ┅
aij
┇┇
┅ ain
am1 am2 ┅
amj
┅ amn
矩阵Am×n看成n个列向量的线性表,即j=(a1j,a2j, …,amj)
我们还可以将数组Am×n看成另外一个线性表: B=(1，,2,，… ，m)，其中i（1≤i ≤m）本身也是一个线性表， 称为行向量，即： I= （ai1，ai2， …，aij ，…，ain）。
Loc[j1,j2,j3]=Loc[c1,c2,c3]+ α1*(j1-c1)+ α2*(j2-c2)+ α3(j3-c3)
=Loc[c1,c2,c3]+ Σαi*(ji-ci) （1≤i≤3）
由公式可知Loc[j1,j2,j3]与j1,j2,j3呈线性关系。 对于ｎ维数组A(c1:d1,c2:d2，…,cn,dn)，我们只要把上式推 广，就可以容易地得到ｎ维数组中任意元素aj1j2…jn的存储 地址的计算公式。
疏矩阵。
0 12 9 0 0 0 0
0 0 3 0 0 15
0 0 0 00 0 0
12 0 0 0 18 0
M6×7= -3 0 0 0 0 14 0

数据结构第五章 数组与广义表

数据结构第五章 数组与广义表
an-1,n-1
压缩存储方法：只需要存储下三角 （含对角线）上的元素。可节省一 半空间。
可以使用一维数组Sa[n(n+1)/2]作为n阶对称矩阵A的存 储结构，且约定以行序为主序存储各个元素，则在Sa[k]和矩
阵元素aij之间存在一一对应关系： （下标变换公式）
i(i+1)/2 + j 当i≥j k = j(j+1)/2 + i 当i<j
q = cpot[col];
T.data[q].i = M.data[p].j; T.data[q].j = M.data[p].i; T.data[q].e = M.data[p].e; ++cpot[col]; }
分析算法FastTransposeSMatrix的时间 复杂度：
for (col=1; col<=M.nu; ++col) … … for (t=1; t<=M.tu; ++t) … … for (col=2; col<=M.nu; ++col) … … for (p=1; p<=M.tu; ++p) … …
//对当前行中每一个非零元
处
brow=M.data[p].j;
理
if (brow < N.nu ) t = N.rpos[brow+1];
M
else { t = N.tu+1 }
的
for (q=N.rpos[brow]; q< t; ++q) { ccol = N.data[q].j; // 乘积元素在Q中列号
一、三元组顺序表
对于稀疏矩阵，非零元可以用三元组表示， 整个稀疏矩阵可以表示为所有非零元的三元组所 构成的线性表。例如：

数据结构 5数组和广义表A

数据结构 5数组和广义表A
12
1 Status Locate(Array A,va_list ap,int &off) 2{ 3 //若ap指示的各下标值合法，则求出该元素在A中，相对地
址off
4 off=0; 5 for(i=0;i<A.dim;++i) 6 { 7 ind=va_arg(ap,int); 8 if(ind<0||ind>A.bounds[i]) return OVERFLOW; 9 off+=A.constants[i] *ind; 10 } 11 return OK; 12 }
行数 总列数，即 第2维长度 元素个数
ij
补充：计算二维数组元素地址的通式
设一般的二维数组是A[c1..d1, c2..d2]，这里c1,c2不一定是0。
单个元素 长度
二维数组列优先存储的通式为： LOC(aij)=LOC(ac1，c2)+[(j-c2)*(d1-c1+1)+i-c1)]*L
6
例1〖软考题〗：一个二维数组A[1..6, 0..7]，每个数组元素
16
5.4
1、定义：
广义表的定义
广义表是线性表的推广，也称为列表（lists） 记为： LS = ( a1 , a2 , ……， an ) 广义表名 表头(Head） 表尾 (Tail) n是表长
在广义表中约定：
① 第一个元素是表头，而其余元素组成的表称为表尾； ② 用小写字母表示原子类型，用大写字母表示列表。
13
1 Status Value(Array A,ElemType &e,…){ 2 //A是n维数组，e为元素变量，随后是n个下标值，若各下
标不超界，则e赋值为所指定的A的元素值，即将指定元素值 读到e变量中。

《数据结构与算法》第五章-数组和广义表学习指导材料

《数据结构与算法》第五章-数组和广义表学习指导材料

《数据结构与算法》第五章数组和广义表本章介绍的数组与广义表可视为线性表的推广，其特点是数据元素仍然是一个表。

本章讨论多维数组的逻辑结构和存储结构、特殊矩阵、矩阵的压缩存储、广义表的逻辑结构和存储结构等。

5.1 多维数组5.1.1 数组的逻辑结构数组是我们很熟悉的一种数据结构，它可以看作线性表的推广。

数组作为一种数据结构其特点是结构中的元素本身可以是具有某种结构的数据，但属于同一数据类型，比如：一维数组可以看作一个线性表，二维数组可以看作“数据元素是一维数组”的一维数组，三维数组可以看作“数据元素是二维数组”的一维数组，依此类推。

图5.1是一个m行n列的二维数组。

5.1.2 数组的内存映象现在来讨论数组在计算机中的存储表示。

通常，数组在内存被映象为向量，即用向量作为数组的一种存储结构，这是因为内存的地址空间是一维的，数组的行列固定后，通过一个映象函数，则可根据数组元素的下标得到它的存储地址。

对于一维数组按下标顺序分配即可。

对多维数组分配时，要把它的元素映象存储在一维存储器中，一般有两种存储方式：一是以行为主序（或先行后列）的顺序存放，如BASIC、PASCAL、COBOL、C等程序设计语言中用的是以行为主的顺序分配，即一行分配完了接着分配下一行。

另一种是以列为主序（先列后行）的顺序存放，如FORTRAN语言中，用的是以列为主序的分配顺序，即一列一列地分配。

以行为主序的分配规律是：最右边的下标先变化，即最右下标从小到大，循环一遍后，右边第二个下标再变，…，从右向左，最后是左下标。

以列为主序分配的规律恰好相反：最左边的下标先变化，即最左下标从小到大，循环一遍后，左边第二个下标再变，…，从左向右，最后是右下标。

例如一个2×3二维数组，逻辑结构可以用图5.2表示。

以行为主序的内存映象如图5.3（a）所示。

分配顺序为：a11 ，a12 ，a13 ，a21 ，a22，a23 ; 以列为主序的分配顺序为：a11 ，a21 ，a12 ，a22，a13 ，a23 ; 它的内存映象如图5.3（b）所示。

数组与广义表

数组与广义表

其中：1） 矩阵Am×n看成n个列向量的线性表
2） 每个列向量：αj=（a1j, a2j, a3j, …, amj ）(0≤j ≤n-1) 3） ai,j在列方向上有一个前驱ai-1,j, 有一个后继ai+1,j
• 或者,可以看成是一个线性表：A=(a0,a1,……,am-1)
• 其中每个数据元素aj是一个行向量形式的线性表： A
}ADT Array
• • • N维数组含有元素的个数： b1 × b2 × … × bn 第i维的长度： bi 元素下标(j1 ， j2， … ，jn)，0 ≤ ji ≤ bi -1
5.1 数组示例：
数组的定义
a00 a01 …….. a10 a11 …….. am-1,n-1 …….. a0,n-1 a1,n-1 am-1,n-1
1 2 … i-1 aij
*(A.base + off) = e;
return OK; }
5.3 矩阵的压缩存储 特殊矩阵和稀疏矩阵
特殊矩阵：矩阵中很多值相同的元素并且它们的分布 有一定的规律。 稀疏矩阵：矩阵中有很多零元素。 压缩存储的基本思想是： ⑴ 为多个值相同的元素只分配一个存储空间；
⑵ 对零元素不分配存储空间。
5.3.1 3 6 4 7 8
普通高等教育“十一五”国家级规划教材
设一个系统中二维数组采用行序为主的存储方式，已知二 维数组a[10][8]中每个元素占用四个存储单元，且第一 个数据元素地址是1000，求a[4][5]的存储地址？
解： Loc(a[4][5])=Loc(a[0][0])+(i*m+j)*k =1000+(4*8+5)*4 =1148
L：每个数据元素占用的存储单元

数据结构第5章

数据结构第5章

第5章：数组和广义表 1. 了解数组的定义；填空题：1、假设有二维数组A 6×8，每个元素用相邻的6个字节存储，存储器按字节编址。

已知A 的起始存储位置（基地址）为1000，则数组A 的体积（存储量）为 288 B ；末尾元素A 57的第一个字节地址为 1282 。

2、三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的 行下标 、 列下标 和 元素值 。

2. 理解数组的顺序表示方法会计算数组元素顺序存储的地址；填空题：1、已知A 的起始存储位置（基地址）为1000，若按行存储时，元素A 14的第一个字节地址为 (8+4)×6+1000=1072 ；若按列存储时，元素A 47的第一个字节地址为 (6×7＋4)×6＋1000）＝1276 。

(注：数组是从0行0列还是从1行1列计算起呢？由末单元为A 57可知，是从0行0列开始！) 2、设数组a[1…60, 1…70]的基地址为2048，每个元素占2个存储单元，若以列序为主序顺序存储，则元素a[32,58]的存储地址为 8950 。

答：不考虑0行0列，利用列优先公式： LOC(a ij )=LOC(a c 1，c 2)+[(j-c 2)*(d 1-c 1+1)+i-c 1)]*L 得：LOC(a 32,58)=2048+[(58-1)*(60-1+1)+32-1]]*2＝8950选择题：（ A ）1、假设有60行70列的二维数组a[1…60, 1…70]以列序为主序顺序存储，其基地址为10000，每个元素占2个存储单元，那么第32行第58列的元素a[32,58]的存储地址为 。

（无第0行第0列元素）A ．16902B ．16904C ．14454D ．答案A, B, C 均不对 答：此题（57列×60行＋31行）×2字节＋10000=16902( B )2、设矩阵A 是一个对称矩阵，为了节省存储，将其下三角部分（如下图所示）按行序存放在一维数组B[ 1, n(n-1)/2 ]中，对下三角部分中任一元素a i,j (i ≤j), 在一维数组B 中下标k 的值是：A ．i(i-1)/2+j-1B ．i(i-1)/2+jC ．i(i+1)/2+j-1D ．i(i+1)/2+j3、从供选择的答案中，选出应填入下面叙述 ？ 内的最确切的解答，把相应编号写在答卷的对应栏内。

数据结构数组与广义表知识点总结

数据结构数组与广义表知识点总结数组是一种线性数据结构，可以存储多个相同类型的元素。

它的特点是元素的大小固定，并且在内存中是连续存储的。

数组的访问方式是通过下标来访问，下标从0开始。

数组可以在编程中应用于各种情况，比如存储一组数字、一组字符串等。

广义表是一种扩展的线性数据结构，可以存储不同类型的元素。

它由元素和表构成，其中表可以是空表、原子或子表。

广义表可以递归定义，即子表可以包含更多的子表。

广义表的访问方式是通过递归来访问，可以对表的元素进行遍历和操作。

在数据结构中，数组和广义表都有自己的特点和用途，下面对它们的知识点进行总结：1.数组的特点及应用：-数组是一种线性数据结构，可以存储多个相同类型的元素。

-数组的内存分配是连续的，可以通过下标来访问元素。

-数组的大小固定，一旦定义后不能改变。

-数组的访问速度快，可以通过下标直接访问元素。

-数组适合用于存储一组相同类型的数据，比如一组数字、一组字符串等。

-数组的应用场景包括但不限于：排序算法、查找算法、图像处理、矩阵运算等。

2.数组的操作和常用算法：-初始化：可以直接赋值或使用循环初始化数组。

-访问元素：通过下标访问元素，下标从0开始。

-修改元素：直接通过下标修改元素的值。

-插入元素：需要移动插入位置之后的元素。

-删除元素：需要移动删除位置之后的元素。

-查找元素：可以使用线性查找或二分查找等算法。

-排序算法：比如冒泡排序、选择排序、插入排序等。

-数组还有一些常用的属性和方法，比如长度、最大值、最小值等。

3.广义表的特点及应用：-广义表是一种扩展的线性数据结构，可以存储不同类型的元素。

-广义表由元素和表构成，表可以是空表、原子或子表。

-广义表可以递归定义，即子表可以包含更多的子表。

-广义表的访问方式是通过递归遍历和操作。

-广义表适合存储一组不同类型的数据，比如存储学生信息、函数调用栈等。

-广义表的应用场景包括但不限于：函数式编程、树的表示、图的表示等。

中南大学数据结构与算法第5章数组和广义表课后作业答案

第5章数组与广义表习题练习答案5.1请按行及按列优先顺序列出四维数组A2*3*2*3的所有元素在内存中的存储次序，开始结点为a0000。

解：按行优先的顺序排列时，先变化右边的下标，也就是右到左依次变化，这个四维数组的排列是这样的：(将这个排列分行写出以便与阅读，只要按从左到右的顺序存放就是在内存中的排列位置) a0000a0001a0002a0010a0011a0012a0100a0101a0102a0110a0111a0112a0200a0201a0202a0210a0211a0212a1000a1001a1002a1010a1011a1012a1100a1101a1102a1110a1111a1112a1200a1201a1202a1210a1211a1212按列优先的顺序排列恰恰相反，变化最快的是左边的下标，然后向右变化，所以这个四维数组的排列将是这样的，(这里为了便于阅读，也将其书写为分行形式)：a0000a1000a0100a1100a0200a1200a0010a1010a0110a1110a0210a1210a0001a1001a0101a1101a0201a1201a0011a1011a0111a1111a0211a1211a0002a1002a0102a1102a0202a1202a0012a1012a0112a1112a0212a02125.2 给出C语言的三维数组地址计算公式。

解：因为C语言的数组下标下界是0，所以Loc(A mnp)=Loc(A000)+((i*n*p)+k)*d其中Amnp表示三维数组。

Loc(A000)表示数组起始位置。

i、j、k表示当前元素的下标,d表示每个元素所占单元数。

5.3设有三对角矩阵A n*n，将其三条对角线上的元素逐行地存储到向量B[0...3n-3]中，使得B[k]=a ij,求：(1)用i , j 表示k的下标变换公式。

(2)用k 表示i,j 的下标变换公式。

数据结构第五章


5.3.1 特殊矩阵
是指非零元素或零元素的分布有一定规律的矩阵。
1、对称矩阵 在一个n阶方阵A中，若元素满足下述性质： aij = aji 0≦i,j≦n-1 则称A为对称矩阵。
对称矩阵中的元素关于主对角线对称，故只 要存储矩阵中上三角或下三角中的元素，这样， 能节约近一半的存储空间。

2013-7-25 第4章 18
5.3 矩阵的压缩存储

在科学与工程计算问题中，矩阵是一种常用 的数学对象，在高级语言编制程序时，常将 一个矩阵描述为一个二维数组。 当矩阵中的非零元素呈某种规律分布或者矩 阵中出现大量的零元素的情况下，会占用许 多单元去存储重复的非零元素或零元素，这 对高阶矩阵会造成极大的浪费。 为了节省存储空间，我们可以对这类矩阵进 行压缩存储：
5.2 数组的顺序表示和实现 由于计算机的内存结构是一维的， 因此用一维内存来表示多维数组，就必 须按某种次序将数组元素排成一列序列 ，然后将这个线性序列存放在存储器中 。 又由于对数组一般不做插入和删除 操作，也就是说，数组一旦建立，结构 中的元素个数和元素间的关系就不再发 生变化。因此，一般都是采用顺序存储 的方法来表示数组。
即为多个相同的非零元素只分配一个存储空间； 对零元素不分配空间。


课堂讨论： 1. 什么是压缩存储？ 若多个数据元素的值都相同，则只分配一个元素值的 存储空间，且零元素不占存储空间。 2. 所有二维数组（矩阵）都能压缩吗？ 未必，要看矩阵是否具备以上压缩条件。 3. 什么样的矩阵具备以上压缩条件？ 一些特殊矩阵，如：对称矩阵，对角矩阵，三角矩阵， 稀疏矩阵等。 4. 什么叫稀疏矩阵？ 矩阵中非零元素的个数较少（一般小于5%）
通常有两种顺序存储方式：
⑴行优先顺序——将数组元素按行排列，第i+1个行 向量紧接在第i个行向量后面。以二维数组为例，按 行优先顺序存储的线性序列为： a11,a12,…,a1n,a21,a22,…a2n,……,am1,am2,…,amn 在PASCAL、C语言中，数组就是按行优先顺序存 储的。 ⑵列优先顺序——将数组元素按列向量排列，第j+1 个列向量紧接在第j个列向量之后，A的m*n个元素按 列优先顺序存储的线性序列为： a11,a21,…,am1,a12,a22,…am2,……,an1,an2,…,anm 在FORTRAN语言中，数组就是按列优先顺序存储的。

数据结构第五章数组和广义表

数据结构第五章数组和广义表(总6页)--本页仅作为文档封面，使用时请直接删除即可----内页可以根据需求调整合适字体及大小--第五章数组和广义表：习题习题一、选择题1．假设以行序为主序存储二维数组A[1．．100,1．．100]，设每个数据元素占两个存储单元，基地址为10，则LOC(A[5，5])=( )。

A. 808B. 818C. 1010D. 10202．同一数组中的元素( )。

A. 长度可以不同 B．不限 C．类型相同 D. 长度不限3．二维数组A的元素都是6个字符组成的串，行下标i的范围从0到8，列下标j的范圈从1到10。

从供选择的答案中选出应填入下列关于数组存储叙述中( )内的正确答案。

(1)存放A至少需要( )个字节。

(2)A的第8列和第5行共占( )个字节。

(3)若A按行存放，元素A[8]【5]的起始地址与A按列存放时的元素( )的起始地址一致。

供选择的答案：(1)A. 90 B. 180 C. 240 D. 270(2) A. 108 B. 114 C. 54 D. 60(3)[8][5] B. A[3][10] [5][8] [O][9]4.数组与一般线性表的区别主要是( )。

A.存储方面B.元素类型方面C.逻辑结构方面D.不能进行插入和删除运算5．设二维数组A[1．．m，1．．n]按行存储在数组B[1．．m×n]中，则二维数组元素A[i，j]在一维数组B中的下标为( )。

A. (i-l)×n+jB. (i-l)×n+j-lC．i×(j-l) D. j×m+i-l6．所谓稀疏矩阵指的是( )。

A.零元素个数较多的矩阵B.零元素个数占矩阵元素中总个数一半的矩阵C.零元素个数远远多于非零元素个数且分布没有规律的矩阵D.包含有零元素的矩阵7．对稀疏矩阵进行压缩存储的目的是( )。

A.便于进行矩阵运算B.便于输入和输出C.节省存储空间D. 降低运算的时间复杂度8．稀疏矩阵一般的压缩存储方法有两种，即( )。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

（3）三元组元素赋值 对于稀疏矩阵A，执行A[i][j]=x。先在三元组表示的data 数组中找到适当的位臵k，若找到了这样的元素，直接将其d 值臵为x，否则将k～t.nums个元素后移一个位臵，将指定元 素x插入到data[k]中。当位臵错误时返回false。对应的算法如 下：
bool SMatrixClass::Setvalue(int i,int j,int x) //三元组元素赋值A[i][j]=x { int k=0,k1; if (i<0 || i>=rows || j<0 || j>=cols) return false; //下标错误时返回false while (k<nums && i>data[k].r) k++; //查找第i行的第一个非零元素 while (k<nums && i==data[k].r && j>data[k].c) k++; //在第i行中查找第j列的元素
if (data[k].r==i && data[k].c==j) //找到了这样的元素 data[k].d=x; else //不存在这样的元素时插入一个元素 { for (k1=nums-1; k1>=k;k1--) //后移元素以便插入 { data[k1+1].r=data[k1].r; data[k1+1].c=data[k1].c; data[k1+1].d=data[k1].d; } data[k].r=i; data[k].c=j; data[k].d=x; nums++; } return true; //赋值成功时返回true
（2）从一个二维稀疏矩阵创建其三元组表示 以行序方式扫描二维稀疏矩阵A，将其非零的元素插入到 三元组的data数组中。对应的算法如下：
void SMatrixClass::CreateTSMatrix(int A[][MAXC],int m,int n) //创建三元组 { int i,j; rows=m; cols=n; nums=0; for (i=0;i<m;i++) { for (j=0;j<n;j++) if (A[i][j]!=0) //只存储非零元素 { data[nums].r=i; data[nums].c=j; data[nums].d=A[i][j]; nums++数组中表示的非零元素通常以行序为主序 顺序排列，它是一种下标按行有序的存储结构。这种有序 存储结构可简化大多数稀疏矩阵运算算法。
（1）三元组顺序表的初始化和销毁 三元组顺序表的初始化和销毁分别通过构造函数和析构函 数来实现，对应的算法如下：
SMatrixClass::SMatrixClass() { data=new TupNode[MaxSize]; } SMatrixClass::~SMatrixClass() { delete [] data; } //构造函数 //分配空间 //析构函数 //释放空间
LOC(ai,j)=LOC(a1,1)+[(i-1)×n+(j-1)]×k
若采用以列序为主序的存储方式，即先存储第1列，然 后紧接着存储第2列，…，最后存储第n列。此时，二维数组 的线性排列次序为： a1,1,a2,1,…,am,1,a1,2,a2,2,…,am,2,…,a1,n,a2,n,…am,n
抽象数据类型d维数组定义如下：
5.1.2 数组的存储结构
数组通常采用顺序存储方式来实现。 一维数组的所有元素依逻辑次序存放在一片连续的内存存 储单元中，其起始地址为第一个元素a1的地址即LOC(a1)，假 设每个数据元素占用k个存储单元，则任一数据元素ai的存储地 址LOC(ai)就可由以下公式求出：
可以将其压缩存放到一个一维数组b[0..n(n+1)/2-1]中，只存放 主对角和下三角部分的元素，ai,j和bk之间的映射关系：
2. 对角矩阵的压缩存储
半带宽为l的对角矩阵 ：
l条
...
l条
0
对于l=1的三对角矩阵，只存储其非零元素，并存储 到一维数组b中，即以行序为主序将a的非零元素ai,j存储到 b的元素bk中，归纳起来有k=2i+j。
}
（4）将指定位臵的元素值赋给变量 对于稀疏矩阵A，执行x=A[i][j]。先在三元组表示的data 数组中找到指定的位臵，将该处的元素值赋给x，当位臵错误 时返回false。对应的算法如下：
bool SMatrixClass::GetValue(int i,int j,int &x) //执行x=A[i][j] { int k=0; if (i<0 || i>=rows || j<0 || j>=cols) return false; //下标错误时返回false while (k<nums && data[k].r<i) k++; //查找第i行的第一个非零元素 while (k<nums && data[k].r==i && data[k].c<j) k++; //在第i行中查找第j列的元素 if (data[k].r==i && data[k].c==j) //找到了这样的元素 x=data[k].d; else x=0; //在三元组中没有找到表示是零元素 return true; //取值成功时返回true }
第5章 数组和广义表
5.1 数 组
5.1.1 数组的基本概念
从逻辑结构上看，数组是一个二元组(index,value)的集合， 对每个index，都有一个value值与之对应。index称为下标，可 以由一个整数、两个整数或多个整数构成，下标含有n（n≥1） 个整数称为维数是n。数组按维数分为一维、二维和多维数组。 一维数组A是n（n＞1）个相同类型数据元素a1，a2，…， an构成的有限序列，其逻辑表示为：A=（a1,a2,…,an），其中， A是数组名，ai（1≤i≤n）为数组A的第i个元素。 一个二维数组可以看作是每个数据元素都是相同类型的一 维数组的一维数组。以此类推，任何多维数组都可以看作一个 线性表，这时线性表中的每个数据元素也是一个线性表。多维 数组是线性表的推广。
（5）输出三元组 从头到尾扫描三元组表示的data数组并输出所有元素值 及其位臵。对应的算法如下：
void SMatrixClass::DispMat() //输出三元组 { int i; if (nums<=0) return; //没有非零元素时返回 cout << "\t" << rows << "\t" << cols << "\t" << nums << endl; cout << "\t------------------\n"; for (i=0;i<nums;i++) cout << "\t" << data[i].r << "\t" << data[i].c << "\t" << data[i].d << endl; }
（6）矩阵转臵 对于一个m×n的稀疏矩阵am×n，其转臵矩阵是一个n×m的 矩阵bn×m，满足bj,i=ai,j，其中0≤i≤m-1，0≤j≤n-1。用形参tb表示 转臵后稀疏矩阵对应的三元组表示。对应的算法如下：
void SMatrixClass::Transpose(SMatrixClass &tb) //矩阵转臵 { int p,q=0,v; //q为tb.data的下标 tb.rows=cols; tb.cols=rows; tb.nums=nums; if (nums!=0) //当前三元组表示中存在非零元素时执行转臵 { for (v=0;v<cols;v++) //tb.data[q]中的记录以c域的次序排列 for (p=0;p<nums;p++) //p为data的下标 if (data[p].c==v) { tb.data[q].r=data[p].c; tb.data[q].c=data[p].r; tb.data[q].d=data[p].d; q++; } } }
下三角部分 ai,j：i>j
a 0, n 1 a1, n 1 ... a 2 , n 1 ... ... ... an 1, n 1 ... ...
上三角部分 ai,j：i<j
主对角线 ai,j：i=j
1. 对称矩阵的压缩存储 若一个n阶方阵a[n,n]中的元素满足ai,j=aj,i（0≤i，j≤n-1），则 称其为n阶对称矩阵。
LOC(ai,j)=LOC(a1,1)+[(j-1)×m+(i-1)]×k
5.1.3 特殊矩阵的压缩存储
二维数组也称为矩阵，一个m行n列的矩阵，当m=n时， 称为方阵，方阵的元素可以分为三部分，即上三角部分， 主对角部分和下三角部分：
a 0 ,1 a 0, 2 a 0,0 a1, 0 a1,1 a1, 2 a 2,0 a 2 ,1 a 2, 2 ... ... ... an 1, 0 an 1,1 an 1, 2
...
0
5.2 稀疏矩阵
一个阶数较大的矩阵中的非零元素个数s相对于矩阵元
素的总个数t十分小时，即s<<t时，称该矩阵为稀疏矩阵。
5.2.1 稀疏矩阵的三元组表示