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

1、代碼

題目如下：
2.8編號為1，2，3，4的四列火車通過一個棧式的列車調度站，可能得到的調度結果有哪些？如果有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;/*定義將通過棧的元素個數(shù)*/ 
int count=0;/* 用于統(tǒng)計輸出序列的個數(shù)  */

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

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，是處理原始數(shù)據(jù)中第pos個元素，pos從0開始
代碼塊1根據(jù)你輸入的len和第pos個元素來判定是否執(zhí)行代碼塊1
例如當你輸入了3，
通過代碼

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

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

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

void scheduler(int pos, int seq_pos)

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

接著進行第一次調用函數(shù)scheduler

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

進行第二次調用函數(shù)scheduler

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

進行第三次調用函數(shù)scheduler

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

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

進行第四次調用函數(shù)sceduler

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

進行第五次調用函數(shù)sceduler

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

進行第六次調用函數(shù)scheduler

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

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

此時，代碼開始進行回溯

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

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

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

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

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

注意，是代碼塊1

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

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

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

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

進行第七次調用函數(shù)sceduler

此時代碼參數(shù)pos=2,seq_pos=1
pos=2<len=3，進入代碼塊1
代碼塊1把pos=2的元素壓入棧中
什么意思？
把三號列車駛入車站

進行第八次調用函數(shù)sceduler

此時代碼參數(shù)pos=3,seq_pos=1
pos=3=len=3，進入代碼塊2
代碼塊2進行了出棧操作，讓在棧頂?shù)?號列車出車站
然后seq_pos++

進行第九次調用函數(shù)scheduler

此時代碼參數(shù)pos=3,seq_pos=2
pos=3=len=3，進入代碼塊2
代碼塊2進行了出棧操作，讓在棧頂?shù)?號列車出車站
然后seq_pos++

進行第十次調用函數(shù)scheduler

pos=3=len=3，同時棧里的三輛列車已經全部駛出車站了，所以進行執(zhí)行代碼塊3
代碼塊3把結果進行了輸出
輸出結果是2,3,1

以此類推…

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

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

4、思維導圖

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

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

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

最新評論