云南师范大学信息学院数据结构课件第5章 数组和广义.pptVIP

* 当矩阵 M 中非零元个数几乎和矩阵元素个数相等时，即 len 和 m×n等数量级时，算法时间复杂度就为 O(m×n2)，虽然节省了存储空间，但时间复杂度提高了。由此可见，上述求转置矩阵算法只适合于 len m×n 的情况。 当矩阵非零元素的位置或个数经常变动时，就不易采用顺序存储结构表示三元组的线性表。例如，在进行 “将矩阵 B 加到矩阵 A 上” 的操作时，由于非零元素的插入或删除将会引起 A.data 中元素的大量移动。为此，对这种类型的矩阵，采用链式存储结构表示三元组的线性表更为恰当。 * 2. 十字链表 (1) 稀疏矩阵的十字链表存储表示 ? 矩阵中非零元的行号 row； ? 矩阵中非零元的列号 col； ? 矩阵中非零元的值 e； ? 向右域 right，用以链接同一行中下一个非零元； ? 向下域 down，用以链接同一列中下一个非零元。 * row down col value right 非零元行号 非零元列号 非零元的值 向下域 向右域 在链表中，矩阵的非零元素可用如下结点表示： typedef struct OLNode { // 结点定义 int row, col; // 该非零元的行和列下标 ElementType value; // 该非零元的值 struct OLNode *right, *down; // 该非零元所在的行表和列表的后继链域 } OLNode; *Olink; typedef struct { // 十字链表定义 int m, n, len; // 稀疏矩阵行数、列数和非零元个数 Olink *row_head, *col_head; // 行和列链表头指针向量基址，由 CreateSMatrix 分配 } CrossList; // 十字链表存储结构的类型名 * 广义表 (generalized list) 是线性表的推广，有时也称为列表（lists，用复数形式以示与统称的表 list 的区别）。广泛地应用于人工智能等领域的 LISP（表处理语言），把广义表作为基本的数据结构，就连程序也表示为一系列的广义表。 * 5.4 广义表 广义表的逻辑结构 和数组一样，广义表也可以看成是线性表在下述含义上的扩展：表中的数据元素本身也是一种数据结构。 * 广义表的存储结构 * 5.4.1 广义表的逻辑结构 广义表一般记作：GL = ( a1 , a2 , … , an ) 其中： n 是广义表 GL 的长度； ai 可以是单个元素，也可以是广义表，分别称为广义表 GL 的原子和子表，习惯上用大写字母表示广义表的名称，用小写字母表示原子的名称。 GL 是广义表 ( a1 , a2 , … , an ) 的名称； 1. 广义表的定义 例5-1 A = ( )，A 是一个空表，它的长度为零。 例5-2 B = (e)，B 只有一个原子 e，它的长度为 1。 例5-3 C = (a, (b, c, d))，C 的长度为 2，两个元素分别为原子 a 和子表 (b, c, d)。 例5-4 D = (A, B, C)，D 的长度为 3，三个元素分别为 A、B 和 C，都是广义表。显然，将上面所述三个子表的值代入以后，则有 D = (( ), (e), (a, (b, c, d)))。 例5-5 E = (a, E)，这是一个递归表，它的长度为 2，E 相当于一个无限的广义表 E = (a, (a, (a, …)))。 * 2. 广义表的三个重要结论 从上述定义和例子推出如下广义表的三个重要结论 (1) 广义表的元素可以是子表，而子表的元素还可以是子表，…。由此，广义表是一个多层次结构。 (2) 广义表可以为其他广义表所共享。例如在上述例子中，广义表 A、B 和 C 为 D 的子表，则在 D 中可以不必列出广义表的值，而是通过子表的名称引用。 (3) 广义表可以是一个递归表，即广义表也可以是其本身的一个子表。例如广义表 E 就是一个递归的表。 * 和线性表相类似，可以对广义表进行的操作有查找、插入、删除和取表元素等。由于广义表在结构上较线性表复