第二章

单链表

链表是最常用、最简单和最基本的数据结构之一。我们先来看看单链表的实现。

2.1  代码实现

单链表的实现如下:

///////////////////////////////////////////////////////////////////////////////
//
//  FileName    :   slist.h
//  Version     :   0.10
//  Author      :   Luo Cong
//  Date        :   2004-12-29 9:58:38
//  Comment     :  
//
///////////////////////////////////////////////////////////////////////////////

#ifndef __SINGLE_LIST_H__
#define __SINGLE_LIST_H__

#include <assert.h>
#include <crtdbg.h>

#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<typename T>
class CNode
{
public:
    T data;
    CNode<T> *next;
    CNode() : data(T()), next(NULL) {}
    CNode(const T &initdata) : data(initdata), next(NULL) {}
    CNode(const T &initdata, CNode<T> *p) : data(initdata), next(p) {}
};

template<typename T>
class CSList
{
protected:
    int m_nCount;
    CNode<T> *m_pNodeHead;

public:
    CSList();
    CSList(const T &initdata);
    ~CSList();

public:
    int     IsEmpty() const;
    int     GetCount() const;
    int     InsertBefore(const int pos, const T data);
    int     InsertAfter(const int pos, const T data);
    int     AddHead(const T data);
    int     AddTail(const T data);
    void    RemoveAt(const int pos);
    void    RemoveHead();
    void    RemoveTail();
    void    RemoveAll();
    T&      GetTail();
    T       GetTail() const;
    T&      GetHead();
    T       GetHead() const;
    T&      GetAt(const int pos);
    T       GetAt(const int pos) const;
    void    SetAt(const int pos, T data);
    int     Find(const T data) const;
};

template<typename T>
inline CSList<T>::CSList() : m_nCount(0), m_pNodeHead(NULL)
{
}

template<typename T>
inline CSList<T>::CSList(const T &initdata) : m_nCount(0), m_pNodeHead(NULL)
{
    AddHead(initdata);
}

template<typename T>
inline CSList<T>::~CSList()
{
    RemoveAll();
}

template<typename T>
inline int CSList<T>::IsEmpty() const
{
    return 0 == m_nCount;
}

template<typename T>
inline int CSList<T>::AddHead(const T data)
{
    CNode<T> *pNewNode;

    pNewNode = new CNode<T>;
    if (NULL == pNewNode)
        return 0;

    pNewNode->data = data;
    pNewNode->next = m_pNodeHead;

    m_pNodeHead = pNewNode;
    ++m_nCount;

    return 1;
}

template<typename T>
inline int CSList<T>::AddTail(const T data)
{
    return InsertAfter(GetCount(), data);
}

// if success, return the position of the new node.
// if fail, return 0.
template<typename T>
inline int CSList<T>::InsertBefore(const int pos, const T data)
{
    int i;
    int nRetPos;
    CNode<T> *pTmpNode1;
    CNode<T> *pTmpNode2;
    CNode<T> *pNewNode;

    pNewNode = new CNode<T>;
    if (NULL == pNewNode)
    {
        nRetPos = 0;
        goto Exit0;
    }

    pNewNode->data = data;

    // if the list is empty, replace the head node with the new node.
    if (NULL == m_pNodeHead)
    {
        pNewNode->next = NULL;
        m_pNodeHead = pNewNode;
        nRetPos = 1;
        goto Exit1;
    }

    // is pos range valid?
    ASSERT(1 <= pos && pos <= m_nCount);

    // insert before head node?
    if (1 == pos)
    {
        pNewNode->next = m_pNodeHead;
        m_pNodeHead = pNewNode;
        nRetPos = 1;
        goto Exit1;
    }

    // if the list is not empty and is not inserted before head node,
    // seek to the pos of the list and insert the new node before it.
    pTmpNode1 = m_pNodeHead;
    for (i = 1; i < pos; ++i)
    {
        pTmpNode2 = pTmpNode1;
        pTmpNode1 = pTmpNode1->next;
    }
    pNewNode->next = pTmpNode1;
    pTmpNode2->next = pNewNode;

    nRetPos = pos;

Exit1:
    ++m_nCount;
Exit0:
    return nRetPos;
}

// if success, return the position of the new node.
// if fail, return 0.
template<typename T>
inline int CSList<T>::InsertAfter(const int pos, const T data)
{
    int i;
    int nRetPos;
    CNode<T> *pTmpNode;
    CNode<T> *pNewNode;

    pNewNode = new CNode<T>;
    if (NULL == pNewNode)
    {
        nRetPos = 0;
        goto Exit0;
    }

    pNewNode->data = data;

    // if the list is empty, replace the head node with the new node.
    if (NULL == m_pNodeHead)
    {
        pNewNode->next = NULL;
        m_pNodeHead = pNewNode;
        nRetPos = 1;
        goto Exit1;
    }

    // is pos range valid?
    ASSERT(1 <= pos && pos <= m_nCount);

    // if the list is not empty,
    // seek to the pos of the list and insert the new node after it.
    pTmpNode = m_pNodeHead;
    for (i = 1; i < pos; ++i)
    {
        pTmpNode = pTmpNode->next;
    }
    pNewNode->next = pTmpNode->next;
    pTmpNode->next = pNewNode;

    nRetPos = pos + 1;

Exit1:
    ++m_nCount;
Exit0:
    return nRetPos;
}

template<typename T>
inline int CSList<T>::GetCount() const
{
    return m_nCount;
}

template<typename T>
inline void CSList<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;
        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;

Exit1:
    delete pTmpNode1;
    --m_nCount;
}

template<typename T>
inline void CSList<T>::RemoveHead()
{
    ASSERT(0 != m_nCount);
    RemoveAt(1);
}

template<typename T>
inline void CSList<T>::RemoveTail()
{
    ASSERT(0 != m_nCount);
    RemoveAt(m_nCount);
}

template<typename T>
inline void CSList<T>::RemoveAll()
{
    int i;
    int nCount;
    CNode<T> *pTmpNode;

    nCount = m_nCount;
    for (i = 0; i < nCount; ++i)
    {
        pTmpNode = m_pNodeHead->next;
        delete m_pNodeHead;
        m_pNodeHead = pTmpNode;
    }

    m_nCount = 0;
}

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

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

    nCount = m_nCount;
    for (i = 1; i < nCount; ++i)
    {
        pTmpNode = pTmpNode->next;
    }

    return pTmpNode->data;
}

template<typename T>
inline T CSList<T>::GetTail() const
{
    ASSERT(0 != m_nCount);

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

    nCount = m_nCount;
    for (i = 1; i < nCount; ++i)
    {
        pTmpNode = pTmpNode->next;
    }

    return pTmpNode->data;
}

template<typename T>
inline T& CSList<T>::GetHead()
{
    ASSERT(0 != m_nCount);
    return m_pNodeHead->data;
}

template<typename T>
inline T CSList<T>::GetHead() const
{
    ASSERT(0 != m_nCount);
    return m_pNodeHead->data;
}

template<typename T>
inline T& CSList<T>::GetAt(const int pos)
{
    ASSERT(1 <= pos && pos <= m_nCount);

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

    for (i = 1; i < pos; ++i)
    {
        pTmpNode = pTmpNode->next;
    }

    return pTmpNode->data;
}

template<typename T>
inline T CSList<T>::GetAt(const int pos) const
{
    ASSERT(1 <= pos && pos <= m_nCount);

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

    for (i = 1; i < pos; ++i)
    {
        pTmpNode = pTmpNode->next;
    }

    return pTmpNode->data;
}

template<typename T>
inline void CSList<T>::SetAt(const int pos, T data)
{
    ASSERT(1 <= pos && pos <= m_nCount);

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

    for (i = 1; i < pos; ++i)
    {
        pTmpNode = pTmpNode->next;
    }
    pTmpNode->data = data;
}

template<typename T>
inline int CSList<T>::Find(const T data) const
{
    int i;
    int nCount;
    CNode<T> *pTmpNode = m_pNodeHead;

    nCount = m_nCount;
    for (i = 0; i < nCount; ++i)
    {
        if (data == pTmpNode->data)
            return i + 1;
        pTmpNode = pTmpNode->next;
    }

    return 0;
}

#endif  // __SINGLE_LIST_H__

调用如下:

///////////////////////////////////////////////////////////////////////////////
//
//  FileName    :   slist.cpp
//  Version     :   0.10
//  Author      :   Luo Cong
//  Date        :   2004-12-29 10:41:18
//  Comment     :  
//
///////////////////////////////////////////////////////////////////////////////

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

int main()
{
    int i;
    int nCount;
    CSList<int> slist;

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

    slist.InsertAfter(slist.InsertAfter(slist.AddHead(1), 2), 3);
    slist.InsertAfter(slist.InsertAfter(slist.GetCount(), 4), 5);
    slist.InsertAfter(slist.GetCount(), 6);
    slist.AddTail(10);
    slist.InsertAfter(slist.InsertBefore(slist.GetCount(), 7), 8);
    slist.SetAt(slist.GetCount(), 9);
    slist.RemoveHead();
    slist.RemoveTail();

    // print out elements
    nCount = slist.GetCount();
    for (i = 0; i < nCount; ++i)
        cout << slist.GetAt(i + 1) << endl;
}

代码比较简单,一看就明白,懒得解释了。如果有bug,请告诉我。

2.2  效率问题

考虑到效率的问题,代码中声明了一个成员变量:m_nCount,用它来记录链表的结点个数。这样有什么好处呢?在某些情况下就不用遍历链表了,例如,至少在GetCount()时能提高速度。

原书中提到了一个“表头”(header)或“哑结点”(dummy node)的概念,这个结点作为第一个结点,位置在0,它是不用的,我个人认为这样做有点浪费空间,所以并没有采用这种做法。

单链表在效率上最大的问题在于,如果要插入一个结点到链表的末端或者删除末端的一个结点,则需要遍历整个链表,时间复杂度是O(N)。平均来说,要访问一个结点,时间复杂度也有O(N/2)。这是链表本身的性质所造成的,没办法解决。不过我们可以采用双链表和循环链表来改善这种情况。

2.3  应用:一元多项式(加法和乘法)

2.3.1  基础知识

我们使用一元多项式来说明单链表的应用。假设有两个一元多项式:

P1(X) = X^2 + 2X + 3

以及

P2(X) = 3X^3 + 10X + 6

现在运用中学的基础知识,计算它们的和:

P1(X) + P2(X) = (X^2 + 2X + 3) + (3X^3 + 10X + 6)
              = 3X^3 + 1X^2 + 12X^1 + 9

以及计算它们的乘积:

P1(X) * P2(X) = (X^2 + 2X + 3) * (3X^3 + 10X + 6)
              = 3X^5 + 6X^4 + 19X^3 + 26X^2 + 42X^1 + 18

怎么样,很容易吧?:) 但我们是灵长类动物,这么繁琐的计算怎么能用手工来完成呢?(试想一下,如果多项式非常大的话……)我们的目标是用计算机来完成这些计算任务,代码就在下面。

2.3.2  代码实现

///////////////////////////////////////////////////////////////////////////////
//
//  FileName    :   poly.cpp
//  Version     :   0.10
//  Author      :   Luo Cong
//  Date        :   2004-12-30 17:32:54
//  Comment     :  
//
///////////////////////////////////////////////////////////////////////////////

#include <stdio.h>
#include "slist.h"

#define Max(x,y) (((x)>(y)) ? (x) : (y))

typedef struct tagPOLYNOMIAL
{
    CSList<int> Coeff;
    int HighPower;
} * Polynomial;

static void AddPolynomial(
    Polynomial polysum,
    const Polynomial poly1,
    const Polynomial poly2
)
{
    int i;
    int sum;
    int tmp1;
    int tmp2;

    polysum->HighPower = Max(poly1->HighPower, poly2->HighPower);
    for (i = 1; i <= polysum->HighPower + 1; ++i)
    {
        tmp1 = poly1->Coeff.GetAt(i);
        tmp2 = poly2->Coeff.GetAt(i);
        sum = tmp1 + tmp2;
        polysum->Coeff.AddTail(sum);
    }
}

static void MulPolynomial(
    Polynomial polymul,
    const Polynomial poly1,
    const Polynomial poly2
)
{
    int i;
    int j;
    int tmp;
    int tmp1;
    int tmp2;

    polymul->HighPower = poly1->HighPower + poly2->HighPower;

    // initialize all elements to zero
    for (i = 0; i <= polymul->HighPower; ++i)
        polymul->Coeff.AddTail(0);

    for (i = 0; i <= poly1->HighPower; ++i)
    {
        tmp1 = poly1->Coeff.GetAt(i + 1);
        for (j = 0; j <= poly2->HighPower; ++j)
        {
            tmp = polymul->Coeff.GetAt(i + j + 1);
            tmp2 = poly2->Coeff.GetAt(j + 1);
            tmp += tmp1 * tmp2;
            polymul->Coeff.SetAt(i + j + 1, tmp);
        }
    }
}

static void PrintPoly(const Polynomial poly)
{
    int i;

    for (i = poly->HighPower; i > 0; i-- )
        printf( "%dX^%d + ", poly->Coeff.GetAt(i + 1), i);
    printf("%d\n", poly->Coeff.GetHead());
}

int main()
{
    Polynomial poly1 = NULL;
    Polynomial poly2 = NULL;
    Polynomial polyresult = NULL;

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

    poly1 = new (struct tagPOLYNOMIAL);
    if (NULL == poly1)
        goto Exit0;

    poly2 = new (struct tagPOLYNOMIAL);
    if (NULL == poly2)
        goto Exit0;

    polyresult = new (struct tagPOLYNOMIAL);
    if (NULL == polyresult)
        goto Exit0;

    // P1(X) = X^2 + 2X + 3
    poly1->HighPower = 2;
    poly1->Coeff.AddHead(0);
    poly1->Coeff.AddHead(1);
    poly1->Coeff.AddHead(2);
    poly1->Coeff.AddHead(3);

    // P2(X) = 3X^3 + 10X + 6
    poly2->HighPower = 3;
    poly2->Coeff.AddHead(3);
    poly2->Coeff.AddHead(0);
    poly2->Coeff.AddHead(10);
    poly2->Coeff.AddHead(6);

    // add result = 3X^3 + 1X^2 + 12X^1 + 9
    AddPolynomial(polyresult, poly1, poly2);
    PrintPoly(polyresult);

    // reset
    polyresult->Coeff.RemoveAll();

    // mul result = 3X^5 + 6X^4 + 19X^3 + 26X^2 + 42X^1 + 18
    MulPolynomial(polyresult, poly1, poly2);
    PrintPoly(polyresult);

Exit0:
    if (poly1)
    {
        delete poly1;
        poly1 = NULL;
    }
    if (poly2)
    {
        delete poly2;
        poly2 = NULL;
    }
    if (polyresult)
    {
        delete polyresult;
        polyresult = NULL;
    }
}

2.3.3  说明

原书中只给出了一元多项式的数组实现,而没有给出单链表的代码。实际上用单链表最大的好处在于多项式的项数可以为任意大。(当然只是理论上的。什么?你的内存是无限大的?好吧,当我没说……)

我没有实现减法操作,实际上减法可以转换成加法来完成,例如 a - b 可以换算成 a + (-b),那么我们的目标就转变为做一个负号的运算了。至于除法,可以通过先换算“-”,然后再用原位加法来计算。(现在你明白加法有多重要了吧?^_^)有兴趣的话,不妨您试试完成它,我的目标只是掌握单链表的使用,因此不再继续深究。