【正文】 CHECK_DF)。}endif // __SINGLE_LIST_H__調(diào)用如下：/////////////////////////////////////////////////////////////////////////////////// FileName : // Version : // Author : Luo Cong// Date : 20041229 10:41:18// Comment : /////////////////////////////////////////////////////////////////////////////////include iostreaminclude using namespace std。 i nCount。 int nCount。 i pos。 pos = m_nCount)。 ++i) { pTmpNode = pTmpNodenext。 int i。 } return pTmpNodedata。 CNodeT *pTmpNode = m_pNodeHead。 CSListT::GetAt(const int pos){ ASSERT(1 = pos amp。 return m_pNodeHeaddata。 ++i) { pTmpNode = pTmpNodenext。 CNodeT *pTmpNode = m_pNodeHead。 } return pTmpNodedata。 nCount = m_nCount。 CSListT::GetTail(){ ASSERT(0 != m_nCount)。 delete m_pNodeHead。 nCount = m_nCount。 RemoveAt(m_nCount)。 m_nCount。 ++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。 // head node? if (1 == pos) { m_pNodeHead = m_pNodeHeadnext。 int i。}templatetypename Tinline int CSListT::GetCount() const{ return m_nCount。 pTmpNodenext = pNewNode。 for (i = 1。 } // is pos range valid? ASSERT(1 = pos amp。 // if the list is empty, replace the head node with the new node. if (NULL == m_pNodeHead) { pNewNodenext = NULL。 pNewNode = new CNodeT。}// if success, return the position of the new node.// if fail, return 0.templatetypename Tinline int CSListT::InsertAfter(const int pos, const T data){ int i。 pTmpNode2next = pNewNode。 i pos。 nRetPos = 1。amp。 m_pNodeHead = pNewNode。 if (NULL == pNewNode) { nRetPos = 0。 CNodeT *pTmpNode1。 return 1。 pNewNodedata = data。}templatetypename Tinline int CSListT::IsEmpty() const{ return 0 == m_nCount。}。 GetAt(const int pos)。 Tamp。 void RemoveAll()。 int AddTail(const T data)。 int GetCount() const。 CSList(const T amp。initdata, CNodeT *p) : data(initdata), next(p) {}}。endififdef _DEBUGifndef ASSERTdefine ASSERT assertendifelse // not _DEBUGifndef ASSERTdefine ASSERTendifendif // _DEBUGtemplatetypename Tclass CNode{public: T data。endif在閱讀時(shí)不用管它們，直接略過即可。頭文件中，我一般會寫3行固定格式的預(yù)編譯語句，如下：ifndef __LIST_H__define __LIST_H__// TODO: Add header body code hereendif // __LIST_H__。在具體的代碼實(shí)現(xiàn)上，我可能會參考MFC、STL……但也可能會進(jìn)行一定的修改。在經(jīng)歷了一段痛苦的斗爭后，我選擇了自學(xué)的道路，想把這門課程扎扎實(shí)實(shí)地學(xué)好。^_^這本教科書所使用的是C語言，也許很多人會說C語言已經(jīng)過時(shí)了，但是，我認(rèn)為在數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)中，應(yīng)該用盡量簡單的語言，以免進(jìn)入了語言的細(xì)枝末節(jié)中，反而沖淡了主題。數(shù)據(jù)結(jié)構(gòu)處算法分析――讀書筆記　第一章前言 所選教材我所選擇的教材是《數(shù)據(jù)結(jié)構(gòu)與算法分析——C語言描述》（原書第2版），英文版的名稱是《Data Structures and Algorithm Analysis in C》，作者是：(美)Mark Allen Weiss。實(shí)際上在國外的許多大學(xué)中（甚至中學(xué)），數(shù)據(jù)結(jié)構(gòu)和算法分析的課程是選用Scheme的，例如MIT麻省理工大學(xué)極其著名的SICP課程。教科書中已經(jīng)給出了大部分的代碼，因此，我基本上也只是重復(fù)敲入了一次而已（或者是改寫成C++），但這并不是沒有意義的。 一些約定我使用的是Visual C++ ，并將會用C/C++來撰寫代碼（我可能會用C++改寫原書中的例子，以便能用在工作中，但一些地方還是會用C），不會使用任何與平臺相關(guān)的特性（因此可以保證有比較好的移植性）。另外，C++操作符new的實(shí)現(xiàn)在不同的編譯器中都不太一樣，在VC6中，如果new失敗，則會返回NULL，程序中我用檢測返回值是否為NULL來判斷new是否成功，但如果這個代碼是用別的編譯器編譯的，則要特別注意別的編譯器是否也是用NULL來表示new失敗的，否則很可能會導(dǎo)致無法意料的結(jié)果。第二章單鏈表鏈表是最常用、最簡單和最基本的數(shù)據(jù)結(jié)構(gòu)之一。 CNodeT *next。templatetypename Tclass CSList{protected: int m_nCount。initdata)。 int InsertBefore(const int pos, const T data)。 void RemoveAt(const int pos)。 Tamp。 GetHead()。 T GetAt(const int pos) const。templatetypename Tinline CSListT::CSList() : m_nCount(0), m_pNodeHead(NULL){}templatetypename Tinline CSListT::CSList(const T amp。}templatetypename Tinline int CSListT::AddHead(const T data){ CNodeT *pNewNode。 pNewNodenext = m_pNodeHead。}templatetypename Tinline int CSListT::AddTail(const T data){ return InsertAfter(GetCount(), data)。 CNodeT *pTmpNode2。 goto Exit0。 nRetPos = 1。 pos = m_nCount)。 goto Exit1。 ++i) { pTmpNode2 = pTmpNode1。 nRetPos = pos。 int nRetPos。 if (NULL == pNewNode) { nRetPos = 0。 m_pNodeHead = pNewNode。amp。 i pos。 nRetPos = pos + 1。}templatetypename Tinline void CSListT::RemoveAt(const int pos){ ASSERT(1 = pos amp。 CNodeT *pTmpNode1。 goto Exit1。 pTmpNode1 = pTmpNode1next。}templatetypename Tinline void CSListT::RemoveHead(){ ASSERT(0 != m_nCount)。}templatetypename Tinline void CSListT::RemoveAll(){ int i。 for (i = 0。 m_pNodeHead = pTmpNode。 int i。 for (i = 1。}templatetypename Tinline T CSListT::GetTail() const{ ASSERT(0 != m_nCount)。 nCount = m_nCount。 } return pTmpNodedata。}templatetypename Tinline T CSListT::GetHead() const{ ASSERT(0 != m_nCount)。amp。 for (i = 1。}templatetypename Tinline T CSListT::GetAt(const int pos) const{ ASSERT(1 = pos amp。 CNodeT *pTmpNode = m_pNodeHead。 } return pTmpNodedata。 int i。 ++i) { pTmpNode = pTmpNodenext。 CNodeT *pTmpNode = m_pNodeHead。 ++i) { if (data == pTmpNodedata) return i + 1。int main(){ int i。endif (((1), 2), 3)。 (((), 7), 8)。 // print out elements nCount = ()。}代碼比較簡單，一看就明白，懶得解釋了。原書中提到了一個“表頭”（header）或“啞結(jié)點(diǎn)”（dummy node）的概念，這個結(jié)點(diǎn)作為第一個結(jié)點(diǎn)，位置在0，它是不用的，我個人認(rèn)為這樣做有點(diǎn)浪費(fèi)空間，所以并沒有采用這種做法。不過我們可以采用雙鏈表和循環(huán)鏈表來改善這種情況。 int HighPower。 int tmp1。 i = polysumHighPower + 1。 polysum(sum)。 int tmp1。 i = polymulHighPower。 ++i) { tmp1 = poly1(i + 1)。 tmp2 = poly2(j + 1)