第四章

循环链表

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()函数,用来获得当前结点的索引值,以便删除当前结点。整个代码应该不难理解,实际动手做做就明白了。 :)