ITPub博客

首页 > 应用开发 > IT综合 > 数据结构学习(C++)——单链表(定义与实现) (转)

数据结构学习(C++)——单链表(定义与实现) (转)

原创 IT综合 作者:gugu99 时间:2007-12-05 09:52:27 0 删除 编辑
数据结构学习(C++)——单链表(定义与实现) (转)[@more@]

节点类

#ifndef Node_HXML:namespace prefix = o ns = "urn:schemas-microsoft-com:Office:office" />

#define Node_H

 

template 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

【说明】因为数据结构里用到这个结构的地方太多了,如果用原书那种声明友元的做法,那声明不知道要比这个类的本身长多少。不如开放成员,事实上,这种结构只是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 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 (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 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 *p = new Node(value, current->link);

    current->link = p;

  }

 

  BOOL InsertBefore(const Type &value)//在当前节点的前面插入一节点,不改变current,改变prior

  {

    Node *p = new Node(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 *p = current;

    prior->link = p->link;

    current = p->link;

    delete p;

    return TURE;

  }

  else return FALSE;

  }

 

  BOOL RemoveAfter()//删除当前节点的下一个节点,不改变current

  {

  if (current->link != NULL && current != NULL)

  {

    Node *p = current->link;

    current->link = p->link;

    delete p;

    return TURE;   

  }

  else return FALSE;

  }

 

friend ostream & operator << (ostream & strm, List &l)

{

    l.First();

  while (l.current->link != NULL) stRM << *l.Next() << " " ;

  strm << endl;

    l.First();

  return strm;

}

 

protected:

 /*主要是为了高效的入队算法所添加的。因为Insert(),Remove(),RemoveAfter()有可能改变last但没有改变last所以这个算法如果在public里除非不使用这些,否则不正确。但是last除了在队列中非常有用外,其他的时候很少用到,没有必要为了这个用途而降低Insert(),Remove()的效率所以把这部分放到protected,实际上主要是为了给队列继承*/  void LastInsert(const Type &value)

  {

    Node *p = new Node(value, last->link);

    last->link = p;

  last = p;

  }

 

  void Initialize()//当表为空表时使指针复位

  {

    current = last = first;

  prior = NULL;

  }

 

  //这部分函数返回类型为Node指针,是扩展List功能的接口

  Node *pGet()

  {

  return current;

  }

 

  Node *pNext()

  {

  prior = current;

    current = current->link;

  return current;

  }

 

  Node *pGetNext()

  {

  return current->link;

  }

 

  Node *pGetFirst()

  {

  return first;

  }

 

  Node *pGetLast()

  {

  return last;

  }

 

  Node *pGetPrior()

  {

  return prior;

  }

 

  void PutLast(Node *p)

  {

  last = p;

  }

  //这部分插入删除函数不建立或删除节点,是原位操作的接口

  void Insert(Node *p)

  {

    p->link = current->link;

    current->link = p;

  }

 

  void InsertBefore(Node *p)

  {

    p->link = current;

    prior->link = p;

  prior = p;

  } 

 

  void LastInsert(Node *p)

  {

    p->link = NULL;

    last->link = p;

  last = p;

  }

 

  Node *pRemove()

  { 

  if (current != NULL && prior != NULL)

  {

    Node *p = current;

    prior->link = current->link;

    current = current->link;

    return p;

  }

  else return NULL;

  }

 

  Node *pRemoveAfter()

  {

  if (current->link != NULL && current != NULL)

  {

    Node *p = current->link;

    current->link = current->link->link;

    return p;  

  }

  else return NULL;

  }

 

 

 

private:

  List(const List &l);

  Node *first, *current, *prior, *last;//尽量不要使用last,如果非要使用先用End()使指针last正确

 

};

 

#endif

【说明】我将原书的游标类Iterator的功能放在了链表类中,屏蔽掉了返回值为Node以及Node*类型的接口,这样的链表简单、实用,扩充性能也很好。

【后记】在完成书后作业的时候,我发现了原书做法的好处,也就是我的做法的不足。如果使用原书的定义,在完成一个功能时,只需要写出对应的函数实现。而在我的定义中,必须先派生一个类,然后把这个功能作为成员或者友元。但是这种比较并不说明书上的定义比我的要合理。首先,使用到原位操作的情况并不多,书后作业只是一种特殊情况;换句话说,书上的定义只是对完成书后作业更实用些。其次,在使用到链表的时候,通常只会用到插入、删除、取数据、搜索等很少的几个功能,我的定义足够用了。而在完成一个软件时,对链表的扩充功能在设计阶段就很清晰了,这时可以派生一个新类在整个软件中使用,对整体的规划更为有利。而对于单个链表的操作,把它作为成员函数更好理解一些。也就是说我的定义灵活性不差。

 


来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/10748419/viewspace-988552/,如需转载,请注明出处,否则将追究法律责任。

请登录后发表评论 登录
全部评论
  • 博文量
    3122
  • 访问量
    2251986