怎么用C语言递归实现火车调度算法
怎么用C语言递归实现火车调度算法
这篇文章主要介绍怎么用C语言递归实现火车调度算法，文中介绍的非常详细，具有一定的参考价值，感兴趣的小伙伴们一定要看完！
1、代码
题目如下：
2.8编号为1，2，3，4的四列火车通过一个栈式的列车调度站，可能得到的调度结果有哪些？如果有n列火车通过调度站，请设计一个算法，输出所有可能的调度结果。
算法运用的思想是运用栈+递归，算法的难点也在于此。先上代码：
#include<stdio.h>#defineMAX100typedefstructs{chara[MAX];inttop;}Stack;/*定义栈的数据*//*定义一些全局变量*/StackS;/*定义全局性的栈*/chard[MAX],seq[MAX];/*d[MAX]用于存储原始入栈序列，seq[MAX]用于存储输出序列*/intlen;/*定义将通过栈的元素个数*/intcount=0;/*用于统计输出序列的个数*/voidinitStack(Stack*S)/*初始化空栈*/{S->top=-1;}voidpush(Stack*S,charx)/*进栈*/{if(S->top>=MAX)return;S->top++;S->a[S->top]=x;}charpop(Stack*S)/*出栈*/{if(S->top==-1){printf("ERROR,POPEmptyStack");return-1;}S->top--;returnS->a[S->top+1];}intisEmpty(Stack*S)/*判断栈是否为空*/{if(S->top==-1)return1;return0;}voidoutSeq(char*seq,intlen)/*输出顶点序列*/{inti;for(i=0;i<len;i++)printf("%2c",seq[i]);printf("\n");}voidscheduler(intpos,intseq_pos){/*pos:处理到原始数据中的第pos个元素，seq_pos：若出栈，应放在当前输出数组的第seq_pos个位置*/inti=0;chart;/*对任何一个数，总是先进栈，再出栈。另外，这里不需要循环，类似于"查找数组中元素"用递归*/if(pos<len){/*一个数进栈后,有两种处理方式：要么立刻出栈,要么进行下一个数的进栈*/push(&S,d[pos]);scheduler(pos+1,seq_pos);pop(&S);}if(!isEmpty(&S)){/*一个数出栈后,有两种处理方式：要么继续出栈,要么继续下一个数的进栈*/t=pop(&S);seq[seq_pos++]=t;scheduler(pos,seq_pos);push(&S,t);}if(pos>=len&&isEmpty(&S)){outSeq(seq,len);count++;}}intmain(){inti;printf("\npleaseinputthenumbescheduled:");scanf("%d",&len);/*用len存储待调度的火车数量*/for(i=0;i<len;i++)d[i]='1'+i;/*创建火车编号，如a、b、c、...等*/printf("theoriginalseqis:");outSeq(d,len);initStack(&S);scheduler(0,0);printf("\ncount=%d",count);return0;}
输入3（即三列火车），得到的结果如下：
2、代码详解
本算法主要是运用了栈+递归+回溯的思想，主要的代码块有三个：
代码块1
if(pos<len){push(&S,d[pos]);scheduler(pos+1,seq_pos);pop(&S);}
代码块2
if(!isEmpty(&S)){t=pop(&S);seq[seq_pos++]=t;scheduler(pos,seq_pos);push(&S,t);}
代码块3
if(pos>=len&&isEmpty(&S)){outSeq(seq,len);count++;}
这里需要注意的是判定元素pos，是处理原始数据中第pos个元素，pos从0开始
代码块1根据你输入的len和第pos个元素来判定是否执行代码块1
例如当你输入了3，
通过代码
scanf("%d",&len);for(i=0;i<len;i++)d[i]='1'+i;
即有三列火车，分别代号为1，2，3
在数组d中的位置分别是0，1，2
当代码第一次执行
voidscheduler(intpos,intseq_pos)
函数的时候，进入了判定
此时参数pos和seq_pos都为0
那么0<len=3，执行代码块1
代码块1把数组第0个元素压入栈中，即1号火车进入车站
接着进行第一次调用函数scheduler
此时参数pos为1，seq_pos为0
因为1<3，继续执行代码块1
代码块1把数组第1个元素压入栈中，即2号火车进入车站
进行第二次调用函数scheduler
此时参数pos为2，seq_pos为0
因为2<3，继续执行代码块1
代码块1把数组第2个元素压入栈中，即3号火车进入车站
进行第三次调用函数scheduler
此时参数pos为3，seq_pos为0
因为3=len=3，所以开始执行代码块2
在代码块2中，把栈顶的元素赋值给t，同时把t放入seq数组的第0个位置中，seq++
即3号列车驶出火车站
进行第四次调用函数sceduler
此时参数pos=3,seq_pos=1
继续执行代码块2，把栈顶的元素赋值给t，同时把t放入seq数组的第1个位置中，seq++
即2号列车驶出火车站
进行第五次调用函数sceduler
此时参数pos=3,seq_pos=2
继续执行代码块2，把栈顶的元素赋值给t，同时把t放入seq数组的第2个位置中，seq++
即1号列车驶出火车站
进行第六次调用函数scheduler
此时参数pos=3,seq_pos=3，现在的情况是三列火车都已经驶出火车站了，也就是栈已经空了，同时满足pos>=len的条件，所以执行代码块3
代码块3把结果进行了输出，
输出结果是3,2,1
第六次调用函数scheduler整个过程结束
此时，代码开始进行回溯
回到了第五次调用函数scheduler中
代码块2中scheduler执行完，执行push，也就是压栈操作，可是现在已经没有火车进站了，因为三列火车都已经走了
代码回到了第四次调用函数scheduler中
代码块2中scheduler执行完，执行push，也就是压栈操作，也没有火车能进车站了
为什么？
还记不记得这个时候是3号列车和2号列车已经出去了，1号列车在车站里，所以没有多余的进站的车了
代码代码回到了第三次调用函数scheduler中
还记不记得这个时候是3号列车、已经出去了，1号列车和2号列车在车站里，所以没有多余的进站的车了
代码代码回到了第二次调用函数scheduler中
代码重新回到了代码块1中
注意，是代码块1
此时，执行了pop，也就是进行了出栈操作
什么意思？
栈顶的3号列车驶出了车站
这里是笔者出现了思维误区的地方，读者不理解递归思想的需要特别注意，当时我在想，3号列车驶出后是不是回到了第一次调用函数？忽略了下面的if语句，错误的认为执行了代码块1后不会执行代码块2，混淆了if-else和if,if语句的关系
代码1执行完，开始执行代码2
注意此时的列车只有两辆，是1号列车和2号列车，参数是pos=2,seq_pos=0
代码块2进行了出栈操作，让在栈顶的2号列车出车站，然后seq_pos++
进行第七次调用函数sceduler
此时代码参数pos=2,seq_pos=1
pos=2<len=3，进入代码块1
代码块1把pos=2的元素压入栈中
什么意思？
把三号列车驶入车站
进行第八次调用函数sceduler
此时代码参数pos=3,seq_pos=1
pos=3=len=3，进入代码块2
代码块2进行了出栈操作，让在栈顶的3号列车出车站
然后seq_pos++
进行第九次调用函数scheduler
此时代码参数pos=3,seq_pos=2
pos=3=len=3，进入代码块2
代码块2进行了出栈操作，让在栈顶的1号列车出车站
然后seq_pos++
进行第十次调用函数scheduler
pos=3=len=3，同时栈里的三辆列车已经全部驶出车站了，所以进行执行代码块3
代码块3把结果进行了输出
输出结果是2,3,1
以此类推…
3、用二叉树表示调用过程
左子树表示压栈（进站），右子树表示出栈（驶出车站），线上数字表示调用函数次数，负数表示出栈，例如-1表示1号列车驶出车站
4、思维导图
以上是“怎么用C语言递归实现火车调度算法”这篇文章的所有内容，感谢各位的阅读！希望分享的内容对大家有帮助，更多相关知识，欢迎关注恰卡编程网行业资讯频道！
