数据结构概论 第5章 数组和广义表 董黎刚 浙江工商大学信电学院.

Presentation on theme: "数据结构概论 第5章 数组和广义表 董黎刚 浙江工商大学信电学院."— Presentation transcript:

1 数据结构概论 第5章 数组和广义表 董黎刚 浙江工商大学信电学院

2 1. 数组的逻辑结构

3 5.1.1 背景 数组（Array）是一种逻辑结构，是一种特殊的线性表：不能插入和删除元素（因为数组中元素的个数固定）。换句话说，数组是操作受限的线性表。 5.1 数组的逻辑结构

4 5.1.2 数组的特点 数组中不能插入和删除元素。因此一般数组都适合用顺序表存储（回避了顺序表的缺点）。
矩阵Am×n可以视为m*n个元素的线性表。然而，数组的数据元素也可以视为一个线性表，比如二维数组是“数据元素为一维数组（线性表）”的线性表。 5.1 数组的逻辑结构

5 5.1.2 数组的特点 二维数组中元素的顺序：行优先和列优先 5.1 数组的逻辑结构

6 5.1.2 数组的特点 按行优先顺序，元素aij的地址是Loc[i,j]=Loc[1,1]+n×(i-1)+(j-1)
如果每个元素占size个存储单元，则为： Loc[i, j]=Loc[1, 1] +(n×(i-1)+j-1)×size 5.1 数组的逻辑结构

7 5.1.3 操作 InitArray(A, n, bound1, …, boundn)：若维数n和各维的长度合法，则构造相应的数组A，并返回TRUE。 DestroyArray（A）：销毁数组A。 GetValue（A，e, index1,…, indexn）：用e返回数组A中由index1,…, indexn所指定的元素的值。 SetValue（A，e，index1, …, indexn）：将数组A中由index1, …, indexn所指定的元素的值置为e。 5.1 数组的逻辑结构

8 2. 三角矩阵和带状矩阵的压缩存储

9 5.2.1 背景 对于一些特殊矩阵，存储全部元素将是浪费空间，因此需要压缩存储。压缩的策略主要是两条：
为多个相同的非零元素只分配一个存储空间 对零元素不分配空间 本学习点学习三角矩阵和带状矩阵等两类矩阵的压缩存储。 5.2 三角矩阵和带状矩阵的压缩存储

10 5.2.2 三角矩阵 三角矩阵大体分为三类：下三角矩阵、上三角矩阵和对称矩阵。
下三角矩阵中，它的上三角(不包括主角线)中的元素均为常数c（经常c=0)。上三角矩阵与下三角矩阵相反。 5.2 三角矩阵和带状矩阵的压缩存储

11 5.2.3 三角矩阵 压缩存储思想：只存储下三角的元素（下面采用行优先） 原矩阵 5.2 三角矩阵和带状矩阵的压缩存储

12 5.2.3 三角矩阵 aij的位置 5.2 三角矩阵和带状矩阵的压缩存储

13 5.2.3 三对角带状矩阵 压缩存储思想：存储带状区域元素 原矩阵 5.2 三角矩阵和带状矩阵的压缩存储

14 5.2.3 三对角带状矩阵 aij的位置 5.2 三角矩阵和带状矩阵的压缩存储

15 3. 稀疏矩阵的压缩存储——三元组表

16 5.3.1 背景 稀疏矩阵（sparse matrix）就是多数元素为0的矩阵。如果还是存储每个元素，可能是浪费空间。
为决定存储方式，引用一个指标——稀疏因子 =t/(m*n) ，其中t为非零元素个数。 稀疏矩阵的一般小于0.05 5.3 稀疏矩阵的压缩存储——三元组表

17 5.3.2 三元组表表示法 存储思想：只存储非零元素。 稀疏矩阵的压缩存储会失去随机存取功能（即不能依靠行号和列号就可以直接访问元素）。
三元组表：将表示稀疏矩阵的非零元素的三元组按行优先(或列优先)的顺序依次存放。 5.3 稀疏矩阵的压缩存储——三元组表

18 5.3.2 三元组表的C语言定义 typedef struct { int row, col; //元素的行和列 int e；//元素值
}Triple; //定义“三元组” //存非零元素的数组，data[0]一般不用 Triple data[101]; //矩阵的行数、列数和非零元素个数 int m,n,len; }TSMatrix；//定义“三元组表” 5.3 稀疏矩阵的压缩存储——三元组表

19 5.3.3 三元组表的评价 优点：三元组表节约了存储空间。但是，矩阵中非0元素超过1/3（即>1/3）就不再节省空间了。
缺点：与正常的存储方式来讲，增加了相关算法的难度。这是以时间换空间。 5.3 稀疏矩阵的压缩存储——三元组表

20 dest[i][j]=source[j][i];
5.3.4 转置算法 一般矩阵的转置 for(i=0; i<m; i++) for(j=0; j<n; j++) dest[i][j]=source[j][i]; 算法复杂度：O（A.m×A.n） 5.3 稀疏矩阵的压缩存储——三元组表

21 5.3.4 转置算法 三元组表矩阵的转置动画 5.3 稀疏矩阵的压缩存储——三元组表

22 5.3.4 转置算法 三元组表矩阵的转置实例 A B 按照A中第1列、第2列、…顺序，也就是B中第1行、第2行、…顺序找遍A中全部元素
算法复杂度：O(A.n×A.len) n是A的列数 5.3 稀疏矩阵的压缩存储——三元组表

23 5.3.4 转置算法 三元组表矩阵的快速转置算法（从A转置到B）
第一步：遍历三元组表A，计算出A中第col列（也就是B中第col行）中元素个数，存入数组num[ ]，从而可以计算出B中每行的开始位置，存入数组position[], 比如position[col]存放B中第col行第一个元素的位置。 第二步：再次遍历三元组表A，依次把A中的元素，按照行列互换，直接放到B的正确位置上。 5.3 稀疏矩阵的压缩存储——三元组表

24 5.3.4 转置算法 三元组表矩阵的快速转置算法 A B A中的列，B中的行 A中每列/B中每行的元素个数 B中每行首元素的存放位置
5.3 稀疏矩阵的压缩存储——三元组表

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

26 5.4.1 背景 为什么用十字链表表示法？ 三元组表的转置和乘法算法时间复杂度与正常存储矩阵相当，但是三元组表的加减法算法效率不佳，因为加减中非零元素的位置和个数会发生很大的变化导致三元组表中大量移动元素。 5.4 稀疏矩阵的压缩存储——十字链表

27 5.4.2 定义 在十字链表中，矩阵的每一个非零元素用一个结点表示 行号 列号 元素值 向下的指针 向右的指针
5.4 稀疏矩阵的压缩存储——十字链表

28 5. 广义表

29 5.5.1 背景 广义表是线性表的扩展：数据元素不属于同一类型。因此，严格地说，广义表是一种非线性结构。
广义表被广泛地应用于人工智能等领域的表处理语言LISP语言中。 5.5 广义表

30 5.5.2 广义表定义 广义表是n个数据元素（d1，d2，d3，…，dn）的有限序列。广义表中的di既可以是单个元素（又称为原子），还可以是一个广义表。 d1是广义表GL的表头，而广义表GL其余部分组成的表（d2，d3，…，dn）称为广义表的表尾。 通常记作：GL=（d1，d2，d3，…，dn）或GL（d1，d2，d3，…，dn） 为了区分原子和广义表，书写时用大写字母表示广义表，用小写字母表示原子。 5.5 广义表

31 5.5.2 广义表实例 D=（）空表；其长度为零。该广义表也可记为D（）。
A=（a，（b，c））表长度为2的广义表，其中第一个元素是单个数据a，第二个元素是一个子表（b，c）。该广义表也可记为A（a，（b，c））。 B=（A，A，D）长度为3的广义表，其前两个元素为表A，第三个元素为空表D。该广义表也可记为B（A，A，D）。 C=（a，C）长度为2递归定义的广义表，C相当于无穷表C=（a，（a,（a，（…））））。该广义表也可记为C（a，C）。 head（A）=a 表A的表头是a。 tail（A）=（（b，c））表A的表尾是（（b，c））。广义表的表尾一定是一个表。 5.5 广义表

32 5.5.3 广义表图形表达 图中的分支结点对应广义表，叶子结点对应原子或空表 D=（） A=（a，（b，c）） B=（A，A，D）
C=（a，C） 图中的分支结点对应广义表，叶子结点对应原子或空表 5.5 广义表

33 5.5.4 广义表存储结构 方式一 （a）表结点 （b）原子结点 D=（） A=（a，（b，c）） B=（A，A，D） C=（a，C）
表头指针 header pointer 表尾指针 tail pointer 方式一 （a）表结点 （b）原子结点 D=（） A=（a，（b，c）） B=（A，A，D） C=（a，C） 5.5 广义表

34 5.5.4 广义表存储结构 方式二 （a）表结点 （b）原子结点 D=（） A=（a，（b，c）） B=（A，A，D） C=（a，C）
表头指针 header pointer 兄弟指针 sibling pointer 方式二 （a）表结点 （b）原子结点 D=（） A=（a，（b，c）） B=（A，A，D） C=（a，C） 5.5 广义表

35 总结