| #ifndef Node_H #define Node_H template <class Type> class Node //单链节点类 { public: Type data; Node<Type> *link; Node() : data(Type()), link(NULL) {} Node(const Type &item) : data(item), link(NULL) {} Node(const Type &item, Node<Type> *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。
单链表类定义和实现
| #ifndef List_H #define List_H #ifndef TURE #define TURE 1 #endif #ifndef FALSE #define FALSE 0 #endif typedef int BOOL; #include "Node.h" template <class Type> class List //单链表定义 { //基本上无参数的成员函数操作的都是当前节点，即current指的节点 //认为表中“第1个节点”是第0个节点，请注意，即表长为1时，最后一个节点是第0个节点 public: List() { first = current = last = new Node<Type>; prior = NULL; } ~List() { MakeEmpty(); delete first; } void MakeEmpty() //置空表 { Node<Type> *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<Type> *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<Type> *p = new Node<Type>(value, current->link); current->link = p; } BOOL InsertBefore(const Type &value)//在当前节点的前面插入一节点，不改变current，改变prior { Node<Type> *p = new Node<Type>(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 <= -1) return FALSE; current = first->link; for (int j = 0; current != NULL && j < i; j , current = current->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<Type> *p = current; prior->link = p->link; current = p->link; delete p; return TURE; } else return FALSE; }
文章整理：西部数码--专业提供域名注册、虚拟主机服务 相关文章
 热点关注
IDC资讯
虚拟主机
域名注册
托管租用
vps主机
智能建站
网站运营 建站经验 策划盈利 搜索优化 网站推广 免费资源 网站联盟 联盟新闻 联盟介绍 联盟点评 网赚技巧 行业资讯 业界动态 搜索引擎 网络游戏 门户动态 电子商务 广告传媒 网络编程 Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它 服务器技术 Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护 软件技巧 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷 Internet Explorer 网页制作 FrontPages Dreamweaver Javascript css photoshop fireworks Flash 程序设计 Java技术 C/C++ VB delphi 网络知识 网络协议 网络安全 网络管理 组网方案 Cisco技术 操作系统 Win2000 WinXP Win2003 Mac OS Linux FreeBSD
| |||||||
