《数据结构数组和广义表》由会员分享，可在线阅读，更多相关《数据结构数组和广义表（37页珍藏版）》请在金锄头文库上搜索。
1、数据结构课程的内容第5章 数组和广义表（Arrays /数组元素基址int dim; /数组维数int *bound; /数组各维长度信息保存区基址int *constants; /数组映像函数常量的基址Array;即Ci信息保存区数组的基本操作函数说明（有5个） （请阅读教材P93-95） N维数组的顺序存储表示（见教材P93）顺序存储方式：按低地址优先（或高地址优先）顺序存入一维 数组。行指针向量a11a12a1nam1am2amn补充： 链式存储方式：用带行指针向量的单链表来表示。注：数组的运算参见下一节实例（稀疏矩阵的转置 ）（难点是多维数组与一维数组的地址映射关系）5.3 矩阵的压缩
2、存储讨论： 1. 什么是压缩存储？若多个数据元素的值都相同，则只分配一个元素值的存储空间 ，且零元素不占存储空间。 2. 什么样的矩阵具备压缩条件？ 特殊矩阵（对称矩阵，对角矩阵，三角矩阵） 和稀疏矩阵。 3. 什么叫稀疏矩阵？矩阵中非零元素的个数较少（一般小于5%）重点介绍稀疏矩阵的压缩和相应的操作。一、稀疏矩阵的压缩存储问题： 如果只存储稀疏矩阵中的非零元素，那这些元素的 位置信息该如何表示？解决思路： 对每个非零元素增开若干存储单元，例如存放其所 在的行号和列号，便可准确反映该元素所在位置。实现方法： 将每个非零元素用一个三元组（i，j，aij）来表示， 则每个稀疏矩阵可用一个三元组表来
3、表示。二、稀疏矩阵的操作例1 ：三元组表中的每个结点对应于稀疏矩阵的一 个非零元素，它包含有三个数据项，分别表示该元 素的 、 和 。 行下标列下标元素值例2：写出右图所示稀疏 矩阵的压缩存储形式。0 12 9 0 0 0 0 0 0 0 0 0-3 0 0 0 14 0 0 0 24 0 0 0 0 18 0 0 0 0 15 0 0 -7 0 0( 1,2,12) ，(1,3,9)， (3,1,-3)， (3,5,14)，(4,3,24)， (5,2,18) ，(6,1,15)， (6,4,-7)法1：用线性表表示：0 12 9 0 0 0 0 0 0 0 0 0-3 0 0 0 14 0
4、 0 0 24 0 0 0 0 18 0 0 0 0 15 0 0 -7 0 0法2：用三元组表表示：0 12 9 0 0 0 0 0 0 0 0 0-3 0 0 0 14 0 0 0 24 0 0 0 0 18 0 0 0 0 15 0 0 -7 0 0121213931-3351443245218611564-7注意：为更可靠描述 ，通常再加一行“总体 ”信息：即总行数、总 列数、非零元素总个 数668ijvalue稀疏矩阵压缩存储的缺点：将失去随机存取功能 :-(0 01 12 23 34 45 56 67 78 8法3：用带辅助向量的三元组表示 。方法： 增加2个辅助向量： 记录每行非
5、0元素个数，用NUM（i）表示； 记录稀疏矩阵中每行第一个非0元素在三元组中的行号，用POS（i）表示。76531211202NUM( i)6543POS( i )21i0 12 9 0 0 0 0 0 0 0 0 0-3 0 0 0 14 0 0 0 24 0 0 0 0 18 0 0 0 0 15 0 0 -7 0 0-7461516182524341453-3139311221866vji0 123456783用途：通过三元组高效访问稀疏矩阵中 任一非零元素。规律：POS(1)1POS(i)POS(i-1)+NUM(i-1)法4：用十字链表表示 用途：方便稀疏矩阵的加减运算； 方法：每个
6、非0元素占用5个域。right downvji同一列中下一非 零元素的指针同一行中下一非 零元素的指针 十字链表的特点： 每行非零元素链接成带表头结点的循环链表； 每列非零元素也链接成带表头结点的循环链表。 则每个非零元素既是行循环链表中的一个结点；又是列循环 链表中的一个结点，即呈十字链状。以刚才的 稀疏矩阵 为例：122100H19311825#define MAXSIZE 125000 /设非零元素最大个数125000typedef struct int i; /元素行号int j; /元素列号ElemType e; /元素值 Triple; typedef struct Triple
7、dataMAXSIZE+1; /三元组表，以行为主序存入一维向量 data 中int mu; /矩阵总行数int nu; /矩阵总列数int tu; /矩阵中非零元素总个数 TsMatrix; 三元组表的顺序存储表示（见教材P98）：/一个结点的结构定义/整个三元组表的定义二、稀疏矩阵的操作 0 12 9 0 0 0 0 0 0 0 0 0 -3 0 0 0 14 0 0 0 24 0 0 0 0 18 0 0 0 0 15 0 0 -7 0 00 0 3 0 0 15 12 0 0 0 18 09 0 0 24 0 0 0 0 0 0 0 -7 0 0 14 0 0 0 0 0 0 0 0
8、0(1, 2, 12)(1, 3, 9 )(3, 1, -3)(3, 5, 14)(4, 3, 24)(5, 2, 18)(6, 1, 15)(6, 4, -7)(1, 3, -3)(1, 6, 15)(2, 1, 12)(2, 5, 18)(3, 1, 9)(3, 4, 24)(4, 6, -7)(5, 3, 14)三 元 组 表 a.data三 元 组 表 b.data转置后MT（以转置运算为例）目的：答：肯定不正确！ 除了： （1）每个元素的行下标和列下标互换（即三元组中 的i和j互换）； 还应该：（2）T的总行数mu和总列数nu与M的不同（互换）；（3）重排三元组内元素顺序，使转置后的
9、三元组也 按行（或列）为主序有规律的排列。上述（1）和（2）容易实现，难点在（3）。若采用三元组压缩技术存储稀疏矩阵，只要把每个 元素的行下标和列下标互换，就完成了对该矩阵的转置运 算，这种说法正确吗？ 有两种实现方法压缩转置(压缩)快速转置提问：方法1：压缩转置思路：反复扫描a.data中的列序，从小到大依次进行转置 。三 元 组 表 a.data三 元 组 表 b.data(1, 3, -3)(1, 6, 15)(2, 1, 12)(2, 5, 18)(3, 1, 9)(3, 4, 24)(4, 6, -7)(5, 3, 14)(1, 2, 12) (1, 3, 9 ) (3, 1, -3
10、) (3, 5, 14) (4, 3, 24) (5, 2, 18) (6, 1, 15) (6, 4, -7)1122col q1 2 3 4p1 2 3 4Status TransPoseSMatrix(TSMatrix M, TSMatrix T.nu=M.mu; T.tu=M.tu;if (T.tu) q=1; for(col=1; col=M.nu; col+) for(p=1; p=M.tu; p+) if (M.datap.j=col)T.dataq.i=M.datap.j; T.dataq.j=M.datap.i;T.dataq.value=M.datap.value; q+;
11、return OK; /TranposeSMatrix;压缩转置算法描述：（见教材P99）/用三元组表存放稀疏矩阵M，求M的转置矩阵T/q是转置矩阵T的结点编号/col是扫描M三元表列序的变量 /p是M三元表中结点编号1、主要时间消耗在查找M.datap.j=col的元素，由两重循 环完成: for(col=1; col=M.nu; col+) 循环次数nufor(p=1; p=M.tu; p+) 循环次数tu 所以该算法的时间复杂度为O(nu*tu)-即M的列数与M中非零元素的个数之积最恶劣情况：M中全是非零元素，此时tu=mu*nu， 时间复杂度为 O(nu2*mu ) 注：若M中基本上是
12、非零元素时，即使用非压缩传统转置算法 的时间复杂度也不过是O(nu*mu) （程序见教材P99）结论：压缩转置算法不能滥用。前提：仅适用于非零元素个数很少（即tumu*nu）的情况。压缩转置算法的效率分析：方法2 快速转置三 元 组 表 a.data三 元 组 表 b.data(1, 3, - 3)(2 ,1,12)(2, 5, 18)(3, 1, 9)(4, 6, -7)(5, 3, 14)(1, 6, 15)(3, 4, 24)(1, 2, 12)(1, 3, 9 )(3, 1, -3)(3, 5, 14)(4, 3, 24)(5, 2, 18)(6, 1, 15)(6, 4, -7)思路
13、：依次把a.data中的元素直接送入b.data的恰当位 置上（即M三元组的p指针不回溯）。关键：怎样寻找b.data的“恰当”位置？p 1 2 3 4q35如果能预知M矩阵每一列(即T的每一行)的非零元素个数，又 能预知第一个非零元素在b.data中的位置,则扫描a.data时便 可以将每个元素准确定位（因为已知若干参考点）。技巧：利用带辅助向量的三元组表，它正好携带每行（或列 ）的非零元素个数 NUM(i)以及每行（或列）的第一个 非零元素在三元组表中的位置POS(i) 等信息。设计思路：i123456NUM(i )202112POS( i )133567不过我们需要的是按列生成的M矩阵的辅助向量。规律：POS(1)1 POS(i)POS(i-1)+NUM(i- 1)请回忆 ：请注意a.data特征：每列首个非零元素必定先被扫描到。令：M中的列变量用col表示；num col ：存放M中第col 列中非0元素个数，cpot col ：存放M中第col列的第一个非0元素的位置，（即b.data中待计算的“恰当”位置所
