树

1.树的有关定义和术语

1.术语
1.树（tree):
树是n(n≥0)个结点的有限集T,
当n=0时，T为空树；
当n>0时,
(1)有且仅有一个称为T的根的结点,
(2)当n>1时,余下的结点分为m(m>0)个互不相交的有限集,,…, ,每个Ti(1≤i≤m)也是一棵树,且称为根的子树。
这个定义是递归的,是一层套一层的

2.结点的度(degree):
结点的子树数目
3.树的度:
树中各结点的度的最大值
4.n度树: 度为n的树
//注意这里度和图的度之间的区别
//2度树一定是二叉树,二叉树不一定是二度树
5.叶子(终端结点): 度为0的结点
6.分枝结点(非终端结点,非叶子):
度不为0的结点
7.双亲(父母,parent)和孩子(儿子,child) :
若结点C是结点P的子树的根,称P是C的双亲，C是P的孩子。
8.结点的层(level):
规定树T的根的层为1，其余任一结点的层等于其双亲的层加1。
9.树的深度(depth,高度):
树中各结点的层的最大值。
10.兄弟(sibling):
同一双亲的结点之间互为兄弟。
11.堂兄弟:
同一层号的结点互为堂兄弟。
12.祖先: 从树的根到某结点所经分枝上的所有结点为该结点的祖先。
13.子孙: 一个结点的所有子树的结点为该结点的子孙。
14.有序树:若任一结点的各棵子树，规定从左至右是有次序的,即不能互换位置,则称该树为有序树。 二叉树一般是有序的
15.无序树: 若任一结点的各棵子树，规定从左至右是无次序的,即能互换位置,则称该树为无序树。普通的树一般是无序的
16.森林: m(m≥0)棵互不相交的树的集合。

2.其他表现形式
1.广义表表现形式

2.Venn图嵌套集合
3.书目表

2.二叉树

1.二叉树的递归定义
二叉树是有限个结点的集合，它或者为空集；或者是由一个根结点和两棵互不相交的，且分别称为根的左子树和右子树的二叉树所组成。

2、二叉树的一些性质
(1)二叉树的第层最多有个结点,
(2)深度为k的二叉树最多有个结点
//这个性质可以由等比数列的前n项和推出来
(3)叶子的数目=度为2的结点数目+1
(4)满二叉树:深度为k,且结点数目为的二叉树,这个时候满二叉树的深度为
对于满二叉树的每一个结点,有以下性质

5.完全二叉树（full binary tree):
深度为k的有n个结点的二叉树,当且仅当每一个结点都与同深度的满二叉树中编号从1至n的结点一一对应,称之为完全二叉树

6.二叉树的存储结构
(1)、对于完全二叉树,我们会使用数组来处理
//不是完全二叉树的话,内存就不能充分的利用,尽量不要选择,如果不得不选择就在缺失的位置补上不存在的标志

(2)、链表(二叉和三叉的)

三叉链表:多了一个指向父亲结点的指针

(3)、静态链表
就是用一个结构体数组,存入数据,左边的结构序号和右边的结构序号

3.二叉树的遍历

1.遍历顺序
前序:根结点-左-右
中序:左-根结点-右
后序:左-右-根结点
层序遍历:一层一层地遍历

2.递归算法实现

void InorderTraversal( BinTree BT )
{
    if( BT ) {
        InorderTraversal( BT->Left );
        /* 此处假设对BT结点的访问就是打印数据 */
        printf("%d ", BT->Data); /* 假设数据为整型 */
        InorderTraversal( BT->Right );
    }
}

void PreorderTraversal( BinTree BT )
{
    if( BT ) {
        printf("%d ", BT->Data );
        PreorderTraversal( BT->Left );
        PreorderTraversal( BT->Right );
    }
}

void PostorderTraversal( BinTree BT )
{
    if( BT ) {
        PostorderTraversal( BT->Left );
        PostorderTraversal( BT->Right );
        printf("%d ", BT->Data);
    }
}

void LevelorderTraversal ( BinTree BT )
{ 
    Queue Q; 
    BinTree T;

    if ( !BT ) return; /* 若是空树则直接返回 */
    
    Q = CreatQueue(); /* 创建空队列Q */
    AddQ( Q, BT );
    while ( !IsEmpty(Q) ) {
        T = DeleteQ( Q );
        printf("%d ", T->Data); /* 访问取出队列的结点 */
        if ( T->Left )   AddQ( Q, T->Left );
        if ( T->Right )  AddQ( Q, T->Right );
    }
}
//source:ZJU

3.中序遍历的非递归实现

void Midorder(struct BiTNode *t)      //t为根指针 
{ struct BiTNode *st[maxleng];//定义指针栈
  int top=0；                  //置空栈
  
do{            
    
    while(t)               //根指针t表示的为非空二叉树 
    
       { if (top==maxleng) exit(OVERFLOW)；//栈已满,退出
                     
         st[top++]=t；             //根指针进栈
      
         t=t->lchild；             //t移向左子树
     
       }   //循环结束表示以栈顶元素的指向为
         
           //根结点的二叉树的左子树遍历结束
    
    if (top)                    //为非空栈   
    
       { t=st[--top]；             //弹出根指针
                                printf("%c",t->data)；    //访问根结点
      
         t=t->rchild；             //遍历右子树
     
       }
   
   } while(top||t)； //父结点未访问，或右子树未遍历
 }
source:HUST

思路就是先找到最左的结点,把经过的根结点都保存了,后来左子树遍历完了就找上面根结点的右子树,再把右子树看成个树遍历,遍历完了就返回上一级(退栈),相当于更大的左子树访问完了

4.先序遍历的非递归实现

一样的,只不过不同的是,这里入栈就输出

5.后序遍历的非递归实现

注意,由于后序遍历需要遍历一遍左子树,在遍历一遍右子树,所以说保存根结点是十分必要的,所以说这里退栈就不会真退,仅仅是访问而已,如果右子树能能和之前访问过的结点匹配的话,就说明已经回到了根结点了!

核心：一个结点需要弹出两次,第一次弹出的时候还需要放回原位（左子树遍历完毕）,第二次弹出的时候才输出其值（右子树遍历完毕）；
Status PostOrder2(BTree *BT) {
     Stack s,s2;
     BTree *T;
     int flag[MaxSize]; 
     s.top=0;
     T=BT;
     while(s.top!=0||T){
         while(T)
         {
             s.data[s.top++]=T;
             flag[s.top-1]=0;
             T=T->lchild;
          } 
          while(s.top!=0&&flag[s.top-1]==1){
              T=s.data[--s.top];
              printf("%3d",T->data);
          }
          if(s.top!=0){
              flag[s.top-1]=1;
              T=s.data[s.top-1];
              T=T->rchild;
          }
          else   break;
     }
     return OK;
source:博客园

     这里规定了访问次数这个量,被访问了两次就是要输出了
while (p != nullptr || !s.empty()) {
         // 入栈
         if (p != nullptr) {
             s.push(p);
             p = p->left;
         }
 
         // 出栈
         if (p == nullptr) {
             p = s.top();
             s.pop();
 
             p->times++;
 
             //遍历右子树
             if (p->times == 1) {
                 s.push(p);
                 p = p->right;
             }
 
             //p.times==2; 继续弹栈
             else {
                 cout << p->data;
                 p = nullptr;   // 回溯的关键步骤
             }
         }
     }

6.输入一组先序序列,构建二叉树

BiTree CreatBiTree2()
 
{ char ch;  BiTree root;  //二叉链表根结点指针
              scanf(“%c”,&ch);      //输入一个结点
   
if (ch =='  ')
     root=NULL;
   
else {
     
root=(BiTree) malloc(leng);  //生成根结点          
     
root->data=ch;
     
root->lchild=CreatBiTree2(); //递归构造左子树 
     
root->rchild=CreatBiTree2(); //递归构造右子树
       
}
  return root;
 
}

当然,传指针传引用都是可以的

7.线索二叉树
二叉树一共有2n个指针域,占用了n-1和,剩下n+1个就会被利用

中序和后序都是一样的

当然了,带个头指针在指向二叉树本身的操作也是被允许的

8.表达式二叉树

9.中序+前序&后序表达式唯一确定二叉树zhon

3.树和森林

1.数组(双亲表示法) 数组里面存的是结构体,结构体两个元素,存数据和双亲

2.孩子表示法(链表)

3.孩子链表表示法
链Hash(bushi)

4.带双亲的孩子链表表示法:每一个结构体加一个双亲

5.树与二叉树的转换

树的遍历:
前根遍历:根——第一个儿子——……
后跟遍历:第一个儿子——第二个儿子——……——根

4.Huffman树

1.路径长度—-路径上分枝的数目(连线的数目)
2.树T的路径长度—-从树T的根到其余每个结点的路径长度之和,记作PL(T)
当n个结点的二叉树为完全二叉树时,PL(T)具有最小值:

当n个结点的二叉树为单枝树时,PL(T)具有最大值：
PL(T) = 1+2+…+(n-1) = n(n-1)/2
树T的带权路径长度—-每个叶子的权与根到该叶子的路径长度的乘积之和，记作WPL(T)=

 n:叶子数 w_k叶子k的权 l_k路径长度

构建的方式用代码实现:
其实树可以表示成父母孩子表示法,每次合并的时候就找最小的两个数,标记已合并,构建新结点,新结点是没合并过的

Huffman编码的构建:就从自己开始找反序列,在调转即可

图

1.图的定义和术语

1.图
图G由顶点集V和关系集E组成,记为:G=(V,E),V是顶点(元素)的有穷非空集，E是两个顶点之间的关系的集合。
若图G任意两顶点a,b之间的关系为有序对,∈E, 则称为从a到b的一条弧/有向边；其中： a是的弧尾，b是的弧头；称该图G是有向图。
若图G的任意两顶点a,b之间的关系为无序对(a,b), 则称(a,b)为无向边(边）,称该图G是无向图。 无向图可简称为图。
2.完全图
3.网:带权的图
4.子图:对图 G=(V,E)和G’=(V’,E’)，
若V’V 且 E’E，则称G’是G的一个子图
5.度:与顶点x相关联的边(x,y)的数目,称为x的度，记作TD(x) 或D(x)
以顶点x为弧尾的弧的数目,称为x的出度，记作OD(x)。
以顶点x为弧头的弧的数目,称为x的入度，记作ID(x)。
6.图的连通性质
对无向图G：
● 若从顶点vi到vj有路径,则称vi和vj是连通的。
● 若图G中任意两顶点是连通的,则称G是连通图。
● 若图G’是G的一个极大连通子图,则称G’是G的一个连通分量。(连通图的连通分量是自身)
对有向图G
● 若在图G中,每对顶点vi和vj之间, 从vi到vj,且从 vj到vi都存在路径,则称G是强连通图。
● 若图G’是G的一个极大强连通子图,则称G’是G的一个强连通分量。(强连通图的强连通分量是自身)
●设G=(V,E),G’=(V’,E’),V=V’,若G是连通图,G’是G的一个极小连通子图, 则G’是G的一棵生成树。
● 若有向图G有且仅有一个顶点的入度为0，其余顶点的入度
为1,则G是一棵有向树。

2.图的存储形式

1.数组表示法/邻接矩阵
顶点数组—用一维数组存储顶点(元素)
邻接矩阵—用二维数组存储顶点(元素)之间的关系(边或弧)
无向图的邻接矩阵是对称的由0-1构成

对于网来说道理亦同

2.邻接表:
无向图:把与头结点相连的所有元素都存进对应的链表里
有向图的邻接表:它指向的元素存进链表
有向图的逆邻接表:指向它的元素存进链表

如果把图改成了网,那就把每个指向的结点加上一个权重空间

3.有向图的十字链表
其实也很简单,每一个边结点加上弧尾和弧头,第一个指针下一个弧头一样的结点,第二个指针指向下一个弧尾一样结点
点结点就是两个指针:第一个指针指向第一个弧头为该结点的边结点;第二个指针就指向第一个弧尾为该结点的边结点

4.邻接多重表
点结点:就是data和第一个含有这个顶点的边
边结点,mark—-标志域，可用以标记该条边是否被搜索过；
vi和vj—-该条边依附的两个顶点在图中的位置；
vilink—-指向下一条依附于顶点vi的边；
vjlink—-指向下一条依附于顶点vj的边。

3.图的遍历

1.深度优先搜索:一直往下走,如果没有没被搜索到的结点,就搜索上一个被搜索的结点(Stack)

2.广度优先搜索:无论如何先把该结点的每个儿子先遍历了(队列)

4.最小生成树

1.DFS和BFS的生成树

生成森林:对图的每个联通分枝进行生成树搜索

5.网的最小生成树:
在网G的各生成树中，其中各边的权之和最小的生成树称为G的最小生成树
MST性质：设G=（V，E）是一个连通图，通过某种算法构造其最小生成树,T=（U，TE）是正在构造的最小生成树。如果边（u,v)是G中所有一端在U中（即u∈U）而另一端在V-U中（即v∈V-U）具有最小值的一条边，则必存在一棵包含边（u,v)的最小生成树。

6.Prim算法:
对n个顶点的连通网，初始时， T=（U，TE），U为一个开始顶点，TE=φ，以后根据MST性质，每次增加一个顶点和一条边，重复n-1次。Ｕ不断增大，Ｖ－Ｕ不断减小直到为空。

/* 邻接矩阵存储 - Prim最小生成树算法 */

Vertex FindMinDist( MGraph Graph, WeightType dist[] )
{ /* 返回未被收录顶点中dist最小者 */
    Vertex MinV, V;
    WeightType MinDist = INFINITY;

    for (V=0; V<Graph->Nv; V++) {
        if ( dist[V]!=0 && dist[V]<MinDist) {
            /* 若V未被收录，且dist[V]更小 */
            MinDist = dist[V]; /* 更新最小距离 */
            MinV = V; /* 更新对应顶点 */
        }
    }
    if (MinDist < INFINITY) /* 若找到最小dist */
        return MinV; /* 返回对应的顶点下标 */
    else return ERROR;  /* 若这样的顶点不存在，返回-1作为标记 */
}

int Prim( MGraph Graph, LGraph MST )
{ /* 将最小生成树保存为邻接表存储的图MST，返回最小权重和 */
    WeightType dist[MaxVertexNum], TotalWeight;
    Vertex parent[MaxVertexNum], V, W;
    int VCount;
    Edge E;
    
    /* 初始化。默认初始点下标是0 */
       for (V=0; V<Graph->Nv; V++) {
        /* 这里假设若V到W没有直接的边，则Graph->G[V][W]定义为INFINITY */
           dist[V] = Graph->G[0][V];
           parent[V] = 0; /* 暂且定义所有顶点的父结点都是初始点0 */ 
    }
    TotalWeight = 0; /* 初始化权重和     */
    VCount = 0;      /* 初始化收录的顶点数 */
    /* 创建包含所有顶点但没有边的图。注意用邻接表版本 */
    MST = CreateGraph(Graph->Nv);
    E = (Edge)malloc( sizeof(struct ENode) ); /* 建立空的边结点 */
           
    /* 将初始点0收录进MST */
    dist[0] = 0;
    VCount ++;
    parent[0] = -1; /* 当前树根是0 */

    while (1) {
        V = FindMinDist( Graph, dist );
        /* V = 未被收录顶点中dist最小者 */
        if ( V==ERROR ) /* 若这样的V不存在 */
            break;   /* 算法结束 */
            
        /* 将V及相应的边<parent[V], V>收录进MST */
        E->V1 = parent[V];
        E->V2 = V;
        E->Weight = dist[V];
        InsertEdge( MST, E );
        TotalWeight += dist[V];
        dist[V] = 0;
        VCount++;
        
        for( W=0; W<Graph->Nv; W++ ) /* 对图中的每个顶点W */
            if ( dist[W]!=0 && Graph->G[V][W]<INFINITY ) {
            /* 若W是V的邻接点并且未被收录 */
                if ( Graph->G[V][W] < dist[W] ) {
                /* 若收录V使得dist[W]变小 */
                    dist[W] = Graph->G[V][W]; /* 更新dist[W] */
                    parent[W] = V; /* 更新树 */
                }
            }
    } /* while结束*/
    if ( VCount < Graph->Nv ) /* MST中收的顶点不到|V|个 */
       TotalWeight = ERROR;
    return TotalWeight;   /* 算法执行完毕，返回最小权重和或错误标记 */
}

2.克鲁斯卡尔:
需要将边按递增次序排列以供选择。选择权重最小的边,然后保证没有环
怎么保证没有环?度!

4.有向无环图应用

一个无环的有向图称为有向无环图（directed acycline graph), 简称DAG图。

1.拓扑排序:
AOV网（Activity On Vertex network:以顶点表示活动，弧表示活动之间的优先关系的DAG图。

拓扑排序算法思想：重复下列操作，直到所有顶点输出完。
（1）在有向图中选一个没有前驱的顶点输出(选择入度为0的顶点)；
（2）从图中删除该顶点和所有以它为尾的弧(修改其它顶点入度) 。

2.AOE网
AOE网研究的问题：
（1） 完成整项工程至少需要多少时间；
（2） 哪些活动是影响工程进度的关键。

1.(顶点）事件vi的最早发生时间ve(vi)：从开始点到vi的最长路径长度。（ve(v1)=0）,既表示事件vi的最早发生时间，也表示所有以vi为尾的弧所表示的活动ak的最早发生时间e(k)。
如果结点只有一个前驱结点:那就是前驱结点ve+到这个结点的边
有多个前驱结点:前驱结点ve+到这的边求最大值
2.活动最早开始时间ee(e)=所连接的弧尾的标记值
3.(顶点）事件vi允许的最迟开始时间vl(vi) = 完成点（汇点）vn的的最早发生时间ve(vn)减去vk到vn的最长路径长度。
如果有多个后继结点,对每个结点的值求最小即可
4.确定了顶点vi的最迟开始时间后，确定所有以vi为弧头的活动ak的最迟开始时间l(k)：表示在不推迟整个工程完成的前提下，活动ak最迟必须开始的时间。
l(ak)=vl(ak弧头对应顶点)-活动ak的持续时间

5 最短路径

算法1（Dijkstra算法）：
以每一个顶点为源点，重复执行Dijkstra算法n次，即可求出每一对顶点之间的最短路径。

/* 邻接矩阵存储 - 有权图的单源最短路算法 */

Vertex FindMinDist( MGraph Graph, int dist[], int collected[] )
{ /* 返回未被收录顶点中dist最小者 */
    Vertex MinV, V;
    int MinDist = INFINITY;

    for (V=0; V<Graph->Nv; V++) {
        if ( collected[V]==false && dist[V]<MinDist) {
            /* 若V未被收录，且dist[V]更小 */
            MinDist = dist[V]; /* 更新最小距离 */
            MinV = V; /* 更新对应顶点 */
        }
    }
    if (MinDist < INFINITY) /* 若找到最小dist */
        return MinV; /* 返回对应的顶点下标 */
    else return ERROR;  /* 若这样的顶点不存在，返回错误标记 */
}

bool Dijkstra( MGraph Graph, int dist[], int path[], Vertex S )
{
    int collected[MaxVertexNum];
    Vertex V, W;

    /* 初始化：此处默认邻接矩阵中不存在的边用INFINITY表示 */
    for ( V=0; V<Graph->Nv; V++ ) {
        dist[V] = Graph->G[S][V];
        if ( dist[V]<INFINITY )
            path[V] = S;
        else
            path[V] = -1;
        collected[V] = false;
    }
    /* 先将起点收入集合 */
    dist[S] = 0;
    collected[S] = true;

    while (1) {
        /* V = 未被收录顶点中dist最小者 */
        V = FindMinDist( Graph, dist, collected );
        if ( V==ERROR ) /* 若这样的V不存在 */
            break;      /* 算法结束 */
        collected[V] = true;  /* 收录V */
        for( W=0; W<Graph->Nv; W++ ) /* 对图中的每个顶点W */
            /* 若W是V的邻接点并且未被收录 */
            if ( collected[W]==false && Graph->G[V][W]<INFINITY ) {
                if ( Graph->G[V][W]<0 ) /* 若有负边 */
                    return false; /* 不能正确解决，返回错误标记 */
                /* 若收录V使得dist[W]变小 */
                if ( dist[V]+Graph->G[V][W] < dist[W] ) {
                    dist[W] = dist[V]+Graph->G[V][W]; /* 更新dist[W] */
                    path[W] = V; /* 更新S到W的路径 */
                }
            }
    } /* while结束*/
    return true; /* 算法执行完毕，返回正确标记 */
}
Source:ZJU

算法2（Floyd算法）：
算法思想：
假设求Vi到Vj的最短路径，如果从Vi到Vj有弧，则存在一条长度为arcs[i][j]的路径，该路径不一定是最短路径，尚需进行n次试探。

首先考虑(Vi,V0,Vj)是否存在（即判断(Vi,V0)和( V0,Vj)是否存在)，如果存在，比较(Vi, Vj)和(Vi,V0)+( V0,Vj)，取长度较短的为从Vi到Vj的中间顶点序号不大于0的最短路径。

再考虑路径上再增加一个顶点V1，如果考虑(Vi,…V1)和(V1,….Vj)， (Vi,…V1)和(V1,….Vj)都是中间顶点序号不大于0的最短路径。 (Vi,…V1，….Vj)可能是从Vi到Vj的中间顶点序号不大于1的最短路径。
比较Vi到Vj的中间顶点序号不大于0的最短路径和(Vi,…V1)+(V1,….Vj)，取长度较短的为从Vi到Vj的中间顶点序号不大于1的最短路径。

bool Floyd( MGraph Graph, WeightType D[][MaxVertexNum], Vertex path[][MaxVertexNum] )
{
    Vertex i, j, k;

    /* 初始化 */
    for ( i=0; i<Graph->Nv; i++ )
        for( j=0; j<Graph->Nv; j++ ) {
            D[i][j] = Graph->G[i][j];
            path[i][j] = -1;
        }

    for( k=0; k<Graph->Nv; k++ )
        for( i=0; i<Graph->Nv; i++ )
            for( j=0; j<Graph->Nv; j++ )
                if( D[i][k] + D[k][j] < D[i][j] ) {
                    D[i][j] = D[i][k] + D[k][j];
                    if ( i==j && D[i][j]<0 ) /* 若发现负值圈 */
                        return false; /* 不能正确解决，返回错误标记 */
                    path[i][j] = k;/*记录I和j之间的中间结点*/
                }
    return true; /* 算法执行完毕，返回正确标记 */
}

查找

查找表: 由同一类型的数据元素（记录）组成的集合。
记作：ST={a1,a2,…,an}
● 关键字: 可以标识一个记录的数据项
● 主关键字: 可以唯一地标识一个记录的数据项
● 次关键字: 可以识别若干记录的数据项

查找—-根据给定的某个关键字值，在查找表中确定一个其关键字等于给定值的记录或数据元素。
设k为给定的一个关键字值，R[1..n]为n个记录的表,若存在R[i].key=k,1≤i≤n,称查找成功；否则称查找失败。

静态查找: 查询某个特定的元素，检查某个特定的数据元素的属性,不插入新元素或删除元素(记录) 。
动态查找: 在查找过程中，同时插入查找表中不存在的数据元素(记录)。

1 顺序查找

typedef struct node
{ keytype key ； //关键字类型
char name[6]； //姓名
…… //其它
} ElemType；
typedef struct
{
ElemType elem[maxsize+1]；//maxsize+1个记录,
//elem[0]为监视哨
int length;
} SSTable;
SSTable ST1,ST2;

不使用监视哨的判断语句:i>=1 && k!=ST.elem[i].key
监视哨:将数组第0个元素设置为要查找的元素
含有监视哨的查找表是肯定能找到的,如果在0找到就是没找到,就符合相等的直接返回下标即可

查找算法的性能分析:

● 考虑查找失败: 使用监视哨elem[0],为 n+1
不使用监视哨elem[0],为 n

假定查找成功和失败的机会相同，对每个记录的查找概率相等， Pi=1/(2*n), 则 ASL=3(n+1)/4

2 二分查找

int binsrch(SSTable  ST,keytype k)
{ 
    int low,mid,hig；
  
  low=1；
  
  hig=ST.length；
  
    while (low<=hig)
  
    {  mid=(low+hig)/2；     //计算中间记录的地址 
     
       if (k<ST.elem[mid].key) 
          
           hig=mid-1；       //查左子表 
     
       else if (k==ST.elem[mid].key) 
          
           return mid；           //查找成功,退出循环
     
       else low=mid+1；  //查右子表
   ｝
    return 0;

小了,往小了猜,大了,往大了猜

判定树

插入方法:右子树最右,左子树最右,递归排序
ASL计算:每一个结点所在的层数求和/总的结点个数
满二叉树:公式:

3 索引顺序表

● 条件
(1)分块表”按块有序”, 索引表”按key有序”
(2)设n个记录分为b个块，每块的记录数s=n/b
● 查找方法
(1)顺序查找(或折半查找)索引表
确定k值所在的块号或块的首地址
(2)在某一块中顺序查找
● 最佳分块
s=√n b=√n

4 二叉排序树

(1) 二叉排序树的定义
如果二叉树的任一结点大于其非空左子树的所有结点，而小于其非空右子树的所有结点，则这棵二叉树称为二叉排序树。对一棵二叉排序树进行中序遍历，所得的结点序列一定是递增有序的。

ASL计算:同查找树
存储结构:跟二叉树一样

查找算法:大的往右,小的往左,找到了返回,遇到NULL就失败

插入算法:

删除算法:在二叉排序树中删除一个结点时，必须将因删除结点而断开的二叉链表重新链接起来，同时确保二叉排序树的性质不会失去。
为保证在删除节点后二叉排序树的性质不会丢失:
1、删除叶结点，只需将其双亲结点指向它的指针置空，再释放它即可。
2、被删结点缺左子树（或右子树），可以用被删节点的右子树（或左子树）顶替它的位置，再释放它。
3、被删结点左、右子树都存在，可以在它的右子树中寻找中序下的第一个结点(关键值最小),用它的值填补到被删结点中，再来处理这个结点的删除问题。
这个中序下的第一个结点就是右子树最左,交换结点域之后删除右子树最左的地方

BinTree Insert( BinTree BST, ElementType X )
{
    if( !BST ){ /* 若原树为空，生成并返回一个结点的二叉搜索树 */
        BST = (BinTree)malloc(sizeof(struct TNode));
        BST->Data = X;
        BST->Left = BST->Right = NULL;
    }
    else { /* 开始找要插入元素的位置 */
        if( X < BST->Data )
            BST->Left = Insert( BST->Left, X );   /*递归插入左子树*/
        else  if( X > BST->Data )
            BST->Right = Insert( BST->Right, X ); /*递归插入右子树*/
        /* else X已经存在，什么都不做 */
    }
    return BST;
}

BinTree Delete( BinTree BST, ElementType X ) 
{ 
    Position Tmp; 

    if( !BST ) 
        printf("要删除的元素未找到"); 
    else {
        if( X < BST->Data ) 
            BST->Left = Delete( BST->Left, X );   /* 从左子树递归删除 */
        else if( X > BST->Data ) 
            BST->Right = Delete( BST->Right, X ); /* 从右子树递归删除 */
        else { /* BST就是要删除的结点 */
            /* 如果被删除结点有左右两个子结点 */ 
            if( BST->Left && BST->Right ) {
                /* 从右子树中找最小的元素填充删除结点 */
                Tmp = FindMin( BST->Right );
                BST->Data = Tmp->Data;
                /* 从右子树中删除最小元素 */
                BST->Right = Delete( BST->Right, BST->Data );
            }
            else { /* 被删除结点有一个或无子结点 */
                Tmp = BST; 
                if( !BST->Left )       /* 只有右孩子或无子结点 */
                    BST = BST->Right; 
                else                   /* 只有左孩子 */
                    BST = BST->Left;
                free( Tmp );
            }
        }
    }
    return BST;
}
Source:ZJU

ASL:
最好情况(为满二叉树）
ASL= = O(log2 n)
最坏情况(为单枝树): ASL=(1+2+…+n)/n=(n+1)/2
平均值: ASL≈O(log2 n)

5 平衡二叉树(AVL树)

AVL树：由G.M.Adelson-Velskii和E.M.Landis提出。
结点的平衡因子：结点的左右子树的深度之差。
平衡二叉树：任意结点的平衡因子的绝对值小于等于1的二叉树。
存储类型:
typedef int DataType; //结点数据类型
typedef struct node { //AVL树结点定义
DataType data; //结点数据域
int balance; //结点平衡因子域
struct node *leftChild, *rightChild;
//结点左、右子树指针域
} AVLNode;
typedef AVLNode * AVLTree; //AVL树

如果在某一结点发现高度不平衡，停止回溯。从发生不平衡的结点起，沿刚才回溯的路径取直接下两层的结点。
如果这三个结点处于一条直线上，则采用单旋转进行平衡化。单旋转可按其方向分为左单旋转和右单旋转, 其中一个是另一 个的镜像，其方向与不平衡的形状相关。
如果这三个结点处于一条折线上，则采用双旋转进行平衡化。双旋转分为先左后右和先右后左两类。

我们看:不平衡的发现者是A,麻烦结点(让A发现不平衡的结点)在A的右边的右边,就需要做左单旋转

我们看:不平衡的发现者是A,麻烦结点(让A发现不平衡的结点)在A的左边的左边,就需要做右单旋转

需要变换的子树都是含有麻烦结点子树的兄弟
我们看:不平衡的发现者是A,麻烦结点(让A发现不平衡的结点)在A的左边的右边,就需要做左右旋转

我们看:不平衡的发现者是A,麻烦结点(让A发现不平衡的结点)在A的右边的左边,就需要做右左旋转

ZJU给出了一个更加直接的结论,可以下载文档查看:

代码:

typedef struct AVLNode *Position;
typedef Position AVLTree; /* AVL树类型 */
struct AVLNode{
    ElementType Data; /* 结点数据 */
    AVLTree Left;     /* 指向左子树 */
    AVLTree Right;    /* 指向右子树 */
    int Height;       /* 树高 */
};

int Max ( int a, int b )
{
    return a > b ? a : b;
}

AVLTree SingleLeftRotation ( AVLTree A )
{ /* 注意：A必须有一个左子结点B */
  /* 将A与B做左单旋，更新A与B的高度，返回新的根结点B */     

    AVLTree B = A->Left;
    A->Left = B->Right;
    B->Right = A;
    A->Height = Max( GetHeight(A->Left), GetHeight(A->Right) ) + 1;
    B->Height = Max( GetHeight(B->Left), A->Height ) + 1;
 
    return B;
}

AVLTree DoubleLeftRightRotation ( AVLTree A )
{ /* 注意：A必须有一个左子结点B，且B必须有一个右子结点C */
  /* 将A、B与C做两次单旋，返回新的根结点C */
    
    /* 将B与C做右单旋，C被返回 */
    A->Left = SingleRightRotation(A->Left);
    /* 将A与C做左单旋，C被返回 */
    return SingleLeftRotation(A);
}

/*************************************/
/* 对称的右单旋与右-左双旋请自己实现 */
/*************************************/

AVLTree Insert( AVLTree T, ElementType X )
{ /* 将X插入AVL树T中，并且返回调整后的AVL树 */
    if ( !T ) { /* 若插入空树，则新建包含一个结点的树 */
        T = (AVLTree)malloc(sizeof(struct AVLNode));
        T->Data = X;
        T->Height = 0;
        T->Left = T->Right = NULL;
    } /* if (插入空树) 结束 */

    else if ( X < T->Data ) {
        /* 插入T的左子树 */
        T->Left = Insert( T->Left, X);
        /* 如果需要左旋 */
        if ( GetHeight(T->Left)-GetHeight(T->Right) == 2 )
            if ( X < T->Left->Data ) 
               T = SingleLeftRotation(T);      /* 左单旋 */
            else 
               T = DoubleLeftRightRotation(T); /* 左-右双旋 */
    } /* else if (插入左子树) 结束 */
    
    else if ( X > T->Data ) {
        /* 插入T的右子树 */
        T->Right = Insert( T->Right, X );
        /* 如果需要右旋 */
        if ( GetHeight(T->Left)-GetHeight(T->Right) == -2 )
            if ( X > T->Right->Data ) 
               T = SingleRightRotation(T);     /* 右单旋 */
            else 
               T = DoubleRightLeftRotation(T); /* 右-左双旋 */
    } /* else if (插入右子树) 结束 */

    /* else X == T->Data，无须插入 */

    /* 别忘了更新树高 */
    T->Height = Max( GetHeight(T->Left), GetHeight(T->Right) ) + 1;
    
    return T;
}

排序

1.插入排序

算法基本思想
将待排序的记录插入到已排序的子文件中去，使得插入之后得到的子文件仍然是有序子文件。插入一个记录，首先要对有序子文件进行查找，以确定这个记录的插入位置。按查找方式的不同，插入排序又可以分为线性插入排序和折半插入排序，前者使用顺序查找，后者使用折半查找。

1.1 简单插入排序

插入排序:设待排序的文件为：(r[1],r[2],…,r[n])
关键字为：(r[1].key,r[2].key,…,r[n].key)
首先,将初始文件中的记录r[1]看作有序子文件；
第1遍：将r[2]插入有序子文件中，若：
r[2].key<r[1].key，
则r[2]插在r[1]之前；否则，插在r[1]的后面。
第2遍：将记录r[3]插入前面已有2个记录的有序子文件中，得到3个记录的有序子文件。
以此类推，依次插入r[4],…,r[n],最后得到n个记录的递增有序文件。

就是找到最好的插入位置

void InsertSort(RecType r[],int n）
// 对数组r[1..n]中的n个记录作插入排序
{ int i,j；
for (i=2；i<=n；i++){
r[0]=r[i]； //待插记录r[i]存入监视哨中
j=i-1； //以排序的范围1-i-1
//从r[i-1]开始向左扫描
while(r[0].key<r[j].key)
{ 
r[j+1]=r[j]； //记录后移
j–； //继续向左扫描
}
r[j+1]=r[0]； //插入记录r[0],即原r[i]
}
}

(1)最好情况，原n个记录递增有序：比较关键字n-1次,移动记录2(n-1)次,(将数据复制到r[0]后又复制回来)
(2)最坏情况:$O(n^2)$

1.2.折半插入排序（二分插入排序）

（a）由于插入排序的基本思想是在一个有序序列中插入一个新的记录，因此可以利用“折半查找”查询插入位置，由此得到的插入排序算法为“折半插入排序”，又被称为二分法插入排序。
（b）直接插入排序的算法简单易行，对长度(n)很大的记录序列宜采用性能更好的插入排序算法。
（c）折半插入排序过程中的折半查找的目的是查询插入点，因此不论是否存在和给定值相同的关键字，结束查找过程的条件都是high<low，并且插入位置为low指示的地方。

void BInsertSort (SqList &L)  {  
// 对顺序表L作折半插入排序　
    for ( i=2; i<=L.length; ++i ) 　
    { 				//假定第一个记录有序　　
        L.r[0] = L.r[i];		// 将L.r[i]暂存到L.r[0]　　
        low = 1; high = i-1;　　
        while (low<=high) 　　
        { 　　// 在r[low..high]中折半查找有序插入的位置　　　
            m = (low+high)/2; 		// 折半　　　
            if (L.r[0].key < L.r[m].key)) 		
                high = m-1;		// 插入点在低半区　　　
            else
 		low = m+1; 		// 插入点在高半区
    　　} // while　　
       for ( j=i-1; j>=low; - -j ) L.r[j+1] = L.r[j]; // 记录后移　　 L.r[high+1] = L.r[0];		// 插入　
    } //for
} // BInsertSort

1.3.希尔(shell)排序 (缩小增量排序)

（a）是插入排序中效率最高的一种排序方法。又称“缩小增量排序”，是由D.L.Shell在1959年提出来的。
（b）基本思想是，先对待排序列进行“宏观调整”，待序列中的记录“基本有序”时再进行直接插入排序。注：所谓“ 基本有序” 是指，在序列中的各个关键字之前，只存在少量关键字比它大的记录。
（c）做法是：先取定一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组，所有距离为d1的倍数的记录放在同一个组中，在各组内进行直接插入排序；然后，到第二个增量d2<d1重复上述分组和排序，直至所取的增量dt=1（dt<dt-1<…<d2<d1），即所有记录放在同一组中进行直接插入排序为止。

例如·:3 2 1

1 4 5 3 2 6
3:三类:14 25 36
1 2 5 3 4 6
2:2类:135 246
1 2 4 3 5 6
1:一类:123456
1 2 3 4 5 6

2 交换排序

2.1 冒泡排序

基本思想: 设待排序的文件为r[1..n]
第1趟(遍)：从r[1]开始,依次比较两个相邻记录的关键字r[i].key和r[i+1].key,若r[i].key>r[i+1].key，则交换记录r[i]和r[i+1]的位置；否则,不交换。(i=1,2,…n-1)
第1趟之后,n个关键字中最大的记录移到了r[n]的位置上。
第2趟：从r[1]开始,依次比较两个相邻记录的关键字r[i].key和r[i+1].key,若r[i].key>r[i+1].key，则交换记录r[i]和r[i+1]的位置；否则,不交换。(i=1,2,…n-2)
第2趟之后,前n-1个关键字中最大的记录移到了r[n-1]的位置上。
……
作完n-1趟,或者不需再交换记录时为止。

    void  bubble1(int a[],int n)
  
    { int i,j,temp；
  
    for(i=0；i<n-1；i++)     //作n-1趟排序
         
for(j=0；j<n-1-i；j++)       
       
              if (a[j]>a[j+1])            
          
                  { temp=a[j]；      //交换记录 
      
                    a[j]=a[j+1]；           
     
                    a[j+1]=temp；           
  
                  }       
      
    for(i=0；i<n；i++)
   printf("%d",a[i])；  //输出排序后的元素 
   
      }

可以加一个swap变量,如果一次排序没换过元素,那就是

● 最好情况: 待排序的文件已是有序文件，只需要进行1趟
排序,共计比较关键字的次数为 n-1 不交换记录。
● 最坏情况: 要经过n-1趟排序，所需总的比较关键字的次数为
(n-1)+(n-2)+…+1＝n(n-1)/2
交换记录的次数最多为
(n-1)+(n-2)+…+1＝n(n-1)/2
移动记录次数最多为
3n(n-1)/2 。
● 只需要少量中间变量作为辅助空间。 O(1)
● 算法是稳定的。

2.2 快速排序

基本思想：首先在r[1..n]中，确定一个r[i]，经过比较和移动，将r[i]放到”中间”某个位置上，使得r[i]左边所有记录的关键字小于等于r[i].key，r[i]右边所有记录的关键字大于等于r[i].key。以r[i]为界,将文件划分为左、右两个子文件。
用同样的方法分别对这两个子文件进行划分, 得到4个更小的子文件。继续进行下去,使得每个子文件只有一个记录为止,便得到原文件的有序文件。

设置两个指针:一个大区域,一个小区域

void quksort(RecType r[],int low,int high)
{  RecType x；int i,j；
 
  if (low<high)                       //有两个以上记录
   
   { i=low；j=high；x=r[i]；          //保存记录到变量x中
     
     do {                             //此时i指示位置可用
        while (i<j && r[j].key>=x.key)
     
        j--；     //j从右向左端扫描通过key不小于x.key的元素

           if (i<j)                        //i,j未相遇
           {   r[i]=r[j]； i++；            //此时j指示位置可用
               while(i<j && r[i].key<=x.key)
               i++；   //i从左向右端扫描通过key不大于x.key的元素
               if (i<j)
             
               { r[j]=r[i]；j--；}
          
           }
 
       } while (i!=j)；                 //i,j未相遇
   
 }

在上一级的函数就分治即可

就平均速度而言，快速排序是已知内部排序方法中最好的一种排序方法,其时间复杂度为$O(nlog_2n)$。
但是，在最坏情况下（基本有序时），快速排序所需的比较次数和冒泡排序的比较次数相同,其时间复杂度为$O(n^2)$。
快速排序需要一个栈空间来实现递归。若每次划分均能将文件均匀分割为两部分，则栈的最大深度为$|log_2n|+1$，所需栈空间为$O(log_2n)$,即空间复杂度 $S(n)= O (log2n)$
快速排序是不稳定的。

ElementType Median3( ElementType A[], int Left, int Right )
{ 
    int Center = (Left+Right) / 2;
    if ( A[Left] > A[Center] )
        Swap( &A[Left], &A[Center] );
    if ( A[Left] > A[Right] )
        Swap( &A[Left], &A[Right] );
    if ( A[Center] > A[Right] )
        Swap( &A[Center], &A[Right] );
    /* 此时A[Left] <= A[Center] <= A[Right] */
    Swap( &A[Center], &A[Right-1] ); /* 将基准Pivot藏到右边*/
    /* 只需要考虑A[Left+1] … A[Right-2] */
    return  A[Right-1];  /* 返回基准Pivot */
}

void Qsort( ElementType A[], int Left, int Right )
{ /* 核心递归函数 */ 
     int Pivot, Cutoff, Low, High;
      
     if ( Cutoff <= Right-Left ) { /* 如果序列元素充分多，进入快排 */
          Pivot = Median3( A, Left, Right ); /* 选基准 */ 
          Low = Left; High = Right-1;
          while (1) { /*将序列中比基准小的移到基准左边，大的移到右边*/
               while ( A[++Low] < Pivot ) ;
               while ( A[--High] > Pivot ) ;
               if ( Low < High ) Swap( &A[Low], &A[High] );
               else break;
          }
          Swap( &A[Low], &A[Right-1] );   /* 将基准换到正确的位置 */ 
          Qsort( A, Left, Low-1 );    /* 递归解决左边 */ 
          Qsort( A, Low+1, Right );   /* 递归解决右边 */  
     }
     else InsertionSort( A+Left, Right-Left+1 ); /* 元素太少，用简单排序 */ 
}

（52, 49, 80, 36, 14, 75, 58, 97, 23, 61）
经第1趟快速排序之后为：(23, 49, 14, 36) 52 (75, 58, 97, 80, 61)
经第2趟快速排序之后为：(14) 23 (49, 36) 52 (61, 58) 75 (80, 97)
经第3趟快速排序之后为：(14, 23, 36, 49, 52, 58, 61, 75, 80, 97)
注：为避免出现枢轴记录关键字为”最大”或”最小”的情况，通常进行的快速排序采用”三者取中”的改进方案，即以 R[s]、R[t] 和 R[(s+t)/2] 三者中关键字介于中值者为枢轴。只要将它和 R[s] 互换，一次划分的算法仍不变。

3 选择排序

3.1 简单选择

算法思想:设待排序的文件为(r[1],r[2],…,r[n]),关键字为(r[1].key,r[2].key,…,r[n].key),
第1趟(遍)：在(r[1],r[2],…,r[n])中,选出关键字最小的记录r[min].key，若min≠1,则交换r[1]和r[min]；
需要进行n-1次比较。
　 第2趟(遍)：在n-1个记录(r[2],…,r[n])中,选出关键字最小的记录r[min].key，若min≠2,则交换r[2]和r[min]；
　 需要进行n-2次比较。
　 第n-1趟(遍)：在最后的2个记录记录(r[n-1],r[n])中,选出关键字最小的记录r[min].key，若min≠n-1,则交换r[n-1]和r[min]；需要进行1次比较。

3.2 树形选择排序

树形选择排序又称锦标赛排序（Tournament Sort），是一种按照锦标赛的思想进行选择排序的方法。可用一棵有n个叶子结点的完全二叉树表示。
基本思想为：
首先对n个记录的关键字进行两两比较，然后在其中n/2个较小者之间再进行两两比较，如此重复，直到选出最小关键字的记录为止（树根）。
将最小关键字输出，且将其原来位置改为极大数，与此位置相关部分重新（向树根方向）进行比较，选出次小关键字，保留结果。
如此下去，直至全部排序完成。

该方法比直接选择排序速度上有很大提高，其缺点有：
（1）需要另开储存空间保存排序结果；
（2）n个待排序关键字，需要额外的（n-1）个内部结点（包括根结点），增加了内存开销。
（3）将最小关键字改为极大数，再与兄弟结点比较属于多余。
故：树形选择排序一般不是用来排序而是用来证明某些问题。为了弥补以上缺点，威洛姆斯在1964年提出了另一种形式的选择排序—堆排序。

3.3 堆排序

堆的定义略
问题1：如何将序列{k1,k2,…,kn} 处理成（大顶）堆（初始化）？
问题2：如何在堆顶元素被替换后，调整剩余元素成为一个新的堆。

void Swap( ElementType *a, ElementType *b )
{
     ElementType t = *a; *a = *b; *b = t;
}
 
void PercDown( ElementType A[], int p, int N )
{ /* 改编代码4.24的PercDown( MaxHeap H, int p )    */
  /* 将N个元素的数组中以A[p]为根的子堆调整为最大堆 */
    int Parent, Child;
    ElementType X;

    X = A[p]; /* 取出根结点存放的值 */
    for( Parent=p; (Parent*2+1)<N; Parent=Child ) {
        Child = Parent * 2 + 1;
        if( (Child!=N-1) && (A[Child]<A[Child+1]) )
            Child++;  /* Child指向左右子结点的较大者 */
        if( X >= A[Child] ) break; /* 找到了合适位置 */
        else  /* 下滤X */
            A[Parent] = A[Child];
    }
    A[Parent] = X;
}

void HeapSort( ElementType A[], int N ) 
{ /* 堆排序 */
     int i;
      
     for ( i=N/2-1; i>=0; i-- )/* 建立最大堆 */
         PercDown( A, i, N );
     
     for ( i=N-1; i>0; i-- ) {
         /* 删除最大堆顶 */
         Swap( &A[0], &A[i] ); /* 见代码7.1 */
         PercDown( A, 0, i );
     }
}

这个代码把问题1和问题2统一化了
时间复杂度:O(nlogn)

4 归并排序

归并的操作,就是两个指针,谁少就copy谁,最后就把剩下的元素copy过去

第一个想法:
每个子文件的长度从2,4,8一直递增

1.假如说:现在还剩下2s以上的空缺,就直接s和s互相互补即可
2.假如说:现在还剩下s-2s的空缺,就剩下的部分归并
3.假如说:现在还剩下0-s的空缺,就直接照抄

当然,还有一种写法就是找到最中间的一个元素,然后进行分化

/* 归并排序 - 递归实现 */

/* L = 左边起始位置, R = 右边起始位置, RightEnd = 右边终点位置*/
void Merge( ElementType A[], ElementType TmpA[], int L, int R, int RightEnd )
{ /* 将有序的A[L]~A[R-1]和A[R]~A[RightEnd]归并成一个有序序列 */
     int LeftEnd, NumElements, Tmp;
     int i;
     
     LeftEnd = R - 1; /* 左边终点位置 */
     Tmp = L;         /* 有序序列的起始位置 */
     NumElements = RightEnd - L + 1;
     
     while( L <= LeftEnd && R <= RightEnd ) {
         if ( A[L] <= A[R] )
             TmpA[Tmp++] = A[L++]; /* 将左边元素复制到TmpA */
         else
             TmpA[Tmp++] = A[R++]; /* 将右边元素复制到TmpA */
     }

     while( L <= LeftEnd )
         TmpA[Tmp++] = A[L++]; /* 直接复制左边剩下的 */
     while( R <= RightEnd )
         TmpA[Tmp++] = A[R++]; /* 直接复制右边剩下的 */
         
     for( i = 0; i < NumElements; i++, RightEnd -- )
         A[RightEnd] = TmpA[RightEnd]; /* 将有序的TmpA[]复制回A[] */
}

void Msort( ElementType A[], ElementType TmpA[], int L, int RightEnd )
{ /* 核心递归排序函数 */ 
     int Center;
     
     if ( L < RightEnd ) {
          Center = (L+RightEnd) / 2;
          Msort( A, TmpA, L, Center );              /* 递归解决左边 */ 
          Msort( A, TmpA, Center+1, RightEnd );     /* 递归解决右边 */  
          Merge( A, TmpA, L, Center+1, RightEnd );  /* 合并两段有序序列 */ 
     }
}

void MergeSort( ElementType A[], int N )
{ /* 归并排序 */
     ElementType *TmpA;
     TmpA = (ElementType *)malloc(N*sizeof(ElementType));
     
     if ( TmpA != NULL ) {
          Msort( A, TmpA, 0, N-1 );
          free( TmpA );
     }
     else printf( "空间不足" );
}

/* 归并排序 - 循环实现 */
/* 这里Merge函数在递归版本中给出 */

/* length = 当前有序子列的长度*/
void Merge_pass( ElementType A[], ElementType TmpA[], int N, int length )
{ /* 两两归并相邻有序子列 */
     int i, j;
      
     for ( i=0; i <= N-2*length; i += 2*length )
         Merge( A, TmpA, i, i+length, i+2*length-1 );
     if ( i+length < N ) /* 归并最后2个子列*/
         Merge( A, TmpA, i, i+length, N-1);
     else /* 最后只剩1个子列*/
         for ( j = i; j < N; j++ ) TmpA[j] = A[j];
}

void Merge_Sort( ElementType A[], int N )
{ 
     int length; 
     ElementType *TmpA;
     
     length = 1; /* 初始化子序列长度*/
     TmpA = malloc( N * sizeof( ElementType ) );
     if ( TmpA != NULL ) {
          while( length < N ) {
              Merge_pass( A, TmpA, N, length );
              length *= 2;
              Merge_pass( TmpA, A, N, length );
              length *= 2;
          }
          free( TmpA );
     }
     else printf( "空间不足" );
}

5 基数排序

就是构建十个桶,按照个位,先按照各元素放入桶里.
接着再取出,按照0-9的顺序,接着是十位,接着是百位

/* 基数排序 - 次位优先 */

/* 假设元素最多有MaxDigit个关键字，基数全是同样的Radix */
#define MaxDigit 4
#define Radix 10

/* 桶元素结点 */
typedef struct Node *PtrToNode;
struct Node {
    int key;
    PtrToNode next;
};

/* 桶头结点 */
struct HeadNode {
    PtrToNode head, tail;
};
typedef struct HeadNode Bucket[Radix];
 
int GetDigit ( int X, int D )
{ /* 默认次位D=1, 主位D<=MaxDigit */
    int d, i;
    
    for (i=1; i<=D; i++) {
        d = X % Radix;
        X /= Radix;
    }
    return d;
}

void LSDRadixSort( ElementType A[], int N )
{ /* 基数排序 - 次位优先 */
     int D, Di, i;
     Bucket B;
     PtrToNode tmp, p, List = NULL; 
     
     for (i=0; i<Radix; i++) /* 初始化每个桶为空链表 */
         B[i].head = B[i].tail = NULL;
     for (i=0; i<N; i++) { /* 将原始序列逆序存入初始链表List */
         tmp = (PtrToNode)malloc(sizeof(struct Node));
         tmp->key = A[i];
         tmp->next = List;
         List = tmp;
     }
     /* 下面开始排序 */ 
     for (D=1; D<=MaxDigit; D++) { /* 对数据的每一位循环处理 */
         /* 下面是分配的过程 */
         p = List;
         while (p) {
             Di = GetDigit(p->key, D); /* 获得当前元素的当前位数字 */
             /* 从List中摘除 */
             tmp = p; p = p->next;
             /* 插入B[Di]号桶尾 */
             tmp->next = NULL;
             if (B[Di].head == NULL)
                 B[Di].head = B[Di].tail = tmp;
             else {
                 B[Di].tail->next = tmp;
                 B[Di].tail = tmp;
             }
         }
         /* 下面是收集的过程 */
         List = NULL; 
         for (Di=Radix-1; Di>=0; Di--) { /* 将每个桶的元素顺序收集入List */
             if (B[Di].head) { /* 如果桶不为空 */
                 /* 整桶插入List表头 */
                 B[Di].tail->next = List;
                 List = B[Di].head;
                 B[Di].head = B[Di].tail = NULL; /* 清空桶 */
             }
         }
     }
     /* 将List倒入A[]并释放空间 */
     for (i=0; i<N; i++) {
        tmp = List;
        List = List->next;
        A[i] = tmp->key;
        free(tmp);
     } 
}

6 计数排序

这个可以用于排序的数范围已知的情况,非常好写

7 排序算法的比较

线性结构

1 基础

1.数据,数据元素,数据对象,数据项,数据结构的概念
什么是基本单位,什么是最小单位,什么是所有能输入到计算机中并被计算机程序处理的符号总称?性质相同的元素的集合?

2.结构的分类?
逻辑结构:集合,线性表,树,图
物理结构:顺序存储结构,物理存储结构,索引存储结构,哈希存储结构

3.引用参数:&:可以扩展为指针

4.算法的五个特征
(1)有穷性
(2)可读性
(3)健壮性
(4)可行性
(5)高效性

5.时间复杂度的分析:
(1)大致的时间复杂度为多数
(2)递归或者循环调用时,调用的每个语句都要算进去
(3)计算语句频度的方法?

6.空间复杂度分析:
(1)递归:有栈存储,至少的空间
(2)有递归次数:

2 线性表

1.表长:表长与存储的长度区别,maxlength和size的区别
2.直接前驱后继:首元素没有前驱,尾元素没有后继
3.抽象数据类型:了解(跟class一样)

4.存储特征:
顺序存储结构:可以随机读取元素,插入删除复杂
链式存储结构:不可以随机读取元素,插入删除较为简单

5.自由区:空闲的空间
6.首地址+偏移量选址法
(见数组)

7.动态静态分配的顺序存储结构

静态存取

#define maxleng 100
 typedef struct     
   { ElemType elem[maxleng]；//下标:0,1,...,maxleng-1
     int length；            //表长
    } SqList；
   SqList La；

动态存取:

#define LIST_INIT_SIZE 100
 #define LISTINCREMENT 10
typedef struct     
   { ElemType *elem；//存储空间基地址
     int length；    //表长
     int listsize;   //当前分配的存储容量
                     //（以sizeof(ElemType)为单位
    } SqList；
   SqList Lb；

有增量#define LISTINCREMENT 10

溢出时扩充的方法

if (L.length>=L.listsize)    /*溢出时扩充*/
      { 
     ElemType *newbase;
     newbase=(ElemType *) realloc(L.elem,
        (L.listsize+LISTINCREMENT)*sizeof(ElemType));
      if (newbase==NULL) return OVERFLOW;   //扩充失败
     L.elem=newbase;
     L.listsize+=LISTINCREMENT;
      }

9.链表
1.带头结点和不带头结点
带头结点的作用:需要额外开辟一个空间,但是插入和删除首元素时不用进行特殊处理

10.静态链表:用数组模拟,数组里面有data域和下一个元素的编号,head->0,尾元素指向0

11.循环链表:
尾指针:有头:指向表头
无头:指向第一个元素
head:设置任意一个指
只需要设一个尾指针就可以满足,可以找到链表的任何一个值

12.双向链表

首结点前驱是空,尾结点后继是空
表头结点前驱是尾结点,后继指头结点
会考一些操作

13.双向循环链表:没有哪一个指针域是空

3 栈和队列

3.1 栈

1.先进后出

2.栈顶和栈底的定义

3.栈顶的几个定义法:和的上一个单元:空栈时分别对应-1和0

4.进展顺序判断:第二斯特林数,溢出和下溢的判断

5.符号表达式和代替递归函数

6.存储形式
(1)数组,加个top
(2)链式存储,用表头插入:搞清楚插入删除的复杂度:

3.2 队列

1.先进先出

2.双向队列:中间值不能动
输入受限:只允许在表的一端插入、在两端删除元素的线性表
输出受限:只许在表的两端插入、在一端删除元素的线性表

3.循环队列:
溢出判断:(Q.rear+1)% MAXLENGQ.front
下溢判断:Q.front==Q.rear
算队列长的方法:(Q.rearQ.front+maxlength)%maxlength
改进:有6个空间,只存5个元素

还要记住几个插入删除的算法怎么写

4 串

1.’\0’C语言
a[0]存指定的串长 Pascal

2.字符堆:指针指向一个地址(第一个字母的地址),还有一个元素存长度

3.链式堆的存储密度
(1)多字符和单字符
(2)计算方式:,开辟的总空间=字符数+指针域

4.KMP算法,求那个next数组的值

5 数组

1.行存储和列存储:
首元素寻址法:有0行0列和无0行0列

从左到右&从右到左

例子:三维数组a[1..p,1..m,1..n],假定无0页0行0列
1)以行序为主序，的地址为

(2)以列序为主序，的地址为

如果有0行0列:所有-1去掉

2.矩阵压缩存储

(1)对称矩阵与三对角

3.稀疏矩阵
(1)三元组表:存行列值和元素值
(2)十字链表

4.广义表:加递归,元素可以是单独的值也可以是新的广义表

结构位置表示:a,b,c,d 都表明好
(1)广义表的图型表示—-树型结构
约定 □—-单元素/原子
○—-列表,若有表名,附表名：对应（）
(2)存储结构

(3)表头:第一个元素:可元素,可表
(4)表尾:剩下的元素都是表尾,一定是广义表