5.ppt数据结构.ppt

第5章 数组和广义表（Arrays Lists） 5.1 数组的定义 二维数组的特点： N维数组的数据类型定义 5.2 数组的顺序存储表示和实现 通常有两种顺序存储方式： 以行序为主序 以列序为主序 若是N维数组，其中任一元素的地址该如何计算？ Loc(j1,j2,…jn)=LOC(0,0,…0)＋ 三维数组的存储 N维数组的顺序存储表示 六维数组的表示：A[5][6][4][2][3][2] 5.3 矩阵的压缩存储 一、稀疏矩阵的压缩存储 例1 ： 三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的 、 和 。 三元组表的顺序存储表示 二、稀疏矩阵的操作 方法1：压缩转置 方法2 快速转置 设计思路： 令：M中的列变量用col表示； num[ col ]：存放M中第col 列中非0元素个数， cpot[ col ]：存放M中第col列的第一个非0元素的位置， （即b.data中待计算的“恰当”位置所需参考点） 5.4 广义表的定义 5.5 广义表的存储结构 1. 与常规算法相比，附加了生成辅助向量表的工作。增开了2个长度为列长的数组(num[ ]和cpos[ ]）。 传统转置：O(mu*nu) 压缩转置：O(mu*tu) 压缩快速转置：O(nu+tu)——牺牲空间效率换时间效率。 快速转置算法的效率分析： 2. 从时间上，此算法用了4个并列的单循环，而且其中前3个单循环都是用来产生辅助向量表的。 for(col = 1; col =M.nu; col++) 循环次数＝nu; for( i = 1; i =M.tu; i ++) 循环次数＝tu; for(col = 2; col =M.nu; col++) 循环次数＝nu; for( p =1; p =M.tu ; p ++ ) 循环次数＝tu; 该算法的时间复杂度＝(nu*2)+(tu*2)=O(nu+tu） 讨论：最恶劣情况是tu=nu*mu(即矩阵中全部是非零元素）， 而此时的时间复杂度也只是O(mu*nu)，并未超过传统转置算法的时间复杂度。 小结： 三、 十字链表 3 0 0 5 0 -1 0 0 2 0 0 0 1 1 3 1 4 5 2 2 -1 3 1 2 ^ ^ ^ ^ ^ ^ ^ 广义表是线性表的推广，也称为列表（lists） 记为： LS = ( a1 , a2 , ……， an ) 广义表名 表头(Head） 表尾 (Tail) 1、定义： ① 第一个元素是表头，而其余元素组成的表称为表尾； ② 用小写字母表示原子类型，用大写字母表示列表。 n是表长 在广义表中约定： 讨论：广义表与线性表的区别和联系？ 广义表中元素既可以是原子类型，也可以是列表； 当每个元素都为原子且类型相同时，就是线性表。 广义表是递归定义的线性结构， LS = ( ?1, ?2, ???, ?n ) 其中：?i 或为原子 或为广义表 例如: A = ( ) F = (d, (e)) D = ((a,(b,c)), F) C = (A, D, F) B = (a, B) = (a, (a, (a, ??? , ) ) ) 广义表 LS = ( ?1, ?2, …, ?n )的结构特点: 1) 广义表中的数据元素有相对次序; 2) 广义表的长度定义为最外层包含元素个数; 3) 广义表的深度定义为所含括弧的重数; 注意:“原子”的深度为 0 ; “空表”的深度为 1 。 4) 广义表可以共享; 5) 广义表可以是一个递归的表; 递归表的深度是无穷值，长度是有限值。 6) 任何一个非空广义表 LS = ( ?1, ?2, …, ?n) 均可分解为 表头 Head(LS) = ?1 和 表尾 Tail(LS) = ( ?2, …, ?n) 两部分 例如: D = ( E, F ) = ((a, (b, c))，F ) Head【 D 】 = E Tail 【 D