数据结构处算法分析――读书笔记第一章前言1.1所选教材我所选择的教材是《数据结构与算法分析——C语言描述》（原书第2版），英文版的名称是《》，作者是：(美)为20世纪顶尖的30部计算机著作之一。之所以选这本书，还因为它的简体中文版翻译得相当不错，几乎没有给我的阅读带来什么障碍。^_^这本教科书所使用的是语言已经过时了，但是，我认为在数据结构的学习中，应该用尽量简单的语言，以免进入了语言的细枝末节中，反而冲淡了主题。实际上在国外的许多大学中（甚至中学），数据结构和算法分析的课程是选用例如MIT麻省理工大学极其著名的SICP课程。呵呵，语言又能说明什么呢？1.2写作原因数据结构与算法分析是计算机专业的必修课——但遗憾的是，我在大学阶段并不是计算机专业的学生，以至于没有系统地跟着老师学习过这门课程。现在我已经工作了，在实际的工作中，我经常感到自己的基础知识不够，有很多问题无法解决。在经历了一段痛苦的斗争后，我选择了自学的道路，想把这门课程扎扎实实地学好。教科书中已经给出了大部分的代码，因此，我基本上也只是重复敲入了一次而已（或者是改写成C++），但这并不是没有意义的。
我们在看书的时候经常会觉得自己已经懂了，但如果真的要亲自动手去做了数据结构于算法分析，却会感到无法下手。我认为，亲自输入一次代码并调试通过，比任何空谈都有效。在具体的代码实现上，我可能会参考MFC、STL„„但也可能会进行一定的修改。1.3一些约定我使用的是.0编译器，并将会用C/C++来撰写代码（我可能会用C++改写原书中的例子数据结构于算法分析 读书笔记之《数据结构与算法分析——C语言描述》(原书第2版)，以便能用在工作中，但一些地方还是会用C），不会使用任何与平台相关的特性（因此可以保证有比较好的移植性）。原书中的代码风格跟我平时的代码风格非常相近，但有一些地方我可能会进行一些改动。我认为数据结构的代码不需要任何界面，因此，请您新建一个工程，类型为ion，即控制台工程。然后添加一个.h头文件和一个.c/.cpp文件。头文件中，我一般会写3行固定格式的预编译语句，如下：##:e#表示这是一个list.h。另外，C++操作符new的实现在不同的编译器中都不太一样，在VC6中，如果new失败，则会返回NULL，程序中我用检测返回值是否为NULL来判断new是否成功，但如果这个代码是用别的编译器编译的，则要特别注意别的编译器是否也是用NULL来表示new失败的，否则很可能会导致无法意料的结果。
为了方便调试内存泄漏，我会在一些地方写入这样的代码：####(,,)#endif###[];#endif####endif####endif#以及：#gFlag(F);#endif在阅读时不用管它们，直接略过即可。第二章单链表链表是最常用、最简单和最基本的数据结构之一。我们先来看看单链表的实现。2.1代码实现单链表的实现如下：-12-299:58:38#H__#H__####(,,)#endif###[];#endif####endif####endif#next;CNode()data(T()),next(NULL)data(),next(NULL)&,(),next(p):;CNode;:();(const&);~();:()const;()const;(,);(,);();();();();();();()const;()const;GetAt();GetAt()const;(,data);()const;::()(0),(NULL)::((0),(NULL)::~()::() ::(const CNode; ; ) data;->next ; ;++; ::(const ((), data); , . fail, ::(const int pos, const ; CNode ; CNode ; CNode ; ; ; empty, . NULL; ; ; valid? (1 head node? ; ; ; head node, ; ;->next ; pos;Exit1: ++; Exit0: ; , . fail, ::(const int pos, const ; CNode ; CNode ; ; ; empty, . NULL; ; ; valid? (1 after ->next;->next ; Exit1:++; Exit0: ; ::() const ; ::(const int pos) );int CNode; CNode ; ? ->next;goto Exit1; after , ; ->next;Exit1: ; --; ::() );(1); ::() );(); ::() ; CNode ; ->next; ; );int ; CNode ; ->data; ::()const );int ; CNode ; ->data; ); ->data; ::()const ); ->data; ::GetAt( pos) );int CNode ->data; ::GetAt( pos) const );int CNode ->data; ::SetAt(const int pos, );int CNode ::Find(const data)const ; CNode * ; ->data) 调用如下： 2004-12-2910:41:18 # # "slist.h" using std; int main() ; slist; #ifdef ( F);#endif slist.(slist.(slist.(1), slist.(10);slist.(slist.(slist.(), slist.();slist.(); 代码比较简单，一看就明白，懒得解释了。
如果有bug，请告诉我。2.2 效率问题 考虑到效率的问题，代码中声明了一个成员变量：，用它来记录链表的结点个数。 这样有什么好处呢？在某些情况下就不用遍历链表了，例如，至少在()时能提高速 原书中提到了一个“表头”（）或“哑结点”（）的概念，这个结点作为第 一个结点，位置在0，它是不用的，我个人认为这样做有点浪费空间，所以并没有采用这种 做法。 单链表在效率上最大的问题在于，如果要插入一个结点到链表的末端或者删除末端的一个结 点，则需要遍历整个链表，时间复杂度是 O(N)。平均来说，要访问一个结点，时间复杂度 也有 O(N/2)。这是链表本身的性质所造成的，没办法解决。不过我们可以采用双链表和循 环链表来改善这种情况。 2.3 应用：一元多项式（加法和乘法） 2.3.1 基础知识 我们使用一元多项式来说明单链表的应用。假设有两个一元多项式： P1(X) 以及P2(X) 现在运用中学的基础知识，计算它们的和：P1(X) 以及计算它们的乘积：P1(X) 18怎么样，很容易吧？:) 但我们是灵长类动物，这么繁琐的计算怎么能用手工来完成呢？（试 想一下，如果多项式非常大的话„„）我们的目标是用计算机来完成这些计算任务，代码就 在下面。
2.3.2 代码实现 2004-12-3017:32:54 # # "slist.h" # Max(x,y) ; int ; ; void ( , const poly1, const poly2 ; int tmp1; int tmp2; -> Max(poly1->,poly2->); poly1->Coeff.GetAt(i);tmp2 poly2->Coeff.GetAt(i);sum tmp2;->Coeff.(sum); ( , const poly1, const poly2 ; int tmp1; int tmp2; -> tmp2;->Coeff.SetAt(i (const poly) ("%dX^%d ("%dn",poly->Coeff.()); () NULL; poly2 NULL; NULL;#ifdef ( F);#endif poly1 new( ); poly1)goto Exit0; poly2 new( ); poly2)goto Exit0; new( ); )goto Exit0; poly1->Coeff.(0);poly1->Coeff.(1); poly1->Coeff.(2); poly1->Coeff.(3); poly2->Coeff.(3);poly2->Coeff.(0); poly2->Coeff.(10); poly2->Coeff.(6); (,poly1, poly2); (); ->Coeff.(); (, poly1, poly2); (); Exit0: ; poly1 ; poly2 ; 2.3.3说明 原书中只给出了一元多项式的数组实现，而没有给出单链表的代码。
实际上用单链表最大的 好处在于多项式的项数可以为任意大。（当然只是理论上的。什么？你的内存是无限大的？ 好吧，当我没说„„） 我没有实现减法操作，实际上减法可以转换成加法来完成，例如 那么我们的目标就转变为做一个负号的运算了。至于除法，可以通过先换算“-”，然后再用原位加法来计算。（现在你明白加法有多重要了吧？^_^）有兴趣的话，不妨您试试完成它， 我的目标只是掌握单链表的使用，因此不再继续深究。 第三章 双链表 单链表学完后数据结构于算法分析，理所当然的就是轮到双链表了。 3.1 代码实现 双链表的实现如下： 2005-1-410:33:21 #H__ # # # #ifdef # new (, , ) #endif #ifdef # new #undef char [] ;#endif #ifdef # # #endif #else # # #endif #endif prior; CNode next; CNode() data(T()),prior(NULL), next(NULL) data(),prior(NULL), next(NULL) :int ; CNode ; CNode ; : (); (const &);~(); : int () const; int () const; int (const int pos, const data);int (const int pos, const data);int (const data);int (const data);void (const int pos); void (); void (); void (); ()const; ()const; GetAt( pos); GetAt( pos) const; void SetAt(const int pos, data);int Find(const data)const; (int&pos); (int&pos); ::() (0),(NULL), (NULL) ::(const (0),(NULL), (NULL) ::~() ::(int&pos) );(1 );int CNode* ++pos; ->data; ::(int&pos) );(1