当前位置：文档之家 › 数据结构-数组与广义表学习资料

数据结构-数组与广义表学习资料

  • 格式：ppt
  • 大小：841.00 KB
  • 文档页数：44

下载文档原格式

  / 44

合集下载

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

数据结构第五章 数组与广义表
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中列号
一、三元组顺序表
对于稀疏矩阵，非零元可以用三元组表示， 整个稀疏矩阵可以表示为所有非零元的三元组所 构成的线性表。例如：

数据结构串、数组和广义表知识点总结

数据结构串、数组和广义表知识点总结

数据结构串、数组和广义表知识点总结
数据结构是计算机科学中研究数据如何组织、存储、管理和操作的学科。

三个常见的数据结构串、数组和广义表都是用于存储和操作数据的。

1. 串：
- 串是由0个或多个字符组成的有限序列。

它是一维数组的特例。

- 串的操作包括插入、删除、修改和查找等常见操作。

- 串可以通过数组、链表或动态分配的内存来实现。

2. 数组：
- 数组是一种线性数据结构，它由一组连续的内存空间组成，
存储相同类型的数据。

- 数组的操作包括插入、删除、修改和查找等常见操作。

- 数组的访问时间复杂度为O(1)，但插入和删除的时间复杂度
较高。

3. 广义表：
- 广义表是由若干元素组成的有序集合，每个元素可以是原子
或者是一个广义表。

- 广义表可以通过链表来实现，每个节点包含两个指针，一个
指向元素，一个指向下一个节点。

- 广义表的操作包括插入、删除、修改和查找等常见操作。

- 广义表可以表示任意层次的嵌套结构，具有灵活性和扩展性。

总结：
- 串、数组和广义表都是常见的数据结构，用于存储和操作数据。

- 串是字符的有限序列，可以通过数组或链表来实现。

- 数组是一维线性数据结构，存储相同类型的数据，具有常数时间复杂度的访问操作。

- 广义表是由元素组成的有序集合，可以通过链表来实现，能够表示任意层次的嵌套结构。

数据结构：第5章 数组与广义表1-数组

数据结构：第5章 数组与广义表1-数组

中的元素均为常数。下三角矩阵正好相反，它的主对
数据结构讲义
第5章 数组与广义表
—数组
数组和广义表
数组和广义表可看成是一种特殊的 线性表，其特殊在于，表中的数据 元素本身也是一种线性表。
几乎所有的程序设计语言都有数组 类型。本节重点讲解稀疏矩阵的实 现。
5.1 数组的定义
由于数组中各元素具有统一的类型，并且 数组元素的下标一般具有固定的上界和下 界，因此，数组的处理比其它复杂的结构 更为简单。
nm
aa1221
aa2222
…………....
aam2n2 ………………..
aamm11 aamm22 ………….... aammnn LLoocc(a( iaj)ij=)L=Loco(ca(a111)1+)[+([j(-i1-)1m)n++((i-j1-1)])*]*l l
aa1mn 1 aa2mn2 …………....
其存储形式如图所示：
15137 50800 18926 30251
a00 a10 a 11 a20 a21 a23 ………………..
70613
an-1 0 a n-1 1 a n-1 2 …a n-1 n-1
图 5.1 对称矩阵
在这个下三角矩阵中，第i行恰有i+1个元素，元素总
数为：
n(n+1)/2
5.2 数组的顺序表示和实现
由于计算机的内存结构是一维的，因此用 一维内存来表示多维数组，就必须按某种 次序将数组元素排成一列序列，然后将这 个线性序列存放在存储器中。
又由于对数组一般不做插入和删除操作， 也就是说，数组一旦建立，结构中的元素 个数和元素间的关系就不再发生变化。因 此，一般都是采用顺序存储的方法来表示 数组。

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

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

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

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

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）所示。

《数据结构——用C语言描述(第二版)》第5章 数组和广义表

《数据结构——用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

数据结构第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.广义表的特点及应用：-广义表是一种扩展的线性数据结构，可以存储不同类型的元素。

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

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

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

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

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

计算机基础综合PPT课件之数据结构-数组与广义表

计算机基础综合PPT课件之数据结构-数组与广义表

数组的定义（3）
基本操作: InitArray(&A, n, bound1,…boundn) //构造数 组A,维数n,各维长度bound1,…boundn DestroyArray(&A) //销毁数组A Value(A, &e, index1,…indexn) //将指定的A元素赋给e Assign(&A, e, index1,…indexn) //将e的值赋给所指定的A的元素
} //for arow } //if return OK; }
链式存储结构
• 带行指针向量的单链表表示法 – 每行的非0元素链成一个单链表 – 每行的头指针组成一个表头指针数组
链式存储结构（2）
• 十字链表表示法
– 在链表中每个非0元素用一个含5个域的结点表示. – 每行的头指针组成一个一维数组 – 每列的头指针组成一个一维数组
零元素的位置
else cb=B.tu+1;
// brow为B的最后一行
for (q=B.rpos[brow];q<cb;++q) {
ccol=B.data[q].j;
//乘积元素在Q中列号
ctemp[ccol]= ctemp[ccol]+A.data[p].e*B.data[q].e;
} //for q
a00
a01 ... a0, n 1
Am n
a10
...
a11
...
a1, n 1
... ... ...
am 1,0
am 1,1
...
am
1,
n
1
数组的定义（2）
• 数组定义方式2（抽象数据类型数组）

数据结构课件PPT数组和广义表

数据结构课件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]; } }

数据结构数组和广义表

数据结构数组和广义表

数据结构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

数据结构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 数组的基本操作
数组一旦被定义，它的维数和维界就不再改变。因此，除了 结构的初始化和销毁之外，数组的基本操作一般不会含有元素 的插入或删除等操作,数组只有访问数组元素和修改元素值的 操作。

第5章 数组和广义表总结

第5章 数组和广义表总结

0603
2090
B5×4 = 0 8 0 0
0000
row col val
4000
0 12
0 44
1 06
1 28
2 19
3 03
现在，要通过A的 三元组表求其转置 矩阵B的三元组表。
row col val
0 16 0 33 1 02 1 29 2 18 4 04
16
三元组表的转置
方法1：设矩阵A是m行、n列、t个非0元素 从头到尾扫描A，将第0列的元素依次放入B（行号列号互换）; 从头到尾扫描A，将第1列的元素依次放入B（行号列号互换）; ．．．．．． 从头到尾扫描A，将第n-1列的元素依次放入B（行号列号互换）; 扫描A几趟？ 矩阵A的列数n
}tritype;
typedef struct { //三元组表
tritype data[MAXSIZE]; //三元组表存储空间
int mu, nu, tu;
//原矩阵的行数、列数、非0元素个数
}Tsmtype, *Tsmlink;
//三元组表说明符
14
三元组表
例 5.3 矩阵的转置。 求矩阵A的转置矩阵B，算法很简单：
ArrayInit(&A, n, d1, d2, ..., dn) ArrayDestroy(&A)
ArrayGet(A, i1, ..., in, &e)
ArrayAssign(&A, i1, ..., in, e) }ADT Array；
数组的基本操作一般不包括插入和删除
4
5.2 数组的存储结构
存储空间是在程序执行时动态分配的
n维数组A[u1][u2]…[un]

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

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

5.3.1
特殊矩阵
1、对称矩阵 在一个n阶方阵A中，若元素满足下述性质： aij = aji 1≤i,j≤n 则称A为对称矩阵。 a11 1 5 1 3 7 a21 a 22 5 0 8 0 0 a31 a32 a33 1 8 9 2 6 ……………….. 3 0 2 5 1 an 1 a n 2 a n 3 …a n n 7 0 6 1 3
第5章
数组和广义表
5.1 数组的定义
5.2 数组的顺序表示和实现
5.3 矩阵的压缩存储
5.3.1 特殊矩阵
5.3.2 稀疏矩阵
5.4 广义表的定义
5.1 数组的定义
数组-----线性表的扩展 A =(a0,a1,a2,…，an-1)
a00 a10 ┇ Am×n= ai0 ┇ am-1,0 a01 … a0j … a11 … a1j … ┇ ai2 … aij … ┇ am-1,2 … am-1,j … a0,n-1 a1,n-1 ai,n-1 am-1,n-1 α0 α1 ┇ Am×n= α i ┇ α m-1
Assign( &A, e, index1, ..., indexn) 赋值操作 初始条件：A是n维数组,e为元素变量,随后是n个下标值。 操作结果：若下标不超界,则将e的值赋给所指定的A的元 素,并返回OK。 对于数组来说一旦维数确定了，每个元素的下标确定了, 那么整个数组就确定了，这样的一个数组结构除了能改变 某元素的值，其他的不能再改变。
5.2 数组的顺序表示和实现
数组类型特点: 1) 只有引用型操作，没有加工型操作; 2) 数组是多维的结构，而存储空间是一个一维的结构。 有两种顺序映象的方式。
有两种顺序映像方法： 1）以行序为主序(行优先，先行后列)：先存储行号较小 的元素，行号相同者先存储列号较小的元素；

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

数据结构讲义第5章-数组和广义表
对于一个矩阵结构,显然用一个二维数组来表示是非常 恰当的.但有时会遇到这样一类矩阵:在这种矩阵中有 许多值相同的元素或者是零元素,为了节省存储空间, 可以对这类矩阵进行压缩存储. 压缩存储是:为多个值相同的元素只分配一个存储空间: 对零元素不分配存储空间. 特殊矩阵:值相同的元素或者零元素在矩阵中的分布有 一定规律,则称此类矩阵为特殊矩阵,反之,称为稀疏 矩阵.
5.4 广义表
5)若广义表不空,则可分成表头和表尾,反之,一对表头和表尾 可唯一确定广义表 对非空广义表:称第一个元素为L的表头,其余元素组成的表称 为LS的表尾; B = (a,(b,c,d)) 表头:a 表尾 ((b,c,d)) 即 HEAD(B)=a, C = (e) D = (A,B,C,f ) 表头:e 表尾 ( ) TAIL(B)=((b,c,d)),
5.4 广义表
4)下面是一些广义表的例子; A = ( ) 空表,表长为0; B = (a,(b,c,d)) B的表长为2,两个元素分别为 a 和子表(b,c,d); C = (e) C中只有一个元素e,表长为1; D = (A,B,C,f ) D 的表长为4,它的前三个元素 A B C 广义表, 4 A,B,C , 第四个是单元素; E=( a ,E ) 递归表.
以二维数组为例:二维数组中的每个元素都受两个线性关 系的约束即行关系和列关系,在每个关系中,每个元素aij 都有且仅有一个直接前趋,都有且仅有一个直接后继. 在行关系中 aij直接前趋是 aij直接后继是 在列关系中 aij直接前趋是 aij直接后继是
a00 a01 a10 a11
a0 n-1 a1 n-1
a11 a21 ┇ a12 a22 ┇ ai2 ┇ … amj … amn … aij … ain … … a1j a2j … … a1n a2n β1 β2 ┇ βi ┇ βm

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

数据结构—第五章_数组和广义表1
初始条件: 是 维数组 为元素 维数组, 初始条件:A是n维数组,e为元素 变量,随后是n 个下标值. 变量,随后是 个下标值. 操作结果:若下标不超界,则将e的 操作结果:若下标不超界,则将 的 值赋给所指定的A的元 值赋给所指定的 的元 素,并返OK. 并返 .
二维数组的定义: 二维数组的定义
初始条件: 是 维数组 为元素变量 维数组, 为元素变量, 初始条件:A是n维数组,e为元素变量, 随后是n 个下标值. 随后是 个下标值. 操作结果:若各下标不超界, 赋值为 操作结果:若各下标不超界,则e赋值为 所指定的A 的元素值, 所指定的 的元素值,并返 回OK. .
Assign(&A, e, index1, ..., indexn)
§5.1 数组的类型定义
ADT Array { 数据对象: 数据对象 D={aj ,j , ...,,j ,j | ji =0,...,bi -1, i=1,2,..,n } 数据关系: 数据关系 R={R1, R2, ..., Rn} Ri={<aj ,... j ,... j , aj , ...j +1, ...j > | 0 ≤ jk ≤ bk -1, 1 ≤ k ≤ n 且k ≠ i, 0 ≤ ji ≤ bi -2, i=2,...,n }
…………………. an1 an2 an3……..
按行序为主序: 按行序为主序: a11 a21 a22 a31 a32
k=0 1 2 3 4 …... …... ann n(n-1)/2 n(n+1)/2-1
an1
Loc( aij)=Loc(a11)+[ i*(i-1)/2 +(j-1)]*L
对角矩阵
a11 a12 0
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

LTA[0..n(n+1)/2-1]
a11 a21 a22 … … k= 0 1 2 … …
aij … … ann n(n+1)/2-1
11
k的含义：按行优先，是第k个（从0开始）
i=3
k=4 152683
1 567 5 289 6 830 7 904
j=2
7904
• 公式的推导（下三角）
– i=3，j=2
3
5.1.1 数组的概念及其与线性表的关系
由定义知，n维数组中有b1b2 … bn个数据元素，每个 数据元素都受到n维关系的约束。
直观的n维数组
以二维数组为例讨论。将二维数组看成是一个定长的线性表，
其每个元素又是一个定长的线性表。
设二维数组A=(aij)mn，则 A=(α1，α2，…，αp) (p=m或n)
数据结构-数组与广义表
知识结构图
数组与广义表
数组
广义表
类表 型示 定方 义法
特 殊 矩 阵
稀 疏 矩 阵
逻存 辑储 应 结结 用 构构
压各
缩种
存运
储算
2
5.1 数组
数组是n(n＞1)个相同数据类型的数据元素a0,a1,a2,...,an-1 构成的占用一块地址连续的内存单元的有限序列。 数组中任意一个元素可以用该元素在数组中的位置来表示， 数组元素的位置通常称作数组的下标。
在每个关系中，元素 (0<=ji<=bi-2)都有一个直接后继
;
a j1 j2 ... jn
数据元素都必须属于同一数据类型;
n=1时，退化为定长的线性表；
n维数组可以看成是线性表的推广。
数组一旦被定义，则维数已定，对于数组的操作只有存取元 素和修改元素。(一旦建立了数组，数组中的元素个数和元 素之间的关系就不再发生变动)
行向量 下标 i
页向量 下标 i
列向量 下标 j
行向量 下标 j
列向量 下标 k
8
二维数组
三维数组
数组的顺序表示-小结
n维数组的特点: 数据元素同属于一种数据类型； 数组一旦被定义，则维数和各维长度不能改变； 数组操作只有引用型操作，没有加工型操作； 数组是多维结构，但存储空间是一维结构。
– 则前面有一个i-1行的完整三角形，共有元素
(1+i-1)(i-1)/2 = i(i-1)/2个
– 另外，同一行，前面还有j-1个元素
– 所以，k = i(i-1)/2+j-1
12
2、三角矩阵
以主对角线划分， n阶三角矩阵有n阶上三角矩阵和n阶下三角矩阵两种。 n阶上三角矩阵的下三角（不包括主对角线）中的元素均为0（或常数）。 n阶下三角矩阵正好相反，它的主对角线上方均为0（或常数）。 注：在大多数情况下， n阶三角矩阵常数为零。
a０的内存单元地址
每个元素所需的字节个数
( 2 ) 一 维 m 行 n 列 的 二 维 数 组
a00
A
a10
M
am1,0
a01 L a11 L MO am1,1 L
a0,n1
a1,n1
L o c ( a i j) L o c ( a 0 0 ) ( i* n j ) * L
M
am1,n1
对于高阶矩阵，若其中非零元素呈某种规律分 布或者矩阵中有大量的零元素，若仍然用常规方法 存储，可能存储重复的非零元素或零元素，将造成 存储空间的大量浪费。对这类矩阵进行压缩存储：
◆ 多个相同的非零元素只分配一个存储空间； ◆ 零元素不分配空间。
10
5.2.1 特殊矩阵的压缩存储
1.对称矩阵 n阶矩阵A中元素满足性质a[i][j]=a[j][i] (1≤i,j≤n)。 （即aij=aji,1<=i,j<=n）
数组是多维的结构，而存储空间是一个一维的结构。（存储 时需要一个次序约定）
6
5.1制
( 1 ) 一 维 数 组 ( n 个 元 素 ) 中 任 一 元 素 a i 的 内 存 单 元 地 址 L o c ( a i ) L o c ( a 0 ) i * L ( 0 i n )
数组顺序表示的特点 存储单元地址连续（需要一段连续空间） 存储规则（以行（列）为主序）决定元素实际存储位置 随机存取 存储密度最大（100%）
9
5.2 矩阵的压缩存储
在科学与工程计算问题中，矩阵是一种常用的数学 对象，在高级语言编程时，通常将一个矩阵描述为 一个二维数组。这样，可以对其元素进行随机存取 ，各种矩阵运算也非常简单。
a11 a12 a13 L
c
a22 a23 L
A c
M
c
c a33 L M MO c cL
a1n
a2n
a3n
M
a mn
a11 c
其中每个数据元素αj是一个列向量(线性表) ： αj =(a1j ，a2j ，…，amj) 1≦j≦n
或是一个行向量：
αi =(ai1 ，ai2 ，…，ain) 1≦i≦m
如图5-1所示。
4
a11 a12 … a1n
A=
a21 a22 … a2n ……………
am1 am2 … amn
(a) 矩阵表示形式
以 行 序 为 主 序 的 求 元 素 地 址 的 公 式 ： L o c (a ij) L o c (a c 1 ,c 2 ) [ (i c 1 )* (d 2 c 2 1 ) (j c 2 ) ]* L
以 列 序 为 主 序 的 求 元 素 地 址 的 公 式 ： L o c (a ij) L o c (a c 1 ,c 2 ) [(j c 2 )* (d 1 c 1 1 ) (i c 1 )]* L
L o c ( a i j) L o c ( a 0 0 ) ( j* m i ) * L
7
( 3 ) 更 一 般 地 假 设 二 维 数 组 行 下 界 是 c 1 ,行 上 界 为 d 1 ,列 下 界 为 c 2 , 列 上 界 为 d 2 ， 即 数 组 A [ c 1 . . . d 1 ,c 2 . . . d 2 ] 。
a11 a21 A= ┆
am1
a11 a12 … a1n
a21 a22 … a2n A= … … … … …
am1 am2 … amn
(b)行向量的一维数组形式
a12 a22 ┆
┆ ┆
a1n a2n ┆
am2 ┆ amn
(c)列向量的一维数组形式
图5-1 二维数组图例形式
5
n维数组的特点
每个数据元素都受着n个关系的约束；