2022年数据结构学习单链表 .pdf

《2022年数据结构学习单链表 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构学习单链表 .pdf（4页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构学习（C+）单链表（定义与实现）happycock（原作）转自 CSDN节点类#ifndef Node_H#define Node_Htemplate 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【说明】因为数据结构里用到这个结构的地方太多了，如果用原书那种声明友元的做法，那声明不知道要比这个类的

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

3、要有缺省构造函数。在下面可以看到构造链表时，使用了这个缺省构造函数。当然，这里是约定带表头节点的链表，不带头节点的情况请大家自己思考。【闲话】请不要对 int*p=new int(1);这种语法有什么怀疑，实际上 int 也可以看成一种class。单链表类#ifndef List_H#define List_H#ifndef TURE#define TURE 1#endif#ifndef FALSE名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 4 页 -#define FALSE 0#endiftypedef int BOOL;#include Node.htemplate c

4、lass 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(

5、first-link=NULL)Initialize();return TURE;else return FALSE;int Length()const/计算带表头节点的单链表长度Node*p=first-link;int count=0;while(p!=NULL)名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 4 页 -p=p-link;count+;return count;Type*Get()/返回当前节点的数据域的地址if(current!=NULL)return¤t-data;else return NULL;BOOL Put(Type const&val

6、ue)/改变当前节点的data，使其为valueif(current!=NULL)current-data=value;return TURE;else return FALSE;Type*GetNext()/返回当前节点的下一个节点的数据域的地址，不改变currentif(current-link!=NULL)return¤t-link-data;else return NULL;Type*Next()/移动 current 到下一个节点，返回节点数据域的地址if(current!=NULL¤t-link!=NULL)prior=current;current=cur

7、rent-link;return¤t-data;elsereturn NULL;void Insert(const Type&value)/在当前节点的后面插入节点，不改变current名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 4 页 -Node*p=new Node(value,current-link);current-link=p;BOOL InsertBefore(const Type&value)/在当前节点的前面插入一节点，不改变current，改变 priorNode*p=new Node(value);if(prior!=NULL)名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 4 页 -