kl800.com省心范文网

第4章 广义线性表(1)_图文

数据结构(C++版)

第四章

广义线性表

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

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

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

数据结构(C++版)

第四章

广义线性表

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

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

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

数据结构(C++版)

第四章

广义线性表

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

数据结构(C++版)

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

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

数据结构(C++版)

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

A=

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

数据结构(C++版)

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

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

A=

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

数据结构(C++版)

广义线性表——多维数组
数组的基本操作
在数组中插入(或)一个元素有意义吗?
将元素 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=

数据结构(C++版)

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

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

数据结构(C++版)

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

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

c al
Loc(al)

al+1

……

ai-1

ai

……

ah

Loc(ai)

数据结构(C++版)

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

一维结构

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

数据结构(C++版)

广义线性表——多维数组
按行优先存储的寻址
m
每行元素个数

整 行 数
本行中aij前面的元素个数

aij

aij前面的元素个数
n
(a) 二维数组
=阴影部分的面积 =整行数×每行元素个数+本行中 aij前面的元素个数 =i*m+j

数据结构(C++版)

广义线性表——多维数组
按行优先存储的寻址
Loc(aij)=Loc(a00)+((i*m+j)×c

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

数据结构(C++版)

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

数据结构(C++版)

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

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

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

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

数据结构(C++版)

矩阵的压缩存储
对称矩阵的压缩存储
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) 计算方法

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

数据结构(C++版)

矩阵的压缩存储
特殊矩阵的压缩存储——三角矩阵 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) 下三角矩阵

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

数据结构(C++版)

矩阵的压缩存储
下三角矩阵的压缩存储 存储
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

数据结构(C++版)

矩阵的压缩存储
上三角矩阵的压缩存储(自己课后思考) 存储

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

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

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

当i≤j
当i>j

数据结构(C++版)

矩阵的压缩存储
*特殊矩阵的压缩存储——对角矩阵 对角矩阵:所有非零元素都集中在以主对角线为中心 的带状区域中,除了主对角线和它的上下方若干条对 角线的元素外,所有其他元素都为零。
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

数据结构(C++版)

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

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

数据结构(C++版)

矩阵的压缩存储
对角矩阵的压缩存储
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) 压缩到一维数组中

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

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

数据结构(C++版)

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

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

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

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

数据结构(C++版)

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

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

数据结构(C++版)

矩阵的压缩存储
稀疏矩阵的压缩存储——三元组顺序表 采用顺序存储结构存储三元组表
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(矩阵的列数)

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

数据结构(C++版)

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

数据结构(C++版)

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

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

数据结构(C++版)

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

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

数据结构(C++版)

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

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

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

数据结构(C++版)

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

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

数据结构(C++版)

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

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

数据结构(C++版)

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

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

数据结构(C++版)

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

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

数据结构(C++版)

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

tag=1

hp tp

tag=0

data

表结点

元素结点

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

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

数据结构(C++版)

tag=1 tag=0

hp tp data

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


数据结构(C++版)



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

1 0 c

1



0 d

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

数据结构(C++版)

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

数据结构(C++版)

1 0 a

1



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

F

1 ∧ ∧

广义线性表——广义表
template <class T> class Lists { public: Lists( ) ; Lists(Lists ls1, Lists ls2); ~Lists( ); int Length( ); int Depth(GLNode<T> *ls); GLNode *Head( ); GLNode *Tail( ); private: GLNode<T> *ls; };

数据结构(C++版)

广 义 表 类 的 声 明

广义线性表——广义表
广义表的操作——建立广义表

数据结构(C++版)

template <class T> Lists::Lists(Lists ls1,Lists ls2) { ls = new GLNode ls->tag = 1; ls->ptr.hp = ls1; ls->ptr.tp = ls2; }

广义线性表——广义表
广义表的操作——求广义表的深度
template <class T> int Lists::Depth(GLNode<T> *ls) { if (ls==NULL) return 1; if (ls->tag==0) return 0; max=0; p = ls; while (p) { dep = Depth(p->ptr.hp); if (dep>max) max = dep; p = p->ptr.tp; } return max+1; }

数据结构(C++版)

第四章

广义线性表
广义线性表

数据结构(C++版)

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

广义表 存储结构

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

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

压 缩 存 储

链 接 存 储 头尾表示法

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

稀疏矩阵
转置算法

寻址的计算方法


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

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

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

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

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

第4章 数据结构-广义线性表. - 清华大学出版社 数据结构(C++版) 第四章 广义线性表 本章的基本内容是: 数组的逻辑结构特征 数组的存储方式及寻址方法 特殊...

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

第4章广义线性表-2 - 4.3 广义表 广义表的基本概念 广义表:n(n≥0)个数据元素的有限序列,记作: LS=(a1,a2,……,an) 其中:LS是广义表的名称,ai(1≤i≤...

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

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

数据结构课件 第4章数组和广义表_图文.ppt

数据结构课件 第4章数组和广义表_数学_高中教育_教育专区。文档均来自网络,如有侵权请联系我删除文档 第四章 广义线性表多维 数组和广义表 1 本章的基本内容:...

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

第四章线性判别函数1 - 第四章 线性判别函数 ? Bayesian分类器设计方

广义线性表.doc

第4 章 广义线性表多维数组和广义表课后习题讲解 1. 填空 ⑴ 数组通常只有两种运算:( )( ),这决定了数组通常采用( )结构来 实现存储。 【解答】存取,...

第2章线性表1(顺序表)_图文.ppt

第2章线性表1(顺序表) - 线性结构的定义: 若结构是非空有限集,则有且仅有一

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

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

第4章非参数判别分类方法(线性判别函数).._图文.ppt

第4章非参数判别分类方法(线性判别函数).. - 模式识别 徐蔚然 北京邮电大学信息工程学院 非参数判别分类方法 ? 包括内容 ? ? ? ? ? 第4章 线性判别函数 第...

2012秋-11第四章4-1-4-4_图文.ppt

2012秋-11第四章4-1-4-4_语文_小学教育_教育...F?t 13 14 §4-2 变形体虚功原理 二、广义力...FQidv ? Mid? ] 适用于各种杆件体系(线性,非线性...

第4章 非参数判别分类方法(线性判别函数)_图文.ppt

第4章 非参数判别分类方法(线性判别函数)_数学_自然科学_专业资料。模式识别...向量模||W'||为1 而W'TX就是直线上任点到W'向量的投影 广义线性判别...

第4章 一元线性回归模型_图文.ppt

第4章 线性回归模型 - 第四章 线性回归模型 第1节 引言 ? 回归分

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

(4.1) 1、拟合广义线性模型在R中可用函数glm()来处理. 以column.2C.csv数据...(zz) 表4.4 logistic回归分类结果 4.1.4 probit回归 和logistic回归类似,结果也...

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

? 本章介绍两种常见的广义线性模型:Logistic模型与 对数线性模型. 2015/10/9 主编:费宇 4 3.1 广义线性模型概述 1.广义线性模型的定义: (1)随机成分:设y1,y...

第4章 统计方法_图文.pdf

第4章 统计方法本章目标 阐述统计推论在数据挖掘中的一些常用方法。 介绍评价...回归方程的广义线性模型如下: Y=α+β1 X1+β2 X2+β3 X3+…+...

第4章 串_图文.ppt

第4章 串 - 本章将讨论串的存储方法、 基本运算及其实现。 第一节 一、基本概念和术语 串类型的定义 1、串:是一种特殊的线性表,数据元素由单个字 符构成。...

第4章 多维数组和广义表_图文.ppt

数据结构 第4章 多维数组和广义第4章 多维数组和广义表 ?4.1 多维数组 ?...?三维数组:每个元素为二维数组的线性表。 ?n维数组:每个元素为n?1维数组的...

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

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