[首页, 上一页, 下一页;   目录 ]

第四章

循环链表

4.1  基本概念

循环链表可以为单链表，也可以为双链表，但我不想把问题搞得那么复杂，姑且就做单链表的循环形式吧。

我们在实现了链表后，必然会提出一个问题：链表能不能首尾相连？怎样实现？

答案：能。其实实现的方法很简单，就是将表中最后一个结点的指针域指向头结点即可（P->next = head;）。这种形成环路的链表称为循环链表。

试想我们在学校的运动场上跑步锻炼身体（学校……好遥远的记忆啊），绕着400米跑道一直跑啊跑，好像永远没有尽头一样。这是因为跑道的首尾是相连的，跑完一圈后，“尾巴”突然就变成了“头”，这跟循环链表的原理是一样的。好了，明白了这个道理，实现起来就简单了，不过要注意的是，在循环链表里面如果要获得结点的个数，不能采用while()循环来遍历表，因为这个循环是永不会结束的，这就像无论有多长的长跑比赛都可以在400米的跑道上进行一样。我的做法还是通过增加一个m_nCount变量，每次新增或删除一个结点就对m_nCount进行相应的操作。

循环链表的特点：

  1. 从任一结点出发均可找到表中其他结点。

  2. 操作仅有一点与单链表不同：循环条件。

4.2  代码实现

循环链表的实现如下：

///////////////////////////////////////////////////////////////////////////////
//
//  FileName    :   clist.h
//  Version     :   0.10
//  Author      :   Luo Cong
//  Date        :   2005-1-5 10:43:17
//  Comment     :  
//
///////////////////////////////////////////////////////////////////////////////

#ifndef __CIRC_LIST_H__
#define __CIRC_LIST_H__

#include "../../slist/src/slist.h"

template<typename T>
class CCList : public CSList<T>
{
protected:
    CNode<T> *m_pNodeCurr;

public:
    CCList();

public:
    T&      GetNext();
    void    RemoveAt(const int pos);
    int     GetCurrentIndex() const;
};

template<typename T>
inline T& CCList<T>::GetNext()
{
    ASSERT(0 != m_nCount);

    if ((NULL == m_pNodeCurr) || (NULL == m_pNodeCurr->next))
        m_pNodeCurr = m_pNodeHead;
    else
        m_pNodeCurr = m_pNodeCurr->next;

    return m_pNodeCurr->data;
}

template<typename T>
inline int CCList<T>::GetCurrentIndex() const
{
    ASSERT(0 != m_nCount);

    int i;
    CNode<T> *pTmpNode = m_pNodeHead;

    for (i = 1; i <= m_nCount; ++i)
    {
        if (pTmpNode == m_pNodeCurr)
            return i;
        else
            pTmpNode = pTmpNode->next;
    }

    return 0;
}

template<typename T>
inline void CCList<T>::RemoveAt(const int pos)
{
    ASSERT(1 <= pos && pos <= m_nCount);

    int i;
    CNode<T> *pTmpNode1;
    CNode<T> *pTmpNode2;

    pTmpNode1 = m_pNodeHead;

    // head node?
    if (1 == pos)
    {
        m_pNodeHead = m_pNodeHead->next;

        // added for loop list
        // m_pNodeCurr will be set to m_pNodeHead in function GetNext()
        m_pNodeCurr = NULL;

        goto Exit1;
    }

    for (i = 1; i < pos; ++i)
    {
        // we will get the previous node of the target node after
        // the for loop finished, and it would be stored into pTmpNode2
        pTmpNode2 = pTmpNode1;
        pTmpNode1 = pTmpNode1->next;
    }
    pTmpNode2->next = pTmpNode1->next;

    // added for loop list
    m_pNodeCurr = pTmpNode2;

Exit1:
    delete pTmpNode1;
    --m_nCount;
}

template<typename T>
inline CCList<T>::CCList() : m_pNodeCurr(NULL)
{
}

#endif  // __CIRC_LIST_H__

4.3  说明

由于循环链表的操作大部分是与非循环链表相同的，因此我的循环链表是直接从单链表继承来的，并且新增了表示当前结点的变量m_pNodeCurr，以及重载了几个函数。但还有两点是需要特别注意的：

  1. 在GetNext()函数中，必须有判断当前结点应该如何指向下一个结点的条件。

  2. 在RemoveAt()函数中，如果要删除一个结点，而该结点又恰好是头结点的话，那么当前结点必须指向NULL，这样才能在GetNext()中重新获得头结点的正确的值。

关于这两点应该毫无疑问吧？呵呵，那就让我们继续吧……什么？你不明白第二点是什么意思？我倒！

让我们来假定一下，如果当前结点指向了尾结点，然后这时我们调用了GetNext()，那么很显然，当前结点就应该指向头结点了。但问题是头结点已经被我们删除了，那么当前结点还能指向哪里呢？这时什么事情都可能发生，计算机可能会格式化了你的硬盘，也可能会把你的情书送给了班里的恐龙，更可能会告诉你的老板你愿意从此以后一分钱工资都不要一直做到over为止……但最有可能发生的事情是产生一个内存访问的异常，所以，咳咳，计算机是很笨的，必须由我们亲自告诉它：“头结点已经完蛋啦，所以当前结点就指向NULL吧，你在GetNext()函数中自个儿给我解决好下一步的问题。”

明白了吗？还不明白的话……我……

4.4  应用：约瑟夫问题

约瑟夫问题几乎是最经典的用来讲解循环链表的案例了。为什么呢？我们来看看这个问题的描述就会明白了：

有一队由n个冒险家组成的探险队深入到热带雨林中，但他们遭遇到了食人族，食人族的游戏规则是让他们围成一圈，然后选定一个数字m，从第1个人开始报数，报到m时，这个人就要被吃掉了，然后从下一个人开始又重新从1报数，重复这个过程，直到剩下最后一个人，这个人是幸运者，可以离开而不被吃掉。那么问题是，谁是这个幸运者呢？

我们来举个例子：

假设这个探险队有6个探险家，食人族选定的数字m是5，那么在第一轮中，5号会被吃掉，剩下的就是：1, 2, 3, 4, 6总共5个人，然后从6号开始，重新从1开始报5个数：6, 1, 2, 3, 4，所以在第二轮里面被吃掉的就是4号……一直重复这个过程，按顺序应该是：5, 4, 6, 2, 3被吃掉，剩下1号活下来。

解决这个问题并不是只能用循环链表的，但使用循环链表应该是最方便的。我写的代码如下：

///////////////////////////////////////////////////////////////////////////////
//
//  FileName    :   joseph.cpp
//  Version     :   0.10
//  Author      :   Luo Cong
//  Date        :   2005-1-5 13:56:32
//  Comment     :  
//
///////////////////////////////////////////////////////////////////////////////

#include <iostream>
#include "clist.h"
using namespace std;

int main()
{
    int i;
    int n;
    int m;
    int nNumber;
    int nCurIndex;
    CCList<int> clist;

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

    cout << "请输入总的人数： ";
    cin >> n;

    cout << "请输入死亡号码： ";
    cin >> m;

    // 初始化序列号码列表：
    for (i = 1; i <= n; ++i)
    {
        clist.AddTail(i);
    }

    i = 0;
    do
    {
        ++i;
        nNumber = clist.GetNext();
        if (i == m)
        {
            cout << "第 " << nNumber << " 个人被吃掉了！" << endl;

            // 这个人倒霉了
            nCurIndex = clist.GetCurrentIndex();
            clist.RemoveAt(nCurIndex);
            --n;

            // 剩下的人重新开始报数
            i = 0;
        }
    } while (1 != n);

    cout << "最后活下来的是： " << clist.GetHead() << endl;
}

为了解决约瑟夫问题，我在循环链表中加入了GetCurrentIndex()函数，用来获得当前结点的索引值，以便删除当前结点。整个代码应该不难理解，实际动手做做就明白了。 :)

[首页, 上一页, 下一页;   目录 ]