數(shù)據(jù)結(jié)構(gòu)處算法分析――讀書筆記.doc

數(shù)據(jù)結(jié)構(gòu)處算法分析讀書筆記第一章前言1.1 所選教材我所選擇的教材是數(shù)據(jù)結(jié)構(gòu)與算法分析C語言描述（原書第2版），英文版的名稱是Data Structures and Algorithm Analysis in C，作者是：(美)Mark Allen Weiss。原書曾被評(píng)為20世紀(jì)頂尖的30部計(jì)算機(jī)著作之一。之所以選這本書，還因?yàn)樗暮?jiǎn)體中文版翻譯得相當(dāng)不錯(cuò)，幾乎沒有給我的閱讀帶來什么障礙。_這本教科書所使用的是C語言，也許很多人會(huì)說C語言已經(jīng)過時(shí)了，但是，我認(rèn)為在數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)中，應(yīng)該用盡量簡(jiǎn)單的語言，以免進(jìn)入了語言的細(xì)枝末節(jié)中，反而沖淡了主題。實(shí)際上在國(guó)外的許多大學(xué)中（甚至中學(xué)），數(shù)據(jù)結(jié)構(gòu)和算法分析的課程是選用Scheme的，例如MIT麻省理工大學(xué)極其著名的SICP課程。呵呵，語言又能說明什么呢？1.2 寫作原因數(shù)據(jù)結(jié)構(gòu)與算法分析是計(jì)算機(jī)專業(yè)的必修課但遺憾的是，我在大學(xué)階段并不是計(jì)算機(jī)專業(yè)的學(xué)生，以至于沒有系統(tǒng)地跟著老師學(xué)習(xí)過這門課程?，F(xiàn)在我已經(jīng)工作了，在實(shí)際的工作中，我經(jīng)常感到自己的基礎(chǔ)知識(shí)不夠，有很多問題無法解決。在經(jīng)歷了一段痛苦的斗爭(zhēng)后，我選擇了自學(xué)的道路，想把這門課程扎扎實(shí)實(shí)地學(xué)好。教科書中已經(jīng)給出了大部分的代碼，因此，我基本上也只是重復(fù)敲入了一次而已（或者是改寫成C+），但這并不是沒有意義的。我們?cè)诳磿臅r(shí)候經(jīng)常會(huì)覺得自己已經(jīng)懂了，但如果真的要親自動(dòng)手去做了，卻會(huì)感到無法下手。我認(rèn)為，親自輸入一次代碼并調(diào)試通過，比任何空談都有效。在具體的代碼實(shí)現(xiàn)上，我可能會(huì)參考MFC、STL但也可能會(huì)進(jìn)行一定的修改。1.3 一些約定我使用的是Visual C+ 6.0編譯器，并將會(huì)用C/C+來撰寫代碼（我可能會(huì)用C+改寫原書中的例子，以便能用在工作中，但一些地方還是會(huì)用C），不會(huì)使用任何與平臺(tái)相關(guān)的特性（因此可以保證有比較好的移植性）。原書中的代碼風(fēng)格跟我平時(shí)的代碼風(fēng)格非常相近，但有一些地方我可能會(huì)進(jìn)行一些改動(dòng)。我認(rèn)為數(shù)據(jù)結(jié)構(gòu)的代碼不需要任何界面，因此，請(qǐng)您新建一個(gè)工程，類型為Win32 Console Application，即控制臺(tái)工程。然后添加一個(gè).h頭文件和一個(gè).c/.cpp文件。頭文件中，我一般會(huì)寫3行固定格式的預(yù)編譯語句，如下：#ifndef _LIST_H_#define _LIST_H_/ TODO: Add header body code here#endif / _LIST_H_表示這是一個(gè)list.h。另外，C+操作符new的實(shí)現(xiàn)在不同的編譯器中都不太一樣，在VC6中，如果new失敗，則會(huì)返回NULL，程序中我用檢測(cè)返回值是否為NULL來判斷new是否成功，但如果這個(gè)代碼是用別的編譯器編譯的，則要特別注意別的編譯器是否也是用NULL來表示new失敗的，否則很可能會(huì)導(dǎo)致無法意料的結(jié)果。為了方便調(diào)試內(nèi)存泄漏，我會(huì)在一些地方寫入這樣的代碼：#include #include #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以及：#ifdef _DEBUG _CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);#endif在閱讀時(shí)不用管它們，直接略過即可。第二章單鏈表鏈表是最常用、最簡(jiǎn)單和最基本的數(shù)據(jù)結(jié)構(gòu)之一。我們先來看看單鏈表的實(shí)現(xiàn)。2.1 代碼實(shí)現(xiàn)單鏈表的實(shí)現(xiàn)如下：/ 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 #include #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 / _DEBUGtemplateclass CNodepublic: T data; CNode *next; CNode() : data(T(), next(NULL) CNode(const T &initdata) : data(initdata), next(NULL) CNode(const T &initdata, CNode *p) : data(initdata), next(p) ;templateclass CSListprotected: int m_nCount; CNode *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;templateinline CSList:CSList() : m_nCount(0), m_pNodeHead(NULL)templateinline CSList:CSList(const T &initdata) : m_nCount(0), m_pNodeHead(NULL) AddHead(initdata);templateinline CSList:CSList() RemoveAll();templateinline int CSList:IsEmpty() const return 0 = m_nCount;templateinline int CSList:AddHead(const T data) CNode *pNewNode; pNewNode = new CNode; if (NULL = pNewNode) return 0; pNewNode-data = data; pNewNode-next = m_pNodeHead; m_pNodeHead = pNewNode; +m_nCount; return 1;templateinline int CSList:AddTail(const T data) return InsertAfter(GetCount(), data);/ if success, return the position of the new node./ if fail, return 0.templateinline int CSList:InsertBefore(const int pos, const T data) int i; int nRetPos; CNode *pTmpNode1; CNode *pTmpNode2; CNode *pNewNode; pNewNode = new CNode; 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 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 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.templateinline int CSList:InsertAfter(const int pos, const T data) int i; int nRetPos; CNode *pTmpNode; CNode *pNewNode; pNewNode = new CNode; 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 next; pNewNode-next = pTmpNode-next; pTmpNode-next = pNewNode; nRetPos = pos + 1;Exit1: +m_nCount;Exit0: return nRetPos;templateinline int CSList:GetCount() const return m_nCount;templateinline void CSList:RemoveAt(const int pos) ASSERT(1 = pos & pos = m_nCount); int i; CNode *pTmpNode1; CNode *pTmpNode2; pTmpNode1 = m_pNodeHead; / head node? if (1 = pos) m_pNodeHead = m_pNodeHead-next; goto Exit1; for (i = 1; i next; pTmpNode2-next = pTmpNode1-next;Exit1: delete pTmpNode1; -m_nCount;templateinline void CSList:RemoveHead() ASSERT(0 != m_nCount); RemoveAt(1);templateinline void CSList:RemoveTail() ASSERT(0 != m_nCount); RemoveAt(m_nCount);templateinline void CSList:RemoveAll() int i; int nCount; CNode *pTmpNode; nCount = m_nCount; for (i = 0; i next; delete m_pNodeHead; m_pNodeHead = pTmpNode; m_nCount = 0;templateinline T& CSList:GetTail() ASSERT(0 != m_nCount); int i; int nCount; CNode *pTmpNode = m_pNodeHead; nCount = m_nCount; for (i = 1; i next; return pTmpNode-data;templateinline T CSList:GetTail() const ASSERT(0 != m_nCount); int i; int nCount; CNode *pTmpNode = m_pNodeHead; nCount = m_nCount; for (i = 1; i next; return pTmpNode-data;templateinline T& CSList:GetHead() ASSERT(0 != m_nCount); return m_pNodeHead-data;templateinline T CSList:GetHead() const ASSERT(0 != m_nCount); return m_pNodeHead-data;templateinline T& CSList:GetAt(const int pos) ASSERT(1 = pos & pos = m_nCount); int i; CNode *pTmpNode = m_pNodeHead; for (i = 1; i next; return pTmpNode-data;templateinline T CSList:GetAt(const int pos) const ASSERT(1 = pos & pos = m_nCount); int i; CNode *pTmpNode = m_pNodeHead; for (i = 1; i next; return pTmpNode-data;templateinline void CSList:SetAt(const int pos, T data) ASSERT(1 = pos & pos = m_nCount); int i; CNode *pTmpNode = m_pNodeHead; for (i = 1; i next; pTmpNode-data = data;templateinline int CSList:Find(const T data) const int i; int nCount; CNode *pTmpNode = m_pNodeHead; nCount = m_nCount; for (i = 0; i data) return i + 1; pTmpNode = pTmpNode-next; return 0;#endif / _SINGLE_LIST_H_調(diào)用如下：/ FileName : slist.cpp/ Version : 0.10/ Author : Luo Cong/ Date : 2004-12-29 10:41:18/ Comment : /#include #include slist.husing namespace std;int main() int i; int nCount; CSList 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;代碼比較簡(jiǎn)單，一看就明白，懶得解釋了。如果有bug，請(qǐng)告訴我。2.2 效率問題考慮到效率的問題，代碼中聲明了一個(gè)成員變量：m_nCount，用它來記錄鏈表的結(jié)點(diǎn)個(gè)數(shù)。這樣有什么好處呢？在某些情況下就不用遍歷鏈表了，例如，至少在GetCount()時(shí)能提高速度。原書中提到了一個(gè)“表頭”（header）或“啞結(jié)點(diǎn)”（dummy node）的概念，這個(gè)結(jié)點(diǎn)作為第一個(gè)結(jié)點(diǎn)，位置在0，它是不用的，我個(gè)人認(rèn)為這樣做有點(diǎn)浪費(fèi)空間，所以并沒有采用這種做法。單鏈表在效率上最大的問題在于，如果要插入一個(gè)結(jié)點(diǎn)到鏈表的末端或者刪除末端的一個(gè)結(jié)點(diǎn)，則需要遍歷整個(gè)鏈表，時(shí)間復(fù)雜度是O(N)。平均來說，要訪問一個(gè)結(jié)點(diǎn)，時(shí)間復(fù)雜度也有O(N/2)。這是鏈表本身的性質(zhì)所造成的，沒辦法解決。不過我們可以采用雙鏈表和循環(huán)鏈表來改善這種情況。2.3 應(yīng)用：一元多項(xiàng)式（加法和乘法）2.3.1 基礎(chǔ)知識(shí)我們使用一元多項(xiàng)式來說明單鏈表的應(yīng)用。假設(shè)有兩個(gè)一元多項(xiàng)式：P1(X) = X2 + 2X + 3以及P2(X) = 3X3 + 10X + 6現(xiàn)在運(yùn)用中學(xué)的基礎(chǔ)知識(shí)，計(jì)算它們的和：P1(X) + P2(X) = (X2 + 2X + 3) + (3X3 + 10X + 6) = 3X3 + 1X2 + 12X1 + 9以及計(jì)算它們的乘積：P1(X) * P2(X) = (X2 + 2X + 3) * (3X3 + 10X + 6) = 3X5 + 6X4 + 19X3 + 26X2 + 42X1 + 18怎么樣，很容易吧？:) 但我們是靈長(zhǎng)類動(dòng)物，這么繁瑣的計(jì)算怎么能用手工來完成呢？（試想一下，如果多項(xiàng)式非常大的話）我們的目標(biāo)是用計(jì)算機(jī)來完成這些計(jì)算任務(wù)，代碼就在下面。2.3.2 代碼實(shí)現(xiàn)/ FileName : poly.cpp/ Version : 0.10/ Author : Luo Cong/ Date : 2004-12-30 17:32:54/ Comment : /#include #include slist.h#define Max(x,y) (x)(y) ? (x) : (y)typedef struct tagPOLYNOMIAL CSList 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 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 HighPower; +i) polymul-Coeff.AddTail(0); for (i = 0; i HighPower; +i) tmp1 = poly1-Coeff.GetAt(i + 1); for (j = 0; j 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(%dn, 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) = X2 + 2X + 3 poly1-HighPower = 2; poly1-Coeff.AddHead(0); poly1-Coeff.AddHead(1); poly1-Coeff.AddHead(2); poly1-Coeff.AddHead(3); / P2(X) = 3X3 + 10X + 6 poly2-HighPower = 3; poly2-Coeff.AddHead(3); poly2-Coeff.AddHead(0); poly2-Coeff.AddHead(10); poly2-Coeff.AddHead(6); / add result = 3X3 + 1X2 + 12X1 + 9 AddPolynomial(polyresult, poly1, poly2); PrintPoly(polyresult); / reset polyresult-Coeff.RemoveAll(); / mul result = 3X5 + 6X4 + 19X3 + 26X2 + 42X1 + 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 說明原書中只給出了一元多項(xiàng)式的數(shù)組實(shí)現(xiàn)，而沒有給出單鏈表的代碼。實(shí)際上用單鏈表最大的好處在于多項(xiàng)式的項(xiàng)數(shù)可以為任意大。（當(dāng)然只是理論上的。什么？你的內(nèi)存是無限大的？好吧，當(dāng)我沒說）我沒有實(shí)現(xiàn)減法操作，實(shí)際上減法可以轉(zhuǎn)換成加法來完成，例如 a - b 可以換算成 a + (-b)，那么我們的目標(biāo)就轉(zhuǎn)變?yōu)樽鲆粋€(gè)負(fù)號(hào)的運(yùn)算了。至于除法，可以通過先換算“-”，然后再用原位加法來計(jì)算。（現(xiàn)在你明白加法有多重要了吧？_）有興趣的話，不妨您試試完成它，我的目標(biāo)只是掌握單鏈表的使用，因此不再繼續(xù)深究。 第三章雙鏈表單鏈表學(xué)完后，理所當(dāng)然的就是輪到雙鏈表了。3.1 代碼實(shí)現(xiàn)雙鏈表的實(shí)現(xiàn)如下：/ 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 #include #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 / _DEBUGtemplateclass CNodepublic: T data; CNode *prior; CNode *next; CNode() : data(T(), prior(NULL), next(NULL) CNode(const T &initdata) : data(initdata), prior(NULL), next(NULL) ;templateclass CDListprotected: int m_nCount; CNode *m_pNodeHead; CNode *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);templateinline CDList:CDList() : m