【文章內容簡介】 : 20041230 17:32:54// Comment : /////////////////////////////////////////////////////////////////////////////////include include define Max(x,y) (((x)(y)) ? (x) : (y))typedef struct tagPOLYNOMIAL{ CSListint Coeff。 int HighPower。} * Polynomial。static void AddPolynomial( Polynomial polysum, const Polynomial poly1, const Polynomial poly2){ int i。 int sum。 int tmp1。 int tmp2。 polysumHighPower = Max(poly1HighPower, poly2HighPower)。 for (i = 1。 i = polysumHighPower + 1。 ++i) { tmp1 = poly1(i)。 tmp2 = poly2(i)。 sum = tmp1 + tmp2。 polysum(sum)。 }}static void MulPolynomial( Polynomial polymul, const Polynomial poly1, const Polynomial poly2){ int i。 int j。 int tmp。 int tmp1。 int tmp2。 polymulHighPower = poly1HighPower + poly2HighPower。 // initialize all elements to zero for (i = 0。 i = polymulHighPower。 ++i) polymul(0)。 for (i = 0。 i = poly1HighPower。 ++i) { tmp1 = poly1(i + 1)。 for (j = 0。 j = poly2HighPower。 ++j) { tmp = polymul(i + j + 1)。 tmp2 = poly2(j + 1)。 tmp += tmp1 * tmp2。 polymul(i + j + 1, tmp)。 } }}static void PrintPoly(const Polynomial poly){ int i。 for (i = polyHighPower。 i 0。 i ) printf( %dX^%d + , poly(i + 1), i)。 printf(%d\n, poly())。}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 poly1HighPower = 2。 poly1(0)。 poly1(1)。 poly1(2)。 poly1(3)。 // P2(X) = 3X^3 + 10X + 6 poly2HighPower = 3。 poly2(3)。 poly2(0)。 poly2(10)。 poly2(6)。 // add result = 3X^3 + 1X^2 + 12X^1 + 9 AddPolynomial(polyresult, poly1, poly2)。 PrintPoly(polyresult)。 // reset polyresult()。 // 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。 }} 說明原書中只給出了一元多項式的數(shù)組實現(xiàn)，而沒有給出單鏈表的代碼。實際上用單鏈表最大的好處在于多項式的項數(shù)可以為任意大。（當然只是理論上的。什么？你的內存是無限大的？好吧，當我沒說……）我沒有實現(xiàn)減法操作，實際上減法可以轉換成加法來完成，例如 a b 可以換算成 a + (b)，那么我們的目標就轉變?yōu)樽鲆粋€負號的運算了。至于除法，可以通過先換算“”，然后再用原位加法來計算。（現(xiàn)在你明白加法有多重要了吧？^_^）有興趣的話，不妨您試試完成它，我的目標只是掌握單鏈表的使用，因此不再繼續(xù)深究。 第三章雙鏈表單鏈表學完后，理所當然的就是輪到雙鏈表了。 代碼實現(xiàn)雙鏈表的實現(xiàn)如下：/////////////////////////////////////////////////////////////////////////////////// FileName : // Version : // Author : Luo Cong// Date : 200514 10:33:21// Comment : /////////////////////////////////////////////////////////////////////////////////ifndef __DOUBLE_LIST_H__define __DOUBLE_LIST_H__include include ifdef _DEBUGdefine DEBUG_NEW new (_NORMAL_BLOCK, THIS_FILE, __LINE__)endififdef _DEBUGdefine new DEBUG_NEWundef THIS_FILEstatic char THIS_FILE[] = __FILE__。endififdef _DEBUGifndef ASSERTdefine ASSERT assertendifelse // not _DEBUGifndef ASSERTdefine ASSERTendifendif // _DEBUGtemplatetypename Tclass CNode{public: T data。 CNodeT *prior。 CNodeT *next。 CNode() : data(T()), prior(NULL), next(NULL) {} CNode(const T amp。initdata) : data(initdata), prior(NULL), next(NULL) {}}。templatetypename Tclass CDList{protected: int m_nCount。 CNodeT *m_pNodeHead。 CNodeT *m_pNodeTail。public: CDList()。 CDList(const T amp。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()。 Tamp。 GetTail()。 T GetTail() const。 Tamp。 GetHead()。 T GetHead() const。 Tamp。 GetAt(const int pos)。 T GetAt(const int pos) const。 void SetAt(const int pos, T data)。 int Find(const T data) const。 Tamp。 GetPrev(int amp。pos)。 Tamp。 GetNext(int amp。pos)。}。templatetypename Tinline CDListT::CDList() : m_nCount(0), m_pNodeHead(NULL), m_pNodeTail(NULL){}templatetypename Tinline CDListT::CDList(const T amp。initdata) : m_nCount(0), m_pNodeHead(NULL), m_pNodeTail(NULL){ AddHead(initdata)。}templatetypename Tinline CDListT::~CDList(){ RemoveAll()。}templatetypename Tinline Tamp。 CDListT::GetNext(int amp。pos){ ASSERT(0 != m_nCount)。 ASSERT(1 = pos amp。amp。 pos = m_nCount)。 int i。 CNodeT *pTmpNode = m_pNodeHead。 for (i = 1。 i pos。 ++i) { pTmpNode = pTmpNodenext。 } ++pos。 return pTmpNodedata。}templatetypename Tinline Tamp。 CDListT::GetPrev(int amp。pos){ ASSERT(0 != m_nCount)。 ASSERT(1 = pos amp。amp。 pos = m_nCount)。 int i。 CNodeT *pTmpNode = m_pNodeHead。 for (i = 1。 i pos。 ++i) {