📄 pollux！出栈进栈的排列序列问题的算法！！！ - 考研论坛.htm
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0050)http://bbs.kaoyan.com/archivecontent.asp?id=427759 -->
<HTML><HEAD><TITLE>pollux！出栈进栈的排列序列问题的算法！！！ - 考研论坛</TITLE><LINK
href="pollux！出栈进栈的排列序列问题的算法！！！ - 考研论坛.files/DEFAULT.css" type=text/css
rel=stylesheet>
<META http-equiv=Expires content=0>
<META http-equiv=Cache-Control content=no-cache>
<META http-equiv=Pragma content=no-cache>
<META http-equiv=Content-Type content="text/html; charset=gb2312">
<META content="MSHTML 5.50.4134.100" name=GENERATOR></HEAD>
<BODY text=#000000 vLink=#000066 link=#000066 bgColor=#ffffff>
<CENTER>
<TABLE width="100%" border=0>
<TBODY>
<TR>
<TD>
<DIV align=right><A target=_blank
href="http://www.kaoyan.com/">kaoyan.com首页</A> | <A
href="http://bbs.kaoyan.com/default.asp">论坛总览</A> | <A
href="http://bbs.kaoyan.com/archive.htm">精华区</A> | <A
href="http://bbs.kaoyan.com/search.asp">论坛搜索</A> | <A
href="javascript:location.reload()">刷新本页</A> | <A
href="http://bbs.kaoyan.com/signup.asp">注册</A> | <A target=_blank
href="http://www.kaoyan.com/guestbook">批评建议</A> | <A target=_blank
href="http://shop.kaoyan.com/">书店</A> | <A
href="mailto:news@kaoyan.com">投稿</A> | <A target=_blank
href="http://chat.kaoyan.com/">聊天</A></DIV></TD></TR></TBODY></TABLE>
<TABLE width="100%" border=0>
<TBODY>
<TR>
<TD bgColor=#3399cc height=1></TD></TR></TBODY></TABLE></CENTER>
<CENTER>
<TABLE width="100%" border=0>
<TBODY>
<TR>
<TD>
<CENTER><IFRAME marginWidth=0 marginHeight=0
src="pollux！出栈进栈的排列序列问题的算法！！！ - 考研论坛.files/bbsadtop.htm" frameBorder=0
width=468 scrolling=no height=60
bordercolor="#000000"></IFRAME></CENTER><BR><BR><BR><IMG
src="pollux！出栈进栈的排列序列问题的算法！！！ - 考研论坛.files/ubbfriendminiicon.gif"
border=0> <B>论坛信使：</B><A
href="http://bbs.kaoyan.com/ubbmisc.asp?action=sendthread&Subject=pollux%A3%A1%B3%F6%D5%BB%BD%F8%D5%BB%B5%C4%C5%C5%C1%D0%D0%F2%C1%D0%CE%CA%CC%E2%B5%C4%CB%E3%B7%A8%A3%A1%A3%A1%A3%A1">发送本页给您的朋友！</A></TD>
<TD vAlign=top>
<P align=left><IMG src="pollux！出栈进栈的排列序列问题的算法！！！ - 考研论坛.files/open.gif"
align=absMiddle> <A
href="http://bbs.kaoyan.com/default.asp"><ACRONYM title=返回讨论区总页.><SPAN
class=smallFont>考研论坛</SPAN></ACRONYM></A> <BR><IMG
src="pollux！出栈进栈的排列序列问题的算法！！！ - 考研论坛.files/tline.gif" align=absMiddle
border=0><IMG src="pollux！出栈进栈的排列序列问题的算法！！！ - 考研论坛.files/open.gif"
align=absMiddle border=0><SPAN class=smallFont> <A
href="http://bbs.kaoyan.com/archivelist.asp?archiveid=8">计算机</A></SPAN><BR><IMG
src="pollux！出栈进栈的排列序列问题的算法！！！ - 考研论坛.files/tline3.gif" align=absMiddle
border=0><IMG src="pollux！出栈进栈的排列序列问题的算法！！！ - 考研论坛.files/open.gif"
align=absMiddle border=0><SPAN
class=smallFont> pollux！出栈进栈的排列序列问题的算法！！！</SPAN></P>
<P><SPAN class=smallFont><IFRAME marginWidth=0 marginHeight=0
src="pollux！出栈进栈的排列序列问题的算法！！！ - 考研论坛.files/newarchive.htm" frameBorder=0
width=150 scrolling=no height=19
BORDERCOLOR="#000000"></IFRAME></SPAN></P></TD></TR></TBODY></TABLE>
<TABLE width="100%" border=0>
<TBODY>
<TR>
<TD colSpan=2>注意：这是一个归档主题。它是只读的。 <BR>此主题先前所在的论坛：计算机</TD></TR>
<TR>
<TD colSpan=2></TD></TR></TBODY></TABLE>
<TABLE cellSpacing=1 cellPadding=4 width="100%" border=0>
<TBODY>
<TR bgColor=#3399cc>
<TD vAlign=center width="18%"><FONT color=#ffffff><B>发表人</B></FONT></TD>
<TD vAlign=center><FONT
color=#ffffff><B>主题: pollux！出栈进栈的排列序列问题的算法！！！</B></FONT></TD></TR>
<TR bgColor=#dcdcdc>
<TD vAlign=top noWrap width="18%">seflyer<BR><IMG
src="pollux！出栈进栈的排列序列问题的算法！！！ - 考研论坛.files/Image18.gif"
vspace=5><BR><B>中级站友</B><BR>积分：305<BR>发贴：75<BR>来自：china<BR>资格：2001-07-14<BR></TD>
<TD vAlign=top><IMG src="pollux！出栈进栈的排列序列问题的算法！！！ - 考研论坛.files/icon10.gif"
align=absMiddle border=0> 发表于 2001-10-04 <FONT
color=#000000>14:19:08</FONT> <A target=_blank
href="http://bbs.kaoyan.com/viewuser.asp?username=seflyer"><IMG
alt=按此观看seflyer的个人资料
src="pollux！出栈进栈的排列序列问题的算法！！！ - 考研论坛.files/profile.gif" align=absMiddle
border=0></A> <IMG alt=该用户不允许显示它的电子邮件
src="pollux！出栈进栈的排列序列问题的算法！！！ - 考研论坛.files/email.gif" align=absMiddle
border=0> <A
href="http://search.tencent.com/cgi-bin/friend/user_show_info?ln=85930412"><IMG
alt="seflyer 的 oicq 是85930412,查看 85930412 的资料"
src="pollux！出栈进栈的排列序列问题的算法！！！ - 考研论坛.files/oicq.gif" align=absMiddle
border=0></A> <A
href="http://bbs.kaoyan.com/pm.asp?action=newpm&recipient=seflyer&subject=pollux%A3%A1%B3%F6%D5%BB%BD%F8%D5%BB%B5%C4%C5%C5%C1%D0%D0%F2%C1%D0%CE%CA%CC%E2%B5%C4%CB%E3%B7%A8%A3%A1%A3%A1%A3%A1"><IMG
alt=发送悄悄话给seflyer src="pollux！出栈进栈的排列序列问题的算法！！！ - 考研论坛.files/pm.gif"
align=absMiddle border=0></A> <A target=_blank
href="http://bbs.kaoyan.com/search.asp?action=searchuser&username=seflyer"><IMG
height=16 alt=搜索seflyer的所有帖子
src="pollux！出栈进栈的排列序列问题的算法！！！ - 考研论坛.files/find.gif" width=16
align=absMiddle border=0></A> <A
href="http://bbs.kaoyan.com/posting.asp?Forum=8&Topic=427759&TopicSubject=pollux%A3%A1%B3%F6%D5%BB%BD%F8%D5%BB%B5%C4%C5%C5%C1%D0%D0%F2%C1%D0%CE%CA%CC%E2%B5%C4%CB%E3%B7%A8%A3%A1%A3%A1%A3%A1&action=editarchive"><IMG
alt=编辑/删除帖子 src="pollux！出栈进栈的排列序列问题的算法！！！ - 考研论坛.files/edit.gif"
align=absMiddle border=0 ?></A>
<HR>
你给出的问题我想了想，给出以下的seflyer算法，不排除有错误的可能，不过我验证了一下好像没错！可能对栈的操作有点敷衍了事，不过不影响理解。<BR>那个扩大了的称球问题，应该是NP完全的。没有最少的比较次数。
<P>BOOL Seflyer(type initial[Max],type
out[Max])<BR>{//验证给定的输入序列initial[Max]，out[Max]是否是合法的进栈出栈所得序列<BR> BOOL
Mark[Max];//凡是出栈的元素均打上标记，以后不再对它进行入栈操作<BR> BOOL
IsinStack[Max];//凡是在栈中的元素均打上标记，以后不再对它进行入栈操作<BR> Stack S;
//存放索引的栈<BR> InitialStack(S);<BR> for(i=0;i<Max;i++)//初始化<BR> {
Mark[i]=FALSE;
<BR> IsinStack[i]=FALSE;<BR> }
<BR> for(i=0;i<Max;i++)<BR> {<BR> while(initial[j]!=out[i])
//找到第i个出栈元素在初始序列中的位置j<BR>j++;
<BR> for(k=0;k<=j;k++)
//将在初始序列j位置前的，所有未处理的，且未入栈的元素入栈<BR> {<BR>
if(Mark[k]==FALSE &&
IsinStack[k]==FALSE)<BR>
{<BR> push(S,k);
<BR> IsinStack[k]=TRUE;<BR>
}<BR>
}<BR> if(GetTop(S)!=j)
//若已经有第j个元素在栈中（非栈顶），则出错无法规约！<BR>return
FALSE;<BR> pop(S);
//栈顶元素符合out[i]，所以出栈<BR> Mark[j]=TRUE;<BR>
}<BR> return TRUE; //正确的规约完<BR>}
<P>
<P>
<HR>
弃我去者昨日之日不可留，<BR>乱我心者今日之日多烦忧。</TD></TR>
<TR bgColor=#f7f7f7>
<TD vAlign=top noWrap width="18%">Pollux<BR><IMG
src="pollux！出栈进栈的排列序列问题的算法！！！ - 考研论坛.files/user1.gif"
vspace=5><BR><B>中级站友</B><BR>积分：306<BR>发贴：79<BR>来自：上海<BR>资格：2001-02-06<BR></TD>
<TD vAlign=top><IMG src="pollux！出栈进栈的排列序列问题的算法！！！ - 考研论坛.files/icon1.gif"
align=absMiddle border=0> 发表于 2001-10-04 <FONT
color=#000000>17:42:21</FONT> <A target=_blank
href="http://bbs.kaoyan.com/viewuser.asp?username=Pollux"><IMG
alt=按此观看Pollux的个人资料
src="pollux！出栈进栈的排列序列问题的算法！！！ - 考研论坛.files/profile.gif" align=absMiddle
border=0></A> <A href="mailto:pollux_bao@chinaren.com"><IMG
alt=按此发邮件给Pollux src="pollux！出栈进栈的排列序列问题的算法！！！ - 考研论坛.files/email.gif"
align=absMiddle border=0></A> <A
href="http://search.tencent.com/cgi-bin/friend/user_show_info?ln=48097898"><IMG
alt="Pollux 的 oicq 是48097898,查看 48097898 的资料"
src="pollux！出栈进栈的排列序列问题的算法！！！ - 考研论坛.files/oicq.gif" align=absMiddle
border=0></A> <A
href="http://bbs.kaoyan.com/pm.asp?action=newpm&recipient=Pollux&subject=pollux%A3%A1%B3%F6%D5%BB%BD%F8%D5%BB%B5%C4%C5%C5%C1%D0%D0%F2%C1%D0%CE%CA%CC%E2%B5%C4%CB%E3%B7%A8%A3%A1%A3%A1%A3%A1"><IMG
alt=发送悄悄话给Pollux src="pollux！出栈进栈的排列序列问题的算法！！！ - 考研论坛.files/pm.gif"
align=absMiddle border=0></A> <A target=_blank
href="http://bbs.kaoyan.com/search.asp?action=searchuser&username=Pollux"><IMG
height=16 alt=搜索Pollux的所有帖子
src="pollux！出栈进栈的排列序列问题的算法！！！ - 考研论坛.files/find.gif" width=16
align=absMiddle border=0></A> <A
href="http://bbs.kaoyan.com/posting.asp?Forum=8&Topic=428134&TopicSubject=pollux%A3%A1%B3%F6%D5%BB%BD%F8%D5%BB%B5%C4%C5%C5%C1%D0%D0%F2%C1%D0%CE%CA%CC%E2%B5%C4%CB%E3%B7%A8%A3%A1%A3%A1%A3%A1&action=editarchive"><IMG
alt=编辑/删除帖子 src="pollux！出栈进栈的排列序列问题的算法！！！ - 考研论坛.files/edit.gif"
align=absMiddle border=0 ?></A>
<HR>
Perfect!
<P></P></TD></TR>
<TR bgColor=#dcdcdc>
<TD vAlign=top noWrap width="18%">biwier<BR><IMG
src="pollux！出栈进栈的排列序列问题的算法！！！ - 考研论坛.files/Imagef1.gif"
vspace=5><BR><B>开国大老</B><BR>积分：1694<BR>发贴：426<BR>来自：四川大学<BR>资格：2000-05-14<BR></TD>
<TD vAlign=top><IMG src="pollux！出栈进栈的排列序列问题的算法！！！ - 考研论坛.files/icon1.gif"
align=absMiddle border=0> 发表于 2001-10-04 <FONT
color=#000000>22:04:21</FONT> <A target=_blank
href="http://bbs.kaoyan.com/viewuser.asp?username=biwier"><IMG
alt=按此观看biwier的个人资料
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -