页数:24页文件大小:206.3 KB来源: 程序设计基础与数据结构ppt课件
本课件讲解三类非线性度更高的结构:先从二维数组的定义、初始化与行优先顺序存储展开多维数组;再进入稀疏矩阵,介绍三元组顺序表、行逻辑链接与十字链表三种压缩存储方法,并给出矩阵转置运算的实现与时间复杂度分析;最后介绍广义表的定义、深度、表头表尾及其链式存储结构。
第五章 多维数组、稀疏矩阵和广义表
5.1 多维数组
二维数组与多维数组
5.1.1 二维数组:以一张学生成绩单为例,同一行是某个学生的各科成绩,同一列是某一科所有学生的成绩,行号与列号共同确定一个元素。
二维数组的定义:类型说明符 数组名[常量表达式1][常量表达式2],例如 int a[3][4]。
二维数组的初始化:可以按行赋初值,也可以按元素排列顺序连续赋初值。
二维数组是特殊的一维数组:可以把二维数组看成是由若干个一维数组作为元素组成的一维数组,其中每个元素又是一个一维数组。(图5-1 二维数组的一维数组视角)
二维数组的顺序存储:由于存储单元是一维的,需要把二维数组的元素按一定次序排列成一维序列后再存放,通常采用行优先顺序,即先存放第0行的各元素,再存放第1行的各元素,依此类推。
5.1.2 多维数组:多维数组中每个元素受多个下标约束,可以看成其元素为(n-1)维数组的一维数组;顺序存储时同样采用行优先(最低下标优先)的次序依次存放。
5.2 稀疏矩阵:在矩阵中,若非零元素的个数远远小于矩阵元素的总数,且非零元素的分布没有规律,则称该矩阵为稀疏矩阵。
| 行 / 列 | 第1列 | 第2列 | 第3列 | 第4列 | 第5列 | 第6列 |
|---|---|---|---|---|---|---|
| 第1行 | 0 | 0 | 0 | 5 | 0 | 0 |
| 第2行 | 0 | 0 | 3 | 0 | 0 | 0 |
| 第3行 | 0 | 0 | 0 | 0 | 6 | 0 |
| 第4行 | 2 | 0 | 4 | 0 | 0 | 0 |
| 第5行 | 0 | 0 | 0 | 0 | 0 | 7 |
说明:原文中矩阵数字严重粘连(如“000500003000000060204000000000 7”),本表依据后文给出的三元组序列与转置矩阵反推还原,建议对照原图核对行列位置。
5.2.1 稀疏矩阵的存储方法:只存储非零元素,常见的压缩存储方式有:
三元组顺序表:将稀疏矩阵的非零元用(行号 i,列号 j,值 value)三元组表示,并按行序优先排列。
| 序号 | i(行号) | j(列号) | value(值) |
|---|---|---|---|
| 1 | 1 | 4 | 5 |
| 2 | 2 | 3 | 3 |
| 3 | 3 | 5 | 6 |
| 4 | 4 | 1 | 2 |
| 5 | 4 | 3 | 4 |
| 6 | 5 | 6 | 7 |
说明:原文该处三元组序列末尾另出现一个“(5,6,6)”,与已有“(5,6,7)”行号列号重复,疑为文字提取误差,本表按十字链表存储示意中的六组三元组给出,建议对照原图核对。
三元组顺序表的存储结构定义:
typedef struct element_st { int data; ... } ELEMENT; typedef struct tuple_st { ELEMENT element; int i, j; } TUPLE;图5-4 稀疏矩阵的三元组表存储示意:矩阵中的非零元按行序优先依次存入三元组表,表中每一项由 i、j、value 三个域组成,并同时保存矩阵的总行数、总列数与非零元个数。
十字链表:为每个非零元设置一个结点,结点包含五个域——行号、列号、值,以及指向同一行下一个非零元的指针与指向同一列下一个非零元的指针。
同一行的非零元通过行链链接成线性链表,同一列的非零元通过列链链接成线性链表,整个矩阵构成十字交叉的链表结构。
图5-6 十字链表的存储表示:稀疏矩阵的十字链表由一组行头指针与一组列头指针共同索引,每个非零元结点同时挂在行链与列链上。
5.2.2 稀疏矩阵的转置运算:转置即把矩阵的行与列互换,A 中第 i 行第 j 列的元素成为 B 中第 j 行第 i 列的元素。
| 行 / 列 | 第1列 | 第2列 | 第3列 | 第4列 | 第5列 |
|---|---|---|---|---|---|
| 第1行 | 0 | 0 | 0 | 2 | 0 |
| 第2行 | 0 | 0 | 0 | 0 | 0 |
| 第3行 | 0 | 3 | 0 | 4 | 0 |
| 第4行 | 5 | 0 | 0 | 0 | 0 |
| 第5行 | 0 | 0 | 6 | 0 | 0 |
| 第6行 | 0 | 0 | 0 | 0 | 7 |
说明:原文转置矩阵的数字同样存在粘连,本表依据三元组与转置对应关系还原,建议对照原图核对。
三元组表的转置算法思路:
转置算法的时间复杂度:
5.3 广义表:广义表是线性表的推广,其元素既可以是单个数据元素,也可以是一个广义表。本节介绍广义表的定义、存储结构及其上的运算。
5.3.1 广义表的定义
广义表的深度:广义表中括号的最大层数称为广义表的深度,原子的深度为0,空表的深度为1。
表头与表尾:
5.3.2 广义表的存储结构:通常采用链式存储,结点中设置一个标志位 tag:
(图5-8 广义表的链式存储结点结构)
广义表的存储示例:图中给出一个含原子与子表的广义表所对应的链式存储结构,表结点与原子结点通过 tag 标志区分并逐层链接。(图5-9 广义表的存储示例)
广义表的基本运算:求表头、求表尾、求长度、求深度、遍历等。
5.3 小结
下载地址:{{downurl}}
{{{a}}}
{{#b}}{{{b}}}
{{/b}} {{/title}} {{#nolog}}登陆注册
{{/nolog}} {{#djsx}}点我刷新
{{/djsx}} {{#gocz}} {{/gocz}} {{#ffqr}} {{/ffqr}}