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

* * * * * * * * * * * * * * * 时间复杂度 对于每个输入的非零元，既要插入在行链表中，又要插入在列链表中，算法5.4没有限定输入顺序，因此对每个输入的非零元都需要在相应的行链表和列链表中查询结点的插入位置。 因此算法5.4的时间复杂度为O (t×s)，其中 t为所建矩阵中非零元的个数，s为其行列的最大值。 * A′＝A＋B * A′＝A＋B 1 1 3 1 4 5 ∧ ∧ 2 2 -1 ∧ ∧ 3 1 2 ∧ ∧ 1 1 2 ∧ 2 3 1 ∧ ∧ 3 1 -2 ∧ ∧ 5 2 3 1 ∧ ∧ ∧ ∧ * 带头结点循环链表表示行关系和列关系的十字链表 * 带头结点循环链表表示行关系和列关系的十字链表 行链表和列链表分别用带头结点的循环链表来表示 行头结点和列头结点共用一个结点 非零元素结点 所有行链表和列链表的头结点用next域链接成一个带头结点的循环链表。 2004-12-16 * 稀疏矩阵的正交链表表示的示例 第五节 递归（recurve） * 递归的概念 递归的定义 若一个对象部分地包含它自己, 或用它自己给自己定义, 则称这个对象是递归的；若一个函数直接地或间接地调用自己, 则称这个函数是递归函数。 在以下三种情况下，常常用到递归方法。 定义是递归的 数据结构是递归的 问题的解法是递归的 * 定义是递归的 求解阶乘函数的递归算法 long Factorial ( long n ) { if ( n == 0 ) return 1; else return n*Factorial (n-1); } 例如，阶乘函数 * 求解阶乘 n! 的过程 * 计算斐波那契数列的函数Fib(n)的定义  求解斐波那契数列的递归算法 long Fib ( long n ) { if ( n = 1 ) return n;  else return Fib (n-1) + Fib (n-2); } * 数据结构是递归的 有哪些信誉好的足球投注网站链表最后一个结点并打印其数值 void Find ( ListNode *f ) { if ( f →next== NULL ) printf(f →data ); else Find ( f →next); } 例如，单链表结构 2004-12-16 * 问题的解法是递归的 例如，汉诺塔(Tower of Hanoi)问题 * 递归过程与递归工作栈 当一个函数在运行期间调用另一个函数时，在运行被调用函数之前，系统需先完成以下工作： 将所有的实在参数、返回地址等信息传递给被调用函数保存； 为被调用函数的局部变量分配存储区； 将控制转移到被调用函数的入口。 从被调用函数返回调用函数之前，系统必须完成的工作： 保存被调用函数的计算结果； 释放被调用函数的数据区； 依照被调用函数保存的返回地址将控制转移到调用函数。 * 递归函数与递归工作栈 递归函数在实现时，需要自己调用自己。 每一次递归调用时，需要为函数中使用的参数、局部变量等另外分配存储空间。 层层向下递归，退出时的次序正好相反： 递归次序 n! (n-1)! (n-2)! 1! 0!=1 返回次序 因此，每层递归调用需分配的空间形成递归工作记录，按后进先出的栈组织。 2004-12-16 * 函数递归时的活动记录 * long Factorial ( long n ) { int temp; if ( n == 0 ) return 1; else temp = n * Factorial (n-1); RetLoc2 return temp; } void main ( ) { int n; n = Factorial (4); RetLoc1 } 2004-12-16 * 计算Factorial时活动记录的内容 第六节 广义表的定义 * 广义表 (General Lists ) 广义表的概念 n ( ? 0 )个表元素组成的有限序列，记作 LS = (a0, a1, a2, …, an-1) LS是表名，ai是表元素，它可以是表(称为子表)，可以是数据元素(称为