(CSDN)数据结构学习(C++)~来自CSDN

数据结构学习（C++）——序言收藏题外话：先前有一篇文章叫《用C++模板描述的链表、栈、队列（声明与实现）》，当时是第一次发表文章（我才注册没几天），很不成熟，改了又改不说，还弄的老长，不利于阅读。于是我重写了一下，并且想做成一个系列，这从我的标题可以看出来。好，言归正传。本篇为后面一系列文章的序言，旨在说明写作的目的，以及写作的风格；或者说是为自己可能的错误，预先给个托词。如果您不想听我在这废话，请跳过本篇，直接阅读后面的文章。但是这样，我不能保证，您在阅读的同时，不会骂我白痴。为什么写这些文章这些文章可以说是《数据结构（用面向对象方法与C++描述）》这本书的读书笔记，但也不完全是。数据结构是计算机专业必修课——几乎每个计算机专业的学生都会推崇他的重要；同时，也是其他专业转修计算机专业的一个难点。从学习的角度来说，严蔚敏的《数据结构（C语言版）》是本不错的书。但是，C语言不是描述的理想工具。《数据结构（C语言版）》的前言里是这样说的：“虽然C语言不是抽象数据类型的理想描述工具，但鉴于目前和近一、二年内，……并增添了C++语言的引用调用参数传递方式等，构成了一个类C描述语言。”从抽象数据类型的定义——一个数学模型以及定义在该模型上的一组操作——可以看出，面向对象语言中类的概念和这个定义很接近，加之C语言的普及，用C++来描述于是就成了顺理成章的事情。于是，清华在2002年的考研参考书目中对《数据结构》的参考书做了改变，使用《数据结构（用面向对象方法与C++描述）》（殷人昆等编著，ISBN7-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，先建立一个Win32ConsoleApplication的emptyproject。后面将陆续往这个工程中添加文件（就是将后面介绍的每一个文件都添加进去，不然到时候找不到xx.h不要埋怨），每一个#ifndefxx_H～#endif和其中的部分为一个头文件，文件名为xx.h。例如：#ifndefList_H#defineList_H……#endif这一大块为一个文件，文件名为List.h数据结构学习（C++）-----单链表（定义与实现）节点类#ifndefNode_H#defineNode_HtemplateclassTypeclassNode//单链节点类{public:Typedata;NodeType*link;Node():data(Type()),link(NULL){}Node(constType&item):data(item),link(NULL){}Node(constType&item,NodeType*p):data(item),link(p){}};#endif【说明】因为数据结构里用到这个结构的地方太多了，如果用原书那种声明友元的做法，那声明不知道要比这个类的本身长多少。不如开放成员，事实上，这种结构只是C中的struct，除了为了方便初始化一下，不需要任何的方法，原书那是画蛇添足。下面可以看到，链表的public部分没有返回Node或者Node*的函数，所以，别的类不可能用这个开放的接口对链表中的节点操作。【重要修改】原书的缺省构造函数是这样的Node():data(NULL),link(NULL){}。我原来也是照着写的，结果当我做扩充时发现这样是不对的。当Type为结构而不是简单类型（int、……），不能简单赋NULL值。这样做使得定义的模板只能用于很少的简单类型。显然，这里应该调用Type的缺省构造函数。这也要求，用在这里的类一定要有缺省构造函数。在下面可以看到构造链表时，使用了这个缺省构造函数。当然，这里是约定带表头节点的链表，不带头节点的情况请大家自己思考。【闲话】请不要对int*p=newint(1);这种语法有什么怀疑，实际上int也可以看成一种class。单链表类#ifndefList_H#defineList_H#ifndefTURE#defineTURE1#endif#ifndefFALSE#defineFALSE0#endiftypedefintBOOL;#includeNode.htemplateclassTypeclassList//单链表定义{//基本上无参数的成员函数操作的都是当前节点，即current指的节点//认为表中“第1个节点”是第0个节点，请注意，即表长为1时，最后一个节点是第0个节点public:List(){first=current=last=newNodeType;prior=NULL;}~List(){MakeEmpty();deletefirst;}voidMakeEmpty()//置空表{NodeType*q;while(first-link!=NULL){q=first-link;first-link=q-link;deleteq;}Initialize();}BOOLIsEmpty(){if(first-link==NULL){Initialize();returnTURE;}elsereturnFALSE;}intLength()const//计算带表头节点的单链表长度{NodeType*p=first-link;intcount=0;while(p!=NULL){p=p-link;count++;}returncount;}Type*Get()//返回当前节点的数据域的地址{if(current!=NULL)return¤t-data;elsereturnNULL;}BOOLPut(Typeconst&value)//改变当前节点的data，使其为value{if(current!=NULL){current-data=value;returnTURE;}elsereturnFALSE;}Type*GetNext()//返回当前节点的下一个节点的数据域的地址，不改变current{if(current-link!=NULL)return¤t-link-data;elsereturnNULL;}Type*Next()//移动current到下一个节点，返回节点数据域的地址{if(current!=NULL&¤t-link!=NULL){prior=current;current=current-link;return¤t-data;}else{returnNULL;}}voidInsert(constType&value)//在当前节点的后面插入节点，不改变current{NodeType*p=newNodeType(value,current-link);current-link=p;}BOOLInsertBefore(constType&value)//在当前节点的前面插入一节点，不改变current，改变prior{NodeType*p=newNodeType(value);if(prior!=NULL){p-link=current;prior-link=p;prior=p;returnTURE;}elsereturnFALSE;}BOOLLocate(inti)//移动current到第i个节点{if(i=-1)returnFALSE;current=first-link;for(intj=0;current!=NULL&&ji;j++,current=current-link)prior=current;if(current!=NULL)returnTURE;elsereturnFALSE;}voidFirst()//移动current到表头{current=first;prior=NULL;}voidEnd()//移动current到表尾{if(last-link!=NULL){for(;current-link!=NULL;current=current-link)prior=current;last=current;}current=last;}BOOLFind(constType&value)//移动current到数据等于value的节点{if(IsEmpty())returnFALSE;for(current=first-link,prior=first;current!=NULL&¤t-data!=value;current=current-link)prior=current;if(current!=NULL)returnTURE;elsereturnFALSE;}BOOLRemove()//删除当前节点，current指向下一个节点，如果current在表尾，执行后current=NULL{if(current!=NULL&&prior!=NULL){NodeType*p=current;prior-link=p-link;current=p-link;deletep;returnTURE;}elsereturnFALSE;}BOOLRemoveAfter()//删除当前节点的下一个节点，不改变current{if(current-link!=NULL&¤t!=NULL){NodeType*p=current-link;current-link=p-link;deletep;returnTURE;}elsereturnFALSE;}friendostream&operator(ostream&strm,ListType&l){l.First();while(