精品计算机课件《C语言数据结构》第章数组和广义表.pptVIP

2007年百度笔试题（以宿舍为单位征解，周四课后交流） 5.1 数组的定义 二维数组的特点： N维数组的数据类型定义 5.2 数组的顺序存储表示和实现 补充：计算二维数组元素地址的通式设一般的二维数组是A[c1..d1, c2..d2]，这里c1,c2不一定是0或1 例3：已知二维数组Am,m按行存储的元素地址公式是： Loc(aij)= Loc(a11)+[(i-1)*m+(j-1)]*K , 请问按列存储的公式相同吗？ 答：尽管是方阵，但公式仍不同。应为： Loc(aij)=Loc(a11)+[(j-1)*m+(i-1)]*K 若是N维数组，其中任一元素的地址该如何计算？ Loc(j1,j2,…jn)=LOC(0,0,…0)＋ N维数组的顺序存储表示（见教材P93） 5.3 矩阵的压缩存储 一、稀疏矩阵的压缩存储 例1 ： 三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的 、 和 。 法2：用十字链表表示 法4：用带辅助向量的三元组表示。 方法： 增加2个辅助向量： ① 记录每行非0元素个数，用NUM（i）表示； ② 记录稀疏矩阵中每行第一个非0元素在三元组中的行号，用POS（i）表示。 二、稀疏矩阵的操作 方法1：压缩转置 今日课后，各班推选一个寝室进行编程PK赛 5.3 矩阵的压缩存储 法4：用带辅助向量的三元组表示。 方法： 增加2个辅助向量： ① 记录每行非0元素个数，用NUM（i）表示； ② 记录稀疏矩阵中每行第一个非0元素在压缩后的三元组中的行号，用POS（i）表示。 二、稀疏矩阵的操作 方法1：压缩转置 方法2 快速转置 设计思路： 令：M矩阵中的列变量用col表示； num[ col ]：存放M中第col 列中非0元素个数 cpos[ col ]：存放M中第col列的第一个非0元素的位置 （即b.data中待计算的“恰当”位置所需参考点） 第5章 数组和广义表（Arrays Lists） 5.4 广义表的定义 2、特点： 有次序性 有长度 有深度 可递归 可共享 介绍两种特殊的基本操作： 5.5 广义表的存储结构 本章小结 7 6 5 3 1 2 1 1 2 0 2 NUM( i) 6 5 4 3 POS( i ) 2 1 i 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 -7 4 6 15 1 6 18 2 5 24 3 4 14 5 3 -3 1 3 9 3 1 12 2 1 8 6 6 v j i 8 7 6 5 4 3 2 1 0 3 用途：便于高效访问稀疏矩阵中任一非零元素。 POS(i)如何计算？ POS(1)＝1 POS(i)＝POS(i-1)+NUM(i-1) 用途后述 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 0 0 –3 0 0 15 12 0 0 0 18 0 9 0 0 24 0 0 0 0 0 0 0 -7 0 0 14 0 0 0 0 0 0 0 0 0 (6, 4, -7) (6, 1, 15) (5, 2, 18) (4, 3, 24) (3, 5, 14) (3, 1, -3) (1, 3, 9 ) (1, 2, 12) (5, 3, 14) (4, 6, -7) (3, 4, 24) (3, 1, 9) (2, 5, 18) (2, 1, 12) (1, 6, 15) (1, 3, -3) 已知 三 元 组 表 a.data 求 三 元 组 表 b.data 转置后