链表是最常用、最简单和最基本的数据结构之一。我们先来看看单链表的实现。
单链表的实现如下：
/////////////////////////////////////////////////////////////////////////////// // // 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，请告诉我。
考虑到效率的问题，代码中声明了一个成员变量：m_nCount，用它来记录链表的结点个数。这样有什么好处呢？在某些情况下就不用遍历链表了，例如，至少在GetCount()时能提高速度。
原书中提到了一个“表头”（header）或“哑结点”（dummy node）的概念，这个结点作为第一个结点，位置在0，它是不用的，我个人认为这样做有点浪费空间，所以并没有采用这种做法。
单链表在效率上最大的问题在于，如果要插入一个结点到链表的末端或者删除末端的一个结点，则需要遍历整个链表，时间复杂度是O(N)。平均来说，要访问一个结点，时间复杂度也有O(N/2)。这是链表本身的性质所造成的，没办法解决。不过我们可以采用双链表和循环链表来改善这种情况。
我们使用一元多项式来说明单链表的应用。假设有两个一元多项式：
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
怎么样，很容易吧？:) 但我们是灵长类动物，这么繁琐的计算怎么能用手工来完成呢？（试想一下，如果多项式非常大的话……）我们的目标是用计算机来完成这些计算任务，代码就在下面。
/////////////////////////////////////////////////////////////////////////////// // // 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; } }
原书中只给出了一元多项式的数组实现，而没有给出单链表的代码。实际上用单链表最大的好处在于多项式的项数可以为任意大。（当然只是理论上的。什么？你的内存是无限大的？好吧，当我没说……）
我没有实现减法操作，实际上减法可以转换成加法来完成，例如 a - b 可以换算成 a + (-b)，那么我们的目标就转变为做一个负号的运算了。至于除法，可以通过先换算“-”，然后再用原位加法来计算。（现在你明白加法有多重要了吧？^_^）有兴趣的话，不妨您试试完成它，我的目标只是掌握单链表的使用，因此不再继续深究。