数据结构与算法分析 学习笔记

第九章

二叉搜索树

9.1  基本概念
二叉树的一个重要的应用是它们在查找中的使用。二叉搜索树的概念相当容易理解，即：对于树中的每个结点X，它的左子树中所有关键字的值都小于X的关键字值，而它的右子树中的所有关键字值都大于X的关键字值。这意味着该树所有的元素都可以用某种统一的方式排序。

例如下面就是一棵合法的二叉搜索树：


     6
    / \\
   2   8
  / \\
1   4
    /
   3


二叉搜索树的性质决定了它在搜索方面有着非常出色的表现：要找到一棵树的最小结点，只需要从根结点开始，只要有左儿子就向左进行，终止结点就是最小的结点。找最大的结点则是往右进行。例如上面的例子中，最小的结点是1，在最左边；最大的结点是8，在最右边。


9.2  代码实现
二叉树的代码实现如下：


///////////////////////////////////////////////////////////////////////////////
//
//  FileName    :   bstree.h
//  Version     :   0.10
//  Author      :   Luo Cong
//  Date        :   2005-1-17 22:53:52
//  Comment     :  
//
///////////////////////////////////////////////////////////////////////////////

#ifndef __BINARY_SEARCH_TREE_H__
#define __BINARY_SEARCH_TREE_H__

#include \\"../../btree/src/btree.h\\"

template<typename T>
class CBSTree : public CBTree<T>
{
private:
    CBTNode<T>* Find(const T &data, CBTNode<T> *p) const;
    CBTNode<T>* FindMin(CBTNode<T> *p) const;
    CBTNode<T>* FindMax(CBTNode<T> *p) const;
    CBTNode<T>* Insert(const T &data, CBTNode<T> *p);
    CBTNode<T>* Delete(const T &data, CBTNode<T> *p);

public:
    CBTNode<T>* Find(const T &data) const;
    CBTNode<T>* FindMin() const;
    CBTNode<T>* FindMax() const;
    CBTNode<T>* Insert(const T &data);
    CBTNode<T>* Delete(const T &data);
};

template<typename T>
inline CBTNode<T>* CBSTree<T>::Find(const T &data) const
{
    return Find(data, m_pNodeRoot);
}

template<typename T>
inline CBTNode<T>* CBSTree<T>::Find(const T &data, CBTNode<T> *p) const
{
    if (NULL == p)
        return NULL;
    if (data < p->data)
        return Find(data, p->left);
    else if (data > p->data)
        return Find(data, p->right);
    else
        return p;
}

template<typename T>
inline CBTNode<T>* CBSTree<T>::FindMin() const
{
    return FindMin(m_pNodeRoot);
}

template<typename T>
inline CBTNode<T>* CBSTree<T>::FindMin(CBTNode<T> *p) const
{
    if (NULL == p)
        return NULL;
    else if (NULL == p->left)
        return p;
    else
        return FindMin(p->left);
}

template<typename T>
inline CBTNode<T>* CBSTree<T>::FindMax() const
{
    return FindMax(m_pNodeRoot);
}

template<typename T>
inline CBTNode<T>* CBSTree<T>::FindMax(CBTNode<T> *p) const
{
    if (NULL == p)
        return NULL;
    else if (NULL == p->right)
        return p;
    else
        return FindMax(p->right);
}

template<typename T>
inline CBTNode<T>* CBSTree<T>::Insert(const T &data)
{
    return Insert(data, m_pNodeRoot);
}

template<typename T>
inline CBTNode<T>* CBSTree<T>::Insert(const T &data, CBTNode<T> *p)
{
    if (NULL == p)
    {
        p = new CBTNode<T>;
        if (NULL == p)
            return NULL;
        else
        {
            p->data = data;
            p->left = NULL;
            p->right = NULL;
            if (NULL == m_pNodeRoot)
            {
                m_pNodeRoot = p;
                m_pNodeRoot->parent = NULL;
            }
        }
    }
    else if (data < p->data)
    {
        p->left = Insert(data, p->left);
        if (p->left)
            p->left->parent = p;
    }
    else if (data > p->data)
    {
        p->right = Insert(data, p->right);
        if (p->right)
            p->right->parent = p;
    }
    // else data is in the tree already, we\'ll do nothing!

    return p;
}

template<typename T>
inline CBTNode<T>* CBSTree<T>::Delete(const T &data)
{
    return Delete(data, m_pNodeRoot);
}

template<typename T>
inline CBTNode<T>* CBSTree<T>::Delete(const T &data, CBTNode<T> *p)
{
    if (NULL == p)
    {
        // Error! data not found!
    }
    else if (data < p->data)
    {
        p->left = Delete(data, p->left);
    }
    else if (data > p->data)
    {
        p->right = Delete(data, p->right);
    }
    else if (p->left && p->right)   // found it, and it has two children
    {
        CBTNode<T> *pTmp = FindMin(p->right);
        p->data = pTmp->data;
        p->right = Delete(p->data, p->right);
    }
    else    // found it, and it has one or zero children
    {
        CBTNode<T> *pTmp = p;
        if (NULL == p->left)
            p = p->right;
        else if (NULL == p->right)
            p = p->left;

        if (p)
            p->parent = pTmp->parent;

        if (m_pNodeRoot == pTmp)
            m_pNodeRoot = p;

        delete pTmp;
    }

    return p;
}

#endif  // __BINARY_SEARCH_TREE_H__

测试代码：


///////////////////////////////////////////////////////////////////////////////
//
//  FileName    :   bstree.cpp
//  Version     :   0.10
//  Author      :   Luo Cong
//  Date        :   2005-1-17 22:55:12
//  Comment     :  
//
///////////////////////////////////////////////////////////////////////////////

#include \\"bstree.h\\"

int main()
{
    CBSTree<int> bstree;

#ifdef _DEBUG
    _CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);
#endif

    bstree.Insert(1);
    bstree.Insert(2);
    bstree.Insert(3);

    bstree.Delete(1);
}


9.3  说明
我的二叉搜索树是从二叉树继承而来的，我写了Find()、FindMin()、FindMax()、Insert()和Delete()一共5个成员函数。这里要说的是，对非线性数据结构的操作总是特别的不直观，因为一般来说我们会选择使用递归——而人脑一般不太容易“调试”递归的程序——如果递归的层数比较少（例如只有1、2次）那还好点，但一旦超过5、6次，恐怕人脑的“堆栈”就要溢出了。

好了，牢骚完毕，来解释一下：


Find()：如果树为空，则返回NULL；如果根结点比它的左儿子要小，就往左进行，否则如果比右儿子小就往右进行，一直到既不大于也不小于它的儿子为止，那么这个结点就一定是我们要找的了。

FindMin()：从根结点开始，只要有左儿子就向左进行，直到遇到终止结点为止。

FindMax()：除分支朝右儿子进行外，其余过程与FindMin()相同。

Insert()：如果找到了相同的元素，则什么都不做；否则，递归查找到遍历路径的最后一点上，然后执行Insert操作。

Delete()：正如许多数据结构一样，最困难的操作是删除。删除的操作可以分成下面几种情况：

如果结点是一片树叶，那么它可以被立即删除。

如果结点有一个儿子，那么该结点可以在其父结点调整指针绕过该结点后被删除。

最复杂的情况是处理具有两个儿子的结点。我们可以用其右子树的最小的数据（很容易找到）代替该结点的数据，并递归地删除那个结点。为什么？因为一个结点肯定比它的右子树的所有结点都小，同时又比它的左子树的所有结点都大，所以我们只要在其右子树中找到最小的那个结点来代替它，就能满足二叉树的性质了。（根据这个规则，我们还可以用其左子树的最大的数据来代替该结点的数据，道理是一样的，不再叙述）



说了那么多，估计我还是没有讲清楚（主要是有点抽象），请读者编译我的代码并亲自动手调试一下吧。我的测试代码没有输出结果，因为要写个打印二叉树的函数我觉得有点烦，您可以在相应的函数中下断点，我个人认为只要能弄懂Delete()函数，那别的应该都没问题了。:)

第十章

AVL树

10.1  基本概念
AVL树的复杂程度真是比二叉搜索树高了整整一个数量级——它的原理并不难弄懂，但要把它用代码实现出来还真的有点费脑筋。下面我们来看看：


10.1.1  AVL树是什么？
AVL树本质上还是一棵二叉搜索树（因此读者可以看到我后面的代码是继承自二叉搜索树的），它的特点是：


本身首先是一棵二叉搜索树。

带有平衡条件：每个结点的左右子树的高度之差的绝对值（平衡因子）最多为1。


例如：


     5              5
    / \\            / \\
   2   6          2   6
  / \\   \\        / \\
1   4   7      1   4
    /              /
   3              3


上图中，左边的是AVL树，而右边的不是。因为左边的树的每个结点的左右子树的高度之差的绝对值都最多为1，而右边的树由于结点6没有子树，导致根结点5的平衡因子为2。


10.1.2  为什么要用AVL树？
有人也许要问：为什么要有AVL树呢？它有什么作用呢？

我们先来看看二叉搜索树吧（因为AVL树本质上是一棵二叉搜索树），假设有这么一种极端的情况：二叉搜索树的结点为1、2、3、4、5，也就是：


1
  \\
   2
    \\
     3
      \\
       4
        \\
         5


聪明的你是不是发现什么了呢？呵呵，显而易见——这棵二叉搜索树其实等同于一个链表了，也就是说，它在查找上的优势已经全无了——在这种情况下，查找一个结点的时间复杂度是O(N)！

好，那么假如是AVL树（别忘了AVL树还是二叉搜索树），则会是：


   2
  / \\
1   4
    / \\
   3   5


可以看出，AVL树的查找平均时间复杂度要比二叉搜索树低——它是O(logN)。也就是说，在大量的随机数据中AVL树的表现要好得多。


10.1.3  旋转
假设有一个结点的平衡因子为2（在AVL树中，最大就是2，因为结点是一个一个地插入到树中的，一旦出现不平衡的状态就会立即进行调整，因此平衡因子最大不可能超过2），那么就需要进行调整。由于任意一个结点最多只有两个儿子，所以当高度不平衡时，只可能是以下四种情况造成的：


对该结点的左儿子的左子树进行了一次插入。

对该结点的左儿子的右子树进行了一次插入。

对该结点的右儿子的左子树进行了一次插入。

对该结点的右儿子的右子树进行了一次插入。


情况1和4是关于该点的镜像对称，同样，情况2和3也是一对镜像对称。因此，理论上只有两种情况，当然了，从编程的角度来看还是四种情况。

第一种情况是插入发生在“外边”的情况（即左-左的情况或右-右的情况），该情况可以通过对树的一次单旋转来完成调整。第二种情况是插入发生在“内部”的情况（即左-右的情况或右-左的情况），该情况要通过稍微复杂些的双旋转来处理。

关于旋转的具体理论分析和例子请参阅教科书，我实在不想在这里重新打一次了……就此省略65535个字，原谅我吧，出来混，迟早要还的。


10.2  代码实现
二叉树的代码实现如下：


///////////////////////////////////////////////////////////////////////////////
//
//  FileName    :   avltree.h
//  Version     :   0.10
//  Author      :   Luo Cong
//  Date        :   2005-1-20 17:04:31
//  Comment     :  
//
///////////////////////////////////////////////////////////////////////////////

#ifndef __AVL_TREE_H__
#define __AVL_TREE_H__

#include \\"../../bstree/src/bstree.h\\"

template<typename T>
class CAVLTree : public CBSTree<T>
{
private:
    CBTNode<T>* Insert(const T &data, CBTNode<T> *p);

public:
    CBTNode<T>* SingleRotateWithLeft(CBTNode<T> *p);
    CBTNode<T>* DoubleRotateWithLeft(CBTNode<T> *p);
    CBTNode<T>* SingleRotateWithRight(CBTNode<T> *p);
    CBTNode<T>* DoubleRotateWithRight(CBTNode<T> *p);
    CBTNode<T>* Insert(const T &data);
    CBTNode<T>* Delete(const T &data);
};

template<typename T>
inline CBTNode<T>* CAVLTree<T>::SingleRotateWithLeft(CBTNode<T> *p)
{
    CBTNode<T> *p2;

    // rotate
    p2 = p->left;
    p->left = p2->right;
    p2->right = p;

    // update parent relationship
    p2->parent = p->parent;
    p->parent = p2;
    if (p->left)
        p->left->parent = p;

    // update root node if necessary
    if (p == m_pNodeRoot)
        m_pNodeRoot = p2;

    return p2;  // New root
}

template<typename T>
inline CBTNode<T>* CAVLTree<T>::DoubleRotateWithLeft(CBTNode<T> *p)
{
    p->left = SingleRotateWithLeft(p->left);
    return SingleRotateWithLeft(p);
}

template<typename T>
inline CBTNode<T>* CAVLTree<T>::SingleRotateWithRight(CBTNode<T> *p)
{
    CBTNode<T> *p2;

    // rotate
    p2 = p->right;
    p->right = p2->left;
    p2->left = p;

    // update parent relationship
    p2->parent = p->parent;
    p->parent = p2;
    if (p->right)
        p->right->parent = p;

    // update root node if necessary
    if (p == m_pNodeRoot)
        m_pNodeRoot = p2;

    return p2;  // New root
}

template<typename T>
inline CBTNode<T>* CAVLTree<T>::DoubleRotateWithRight(CBTNode<T> *p)
{
    p->right = SingleRotateWithLeft(p->right);
    return SingleRotateWithRight(p);
}

template<typename T>
inline CBTNode<T>* CAVLTree<T>::Insert(const T &data)
{
    return Insert(data, m_pNodeRoot);
}

template<typename T>
inline CBTNode<T>* CAVLTree<T>::Insert(const T &data, CBTNode<T> *p)
{
    if (NULL == p)
    {
        // Create and return a one-node tree
        p = new CBTNode<T>;
        if (NULL == p)
            return NULL;
        else
        {
            p->data = data;
            p->left = NULL;
            p->right = NULL;
            if (NULL == m_pNodeRoot)
            {
                m_pNodeRoot = p;
                m_pNodeRoot->parent = NULL;
            }
        }
    }
    // left child
    else if (data < p->data)
    {
        p->left = Insert(data, p->left);
        if (p->left)
            p->left->parent = p;

        if (2 == (GetDepth(p->left) - GetDepth(p->right)))
        {
            // left tree, need to do single rotation
            if (data < p->left->data)
                p = SingleRotateWithLeft(p);
            // right tree, need to do double rotation
            else
                p = DoubleRotateWithLeft(p);
        }
    }
    // right child
    else if (data > p->data)
    {
        p->right = Insert(data, p->right);
        if (p->right)
            p->right->parent = p;

        if (2 == (GetDepth(p->right) - GetDepth(p->left)))
        {
            // right tree, need to do single rotation
            if (data > p->right->data)
                p = SingleRotateWithRight(p);
            // left tree, need to do double rotation
            else
                p = DoubleRotateWithRight(p);
        }
    }
    // else data is in the tree already, we\'ll do nothing!

    return p;
}

template<typename T>
inline CBTNode<T>* CAVLTree<T>::Delete(const T &data)
{
    // not completed yet.
    return NULL;
}

#endif  // __AVL_TREE_H__

测试代码：


///////////////////////////////////////////////////////////////////////////////
//
//  FileName    :   avltree.cpp
//  Version     :   0.10
//  Author      :   Luo Cong
//  Date        :   2005-1-20 17:06:50
//  Comment     :  
//
///////////////////////////////////////////////////////////////////////////////

#include \\"avltree.h\\"

int main()
{
    CAVLTree<int> avltree;

#ifdef _DEBUG
    _CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);
#endif

    avltree.Insert(1);
    avltree.Insert(2);
    avltree.Insert(3);
    avltree.Insert(4);
}

10.3  说明
我的AVL树是从二叉搜索树继承而来的（还记得我的二叉搜索树又是从二叉树继承来的吗？^_^）。另外，由于水平的关系，我没有写出Delete()函数来，因此如果您使用了Delete()，那是不会有效果的。-_-b...

插入的核心思路是通过递归（又是递归！）找到合适的位置，插入新结点，然后看新结点是否平衡（平衡因子是否为2），如果不平衡的话，就分成两种大情况以及两种小情况：


在结点的左儿子(data < p->data)

在左儿子的左子树((data < p->data) AND (data < p->left->data))，“外边”，要做单旋转。

在左儿子的右子树((data < p->data) AND (data > p->left->data0))，“内部”，要做双旋转。


在结点的右儿子(data > p->data)

在右儿子的左子树((data > p->data) AND (data < p->right->data))，“内部”，要做双旋转。

在右儿子的右子树((data > p->data) AND (data > p->right->data))，“外边”，要做单旋转。



代码已经写得很清楚了，我就不多废话了，关键在于动手去调试，这样才能弄明白。值得说明的是，当进行了旋转之后，必定会有结点的“父结点”是需要更新的，例如：


   2
  / \\
1   4
    / \\
   3   5
        \\
         6


上图是调整前的，下图是调整后的：


     4
    / \\
   2   5
  / \\   \\
1   3   6


可以看出，根结点2不平衡，是由于它的右儿子的右子树插入了新的结点6造成的。因此，这属于“外边”的情况，要进行一次单旋转。于是我们就把结点4调整上来作为根结点，再把结点2作为4的左儿子，最后把结点2的右儿子修改为原来的结点4的左儿子。

调整后的parent指针变化规律如下：


调整前的右儿子（调整后它就变为父亲了）的parent指针应该指向调整前的父亲（调整后它就变成左儿子了）的parent指针。

调整前的父亲（调整后它就变成左儿子了）的parent指针应该指向调整前的右儿子（调整后它就变成父亲了）。

调整前的父亲的右儿子的parent指针应该指向调整前的右儿子的左儿子。


很难理解是吗？我来联系到上图说明：


调整前的右儿子是结点4，调整后，它的parent指针应该指向调整前它的父亲的parent指针，也就是NULL，因为调整前结点4的父亲是结点2，而结点2是根结点，其parent指针为NULL。

调整前的父亲是结点2，调整后，它的parent指针应该指向调整前的右儿子（结点4）。

调整前的父亲的右儿子（也就是调整后的结点2的右儿子）应该指向调整前的右儿子（结点4）的左儿子（结点3）。


这是SingleRotateWithRight()里面对parent指针的处理，SingleRotateWithLeft()里面的道理也是相通的，只是顺序有点不同。

呵呵，希望没把您弄晕。^_^

AVL树就讲到这里了，如果您有兴趣，可以把Delete()函数写完，并请给我一份以便我学习。

第十一章

排序

11.1  基本概念
排序可以说是百花齐放，据算法宗师高德纳爷爷的《TAOCP》第三卷所记载的至少就有20多种。从大的方面来说，排序可以分成内排序和外排序——内排序是外排序的基础。我们常用的内排序又可以粗略分成下面的类型：


插入排序

交换排序

堆排序

归并排序


别看排序有那么多种类型，但它们都离不开这样的核心思想：


|有序序列区|无序序列区|


一个待排序列总是被不断从无序序列转变为有序序列。

从效率来说，目前已知最快的排序方法是“快速排序（QuickSort）”。牛B吧？呵呵，连名字都起得那么牛。（别的排序方法的名称要么是表示出它的本质（例如“插入排序”），要么是以其发明者命名的（例如“ShellSort”），只有QuickSort是直言不讳地用“Quick”来命名，这或许就是在排序上的最高荣誉吧！）

但要注意的是，没有一种排序方法的效率是在任何情况下都能独占鳌头的，具体采取哪种方法要根据实际情况而定（有的人喜欢用快速排序通吃各种情况，这有点像是赌博了，呵呵）。我举个例子，假设要在10000个随机的数据中找出最大的10个数，那么采用堆排序应该是最合适的，因为：第一，经验指出堆排序是一个非常稳定的算法，在各种环境中其效率变化不会太大；第二，堆排序的特性决定了只要构建一棵根节点为最大数的优先队列树，然后取其前10个根节点就行了。

该说的基本上就说完了，我不想重复敲入书上的话，各种排序算法的具体解释请参阅教科书，下面给出代码。


11.2  代码实现
各种排序的代码实现如下：


///////////////////////////////////////////////////////////////////////////////
//
//  FileName    :   sort.h
//  Version     :   0.10
//  Author      :   Luo Cong
//  Date        :   2005-1-23 16:49:42
//  Comment     :  
//
///////////////////////////////////////////////////////////////////////////////

#ifndef __SORT_H__
#define __SORT_H__

template&lt;typename T&gt;
class CSort
{
private:
    // the following three functions are for HeapSort():
    int  LeftChild(const int i);
    void PercDown(T x[], int i, const int n);
    void Swap(T *l, T *r);
    // the following two functions are for MergeSort():
    void MSort(T x[], T tmp[], int left, int right);
    void Merge(T x[], T tmp[], int lpos, int rpos, int rightend);
    // for QuickSort():
    T Median3(T x[], const int left, const int right);

public:
    void InsertSort(T x[], const int n);
    void ShellSort(T x[], const int n);
    void HeapSort(T x[], const int n);
    void MergeSort(T x[], int n);
    void QuickSort(T x[], int left, int right);
};

template&lt;typename T&gt;
inline void CSort&lt;T&gt;::InsertSort(T x[], const int n)
{
    int i;
    int j;
    T tmp;

    for (i = 0; i &lt; n; ++i)
    {
        tmp = x;             // copy it first
        for (j = i; j &gt; 0; --j) // unsorted region; (0 ~ (i - 1)) is sorted
            if (x[j - 1] &gt; tmp)
                x[j] = x[j - 1];// move back elements to empty a right position
            else
                break;          // we got it! x[j] is the right position
        x[j] = tmp;             // place it to the right position
    }
}

template&lt;typename T&gt;
inline void CSort&lt;T&gt;::ShellSort(T x[], const int n)
{
    int i;
    int j;
    int nIncrement;
    T tmp;

    for (nIncrement = n / 2; nIncrement &gt; 0; nIncrement /= 2)
    {
        for (i = nIncrement; i &lt; n; ++i)
        {
            tmp = x;
            for (j = i; j &gt;= nIncrement; j -= nIncrement)
            {
                if (tmp &lt; x[j - nIncrement])
                    x[j] = x[j - nIncrement];
                else
                    break;
            }
            x[j] = tmp;
        }
    }
}

template&lt;typename T&gt;
inline int CSort&lt;T&gt;::LeftChild(const int i)
{
    return (2 * i + 1);
}

template&lt;typename T&gt;
inline void CSort&lt;T&gt;::PercDown(T x[], int i, const int n)
{
    int nChild;
    T tmp;

    for (tmp = x; LeftChild(i) &lt; n; i = nChild)
    {
        nChild = LeftChild(i);
        if ((nChild != n - 1) &amp;&amp; (x[nChild + 1] &gt; x[nChild]))
            ++nChild;
        if (tmp &lt; x[nChild])
            x = x[nChild];
        else
            break;
    }
    x = tmp;
}

template&lt;typename T&gt;
inline void CSort&lt;T&gt;::Swap(T *l, T *r)
{
    T tmp = *l;
    *l = *r;
    *r = tmp;
}

template&lt;typename T&gt;
inline void CSort&lt;T&gt;::HeapSort(T x[], const int n)
{
    int i;

    for (i = n / 2; i &gt;= 0; --i)    // build heap
        PercDown(x, i, n);
    for (i = n - 1; i &gt; 0; --i)
    {
        Swap(&amp;x[0], &amp;x);         // delete max
        PercDown(x, 0, i);
    }
}

template&lt;typename T&gt;
inline void CSort&lt;T&gt;::Merge(T x[], T tmp[], int lpos, int rpos, int rightend)
{
    int i;
    int leftend;
    int numelements;
    int tmppos;

    leftend = rpos - 1;
    tmppos = lpos;
    numelements = rightend - lpos + 1;

    // main loop
    while ((lpos &lt;= leftend) &amp;&amp; (rpos &lt;= rightend))
    {
        if (x[lpos] &lt;= x[rpos])
            tmp[tmppos++] = x[lpos++];
        else
            tmp[tmppos++] = x[rpos++];
    }

    while (lpos &lt;= leftend)     // copy rest of first half
        tmp[tmppos++] = x[lpos++];
    while (rpos &lt;= rightend)    // copy rest of second half
        tmp[tmppos++] = x[rpos++];

    // copy tmp back
    for (i = 0; i &lt; numelements; ++i, --rightend)
        x[rightend] = tmp[rightend];
}

template&lt;typename T&gt;
inline void CSort&lt;T&gt;::MSort(T x[], T tmp[], int left, int right)
{
    int center;

    if (left &lt; right)
    {
        center = (left + right) / 2;
        MSort(x, tmp, left, center);
        MSort(x, tmp, center + 1, right);
        Merge(x, tmp, left, center + 1, right);
    }
}

template&lt;typename T&gt;
inline void CSort&lt;T&gt;::MergeSort(T x[], int n)
{
    T *tmp;

    tmp = new (T[n * sizeof(T)]);
    if (NULL != tmp)
    {
        MSort(x, tmp, 0, n - 1);
        delete tmp;
    }
}

template&lt;typename T&gt;
inline T CSort&lt;T&gt;::Median3(T x[], const int left, const int right)
{
    int center = (left + right) / 2;

    if (x[left] &gt; x[center])
        Swap(&amp;x[left], &amp;x[center]);
    if (x[left] &gt; x[right])
        Swap(&amp;x[left], &amp;x[right]);
    if (x[center] &gt; x[right])
        Swap(&amp;x[center], &amp;x[right]);

    // invariant: x[left] &lt;= x[center] &lt;= x[right]

    Swap(&amp;x[center], &amp;x[right - 1]);    // hide pivot
    return x[right - 1];                // return pivot
}

template&lt;typename T&gt;
inline void CSort&lt;T&gt;::QuickSort(T x[], int left, int right)
{
    int i;
    int j;
    int cutoff = 3;
    T pivot;

    if (left + cutoff &lt;= right)
    {
        pivot = Median3(x, left, right);
        i = left;
        j = right - 1;
        for (;;)
        {
            while (x[++i] &lt; pivot) {}
            while (x[--j] &gt; pivot) {}
            if (i &lt; j)
                Swap(&amp;x, &amp;x[j]);
            else
                break;
        }
        Swap(&amp;x, &amp;x[right - 1]); // restore pivot
        QuickSort(x, left, i - 1);
        QuickSort(x, i + 1, right);
    }
    else    // do an insertion sort on the subarray
        InsertSort(x + left, right - left + 1);
}

#endif  // __SORT_H__

测试代码：


///////////////////////////////////////////////////////////////////////////////
//
//  FileName    :   sort.cpp
//  Version     :   0.10
//  Author      :   Luo Cong
//  Date        :   2005-1-23 16:49:39
//  Comment     :  
//
///////////////////////////////////////////////////////////////////////////////

#include \\&quot;sort.h\\&quot;

int main()
{
    int x[] = {2, 9, 1, 6, 4, 8, 10, 7, 3, 5};
    CSort&lt;int&gt; sort;

    sort.QuickSort(x, 0, 9);
    // sort.ShellSort(x, 10);
}

第十二章

图的储存

12.1  基本概念
图（Graph）是数据结构中的最后一个“堡垒”——攻下它，数据结构就结束了。但就像在打游戏的最终BOSS一样，BOSS肯定是最强的，图也一样，它比线性表和树都更为复杂。在线性表中，数据元素间仅有线性关系，每个数据元素只有一个直接前驱和一个直接后继，也就是“一对一”的关系；在树形结构中，数据元素之间有着比较明显的层次关系，并且每一层上的数据元素可能和下一层中多个元素（儿子）相关，但只能和上一层中的一个元素（父亲）相关，也就是它是“一对多”的关系。到了图形结构中，数据元素之间的关系就可以是任意的，图中任意两个数据元素之间都可能相关，即“多对多”的关系。因此，图在200多年的发展中，应用极其广泛。这也造成了大部分高级的算法分析都不可避免地要用到图的知识。

不管图形结构有多复杂，我们要做的第一步必定是要先把它用某种结构储存起来。关于这一点，我们在树里面已经有了体会——对树的学习，关键是学习如何建树以及排序。我们要透过现象看本质，别看书里唧歪了半天，列了好多种储存图的方法，但其核心其实只有一个，那就是邻接矩阵（Adjacency Matrix）。但邻接矩阵的缺点是它对空间的耗费比较大，因为它是用一个二维数组来储存图的顶点和边的信息的——如果有N个顶点，则需要有N ^ 2的空间来储存。因此，如果图是稀疏的，那么我们就可以用邻接表（Adjacency List）来储存它，充分发挥链表的动态规划空间的优点。

下面我就分别给出这两种结构的代码实现。其中，邻接表使用了前面所写的单链表的类，因此在具体的实现上并不会太困难。另外，由于图结构本身比较复杂的原因，我无法把基类写得十分具有通用性，但它们应该已经可以基本满足后面的学习的需要了。


12.2  邻接矩阵

///////////////////////////////////////////////////////////////////////////////
//
//  FileName    :   MatrixGraph.h
//  Version     :   0.10
//  Author      :   Luo Cong
//  Date        :   2005-1-27 0:01:12
//  Comment     :  
//
///////////////////////////////////////////////////////////////////////////////

#ifndef __MATRIX_GRAPH_H__
#define __MATRIX_GRAPH_H__

#include &lt;iostream&gt;
using namespace std;

#include &lt;assert.h&gt;
#include &lt;crtdbg.h&gt;

#ifdef _DEBUG
#define DEBUG_NEW new (_NORMAL_BLOCK, THIS_FILE, __LINE__)
#endif

#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif

#ifdef _DEBUG
#ifndef ASSERT
#define ASSERT  assert
#endif
#else   // not _DEBUG
#ifndef ASSERT
#define ASSERT
#endif
#endif  // _DEBUG

template&lt;typename T_Vertex, typename T_Edge&gt;
class CMatrixGraph
{
    friend ostream&amp; operator&lt;&lt;(ostream &amp;os, CMatrixGraph&lt;T_Vertex, T_Edge&gt; &amp;g);

private:
    int m_nVertexNum;
    int m_nEdgeNum;
    int m_nMaxVertexNum;
    T_Vertex *m_Vertex;
    T_Edge **m_Edge;
    T_Vertex m_NoVertex;
    T_Edge m_NoEdge;

public:
    CMatrixGraph(const int nMaxVertexNum);
    ~CMatrixGraph();

public:
    int GetVertexNum() const;
    int GetEdgeNum() const;
    T_Vertex&amp; GetVertexAt(const int n);
    T_Vertex  GetVertexAt(const int n) const;
    T_Edge&amp; GetEdgeAt(const int nVertexIndex, const int n);
    T_Edge  GetEdgeAt(const int nVertexIndex, const int n) const;
    int Find(const T_Vertex &amp;v, int *nIndex = NULL) const;
    int InsertVertex(const T_Vertex &amp;v);
    int InsertEdge(const T_Vertex &amp;v1, const T_Vertex &amp;v2, const T_Edge &amp;e);
    int GetFirstAdjVertexIndex(const int n) const;
    int GetNextAdjVertexIndex(const int n, const int nn) const;
};

template&lt;typename T_Vertex, typename T_Edge&gt;
inline CMatrixGraph&lt;T_Vertex, T_Edge&gt;::CMatrixGraph(const int nMaxVertexNum)
                                     : m_nVertexNum(0),
                                       m_nEdgeNum(0),
                                       m_nMaxVertexNum(nMaxVertexNum),
                                       m_NoVertex(0), // this can be customized
                                       m_NoEdge(0)    // this can be customized
{
    int i;

    m_Edge = new T_Edge*[nMaxVertexNum];
    if (NULL == m_Edge)
        return;

    for (i = 0; i &lt; nMaxVertexNum; ++i)
    {
        m_Edge = new T_Edge[nMaxVertexNum];
    }

    m_Vertex = new T_Vertex[nMaxVertexNum];
}

template&lt;typename T_Vertex, typename T_Edge&gt;
inline CMatrixGraph&lt;T_Vertex, T_Edge&gt;::~CMatrixGraph()
{
    int i;

    delete[] m_Vertex;

    for (i = 0; i &lt; m_nMaxVertexNum; ++i)
    {
        delete[] m_Edge;
    }
    delete[] m_Edge;
}

template&lt;typename T_Vertex, typename T_Edge&gt;
inline int CMatrixGraph&lt;T_Vertex, T_Edge&gt;::Find(
    const T_Vertex &amp;v,
    int *nIndex
) const
{
    int i;
    int nVertexNum = m_nVertexNum;

    for (i = 0; i &lt; nVertexNum; ++i)
    {
        if (v == m_Vertex)
        {
            if (nIndex)
                *nIndex = i;
            return 1;
        }
    }
    return 0;
}

template&lt;typename T_Vertex, typename T_Edge&gt;
inline int CMatrixGraph&lt;T_Vertex, T_Edge&gt;::InsertVertex(const T_Vertex &amp;v)
{
    int i;

    if ((m_nVertexNum &gt;= m_nMaxVertexNum) || Find(v))
        return 0;

    m_Vertex[m_nVertexNum] = v;

    for (i = 0; i &lt; m_nMaxVertexNum; ++i)
        m_Edge[m_nVertexNum] = m_NoEdge;

    ++m_nVertexNum;

    return 1;
}

template&lt;typename T_Vertex, typename T_Edge&gt;
inline int CMatrixGraph&lt;T_Vertex, T_Edge&gt;::InsertEdge(
    const T_Vertex &amp;v1,
    const T_Vertex &amp;v2,
    const T_Edge &amp;e
)
{
    int nIndexV1;
    int nIndexV2;

    if (
        (v1 == v2) ||
        (!Find(v1, &amp;nIndexV1)) ||
        (!Find(v2, &amp;nIndexV2)) ||
        (m_Edge[nIndexV1][nIndexV2] != m_NoEdge)
    )
        return 0;

    m_Edge[nIndexV1][nIndexV2] = e;
    ++m_nEdgeNum;

    return 1;
}

template&lt;typename T_Vertex, typename T_Edge&gt;
inline T_Edge&amp; CMatrixGraph&lt;T_Vertex, T_Edge&gt;::GetEdgeAt(
    const int nVertexIndex,
    const int n
)
{
    if ((0 &gt; nVertexIndex) || (nVertexIndex &gt;= m_nMaxVertexNum))
        return m_NoEdge;

    if ((0 &gt; n) || (n &gt;= m_nMaxVertexNum))
        return m_NoEdge;

    return *(&amp;m_Edge[nVertexIndex][n]);
}

template&lt;typename T_Vertex, typename T_Edge&gt;
inline T_Edge CMatrixGraph&lt;T_Vertex, T_Edge&gt;::GetEdgeAt(
    const int nVertexIndex,
    const int n
) const
{
    if ((0 &gt; nVertexIndex) || (nVertexIndex &gt;= m_nMaxVertexNum))
        return m_NoEdge;

    if ((0 &gt; n) || (n &gt;= m_nMaxVertexNum))
        return m_NoEdge;

    return m_Edge[nVertexIndex][n];
}

template&lt;typename T_Vertex, typename T_Edge&gt;
inline T_Vertex&amp; CMatrixGraph&lt;T_Vertex, T_Edge&gt;::GetVertexAt(const int n)
{
    if ((0 &gt; n) || (n &gt;= m_nMaxVertexNum))
        return m_NoVertex;
    else
        return *(&amp;m_Vertex[n]);
}

template&lt;typename T_Vertex, typename T_Edge&gt;
inline T_Vertex CMatrixGraph&lt;T_Vertex, T_Edge&gt;::GetVertexAt(const int n) const
{
    if ((0 &gt; n) || (n &gt;= m_nMaxVertexNum))
        return m_NoVertex;
    else
        return m_Vertex[n];
}

template&lt;typename T_Vertex, typename T_Edge&gt;
inline int CMatrixGraph&lt;T_Vertex, T_Edge&gt;::GetVertexNum() const
{
    return m_nVertexNum;
}

template&lt;typename T_Vertex, typename T_Edge&gt;
inline int CMatrixGraph&lt;T_Vertex, T_Edge&gt;::GetEdgeNum() const
{
    return m_nEdgeNum;
}

template&lt;typename T_Vertex, typename T_Edge&gt;
inline int CMatrixGraph&lt;T_Vertex, T_Edge&gt;::GetFirstAdjVertexIndex(
    const int n
) const
{
    int i;

    for (i = 0; i &lt; m_nVertexNum; ++i)
    {
        if (m_Edge[n] != m_NoEdge)
            return i;
    }
    return -1;
}

template&lt;typename T_Vertex, typename T_Edge&gt;
inline int CMatrixGraph&lt;T_Vertex, T_Edge&gt;::GetNextAdjVertexIndex(
    const int n,
    const int nn
) const
{
    int i;

    for (i = nn + 1; i &lt; m_nVertexNum; ++i)
    {
        if (m_Edge[n] != m_NoEdge)
            return i;
    }
    return -1;
}

template&lt;typename T_Vertex, typename T_Edge&gt;
inline ostream &amp;operator&lt;&lt;(ostream &amp;os, CMatrixGraph&lt;T_Vertex, T_Edge&gt; &amp;g)
{
    int i;
    int j;
    int nVertexNum;

    nVertexNum = g.GetVertexNum();
    for (i = 0; i &lt; nVertexNum; ++i)
    {
        for (j = 0; j &lt; nVertexNum; ++j)
        {
            os &lt;&lt; g.GetEdgeAt(i, j) &lt;&lt; \' \';
        }
        os &lt;&lt; endl;
    }

    return os;
}

#endif  // __MATRIX_GRAPH_H__

测试代码：


///////////////////////////////////////////////////////////////////////////////
//
//  FileName    :   MatrixGraph.cpp
//  Version     :   0.10
//  Author      :   Luo Cong
//  Date        :   2005-1-27 0:02:03
//  Comment     :  
//
///////////////////////////////////////////////////////////////////////////////

#include \\&quot;MatrixGraph.h\\&quot;

int main()
{
    CMatrixGraph&lt;int, int&gt; mgraph(4);

#ifdef _DEBUG
    _CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);
#endif

    // (1)－－&gt;(2)
    // ｜↖
    // ｜  ﹨
    // ↓    ﹨
    // (3)－－&gt;(4)
    mgraph.InsertVertex(1);
    mgraph.InsertVertex(2);
    mgraph.InsertVertex(3);
    mgraph.InsertVertex(4);
    mgraph.InsertEdge(1, 2, 1);
    mgraph.InsertEdge(1, 3, 1);
    mgraph.InsertEdge(3, 4, 1);
    mgraph.InsertEdge(4, 1, 1);

    cout &lt;&lt; mgraph &lt;&lt; endl;
}


12.3  邻接链表

///////////////////////////////////////////////////////////////////////////////
//
//  FileName    :   ListGraph.h
//  Version     :   0.10
//  Author      :   Luo Cong
//  Date        :   2005-1-27 10:26:20
//  Comment     :  
//
///////////////////////////////////////////////////////////////////////////////

#ifndef __LIST_GRAPH_H__
#define __LIST_GRAPH_H__

#include &lt;iostream&gt;
using namespace std;

#include \\&quot;../../slist/src/slist.h\\&quot;

template&lt;typename T_Vertex, typename T_Edge&gt;
class CListGraph
{
    friend ostream&amp; operator&lt;&lt;(ostream &amp;os, CListGraph&lt;T_Vertex, T_Edge&gt; &amp;g);

private:
    typedef struct tagLGEdge
    {
        int nextvertexindex;
        T_Edge edata;
    } LGEdge;

    typedef struct tagLGVertex
    {
        T_Vertex vdata;
        CSList&lt;LGEdge&gt; *edgelist;
    } LGVertex;

    int m_nVertexNum;
    int m_nEdgeNum;
    CSList&lt;LGVertex&gt; m_Vertex;

public:
    CListGraph();
    ~CListGraph();
    void Output(ostream &amp;os) const;

private:
    int GetVertexAt(const int n, LGVertex *vertex) const;
    int GetEdgeAt(const int nVertexIndex, const int n, LGEdge *edge) const;

public:
    int GetVertexNum() const;
    int GetEdgeNum() const;
    int GetVertexAt(const int n, T_Vertex *v) const;
    int GetEdgeAt(const int nVertexIndex, const int n, T_Edge *e) const;
    T_Edge GetEdgeAt(const int nVertexIndex, const int n) const;
    int Find(const T_Vertex &amp;v, int *nIndex = NULL) const;
    int InsertVertex(const T_Vertex &amp;v);
    int InsertEdge(const T_Vertex &amp;v1, const T_Vertex &amp;v2, const T_Edge &amp;e);
    int GetFirstAdjVertexIndex(const int n) const;
    int GetNextAdjVertexIndex(const int n, const int nn) const;
};

template&lt;typename T_Vertex, typename T_Edge&gt;
inline CListGraph&lt;T_Vertex, T_Edge&gt;::CListGraph()
                                   : m_nVertexNum(0),
                                     m_nEdgeNum(0)
{
}

template&lt;typename T_Vertex, typename T_Edge&gt;
inline CListGraph&lt;T_Vertex, T_Edge&gt;::~CListGraph()
{
    int i;
    int nVertexNum = m_nVertexNum;
    CSList&lt;LGEdge&gt; *edgelist;

    for (i = 0; i &lt; nVertexNum; ++i)
    {
        edgelist = m_Vertex.GetAt(i + 1).edgelist;
        if (edgelist)
        {
            edgelist-&gt;RemoveAll();
            delete edgelist;
        }
    }
}

template&lt;typename T_Vertex, typename T_Edge&gt;
inline int CListGraph&lt;T_Vertex, T_Edge&gt;::GetVertexNum() const
{
    return m_nVertexNum;
}

template&lt;typename T_Vertex, typename T_Edge&gt;
inline int CListGraph&lt;T_Vertex, T_Edge&gt;::GetEdgeNum() const
{
    return m_nEdgeNum;
}

template&lt;typename T_Vertex, typename T_Edge&gt;
inline int CListGraph&lt;T_Vertex, T_Edge&gt;::GetVertexAt(
    const int n,
    LGVertex *vertex
) const
{
    ASSERT(vertex);

    if ((0 &gt; n) || (n &gt;= m_Vertex.GetCount()))
        return 0;

    *vertex = m_Vertex.GetAt(n + 1);
    return 1;
}

template&lt;typename T_Vertex, typename T_Edge&gt;
inline int CListGraph&lt;T_Vertex, T_Edge&gt;::GetVertexAt(
    const int n,
    T_Vertex *v
) const
{
    ASSERT(v);

    LGVertex vertex;

    if (GetVertexAt(n, &amp;vertex))
    {
        *v = vertex.vdata;
        return 1;
    }
    else
        return 0;
}

template&lt;typename T_Vertex, typename T_Edge&gt;
inline int CListGraph&lt;T_Vertex, T_Edge&gt;::GetEdgeAt(
    const int nVertexIndex,
    const int n,
    LGEdge *edge
) const
{
    ASSERT(edge);

    LGVertex vertex;
    int nVertexEdgelistCount;

    if (0 == GetVertexAt(nVertexIndex, &amp;vertex))
        return 0;

    if (vertex.edgelist)
        nVertexEdgelistCount = vertex.edgelist-&gt;GetCount();
    else
        return 0;

    if (
        (0 &gt; n) ||
        (n &gt;= nVertexEdgelistCount)
    )
        return 0;

    *edge = vertex.edgelist-&gt;GetAt(n + 1);

    return 1;
}

template&lt;typename T_Vertex, typename T_Edge&gt;
inline int CListGraph&lt;T_Vertex, T_Edge&gt;::GetEdgeAt(
    const int nVertexIndex,
    const int n,
    T_Edge *e
) const
{
    ASSERT(e);

    LGEdge edge;

    if (GetEdgeAt(nVertexIndex, n, &amp;edge))
    {
        *e = edge.edata;
        return 1;
    }
    else
        return 0;
}

template&lt;typename T_Vertex, typename T_Edge&gt;
inline int CListGraph&lt;T_Vertex, T_Edge&gt;::Find(
    const T_Vertex &amp;v,
    int *nIndex
) const
{
    int i;
    int nVertexNum = m_nVertexNum;
    LGVertex vertex;

    for (i = 0; i &lt; nVertexNum; ++i)
    {
        vertex = m_Vertex.GetAt(i + 1);
        if (v == vertex.vdata)
        {
            if (nIndex)
                *nIndex = i;
            return 1;
        }
    }
    return 0;
}

template&lt;typename T_Vertex, typename T_Edge&gt;
inline int CListGraph&lt;T_Vertex, T_Edge&gt;::InsertVertex(const T_Vertex &amp;v)
{
    LGVertex vertex;

    if (Find(v))
        return 0;

    vertex.vdata = v;
    vertex.edgelist = NULL;
    m_Vertex.AddTail(vertex);
    ++m_nVertexNum;

    return 1;
}

template&lt;typename T_Vertex, typename T_Edge&gt;
inline int CListGraph&lt;T_Vertex, T_Edge&gt;::InsertEdge(
    const T_Vertex &amp;v1,
    const T_Vertex &amp;v2,
    const T_Edge &amp;e
)
{
    int i;
    int nIndexV1;
    int nIndexV2;
    LGEdge edge;
    CSList&lt;LGEdge&gt; *edgelist;
    int nVertexEdgelistCount;

    if (
        (v1 == v2) ||
        (!Find(v1, &amp;nIndexV1)) ||
        (!Find(v2, &amp;nIndexV2))
    )
        return 0;

    // if there\'s no edges, let\'s create it first
    edgelist = m_Vertex.GetAt(nIndexV1 + 1).edgelist;
    if (NULL == edgelist)
    {
        edgelist = new CSList&lt;LGEdge&gt;;
        m_Vertex.GetAt(nIndexV1 + 1).edgelist = edgelist;
    }

    // is there an edge between v1 and v2 already?
    nVertexEdgelistCount = edgelist-&gt;GetCount();
    for (i = 0; i &lt; nVertexEdgelistCount; ++i)
    {
        edge = edgelist-&gt;GetAt(i + 1);
        if (
            (edge.edata == e) &amp;&amp;
            (edge.nextvertexindex == nIndexV2)
        )
            return 0;
    }

    // new edge\'s data
    edge.edata = e;
    edge.nextvertexindex = nIndexV2;

    edgelist-&gt;AddTail(edge);

    ++m_nEdgeNum;

    return 1;
}

template&lt;typename T_Vertex, typename T_Edge&gt;
inline int CListGraph&lt;T_Vertex, T_Edge&gt;::GetFirstAdjVertexIndex(
    const int n
) const
{
    LGVertex vertex;

    if (0 == GetVertexAt(n, &amp;vertex))
        return -1;
    if (vertex.edgelist)
        return vertex.edgelist-&gt;GetHead().nextvertexindex;
    return -1;
}

template&lt;typename T_Vertex, typename T_Edge&gt;
inline int CListGraph&lt;T_Vertex, T_Edge&gt;::GetNextAdjVertexIndex(
    const int n,
    const int nn
) const
{
    LGEdge edge;
    LGVertex vertex;
    int nVertexEdgelistCount;

    if (0 == GetVertexAt(n, &amp;vertex))
        return -1;

    if (vertex.edgelist)
        nVertexEdgelistCount = vertex.edgelist-&gt;GetCount();
    else
        return -1;

    if (
        (0 &gt; nn) ||
        ((nn + 1) &gt;= nVertexEdgelistCount)
    )
        return -1;

    edge = vertex.edgelist-&gt;GetAt((nn + 1) + 1);

    return edge.nextvertexindex;
}

template&lt;typename T_Vertex, typename T_Edge&gt;
inline void CListGraph&lt;T_Vertex, T_Edge&gt;::Output(ostream &amp;os) const
{
    int i;
    int j;
    LGEdge edge;
    LGVertex vertex;
    int nVertexNum;
    int nVertexEdgelistCount;

    nVertexNum = GetVertexNum();
    for (i = 0; i &lt; nVertexNum; ++i)
    {
        if (0 == GetVertexAt(i, &amp;vertex))
            return ;
        os &lt;&lt; \\&quot;(V\\&quot; &lt;&lt; i + 1 &lt;&lt; \\&quot;) \\&quot;;
        os &lt;&lt; \'V\' &lt;&lt; vertex.vdata;
        if (vertex.edgelist)
            nVertexEdgelistCount = vertex.edgelist-&gt;GetCount();
        else
            nVertexEdgelistCount = 0;
        for (j = 0; j &lt; nVertexEdgelistCount; ++j)
        {
            os &lt;&lt; \\&quot; --&gt; \\&quot;;
            edge = vertex.edgelist-&gt;GetAt(j + 1);
            os &lt;&lt; \'V\' &lt;&lt; edge.nextvertexindex + 1;
        }
        os &lt;&lt; endl;
    }
}

template&lt;typename T_Vertex, typename T_Edge&gt;
inline ostream&amp; operator&lt;&lt;(ostream &amp;os, CListGraph&lt;T_Vertex, T_Edge&gt; &amp;g)
{
    g.Output(os);
    return os;
}

#endif  // __LIST_GRAPH_H__

测试代码：


///////////////////////////////////////////////////////////////////////////////
//
//  FileName    :   ListGraph.cpp
//  Version     :   0.10
//  Author      :   Luo Cong
//  Date        :   2005-1-27 10:27:55
//  Comment     :  
//
///////////////////////////////////////////////////////////////////////////////

#include \\&quot;ListGraph.h\\&quot;

int main()
{
    CListGraph&lt;int, int&gt; lgraph;

#ifdef _DEBUG
    _CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);
#endif

    // (1)－－&gt;(2)
    // ｜↖
    // ｜  ﹨
    // ↓    ﹨
    // (3)－－&gt;(4)
    lgraph.InsertVertex(1);
    lgraph.InsertVertex(2);
    lgraph.InsertVertex(3);
    lgraph.InsertVertex(4);
    lgraph.InsertEdge(1, 2, 1);
    lgraph.InsertEdge(1, 3, 1);
    lgraph.InsertEdge(3, 4, 1);
    lgraph.InsertEdge(4, 1, 1);

    cout &lt;&lt; lgraph &lt;&lt; endl;
}

第十三章

图的遍历

13.1  基本概念
解决了图的储存问题后，接下来的肯定就是解决如何去访问图上面的元素的问题了，也就是图的遍历。书里面对图的遍历是用深度优先搜索算法（Depth First Search，简称DFS）和广度优先搜索算法（Breadth First Search，简称BFS），其实说白了就是按照“分层”的思想来进行。深度优先就是先访问完最深层次的数据元素，广度优先就是先访问完同一层次的数据元素，它们的时间复杂度都是一样的，只是访问元素的顺序不同而已。


13.2  代码实现

///////////////////////////////////////////////////////////////////////////////
//
//  FileName    :   TraverseGraph.h
//  Version     :   0.10
//  Author      :   Luo Cong
//  Date        :   2005-1-29 16:28:44
//  Comment     :  
//
///////////////////////////////////////////////////////////////////////////////

#ifndef __TRAVERSE_GRAPH_H__
#define __TRAVERSE_GRAPH_H__

#include \\&quot;../../ListGraph/src/ListGraph.h\\&quot;
#include \\&quot;../../queue/src/lqueue.h\\&quot;

template&lt;typename T_Vertex, typename T_Edge&gt;
class CTraverseGraph : public CListGraph&lt;T_Vertex, T_Edge&gt;
{
protected:
    int *m_nVisited;

private:
    int InitializeVisited(const int n);
    void FinalizeVisited();
    void DFS(const int n, void (*Visit)(const T_Vertex &amp;vertex)) const;

public:
    void DFS(void (*Visit)(const T_Vertex &amp;vertex));
    void BFS(void (*Visit)(const T_Vertex &amp;vertex));
};

template&lt;typename T_Vertex, typename T_Edge&gt;
inline int CTraverseGraph&lt;T_Vertex, T_Edge&gt;::InitializeVisited(const int n)
{
    int i;

    m_nVisited = new int[n];
    if (NULL == m_nVisited)
        return 0;

    for (i = 0; i &lt; n; ++i)
        m_nVisited = 0;

    return 1;
}

template&lt;typename T_Vertex, typename T_Edge&gt;
inline void CTraverseGraph&lt;T_Vertex, T_Edge&gt;::FinalizeVisited()
{
    if (m_nVisited)
    {
        delete[] m_nVisited;
        m_nVisited = NULL;
    }
}

template&lt;typename T_Vertex, typename T_Edge&gt;
inline void CTraverseGraph&lt;T_Vertex, T_Edge&gt;::DFS(
    const int n,
    void (*Visit)(const T_Vertex &amp;vertex)
) const
{
    int i;
    int j = 0;
    int nRetCode;
    T_Vertex vertex;

    m_nVisited[n] = 1;

    nRetCode = GetVertexAt(n, &amp;vertex);
    if (0 == nRetCode)
        return ;
    Visit(vertex);

    i = GetFirstAdjVertexIndex(n);
    for (; i != -1; i = GetNextAdjVertexIndex(n, j++))
    {
        if (!m_nVisited)
            DFS(i, Visit);
    }
}

template&lt;typename T_Vertex, typename T_Edge&gt;
inline void CTraverseGraph&lt;T_Vertex, T_Edge&gt;::DFS(
    void (*Visit)(const T_Vertex &amp;vertex)
)
{
    int i;
    int nVertexNum;

    nVertexNum = GetVertexNum();

    if (!InitializeVisited(nVertexNum))
        return ;

    for (i = 0; i &lt; nVertexNum; ++i)
    {
        if (!m_nVisited)
            DFS(i, Visit);
    }

    FinalizeVisited();
}

template&lt;typename T_Vertex, typename T_Edge&gt;
inline void CTraverseGraph&lt;T_Vertex, T_Edge&gt;::BFS(
    void (*Visit)(const T_Vertex &amp;vertex)
)
{
    int i;
    int j;
    int k;
    int l;
    int nRetCode;
    int nVertexNum;
    T_Vertex vertex;
    CLQueue&lt;int&gt; queue;

    nVertexNum = GetVertexNum();

    if (!InitializeVisited(nVertexNum))
        return ;

    for (i = 0; i &lt; nVertexNum; ++i)
    {
        if (m_nVisited)
            continue;

        // visit vertex
        m_nVisited = 1;
        nRetCode = GetVertexAt(i, &amp;vertex);
        if (0 == nRetCode)
            return ;
        Visit(vertex);
        queue.EnQueue(i);

        // visit vertex\'s adjacency vertex(s)
        while (!queue.IsEmpty())
        {
            j = queue.DeQueue();    // equal to i above
            k = GetFirstAdjVertexIndex(j);
            l = 0;
            // adjacency vertex(s):
            for (; k != -1; k = GetNextAdjVertexIndex(j, l++))
            {
                if (!m_nVisited[k])
                {
                    m_nVisited[k] = 1;
                    nRetCode = GetVertexAt(k, &amp;vertex);
                    if (0 == nRetCode)
                        return ;
                    Visit(vertex);
                    queue.EnQueue(k);
                }
            }
        }
    }

    FinalizeVisited();
}

#endif  // __TRAVERSE_GRAPH_H__

测试代码：


///////////////////////////////////////////////////////////////////////////////
//
//  FileName    :   TraverseGraph.cpp
//  Version     :   0.10
//  Author      :   Luo Cong
//  Date        :   2005-1-29 16:30:34
//  Comment     :  
//
///////////////////////////////////////////////////////////////////////////////

#include \\&quot;TraverseGraph.h\\&quot;

typedef int ElementType;

static void PrintVertex(const ElementType &amp;vertex)
{
    cout &lt;&lt; \'V\' &lt;&lt; vertex &lt;&lt; \\&quot; --&gt; \\&quot;;
}

int main()
{
    CTraverseGraph&lt;ElementType, ElementType&gt; tgraph;

#ifdef _DEBUG
    _CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);
#endif

    //        (1)
    //        /  \\
    //       /    \\
    //      /      \\
    //    (2)      (3)
    //    / \\      / \\
    //   /   \\    /   \\
    // (4)   (5) (6)--(7)
    //   \\   /
    //    \\ /
    //    (8)
    tgraph.InsertVertex(1);
    tgraph.InsertVertex(2);
    tgraph.InsertVertex(3);
    tgraph.InsertVertex(4);
    tgraph.InsertVertex(5);
    tgraph.InsertVertex(6);
    tgraph.InsertVertex(7);
    tgraph.InsertVertex(8);
    // 因为CListGraph是一个有向图类，所以这里为了创建一个无向图，
    // 必须把每条边从入边和出边两个方向分别创建一次：
    tgraph.InsertEdge(1, 2, 1);
    tgraph.InsertEdge(2, 1, 1);
    tgraph.InsertEdge(1, 3, 1);
    tgraph.InsertEdge(3, 1, 1);
    tgraph.InsertEdge(2, 4, 1);
    tgraph.InsertEdge(4, 2, 1);
    tgraph.InsertEdge(2, 5, 1);
    tgraph.InsertEdge(5, 2, 1);
    tgraph.InsertEdge(3, 6, 1);
    tgraph.InsertEdge(6, 3, 1);
    tgraph.InsertEdge(3, 7, 1);
    tgraph.InsertEdge(7, 3, 1);
    tgraph.InsertEdge(6, 7, 1);
    tgraph.InsertEdge(7, 6, 1);
    tgraph.InsertEdge(4, 8, 1);
    tgraph.InsertEdge(8, 4, 1);
    tgraph.InsertEdge(5, 8, 1);
    tgraph.InsertEdge(8, 5, 1);

    cout &lt;&lt; \\&quot;Graph is:\\&quot; &lt;&lt; endl;
    cout &lt;&lt; tgraph &lt;&lt; endl;

    cout &lt;&lt; \\&quot;DFS Traverse:\\&quot; &lt;&lt; endl;
    tgraph.DFS(PrintVertex);
    cout &lt;&lt; \\&quot;NULL\\&quot; &lt;&lt; endl &lt;&lt; endl;

    cout &lt;&lt; \\&quot;BFS Traverse:\\&quot; &lt;&lt; endl;
    tgraph.BFS(PrintVertex);
    cout &lt;&lt; \\&quot;NULL\\&quot; &lt;&lt; endl;
}

13.3  说明
为了说明DFS和BFS，我另外写了一个类：CTraverseGraph，它继承于前面的邻接链表图类：CListGraph。呵呵，用C++的继承机制真是舒服啊，不用每次都重写一堆功能重复的代码了，而且它能更直观地表现出数据结构的ADT来，实在是居家旅行、跳槽单干的必备良器……嗯，扯远了，咳咳。另外，我之所以不把DFS和BFS这两个函数直接写到图的基类里面，是因为对图的遍历很难做到高度抽象的通用性，所以在这里就只写了一个试验级别的CTraverseGraph了，但是说实话，对于试验来说，它已经足够

over 全部转载完毕

很不错 ，真的 ，但是 可能对复习的后阶段主要是算法设计有用

有道理。。。得思索思索！

有道理。。。得思索思索！

有道理。。。得思索思索！