当前位置：文档之家 › 第5章 数组和广义表[58页]

第5章 数组和广义表[58页]

  • 格式：ppt
  • 大小：2.30 MB
  • 文档页数：30

下载文档原格式

  / 30

合集下载

《数据结构——用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.1 多维数组5.1.1 数组的逻辑结构数组是我们很熟悉的一种数据结构，它可以看作线性表的推广。

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

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

标识，因此，在数组上不能做插入、删除数据元素的操作。

通常在各种高级语言中数组一旦被定义，每一维的大小及上下界都不能改变。

在数组中通常做下面两种操作：(1)取值操作：给定一组下标，读其对应的数据元素。

(2)赋值操作：给定一组下标，存储或修改与其相对应的数据元素。

我们着重研究二维和三维数组，因为它们的应用是广泛的，尤其是二维数组。

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

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

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

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

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

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

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

第5 章数组和广义表

第5 章数组和广义表
Loc[i,j,k]=Loc[1,1,1]+(i-1)*m*n+(j-1)*n+(k-1) 其中1≤i≤ｒ，1≤j≤ｍ，1≤k≤ｎ。
2019/11/8
14
如果将三维数组推广到一般情况，即：用j1，j2， j3代替数组下标i，j，k；并且j1，j2，j3的下限为c1， c2，c3，上限分别为d1，d2，d3，每个元素占一个 存储单元。则三维数组中任意元素 a(j1，j2，j3)的地址为：
………
……
特点:
i=1, j=1,2; 当 1<i<n，j=i-1, i, i+1
i=n, j=n-1, n;
时，aij非零，其他元素均为零。
2019/11/8
21
三对角带状矩阵的压缩存储，以行序为主序进行存储， 并且只存储非零元素。其方法为：
1. 确定存储该矩阵所需的一维向量空间的大小
从三对角带状矩阵中可看出：除第一行和最后一行只有两 个元素外，其余各行均有3个非零元素。由此可得到一维向量
i(i-1)/2+j-1 当i>=j k=
j(j-1)/2+i-1 当i<j
2019/11/8
20
5.3.2 带状矩阵
带状矩阵：在矩阵A中，所有的非零元素都集中在以主对角 线为中心的带状区域中。最常见的是三对角带状矩阵。
a11 a12
a21 a22 a23
An×n =
a32 a33 a34 a43 a44 a45
Loc[i,j]=Loc[1,1]+n ×(i-1)+(j-1)
其中n为第2维的长度
如果每个元素占size个存储单元 ，则任意元 素aij的地址计算公式为：
Loc[i,j]=Loc[1,1] + (n×(i-1)+j-1)×size

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

大学数据结构课件--第5章 数组和广义表

大学数据结构课件--第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 ) ( ( ( (
① 数组中的元素都具有统一的类型; ② 数组元素的下标一般都具有固定的上界和下界，即数组一旦 被定义，它的维数和维界就不再发生改变； ③ 数组的基本操作简单：初始化、销毁、存取元素和修改元素值

第五章数组和广义表

第五章数组和广义表
TransposeSMatrix ( M, &T )
稀疏矩阵M存在
由稀疏矩阵M复制 得到T
稀疏矩阵M与N的行 求稀疏矩阵的和Q 数和列数对应相等 ＝M＋N
稀疏矩阵M与N的行 求稀疏矩阵的差Q 数和列数对应相等 ＝M－N
稀疏矩阵M的列数 求稀疏矩阵乘积Q
等于N的行数
＝M＊N
稀疏矩阵M存在
求稀疏矩阵M的转 置矩阵T
M.chead
M.rhead
30 05
113
145
M = 0 -1 0 0
2 000
2 2 -1
312
稀疏矩阵的十字链表存储表示：
typedef struct OLNode { int i, j ; // 非零元的行和列下标 ElemType e ; Struct OLNode *right, *down ; // 该非零元所在行表和列表的后继链域
1 当i

j
a00 a10 a11 a20 k= 0 1 2 3
… an-1, 0 … n(n-1)/2
an-1, n-1 n(n+1)/2-1
ADT SparseMatris { 数据对象：
D = { aij | i = 1, 2, …, m; j =1, 2, … , n; aij∈ElemSet，m和n分别称为矩阵的行数和列数}
第五章 数组和广义表
ADT Array { 数据对象：{ ji = 0, … , bi-1 , i = 1, 2 , … ,
n, D = { aj1j2…jn | n ( > 0 )称为数组的维数， bi是数组第i维的长度， ji是数组元素的第i维下标， aj1j2…jn∈ElemSet } 数据关系：R = { R1, R2, …, Rn }

第5 章数组和广义表


0 12 9 0 0 0 0 0 0 0 00 0 0
M6×7= -3 0 0 0 0 14 0
0 0 24 0 0 0 0 0 18 0 0 0 0 0 15 0 0 -7 0 0 0
2019/10/17
N6×7=
0 0 3 0 0 15 12 0 0 0 18 0 9 0 0 24 0 0 0 0 0 0 0 -7 0 00 0 0 0 0 0 14 0 0 0 0 0 0 00 0
Loc[i,j,k]=Loc[1,1,1]+(i-1)*m*n+(j-1)*n+(k-1) 其中1≤i≤ｒ，1≤j≤ｍ，1≤k≤ｎ。
2019/10/17
14
如果将三维数组推广到一般情况，即：用j1，j2， j3代替数组下标i，j，k；并且j1，j2，j3的下限为c1， c2，c3，上限分别为d1，d2，d3，每个元素占一个 存储单元。则三维数组中任意元素 a(j1，j2，j3)的地址为：
所需的空间大小为：3n-2。
2. 确定非零元素在一维数组空间中的位置
假设每个非零元素所占的空间的大小为1个单元 LOC[i , j] = LOC[1,1]+2(i-1)+j-1
2019/10/17
22
5.3.3 稀疏矩阵
稀疏矩阵：指矩阵中大多数元素为零的矩阵。一般地，当非 零元素个数只占矩阵元素总数的25%—30%,或低于这个百分 数时，我们称这样的矩阵为稀疏矩阵。
Loc[i,j]=Loc[0,0]+（n×i+j）*size
其中n为第2维的长度
2019/10/17
12
三维数组A（1..r , 1..m , 1..n）可以看成是r个m×n的 二维数组 ，如下图所示：

数据结构数组和广义表

数据结构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)数组地每个数据元素都与一组唯一地下标值对应。

第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）以行序为主序(行优先，先行后列)：先存储行号较小 的元素，行号相同者先存储列号较小的元素；
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

//构造m×n矩阵
《数据结构与算法（Java版）（第5版）》第5章 9
矩阵类Matrix
int getRows()
//行数
int getColumns()
//列数
int get(int i, int j) //第i行第j列元素
void set(int i,int j,int x)//设置第i行j列元素为x
i
0 … element[i].length-1
element
0
1 element.length-1 ∧
element[0]=new int[3]; element[1]=new int[4];
(c) 申请第二维的存储空间
（3）二维数组可作为方法的参数和返回值
参数传递规则同赋值，即传递数组引用。
void print(int[][] element) //方法参数
储结构做准备。 • ③ 以特殊矩阵（稀疏矩阵）为例，研究数据压缩存储方法。 • ④ 理解广义表概念，熟悉广义表的存储结构和实现。 • 重点和实验：稀疏矩阵采用行的单链表压缩存储。 • 难点：① 行的单链表存储结构。
② 广义表存储结构和实现，递归定义及递归算法 设计。
《数据结构与算法（Java版）（第5版）》第5章 2
int[][] yanghui(int n)
//返回二维数组
《数据结构与算法（Java版）（第5版）》第5章 7
【典型案例5-1】矩阵运算。
a00
Amn
a10 …
am1,0
a01 a11 … am1,1
… a0,n1
…
a1,n1
… …
…
am1,n1
设 Cmn Amn Bmn ，有 cij aij bij
行前驱 ai-1,j
a1,1
a1,j
a1,n-1
列前驱 ai,j-1
ai,j
a0,j a1,j ai,j am-1,j
a0,n-1 a1,n-1 ai,n-1 am-1,n-1
ai,j+1 列后继
ai,1 am-1,1
ai,j
ai,n-1
am-1,j am-1,n-1
行后继 ai+1,j
《数据结构与算法（Java版）（第5版）》第5章 3
3. Java语言的二维数组
动态的，引用模型。不支持类似C/C++的静态二维 数组。
（1）声明和使用二维数组
int[][] element;
//声明
element = new int[4][5];
//动态申请
int[][] element={ {1,2,3}, {4,5,6} };//赋初值
element.length
设 Cmn Amn Bmn ，有 cij aij bij
设 Cml Amn Bnl
，有
n1
cij (aik bkj )
k 0
设 Tnm Amn的转置矩阵 ，有
tij a ji
《数据结构与算法（Java版）（第5版）》第5章 8
【例5.1】 矩阵类。
public class Matrix
第5章 数组和广义表
5.1 数组 5.2 特殊矩阵的压缩存储 5.3 广义表 习题5（1）数组
《数据结构与算法（Java版）（第5版）》第5章 1
第5章 数组和广义表
• 目的：两种包含子结构的线性结构：数组和广义表。 • 内容要求：① 理解二维数组的存储结构，掌握使用方法。 • ② 实现两种存储结构的矩阵类及矩阵运算，为第7章图的存
String toString()
//描述字符串，行主序
void setRowsColumns(int m, int n)
//设置矩阵为m行n列，矩阵扩容，复制。
//7.2.1节图的邻接矩阵
}
《数据结构与算法（Java版）（第5版）》第5章 10
value数组和mata矩阵存储结构
int[][] value={{1,2,3},{4,5,6,7,8},{9}}; //长度不同 Matrix mata=new Matrix(3, 4, value); //矩阵，补0，忽略多余
//矩阵类
{
private int rows, columns; //行数、列数
private int[][] element; //二维数组
public Matrix(int m, int n) //构造m×n零矩阵
public Matrix(int n)
//构造n×n零方阵
public Matrix(int m, int n, int[][] value)
2. 二维数组的存储结构
0 a0,0
（1）二维数组的顺序存储结构
…
第0行
行主序
n-1 a0,n-1 …
int a[3][4]; //C
i×n ai,0
…
Loc(aij ) Loc(a00 ) (i n j) c i×n+j ai,j 第i行
…
O(1)，
i×n+n-1 ai,n-1
j
//返回二维数组的长度，行数
element[0].length //返回一维数组的长度，列数
《数据结构与算法（Java版）（第5版）》第5章 6
（2）不规则的二维数组
element
element
0∧
1∧
element.length-1 ∧
int[][] element; (a) 声明数组变量
element=new int[3][]; (b) 申请第一维的存储空间
§5.1 数组
列
0
1
j
n-1
一维数组
行0
① Loc(ai)= Loc(a0)＋i ×c O(1)，随机存取结构
1 i
多维数组
m-1
a0,0 a1,0 ai,0 am-1,0
a0,1 a1,1 ai,1 am-1,1
1. 二维数组的逻辑结构
1 是j “元n素-1为一维数组”
a0,1
a的0,j 一维a0数,n-1组。
1 a0,1 a1,1 ai,1 am-1,1
j
n-1
a0,j
a0,n-1
a1,j
a1,n-1
ai,j
ai,n-1
am-1,j am-1,n-1
数组元素 int element[i][j]
int[][] mat=new int[m][n]; //Java O(1)，随机存取结构
《数据结构与算法（Java版）（第5版）》第5章 5
随机பைடு நூலகம்取结构
… (m-1)×n am-1,0
…
第m-1行
m×n-1 am-1,n-1
《数据结构与(a算) 法行（主Ja序va版）（第5版）》第5章 4
（2）二维数组的动态存储结构
二维数组变量 int[][] element
int[] 0 1 i m-1
0 a0,0 a1,0 ai,0 am-1,0