数据结构 数组与广义表
- 格式：ppt
- 大小：400.50 KB
- 文档页数：49
下载文档原格式
合集下载
数据结构第4章 数组和广义表
第4章数组和广义表【例4-1】二维数组A的每一个元素是由6个字符组成的串，其行下标i=0，1，…，8，列下标j=1，2，…，10。
若A以行为主序存储元素，A[8][5]的物理地址与当A按列为主序存储时的元素（）的物理地址相同。
设每个字符占一个字节。
A．A[8][5] B．A[3][10] C．A[5][8] D．A[0][9]解：二维数A是一个9行10列的矩阵，即A[9][10]。
按行存储时，A[8][5]是第85个元素存储的元素。
而按列存储时，第85个存储的元素是A[3][10]。
即正确答案为B。
【例4-2】若对n阶对称矩阵A以行序为主序方式将其下三角形的元素（包括主对角线上所有元素）依次存放于一维数组B[n（n+1）/2]中，则在B中确定的位置k的关系为（）。
A．jii+-2)1(*B．ijj+-2)1(*C．jii++2)1(*D．ijj++2)1(*解：如果a ij按行存储，那么它的前面有i-1行，其有元素个数为：1+2+3+…+（i-1）=i（i-1）/2。
同时它又是所在行的第j列，因此它排列的顺序还得加上j，一维数组B[n(n+1)/2]中的位置k与其下标的关系是：jii+-2)1(*。
因此答案为A。
【例4-3】已知n阶下三角矩阵A，按照压缩存储的思想，可以将其主对角线以下所有元素（包括主对角线上元素）依次存放于一维数组B中。
请写出从第一列开始以列序为主序分配方式时在B中确定元素a ij的存放位置的公式。
解：如果a ij按列存储，那么它的前面有j-1列，共有元素：n+(n-1)+(n-2)+ …+[n-(j-2)]=(j-1)*n-2)1)(2(--jj而它又是所在列的第i行，因此在它前的元素个数还得加上i。
因此它在一维数组B中的存储顺序为：(j-1)*n-2)1)(2(--jj+i【例4-4】已知广义表L=((x,y,z),a,(u,t,w))，从L表中取出的原子项ASCII码最大的运算是（）。
数据结构第五章 数组与广义表
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中列号
一、三元组顺序表
对于稀疏矩阵，非零元可以用三元组表示， 整个稀疏矩阵可以表示为所有非零元的三元组所 构成的线性表。例如：
压缩存储方法：只需要存储下三角 （含对角线）上的元素。可节省一 半空间。
可以使用一维数组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.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）所示。
数据结构教程李春葆课后答案第6章数组和广义表
3. 如果某个一维数组 A 的元素个数 n 很大，存在大量重复的元素，且所有元素值相同 的元素紧挨在一起，请设计一种压缩存储方式使得存储空间更节省。
答：设数组的元素类型为 ElemType，采用一种结构体数组 B 来实现压缩存储，该结构 体数组的元素类型如下：
struct { ElemType data;
解：从二维数组 B 的右上角的元素开始比较。每次比较有三种可能的结果：若相等， 则比较结束；若 x 大于右上角元素，则可断定二维数组的最上面一行肯定没有与 x 相等的 数据，下次比较时搜索范围可减少一行；若 x 小于右上角元素，则可断定二维数组的最右 面一列肯定不包含与 x 相等的数据，下次比较时可把最右一列剔除出搜索范围。这样，每 次比较可使搜索范围减少一行或一列，最多经过 m+n 次比较就可找到要求的与 x 相等的元 素。对应的程序如下：
{ printf("不是对角矩阵\n");
return false;
}
for (int i=0;i<a.nums;i++)
if (a.data[i].r==a.data[i].c) //行号等于列号
sum+=a.data[i].d;
return true;
}
11. 设计一个算法 Same(g1，g2)，判断两个广义表 g1 和 g2 是否相同。 解：判断广义表是否相同过程是，若 g1 和 g2 均为 NULL，则返回 true；若 g1 和 g2 中一个为 NULL，另一不为 NULL，则返回 false；若 g1 和 g2 均不为 NULL，若同为原子 且原子值不相等，则返回 false，若同为原子且原子值相等，则返回 Same(g1->link，g2->link)， 若同为子表，则返回 Same(g1->val.sublist，g2->val.sublist) & Same(g1->link，g2->link)的 结果，若一个为原子另一个为子表，则返回 false。对应的算法如下：
《数据结构——用C语言描述(第二版)》第5章 数组和广义表
是指矩阵的下三角（不含对角线）中的元素均为常数C或零的n阶矩阵，下 三角矩阵则与之相反，如图5.3所示。
第五章 数组和广义表
在压缩存储时，矩阵中值相同的元素C可共享一个存储空间，元素 为零则可不必分配空间，而其余的元素有 n(n+1)/2个，因此三角矩阵 可用一维数组M[n×(n+1)/2+1]来存储，其中常数C放在数组的最后一 个下标变量中。
假设A和B矩阵分别用matrix型指针变量a和b表示，矩阵的转置可以 按以下进行：由于Ｂ的行是Ａ的列，所以可按照b->data三元组表的次序在 a->data中找到相应的三元组进行转置，即可按a->data的列序转置，所得 到的转置矩阵Ｂ的三元组表b->data必定是按行优先存放的。因此，可以对 三元组表a->data从第一行起扫描，找到Ａ的每一列中所有的非零元素，就 可以实现转置。
LOC ( aij ) =LOC ( a00) +(i×n+j) × c 同理可推导出以列为主序优先存储时数据元素a i j 的存储地址，其计算公式 为：
LOC( a i j ) =LOC( a00 ) +( j × n +i ) × c 对于三维数组Am×n×p而言，若以行为主序优先存储时，则其数据元 素aijk的存储地址可为： LOC ( a i j k) =LOC ( a000) +[ i × m×p +j ×p +k] × c 对于一般的二维数组A[c1…d1，c2…d2]而言，此处c1，c2的值不一定是 0，a i j 的地址为： LOC ( a i j ) =LOC ( a c 1 c 2 ) +[ ( i – c 1 )* ( d 2 – c 2 +1) +j – c 2 ] * c
第五章 数组和广义表
在压缩存储时，矩阵中值相同的元素C可共享一个存储空间，元素 为零则可不必分配空间，而其余的元素有 n(n+1)/2个，因此三角矩阵 可用一维数组M[n×(n+1)/2+1]来存储，其中常数C放在数组的最后一 个下标变量中。
假设A和B矩阵分别用matrix型指针变量a和b表示，矩阵的转置可以 按以下进行：由于Ｂ的行是Ａ的列，所以可按照b->data三元组表的次序在 a->data中找到相应的三元组进行转置，即可按a->data的列序转置，所得 到的转置矩阵Ｂ的三元组表b->data必定是按行优先存放的。因此，可以对 三元组表a->data从第一行起扫描，找到Ａ的每一列中所有的非零元素，就 可以实现转置。
LOC ( aij ) =LOC ( a00) +(i×n+j) × c 同理可推导出以列为主序优先存储时数据元素a i j 的存储地址，其计算公式 为：
LOC( a i j ) =LOC( a00 ) +( j × n +i ) × c 对于三维数组Am×n×p而言，若以行为主序优先存储时，则其数据元 素aijk的存储地址可为： LOC ( a i j k) =LOC ( a000) +[ i × m×p +j ×p +k] × c 对于一般的二维数组A[c1…d1，c2…d2]而言，此处c1，c2的值不一定是 0，a i j 的地址为： LOC ( a i j ) =LOC ( a c 1 c 2 ) +[ ( i – c 1 )* ( d 2 – c 2 +1) +j – c 2 ] * c
数据结构第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、从供选择的答案中，选出应填入下面叙述 ？ 内的最确切的解答，把相应编号写在答卷的对应栏内。
中南大学数据结构与算法第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语言中，数组就是按列优先顺序存储的。
数据结构课件PPT数组和广义表
T.mu=M.nu; T.nu=M.mu; T.tu=M.tu; if (T.tu)
{ q=1; for (col=1;col<=T.mu;++col) for(p=1;p<=M.tu;++p) if ( M.data[p].j==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; ++q; } }
(row) (col) (value)
[0] 1 4 22
[0] 1 5 91
[1] 1 7 15
[1] 2 2 11
[2] 2 2 11
[2] 3 6 28
[3] 2 [4] 3来自6 17 4 -6[3] 4 [4] 4
1 22 3 -6
[5] 4 6 39
[5] 6 2 17
[6] 5 1 91
[6] 6 4 39
cpot[1]=1 cpot[col]=cpot[col-1]+num[col-1]
稀疏矩阵的快速转置(算法5.2)
Status FastTransposeSMatrix(TSMatrix M,TSMatrix &T) { T.mu=M.nu; T.nu=M.mu; T.tu=M.tu;
if (T.tu) { for (col=1;col<=M.nu;++col) num[col]=0; for (t=1;t<=M.tu;++t) ++num[M.data[t].j]; cpot[1]=1; for ( col=2;col<=M.nu;++col) cpot[col]=cpot[col-1]+num[col-1]; for (p=1;p<=M.Tu;++p) { col=M.data[p].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]; } }
{ q=1; for (col=1;col<=T.mu;++col) for(p=1;p<=M.tu;++p) if ( M.data[p].j==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; ++q; } }
(row) (col) (value)
[0] 1 4 22
[0] 1 5 91
[1] 1 7 15
[1] 2 2 11
[2] 2 2 11
[2] 3 6 28
[3] 2 [4] 3来自6 17 4 -6[3] 4 [4] 4
1 22 3 -6
[5] 4 6 39
[5] 6 2 17
[6] 5 1 91
[6] 6 4 39
cpot[1]=1 cpot[col]=cpot[col-1]+num[col-1]
稀疏矩阵的快速转置(算法5.2)
Status FastTransposeSMatrix(TSMatrix M,TSMatrix &T) { T.mu=M.nu; T.nu=M.mu; T.tu=M.tu;
if (T.tu) { for (col=1;col<=M.nu;++col) num[col]=0; for (t=1;t<=M.tu;++t) ++num[M.data[t].j]; cpot[1]=1; for ( col=2;col<=M.nu;++col) cpot[col]=cpot[col-1]+num[col-1]; for (p=1;p<=M.Tu;++p) { col=M.data[p].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]; } }
数据结构第五章数组和广义表
数据结构第五章数组和广义表(总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．假设以行序为主序存储二维数组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．稀疏矩阵一般的压缩存储方法有两种，即( )。
A.二维数组和三维数组B.三元组和散列C.三元组和十字链表D.散列和十字链表9．有一个100×90的稀疏矩阵，非0元素有10个，设每个整型数占两字节，则用三元组表示该矩阵时，所需的字节数是( )。
大学数据结构课件--第5章 数组和广义表
a 32 a 33 a 34 0 0
a 43 a 44 a 45 0
a 54 a 55 a 56 a 65 a 66
5.3.2 稀疏矩阵
稀疏矩阵的存储：如何表示非零元素的位置信息 1. 三元组表：每个元素用一个三元组（i，j，v）来表示。 i j v
0 1 6 1 1 6 2 3 8 12 9
2
3 4 5 6 7 8
2
5.2 数组的顺序表示和实现
a00 a00 a10 a01 存储单元是一维结构，而数组是个多维结构 , …… …… 则用一组连续存储单元存放数组的数据元素就有 am-1,0 a0,n-1 个次序约定问题。 a01 a10
a11
……
a11
……
二维数组可有两种存储方式： am-1,1 a1,n-1
……
K=
i*n-i(i-1)/2+j-i n(n+1)/2
当 i≤j 当i>j
0 a11 ... a1n-1 ... ... ... ... 0 0 0 an-1n-1
当i ≤ j时,a[i][j]是非零元素, a[i][j]前面有i行,共有n+(n-1)+(n-2)+…(n-(i-1))
=i(n+[n-(i-1)])/2=i*n-i(i-1)/2个元素，a[i][j]前面有j列，共j-i个非零元素，
A m× n
( a10 a11 … a1,n-1 )
=
注：
( … … …… ) ( am-1,0 am-1,2 … am-1,n-1 ) ( ( ( (
① 数组中的元素都具有统一的类型; ② 数组元素的下标一般都具有固定的上界和下界，即数组一旦 被定义，它的维数和维界就不再发生改变； ③ 数组的基本操作简单：初始化、销毁、存取元素和修改元素值
数据结构考研真题 数组和广义表
第 5 章数组和广义表一、选择题为第一元素，其存1.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11的地址为（）。
【燕山大学 2001 一、2 （2储地址为1，每个元素占一个地址空间，则a85分）】A. 13B. 33C. 18D. 402. 有一个二维数组A[1:6，0:7] 每个数组元素用相邻的6个字节存储，存储器按字节编址，那么这个数组的体积是（①）个字节。
假设存储数组元素A[1，0]的第一个字节的地址是0，则存储数组A的最后一个元素的第一个字节的地址是（②）。
若按行存储，则A[2，4]的第一个字节的地址是（③）。
若按列存储，则A[5，7]的第一个字节的地址是（④）。
就一般情况而言，当（⑤）时，按行存储的A[I，J]地址与按列存储的A[J，I]地址相等。
供选择的答案：【上海海运学院 1998 二、2 （5分）】①-④： A．12 B. 66 C. 72 D. 96 E. 114 F. 120G. 156 H. 234 I. 276 J. 282 K. 283 L. 288⑤： A．行与列的上界相同 B. 行与列的下界相同C. 行与列的上、下界都相同D. 行的元素个数与列的元素个数相同3. 设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1 到8 ，j的值为1 到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为( )。
A. BA+141B. BA+180C. BA+222D. BA+225【南京理工大学 1997 一、8 （2分）】4. 假设以行序为主序存储二维数组A=array[1..100，1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5，5]=（）。
【福州大学 1998 一、10 (2分)】A. 808B. 818C. 1010D. 10205. 数组A[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5，5]的地址是( )。
数据结构 数组和广义表习题
第五章数组和广义表习题一、选择题1.已知广义表LS＝((a,b,c),(d,e,f))，运用head和tail函数取出LS中原子e运算是。
A.head(tail(LS))B.tail (head(LS))C.head(tail(head(tail(LS))))D. head(tail(tail(head(LS))))2.若广义表A满足head(A)＝ tail(A)，则A为。
A.（）B.（（））C.（（）,（））D.（（）,（）,（））3.广义表A=(a,b,(c,d),(e,(f,g)))，则下面式子Head(Tail(Head(Tail(Tail(A)))))的值为。
A.（）B.（d）C.cD.d4.稀疏矩阵一般的压缩存储方法有 两种。
A.二维数组和三维数组B.三元组和散列表C.三元组和十字链表D.散列表和十字链表5.已知矩阵A是一个对称矩阵，为了节省存储，将其下三角部分按行优先存放在一维数组B[1…n(n-1)/2]中，对下三角部分中任一元素aij(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+j6.已知广义表L＝((x,y,z),a,(u,t,w))，从L表中取出原子u的运算是。
A.head(tail(tail(L)))B.tail(head(head(tail(L))))C.head(tail(head(tail(L))))D.head(head(tail(tail(L))))7.广义表L＝((a,b,c))，则L的长度和深度分别为。
A.1和1B.1和3C.1和2D.2和38. tail (head(((a,b,c,d,e))))= 。
A.aB.c,dC.D.(b,c,d,e)9.二维数组A[10…20,5…10]采用列序方式存储，每个数据元素占4个存储单元，且A[10,5]的存储地址是1000，则A[20,9]的地址是。
数据结构课后习题答案第五章数组与广义表
第五章数组与广义表一、假设有二维数组A6*8，每个元素用相邻的6个字节存储，存储器按字节编址。
已知A的起始存储位置（基地址）为1000。
计算：1、数组A的体积（即存储量）；2、数组A的最后一个元素a57的第一个字节的地址；3、按行存储时，元素a14的第一个字节的地址；4、按列存储时，元素a47的第一个字节的地址；答案：1、（6*8）*6=2882、loc(a57)=1000+(5*8+7)*6=1282或=1000+（288-6）=12823、loc(a14)=1000+(1*8+4)*6=10724、loc(a47)=1000+(7*6+4)*6=1276二、假设按低下标(行优先)优先存储整数数组A9*3*5*8时第一个元素的字节地址是100，每个整数占四个字节。
问下列元素的存储地址是什么？（1）a0000(2)a1111(3)a3125 (4)a8247答案：（1）100（2）loc(a1111)=100+(1*3*5*8+1*5*8+1*8+1)*4=776(3) loc(a3125)=100+(3*3*5*8+1*5*8+2*8+5)*4=1784(4) loc(a8247)=100+(8*3*5*8+2*5*8+4*8+7)*4=4416五、设有一个上三角矩阵（aij）n*n,将其上三角元素逐行存于数组B[m]中，（m 充分大），使得B[k]=aij且k=f1(i)+f2(j)+c。
试推导出函数f1,f2和常数C（要求f1和f2中不含常数项）。
答：K=n+(n-1)+(n-2)+…..+(n-(i-1)+1)+j-i=(i-1)(n+(n-i+2))/2+j-i所以f1(i)=(n+1/2)i-1/2i2f2(j)=jc=-(n+1)九、已知A为稀疏矩阵，试从空间和时间角度比较采用两种不同的存储结构（二维数组和三元组表）完成∑aii运算的优缺点。
（对角线求和）解：1、二维数组For(i=1;i<=n;i++)S=s+a[i][i];时间复杂度：O（n）2、for(i=1;i<=m.tu;i++)If(a.data[k].i==a.data[k].j) s=s+a.data[k].value;时间复杂度：O（n2）二十一、当稀疏矩阵A和B均以三元组表作为存储结构时，试写出矩阵相加的算法，其结果存放在三元组表C中。
数据结构数组和广义表
数据结构05数组与广义表数组与广义表可以看做是线性表地扩展,即数组与广义表地数据元素本身也是一种数据结构。
5.1 数组地基本概念5.2 数组地存储结构5.3 矩阵地压缩存储5.4 广义表地基本概念数组是由相同类型地一组数据元素组成地一个有限序列。
其数据元素通常也称为数组元素。
数组地每个数据元素都有一个序号,称为下标。
可以通过数组下标访问数据元素。
数据元素受n(n≥1)个线性关系地约束,每个数据元素在n个线性关系地序号 i1,i2,…,in称为该数据元素地下标,并称该数组为n维数组。
如下图是一个m行,n列地二维数组A矩阵任何一个元素都有两个下标,一个为行号,另一个为列号。
如aij表示第i行j列地数据元素。
数组也是一种线性数据结构,它可以看成是线性表地一种扩充。
一维数组可以看作是一个线性表,二维数组可以看作数据元素是一维数组（或线性表）地线性表,其一行或一列就是一个一维数组地数据元素。
如上例地二维数组既可表示成一个行向量地线性表: A1=(a11,a12,···,a1n)A2=(a21,a22, ···,a2n)A=(A1,A2, ···,Am) ············Am=(am1,am2, ···,amn)也可表示成一个列向量地线性表:B1=(a11,a21,···,am1)B2=(a12,a22, ···,am2)A=(B1,B2, ···,Bm) ············Bn=(a1n,a2n, ···,amn)数组地每个数据元素都与一组唯一地下标值对应。
数据结构05数组和广义表11
2021/11/8
12
设有m×n二维数组Amn，下面我们看按元素的下标求其 地址的计算：
以“行为主序”的分配为例：设数组的基址为LOC(a11)， 每个数组元素占据l个地址单元，那么aij 的物理地址可用一 线性寻址函数计算：
LOC(aij) = LOC(a11) + ( (i-1)*n + j-1 ) * l 在C语言中，数组中每一维的下界定义为0，则：
(1) 取值操作：给定一组下标，读其对应的数据元素。
(2) 赋值操作：给定一组下标，存储或修改与其相对应的
数据元素。
我们着重研究二维和三维数组，因为它们的应用是广泛的，
尤其是二维数组。
2021/11/8
9
5.1.3 数组的存储结构
• 通常，数组在内存中被映象为向量，即用向量作为数组的 一种存储结构，这是因为内存的地址空间是一维的，数组的行 列固定后，通过一个映象函数，则可根据数组元素的下标得到 它的存储地址。
• 任一数据元素的存储地址可由公式算出：
Loc(a i,j)=loc(a 0,0)+(i*n+j)*L
– 以列序为主序的顺序存储
• 在以列序为主序的存储方式中，数组元素按列向量排列， 即第j+1个列向量紧接在第j个列向量之后, 把所有数组 元素顺序存放在一块连续的存储单元中。
• 任一数据元素的存储地址可由公式算出
–Loc(a i,j)=loc(a c1,c2)+[(j-c1)*(d1-c1+1)+(i-c1)]*L
2021/11/8
8
5.1.2 数组的基本操作
数组一旦被定义，它的维数和维界就不再改变。因此，除了 结构的初始化和销毁之外，数组的基本操作一般不会含有元素 的插入或删除等操作,数组只有访问数组元素和修改元素值的 操作。
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
1) 广义表中的数据元素有相对次序；
2) 广义表的长度定义为最外层包含元素个数； 3) 广义表的深度定义为所含括弧的重数；
注意：“原子”的深度为 0 “空表”的深度为 1
4) 广义表可以共享； 5) 广义表可以是一个递归的表。
递归表的深度是无穷值，长度是有限值。
for (col=1; col<=M.nu; ++col) num[col] = 0; for (t=1; t<=M.tu; ++t) ++num[M.data[t].j]; cpot[1] = 1; for (col=2; col<=M.nu; ++col)
cpot[col] = cpot[col-1] + num[col-1]; for (p=1; p<=M.tu; ++p) { 转置矩阵元素 } } // if return OK; } // FastTransposeSMatrix
K=i(i-1)/2+j-1
=3(3-1)/2+2-1=4
a11 a21 a22 a31 a32 a33 a 41 a42 a43 a44
0 1 2 3 4 5 6 7 8 9…n(n+1)/2
二、 随机稀疏矩阵 非零元在矩阵中随机出现
随机稀疏矩阵的压缩存储方法:
1、三元组顺序表 2、行逻辑联接的顺序表
T.data[q].i=M.data[p].j;
T.data[q].j=M.data[p].i;
T.data[q].v=M.data[p].v; ++q ;}
} return OK;
}// TransposeSMatrix
快速转置 用“三元组”表示时如何实现？
1 2 14 1 5 -5 2 2 -7 3 1 36 3 4 28
row
12 3
rpos[row] 1 3 4
3、 十字链表
M.chead
^
M.rhead
113
2 2 -1
^^
312
^^
145
^^
3005 0 -1 0 0 2000
5.4 广义表的类型定义
ADT GList { 数据对象：D＝{ei | i=1,2,..,n; n≥0; ei∈AtomSet 或 ei∈GList, AtomSet为某个数据对象 } 数据关系：
i(i-1)/2+j-1 当i>=j 下三角(存)
K= j(j-1)/2+i-1 当i<j 上三角
(i,j从1开始标识,k从0开始标识)
a11 a12 a13 a14 a21 a22 a23 a24 a31 a32 a33 a34 a41 a42 a43 a44
例:i=3,j=2 求a32存储位 置k=?
0 14 0 0 5
0
7 0
0
0
36 0 0 28 0
TSMatrix T ;
i je
T.mu 3
T.nu 5 T.tu 5
T.data[1] 1 1 2 14
T.data[2] 2 1 5 -5
…
3 2 2 -7 4 3 1 36
T.data[5] 5 3 4 28
如何求转置矩阵？
0 14 0 0 5
R1＝{<ei-1, ei >| ei-1 ,ei∈D, 2≤i≤n} 基本操作:
} ADT GList
基 本 操 作
• 结构的创建和销毁
InitGList(&L); DestroyGList(&L); CreateGList(&L, S); CopyGList(&T,
• 状态函数
GListLength(L); GListDepth(L);
类型特点: 1) 只有引用型操作，没有加工型操作； 2) 数组是多维的结构，而存储空间是
一个一维的结构。
有两种顺序映象的方式: 1)以行序为主序 2)以列序为主序
以“行序为主序”的存储映象 例如：m*n二维数组
a0,0 a0,1 a0,2 a1,0 a1,1 a1,2
a0,0 a0,1 a0,2 a1,0 a1,1 a1,2
用“三元组”表示时如何实现？
ij v
1 2 14
ij v
1 3 36
1 5 -5
2 1 14
2 2 -7
2 2 -7
3 1 36
4 3 28
3 4 28
5 1 -5
a.data
b.data
Status TransposeSMatrix（TSMatrix M， TSMatrix &T）{//采用三元组表存储表示,求稀疏
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) … …
时间复杂度为: O(M.nu+M.tu)
2、行逻辑联接的顺序表
cpot[1] = 1; for (col=2; col<=M.nu; ++col)
cpot[col] = cpot[col-1] + num[col-1];
Status FastTransposeSMatrix(TSMatrix M, TSMatrix &T){
T.mu = M.nu; T.nu = M.mu; T.tu = M.tu; if (T.tu) {
矩阵M的转置矩阵T 。
T.mu=M.nu ; T.nu=M.mu ; T.tu=M.tu ;
if (T.tu) { q=1 ;
for (col=1 ;col<=M.nu;++col) for (p=1;p<=M.tu ; ++p)
时间复杂度
if(M.data[p].j==col) {
O（nu*tu）
Triple data[MAXSIZE + 1]; int rpos[MAXMN + 1]; int mu, nu, tu; } RLSMatrix; // 行逻辑链接顺序表类型
0 14 0 0 5
0
7 0
0
0
36 0 0 28 0
i je
1 1 2 14 2 1 5 -5 3 2 2 -7 4 3 1 36 5 3 4 28
遇除法，还需判别除数是否为零。
பைடு நூலகம்
解决问题的原则:
1) 尽可能少存或不存零值元素；
2) 尽可能减少没有实际意义的运算；
3) 操作方便。 即： 能尽可能快地找到与
下标值(i，j)对应的元素， 能尽可能快地找到同
一行或同一列的非零值元。
有两类稀疏矩阵：
一、 特殊矩阵
非零元在矩阵中的分布有一定规则
例如: 对称矩阵、三角矩阵
a00 a01 a02 … a10 a11 a21
a0n-1
a00 a01 0 a11
a0n-1 a1n-1
an-10 an-11
an-1 n-1
00
0 an-1 n-1
对于对称矩阵aij=aji (1<=i,j<=n)
我们可以为每一对对称元素分配一个存储 空间,即将n2个元压缩存储到n(n+2)/2个元 的空间中.假设以一维数组sa[n(n+1)/2]作为 对称矩阵的存储结构。sa[k]和aij之间存在 着一一对应的关系:
Col = M.data[p].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的时间 复杂度：
操作结果：若各下标不超界，则e赋值为 所指定的A 的元素值，并返 回OK。
Assign(&A, e, index1, ..., indexn)
初始条件：A是n维数组，e为元素变量， 随后是n 个下标值。
操作结果：若下标不超界，则将e的值赋 给所指定的A的元素，并返回 OK。
5.2 数组的顺序表示和实现
L
二维数组A中任一元素ai,j 的存储位置 LOC(i,j) = LOC(0,0) + (n×i＋j)× L
n:每行元素的个数 称为基地址或基址。
以“列序为主序”的存储映象
a0,0 a0,1 a0,2 a1,0 a1,1 a1,2
a0,0 a1,0 a0,1 a1,1 a0,2 a1,2
二维数组A中任一元素ai,j 的存储位置 LOC(i,j) = LOC(0,0) + (m×j＋i)×L
L);
GListEmpty(L); GetHead(L); GetTail(L);
• 插入和删除操作
InsertFirst_GL(&L, e);
DeleteFirst_GL(&L, &e);
• 遍历
Traverse_GL(L, Visit());
广义表 LS = ( 1, 2, …, n )的结构特点:
3、 十字链表
1、三元组顺序表
#define MAXSIZE 12500
typedef struct { int i, j; //该非零元的行下标和列下标 ElemType e; // 该非零元的值
} Triple; // 三元组类型 typedef struct {
2) 广义表的长度定义为最外层包含元素个数； 3) 广义表的深度定义为所含括弧的重数；
注意：“原子”的深度为 0 “空表”的深度为 1
4) 广义表可以共享； 5) 广义表可以是一个递归的表。
递归表的深度是无穷值，长度是有限值。
for (col=1; col<=M.nu; ++col) num[col] = 0; for (t=1; t<=M.tu; ++t) ++num[M.data[t].j]; cpot[1] = 1; for (col=2; col<=M.nu; ++col)
cpot[col] = cpot[col-1] + num[col-1]; for (p=1; p<=M.tu; ++p) { 转置矩阵元素 } } // if return OK; } // FastTransposeSMatrix
K=i(i-1)/2+j-1
=3(3-1)/2+2-1=4
a11 a21 a22 a31 a32 a33 a 41 a42 a43 a44
0 1 2 3 4 5 6 7 8 9…n(n+1)/2
二、 随机稀疏矩阵 非零元在矩阵中随机出现
随机稀疏矩阵的压缩存储方法:
1、三元组顺序表 2、行逻辑联接的顺序表
T.data[q].i=M.data[p].j;
T.data[q].j=M.data[p].i;
T.data[q].v=M.data[p].v; ++q ;}
} return OK;
}// TransposeSMatrix
快速转置 用“三元组”表示时如何实现？
1 2 14 1 5 -5 2 2 -7 3 1 36 3 4 28
row
12 3
rpos[row] 1 3 4
3、 十字链表
M.chead
^
M.rhead
113
2 2 -1
^^
312
^^
145
^^
3005 0 -1 0 0 2000
5.4 广义表的类型定义
ADT GList { 数据对象：D＝{ei | i=1,2,..,n; n≥0; ei∈AtomSet 或 ei∈GList, AtomSet为某个数据对象 } 数据关系：
i(i-1)/2+j-1 当i>=j 下三角(存)
K= j(j-1)/2+i-1 当i<j 上三角
(i,j从1开始标识,k从0开始标识)
a11 a12 a13 a14 a21 a22 a23 a24 a31 a32 a33 a34 a41 a42 a43 a44
例:i=3,j=2 求a32存储位 置k=?
0 14 0 0 5
0
7 0
0
0
36 0 0 28 0
TSMatrix T ;
i je
T.mu 3
T.nu 5 T.tu 5
T.data[1] 1 1 2 14
T.data[2] 2 1 5 -5
…
3 2 2 -7 4 3 1 36
T.data[5] 5 3 4 28
如何求转置矩阵？
0 14 0 0 5
R1＝{<ei-1, ei >| ei-1 ,ei∈D, 2≤i≤n} 基本操作:
} ADT GList
基 本 操 作
• 结构的创建和销毁
InitGList(&L); DestroyGList(&L); CreateGList(&L, S); CopyGList(&T,
• 状态函数
GListLength(L); GListDepth(L);
类型特点: 1) 只有引用型操作，没有加工型操作； 2) 数组是多维的结构，而存储空间是
一个一维的结构。
有两种顺序映象的方式: 1)以行序为主序 2)以列序为主序
以“行序为主序”的存储映象 例如：m*n二维数组
a0,0 a0,1 a0,2 a1,0 a1,1 a1,2
a0,0 a0,1 a0,2 a1,0 a1,1 a1,2
用“三元组”表示时如何实现？
ij v
1 2 14
ij v
1 3 36
1 5 -5
2 1 14
2 2 -7
2 2 -7
3 1 36
4 3 28
3 4 28
5 1 -5
a.data
b.data
Status TransposeSMatrix（TSMatrix M， TSMatrix &T）{//采用三元组表存储表示,求稀疏
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) … …
时间复杂度为: O(M.nu+M.tu)
2、行逻辑联接的顺序表
cpot[1] = 1; for (col=2; col<=M.nu; ++col)
cpot[col] = cpot[col-1] + num[col-1];
Status FastTransposeSMatrix(TSMatrix M, TSMatrix &T){
T.mu = M.nu; T.nu = M.mu; T.tu = M.tu; if (T.tu) {
矩阵M的转置矩阵T 。
T.mu=M.nu ; T.nu=M.mu ; T.tu=M.tu ;
if (T.tu) { q=1 ;
for (col=1 ;col<=M.nu;++col) for (p=1;p<=M.tu ; ++p)
时间复杂度
if(M.data[p].j==col) {
O（nu*tu）
Triple data[MAXSIZE + 1]; int rpos[MAXMN + 1]; int mu, nu, tu; } RLSMatrix; // 行逻辑链接顺序表类型
0 14 0 0 5
0
7 0
0
0
36 0 0 28 0
i je
1 1 2 14 2 1 5 -5 3 2 2 -7 4 3 1 36 5 3 4 28
遇除法，还需判别除数是否为零。
பைடு நூலகம்
解决问题的原则:
1) 尽可能少存或不存零值元素；
2) 尽可能减少没有实际意义的运算；
3) 操作方便。 即： 能尽可能快地找到与
下标值(i，j)对应的元素， 能尽可能快地找到同
一行或同一列的非零值元。
有两类稀疏矩阵：
一、 特殊矩阵
非零元在矩阵中的分布有一定规则
例如: 对称矩阵、三角矩阵
a00 a01 a02 … a10 a11 a21
a0n-1
a00 a01 0 a11
a0n-1 a1n-1
an-10 an-11
an-1 n-1
00
0 an-1 n-1
对于对称矩阵aij=aji (1<=i,j<=n)
我们可以为每一对对称元素分配一个存储 空间,即将n2个元压缩存储到n(n+2)/2个元 的空间中.假设以一维数组sa[n(n+1)/2]作为 对称矩阵的存储结构。sa[k]和aij之间存在 着一一对应的关系:
Col = M.data[p].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的时间 复杂度：
操作结果：若各下标不超界，则e赋值为 所指定的A 的元素值，并返 回OK。
Assign(&A, e, index1, ..., indexn)
初始条件：A是n维数组，e为元素变量， 随后是n 个下标值。
操作结果：若下标不超界，则将e的值赋 给所指定的A的元素，并返回 OK。
5.2 数组的顺序表示和实现
L
二维数组A中任一元素ai,j 的存储位置 LOC(i,j) = LOC(0,0) + (n×i＋j)× L
n:每行元素的个数 称为基地址或基址。
以“列序为主序”的存储映象
a0,0 a0,1 a0,2 a1,0 a1,1 a1,2
a0,0 a1,0 a0,1 a1,1 a0,2 a1,2
二维数组A中任一元素ai,j 的存储位置 LOC(i,j) = LOC(0,0) + (m×j＋i)×L
L);
GListEmpty(L); GetHead(L); GetTail(L);
• 插入和删除操作
InsertFirst_GL(&L, e);
DeleteFirst_GL(&L, &e);
• 遍历
Traverse_GL(L, Visit());
广义表 LS = ( 1, 2, …, n )的结构特点:
3、 十字链表
1、三元组顺序表
#define MAXSIZE 12500
typedef struct { int i, j; //该非零元的行下标和列下标 ElemType e; // 该非零元的值
} Triple; // 三元组类型 typedef struct {