[讨论]给大家出道题提提神

[skycn]

拓扑排序

这是我们老师留的题目，我已经做出来了，但算法不很好，题目如下

用C写一个程序，该程序从一个文本文件中读入一组字符，该文件的内容格式如下：
ab
ac
bd
be
cd
ce
df
eg
fh
gi

这种排列方式产生了一个拓扑图形，如下：
b d f h
a
c e g i

a的后面是b, b的后面是d和e, c的后面是d和e................
以此类推。

要求1: 将这个图形重新排列，并按照类似下面的顺序重新输出到屏幕上：
abcdefghi

要求2: 找出所有符合要求1的排列顺序，类似这样的排列acbedgfih也是符合要求的，找出所有的，并输出到屏幕

////////////////////
我的做法是:把每一个字符都给一个等级，a是1级，b,c是2级，d,e是3级，f,g是4级，i,h是5级，然后按级别输出。第二步，把所有的字符所有的排列可能性都找出来，然后再按等级输出，这样就找出所有符合规定的排列。这种算法在寻找所有可能的排列顺序时候很费时间，如果一个图很大的话，时间会很久。

就这个，我题目已经交了，绝对不是为了骗答案，纯粹娱乐，各位朋友各抒己见吧

[boliang319]

这是图论当中一个经典的问题。

首先，根据输入构造一个图，输入的每一行都是图中的一条有向边，输入的字母，就是节点。
比方说输入ab，那么对应的边就是 a -->b
此外，对于图的每一个节点，都定义一个出度与入度的概念。
所谓出度，就是由该节点发出去的有向边的条数， 所谓入度，则是指图中指向该节点的边的条数。
例如，对于题目中的例子，a的出度为2，入度为0；b的出度为2，入度为1；一次类推吧

产生所有序列的过程是一个使用深度优先的方法不断的在图中删除节点的过程。
每一次，可以从图中删除入度为0的节点，当有多于1个如度为0的节点的时候，就有了多个分之，
可以采用深度优先的方法，检查每一个分支。删除节点的同时，需要删除所有与该结点相关的边。
比方说删除节点a以后，边a-->b,a-->c被删除，这时候，bc的入度也就成了0，下一步就有了两个
可以被删出的节点：b和c
使用这样的方法，当图中所有的节点都被删除了，也就获得了满足条件的序列了。

不知道搂主看懂了没有，如果有点糊涂的话，可以去看看图论书，里头有好多类似的有意思的东西。

[skycn]

我明白，这种方法我试过，但可能是我理解有误，所以没有成功，是这样

因为输出的格式必须是：a bc de fg hi
这样，如果我递归删除的话，就成了这样： 找到a，把a删除，a的后面是bc。找到b，把b删除，b后是de。找到c,删除c,c后是de。找到d，d后是f,删除d。找到f，删除f，f后是h。找到h，删除h，h后面没了。然后倒回来，找到e，删除e，e后是g。找到g，删除g，g后是i。找到i，没了。

上面每删除一个字符就输出一个字符，最后，结果是这样： a bc dfh egi
这就不对了

图论我们还没学，你说对了，这道题就是数学老师出的

[skycn]

我明白了，我应该删入度为0的，不应该递归删。递归的话，就一条线下去了，所以到了d的时候，下一个被删的一定是f

可惜已经交了

[boliang319]

尽量不要用递归，递归的性能不好。
频繁的子程序调用会增加额外的处理时间。

我明白了，我应该删入度为0的，不应该递归删。递归的话，就一条线下去了，所以到了d的时候，下一个被删的一定是f

可惜已经交了

[skycn]

可是如果用诸如while类的循环的话，篇幅会太长，特别容易自己把自己稿乱了，递归相对明了一些
另外，我有个问题不明白，一个递归函数，比如，function(int max)
它调用它自己的时候，我是这样：
max--;
function(max);
好呢，还是
function(max--);
比较好。

我今天发现这两种方式的结果是不一样的，为什么？

[boliang319]

可是如果用诸如while类的循环的话，篇幅会太长，特别容易自己把自己稿乱了，递归相对明了一些
另外，我有个问题不明白，一个递归函数，比如，function(int max)
它调用它自己的时候，我是这样：
max--;
function(max);
好呢，还是
function(max--);
比较好。

我今天发现这两种方式的结果是不一样的，为什么？

代码： 全选

 max--;
function(max);

等价于

代码： 全选

function(--max);

而

代码： 全选

function(max--);［/code]则等价于[code]function(max);
max--;

也就是a-- 与 --a的差别，--在前的话就是先做减一操作，再引用变量的指；--在后则是先引用变量的值，然后减一操作。

[xhy]

很死的题目

如果对象全部都是字符
就容易的很