if (v1!=v2)    //v1=v2表示这条边的两端在同一个集合中
     { printf(“(%d,%d)”,ge[i].bv, ge[i].tv);
       set[v1]=v2; j++;
     }
   i++;
 }
}  //该算法可以自己拿个简单的例子走一遍
(１) 两种算法的比较：Prim算法时间复杂度O(n**2),与边数无关，适合边稠密的图
                   Kruskal算法时间复杂度O(eloge) 适合求顶点稠密的图
(２) 最小生成树不唯一，用不同的算法得出的最小生成树不同
6关节点，重连通图（要求会判断是否是重连通图）
关节点的特性：若生成树根结点有两个子树，其比是关节点
若一棵子树的所有子孙没有指向其祖先的回边
8. 最短路径会手工求就行
9. 拓扑排序会手工排就行
（利用深度优先遍历退栈的逆序列  P183）
若求不出一个图的拓扑排序，则说明该图有回路。
10. 关键路径（会手工做，会求事件和活动的最早最晚时间）
11. Aov:用顶点表示活动，弧表示活动间的优先关系的有向图，趁为顶点表示活动的网
AoE: 顶点表示事件，边表示活动
DaG: 有向无环图，都能进行拓扑排序
  第九章：查找
１. 顺序查找：既可查顺序表也可查线性表（设监视哨）
２. 分析平均查找长度  AsL=∑Pi*Ci (求和下限i=1, 上限n)
Pi 为查找表中第 i个记录的概率  Ci=n-i+1
在等概率的情况下 Pi=1/n  ASL=(n+1)/2
在不等概率的情况下要根据公式分别求出概率Pi和Ci;
３. 有序查找表—折半查找
有序顺序表才可用折半查找，折半查找的判定树一定要会。
表长确定，平均查找长度确定，判定树的拓扑结构确定
n个结点的判定树深度为 +1。
折半查找法在查找过程中进行的比较次数最多不超过其判定树的深度。
设表长为n=(2**h) –1 ,查找成功的概率相等，不成功的概率为0，采用二分法查找，问ASL是多少？判定树是深度为h的满二叉树。
  ASL=1/n(1*2**(1-1)+2*2**(2-1)+3*2**(3-1)….+h*2**(h-1))
  令S=1/n(1*2**0+2*2**1+3*2**2+….+h*2**(h-1))
    S=2S-S=1/n[h*2**h-(2**0+2**1+….2**(h-1))  //其中小括号正好为深度为h的满二叉树的总结点数。
     =1/n[h*2**h-2**h +1]=1/n[(h-1)*2**h+1]=1/n[(log2(n+1)-1)*(n-1)+1]
     =1/n[(n+1)log2(n+1)-n]=(n+1)/nlog2(n+1)-1
 //熟悉上述的推导方法
４. 分块查找
(１) 适用条件：分块有序表
分块查找方法的评价 P226
都采用顺序查找，在等概率的情况下分几块平均查找长度最小(参看教材)
５. 设有关键字为k1….kn,查找成功的概率为2**-1, 2**-2 ….2**-n，查找不成功的概率为2**-n,  (1)若从左向右顺序查找，ASL是多少？
(2)从右向左顺序查找，ASL是多少？
（3总的ASL是多少？
 解：（1）ASL=(∑i*2**-I)+(n+2**-n) // 其中求和的下限是i=1,上限是n。第一部分是查找成功的ASL，第二部分是查找不成功的ASL
=1*（2**-1）+2*（2**-2）+….+n*(2**-n)+n*(2**-n)
令 S=1* (2**-1)+….+n*(2**-n)
   S=2S-S=1+(2**-1)+(2**-2)+……+(2**-(n-1))-n*(2**-n)
    =2-(2**-(n-1))-n*(2**-n)
则 ASL=S+n*(2**-n)=2-(2**-(n-1))    时间复杂度为O(1),当n趋向0时ASL=2
(2)ASL=(∑(n+1-i)*(2**-i) + (n*(2**-n))) 其中求和的下限是i=1,上限是n
          =n*(2**-1)+(n-1)*(2**-2)+….+(2**-n)+n*(2**-n)
令S=n*(2**-1)+….(2**-n)
  S=2S-S=n-(1-(2**-n))
  则ASL=n+(n+1)*(2**-n)-1       最坏的情况下时间复杂度为O(n)
(3)总的ASL取最小值　　ASL=2-(2**-(n-1))
６. 动态查找是重点
７. 二叉排序树中的插入和删除要会
删除一个结点后，二叉树的中序遍历仍是递增
　　　　　会求二叉排序树查找的平均ASL(要分清查找成功的结点和查找失败结点的(外结点)的ASL)
８. 设有关键字n=(2**h)，查找成功的概率相等，构成二叉排序树，ASL最大多少？最大树高是多少？
解：高为n时，ASL最大(1=2=3+…+n)/n=(n+1)/2
深度为h的满二叉树时，ASL最小：((n+1)/n)*log2(n+1)-1
９. 设有1023个关键字的二叉排序树，查找成功的概率相等，使ASL最小时树高是多少？
根据第８题的公式((n+1)/n)*log2(n+1)-1＝(1024/1023)log2(1024)- 1=10240/1023-1
所以树高h=10
１０. 掌握如何构造平衡二叉树（多做几次练习，参看光盘的数据结构课件）
如何选旋转轴？选离插入点最近的不平衡点的儿子结点
１１. 具有n个叶子结点的非满二叉树的完全二叉树深度为（ +1）
具有n个叶子结点的满二叉树的深度为（log2(n) + 1 ）
具有n个结点的完全二叉树的深度（ +1）
具有n个结点的折半查找判定树的深度为（ +1）
１２. 含n个关键字的平衡二叉树的最大深度为？
n=0　　　　　n=1      n=2        n=4       n=7
           空树
　　　　最大深 ０         1       2           3         4
反过来，深度为h的二叉平衡树中所含结点的最小值多少？
　　　　　h=0, N0=0; h=1,N1=1; h=2,N2=2; h=3,N3=4
          一般情况：　Nh=N(h-1)+N(h-2)+1
          利用归纳法证得：Nh=F(h+2)-1　　　 P书238
          当平衡二叉树含20个结点，高度最高是多少？
        N4=2+4+1=7,  N5=4+7+1=12, N6=7+12+1=20
           所以h=6
１３. B树： 定义，查找过程，插入，删除必须掌握（多做点相关的题目）
       　　高度为k的2-3树的结点数至少是： 二叉排序树 (2**k )– 1
           最多有多少个结点：每个结点含两个关键字最多有：∑3**(i-1)=[(3**k)-1]/2 求和下限是i=1,上限是k
           高为h的m阶B-树的结点数至少是：t=
                层    结点
1 1
2 2
3 2t     所有结点相加=1+2*∑(t**i) 求和下限i=0,上限为k-2                                                  
4 2*(t**2)            =1+2*[(t**(h-1)-1)/(t-1)]
..       ..
h       2*(t**(h-2))
           高为h的m阶B-树的结点数最多有多少：
                层     结点
1 1
2 m      结点相加=∑(m**i)   求和下限i=0,上限为k-1 
3 m**2           =[(m**k)-1]/(m-1)
..        ..
n        m**(n-1)
１４. 高度为h的m阶B树的关键字数最多是( (m**h)-1)，至少是(2*[t**(h-1)]-1)，其中t= 
分析：最少，(m-1)* ∑[m**(i-1)]   求和下限i=1,上限为h
           =(m-1)*[(m**h) –1]/(m-1)
           =(m**h)-1
      最多，1+2(t-1) ∑[m**(i-2)]  求和下限i=2,上限为h
           =1+2(t-1)*[t**(h-1) –1]/(t-1)
           =2*[t**(h-1)]-1
１５. N个结点的m阶B-树至少含(( -1)*(n-1)+1)个关键字 //注意好好听老师的讲解，了解式中的每项是怎么得来的
１６. B树中的空指针数总比关键字数多1