数据结构学习(c)之单链表

《数据结构学习(c)之单链表》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、数据结构学习(C++)之单链表节点类ftifndefNodeH^defineNodeHtemplateclassNode//单链节点类{public:Typedata;Node*link;Node():data(Type()),link(NULL){}Node(constType&item):data(item),link(NULL){}Node(constType&item,Node*p):data(item),link(p){}};#endif【说明】因为数据结构里用到这个结构的地方太多了，如果川《数据结构》那种声明友

2、元的做法，那声明不知道要比这个类的本身长多少。不如开放成员，事实上，这种结构只是C中的struct,除了为了方便初始化一下，不需要任何的方法，原书那是画蛇添足。下而可以看到，链表的public部分没有返冋Node或者Node*的函数，所以，别的类不可能用这个开放的接口对链表中的节点操作。【重要修改】原书的缺省构造两数是这样的Node():data(NULL),link(NULL){}。我原來也是照着写的，结果当我做扩充时发现这样是不对的。当Type为结构而不是简单类型(im、……),不能简单赋NUI丄值。这样做使得定义的模板只能用于很少的简单类型。显然，这里应该调用T

3、ype的缺省构造函数。这也耍求，用在这里的类一定要有缺省构造函数。在下面可以看到构造链表时，使用了这个缺省构造函数。当然，这里是约定带表头节点的链表，不带头节点的情况请大家自己思考。【闲话】请不要对int*p=newint(1);这种语法冇什么怀疑，实际tint也口J以看成一种classo单链表类定义与实现itifndefListH^defineList_H#ifndefTURK#defineTURE1ttendifttifndefFALSE#defineFALSE0#endiftypedefintBOOL;#include"Node,h"template

4、Type>classList//单链表定义{//基本上无参数的成员函数操作的都是当询节点，即current指的节点〃认为表中“第1个节点”是第0个节点，请注意，即表长为1时，最后一个节点是第0个节点public:List(){first=current=last=newNode;prior=NULL;}"ListO{MakeEmpty0:deletefirst;}voidMakeEmpty0//置空表{Node*q;while(first->link!=NULL){q=first->link;first->link=q->link;delete

5、q;}InitializeO;)BOOLIsEmptyO{if(first->link==NULL){Initialize();returnTIRE;}elsereturnFALSE;)intLength()const//计算带表头节点的单链表长度{Node*p=first~>link;intcount=0;while(p!=NULL){p=p->link;count++;}returncount;)Type*Get()//返回当前节点的数据域的地址if(current!=NULL)return¤t->data;elsereturnNULL;)

6、BOOLPut(Typeconst&value)//改变当前节点的data,使其为value{if(current!=NULL){current->data=value;returnTIRE;}elsereturnFALSE;)Type*GetNcxt()//返冋当前节点的下一个节点的数据域的地址，不改变current{if(current->link!=NULL)return¤t->link->data;elsereturnNULL;)Type*Next()//移动current到下一个节点，返冋节点数据域的地址{if(current!=NULL&&cu

7、rrent-〉】ink!=NULL){prior=current;current=current->link;return¤t-〉data;)else{returnNULL;})voidInsert(constType&value)//在当前节点的后面插入节点，不改变current{Node*p二newNodc(value,currcnt->link);current->1ink=p;)BOOLInsertBefore(constTypeftvalue)//在当前节点的前面插入一节点，不改变current,改变pr