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

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

  • 格式：ppt
  • 大小：790.50 KB
  • 文档页数：52

下载文档原格式

  / 52

合集下载

第5章数组和广义表PPT课件

第5章数组和广义表PPT课件
A、j(j-1)/2+i-1 B、j(j-1)/2+i C、j(j+1)/2+i-1 D、 j(j+1)/2+i
数据结构（Java版）》叶核亚
5.2.2 稀疏矩阵的压缩存储
表示稀疏矩阵的三元组
0 0 11 0 17 0
0
20
0
0
0
0
行号 row
列号 column
元素值 value
A56
0 19
设矩阵A是一个对称矩阵，为了节省空间，将其下三角部分 按行优先存放在一维数组B中。对下三角矩阵中任一元素 aij(i>=j,j>=1)，在一维数组B中下标K的值是：
A、i(i-1)/2+j-1 B、i(i-1)/2+j C、i(i+1)/2+j-1 D、 i(i+1)/2+j
设矩阵A是一个对称矩阵，为了节省空间，将其上三角部分 按列优先存放在一维数组B中。对上三角矩阵中任一元素 aij(i<=j,i>=1)，在一维数组B中下标K的值是：
1．多维数组的逻辑结构
数据结构（Java版）》叶核亚
5.1.2 多维数组
2．多维数组的遍历
（1）行优先次序
a1,1 a1,2 a1,n
Amn
a2,1
am,1
a2,2 am,2
a2,n
am,n
a1,1，a1,2，…，a1,n，a2,1，a2,2，…， a2,n，…，am,1，am,2，…，am,n
常见的广义表为：
L＝(a，b)
//线性表，长度为2 ，深度为1
T＝(c，L)＝(c，(a，b)) //L为T的子表，T的长度为2 ， 深度为2

Chapter05_数组和广义表_数据结构(C语言版)_严蔚敏_配套ppt课件

Chapter05_数组和广义表_数据结构(C语言版)_严蔚敏_配套ppt课件

M
1 1 2 3 3 4
1 5 3 1 2 4
3 7 -1 -1 -2 2
N
1 1 2 3 4 5
1 3 3 2 4 1
3 -1 -2 -1 2 7
行列下 标调换
1 5 3 1 2 4
1 1 2 3 3 4
3 7 -1 -1 -2 2
按行下 标排序
法1：
按照矩阵M的列序进行转置，即按三元组A的 第二个字段值（列下标）由小到大的顺序进行转置。 为了找到M中每一列中所有的非零元素，需要对其 三元组表a.data从第一行起整个扫描一遍，由于 a.data是以M的行序为主序来存放每个非零元素 的，对于M中具有相同列下标的非零元来讲，先扫 描到的非零元的行下标一定小于后扫描到的非零元 的行下标，由此得到的恰是b.data应有的顺序。
• 压缩的含义
– 为多个值相同的元素只分配一个存贮空间； – 零元素不分配或少分配存贮空间。
• 特殊矩阵：元素值相同或零元素分布有 一定规律的矩阵。 • 稀疏矩阵：元素值相同或零元素分布没 有规律的矩阵。 • 特殊矩阵的压缩存贮实际是将二维数组 的数据元素压缩到一维数组上。
特殊矩阵的压缩存储
特殊矩阵: 非零元在矩阵中的分布有一定规则
常用的稀疏矩阵的存储方法
三元组表示法 顺序存储 行逻辑联接的顺序表 带辅助行向量的二元组表示法 伪地址表示法 带行指针向量的单链表示法 链接存储 散列存储 行列表示法（十字链表） 多链表示法（正交表）
顺序存储
1、三元组表示法 用一个线性表来表示稀疏矩阵，线性表的每个 结点对应稀疏矩阵的一个非零元素。其中包括三个 域，分别为该元素的行下标、列下标和值。结点间 的先后顺序按矩阵的行优先顺序排列（跳过零元 素），将线性表用顺序的方法存储在连续的存储区 里。

chapter5数组和广义表.ppt

chapter5数组和广义表.ppt
以此类推。
三元组的存储位置
row
col
item
0
0
15
0
3
22
0
5
-15
1
1
11
1
2
3
2
3
6
4
0
9
7 (非零元素个数) 5(行数) 6(列数)
第0列第1个非零元素 第0列有2个非零元素
第1列第1个非零元素
算法思路
引入两个数组作为辅助数据结构：
num[nu]存储矩阵A中某列的非零元素的个数 cpot[nu]表示矩阵A中某列的第一个非零元素
13-Oct-19
3
数组的特点
N
数组中的总元素个数为： bi i 1
数组是一种结构固定，且操作有限制的线性表
数组的结构固定，通常不能改变它的维数，也不能改变每 个维数的长度
通过给定数组元数的下标，人们可以存取相应的数据元素 通过给定数组元数的下标，人们可以修改数据元素的值 通常情况下不能对数组元素做插入和删除操作，常用的操
1
1
11
1
2
3
2
3
6
4
0
9
7 (非零元素个数) 5(行数) 6(列数)
row
col
item
0
0
15
7 (非零元素个数) 6(行数) 5(列数)
三元组表的转置算法1示例
row
col
item
0
0
15
0
3
22
0
5
-15
1
1
11
1
2
3
2
3
6

数据结构课件-DS05-数组与广义表.ppt

数据结构课件-DS05-数组与广义表.ppt
若i > j，数组元素A[i][j]在矩阵的下三角部分，在 数组 B 中没有存放。因此，找它的对称元素A[j][i]。
的 i, 此即为该元素的行号。 j = k - i * (i + 1) / 2
此即为该元素的列号。 例，当 k = 8, 3*4 / 2 = 6 k < 4*5 / 2 =10,
取 i = 3。则 j = 8 - 3*4 / 2 = 2。
第 章 数组和广义表
a00 a01 a02 a03 上
n=4
第 章 数组和广义表
第五章 数组
数组的类型定义和表示方法 特殊矩阵和稀疏矩阵存储方法
及运算的实现 广义表的结构特点
第 章 数组和广义表
数组可以看成是一种特殊的线性表，即线性表 中数据元素本身也是一个线性表
5.1.1 二维数组的定义
定义
)
)
)
(a11 a12 ... ... a1n)
)
)
Amn
(a21
n1
n
aj1ij kj1mk in*l
第 章 数组和广义表
5.2.1 特殊矩阵
为节约存储，只存对角线及对角线以上的元素， 或者只存对角线及对角线以下的元素。前者称为 上三角矩阵，后者称为下三角矩阵。
a00 a01 a02 a0n1
aaan121000
a11
a21 an11
a12
a22 an12
数据元素同构
数组运算
给定一组下标，存取相应的数据元素
给定一组下标，修改数据元素的值
第 章 数组和广义表
矩阵Am×n看成n个列向量的线性表
第 章 数组和广义表
矩阵Am×n看成m个行向量的线性表
第 章 数组和广义表

数组和广义表PPT课件

数组和广义表PPT课件
❖ 设在矩阵A中，有s个非零元素。令 e=s/(m*n)，称e为矩阵的稀疏因子。通常 认为e≤0.05时称之为稀疏矩阵。
第18页/共57页
5.3.2稀疏矩阵的压缩存储
❖在存储稀疏矩阵时，由于非零元素的分布一般 是没有规律的，因此在存储非零元素的同时，还 必须同时记下它所在的行和列的位置（i,j)。反 之，一个三元组(i,j,aij)惟一确定了矩阵A的一个 非零元。因此，稀疏矩阵可由表示非零元的三元 组及其行列数唯一确定。
a0,0 a0,1 a1,0 a1,1 a1,2
a2,1 a2,2 a2,3 …. ai,j …. an-2,n-3 an-2,n-2 an-2,n-1 an-1,n-2 an-1, n-1
k=? m=?
数组B
a0,0 a0,1 a1,0 ...
ai,j
...
下标
012
k k+1
m
第16页/共57页
k=? m=?
数组B 下标
a1,1 a2,1 a2,2 a3,1 … ai,j
1234
k
… an,n
m
第11页/共57页
5.3.1(续)三角矩阵的压缩存储
❖ 三角矩阵：上(下)三角矩阵是指矩阵的下（上）
三角（不包括对角线）中的元素均为常数或零的n
阶矩阵，即非零元素的分布在矩阵中呈现为三角
形。
❖ 例如：一个4*4的三角矩阵。
❖ 压缩存储：为多个值相同的非零元素只分配 一个存储空间；对零元素不分配空间。
第8页/共57页
5.3.1特殊矩阵的压缩存储
❖ 特殊矩阵：非零元素按照一定的规律分布。 ❖ 常见的特殊矩阵有对称矩阵、三角矩阵、对角矩
阵等。 ➢ 对称矩阵：元素的值按照主对角线对称

数据结构之数组与广义表课件PPT课件

数据结构之数组与广义表课件PPT课件

对称矩阵有n*n个元素，但只存储n*(n+1)/2 个元素即可. 若以行序为主序，把下三角中的 元素，存储在一个一维数组SA[n*(n+1)/2] 中， 则 A[i,j] 和SA[k] 的对应关系如下：
若 i>=j , 则A[i, j]在下三角中，A[i, j]之前共有 1+2+……+i+j = i*(i+1)/2+j 个元素，因此有
2
3 -1
3
1
-1

6
4
5
2
8
6
1
5
7
6
9
7 7 7
t: 1 3 -1
165 212 258 3 1 -1 634 679
➢ 基本思想：
把S转置成T，就是把S中的每一个三元组的 行号和列号（row 和col）交换，并存储在T 中。但是，这样的结果是按列优先存储的稀 疏矩阵T，所以，还必须重新排列三元组的 顺序。
3.稀疏矩阵的压缩存储
➢ 若一个m*n矩阵，有s个非0元素， 记 e=s/(m*n) e 称为稀疏因子。 当 e0.05时，则称为稀疏矩阵。
例: M=
0 2 -1 0 0 0 0 0000000 -1 0 0 0 0 4 0 0000000 0800000 5000000 0000090
➢ 在稀疏矩阵中，非0元素的排列无规律，所以不 能采用以前的压缩方法。
1. 一维数组的寻址公式
对于一维数组，若其第一个元素的首地
址为Loc(a0)，下标为 i 的数组元素A[i]的地
址为Loc(ai)，
a a 则 Loc( i) = Loc( 0) + k * i
( 0≤i≤n-1)

数据结构第5章数组和广义表2广义表ppt课件PPT精品文档33页

所以在对应的存储结构中，其存储结点也有相应划分。 对于原子结点，应包含值域； 对于表结点，应包含指示表头的表头指针域(指向
表中的第一个元素)和指示表尾的表尾指针域(指向除 去原表头元素后的广义表)。
4）D=( A , B ,C )
n=3，3个元素都是子表
5）E=(a, E)
n=2，a 为原子，E为子表
D=(A,B,C)=(( ),(e),(a,(b,c,d)))，共享表
E=(a,E)=(a,(a,E))= (a,(a,(a,…….)))，E为递归表
§5.4 广义表的类型定义
❖试用图形表示下列广义表
§5.4 广义表的类型定义 ❖广义表的特点
▪ 可共享
广义表的元素可以为其他广义表所共享 A = ( a , B ) =( a , ( b , c , d ) )
§5.4 广义表的类型定义
❖例1：求下列广义表的长度
1）A =( )
n=0，因为A是空表
2）B = ( e )
n=1，表中元素e是原子
3）C =( a ,( b , c , d ) ) n=2，a 为原子，(b, c, d)为子表
6. GetHead{ ( ( ) ) }＝ ( ) .
7. GetTail{ ( ( ) ) }＝ ( ) .
(a, b)
§5.4 广义表的类型定义 ❖注意：( )和( ( ) )的区别
前者为空表，长度=0，深度=1； 后者长度=1，深度=2，表头、表尾均为( )
§5.5 广义表的存储结构
❖广义表的存储结构
§5.4 广义表的类型定义
❖广义表的特点
▪ 有深度
广义表的深度定义为广义表中括弧的最大重数
如: H = (d, (e,( )))深度为3 注意：(1)空表的深度为1；

第五部分数组和广义表教学课件


的 压
常数。下三角矩阵正好相反，它的主对角线上方均为常数， 如图所示。在大多数情况下，三角矩阵常数为零。
缩
存
a00 0 0 …….. 0
储
a10 a11 0 …….. 0
…………………. 0 an-10 an-11 an-12…….. an-1n-1
三角矩阵中的重复元素c可共享一个存储空间，其
矩
余的元素正好有n(n+1)/2个，因此，三角矩阵可压缩
ji =0,...,bi -1, i=1,2,..,n
}
数据关系：
R1＝{ 0
a a <

j1 … ji…,jn jk bk -1,
1j1
…

kji+1…njn
>| 且k i,
0 ji bi -2, i=2,...,n, 0 ji bi -2,}
二维数组的定义:
数 数据对象:
实
现
以行序为主序(低下标优先)
以列序为主序(高下标优先)
0
a00
按行序为主序存放
1
a01
数
…….
组 的
n-1 a0n-1
顺
n
a10
序 表 示
a00 a01 …….. a0n-1 a10 a11 …….. a0n-1
a11 ……..
和
a1n-1
实
………………….
……….
现
am-10am-11 …….. am-1n-1
定
10
11
1 n-2
义
A
=
m* n
...
... ...
...
a
a

数据结构课件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章 数组和广义表


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 ) ( ( ( (
① 数组中的元素都具有统一的类型; ② 数组元素的下标一般都具有固定的上界和下界，即数组一旦 被定义，它的维数和维界就不再发生改变； ③ 数组的基本操作简单：初始化、销毁、存取元素和修改元素值
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

a00 a10 a11 a20 …… an-1 0 … an-1,n-1
K=0 1 2 3
… … … n(n+1)/2-1
在这个下三角矩阵中，第i行恰有i+1个元素，元素
总数为：n(n+1)/2
因此，我们可以将这些元素存放在一个向量 sa[0..n(n+1)/2-1]中。为了便于访问对称矩阵A中的元
A： i 1 1 3 3 4 5 6 6
jv 2 12 39 1 -3 6 14 3 24 2 18 1 15 4 -7
例：矩阵的转置
0 12 9 0 0 0 0 0 0 0 000 0
M= -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 6*7
a00 a01 a10 a11 a12 a21 a22 a23 …. ….. …. an-2 n-3 an-2 n-2 an-2 n-1 an-1 n-2 an-1 n-1
需存储的元素个数为3n-2。
a00 a01 a10 a11 a12 a21 … … a n-1 n-2 a n-1 n-1
K=0 1 2 3 4 5 … … 3n-4 3n-3
ቤተ መጻሕፍቲ ባይዱ
一、三元组顺序表
#define maxsize 100 typedef int datatype;
typedef struct{ int i,j; //第i行第j列 datatype v; // v:非0值
}triple; typedef struct{
triple data[maxsize]; int m,n,t; //m行、n列、t个非0元 }tripletable;
9 a[2][1]
10 a[2][2]
11 a[2][3]
a[0] a[1] a[2]
例1：二维数组Amn按“行优先顺序”存储在内存 中， 且每个元素占用d个存储单元。 求元素aij的存储地址。 LOC(aij)=LOC(a11)+[(i-1)*n+j-1]*d
例2：三维数组Amnp按“行优先顺序”存储在内存 中， 且每个元素占用d个存储单元。 求元素aijk的存储地址。 LOC(aijk)=LOC(a111)+[(i-1)*n*p+( j-1)*p +(k-1)]*d
可以将数组A看成长度为n的线性表C
C = (c1, c2 , … c n)
其中，每个元素cj是长度为m的线性表, 既数组A中的 第j列。
cj= a1j, a2j , … amj
5.1 数组的定义
Amn=
a11 a12 … a1n a21 a22 … a2n … … ……
am1 am2 … amn
数组只有两个操作：
a[2] a2[210]71[60] a2[10291][81] a2[20212][02] a2[20232][23]
每个元素a[i]由包含4个元素 的一维数组组成
0 a[0][0] 1 a[0][1] 2 a[0][2]
3 a[0][3] 4 a[1][0] 5 a[1][1] 6 a[1][2] 7 a[1][3] 8 a[2][0]
5.3.2 稀疏矩阵
设矩阵A中有s个非零元素，若s远远小于 矩阵元素的总数（即s<<m×n），则 称A为稀疏矩阵。
0 12 9 0 0 0 0 0 0 0 000 0 -3 0 0 0 0 14 0 M= 0 0 24 0 0 0 0 0 18 0 0 0 0 0 15 0 0 –7 0 0 0 m*n
0 0 -3 0 0 15
12 0 0 0 18 0
N=
9 0 0 24 0 0 0 0 0 0 0 -7
000 0 00
0 0 14 0 0 0
0 0 0 0 0 0 7*6
例：矩阵的转置
方法一：
(1)将三元组表A中每一个元素的行、列互换三元组表B中 (2)对三元组表B，依行进行排序。
5 数组和广义表
5.1 数组的定义 5.2 数组的顺序表示和实现 5.3 矩阵的压缩存储
5.3.1 特殊矩阵 5.3.2 稀疏矩阵 5.4 广义表的定义 5.5 广义表的存储结构
5.1 数组的定义
Amn=
a11 a12 … a1n a21 a22 … a2n … … ……
am1 am2 … amn
（1）存取元素 （2）修改元素值
C描述： datatype a[m][n]
5.2 数组的顺序表示和实现
数组有两种顺序存储方式：
⑴行优先顺序 ——将数组元素按行排列。 a11,a12,…,a1n,a21,a22,…a2n,……,am1,am2,…,amn 在C语言中，数组就是按行优先顺序存储的。
⑵列优先顺序 ——将数组元素按列向量排列。 a11,a21,…,am1,a12,a22,…am2,……,a1n,a2n,…,amn
❖二维数组理解
二维数组a是由3个元素组成
例 int a[3][4];
行名
a[0] a2[00]0[00] a2[000][21] a2[000][42] a2[000]0[36]
1
3
5
7
a[1] a[210]0[08] a2[10]1[01] a2[10]1[22] a2[01]1[43] 9 11 13 15
素，我们必须在aij和sak之间找一个对应关系。
k= i(i+1)/2+j 当i>=j j( j+1)/2+i 当i<j
二、对角矩阵
对角矩阵中，所有的非零元素集中在以主对角线为 了相k中邻= 心两的侧的带状若区干域条对中角，即线除上的了元主对素角之外线，和其主对余元角素线 皆为零。下图给出了一个三对角矩阵，
5.3 矩阵的压缩存储
5.3.1特殊矩阵
一、对称矩阵 在一个n阶方阵A中，若元素满足下述性质： aij=aji 0≦i,j≦n-1
则称A为对称矩阵。
15137 50800 18926 30251 70613
a00 a10 a 11 a20 a21 a22 ………………..
an-1 0 a n-1 1 a n-1 2 …a n-1 n-1
可以将数组A看成长度为m的线性表B
B = (b1, b2 , … bm )
其中，每个元素bi是长度为n的线性表, 既数组A中的 第i行。
bi= ai1 , ai2 , … ain
5.1 数组的定义
Amn=
a11 a12 … a1n a21 a22 … a2n … … ……
am1 am2 … amn