|
以文本方式查看主题 - 中文XML论坛 - 专业的XML技术讨论区 (http://bbs.xml.org.cn/index.asp) -- 『 计算机考研交流 』 (http://bbs.xml.org.cn/list.asp?boardid=67) ---- [求助]出栈顺序判断程序 (http://bbs.xml.org.cn/dispbbs.asp?boardid=67&rootid=&id=63312) |
|
-- 作者：LarryG -- 发布时间：6/1/2008 11:13:00 AM -- [求助]出栈顺序判断程序 任意一个由1，2，……n组成的排列，判断其是否是 |
|
-- 作者：meirui -- 发布时间：6/1/2008 11:51:00 AM -- 思路：无论如何调度，我们的操作都是入栈和出栈，设定入栈为1，出栈为0，对n个元素有2n次这样的操作，例如n=4，则有操作11110000、10101010等，于是我们有理由构造一个操作命令队列b[]，注意这个队列中有三个要求： 1.其中1和0的数目要相等，代表入栈和出栈操作完整，入栈操作=出栈操作 2.从左往右1的数目一定不能小于0的数目，否则没有栈中元素可以出栈 3.数列第一个元素一定为1，最后一个一定为0，即第一次操作必须为入栈，最后一次操作必须 为出栈，这样就只需考察中间n-2元素，开头和结尾的数据没有必要考虑 于是按照这样的规则，就可以对n个元素进行全排列，找出符合规则的序列 |
|
-- 作者：LarryG -- 发布时间：6/1/2008 1:24:00 PM -- 谢谢！很有启发性！！ |
|
-- 作者：jeJee -- 发布时间：6/1/2008 2:21:00 PM -- 算法实际上就是对入栈出栈的模拟 有入栈序列a[] 和出栈序列 b[] 和一个栈 s 1，如果要入栈的数和要出栈的数相同，则直接入栈再出栈 2，如果不同，则先判断栈顶的数是否就是要出栈的数，如果是则直接出栈 3，否则就把要入栈的数入栈 4，重复1，2，3直到所有要入栈的数都已入栈 5，对于栈中剩下的数，如果栈顶元素等于出栈元素则直接出栈，如果不等则表明出栈序列非法 6，重复5直到栈中元素全部处理完，或出栈序列非法 |
|
W 3 C h i n a ( since 2003 ) 旗 下 站 点 苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》 |
14,610.350ms |