数据结构一题！！
内容：本人现有一难题无法解决，望高手赐教，具体如下：
车厢调度问题：（用堆栈——顺序栈实现）调度入口有序列号为1，2，3....n的车厢，求从输出口输出的长度为n的车厢序列
望高手赐教算法！！多谢 最好能用c实现/
200分等你！！！
问题点数：20、回复次数：6Top
1 楼quicmous（快鼠）回复于 2002-07-13 22:47:07 得分 0
C语言源代码如下。说明：
1.MAXNUM为车厢数;
2.MAXCOPY用于保存已经打印方案的数量，防止打印重复的方案。实际上它的值设为MAXNUM的
阶乘比较合适，这样可以在print_result中动态申请内存，程序就比较完善了。因为我从网
上临时下载的BC3.1没有联机帮助，我记不清楚如何动态申请内存了，因此留有一个小小的瑕
毗。
3.pass,push,pop为三种可能的操作，它们返回操作后的列车状态TRAIN。
4.display(X)打印X状态下可能的输出。
#include <stdio.h>
#include <mem.h>
#define MAXNUM 4
#define MAXCOPY 100
typedef struct {
int R[MAXNUM];//进站的队列
int S[MAXNUM];//栈
int T[MAXNUM];//出站的队列
int RCount,SCount,TCount;//三个队列的长度
} TRAIN;
TRAIN pass(TRAIN X){
X.T[X.TCount]=X.R[X.RCount-1];
X.RCount--;
X.TCount++;
return X;
}
TRAIN push(TRAIN X){
X.S[X.SCount]=X.R[X.RCount-1];
X.RCount--;
X.SCount++;
return X;
}
TRAIN pop(TRAIN X){
X.T[X.TCount]=X.S[X.SCount-1];
X.SCount--;
X.TCount++;
return X;
}
void print_result(TRAIN X){
static int TCOPY[MAXCOPY][MAXNUM];
static int COPYCOUNT=0;
for (int i=0;i<COPYCOUNT;i++){
for (int j=0;j<MAXNUM;j++){
if (TCOPY[i][j]!=X.T[j]) goto NextCopy;
}
return;
NextCopy:
}
for (i=0;i<MAXNUM;i++){
printf("%d",X.T[i]);
TCOPY[COPYCOUNT][i]=X.T[i];
}
printf("\n");
COPYCOUNT++;
}
void display(TRAIN X){
if (!X.RCount) {
if (!X.SCount) print_result(X);
else display(pop(X));
}
else {
display(pass(X));
display(push(X));
if (X.SCount) display(pop(X));
}
}
void main(){
TRAIN X;
for (int i=0;i<MAXNUM;i++) X.R[i]=MAXNUM-i;
X.RCount=MAXNUM;
X.SCount=0;
X.TCount=0;
display(X);
}
Top
2 楼zhoukun666（我喜欢==〉{ 。}{ 。}）回复于 2002-07-15 20:15:01 得分 0
http://www.csdn.net/expert/topic/775/775678.xml?temp=.5317194Top
3 楼zhoukun666（我喜欢==〉{ 。}{ 。}）回复于 2002-07-15 20:17:35 得分 0
http://www.csdn.net/expert/topic/868/868504.xml?temp=.2995264Top
4 楼atlantis13579（更深的蓝)(^_^）回复于 2002-07-15 20:38:57 得分 20
【题目】火车调度问题
【参考程序】
const max=10;
type shuzu=array[1..max] of 0..max;
var stack,exitout:shuzu;
n,total:integer;
procedure output(exitout:shuzu);
var i:integer;
begin
for i:=1 to n do write(exitout[i]:2);writeln;
inc(total);
end;
procedure find(dep,have,rest,exit_weizhi:integer;stack,exitout:shuzu);
{dep:步数,have:入口处有多少辆车;rest:车站中有多少车;}
{exit_weizhi:从车站开出后,排在出口处的位置;}
{stack:车站中车辆情况数组;exitout:出口处车辆情况数组}
var i:integer;
begin {分入站,出站两种情况讨论}
if have>0 then begin {还有车未入站}
stack[rest+1]:=n+1-have; {入站}
if dep=2*n then output(exitout)
else find(dep+1,have-1,rest+1,exit_weizhi,stack,exitout);
end;
if rest>0 then begin {还有车可出站}
exitout[exit_weizhi+1]:=stack[rest]; {出站}
if dep=2*n then output(exitout) {经过2n步后,输出一种方案}
else find(dep+1,have,rest-1,exit_weizhi+1,stack,exitout);
end;
end;
begin
writeln('input n:');
readln(n);
fillchar(stack,sizeof(stack),0);
fillchar(exitout,sizeof(exitout),0);
total:=0;
find(1,n,0,0,stack,exitout);
writeln('total:',total);
readln;
end.
Top
5 楼atlantis13579（更深的蓝)(^_^）回复于 2002-07-15 20:39:09 得分 0
【解法2】用穷举二进制数串的方法完成.
uses crt;
var i,n,m,t:integer;
a,s,c:array[1..1000] of integer;
procedure test;
var t1,t2,k:integer;
notok:boolean;
begin
t1:=0;k:=0;t2:=0;
i:=0;
notok:=false;
repeat {二进制数串中,0表示出栈,1表示入栈}
i:=i+1; {数串中第I位}
if a[i]=1 then begin {第I位为1,则表示车要入栈}
inc(k); {栈中车数}
inc(t1); {入栈记录,T1为栈指针,S为栈数组}
s[t1]:=k;
end
else {第I位为0,车要出栈}
if t1<1 then notok:=true {已经无车可出,当然NOT_OK了}
else begin inc(t2);c[t2]:=s[t1];dec(t1);end;
{栈中有车,出栈,放到C数组中去,T2为C的指针,栈指针T1下调1}
until (i=2*n) or notok; {整个数串均已判完,或中途出现不OK的情况}
if (t1=0) and not notok then begin {该数串符合出入栈的规律则输出}
inc(m);write('[',m,']');
for i:=1 to t2 do write(c[i]:2);
writeln;
end;
end;
begin
clrscr; write('N=');readln(n);
m:=0;
for i:=1 to 2*n do a[i]:=0; {
repeat {循环产生N位二进制数串}
test; {判断该数串是否符合车出入栈的规律}
t:=2*n;
a[t]:=a[t]+1; {产生下一个二进制数串}
while (t>1) and (a[t]>1) do begin
a[t]:=0;dec(t);a[t]:=a[t]+1;
end;
until a[1]=2;
readln;
end.
N: 4 6 7 8
TOTAL: 14 132 429 1430
Top
