读书笔记之《数据结构与算法分析——C语言描述》(原书第2版).doc

数据结构处算法分析读书笔记第一章前言1.1 所选教材我所选择的教材是数据结构与算法分析c语言描述（原书第2版），英文版的名称是data structures and algorithm analysis in c，作者是：(美)mark allen weiss。原书曾被评为20世纪顶尖的30部计算机著作之一。之所以选这本书，还因为它的简体中文版翻译得相当不错，几乎没有给我的阅读带来什么障碍。_这本教科书所使用的是c语言，也许很多人会说c语言已经过时了，但是，我认为在数据结构的学习中，应该用尽量简单的语言，以免进入了语言的细枝末节中，反而冲淡了主题。实际上在国外的许多大学中（甚至中学），数据结构和算法分析的课程是选用scheme的，例如mit麻省理工大学极其著名的sicp课程。呵呵，语言又能说明什么呢？1.2 写作原因数据结构与算法分析是计算机专业的必修课但遗憾的是，我在大学阶段并不是计算机专业的学生，以至于没有系统地跟着老师学习过这门课程。现在我已经工作了，在实际的工作中，我经常感到自己的基础知识不够，有很多问题无法解决。在经历了一段痛苦的斗争后，我选择了自学的道路，想把这门课程扎扎实实地学好。教科书中已经给出了大部分的代码，因此，我基本上也只是重复敲入了一次而已（或者是改写成c+），但这并不是没有意义的。我们在看书的时候经常会觉得自己已经懂了，但如果真的要亲自动手去做了，却会感到无法下手。我认为，亲自输入一次代码并调试通过，比任何空谈都有效。在具体的代码实现上，我可能会参考mfc、stl但也可能会进行一定的修改。1.3 一些约定我使用的是visual c+ 6.0编译器，并将会用c/c+来撰写代码（我可能会用c+改写原书中的例子，以便能用在工作中，但一些地方还是会用c），不会使用任何与平台相关的特性（因此可以保证有比较好的移植性）。原书中的代码风格跟我平时的代码风格非常相近，但有一些地方我可能会进行一些改动。我认为数据结构的代码不需要任何界面，因此，请您新建一个工程，类型为win32 console application，即控制台工程。然后添加一个.h头文件和一个.c/.cpp文件。头文件中，我一般会写3行固定格式的预编译语句，如下：#ifndef _list_h_#define _list_h_/ todo: add header body code here#endif / _list_h_表示这是一个list.h。另外，c+操作符new的实现在不同的编译器中都不太一样，在vc6中，如果new失败，则会返回null，程序中我用检测返回值是否为null来判断new是否成功，但如果这个代码是用别的编译器编译的，则要特别注意别的编译器是否也是用null来表示new失败的，否则很可能会导致无法意料的结果。为了方便调试内存泄漏，我会在一些地方写入这样的代码：#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在阅读时不用管它们，直接略过即可。第二章单链表链表是最常用、最简单和最基本的数据结构之一。我们先来看看单链表的实现。2.1 代码实现单链表的实现如下：/ 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_调用如下：/ 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;代码比较简单，一看就明白，懒得解释了。如果有bug，请告诉我。2.2 效率问题考虑到效率的问题，代码中声明了一个成员变量：m_ncount，用它来记录链表的结点个数。这样有什么好处呢？在某些情况下就不用遍历链表了，例如，至少在getcount()时能提高速度。原书中提到了一个“表头”（header）或“哑结点”（dummy node）的概念，这个结点作为第一个结点，位置在0，它是不用的，我个人认为这样做有点浪费空间，所以并没有采用这种做法。单链表在效率上最大的问题在于，如果要插入一个结点到链表的末端或者删除末端的一个结点，则需要遍历整个链表，时间复杂度是o(n)。平均来说，要访问一个结点，时间复杂度也有o(n/2)。这是链表本身的性质所造成的，没办法解决。不过我们可以采用双链表和循环链表来改善这种情况。2.3 应用：一元多项式（加法和乘法）2.3.1 基础知识我们使用一元多项式来说明单链表的应用。假设有两个一元多项式：p1(x) = x2 + 2x + 3以及p2(x) = 3x3 + 10x + 6现在运用中学的基础知识，计算它们的和：p1(x) + p2(x) = (x2 + 2x + 3) + (3x3 + 10x + 6) = 3x3 + 1x2 + 12x1 + 9以及计算它们的乘积：p1(x) * p2(x) = (x2 + 2x + 3) * (3x3 + 10x + 6) = 3x5 + 6x4 + 19x3 + 26x2 + 42x1 + 18怎么样，很容易吧？:) 但我们是灵长类动物，这么繁琐的计算怎么能用手工来完成呢？（试想一下，如果多项式非常大的话）我们的目标是用计算机来完成这些计算任务，代码就在下面。2.3.2 代码实现/ 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 说明原书中只给出了一元多项式的数组实现，而没有给出单链表的代码。实际上用单链表最大的好处在于多项式的项数可以为任意大。（当然只是理论上的。什么？你的内存是无限大的？好吧，当我没说）我没有实现减法操作，实际上减法可以转换成加法来完成，例如 a - b 可以换算成 a + (-b)，那么我们的目标就转变为做一个负号的运算了。至于除法，可以通过先换算“-”，然后再用原位加法来计算。（现在你明白加法有多重要了吧？_）有兴趣的话，不妨您试试完成它，我的目标只是掌握单链表的使用，因此不再继续深究。 第三章双链表单链表学完后，理所当然的就是轮到双链表了。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 #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:cdlis