ITPub博客

首页 > 应用开发 > IT综合 > 数据结构学习(C++)——循环链表 (转)

数据结构学习(C++)——循环链表 (转)

原创 IT综合 作者:amyz 时间:2007-11-07 17:34:21 0 删除 编辑
数据结构学习(C++)——循环链表 (转)[@more@]

原书对循环链表的介绍很简略,实现部分也不完整(当然了,如果完整就又是重复建设)。而我也没觉得循环链表有什么别的用,他更应该是为了一个特殊的问题而产生的,这只是个人的看法。我从链表类派生出了循环链表,这需要注意几个细节。XML:namespace prefix = o ns = "urn:schemas-microsoft-com:Office:office" />

1.  构造函数:派生类实例化时,先调用基类的构造函数;因此,初始化循环链表的工作就是将带表头的空链表的表头节点的link指向表头节点,从而构成一个圈。

2.  析构函数:释放对象时,先调用派生类的析构函数,然后调用基类的析构函数。因此,释放循环链表只需要将循环链表变成普通的单链表,然后这个单链表会被基类的析构函数释放。这里假定不使用这种语句Base *p = new Drived;delete p;因为我在~List()前面没有加virtual。你可以参阅各种C++书籍搞清这类问题。

3.  判空函数:条件不是检测头节点的link是否为空,而是是否指向头节点。

4.  置空函数:原来的显然不能工作了,实际上只要从表头位置不断后删直到表空就可以了。

5.  Next():遇到表头节点要跳过去。

6.  Remove():当前节点是表头节点时不能删,删了表头节点的后果自己想吧(因为在循环链表中prior指针不一定为空——其实应该是一定不空,但是由于继承部分List函数,所以就是不一定了,以至于原来的Remove()检查可能无效);如果删除的是表尾节点,删除后当前指针将指向表头节点,要跳过去指向下一个。总之,使用Next()和Remove()时,不能让外界觉察到表头节点的存在,否则,当你循环计数时,表头节点就被算进去了。

7.  “<<”必须重写,否则,当你执行cout << CircList;这种东西时,天哪,自己想去吧;当然了,只需要拷贝过来修改一下循环判断就可以了。

8.  End()将不能工作,考虑到如果按照原来的功能来实现,效率很低,而且用处不大,所以修改End()功能定义为更正last指针。为避免混淆,将其放在private,对外不提供这个功能。

定义和实现

#ifndef CircList_H

#define CircList_H

 

include “List.h”

 

template class CircList : public List

{

public:

  CircList() { pGetFirst()->link = pGetFirst(); }

  ~CircList() { End(); pGetLast()->link = NULL; }

  BOOL IsEmpty()

  {

    Node *p = pGetFirst();

  return p->link == p;

  }

 

  Type *Next()

  {

  if (pNext() == pGetFirst()) pNext();

  return Get();

  }

 

  BOOL Remove()

  {

    if(!IsEmpty())

  {

  if (pGet() == pGetFirst()) return FALSE;

    List::Remove();

  if (pGet() == pGetFirst()) pNext();

    return TURE;

  }

  return FALSE;

  }

 

 

  void MakeEmpty()

  {

    First();

  while (!IsEmpty()) RemoveAfter();

  }

 

  void LastInsert(const Type &value)

  {

  End();

    List::LastInsert(value);

  }

private:

  void End()

  {

  if (pGetLast()->link != pGetFirst())

  {

    Node *pfirst = pGetFirst();

    for (Node *p = pGet(); p->link != pfirst; p = pNext());

    PutLast(p);

  }

  }

 

friend ostream & operator << (ostream & strm, CircList &cl)

{

    cl.First();

    Node *pfirst = cl.pGetFirst();

  while (cl.pGet()->link != pfirst) stRM << *cl.Next() << " " ;

  strm << endl;

    cl.First();

  return strm;

}

 

};

 

#endif

【说明】为了后面的约瑟夫问题,我添加了LastInsert。如果使用Insert是倒插,当然可以倒输入来解决,但这样的做法有将就的嫌疑,而不断的Locate显然效率太低。显然,Find,Loacte,Length这类继承过来的函数,运行起来会发生意想不到的事,我没有在这里给出重新的实现出于以下原因:

  • Find可以把原来的代码拷过来修改一下循环判定,但也可以不改。方法是,采用后面介绍的查找表的办法,在表头节点放查找值,这样就一定会查找成功了。然后检查当前节点是否为头节点就可以判断是否真正查找成功,如果你自己完成这个函数,将会有很多收获。给个例子:

BOOL Find(const Type &value)

  {

    pGetFirst()->data = value;

    List::Find(value);

  if (pGet() == pGetFirst()) return FALSE;

  return TURE;

  }

  • Locate原来的实现在这里其实也没什么语义的毛病,无非是转圈吗,当然怎么改随你。建议配合Length检查定位值的合法,这样可以把转圈提前扼杀。
  • Length你说循环链表有多长?就像无论多长的长跑比赛都可以在400米的跑道进行一样。这里建议增加一个私有数据成员length,在每次插入删除时调整,因为改动的地方比较多,所以我就偷懒了,主要是觉得很少用。

 

 

约瑟夫问题

几乎提到循环链表总要提到约瑟夫问题,而我当年还在学BASIC时,就告诉我解决这个问题要构造一个循环链表,当然了,在BASIC里是静态链表。真的好像循环链表就是为了这个问题而存在的。为了照顾没听说过的人,我简单介绍一下这个问题:

说是一个旅行社要从n名旅客中选出一名幸运旅客,为他提供免费环球旅行服务。方法是,大家站成圈,然后选定一个m,从第1个人开始报数,报到m时,这个人OUT,然后从下一个人开始重新从1报数,重复这个过程,直到最后剩下一个人就是幸运之星。问题就是谁是幸运者呢?或者说是怎样才能赢大奖。

我用这个问题测试了整数情况下循环链表各个成员函数的正确性,相应函数如下:

void CircListTest_int()

{

  CircList a;

  cout << endl << "整型循环链表测试:求解约瑟夫问题" << endl;

  int n, m;//n是总人数,m是报数值

  cout << "输入总人数:";

  cin >> n;

  cout << "输入报数值:";

  cin >> m;

  for (int i = 1; i <= n; i++) a.LastInsert(i);

  cout << a;

  a.Locate(0);

  for (i = 0; i < n - 1; i++)

  {

  for (int j = 0; j < m - 1; j++) a.Next();

  cout << "第" << *a.Get() << "位旅客被淘汰" << endl;

    a.Remove();

  }

  cout << "第" << *a.Get() << "位旅客获胜" << endl;

  cout << a;

  a.MakeEmpty();

  cout << a;

 

}

【后记】就是做了循环链表这个派生类,我才发现了原来写的链表类的许多隐患,比如原来的Find,在整数链表里当你寻找0时,无一例外的会停在表头,所以你现在看到的链表类已经和我当初写的有很大的变化了,也可能有些我还没有发现,欢迎指正。

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

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