考试网 >> IT认证 >> 水平 >> 程序员 >> 软考指南：程序员数据结构笔记2

发布时间：2006-06-28 01:53     点击：

　递归

　　定义：问题规模为N的解依赖于小规模问题的解。问题的求解通过小规模问题的解得到。

　　包括二个步骤：

　　1） 递推 6!=>5!=>4!=>3!=>2!=>1!=>0!

　　2） 回归 720<=120<=24<=6 <=2 <=1 <=0

　　递归工作栈实现递归的机制。

　　2、有关算法：

　　1） 顺序，链表结构下的出栈，入栈

　　2） 循環，队列的入队列，出队列。

　　3） 链队列的入队列，出队列。

　　4） 表达式计算：后缀表达式 35+6/4368/+*- 

　　　　　　　　　　中缀表达式 （3+5）/6-4*（3+6/8） 

　　由于中缀比较难处理，计算机内一般先将中缀转换为后缀。

　　运算：碰到操作数，不运算，碰到操符，运算其前两个操作数。

　　　中缀=>后缀

　　5) 迷宫问题

　　6) 线性链表的递归算法 一个链表=一个结点+一个链表

　　int fuction(NODE *p) {

　　　if(p==NULL) return 0;

　　　else return(function(p->next));

　　}

　　树与二叉树

　　一、 知识点:

　　1. 树的定义: data_struct(D,R);

　　其中:D中有一个根,把D和出度去掉,可以分成M个部分.

　　D1,D2,D3,D4,D5…DM

　　R1,R2,R3,R4,R5…RM

　　而子树Ri形成树.

　　1) 递归定义 高度

　　2) 结点个数=1 

　　  

    O    --0

 

 O    O  --1

 

O  O  O  O --2

 此树的高度为2

　　2.二叉树定义:   

　　结点个数>=0 .

　　3. 术语:左右孩子,双亲,子树,度,高度等概念.

发表评论： 匿名发表 用户名: 查看评论

您将承担一切因您的行为、言论而直接或间接导致的民事或刑事法律责任 留言板管理人员有权保留或删除其管辖留言中的任意内容 本站提醒：不要进行人身攻击。谢谢配合。