程序员数据结构笔记（二）
　● 栈的存储结构:顺序,链接
　　　/ push(s,d)
　　● 栈的基本操作:
　　　\ pop(s)

　　栈定义：
　　struct {
　　　datatype data[max_num];
　

　　●队列定义
　　特点:先进先出
　　/入队列 in_queue(Q,x)
　　●队列的操作:
　　\出队列 del_queue(Q)
　　●队列存储结构:
　　链队列:
　　Typedef struct node{
　　　Datatype data;
　　　Struct node *next;
　　}NODE;
　　Typedef struct {
　　　NODE *front;
　　　NODE *rear;
　　}Queue;
　　顺序队列:
　　struct {
　　　datatype data[max_num];
　　　int front,rear;
　　};
　　问题:
　　队列ó线性表
　　假溢出<=循環队列
　　队列满，队列空条件一样<=浪费一个存储空间

　　递归
　　定义：问题规模为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
　　  
2.二叉树定义:
　　结点个数>=0 .
　　3. 术语:左右孩子,双亲,子树,度,高度等概念.
　　4. 二叉树的性质
　　●层次为I的二叉树 I层结点 2I 个
　　●高度为H的二叉树结点 2H+1-1个
　　●H(点)=E(边)+1
　　●个数为N的完全二叉树高度为|_LOG2n_|
　　●完全二叉树结点编号:从上到下,从左到右.
 
i结点的双亲: |_i/2_| |_i-1/2_|    1      
i结点的左孩子: 2i 2i+1  2    3    
i结点的右孩子: 2i+1 2i+2 4  5  6  7   
(根) 1为起点         
二叉树的存储结构:
　　　　1) 扩展成为完全二叉树,以一维数组存储。
 
     A       
  B      C    
 D      E  F   
G  H    I    
 
数组下标 0 1 2 3 4 5 6&