数据结构学习(C)单链表(定义与实现).pdf-得力文库

资源描述

《数据结构学习(C)单链表(定义与实现).pdf》由会员分享，可在线阅读，更多相关《数据结构学习(C)单链表(定义与实现).pdf（4页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、数据结构学习（数据结构学习（C+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 值。这样做使

3、得定义的模板只能用于很少的简单类型。显然，这里应该调用 Type的缺省构造函数。这也要求，用在这里的类一定要有缺省构造函数。在下面可以看到构造链表时，使用了这个缺省构造函数。当然，这里是约定带表头节点的链表，不带头节点的情况请大家自己思考。【闲话】请不要对 int *p = new int(1);这种语法有什么怀疑，实际上 int 也可以看成一种 class。单链表类单链表类#ifndef List_H#define List_H#ifndef TURE#define TURE 1#endif#ifndef FALSE#define FALSE 0#endiftypedef int

4、 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-l

5、ink = 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

6、 return NULL;BOOL Put(Type const &value)/改变当前节点的 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 (curren

7、t != NULL & current-link != NULL)prior = current;current = current-link;return ¤t-data;elsereturn NULL;void Insert(const Type &value)/在当前节点的后面插入节点，不改变currentNode *p = new Node(value, current-link);current-link = p;BOOL InsertBefore(const Type &value)/在当前节点的前面插入一节点，不改变current，改变 priorNode *p = new Node(value);if (prior != NULL)

展开阅读全文