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

deaboway

呵呵，可以这么说~~~~~
现在都已经是后网络时代了，6步应该够了！
好像扯远了……

Austern

这篇文章我仔细的看了一边，写的不错，感觉用C++来实现多层链表的遍历比C要来的灵活
不过有一点我想问一下，为什么偏要用末尾增加一个节点的方法来结束遍历呢/
这样会不会好一些
[code:1]
int myPoint::draw(){
  ……

  return (next?next->draw():0);
}
[/code:1]
多层链表有很多的末尾，每个末尾后添加一个myObj对象，我感觉会浪费不少资源

Fujinsan

是否浪费资源，主要取决于良好的设计。我以前曾有两个同事分别用VB和VC开发同一个软件，但是结果用VB做的反而运行速度更快。原因是使用VB的那位有更长的软件设计经验。

sjinny

[quote:a774a5ff5b="Austern"]这篇文章我仔细的看了一边，写的不错，感觉用C++来实现多层链表的遍历比C要来的灵活
不过有一点我想问一下，为什么偏要用末尾增加一个节点的方法来结束遍历呢/
这样会不会好一些
[code:1]
int myPoint::draw(){
  ……

  return (next?next->draw():0);
}
[/code:1]
多层链表有很多的末尾，每个末尾后添加一个myObj对象，我感觉会浪费不少资源[/quote]

是这样的，因为链表的遍历是依靠这个：
[code:1]
int foo::draw(){
    ..........

    return next->draw();
}
[/code:1]
所以，如果末尾没有myObj对象，那么最后一个节点的draw()被调用后，它最后一个操作是next->draw()，但它后面没有对象了，所以就成了NULL->draw()，要是next不是NULL，可能会更糟。要使遍历一个分支时，遍历行为能在链表末尾停下来，那么链表末尾的对象的draw()里，最后一句就必须是return 0;

呵呵，终于有人发问了，呵呵   

deaboway

[quote:d699652e37="Fujinsan"]是否浪费资源，主要取决于良好的设计。我以前曾有两个同事分别用VB和VC开发同一个软件，但是结果用VB做的反而运行速度更快。原因是使用VB的那位有更长的软件设计经验。[/quote]

我感觉还是算法比较重要，向你所说的情况，他们使用的算法一定不同……

sjinny

我的理想：用并不太复杂的数据结构来使算法简化。
一个程序，用最少的代码、最简单的设计来实现优秀的性能和功能，并且保证一定程度的可维护性，那就是完美的程序。
所以我一直安慰自己：虽然自己没写过XX万行代码，但是这不意味着我一定很菜~~ :D

wsm

还不错 树结构用得还不多 没怎么考虑过 （而且什么beita beita+ 红白 就是麻烦）不过还是更喜欢一些特定的优化算法
呵呵 还趁机推销自己的东东阿
附带说一句：小世界理论是个说法吧？可以证明么？ 我看不可以吧
1。选出任意个（>2）互相都不直接认识的人，这不会有困难吧？
2。其他人全部死掉。ok 现在一步迈不出去了
3。然后考虑可以加上的人，只要不达到这个6步规则就可以加上
4。剩下的人？今天还活着，你怎么知道明天演算完了他们还活着呢？
5。所以这个规则不存在

sjinny

据说这个理论是先做了实验然后得出的~~

喂，别说不相干的啊，谈谈这篇文章啊~~ :D 具体的技术问题~~ :D:D

进

源代码还好，看的懂。可一些专业的术语不太明白。自己对linux了解太少了！要补补了！

hibernate

我也觉得没有必要用到继承和虚节点的
因为这样加大开销（空间上和时间上）
我觉得可以这样：
return((next!=NULL)&&(next->draw()))（这么写为了清晰点，好分析）
为什么可以呢？
因为对于&&如果第一个参数是假的话就会直接返回false,不会接着计算
那么如果next==NULL,就不会出现next->draw()的情况
不知道sjinny认为呢？
当然，用到继承和虚节点可以解决多级链表是不同类型的事例
我说的方法当然只能用来遍历同种节点的例子了

sjinny

呵呵，有道理啊~~~
hibernate, 你的方法其实也可以用来遍历多级链表啊，因为是否要进入下一层的链表完全由每个节点自己决定的，所以我的方案应该照你的办法改进一下，这样就可以不要末尾的Obj对象了。这样在增加节点的时候就更方便了。
……
晕，才发现，这个办法其实和使用if语句进行判断也没区别嘛~~这样就增加了判断所用的时间，少了末尾对象占的空间。我的办法应该算用空间换时间吧~不过再想想，我的办法里还有个末尾对象的函数draw()的执行时间，那么，只有在链表足够长时，我的办法才能有用空间换时间的效果，可是为了防止栈嵌套的过多（什么是堆栈溢出？），链表的长度又不能太长，……，这样就不太好算了~~

hibernate

of course 我说的是多级链表
我只是说我的办法适应于节点是同一类的
如果节点是不同类的话，就应该用继承，用你说的办法
同时我并不认为你说的方法是用空间换时间
1：每个末节点你首先得执行一次virtue draw()
2：用继承本身就需要时间开销来链接的

当然，这和用if判断其实是一样的

sjinny

我觉得虚函数的时间开销应该不大吧，因为只是在一个虚函数表里查找地址，而且这种查找应该是直接用指针找到的吧，所以应该只是多了几层指针访问吧？不过C++标准里没有规定多态的具体实现方法，不知道gcc是怎么做的。

默难

呵呵~前几天又翻了翻数据结构，这个问题很像二叉树啊~可以借用堆栈和中间节点来实现~

sjinny

和二叉树有联系吗？？