怎么用C語言遞歸實現火車調度算法

這篇文章主要介紹怎么用C語言遞歸實現火車調度算法，文中介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們一定要看完！

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;/* 用于統計輸出序列的個數  */

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; 
/*對任何一個數，總是先進棧，再出棧。另外，這里不需要循環，類似于"查找數組中元素"用遞歸*/ 
	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++; } 
}

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; /*創建火車編號，如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個元素來判定是否執行代碼塊1
例如當你輸入了3，
通過代碼

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

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

當代碼第一次執行

void scheduler(int pos, int seq_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語言遞歸實現火車調度算法”這篇文章的所有內容，感謝各位的閱讀！希望分享的內容對大家有幫助，更多相關知識，歡迎關注億速云行業資訊頻道！