用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(即三列火车),得到的结果如下:

a8945098d98e490c9968e2f691a144b4.png

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号列车驶出车站

image.jpeg

4、思维导图

f03c0468f6114ec6b2fc23bef6e6c13c.jpg

本文代码参考自李云清《数据结构》第三版课本习题火车调度算法答案


本文有参考作者@littlehedgehog的火车调度详解,但作者@littlehedgehog并未对代码块1中pop的作用和代码块2中push进行分析,在此表示感谢


通过本题,可以加深对栈和递归算法的理解,感谢各位读者的浏览,谢谢!

如有错字问题还请谅解!



相关文章
|
2月前
|
算法 调度 UED
探索操作系统的心脏:调度算法的奥秘与影响
【10月更文挑战第9天】 本文深入探讨了操作系统中至关重要的组件——调度算法,它如同人体的心脏,维持着系统资源的有序流动和任务的高效执行。我们将揭开调度算法的神秘面纱,从基本概念到实际应用,全面剖析其在操作系统中的核心地位,以及如何通过优化调度算法来提升系统性能。
|
12天前
|
算法 数据处理 C语言
C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合
本文深入解析了C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合,旨在帮助读者掌握这一高效的数据处理方法。
23 1
|
11天前
|
存储 算法 程序员
C 语言递归算法:以简洁代码驾驭复杂逻辑
C语言递归算法简介:通过简洁的代码实现复杂的逻辑处理,递归函数自我调用解决分层问题,高效而优雅。适用于树形结构遍历、数学计算等领域。
|
12天前
|
存储 缓存 算法
C语言在实现高效算法方面的特点与优势,包括高效性、灵活性、可移植性和底层访问能力
本文探讨了C语言在实现高效算法方面的特点与优势,包括高效性、灵活性、可移植性和底层访问能力。文章还分析了数据结构的选择与优化、算法设计的优化策略、内存管理和代码优化技巧,并通过实际案例展示了C语言在排序和图遍历算法中的高效实现。
33 2
|
12天前
|
机器学习/深度学习 算法 数据挖掘
C语言在机器学习中的应用及其重要性。C语言以其高效性、灵活性和可移植性,适合开发高性能的机器学习算法,尤其在底层算法实现、嵌入式系统和高性能计算中表现突出
本文探讨了C语言在机器学习中的应用及其重要性。C语言以其高效性、灵活性和可移植性,适合开发高性能的机器学习算法,尤其在底层算法实现、嵌入式系统和高性能计算中表现突出。文章还介绍了C语言在知名机器学习库中的作用,以及与Python等语言结合使用的案例,展望了其未来发展的挑战与机遇。
30 1
|
12天前
|
并行计算 算法 测试技术
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面,旨在通过综合策略提升程序性能,满足实际需求。
37 1
|
1月前
|
存储 算法 数据管理
C语言算法复杂度
【10月更文挑战第20天】
C语言算法复杂度
|
1月前
|
算法 调度
基于遗传模拟退火混合优化算法的车间作业最优调度matlab仿真,输出甘特图
车间作业调度问题(JSSP)通过遗传算法(GA)和模拟退火算法(SA)优化多个作业在并行工作中心上的加工顺序和时间,以最小化总完成时间和机器闲置时间。MATLAB2022a版本运行测试,展示了有效性和可行性。核心程序采用作业列表表示法,结合遗传操作和模拟退火过程,提高算法性能。
|
1月前
|
算法 Python
在Python编程中,分治法、贪心算法和动态规划是三种重要的算法。分治法通过将大问题分解为小问题,递归解决后合并结果
在Python编程中,分治法、贪心算法和动态规划是三种重要的算法。分治法通过将大问题分解为小问题,递归解决后合并结果;贪心算法在每一步选择局部最优解,追求全局最优;动态规划通过保存子问题的解,避免重复计算,确保全局最优。这三种算法各具特色,适用于不同类型的问题,合理选择能显著提升编程效率。
41 2
|
1月前
|
人工智能 算法 大数据
Linux内核中的调度算法演变:从O(1)到CFS的优化之旅###
本文深入探讨了Linux操作系统内核中进程调度算法的发展历程,聚焦于O(1)调度器向完全公平调度器(CFS)的转变。不同于传统摘要对研究背景、方法、结果和结论的概述,本文创新性地采用“技术演进时间线”的形式,简明扼要地勾勒出这一转变背后的关键技术里程碑,旨在为读者提供一个清晰的历史脉络,引领其深入了解Linux调度机制的革新之路。 ###