教材典型算法

树

树的遍历算法

1. 先序遍历

void Preorder(BiTree T, void (*visit)(TElemType& e))
{
    if(T)
    {
        visit(T->data); // 先访问根结点
        // 再递归访问左子树和柚子树
        Preorder(T->lchild, visit);
        Preorder(T->rchild, visit);
    }
}

先序、中序、后序遍历算法思路几乎完全一致，不再赘述。

1. 中序遍历的非递归描述

// 对于中序遍历一棵二叉树，第一个要访问的根结点一定是最左边的结点
// 因此，GoFarLeft函数的功能就是对二叉树T，寻找最左边的结点
// 同时，用一个栈S保存每一次的根结点，它是中序遍历的中间访问者
BiTNode *GoFarLeft(BiTree T, Stack *S)
{
    // 代表当前根结点不存在了，返回空
    if(!T)  return NULL;
    // 当前根结点有左子树，往左继续寻找
    while(T->lchild)
    {
        Push(S, T);
        T = T->lchild;
    }
    return T;
}

// 非递归的中序遍历算法
void Inorder_I(BiTree T, void (*visit)(TelemType& e))
{
    Stack *S;
    t = GoFarLeft(T, S);    // 寻找最左下边的结点
    // 每一次循环，访问一个结点
    while(t)
    {
        visit(t->data);
        // 如果t有柚子树，就得继续遍历柚子树，用相同的方式
        if(t->rchild)
            t = GoFarLeft(t->rchild, S);
        // t没有柚子树，t本来就没有左子树，则应该访问其父结点了，S中存放了结点路径
        else if(!StackEmpty(S))
            t = Pop(S);
        else
            t = NULL;
    }
}

非递归。

1. 求二叉树的深度

int Depth(BiTree T)
{
    if(!T)  depthval = 0;
    else 
    {
        depthLeft = Depth(T->lchild);
        depthRight = Depth(T->lchild);
        depthval = (depthLeft > depthRight ? depthLeft : depthRight) + 1;
    }
    return depthval;
}

求深度。

1. 建树
   已知一棵二叉树的先序遍历和中序遍历，还原这棵二叉树。

void CrtBT(BiTree& T, char pre[], char ino[], int ps, int is, int n)
{
    if(n == 0)  T = NULL;
    else 
    {
        k = Search(ino, pre[ps]);
        if(k == -1) T = NULL;
        else
        {
            T = (BiTNode*)malloc(sizeof(BiTNode));
            T->data = pre[ps];
            if(k == is) T->Lchild = NULL;
            else    CrtBT(T->Lchild, pre[], ino[], ps+1, is, k - is);
            if(k == is+n-1) T->Rchild = NULL;
            else    CrtBT(T->Rchild, pre[], ino[], ps+1+(k-is), k+1, n-(k-is)-1);
        }
    }
}

555

1. 二叉树按层次遍历

Status LevelOrderTravel(BiTree T)
{
    Queue Q;
    InitQueue(Q);
    if(T)   Enqueue(Q, T);
    while(!QueueEmpty(Q))
    {
        Dequeue(Q, &E);
        visit(E);
        if(E->lchild)   EnQueue(Q, E->lchild);
        if(E->rchild)   EnQueue(Q, E->rchild);
    }
}

图

深度优先遍历

void DFSTravel(Graph G)
{
    for(v=0; v < G.Vexnum; ++v)
    {
        visited[v] = false;
    }
    for(v=0; v < G.Vexnum; ++v)
    {
        if(!visited[v]) DFS(G, v);
    }
}

void DFS(Graph G, int v)
{
    visited[v] = true;
    printf();
    for(w=0; w < G.vexnum; w++)
        if(G.arcs[v][w].adj != 0 && !visited[w])
            DFS(G, w);
}

拓扑排序

// 求各顶点入度
void FindInDegree(ALGraph G, int indegree[])
{
    int i;
    ArcNode *p;
    for(i=0; i < G.vexnum; i++)
    {
        while(p)
        {
            indegree[p->adjvex]++;
            p = p->next;
        }
    }
}

迪杰斯特拉算法

// final[]记录当前结点是否已经求出最短路径
// D[]记录当前所找的源点到每一个终点的最短路径长度
// P[]记录路径
// v0表示初始单源点起点
void ShortestPath_DIJ(MGraph G, int v0, int &P, float &D)
{
    int i=0,j,v,w,min,final[N];
    for(v=0; v < G.vexnum; ++v)
    {
        final[v] = FALSE;
        D[v] = G.arcs[v0][v];
        P[v] = -1;
        if(D[v] < INFINITY) P[v] = v0;
        final[v0] = TRUE;
        P[v0] = -1;
    }

    // 确定下一次的出发点
    for(i=1; i < G.vexnum; i++)
    {
        // 要找到当前还未确定最小路径长度的最小值
        min = INFINITY;
        for(w=0; w < G.vexnum; ++w)
        if(!final[w])
            if(D[w] < min)
            {
                v = w;
                min = D[w];
            }
    }

    final[v] = TRUE;    // 一旦确定了最小值，那么源点到它的最短路径也就确定了

    // 以这次的顶点v为起始点，进行最短路径的更新
    for(w=0; w < G.vexnum; ++w)
    {
        if(!final[w] && (min+G.arcs[v][w] < D[w]))
        {
            // 对满足条件的顶点，更新需要更新最短路径和最短路径长
            D[w] = min + G.arcs[v][w].adj;
            P[w] = v;
        }
    }
}

排序

插入排序

void InsertionSort(SqList &L)
{
    int i,j;
    // 从第二项开始排序
    for(i = 2; i <= L.length; ++i)
    {
        // 每一次排序前面的都已经排序好了
        if(L.r[i].key < L.r[i-1].key)
        {
            L.r[0] = L.r[i];    // 复制为监视哨
            for(j = i-1; L.r[0].key < L.r[j].key; --j)
            {
                L.r[j+1] = L.r[j];  // 记录后移
            }
            L.r[j+1] = L.r[0];  // 插入到正确的位置
        }
    }
}

快速排序

int Partition(SqList &L, int low, int high)
{
    KeyType pivotkey;
    L.r[0] = L.r[low];
    pivotkey = L.r[low].key;
    while(low < high)
    {
        // 从高位开始遍历，确保元素都大于枢轴
        while(low < high && L.r[high].key >= pivotkey)
            --high;
        L.r[low] = L.r[high];

        // 从地位开始遍历，确保元素都小于枢轴
        while(low < high && L.r[low].key <= povotkey)
            ++low;
        L.r[high] = L.r[low];
    }
    L.r[low] = L.r[0];
    return low; // 返回枢轴最后的位置
}

void QSort(SqList &L, int low, int high)
{
    int pivotloc;
    if(low < high)
    {
        pivotloc = Partition(L, low, high);
        QSort(L, low, pivotloc-1);
        QSort(L, pivotloc+1, high);
    }
}

堆排序

筛选算法：

// 调整堆结构
void HeapAdjust(HeapType &H, int s, int m)
{
    int j;
    RedType rc;
    rc = H.r[s];    // 将堆顶元素暂存下来到rc
    for(j=2*s; j <= m; j*=2)
    {
        // 横比，j初始值指向左孩子
        if(j < m && H.r[j].key < H.r[j+1].key)
            j++;
        // 纵比，如果右孩子比父节点小，表示该堆不需要调整
        if(rc.key >= H.r[j].key)    break;
        H.r[s] = H.r[j];
        s = j;
        // j*=2,表示进入下一个堆结构
    }
    H.r[s] = rc;
}

归并排序

void Merge(RcdType SR[], RcdType &TR[], int i, int m, in t n)
{
    for(j = m+1, k=i; i <= m && j <= n; ++k)
    {
        if(SR[i].key < SR[i].key)
            TR[k] = SR[i++];
        else
            TR[k] = SR[j++];
    }
    while(i <= m)   TR[k++] = SR[i++];
    while(j <= n)   TR[k++] = SR[j++];
}

void MSort(RcdType SR[], RcdType &TR[], int s, int t)
{
    if(s==t)    TR[s] = SR[s];
    else
    {
        m = (s+t)/2;
        MSort(SR, TR2, s, m);
        MSort(SR, TR2, m+1, t);
        Merge(TR2, TR, s, m, t);
    }
}