货场车皮的编序问题.docx

1、 8 货场车皮的编序问题 (2 人 ) 题目内容 (小 4号黑体 ) 在火车货场车皮编解场， 2 条轨道连接到 2 条侧轨道，形成 2 个铁路转轨栈，期中左边轨道为车皮入口，编号为 A； 右边轨道为出口编号为 D； 2 个铁路转轨栈分别编号为 C 和 D 入下图所示。编号为 a, b, c, , 的 n 各车皮依序停放在车皮的入口处，调度室要安排个车皮进出栈次序，使得在出口处个车皮按照预先制定的顺序依次出站。车皮移动时只能按照从左到右的方向移动。 实现要求： 对于给定的车皮数 n，以及各车皮的出站顺序，编程计算最优调度方案，使得移动车皮的次数最少。 问题解决要用到堆栈，分别用顺序栈和链栈实现。

2、 数据输入： 由文件 input.txt 给出数据。第一行有 1 个正整数 n，表示车皮数；接下来的 1 行是一个字符串，表示预先确定的车皮的出站顺序。 数据输出： 将计算得到的最优调度方案输出到文件 output.txt，文件的第一行使最少移动次数 m，接下来的 m 行使对于最优方案的 m 次移动。每次移动用“ cXY”的 3 个字符表示，其中 c 表示车皮编号， X 表示其时栈号， Y 表示目标栈号。如果无法调度则输出“ No Solution!” a, b, c, A D B C 铁路 转轨栈 输入文件示例 输出文件示例 input.txt 3 abc output.txt 5 c A

3、B b A B a A D b B D c B D #include #include typedef struct char stack60 ; int top ; Stack ; int stepsum=0 ; / 总步数 void initialize(Stack *a ) /初始化 a-top=0 ; int Read_File(Stack *a , int *len) /读取文件 FILE *fp ; int n=0,i=0 ; fp=fopen(“input.txt“ ,“r“ ) ; /打开文件 if(fp=NULL) printf(“打开文件失败 n“) ; exit(0) ;

4、 fscanf( fp ,“%d“ ,/读取车皮数 printf(“车皮数是 : %dn“,n) ; fscanf( fp ,“%s“ ,a-stack) ;/读取车皮编号 printf(“车皮编号 :%sn“,a-stack) ; for(i=0;a-stacki!=0 ; i+) ; if(i!=n)/读取到的车皮编号个数，和数字不相等时 printf(“输入的车皮数和对应的车皮编号个数不相等请在 input.txt 中修改 n“) ; fclose(fp) ; exit( 0 ) ;/读取失败，返回 0 a-top=n ; *len= n ; fclose(fp) ; return 1

5、; /= void ok_Write_to_file(char a4) FILE *fp ; fp=fopen(“output.txt“,“w“) ; if(fp=NULL) printf(“打开写入文件失败 n“) ; exit(0) ; int step=stepsum,j=0 ; printf(“nn %dn“,step) ; fprintf(fp,“ %dn“,step) ; for(j=0 ;j rankj temp=rankmax_min; rankmax_min=ranki ; ranki=temp ; return 1 ; /=Screen(A,B,C,D, Record_st

6、ep) ; void Screen(Stack *A,Stack *B,Stack *C,Stack *D,char Record_step4) int j ; if(stepsum0) printf(“- 第 %d 步 %s -n“,stepsum ,Record_stepstepsum-1) ; if(A-top 0) printf(“A:%-20s“,A-stack); else printf(“A: “) ; if(B-top0) printf(“B:%-20s“,B-stack); else printf(“B: “) ; if(C-top 0) printf(“C:%-20s“,C

7、-stack); else printf(“C: “) ; if(D-top 0) printf(“D:%-20s“,D-stack); else printf(“D: “) ; printf(“n“) ; for(j=0 ;jtop-1 ,ma=0;/ rank2ma 表示当前要送进 D 的车皮 rank1mz为当前送进 C 中的车皮 否则送进 B char ch ; while(1) if(rank2ma=A-stackA-top-1) /移动 从 A 到 D D-stack(D-top)+=A-stack-(A-top) ; /移动 D-stackD-top=0 ; A-stackA-t

8、op= 0 ; for(i=0 ;rank1i!=0 ;i+) / 删除已经排好顺序的 rank1 表示已经 从 A 运出去 rank1i=rank1i+1 ; mz- ; Record_stepstepsum0=rank2ma; /记录 从 A 移动到 D Record_stepstepsum1=A ; Record_stepstepsum2=D ; Record_stepstepsum3=0 ; ma+ ; / rank2ma 下一个要送到 D 的车皮编号 stepsum+ ; / 总步数 加 1 else if(rank1mz=A-stackA-top-1) / 从 A 移动到 C 中

9、Record_stepstepsum0=rank1mz; /记录移动 从 A 移动到 C 中 Record_stepstepsum1=A ; Record_stepstepsum2=C ; Record_stepstepsum3=0 ; stepsum+ ;/总步数 C-stack(C-top)+=A-stack-(A-top) ; /移动 C-stackC-top=0 ; A-stackA-top= 0 ; rank1mz=0; mz- ; else Record_stepstepsum0=A-stack-(A-top); / 记录从 A 移动到 B 中 Record_stepstepsum

10、1=A ; Record_stepstepsum2=B ; Record_stepstepsum3=0 ; stepsum+ ;/总步数 /从 A 移动到 B B-stack(B-top)+=A-stackA-top ; /移动 ch=A-stackA-top ; for( i=0;rank1i!=0 ;i+)/从 rank1 中删除 ch if(ch=rank1i) while(rank1i!=0) rank1i=rank1i+1 ; i+ ; mz- ; B-stackB-top=0 ; A-stackA-top= 0 ; Screen(A,B,C,D, Record_step) ; if

11、(mz0) if(b.stacki-1=rank2ma) return i ; /存在返回 i (i-1 为所在其下标 i- ; return -1 ; /没找到返回 -1 /333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333 int B_to_C_orD(Stack *A,Stack *B,Stack *C,Stack *D,int top,int *ma,char Record_

12、step4)/当不是栈顶时 从 B 运到 C ; 如果是栈顶则 B 送到 D /top-1 为所在其下标 while (B-top!=top) Record_stepstepsum0=B-stack-(B-top); / B 送 C Record_stepstepsum1=B ; Record_stepstepsum2=C ; Record_stepstepsum3=0 ; stepsum+ ;/总步数 C-stack(C-top)+=B-stackB-top ; C-stackC-top=0 ; B-stackB-top=0 ; Screen(A,B,C,D, Record_step) ;

13、if(top=B-top) /是栈顶 从 B 移动到 D Record_stepstepsum0=B-stack-(B-top); Record_stepstepsum1=B ; Record_stepstepsum2=D ; Record_stepstepsum3=0 ; stepsum+ ; /总步数 D-stack(D-top)+=B-stackB-top ; D-stackD-top=0 ; B-stackB-top=0 ; (*ma)+ ;/下一个要移动 的车皮 Screen(A,B,C,D, Record_step) ; return 1 ; return 0; /44444444

14、4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444 int C_to_D (Stack *A,Stack *B,Stack *C,Stack *D,char rank2 ,int *ma ,char Record_step4) / rank2ma 表示当前要送进 D 的车皮 / 因为移动顺序只能从左到右 所以 rank2ma不在 D 栈顶时，则 if(C-stack(C-top-1)=rank2*ma)/ 如果

15、 在 栈 顶 则 C 送到 D / 输出 No Solution！ Record_stepstepsum0=C-stack-(C-top); Record_stepstepsum1=C ; /记录移动 从 C 到 D Record_stepstepsum2=D ; Record_stepstepsum3=0 ; stepsum+ ;/总步数 D-stack(D-top)+=C-stackC-top ; D-stackD-top=0 ; C-stackC-top=0 ; (*ma)+ ; / return 1 ; else return 0 ; / 返回 0 的时候为 无法调度 输出 No So

16、lution！ /= void main() Stack A,B,C,D;/栈号 initialize(initialize(initialize(initialize(/初始化 char Record_step664 ;/ Record_step 记录移动的步骤 int top ; int fal=-1 ;/ 最后对 在 C 中的车皮进行判断 如果为 0 的时候则为无法调度 int len=0 ; /输入的 车皮数 int k=0; char rank160,rank260 ; /对车皮的顺序进行排序 int ma=-1; / 在排列好的序列中 要送到 D 的车皮的序号 Read_File( /读取文件 for(int i=0; i0)/当 B 不为空时在 B 找 top=Judge(B , ma, rank2 ) ;/判断下个送到 D 的是否在 B 中 如果在返回值 top （ top-1 为所在其下标） if(top0)/在 B 中 top=B_to_C_orD( /当不是