kl800.com省心范文网

第4章 广义线性表_图文

第五章

广义线性表

本章的基本内容是:
数组的逻辑结构特征

数组的存储方式及寻址方法
特殊矩阵和稀疏矩阵的压缩存储方法

广义表的基本概念和存储结构

第四章

广义线性表

线性表——具有相同类型的数据元素的有限序列。 限制插入、删除位置 特 殊 线 性 表 栈——仅在表尾进行插入和删除操作的线性表。

队列——在一端进行插入操作,而另一端进行 删除操作的线性表。
串——零个或多个字符组成的有限序列 。 限制元素类型为字符

线性表——具有相同类型的数据元素的有限序列。

第四章

广义线性表

线性表——具有相同类型的数据元素的有限序列。 将元素的类型进行扩充 广 义 线 性 表 (多维)数组——线性表中的数据元素可以是 线性表,但所有元素的类型相同。 广义表——线性表中的数据元素可以是线性表, 且元素的类型可以不相同。

广义线性表——多维数组
数组的定义
数组是由一组类型相同的数据元素构成的有序集 合,每个数据元素称为一个数组元素(简称为元 素),每个元素受n(n≥1)个线性关系的约束,每 个元素在n个线性关系中的序号i1、i2、…、in称为 该元素的下标,并称该数组为 n 维数组。

数组的特点
?元素本身可以具有某种结构,属于同一数据类型; ?数组是一个具有固定格式和数量的数据集合。

广义线性表——多维数组
数组示例
a11 a21 … am1 a12 a22 … am2 … … … … a1n a2n … amn

A=

例如,元素a22受两个线性关系的约束,在行上有
一个行前驱a21和一个行后继a23,在列上有一个列 前驱a12和和一个列后继a32。

广义线性表——多维数组
数组——线性表的推广
a11 a21 … am1 a12 a22 … am2 … … … … a1n a2n … amn

A=(A1,A2,……,An)
其中: Ai=(a1i,a2i,……,ami) (1≤i≤n)

A=

二维数组是数据元素为线性表的线性表。

广义线性表——多维数组
数组的基本操作
在数组中插入(或删除)一个元素有意义吗?
将元素 x 插入 到数组中第1行第2列。
删除数组中 第1行第2列元素。

x a11 a21 … am1 a12 a22 … am2 … … … … a1n a2n … amn
a11 a21 … am1 a12 a22 … am2 … … … … a1n a2n … amn

A=

A=

广义线性表——多维数组
数组的基本操作
⑴ 存取:给定一组下标,读出对应的数组元素; ⑵ 修改:给定一组下标,存储或修改与其相对应的 数组元素。 存取和修改操作本质上只对应一种操作——寻址

数组应该采用何种方式存储?
数组没有插入和删除操作,所以,不用预留空间, 适合采用顺序存储。

广义线性表——多维数组
数组的存储结构与寻址——一维数组
设一维数组的下标的范围为闭区间[l,h],每个 数组元素占用 c 个存储单元,则其任一元素 ai 的 存储地址可由下式确定:

Loc(ai)=Loc(al)+(i-l)×c

c al
Loc(al)

al+1

……

ai-1

ai

……

ah

Loc(ai)

广义线性表——多维数组
数组的存储结构与寻址——二维数组
二维数组
二维结构 内 存

一维结构

常用的映射方法有两种: ?按行优先:先行后列,先存储行号较小的元素, 行号相同者先存储列号较小的元素。 ?按列优先:先列后行,先存储列号较小的元素, 列号相同者先存储行号较小的元素。

广义线性表——多维数组
按行优先存储的寻址
l2 l1
aij
本行中aij前面的元素个数 每行元素个数

h2

整 行 数

aij前面的元素个数
h1
(a) 二维数组
=阴影部分的面积 =整行数×每行元素个数+本行中 aij前面的元素个数 =(i -l1)×(h2 -l2+1)+(j -l2)

广义线性表——多维数组
按行优先存储的寻址
第l1行 第l1+1行


al1l2



al1h2 a(l1+1)l2

a(l1+1)h2

……

aij



ah1 h2

Loc(al1l2)

(i -l1)×(h2 -l2+1)+(j -l2)个元素

Loc(aij)

Loc(aij)=Loc(al1l2)+((i-l1)×(h2-l2+1)+(j-l2))×c

按列优先存储的寻址方法与此类似。

广义线性表——多维数组
数组的存储结构与寻址——多维数组
n(n>2)维 数组一般也采用 按行优先和按列 优先两种存储方 法。请自行推导 任一元素存储地 址的计算方法。 Loc(aijk ) = Loc(a000) +( i×m2×m3 + j×m3 + k )×c

矩阵的压缩存储
特殊矩阵和稀疏矩阵
特殊矩阵:矩阵中很多值相同的元素并且它们的分布 有一定的规律。
稀疏矩阵:矩阵中有很多零元素。

压缩存储的基本思想是:
⑴ 为多个值相同的元素只分配一个存储空间; ⑵ 对零元素不分配存储空间。

矩阵的压缩存储
特殊矩阵的压缩存储——对称矩阵

A=

3 6 4 7 8

6 2 8 4 2

4 8 1 6 9

7 4 6 0 5

8 2 9 5 7

对称矩阵特点:aij=aji

如何压缩存储? 只存储下三角部分的元素。

矩阵的压缩存储
对称矩阵的压缩存储
0 … j …
0 …

n-1
第 0行 第1行

每行元素个数

1 2 … i aij

… 第i-1行

i n-1

aij

aij在一维数组中的序号 =阴影部分的面积 = i×(i+1)/2+ j+1 ∵一维数组下标从0开始 ∴aij在一维数组中的下标 k= i×(i+1)/2+ j

aij在本行中的序号

(a) 下三角矩阵

(b) 存储说明

(c) 计算方法

矩阵的压缩存储
对称矩阵的压缩存储
0 1 2 3 4 5

k … aij … a n-10 an-11 …

n(n+1)/2-1

a00
第0行

a10

a11

a20

a21
第2行

a22

an-1n-1

第1行

第n-1行

对于下三角中的元素aij(i≥j),在数组SA中的下标k 与i、j的关系为:k=i×(i+1)/2+j 。 上三角中的元素aij(i<j),因为aij=aji,则访问和 它对应的元素aji即可,即:k=j×(j+1)/2+i 。

矩阵的压缩存储
特殊矩阵的压缩存储——三角矩阵 3 6 4 7 8 c c 2 c 8 1 4 6 2 9 c c c 0 5 c c c c 7

3 c c c c
(b)

4 8 1 2 9 4 c 1 5 c c 0 c c c
上三角矩阵

0 6 7 8 7

(a) 下三角矩阵

如何压缩存储?
只存储上三角(或下三角)部分的元素。

矩阵的压缩存储
下三角矩阵的压缩存储 存储
0 1

下三角元素
对角线上方的常数——只存一个
2 3 4 5

k

n(n+1)/2

a00
第0行

a10

a11

a20

a21
第2行

a22



aij



an-1n-1 c

第1行

矩阵中任一元素aij在数组中的下标k与i、j的对应关系: k=

i×(i+1)/2+j
n×(n+1)/2

当i≥j
当i<j

矩阵的压缩存储
上三角矩阵的压缩存储 存储

上三角元素
对角线上方的常数——只存一个

矩阵中任一元素aij在数组中的下标k与i、j的对应关系: k=

i×(2n-i+1)/2+j-i
n×(n+1) /2

当i≤j
当i>j

矩阵的压缩存储
特殊矩阵的压缩存储——对角矩阵 对角矩阵:所有非零元素都集中在以主对角线为中心 的带状区域中,除了主对角线和它的上下方若干条对 角线的元素外,所有其他元素都为零。
a00 a01 0
A=

0 0

0 0

a10 a11 a12 0 0 0 a21 a22 0 0 a32 0

a23 0 a33 a34 a43 a44

矩阵的压缩存储
对角矩阵的压缩存储

a00 a01 0 a10 a11 a12

0 0

0 0

A=

0 0 0

a21 a22 a23 0 0 a32 a33 a34 0 0 a43 a44

将带状区 域立起来

B=

0 a10 a21 a32 a43

a00 a11 a22 a33 a44

a01 a12 a23 a34 0

映射到二维数组B中,映射关系

t=i s=j-i+1

矩阵的压缩存储
对角矩阵的压缩存储
a00 a01 A=
0 0 0

a10 a11 a12 0 0 0 a21 a22 a23 0 a32 a33 a34 0 0 0 0 0 a43 a44
(a) 三对角矩阵
按行 存储

元素aij在一维数组中的序号 =2 + 3(i-1)+( j-i + 2) =2i+ j+1 ∵一维数组下标从0开始 ∴元素aij在一维数组中的下标 =2i+ j (b) 寻址的计算方法

0

1

2

3

4

5

6

7

8

9 10

11 12

a00 a01 a10 a11 a12 a21 a22 a23 a32 a33 a34 a43 a44
(c) 压缩到一维数组中

矩阵的压缩存储
稀疏矩阵的压缩存储

A=

15 0 0 0 9

0 11 0 0 0

0 0 0 0 0

0 0 6 0 0

0 0 0 0 0

0 0 0 0 0

如何只存储非零元素?
注意:稀疏矩阵中的非零元素的分布没有规律。

矩阵的压缩存储
稀疏矩阵的压缩存储

将稀疏矩阵中的每个非零元素表示为:
(行号,列号,非零元素值)——三元组 定义三元组: struct element { int row, col; T item };

//行号,列号 //非零元素值

矩阵的压缩存储
稀疏矩阵的压缩存储 三元组表:将稀疏矩阵的非零元素对应的三元组所 构成的集合,按行优先的顺序排列成一个线性表。

A=

15 0 0 0 9

0 11 0 0 0

0 0 0 0 0

0 0 6 0 0

0 0 0 0 0

0 0 0 0 0

三元组表=( (0,0,15), (1,1,11), (2,3,6), (4,0,9) ) 如何存储三元组表?

矩阵的压缩存储
稀疏矩阵的压缩存储——三元组顺序表 采用顺序存储结构存储三元组表

15 0 0 A= 0 91

0 11 0 0 0

0 3 0 0 0

22 0 6 0 0

0 -15 0 0 0 0 0 0 0 0

三元组顺序表是否 需要预留存储空间? 稀疏矩阵的修改操作

三元组顺序表的插入/删除操作

矩阵的压缩存储
稀疏矩阵的压缩存储——三元组顺序表 采用顺序存储结构存储三元组表
0 1 2 3 4 5 6
MaxTerm-1

15 0 0 A= 0 91

0 11 0 0 0

0 3 0 0 0

22 0 6 0 0

0 -15 0 0 0 0 0 0 0 0

row col item 0 0 15 0 3 22 0 5 -15 1 1 11 1 2 3 2 3 6 4 0 91 空 空 空 闲 闲 闲 7(非零元个数) 5(矩阵的行数) 6(矩阵的列数)

是否对应惟一的稀疏矩阵?

矩阵的压缩存储
稀疏矩阵的压缩存储——三元组顺序表 存储结构定义: #define MaxTerm=100; struct SparseMatrix { T data[MaxTerm]; //存储非零元素 int mu, nu, tu; //行数,列数,非零元个数 };

矩阵的压缩存储
三元组顺序表操作——转置操作 例:

15 0 A= 0 0 91

0 11 0 0 0

0 3 0 0 0

22 0 6 0 0

0 0 0 0 0

-15 0 0 0 0

15 0 0 B= 22 0 -15

0 11 3 0 0 0

0 0 0 6 0 0

0 91 0 0 0 0 0 0 0 0 0 0

矩阵的压缩存储
0 1 2 3 4 5 6
MaxTerm-1

row col item 0 0 15 0 3 22 0 5 -15 1 1 11 1 2 3 2 3 6 4 0 91 空 空 空
闲 闲 闲 5(矩阵的行数) 6(矩阵的列数) 7(非零元个数)

0 1 2 3 4 5 6
MaxTerm-1

row col item 0 0 15 0 4 91 1 1 11 2 1 3 3 0 22 3 2 6 5 0 -15 空 空 空 闲 闲 闲 6(矩阵的行数) 5(矩阵的列数) 7(非零元个数)

矩阵的压缩存储
三元组顺序表转置算法——算法Ⅰ 基本思想:直接取,顺序存。即在A的三元组顺序 表中依次找第0列、第1列、…直到最后一列的三元 组,并将找到的每个三元组的行、列交换后顺序存 储到B的三元组顺序表中。

矩阵的压缩存储
设置矩阵B的行数、列数、非零元个数
0 1 2 3 4 5 6
MaxTerm-1

row col item 0 0 15 0 3 22 0 5 -15 1 1 11 1 2 3 2 3 6 4 0 91 空 空 空 闲 闲 闲 5(矩阵的行数) 6(矩阵的列数) 7(非零元个数)

row col 0 1 2 3 4 5 6
MaxTerm-1

item

6(矩阵的行数) 5(矩阵的列数) 7(非零元个数)

矩阵的压缩存储
在矩阵A中查找第0列非零元,顺序存储到矩阵B中
0 1 2 3 4 5 6
MaxTerm-1

row col item 0 0 15 0 3 22 0 5 -15 1 1 11 1 2 3 2 3 6 4 0 91 空 空 空 闲 闲 闲 5(矩阵的行数) 6(矩阵的列数) 7(非零元个数)

row col 0 0 0 0 4 1 2 3 4 5 6
MaxTerm-1

item 15 91

6(矩阵的行数) 5(矩阵的列数) 7(非零元个数)

矩阵的压缩存储
在矩阵A中查找第1列非零元,顺序存储到矩阵B中
0 1 2 3 4 5 6
MaxTerm-1

row col item 0 0 15 0 3 22 0 5 -15 1 1 11 1 2 3 2 3 6 4 0 91 空 空 空 闲 闲 闲 5(矩阵的行数) 6(矩阵的列数) 7(非零元个数)

row col 0 0 0 0 4 1 1 1 2 3 4 5 6
MaxTerm-1

item 15 91 11

6(矩阵的行数) 5(矩阵的列数) 7(非零元个数)

矩阵的压缩存储
在矩阵A中查找第2列非零元,顺序存储到矩阵B中
0 1 2 3 4 5 6
MaxTerm-1

row col item 0 0 15 0 3 22 0 5 -15 1 1 11 1 2 3 2 3 6 4 0 91 空 空 空 闲 闲 闲 5(矩阵的行数) 6(矩阵的列数) 7(非零元个数)

0 1 2 3 4 5 6
MaxTerm-1

row col 0 0 0 4 1 1 2 1

item 15 91 11 3

6(矩阵的行数) 5(矩阵的列数) 7(非零元个数)

矩阵的压缩存储
在矩阵A中查找第3列非零元,顺序存储到矩阵B中
0 1 2 3 4 5 6
MaxTerm-1

row col item 0 0 15 0 3 22 0 5 -15 1 1 11 1 2 3 2 3 6 4 0 91 空 空 空 闲 闲 闲 5(矩阵的行数) 6(矩阵的列数) 7(非零元个数)

0 1 2 3 4 5 6
MaxTerm-1

row col 0 0 0 4 1 1 2 1 3 0 3 2

item 15 91 11 3 22 6

6(矩阵的行数) 5(矩阵的列数) 7(非零元个数)

矩阵的压缩存储
在矩阵A中查找第4列非零元,顺序存储到矩阵B中
0 1 2 3 4 5 6
MaxTerm-1

row col item 0 0 15 0 3 22 0 5 -15 1 1 11 1 2 3 2 3 6 4 0 91 空 空 空 闲 闲 闲 5(矩阵的行数) 6(矩阵的列数) 7(非零元个数)

0 1 2 3 4 5 6
MaxTerm-1

row col 0 0 0 4 1 1 2 1 3 0 3 2

item 15 91 11 3 22 6

6(矩阵的行数) 5(矩阵的列数) 7(非零元个数)

矩阵的压缩存储
在矩阵A中查找第5列非零元,顺序存储到矩阵B中
0 1 2 3 4 5 6
MaxTerm-1

row col item 0 0 15 0 3 22 0 5 -15 1 1 11 1 2 3 2 3 6 4 0 91 空 空 空 闲 闲 闲 5(矩阵的行数) 6(矩阵的列数) 7(非零元个数)

0 1 2 3 4 5 6
MaxTerm-1

row col 0 0 0 4 1 1 2 1 3 0 3 2 5 0

item 15 91 11 3 22 6 -15

6(矩阵的行数) 5(矩阵的列数) 7(非零元个数)

矩阵的压缩存储
在矩阵A中查找第6列非零元,顺序存储到矩阵B中
0 1 2 3 4 5 6
MaxTerm-1

row col item 0 0 15 0 3 22 0 5 -15 1 1 11 1 2 3 2 3 6 4 0 91 空 空 空 闲 闲 闲 5(矩阵的行数) 6(矩阵的列数) 7(非零元个数)

0 1 2 3 4 5 6
MaxTerm-1

row col 0 0 0 4 1 1 2 1 3 0 3 2 5 0

item 15 91 11 3 22 6 -15

6(矩阵的行数) 5(矩阵的列数) 7(非零元个数)

矩阵的压缩存储
三元组顺序表转置算法Ⅰ——伪代码
1. 设置转置后矩阵B的行数、列数和非零元个数; 2. 在B中设置初始存储位置pb; 3. for (col=最小列号; col<=最大列号; col++) 3.1 在A中查找列号为col的三元组; 3.2 交换其行号和列号,存入B中pb位置; 3.3 pb++;

矩阵的压缩存储
三元组顺序表转置算法——算法Ⅱ 基本思想:顺序取,直接存。即在A中依次取三元 组,交换其行号和列号放到B 中适当位置。 如何确定当前从A中取出的三元组在B中的位置? 分析:A中第0列的第一个非零元素一定存储在B中下 标为0的位置上,该列中其它非零元素应存放在B中 后面连续的位置上,那么第1列的第一个非零元素在 B中的位置便等于第0列的第一个非零元素在B中的位 置加上第0列的非零元素的个数,以此类推。

矩阵的压缩存储
三元组顺序表转置算法——算法Ⅱ
0 1 2 3 4 5 6
MaxTerm-1

row col 0 0 0 4 1 1 2 1 3 0 3 2 5 0

item 15 91 11 3 22 6 -15

第0列第1个非零元素 第0列有2个非零元素 第1列第1个非零元素

6(矩阵的行数) 5(矩阵的列数) 7(非零元个数)

矩阵的压缩存储
三元组顺序表转置算法——算法Ⅱ 数据结构设计: 引入两个数组作为辅助数据结构: num[nu]:存储矩阵A中某列的非零元素的个数; cpot[nu]:初值表示矩阵A中某列的第一个非零元素 在B中的位置。 num与cpot存在如下递推关系: cpot[0]=0; cpot[col]=cpot[col-1]+num[col-1]; 1≤col<nu

矩阵的压缩存储
根据矩阵A计算num和cpot
0 1 2 3 4 5 6
MaxTerm-1

row col item 0 0 15 0 3 22 0 5 -15 1 1 11 1 2 3 2 3 6 4 0 91 空 空 空 闲 闲 闲 5(矩阵的行数) 6(矩阵的列数) 7(非零元个数)

col

0

1

2

3

4

5

num[col] 2 1 1 2 cpot[col] 0 2 3 4

0 1 6 6

矩阵的压缩存储
将矩阵A中col列元素存放在B中下标为cpot[col]的位置
0 1 2 3 4 5 6 row col item 0 0 15 0 3 22 0 5 -15 1 1 11 1 2 3 2 3 6 4 0 91 空 空 空 闲 闲 闲 5(矩阵的行数) 6(矩阵的列数) 7(非零元个数) row col 0 0 0 1 2 3 4 5 6 item 15

cpot[0] cpot[0] cpot[1] cpot[2] cpot[3]
cpot[4] cpot[5]

6(矩阵的行数) 5(矩阵的列数) 7(非零元个数)

矩阵的压缩存储
将矩阵A中col列元素存放在B中下标为cpot[col]的位置
0 1 2 3 4 5 6 row col item 0 0 15 0 3 22 0 5 -15 1 1 11 1 2 3 2 3 6 4 0 91 空 空 空 闲 闲 闲 5(矩阵的行数) 6(矩阵的列数) 7(非零元个数) row col 0 0 0 1 2 3 3 0 4 5 6 item 15

22

cpot[0] cpot[1] cpot[2] cpot[3] cpot[3] cpot[4] cpot[5]

6(矩阵的行数) 5(矩阵的列数) 7(非零元个数)

矩阵的压缩存储
将矩阵A中col列元素存放在B中下标为cpot[col]的位置
0 1 2 3 4 5 6 row col item 0 0 15 0 3 22 0 5 -15 1 1 11 1 2 3 2 3 6 4 0 91 空 空 空 闲 闲 闲 5(矩阵的行数) 6(矩阵的列数) 7(非零元个数) row col 0 0 0 1 2 3 3 0 4 5 5 0 6 item 15

cpot[0] cpot[1] cpot[2] 22
-15 cpot[3] cpot[4] cpot[5] cpot[5]

6(矩阵的行数) 5(矩阵的列数) 7(非零元个数)

矩阵的压缩存储
将矩阵A中col列元素存放在B中下标为cpot[col]的位置
0 1 2 3 4 5 6 row col item 0 0 15 0 3 22 0 5 -15 1 1 11 1 2 3 2 3 6 4 0 91 空 空 空 闲 闲 闲 5(矩阵的行数) 6(矩阵的列数) 7(非零元个数) row col 0 0 0 1 1 1 2 3 3 0 4 5 5 0 6 item 15 11

cpot[0] cpot[1] cpot[2] cpot[1]
cpot[3] cpot[4] cpot[5]

22
-15

6(矩阵的行数) 5(矩阵的列数) 7(非零元个数)

矩阵的压缩存储
将矩阵A中col列元素存放在B中下标为cpot[col]的位置
0 1 2 3 4 5 6 row col item 0 0 15 0 3 22 0 5 -15 1 1 11 1 2 3 2 3 6 4 0 91 空 空 空 闲 闲 闲 5(矩阵的行数) 6(矩阵的列数) 7(非零元个数) row col 0 0 0 1 1 1 2 2 1 3 3 0 4 5 5 0 6 item 15

cpot[0]
11 3 22 -15 cpot[2] cpot[1] cpot[1] cpot[2] cpot[3] cpot[4] cpot[5]

6(矩阵的行数) 5(矩阵的列数) 7(非零元个数)

矩阵的压缩存储
将矩阵A中col列元素存放在B中下标为cpot[col]的位置
0 1 2 3 4 5 6 row col item 0 0 15 0 3 22 0 5 -15 1 1 11 1 2 3 2 3 6 4 0 91 空 空 空 闲 闲 闲 5(矩阵的行数) 6(矩阵的列数) 7(非零元个数) row col 0 0 0 1 1 1 2 2 1 3 3 0 4 3 2 5 5 0 6 item 15

cpot[0]
11 3 22 6 -15 cpot[1] cpot[2] cpot[3] cpot[4] cpot[3] cpot[5]

6(矩阵的行数) 5(矩阵的列数) 7(非零元个数)

矩阵的压缩存储
将矩阵A中col列元素存放在B中下标为cpot[col]的位置
0 1 2 3 4 5 6 row col item 0 0 15 0 3 22 0 5 -15 1 1 11 1 2 3 2 3 6 4 0 91 空 空 空 闲 闲 闲 5(矩阵的行数) 6(矩阵的列数) 7(非零元个数) 0 1 2 3 4 5 6 row col 0 0 0 4 1 1 2 1 3 0 3 2 5 0 item 15 91 11 3 22 6 -15

cpot[0] cpot[0] cpot[1] cpot[2]
cpot[4] cpot[3] cpot[5]

6(矩阵的行数) 5(矩阵的列数) 7(非零元个数)

矩阵的压缩存储
三元组顺序表转置算法Ⅱ——伪代码 1. 设置转置后矩阵B的行数、列数和非零元素的个数; 2. 计算A中每一列的非零元素个数; 3. 计算A中每一列的第一个非零元素在B中的下标; 4. 依次取A中的每一个非零元素对应的三元组; 4.1 确定该元素在B中的下标pb; 4.2 将该元素的行号列号交换后存入B中pb的位置; 4.3 预置该元素所在列的下一个元素的存放位置;

矩阵的压缩存储
稀疏矩阵的压缩存储——十字链表 采用链接存储结构存储三元组表,每个非零元素对应 的三元组存储为一个链表结点,结构为: row down col item right

row:存储非零元素的行号 col:存储非零元素的列号 item:存储非零元素的值 right:指针域,指向同一行中的下一个三元组 down:指针域,指向同一列中的下一个三元组

矩阵的压缩存储
稀疏矩阵的压缩存储——十字链表


0

0

3

0


3

5


1


1 1


2


0

2


3 0 0 5 M= 0 1 0 0
2 0 0 0

广义线性表——广义表
广义表的基本概念
广义表:n(n≥0)个数据元素的有限序列,记作: LS=(a1,a2,……,an) 其中:LS是广义表的名称,ai(1≤i≤n)是LS的成员 (或直接元素),它可以是单个的数据元素,也可以 是一个广义表,分别称为LS的单元素(或原子)和子 表。

通常用大写字母表示广义表,用小写字母表示单元素。
广义表的逻辑结构:直接元素之间是线性关系。

广义线性表——广义表
广义表的基本概念
长度:广义表LS中的直接元素的个数;

深度:广义表LS中括号的最大嵌套层数。
表头:广义表LS非空时,称第一个元素为LS的表头;

表尾:广义表LS中除表头外其余元素组成的广义表。
广义表( )和广义表(( ))不同?

广义线性表——广义表
广义表的示例

A =( ) B =(e) C =(a, (b,c,d)) D =(A, B, C) E =(a, E) F =(( ))
长度?深度?表头?表尾?

广义线性表——广义表
广义表的图形表示

A =( ) B =(e) C =(a, (b,c,d)) D =(A, B, C) E =(a, E) F =(( ))

D

A

B e a b

C

c

d

广义线性表——广义表
广义表可以采用顺序存储结构吗? 由于广义表中的数据元素的类型不统一,因此难以 采用顺序存储结构来存储。 如何采用链接存储结构存储广义表? 若广义表不空,则可分解为表头和表尾;反之,一 对确定的表头和表尾可唯一地确定一个广义表。

采用头尾表示法存储广义表

广义线性表——广义表
广义表的存储结构——头尾表示法
头尾表示法中的结点结构?

广义表中的数据元素既可以是广义表也可以是单元素
表结点——存储广义表;元素结点——存储单元素

广义线性表——广义表
广义表的存储结构——头尾表示法
结点结构

tag=1

hp tp

tag=0

data

表结点

元素结点

tag:区分表结点和元素结点的标志; hp:指向表头结点的指针; tp:指向表尾结点的指针; data:数据域,存放单元素。

广义线性表——广义表
广义表的存储结构——头尾表示法
定义结点结构
enum Elemtag {Atom, List}; struct GLNode { Elemtag tag; union { T data; struct { GLNode *hp, *tp; } ptr; }; };

tag=1 tag=0

hp tp data

广义线性表——广义表
广义表的存储结构——头尾表示法
A B NULL 1 0 e C 1 0 a 1 1 0 b




A =( ) B =(e) C =(a, (b,c,d))

1 0 c

1



0 d

广义线性表——广义表
广义表的存储结构——头尾表示法
D

1 ∧

1

1



A =( ) B =(e) C =(a, (b,c,d)) D =(A, B, C)


B

1 0 e



C

1 0 a

1 1 0 b

1 0 c

1



0 d

广义线性表——广义表
广义表的存储结构——头尾表示法
E

1 0 a

1



E =(a, E) F =(( ))

F

1 ∧ ∧

第四章

广义线性表
广义线性表

多维数组 逻辑结构 存储结构 逻辑结构
⑴基本概念 · 广义表定义 · 表头、表尾 · 长度、深度 ⑵ADT定义

广义表 存储结构

⑴数组的定义 ⑵基本操作 ⑶ADT定义

顺 序 存 储
按 行 优 先 按 列 优 先

压 缩 存 储

链 接 存 储 头尾表示法

特殊矩阵 · 对称矩阵 · 三角矩阵 · 对角矩阵

稀疏矩阵
转置算法

寻址的计算方法


第4章广义线性表-1_图文.ppt

第4章广义线性表-1 - 第4章 广义线性表多维数组和广义表 本章的基本内容是

第4章广义线性表-2_图文.ppt

第4章广义线性表-2 - 4.3 广义表 广义表的基本概念 广义表:n(n≥0)

数据结构 第4章 广义线性表(g)_图文.ppt

数据结构 第4章 广义线性表(g) - 广东海洋大学 谢仕义 数据结构(C++版) 第四章 广义线性表 本章的基本内容是: 数组的逻辑结构特征 数组的存储方式及寻址方法...

第四章-广义线性回归_图文.pdf

第四章 广义线性回归 第四章 广义线性回归 1 / 26 第四章 广义线性回归 4.1 4.1.1 模型设定线性模型设定如下: 广义线性设定 其中, 为被解释变量, 为 K ...

广义线性表_图文.ppt

清华大学出版社 数据结构(C++版) 第四章 广义线性表 本章的基本内容是:数组

广义线性表剖析_图文.ppt

广义线性表剖析 - 清华大学出版社 数据结构(C++版) 第四章 广义线性表

第4章 其他线性数据结构_图文.ppt

第4章 其他线性数据结构_其它_职业教育_教育专区。第4章 其他线性数据结构 ...中的数据元素可以具 有不同的结构,故通常都采用链式的存储结构来存储广义 表。...

机器学习与模式识别-第4章_线性判别_图文.pdf

机器学习与模式识别-第4章_线性判别 - 第四章 线性判别函数 1 ? ? 4.1 引言 4.2 Fisher线性判别 ? 4.3 感知准则函数 ? 4.4 最小平方误差准则函数 ? ...

第四章 线性判别函数_图文.ppt

第四章 线性判别函数 §4.1 引言 1.按贝叶斯决策理论设计分类器的步骤 2.获取...广义线性判别函数 ? (所谓广义线性判别函数就是把非线性判别函数 映射到另外一...

[工学]第4章___线性系统的概轨迹法_图文.ppt

[工学]第4章___线性系统的概轨迹法 - 第四章 线性系统的根轨迹法 §4-1 根轨迹法的基本概念 §4-2 §4-3 §4-4 常规根轨迹的绘制法则 广义根轨迹...

模式识别 第四章 线性判别函数_图文.ppt

第四章 线性判别函数 1 主要内容 ?引言 ?Fisher线性判别 ?感知器准则 ?最小...一类是线性判别函数: ?线性判别函数 ?广义线性判别函数 (所谓广义线性判别函数就...

模式识别课件 第4章_图文.ppt

aT y 广义线性 判别函数 维数为10 第四章 线性判别函数 15 4.2 Fisher线性...而离散矩阵只是表 示有限个样本在空间分布的离散程度 第四章 线性判别函数 18 ...

第四章 极大似然估计和广义矩估计_图文.ppt

第四章 极大似然估计和广义矩估计_其它_职业教育_教育专区。第四章 极大似然...非线性模型的极大似然估计,将在第五章中介绍 。 16 双变量线性回归模型的极...

第四章 极大似然估计、非线性估计和广义矩估计_图文.ppt

第四章 极大似然估计、非线性估计和广义矩估计_理学_高等教育_教育专区。第四..

第四章 横截面数据分类_图文.ppt

数量自变量的判别分析,都 属于广义线性模型的特例,所以先简单回归一下广义线性...(见表4.11),行代 表正确的类,列代表模型判断的类,对角线外为判错个数....

广义线性表多维数组和广义表.doc

广义线性表多维数组和广义表 - 第 4 章 广义线性表多维数组和广义表

第8章_广义线性模型_图文.ppt

第8章_广义线性模型 - ? 回归分析中假定随机扰动服从这样的一些 正态分布:其

第3章-广义线性模型_图文.ppt

第3章-广义线性模型_经济/市场_经管营销_专业资料。主编:费宇 中国人民大学...2015/10/9 主编:费宇 15 例3.2(数据文件为eg3.2) 表3.4 Breslow癫痫...

数据结构第2章线性表讲义._图文.ppt

线性结构的特点: 简言之,线性结构反映结点间的逻辑关系是 一对一 第2章 线性表 线性结构 第3章 栈和队列 第4章 串、数组和广义线性表 最典型、最常用...

第4章 信道_图文.ppt

分类有线信道 狭义信道 信 无线信道 道 恒参信道 调制信道 广义信道 随参信道...举例表助词“的” 1.泻出于两峰之间者;2.醉翁之意不在酒;3.山水之乐;4....