商务合作:179001057@qq.com

第三章 双链表

技术2022-05-11  1


某平台价值19860元的编程课程资料免费领取【点我领取】


第三章

双链表单链表学完后,理所当然的就是轮到双链表了。

3.1  代码实现双链表的实现如下:

///////  FileName    :   dlist.h//  Version     :   0.10//  Author      :   Luo Cong//  Date        :   2005-1-4 10:33:21//  Comment     :  /////

#ifndef __DOUBLE_LIST_H__#define __DOUBLE_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_FILEstatic 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> *prior;    CNode<T> *next;    CNode() : data(T()), prior(NULL), next(NULL) {}    CNode(const T &initdata) : data(initdata), prior(NULL), next(NULL) {}};

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

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

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;    T&      GetPrev(int &pos);    T&      GetNext(int &pos);};

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

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

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

template<typename T>inline T& CDList<T>::GetNext(int &pos){    ASSERT(0 != m_nCount);    ASSERT(1 <= pos && pos <= m_nCount);

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

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

    ++pos;

    return pTmpNode->data;}

template<typename T>inline T& CDList<T>::GetPrev(int &pos){    ASSERT(0 != m_nCount);    ASSERT(1 <= pos && pos <= m_nCount);

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

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

    --pos;

    return pTmpNode->data;}

template<typename T>inline int CDList<T>::InsertBefore(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->prior = NULL;        pNewNode->next = NULL;        m_pNodeHead = pNewNode;        m_pNodeTail = pNewNode;        nRetPos = 1;        goto Exit1;    }

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

    // insert before head node?    if (1 == pos)    {        pNewNode->prior = NULL;        pNewNode->next = m_pNodeHead;        m_pNodeHead->prior = pNewNode;        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.    pTmpNode = m_pNodeHead;    for (i = 1; i < pos; ++i)    {        pTmpNode = pTmpNode->next;    }    pNewNode->next = pTmpNode;    pNewNode->prior = pTmpNode->prior;

    pTmpNode->prior->next = pNewNode;    pTmpNode->prior = pNewNode;

    // if tail node, must update m_pNodeTail    if (NULL == pNewNode->next)    {        m_pNodeTail = pNewNode;    }

    nRetPos = pos;

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

template<typename T>inline int CDList<T>::InsertAfter(const int pos, const T data){    int i;    int nRetPos;    CNode<T> *pNewNode;    CNode<T> *pTmpNode;

    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->prior = NULL;        pNewNode->next = NULL;        m_pNodeHead = pNewNode;        m_pNodeTail = 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;    pNewNode->prior = pTmpNode;

    // if NewNode's position is m_pNodeTail, update m_pNodeTail    if (pTmpNode->next == m_pNodeTail)    {        m_pNodeTail->prior = pNewNode;    }

    pTmpNode->next = pNewNode;

    // if tail node, must update m_pNodeTail    if (NULL == pNewNode->next)    {        m_pNodeTail = pNewNode;    }

    nRetPos = pos + 1;

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

template<typename T>inline T& CDList<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 CDList<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 int CDList<T>::AddHead(const T data){    return InsertBefore(1, data);}

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

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

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

template<typename T>inline T& CDList<T>::GetTail(){    ASSERT(0 != m_nCount);    return m_pNodeTail->data;}

template<typename T>inline T CDList<T>::GetTail() const{    ASSERT(0 != m_nCount);    return m_pNodeTail->data;}

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

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

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

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

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

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

Exit1:    delete pTmpNode;    --m_nCount;    if (0 == m_nCount)    {        m_pNodeTail = NULL;    }}

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

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

template<typename T>inline void CDList<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 void CDList<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 CDList<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  // __DOUBLE_LIST_H__

调用如下:

///////  FileName    :   dlist.cpp//  Version     :   0.10//  Author      :   Luo Cong//  Date        :   2005-1-4 10:58:22//  Comment     :  /////

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

int main(){    int i;    int nCount;    CDList<int> dlist;

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

    dlist.AddTail(1);    dlist.AddTail(3);    dlist.InsertBefore(2, 2);    dlist.AddHead(4);    dlist.RemoveTail();

    nCount = dlist.GetCount();    for (i = 1; i <= nCount;)    {        cout << dlist.GetNext(i) << endl;    }}

3.2  说明单链表的结点中只有一个指向直接后继结点的指针,所以,从某个结点出发只能顺着指针往后查询其他的结点。靠,那如果我想访问某个结点的前一个结点,岂不只能重新从表头结点开始了?效率真低啊!换句话说,在单链表中,GetNext()的时间复杂度为O(1),而GetPrev()的时间复杂度则为O(N)。为克服单链表这种单向性的缺点,我们可以利用——“当当当当”,Only you,就是——双链表。

顾名思义,在双链表的结点中有两个指针,一个指向直接后继,另一个指向直接前驱,在C++语言中表示如下:

struct Node{    struct Node *prior;    struct Node *next;    T data;};

大部分对双链表的操作(只涉及到向后方向的指针的操作)都与单链表的相同,但在插入、删除时有很大的不同,在双链表中需同时修改两个方向上的指针。因此,可以直接继承单链表的类来完成双链表,然后改改不一样的函数就行了。但我没有这样做,别问为什么,人品问题而已。

如果你已经熟练掌握了单链表的指针域,那么双链表的这部分应该难不倒你了。不多说了,请看代码吧。如果有bug,请告诉我。^_^  


最新回复(0)