云大数据结构课程教学课件第5章数组和广义表67.ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 矩阵相乘过程 两个稀疏矩阵相乘（Q＝M×N）的过程可大致描述如下：Q初始化;if （Q是非零矩阵 ）{ // 逐行求积　for (arow=1; arow=M.mu; ++arow) 　{ 　// 处理M的每一行　　ctemp[] = 0; 　　// 累加器清零　　计算 Q 中第 arow 行的积并存入 ctemp[]中；　　将 ctemp[] 中非零元压缩存储到 Q.data；　} // for arow } // if * Q初始化 对矩阵Q进行初始化的操作如下：　　Q.rows = M.rows;// Q的行数和M相同　　Q.cols = N.cols;// Q的列数和N相同　　Q.items = 0;　 // Q的非零元个数初始化为零  * 1 1 6 2 1 2 2 2 1 -2 4 2 3 1 算法5.3的动画演示 * 时间复杂度 算法5.3中，累加器ctemp初始化的时间复杂度为 O(M.rows×N.cols)，求O的所有非零元的时间复杂度为O(M.terms×N.terms/N.rows)，对Q进行压缩存储的时间复杂度为O(M.rows×N.cols)。因此总的时间复杂度为O(M.rows×N.cols+M.items×N.items/N.rows)  * 十字链表 顺序表的缺点 * 十字链表 在链表中，每个非零元可用一个含5个域的结点表示，其中i、j和e这3个域分别表示该非零元所在的行、列和非零元的值，向右域right用以链接同一行中的下一个非零元，向下域down用以链接同一列的下一个非零元。 每个非零元既是某个行链接表中的一个结点，又是某个列链接表中的一个结点，整个矩阵构成了一个十字交叉的链表，故称这样的存储结构为十字链表。 * i j e down right * 创建稀疏矩阵M的十字链表 1 1 3 3 1 2 ∧ ∧ 1 4 5 ∧ ∧ 2 2 -1 ∧ ∧ ∧ M.chead M.rhead * 时间复杂度 对于每个输入的非零元，既要插入在行链表中，又要插入在列链表中，算法5.4没有限定输入顺序，因此对每个输入的非零元都需要在相应的行链表和列链表中查询结点的插入位置。 因此算法5.4的时间复杂度为O (t×s)，其中 t为所建矩阵中非零元的个数，s为其行列的最大值。 第四节 广义表的定义 * 广义表的定义 ADT GList { 数据对象：  数据关系： } ADT GList　　 * 广义表的定义 广义表是一种“多层次”的“线性结构”，一般记作 　　　 其中,LS为广义表 的名称。N是它的长度。在线性表的定义中， 只限于是单个元素。而在广义表的定义中， 可以是单个元素，也可以是广义表，分别称为广义表LS的原子和子表。 * 广义表的定义 习惯上，用大写字母表示广义表的名称，用小写字母标示原子。当广义表LS非空时，称第一个元素 为LS的表头（Head），称其余元素组成的表 是LS的表尾（Tail）。 * 广义表的例子 ⑴A=()—A是一个空表，它的长度为零。 ⑵B=(e)—列表B只有一个原子e，B的长度为1。 ⑶C=(a,(b,c,d))—列表C的长度为2，两个元素分别为原子a和子表（b,c,d）。 ⑷D=(A,B,C)—列表D的长度为3，3个元素都是列表。显然，将子表的值代入后，则有D=((),(e),(a,(b,c,d)))。 ⑸E=(a,E)—这是一个递归的表，它的长度为2。E相当于一个无限的列表E=(a,(a,(a,…)))。 　　 * 广义表的性质 从上述定义和例子可以推出列表的3个重要结论： （1）列表的元素可以是子表，而子表的元素还可以是子表… … 由此，列表是一个多层次的结构，可以用图形象地表示。 （2）列表可以为其它列表所共享。 （3）列表可以是一个递归的表，即列表也可以是其本身的一个子表。 * 列表的图形表示 上例中列表D的图形表示 * 广义表的表头和表尾 根据前述对表头、表尾的定义可知： 任何一个非空列表其表头可能是原子，也可能是列表，而其表尾必定为列表。例如： GetHead(B)=e, GetTail(B)=(), GetHead(D)=A, GetTail(D)=(B,C), 由于(B,C)为非空列表，则可继续分解得到： GetHead((B,C))=B, GetTail((B,C))=(C) * 链式存储结构 由于广义表