使用面向对象的方法开发程序：多层链表的遍历

sjinny

my3Dgui开发过程中我的心得和经验 之一
  使用面向对象的方法开发程序：多层链表的遍历
    如果现在有一个链表，可以怎样来遍历？
[code:1]
for(obj* now=begin; now!=NULL; now=now->next){
  ……
}
[/code:1]
    那么如果链表之中有子链表呢？比如以下的结构：
[code:1]
●→●→●→●→●→●→●→●→●→●→●→●→●→NULL
    ↓         ↓     ↓
    ●         ●     ●→●→●→●→●→NULL
    ↓         ↓     ↓     ↓
    ●        NULL   ●     ●
    ↓               ↓     ↓
   NULL             ●     ●
                    ↓     ↓
                    NULL  ●→●→●→●→NULL
                          ↓
                         NULL
[/code:1]
    这样一组分层次结构的链表，又该如何遍历？其中有这样几个问题：1.每个节点可能是不同类型的；2.每一层链表的长度都是不同的、不可确定的；3.这一组链表的层数往往是不可确定的。
    第一个问题，使用面向对象中的多态特性就可以解决，既保证所有节点所属类都是由同一个基类直接或间接地派生而来的，把循环体中要用的成员函数作为虚函数放进基类中进行声明，节点间使用基类指针来连接。
    第二个问题，在使用for循环时，把运行循环体的条件设为“now指针没有指向NULL”，就像本文开头的那个例子。
    第三个问题，其中还可分为两个问题：1.如何进入子链表进行遍历；2.如何遍历多层子链表。一种办法是使用运行期类型检测，检测当前对象是否拥有子链表，然后再进行遍历；这样有两个缺点：运行期类型检测据说挺慢；遍历时，得检测每个节点的类型并做判断。如果不检测每个节点的类型，那么遍历时就不知道当前要处理的节点是否还拥有子链表，那么该怎么办呢？
    下面我提出我的办法：
    先看这样一个类：
[code:1]
class myPoint{
public:
        myPoint();
        ~myPoint();
  /** draw this point */
  int draw();
public: // Public attributes
  /** the pointer points to the next object */
  myPoint *next;
};
/** draw this point */
int myPoint::draw(){
  ……

  return next->draw();
}
[/code:1]
    请注意draw()函数体里最后一个语句：return next->draw();。设想一下：一个链表，每个节点都是myPoint类的实例，当调用头节点的draw()方法且该函数返回之后，整个链表都被遍历了一次，每个节点都依次被调用了draw()方法。使用这样的类，就避免了使用循环语句来进行遍历。可是，当执行了最后一个节点的draw()方法时，其实执行的就是NULL->draw()，这怎么行？另外，如果每个节点是不同类型的呢？那么就要使用这个类：
[code:1]
class myObj {
public:
        myObj();
        virtual ~myObj();
  /** draw this object
  if no problems return 0;
  */
  virtual int draw();
};
/** draw this object
if no problems return 0;
*/
int myObj::draw(){
  return 0;
}
[/code:1]
    原来的myPoint类要改成这样：
[code:1]
class myPoint : public myObj   {
public:
        myPoint();
        virtual ~myPoint();
  /** draw this point */
  virtual int draw();
public: // Public attributes
  /** the pointer points to the next object */
  myObj *next;
};
/** draw this point */
int myPoint::draw(){
  ……

  return next->draw();
}
myPoint::~myPoint(){
  delete next;
}
[/code:1]
    确保每个节点所属的类都是由myObj类派生而来；用于连接相临节点的指针是myObj类型的指针。这样就可以解决各个节点类型不同的问题了。当调用了头节点的draw()方法后，如何让这一“链式反应”在最后一个节点处终止并使函数返回呢？这就需要在链表的末尾再加一个节点，但是这个节点是myObj的实例。这样，当倒数第二个节点的draw()方法被调用后，最后一个节点，就是那个myObj类的实例的draw()方法将被调用，它将直接返回数值0，“链式反应”就结束了。这样，没有使用循环，不需要知道链表长度，也不需要知道每个节点的类型，仍然完成了遍历。那么，如何遍历多层链表呢？看看这个类：
[code:1]
class myShape : public myObj  {
public:
        myShape();
        virtual ~myShape();
  /** draw this shape with points */
  virtual int draw();
public: // Public attributes
  /** a pointer points to the first object (point) of this shape */
  myObj *objsBegin;
  /** a pointer points to the next object (shape) */
  myObj *next;
};
[/code:1]
    其中的objsBegin是个指针，指向了由myShape的一个实例所拥有的一个子链表。遍历这个子链表，只需要调用objsBegin->draw()就行了。所以，myShape的draw()方法是这样实现的：
[code:1]
/** draw this shape with points */
int myShape::draw(){
  ……
      objsBegin->draw();
  ……

  return next->draw();
}
[/code:1]
    所以，当myShape的一个实例在链表中被调用了draw()方法时，它会先遍历自己的子链表，然后再继续调用下一个节点的draw()方法。这样就实现了对子链表的遍历。同时，不需要知道链表的层数，无论链表的层次结构有多复杂，都可以通过使用这种结构的类来保证每个子链表都会被遍历。事实上，对于不同的链表，遍历时调用的方法都是可以不同的，这也增加了灵活性。
    至此，已经可以遍历多层次的链表了。那么怎样销毁这样一组链表呢？请注意这些代码：
[code:1]
myPoint::~myPoint(){
  delete next;
}
myShape::~myShape(){
  delete objsBegin;
  delete next;
}
[/code:1]
    这样，只需要delete这组链表的头节点，就可以把整组链表delete掉了。

    优点：灵活、模块化特性好。
    缺点：遍历时可能会使函数调用时的栈嵌套层数过多，遍历时会占用很多内存。

sjinny

有什么想讨论的请跟帖~~

goldpig

嘿嘿，看得有点乏力。板猪同学一方面认为大家的水平参差不齐，另一方面却又弄些抽像的东西出来，如此只怕时间长了就曲高和寡了，有违开坛之初衷。
windows能如此快的发展，雅俗共赏是它的脉门。
我个人喜欢带解决实际问题的，或是能指点思路的文章；而且也认为，真正要普及linux，有必要把一些专业术语市俗化。

呵呵，乱弹一气，也有点词不搭意，勿怪。

zhon

你这篇文章我没有仔细看，因为对于这方面内容我不是很熟悉，而且，c++用得不深，所以给不出什么评价了！

sjinny

本来想结合我写的程序讲的，但是发现涉及了太多琐碎的内容，就觉得太罗嗦，所以就没结合具体的程序。
Sorry~~~

wuhu

最好能具体个事例,别太大,让我们实践实践,实践才能长大嘛

Fujinsan

这样没有一个中心目标，活动是搞不起来的。两种方案：
要么从基础开始，按照学习大纲，一起找资料过来，大家一起读资料，谈心得；
要么从项目开始，按照所需技术，一起探讨和研究，分工进行，学以致用。

sjinny

我在构想一个游戏，但是……我没游戏编程的经验，所以没法带领团队做工作，可松散的开发模式可能结果是不了了之，就看各位的决心了~~~~

wuhu

[quote:bf5e409e83="Fujinsan"]
要么从项目开始，按照所需技术，一起探讨和研究，分工进行，学以致用。[/quote]
这个感觉挺好的,出现不足,自己去找资料,各位大哥也可以稍微轻松一下哦

sjinny

谈谈你想做什么~~

默难

嗯……感觉不错~很专业啊~

deaboway

看是看得懂，但是my3Dgui我不知是什么，多层链表的遍历的问题是数据结构的内容，这个我正在复习，因为要考高程。

缺点：遍历时可能会使函数调用时的栈嵌套层数过多，遍历时会占用很多内存。

我们短学期要编一个小世界的分析程序，我打算用Perl实现，主要的问题就是多层链表的遍历时的速度太慢。比如……分析几千字的《老子》竟然要5分钟！？郁闷ing

sjinny

你是怎样遍历链表的？
你看我的主页就知道my3Dgui了

deaboway

所谓小世界最初是说“世界上任意两个人的最短关系最多不超过六步”，我们的任务是分析中国的文学著作是否有小世界的性质，我现在准备用有向图解决它了，两个星期后我会把它放到网上，大家一同探讨之……

sjinny

其实“小世界”的性质体现的是人群之间的联系的紧密程度
如果这个社会信息不畅、人与人之间非常冷漠，那么6步是肯定不够的
这个实验倒是可以用来测量社会的文明程度，呵呵