筆者在李云清版的《數(shù)據(jù)結(jié)構(gòu)》中第二章遇到了這道經(jīng)典的火車調(diào)度題，經(jīng)過對一些前輩的代碼進(jìn)行學(xué)習(xí)，以下將這段火車代碼進(jìn)行分析詳解，不對之處，還請各位大佬指示，不勝感激！

1、代碼

題目如下：
2.8編號為1，2，3，4的四列火車通過一個(gè)棧式的列車調(diào)度站，可能得到的調(diào)度結(jié)果有哪些？如果有n列火車通過調(diào)度站，請?jiān)O(shè)計(jì)一個(gè)算法，輸出所有可能的調(diào)度結(jié)果。

算法運(yùn)用的思想是運(yùn)用棧+遞歸，算法的難點(diǎn)也在于此。先上代碼：

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

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

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

void push(Stack *S,char x) /*進(jìn)棧*/
{
	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)/*輸出頂點(diǎn)序列*/  
{    
	int i; 
	for(i=0; i<len; i++)  
	printf("%2c",seq[i]); 
	printf("\n"); 
} 

void scheduler(int pos, int seq_pos)
{    /* pos: 處理到原始數(shù)據(jù)中的第pos個(gè)元素， 
 seq_pos：若出棧，應(yīng)放在當(dāng)前輸出數(shù)組的第seq_pos個(gè)位置 
*/ 
	int i=0;char t; 
/*對任何一個(gè)數(shù)，總是先進(jìn)棧，再出棧。另外，這里不需要循環(huán)，類似于"查找數(shù)組中元素"用遞歸*/ 
	if(pos<len){
		/*一個(gè)數(shù)進(jìn)棧后,有兩種處理方式：要么立刻出棧,要么進(jìn)行下一個(gè)數(shù)的進(jìn)棧*/ 
	push(&S,d[pos]); 
	scheduler(pos+1,seq_pos); 
	pop(&S); 
	} 
	if (!isEmpty(&S)){/*一個(gè)數(shù)出棧后,有兩種處理方式：要么繼續(xù)出棧,要么繼續(xù)下一個(gè)數(shù)的進(jìn)
	棧*/ 
	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存儲待調(diào)度的火車數(shù)量*/ 
   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（即三列火車），得到的結(jié)果如下：

2、代碼詳解

本算法主要是運(yùn)用了棧+遞歸+回溯的思想，主要的代碼塊有三個(gè)：
代碼塊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，是處理原始數(shù)據(jù)中第pos個(gè)元素，pos從0開始
代碼塊1根據(jù)你輸入的len和第pos個(gè)元素來判定是否執(zhí)行代碼塊1
例如當(dāng)你輸入了3，
通過代碼

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

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

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

void scheduler(int pos, int seq_pos)

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

接著進(jìn)行第一次調(diào)用函數(shù)scheduler

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

進(jìn)行第二次調(diào)用函數(shù)scheduler

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

進(jìn)行第三次調(diào)用函數(shù)scheduler

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

在代碼塊2中，把棧頂?shù)脑刭x值給t，同時(shí)把t放入seq數(shù)組的第0個(gè)位置中，seq++
即3號列車駛出火車站

進(jìn)行第四次調(diào)用函數(shù)sceduler

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

進(jìn)行第五次調(diào)用函數(shù)sceduler

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

進(jìn)行第六次調(diào)用函數(shù)scheduler

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

代碼塊3把結(jié)果進(jìn)行了輸出，
輸出結(jié)果是3,2,1
第六次調(diào)用函數(shù)scheduler整個(gè)過程結(jié)束

此時(shí)，代碼開始進(jìn)行回溯

回到了第五次調(diào)用函數(shù)scheduler中
代碼塊2中scheduler執(zhí)行完，執(zhí)行push，也就是壓棧操作，可是現(xiàn)在已經(jīng)沒有火車進(jìn)站了，因?yàn)槿谢疖嚩家呀?jīng)走了

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

代碼代碼回到了第三次調(diào)用函數(shù)scheduler中
還記不記得這個(gè)時(shí)候是3號列車、已經(jīng)出去了，1號列車和2號列車在車站里，所以沒有多余的進(jìn)站的車了

代碼代碼回到了第二次調(diào)用函數(shù)scheduler中

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

注意，是代碼塊1

此時(shí)，執(zhí)行了pop，也就是進(jìn)行了出棧操作
什么意思？
棧頂?shù)?號列車駛出了車站

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

代碼1執(zhí)行完，開始執(zhí)行代碼2
注意此時(shí)的列車只有兩輛，是1號列車和2號列車，參數(shù)是pos=2,seq_pos=0

代碼塊2進(jìn)行了出棧操作，讓在棧頂?shù)?號列車出車站，然后seq_pos++

進(jìn)行第七次調(diào)用函數(shù)sceduler

此時(shí)代碼參數(shù)pos=2,seq_pos=1
pos=2<len=3，進(jìn)入代碼塊1
代碼塊1把pos=2的元素壓入棧中
什么意思？
把三號列車駛?cè)胲囌?/strong>