清华大学与-数据结构 .ppt

递归(Recurve)的概念 迷宫(Maze)问题 递归过程与递归工作栈 广义表 (General Lists ) 递归的概念 递归的定义 若一个对象部分地包含它自己, 或用它自己给自己定义, 则称这个对象是递归的；若一个过程直接地或间接地调用自己, 则称这个过程是递归的过程。 在以下三种情况下，常常用到递归方法。 定义是递归的 数据结构是递归的 问题的解法是递归的 定义是递归的 求解阶乘 n! 的过程  在链表中寻找等于给定值的结点并打印其数值template class Type void Print ( ListNodeType *f ) { if ( f != NULL) if ( f →data == x ) cout f→data endl; else Print ( f→link );} 迷宫问题 Maze::Maze ( char *filename ) {//构造函数：从文件 filename 中读取各路口//和出口的数据 ifstream fin; fin.open ( filename, ios::in | ios::nocreate ); //为输入打开文件,文件不存在则打开失败 if ( !fin ) { cout “迷宫数据文件” filename  “打不开” endl; exit (1); } fin MazeSize; //输入迷宫路口数 递归过程与递归工作栈 递归过程在实现时，需要自己调用自己。 每一次递归调用时，需要为过程中使用的参数、局部变量等另外分配存储空间。 层层向下递归，退出时的次序正好相反： 递归次序 n! (n-1)! (n-2)! 1! 0!=1 返回次序 因此，每层递归调用需分配的空间形成递归工作记录，按后进先出的栈组织。 函数递归时的活动记录 广义表 (General Lists ) 广义表的特性 有次序性 有长度 有深度 可递归 可共享 广义表结点定义 标志域 utype, 表明结点类型。0为表头结点，1 为整型原子结点，2为字符型原子结点，3为子表结点。 值域 value。当 utype = 0 时为表引用计数，= 1时为整数值，= 2 时为字符值， = 3 时为指向子表的表头结点的指针。 尾指针域 tlink。当 utype = 0 时为指向该表表头元素的指针；当 utype ? 0 时为指向同一层下一个表结点的指针。 GenListNode *First ( ); GenListNode * Next ( GenListNode *elem ); void Push ( GenListNode x ); GenList Addon ( GenList list, GenListNode x ); void setHead ( GenListNode x ); viod setNext ( GenListNode *elem1, GenListNode *elem2 ); void setTail ( GenList list ); void Copy ( const GenList l ); int depth ( ); int Createlist ( GenListNode *ls, char * s ); } 广义表的访问算法 广义表结点类的存取成员函数 GenListNode GenListNode:: Info (GenListNode *elem ) { //提取广义表中指定表元素elem的值 GenListNode * pitem = new GenListNode; pitem→utype = elem→utype; pitem→value = elem→value; return pitem; } void GenListNode::setInfo(GenListNode *elem, GenListNode x ) { //将表元素elem中的值修改为x elem→utype = x→utype;