首页计算机计算机基础程序设计基础与数据结构 06 第五章 多维数组、稀疏矩阵和广义表.pptx

06 第五章 多维数组、稀疏矩阵和广义表.pptx

页数:24页文件大小:206.3 KB来源: 程序设计基础与数据结构ppt课件

本课件讲解三类非线性度更高的结构:先从二维数组的定义、初始化与行优先顺序存储展开多维数组;再进入稀疏矩阵,介绍三元组顺序表、行逻辑链接与十字链表三种压缩存储方法,并给出矩阵转置运算的实现与时间复杂度分析;最后介绍广义表的定义、深度、表头表尾及其链式存储结构。

第五章章节目录页,列出多维数组、稀疏矩阵、广义表与小结四个板块
多维数组概述页,给出数组的定义、一维二维与多维的分类以及数组上的基本操作
二维数组与多维数组说明页,指出二维数组元素受两个下标约束并可推广到n维
查看本课件的文字版(共 24 页,供检索与复制)

第1页:第五章 多维数组、稀疏矩阵和广义表

第五章 多维数组、稀疏矩阵和广义表

  • 5.1 多维数组
  • 5.2 稀疏矩阵
  • 5.3 广义表
  • 5.4 小结

第2页:多维数组概述

5.1 多维数组

  • 数组的定义:数组是相同类型的数据元素的有序集合。
  • 数组的分类:一维数组、二维数组、多维数组。
  • 数组的基本操作:初始化、销毁、取元素、修改元素、遍历等。

第3页:二维数组与多维数组

二维数组与多维数组

  • 二维数组:数组中的每个元素都受两个下标关系的约束。
  • 多维数组:数组中的每个元素都受多个下标关系的约束,二维以上的数组统称为多维数组。

第4页:二维数组示例

5.1.1 二维数组:以一张学生成绩单为例,同一行是某个学生的各科成绩,同一列是某一科所有学生的成绩,行号与列号共同确定一个元素。

第5页:二维数组的定义与初始化

二维数组的定义:类型说明符 数组名[常量表达式1][常量表达式2],例如 int a[3][4]。

二维数组的初始化:可以按行赋初值,也可以按元素排列顺序连续赋初值。

第6页:二维数组是一维数组的推广

二维数组是特殊的一维数组:可以把二维数组看成是由若干个一维数组作为元素组成的一维数组,其中每个元素又是一个一维数组。(图5-1 二维数组的一维数组视角)

第7页:二维数组的行优先存储

二维数组的顺序存储:由于存储单元是一维的,需要把二维数组的元素按一定次序排列成一维序列后再存放,通常采用行优先顺序,即先存放第0行的各元素,再存放第1行的各元素,依此类推。

第8页:多维数组

5.1.2 多维数组:多维数组中每个元素受多个下标约束,可以看成其元素为(n-1)维数组的一维数组;顺序存储时同样采用行优先(最低下标优先)的次序依次存放。

第9页:稀疏矩阵示例

5.2 稀疏矩阵:在矩阵中,若非零元素的个数远远小于矩阵元素的总数,且非零元素的分布没有规律,则称该矩阵为稀疏矩阵。

稀疏矩阵示例(非零元 5、3、6、2、4、7)
行 / 列第1列第2列第3列第4列第5列第6列
第1行000500
第2行003000
第3行000060
第4行204000
第5行000007

说明:原文中矩阵数字严重粘连(如“000500003000000060204000000000 7”),本表依据后文给出的三元组序列与转置矩阵反推还原,建议对照原图核对行列位置。

第10页:稀疏矩阵的存储方法

5.2.1 稀疏矩阵的存储方法:只存储非零元素,常见的压缩存储方式有:

  • 三元组顺序表
  • 行逻辑链接的顺序表
  • 十字链表

第11页:三元组顺序表

三元组顺序表:将稀疏矩阵的非零元用(行号 i,列号 j,值 value)三元组表示,并按行序优先排列。

稀疏矩阵的三元组顺序表
序号i(行号)j(列号)value(值)
1145
2233
3356
4412
5434
6567

说明:原文该处三元组序列末尾另出现一个“(5,6,6)”,与已有“(5,6,7)”行号列号重复,疑为文字提取误差,本表按十字链表存储示意中的六组三元组给出,建议对照原图核对。

第12页:三元组的类型定义

三元组顺序表的存储结构定义:

 typedef struct element_st { int data; ... } ELEMENT; typedef struct tuple_st { ELEMENT element; int i, j; } TUPLE;

第13页:三元组表存储示意

图5-4 稀疏矩阵的三元组表存储示意:矩阵中的非零元按行序优先依次存入三元组表,表中每一项由 i、j、value 三个域组成,并同时保存矩阵的总行数、总列数与非零元个数。

第14页:十字链表结点结构

十字链表:为每个非零元设置一个结点,结点包含五个域——行号、列号、值,以及指向同一行下一个非零元的指针与指向同一列下一个非零元的指针。

同一行的非零元通过行链链接成线性链表,同一列的非零元通过列链链接成线性链表,整个矩阵构成十字交叉的链表结构。

第15页:十字链表存储表示

图5-6 十字链表的存储表示:稀疏矩阵的十字链表由一组行头指针与一组列头指针共同索引,每个非零元结点同时挂在行链与列链上。

第16页:稀疏矩阵的转置

5.2.2 稀疏矩阵的转置运算:转置即把矩阵的行与列互换,A 中第 i 行第 j 列的元素成为 B 中第 j 行第 i 列的元素。

转置矩阵示例(B,6 行 5 列)
行 / 列第1列第2列第3列第4列第5列
第1行00020
第2行00000
第3行03040
第4行50000
第5行00600
第6行00007

说明:原文转置矩阵的数字同样存在粘连,本表依据三元组与转置对应关系还原,建议对照原图核对。

第17页:三元组表的转置算法

三元组表的转置算法思路:

  • 第一步:交换三元组表中每个元素的行号与列号,得到行列互换后的三元组。
  • 第二步:由于转置后要求按行序优先排列,需按原矩阵的列号从小到大依次扫描,把得到的三元组依次放入结果表。
  • 结果表中同时更新矩阵的行数、列数与非零元个数。

第18页:转置算法的复杂度

转置算法的时间复杂度:

  • 若三元组表中非零元个数为 t、原矩阵列数为 n,则按列序扫描的双层循环需执行 n 趟,每趟扫描全部 t 个三元组。
  • 因此时间复杂度为 O(n × t),当非零元个数 t 与矩阵规模 m × n 同数量级时,其复杂度高于普通矩阵转置的 O(m × n)。

第19页:广义表概述

5.3 广义表:广义表是线性表的推广,其元素既可以是单个数据元素,也可以是一个广义表。本节介绍广义表的定义、存储结构及其上的运算。

第20页:广义表的定义

5.3.1 广义表的定义

  • 广义表是 n(n ≥ 0)个数据元素 a1, a2, ..., an 的有限序列,记作 LS = (a1, a2, ..., an)。
  • 其中 ai 既可以是单个数据元素(称为原子),也可以是一个广义表(称为子表)。
  • 当 n = 0 时为空表;表的第一个元素 a1 称为表头,其余元素组成的表称为表尾。

第21页:广义表的深度与表头表尾

广义表的深度:广义表中括号的最大层数称为广义表的深度,原子的深度为0,空表的深度为1。

表头与表尾:

  • 表头 head(LS):广义表的第一个元素,可以是原子,也可以是子表。
  • 表尾 tail(LS):除表头外其余元素组成的广义表,必定是一个广义表。

第22页:广义表的存储结构

5.3.2 广义表的存储结构:通常采用链式存储,结点中设置一个标志位 tag:

  • tag = 0 表示原子结点,另设域存放原子值;
  • tag = 1 表示表结点,另设指针指向子表;
  • 此外还设有指向同一层下一个结点的指针,从而把同一层的元素串成链表。

(图5-8 广义表的链式存储结点结构)

第23页:广义表的存储示例与运算

广义表的存储示例:图中给出一个含原子与子表的广义表所对应的链式存储结构,表结点与原子结点通过 tag 标志区分并逐层链接。(图5-9 广义表的存储示例)

广义表的基本运算:求表头、求表尾、求长度、求深度、遍历等。

第24页:第五章小结

5.3 小结

  • 多维数组:数组的定义与顺序存储
  • 特殊的矩阵:对称矩阵、三角矩阵、稀疏矩阵的压缩存储
  • 广义表:广义表的概念、存储与运算
顶部目录