筆者在李云清版的《數據結構》中第二章遇到了這道經典的火車調度題，經過對一些前輩的代碼進行學習，以下將這段火車代碼進行分析詳解，不對之處，還請各位大佬指示，不勝感激！

1、代碼

題目如下：
2.8編號為1，2，3，4的四列火車通過一個棧式的列車調度站，可能得到的調度結果有哪些？如果有n列火車通過調度站，請設計一個算法，輸出所有可能的調度結果。

算法運用的思想是運用棧+遞歸，算法的難點也在于此。先上代碼：

#include <stdio.h>
#define MAX 100
typedef struct s{
	char a[MAX];
	int top;
}Stack;/*定義棧的數據*/
/*定義一些全局變量*/
Stack S;/*定義全局性的棧*/

char d[MAX],seq[MAX];
/*d[MAX]用于存儲原始入棧序列，seq[MAX]用于存儲輸出序列*/
int len;/*定義將通過棧的元素個數*/ 
int count=0;/* 用于統(tǒng)計輸出序列的個數  */

void initStack(Stack *S) /*初始化空棧*/
{
	S->top=-1;
}

void push(Stack *S,char x) /*進棧*/
{
	if(S->top>=MAX) return;
	S->top++;
	S->a[S->top]=x;
}

char pop(Stack *S) /*出棧*/
{
	if (S->top==-1) 
	{ printf("ERROR, POP Empty Stack");  
	return -1; 
    }  
	S->top--;    
	return S->a[S->top+1];  
} 

int isEmpty(Stack *S)/*判斷棧是否為空*/  
{     
	if (S->top==-1) return 1; 
	return 0; 
} 

void outSeq(char *seq, int len)/*輸出頂點序列*/  
{    
	int i; 
	for(i=0; i<len; i++)  
	printf("%2c",seq[i]); 
	printf("\n"); 
} 

void scheduler(int pos, int seq_pos)
{    /* pos: 處理到原始數據中的第pos個元素， 
 seq_pos：若出棧，應放在當前輸出數組的第seq_pos個位置 
*/ 
	int i=0;char t; 
/*對任何一個數，總是先進棧，再出棧。另外，這里不需要循環(huán)，類似于"查找數組中元素"用遞歸*/ 
	if(pos<len){
		/*一個數進棧后,有兩種處理方式：要么立刻出棧,要么進行下一個數的進棧*/ 
	push(&S,d[pos]); 
	scheduler(pos+1,seq_pos); 
	pop(&S); 
	} 
	if (!isEmpty(&S)){/*一個數出棧后,有兩種處理方式：要么繼續(xù)出棧,要么繼續(xù)下一個數的進
	棧*/ 
	t=pop(&S); 
	seq[seq_pos++]=t; 
	scheduler(pos,seq_pos); 
	push(&S,t); 
	} 
	if (pos>=len && isEmpty(&S))  
	{ outSeq(seq,len); count++; } 
}

int main(){ 
   int i; 
   printf("\nplease input the num be scheduled: "); 
   scanf("%d", &len); /*用len存儲待調度的火車數量*/ 
   for(i=0; i<len; i++) 
     d[i]='1'+i; /*創(chuàng)建火車編號，如a、b、c、...等*/ 
   printf("the original seq is:"); 
   outSeq(d,len); 
   initStack(&S); 
   scheduler(0,0); 
   printf("\n count=%d", count); 
   return 0; 
} 

輸入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個元素來判定是否執(zhí)行代碼塊1
例如當你輸入了3，
通過代碼

scanf("%d", &len);
   for(i=0; i<len; i++) 
     d[i]='1'+i; 

即有三列火車，分別代號為1，2，3
在數組d中的位置分別是0，1，2

當代碼第一次執(zhí)行

void scheduler(int pos, int seq_pos)

函數的時候，進入了判定
此時參數pos和seq_pos都為0
那么0<len=3，執(zhí)行代碼塊1
代碼塊1把數組第0個元素壓入棧中，即1號火車進入車站

接著進行第一次調用函數scheduler

此時參數pos為1，seq_pos為0
因為1<3，繼續(xù)執(zhí)行代碼塊1
代碼塊1把數組第1個元素壓入棧中，即2號火車進入車站

進行第二次調用函數scheduler

此時參數pos為2，seq_pos為0
因為2<3，繼續(xù)執(zhí)行代碼塊1
代碼塊1把數組第2個元素壓入棧中，即3號火車進入車站

進行第三次調用函數scheduler

此時參數pos為3，seq_pos為0
因為3=len=3，所以開始執(zhí)行代碼塊2

在代碼塊2中，把棧頂的元素賦值給t，同時把t放入seq數組的第0個位置中，seq++
即3號列車駛出火車站

進行第四次調用函數sceduler

此時參數pos=3,seq_pos=1
繼續(xù)執(zhí)行代碼塊2，把棧頂的元素賦值給t，同時把t放入seq數組的第1個位置中，seq++
即2號列車駛出火車站

進行第五次調用函數sceduler

此時參數pos=3,seq_pos=2
繼續(xù)執(zhí)行代碼塊2，把棧頂的元素賦值給t，同時把t放入seq數組的第2個位置中，seq++
即1號列車駛出火車站

進行第六次調用函數scheduler

此時參數pos=3,seq_pos=3，現在的情況是三列火車都已經駛出火車站了，也就是棧已經空了，同時滿足pos>=len的條件，所以執(zhí)行代碼塊3

代碼塊3把結果進行了輸出，
輸出結果是3,2,1
第六次調用函數scheduler整個過程結束

此時，代碼開始進行回溯

回到了第五次調用函數scheduler中
代碼塊2中scheduler執(zhí)行完，執(zhí)行push，也就是壓棧操作，可是現在已經沒有火車進站了，因為三列火車都已經走了

代碼回到了第四次調用函數scheduler中
代碼塊2中scheduler執(zhí)行完，執(zhí)行push，也就是壓棧操作，也沒有火車能進車站了
為什么？
還記不記得這個時候是3號列車和2號列車已經出去了，1號列車在車站里，所以沒有多余的進站的車了

代碼代碼回到了第三次調用函數scheduler中
還記不記得這個時候是3號列車、已經出去了，1號列車和2號列車在車站里，所以沒有多余的進站的車了

代碼代碼回到了第二次調用函數scheduler中

代碼重新回到了代碼塊1中

注意，是代碼塊1

此時，執(zhí)行了pop，也就是進行了出棧操作
什么意思？
棧頂的3號列車駛出了車站

這里是筆者出現了思維誤區(qū)的地方，讀者不理解遞歸思想的需要特別注意，當時我在想，3號列車駛出后是不是回到了第一次調用函數？忽略了下面的if語句，錯誤的認為執(zhí)行了代碼塊1后不會執(zhí)行代碼塊2，混淆了if-else和if,if語句的關系

代碼1執(zhí)行完，開始執(zhí)行代碼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，同時棧里的三輛列車已經全部駛出車站了，所以進行執(zhí)行代碼塊3
代碼塊3把結果進行了輸出
輸出結果是2,3,1

以此類推…

3、用二叉樹表示調用過程

左子樹表示壓棧（進站），右子樹表示出棧（駛出車站），線上數字表示調用函數次數，負數表示出棧，例如-1表示1號列車駛出車站

4、思維導圖

本文代碼參考自李云清《數據結構》第三版課本習題火車調度算法答案

本文有參考作者@littlehedgehog的火車調度詳解，但作者@littlehedgehog并未對代碼塊1中pop的作用和代碼塊2中push進行分析，在此表示感謝

到此這篇關于用C語言遞歸實現火車調度算法詳解的文章就介紹到這了,更多相關用C語言遞歸實現火車調度算法詳解內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

最新評論