当前位置：首页 » 软件开发

开发技术指南» 文章正文

    引言： 节点类 #ifndef Node_H tyle="MA

 

 

数据结构学习（C++）——单链表（定义与实现）
节点类

#define node_h 【程序编程相关:A LITE VIRUS ABOUT P】

#ifndef node_h 【推荐阅读:让应用程序从IE中获取键入的网址】

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()

...   下一页

» 本期热门文章：

· 热门栏目：

» 相关精选文章

» 其它相关：