data_数据结构——CSDN.doc

1 数据结构学习（C+）序言 题外话：先前有一篇文章叫用C+模板描述的链表、栈、队列（声明与实现），当时是第一次发表文章（我才注册没几天），很不成熟，改了又改不说，还弄的老长，不利于阅读。于是我重写了一下，并且想做成一个系列，这从我的标题可以看出来。好，言归正传。本篇为后面一系列文章的序言，旨在说明写作的目的，以及写作的风格；或者说是为自己可能的错误，预先给个托词。如果您不想听我在这废话，请跳过本篇，直接阅读后面的文章。但是这样，我不能保证，您在阅读的同时，不会骂我白痴。为什么写这些文章这些文章可以说是数据结构（用面向对象方法与C+描述）这本书的读书笔记，但也不完全是。数据结构是计算机专业必修课几乎每个计算机专业的学生都会推崇他的重要；同时，也是其他专业转修计算机专业的一个难点。从学习的角度来说，严蔚敏的数据结构（C语言版）是本不错的书。但是，C语言不是描述的理想工具。数据结构（C语言版）的前言里是这样说的：“虽然C语言不是抽象数据类型的理想描述工具，但鉴于目前和近一、二年内，并增添了C+语言的引用调用参数传递方式等，构成了一个类C描述语言。”从抽象数据类型的定义一个数学模型以及定义在该模型上的一组操作可以看出，面向对象语言中类的概念和这个定义很接近，加之C语言的普及，用C+来描述于是就成了顺理成章的事情。于是，清华在2002年的考研参考书目中对数据结构的参考书做了改变，使用数据结构（用面向对象方法与C+描述）（殷人昆等编著，ISBN 7-302-03405-2/TP1845）作为参考书，而实际上考的也是（废话，不是那叫误导）。坦白的讲，原书把教学目的和提供实例的目的搞混了，结果是个四不象：作为教科书，条理不清晰；提供各个方法的实现，也不是很实用，相反，重复建设太多。至于错误，可能有些是笔误，比如少个友元声明了，不是继承而使用别的类的成员函数没有指明了；还有一些，就是考虑不够周全。不管怎么说，现在不是挑书的时候，你想考清华的计算机专业研究生吗，这本书是你不二的选择。我发现读懂此书的最好方法，就是自己按照书上的思路，以及实际应用的分析，自己重新实现各种抽象数据类型。这样做还有一个好处，为自己将来积累一点财富。我的写作风格编译器我选用的是VC6，因此，我不保证我提供的代码在别的编译器也能通过从头到尾只使用了iostream.h，没有任何别的库，当然更没有MFC，标准的C+代码应该没什么问题。全部是手工完成的代码，没有使用ClassWizard，主要是不喜欢那些乱七八糟的预处理和注释。这样完成之后，发现C+的声明和实现分开xx.h+xx.ccp这种文档结构并不招人喜欢很乱。于是我采用了单工程单cpp的结构，就是一个工程只有一个cpp文件，放main()，其他的部分都是头文件，声明和实现放在一起其实这是违反C+规范的，C+要求函数必须声明原型，实际上，我觉得这很罗嗦（我这是典型的C后遗症，以前用TC时为了不声明原型，把函数都放到main()前面），声明一下原型，我认为这和设定密码需要确认一个道理。由于使用的IDE环境，把声明单独集中起来作为一个文件已经没有必要ClassView窗口很好用，就因为如此，我几乎从来不去看类的声明文件。除非你提供的是一个库，在你的工程中单独的声明文件已经不是必须的了。当然，这里的前提是从一个空的工程建立你的项目。如果你使用了AppWizard，我很难想象不使用ClassWizard的。因为这时文档的结构已经确定了，你所做的实际上是在修修补补。什么人适合读这些文章l 刚开始从C过渡到C+的人，看完这些后，会体会到C+的新特性。l 和我一样研读那本黄皮书的人，希望看完之后能更好的理解和学习。l 从未编写过超过1000行代码程序的人，这样我们才能达到共鸣。因为我们从来不使用工具和库文件，做的事都是在编程老手看来很蠢的事。一些约定假定你使用的是VC6，先建立一个Win32 Console Application的empty project。后面将陆续往这个工程中添加文件（就是将后面介绍的每一个文件都添加进去，不然到时候找不到xx.h不要埋怨），每一个#ifndef xx_H#endif和其中的部分为一个头文件，文件名为xx.h。例如：#ifndef List_H#define List_H#endif这一大块为一个文件，文件名为List.h2 单链表（定义与实现）2.1 节点类#ifndef Node_H#define Node_H template class Node /单链节点类public: Type data; Node *link; Node() : data(Type(), link(NULL) Node(const Type &item) : data(item), link(NULL) Node(const Type &item, Node *p) : data(item), link(p) ;#endif【说明】因为数据结构里用到这个结构的地方太多了，如果用原书那种声明友元的做法，那声明不知道要比这个类的本身长多少。不如开放成员，事实上，这种结构只是C中的struct，除了为了方便初始化一下，不需要任何的方法，原书那是画蛇添足。下面可以看到，链表的public部分没有返回Node或者Node*的函数，所以，别的类不可能用这个开放的接口对链表中的节点操作。【重要修改】原书的缺省构造函数是这样的Node() : data(NULL), link(NULL) 。我原来也是照着写的，结果当我做扩充时发现这样是不对的。当Type为结构而不是简单类型（int、），不能简单赋NULL值。这样做使得定义的模板只能用于很少的简单类型。显然，这里应该调用Type的缺省构造函数。 这也要求，用在这里的类一定要有缺省构造函数。在下面可以看到构造链表时，使用了这个缺省构造函数。当然，这里是约定带表头节点的链表，不带头节点的情况请大家自己思考。【闲话】请不要对int *p = new int(1);这种语法有什么怀疑，实际上int也可以看成一种class。2.2 单链表类#ifndef List_H#define List_H#ifndef TURE#define TURE 1#endif#ifndef FALSE#define FALSE 0#endiftypedef int BOOL;#include Node.htemplate class List /单链表定义/基本上无参数的成员函数操作的都是当前节点，即current指的节点/认为表中“第1个节点”是第0个节点，请注意，即表长为1时，最后一个节点是第0个节点public: List() first = current = last = new Node; prior = NULL; List() MakeEmpty(); delete first; void MakeEmpty() /置空表 Node *q; while (first-link != NULL) q = first-link; first-link = q-link; delete q; Initialize(); BOOL IsEmpty() if (first-link = NULL) Initialize(); return TURE; else return FALSE; int Length() const /计算带表头节点的单链表长度 Node *p = first-link; int count = 0; while (p != NULL) p = p-link; count+; return count; Type *Get()/返回当前节点的数据域的地址 if (current != NULL) return ¤t-data; else return NULL; BOOL Put(Type const &value)/改变当前节点的data，使其为value if (current != NULL) current-data = value; return TURE; else return FALSE; Type *GetNext()/返回当前节点的下一个节点的数据域的地址，不改变current if (current-link != NULL) return ¤t-link-data; else return NULL; Type *Next()/移动current到下一个节点，返回节点数据域的地址 if (current != NULL & current-link != NULL) prior = current; current = current-link; return ¤t-data; else return NULL; void Insert(const Type &value)/在当前节点的后面插入节点，不改变current Node *p = new Node(value, current-link); current-link = p; BOOL InsertBefore(const Type &value)/在当前节点的前面插入一节点，不改变current，改变prior Node *p = new Node(value); if (prior != NULL) p-link = current; prior-link = p; prior = p; return TURE; else return FALSE; BOOL Locate(int i)/移动current到第i个节点 if (i link; for (int j = 0; current != NULL & j link) prior = current; if (current != NULL) return TURE; else return FALSE; void First()/移动current到表头 current = first; prior = NULL; void End()/移动current到表尾 if (last-link != NULL) for ( ;current-link != NULL; current = current-link) prior = current; last = current; current = last; BOOL Find(const Type &value)/移动current到数据等于value的节点 if (IsEmpty() return FALSE; for (current = first-link, prior = first; current != NULL & current-data != value; current = current-link) prior = current; if (current != NULL) return TURE; else return FALSE; BOOL Remove()/删除当前节点，current指向下一个节点，如果current在表尾，执行后current = NULL if (current != NULL & prior != NULL) Node *p = current; prior-link = p-link; current = p-link; delete p; return TURE; else return FALSE; BOOL RemoveAfter()/删除当前节点的下一个节点，不改变current if (current-link != NULL & current != NULL) Node *p = current-link; current-link = p-link; delete p; return TURE; else return FALSE; friend ostream & operator (ostream & strm, List &l) l.First(); while (l.current-link != NULL) strm *l.Next() ; strm endl; l.First(); return strm; protected: /*主要是为了高效的入队算法所添加的。因为Insert()，Remove()，RemoveAfter()有可能改变last但没有改变last所以这个算法如果在public里除非不使用这些，否则不正确。但是last除了在队列中非常有用外，其他的时候很少用到，没有必要为了这个用途而降低Insert()，Remove()的效率所以把这部分放到protected，实际上主要是为了给队列继承*/ void LastInsert(const Type &value) Node *p = new Node(value, last-link); last-link = p; last = p; void Initialize()/当表为空表时使指针复位 current = last = first; prior = NULL; /这部分函数返回类型为Node指针,是扩展List功能的接口 Node *pGet() return current; Node *pNext() prior = current; current = current-link; return current; Node *pGetNext() return current-link; Node *pGetFirst() return first; Node *pGetLast() return last; Node *pGetPrior() return prior; void PutLast(Node *p) last = p; /这部分插入删除函数不建立或删除节点，是原位操作的接口 void Insert(Node *p) p-link = current-link; current-link = p; void InsertBefore(Node *p) p-link = current; prior-link = p; prior = p; void LastInsert(Node *p) p-link = NULL; last-link = p; last = p; Node *pRemove() if (current != NULL & prior != NULL) Node *p = current; prior-link = current-link; current = current-link; return p; else return NULL; Node *pRemoveAfter() if (current-link != NULL & current != NULL) Node *p = current-link; current-link = current-link-link; return p; else return NULL; private: List(const List &l); Node *first, *current, *prior, *last;/尽量不要使用last，如果非要使用先用End()使指针last正确 ; #endif【说明】我将原书的游标类Iterator的功能放在了链表类中，屏蔽掉了返回值为Node以及Node*类型的接口，这样的链表简单、实用，扩充性能也很好。【后记】在完成书后作业的时候，我发现了原书做法的好处，也就是我的做法的不足。如果使用原书的定义，在完成一个功能时，只需要写出对应的函数实现。而在我的定义中，必须先派生一个类，然后把这个功能作为成员或者友元。但是这种比较并不说明书上的定义比我的要合理。首先，使用到原位操作的情况并不多，书后作业只是一种特殊情况；换句话说，书上的定义只是对完成书后作业更实用些。其次，在使用到链表的时候，通常只会用到插入、删除、取数据、搜索等很少的几个功能，我的定义足够用了。而在完成一个软件时，对链表的扩充功能在设计阶段就很清晰了，这时可以派生一个新类在整个软件中使用，对整体的规划更为有利。而对于单个链表的操作，把它作为成员函数更好理解一些。也就是说我的定义灵活性不差。2.3 单链表应用（一元多项式【1】） 总算到了这里，这时，你会很得意的说，辛辛苦苦学的单链表总算知道能干点什么了。但是很不幸，如果你和我一样看的是那本书，到这里，你可能比学双向链表时还要痛苦。如果你是按照书上的介绍一步一步做到这里，你能把书上的多项式加法函数调试出来，我对你致以十二分的敬意。说到这里，我想起来我发单链表的时候，有人给我建议说：最好把链表和链表位置这两个分开。没错，C+标准库是这么做的，而我也不是什么专家，也不能证明什么优劣；但是，对于初学者来说，一个类总比两个类好操作。我不清楚原书这部分的程序究竟调没调试，但这种语句我是绝对看不懂的：ListNode *pa, *pb, *pc, *p;ListIterator Aiter(ah.poly);ListIterator Biter(ah.poly);pa = pc = Aiter.First(); pb = p = Biter.First();.pa-coef = pa-coef + pb-coef;p = pb; pb = Biter.Next(); delete p;如果你没有原书，我来解释一下。pa, pb, p 究竟指向什么？你说这很清楚，ListNode这样的节点呗。但按照原书的定义，ListIterator:First()等等函数返回是指向data域的指针，他们怎么能直接赋值？到了下面更乱了，pb指向的区域直接分解出了Term的数据成员，也就是说是指向Term结构的；然后让ListNode类型的指针p指向这个Term结构，最后，居然把这个结构delete了，天啊，ListNode这样的节点的data域被delete了！如果从基本的节点操作入手，谁也不会弄的这么乱。但正因为又多了一个类，很多事就疏忽了。所以，我并不怀疑标准库的做法，只是对于初学者，同一时间最好只对一个类操作。我以我的定义为基础，重新完成了这段程序。我并不欣赏原位操作的多项式加法（），PolyA+PolyB，然后B就嗖的一下没了，A就多了一堆（也可能少了一堆）；你作intJ+intK的时候怎么没见J和K有什么变化。与其这样，重载“+”还不如写成PolyA.Add(PolyB)或者PolyAdd(PolyA,PolyB)。一元多项式类定义与实现#ifndef Polynomial_H#define Polynomial_H #include List.h class Termpublic: int coef; int exp; Term() : coef(0), exp(0) Term(int c, int e) : coef(c), exp(e) Term(int c) : coef(c), exp(0) ; class Polynomial : Listpublic: void Input() cout endl 输入多项式的各项系数和指数; cout endl 注意：请按降序输入各项,输入系数0表示结束 endl; int coef, exp; for(int i = 1; ; i+) cout 第 i coef; if (coef) cout exp; Term term(coef, exp); Insert(term); else break; void Print() cout endl; First(); if (!IsEmpty() Term *p = Next(); cout coef; if (p-exp) cout exp != 1) cout exp; while (Next() != NULL) p = Get(); if (p-coef 0) cout +; cout coef; if (p-exp) cout exp != 1) cout exp; cout endl; friend void PolyAdd (Polynomial &polyA, Polynomial &polyB) Node *pA, *pB; polyA.First();polyB.First(); pA = polyA.pNext();pB = polyB.pNext(); while (pA != NULL & pB !=NULL) if (pA-data.exp = pB-data.exp) pA-data.coef = pA-data.coef + pB-data.coef; polyB.Remove(); if (!pA-data.coef) polyA.Remove(); else polyA.pNext(); else if (pA-data.exp pB-data.exp) polyB.pRemove(); polyA.InsertBefore(pB); else if (pA-data.exp data.exp) polyA.pNext(); pA = polyA.pGet();pB = polyB.pGet(); if (pA = NULL) polyA.pGetPrior()-link = pB; polyB.pGetPrior()-link = NULL; ; #endif【说明】对于多项式，通常我们都是降序书写的，于是我就要求降序输入。但是对于做加法来说，确实升序的要方便一些，于是，实际上到了内部，就变成升序的了。对于输出格式（从C的时候我就不喜欢做这个），尽量照顾习惯，但是当非常数项系数为1的时候还是会输出系数的，我实在不想把一个实际应用中根本拿不出台的输出函数搞的很复杂。为我编起来方便，输出变成了升序的，请多包含。测试程序就不给了，很简单。在续篇中，我将完成一元多项式“”“”“”“”的重载为什么没有“”，这种运算我拿笔算都不麻利，编起来就更闹心了，我还清楚的记得拿汇编写多字节除法程序时的痛苦。到了下一篇，你就可以这样写了a=b+c*d;a.Print();2.4 单链表应用（一元多项式【2】） 按照原书的安排，对多项式的讲解到上一篇就应该结束了，但我还想做一些延伸。比如说，你很清楚多项式的系数肯定不总是整数，但为什么用整型呢？我看到原书用的是整型，我也有这个疑问。但是，一旦动起手来，就会发现改成浮点不仅仅只是在定义Term时把int coef;改成float coef;很多的细节都要考虑到（给个提示，你知道浮点零是多少吗）。我试了一下，最后放弃了；理由是，写这些只是为了学习，没必要搞的那么复杂，能说明问题就可以了。在下面将会有些重载运算符的例子，我们的工作将是使多项式的运算看起来更符合书写习惯。完成这些是我觉得我擅自将原书的“”改成了PolyAdd()，总要给个交待吧。很快你就会看到原位运算的多项式加法在多项式运算中有多么重要，往下看之前，请确保弄懂了上一篇的内容。准备工作下面将完成单链表的赋值运算的重载，请把这部分加到List类的public部分。的确，这部分也可以放在多项式类里实现；但是，复制一个多项式实际上就是复制一个单链表，与其单单做一个多项式赋值，还不如完成单链表的赋值，让派生类都能共享。operator = (const List &l) MakeEmpty(); for (Node *p = l.first-link; p != NULL; p = p-link) LastInsert(p-data); 还记得List类的private里面的这个List(const List &l)吗？当初怕它惹祸，直接将它禁用了，既然现在=都能用了，为了这种语法List b = a;顺便也把它完成了吧。现在可以把它从private放到public了。List(const List &l) first = current = last = new Node; prior = NULL; for (Node *p = l.first-link; p != NULL; p = p-link) LastInsert(p-data); 终于可以这样写了a = b + c * dfriend Polynomial operator + (Polynomial &polyA, Polynomial &polyB) Polynomial tempA = polyA;Polynomial tempB = polyB; PolyAdd(tempA, tempB); return tempA; friend Polynomial operator * (Polynomial &polyA, Polynomial &polyB) Node *pA = polyA.pGetFirst()-link; Node *pB = polyB.pGetFirst()-link; Polynomial polyTempA, polyTempB; int coef, exp; if (pA = NULL | pB = NULL) return polyTempA; for (pA = polyA.pGetFirst()-link; pA != NULL; pA = pA-link) for(pB = polyB.pGetFirst()-link; pB != NULL; pB = pB-link) coef = pA-data.coef * pB-data.coef; exp = pA-data.exp + pB-data.exp; Term term(coef, exp); polyTempB.LastInsert(term); PolyAdd(polyTempA, polyTempB); polyTempB.Initialize(); return polyTempA;【后记】很显然，在“”的处理上我偷懒了，但这是最方便的。乘法部分只要参照手工运算，还是很简单的，我就不解释了。对于“”，可以先完成（a）这样的算法，然后就可以用加法完成了，而你要是象我一样懒很可能就会做这种事a1a，真的不提倡，超低的效率。对于除法，如果你会用汇编写多字节除法（跟手工计算很像），依样画葫芦也能弄出来，但首先要完成“”。如果要写又得好长，留给你完成吧。到这里你明白原位加法的重要了吧，这些运算实际上都是靠它实现的。3 双向链表 3.1 序原书这部分内容很多，至少相对于循环链表是很多。相信当你把单链表的指针域搞清楚后，这部分应该难不倒你。现在我的问题是，能不能从单链表派生出双向链表？你可以有几种做法：一种就是先定义一个双链节点但是，它的名字必须叫Node，这是没办法的事；不然你就只好拷贝一份单链表的实现文件，把其中的Node全都替换成你的双链节点名字，但是这就不叫继承了。另一种做法就是先定义一种结构例如这样的：template class newtypepublic:Type data;Node *link;当你派生双向链表时，这样写template class DblList : public Listnewtype ，注意连续的两个“”之间要有空格。或者根本不定义这样的结构，直接拿Node类型来做，例如我下面给出的。但是，请注意要完成“=”的重载，否则，你又要重写Find函数，