源代码：车厢调度：数据结构课程设计

课程设计任务书及成绩评定

  1、设计目的

巩固和加深对数据结构的理解，通过上机实验、调试程序，加深对课本知识的理解，最终使学生能够熟练应用数据结构的知识写程序。

（1）通过本课程的学习，能熟练掌握几种基本数据结构的基本操作。

（2）能针对给定题目，选择相应的数据结构，分析并设计算法，进而给出问题的正确求解过程并编写代码实现。

2、设计题目要求： 

 问题描述：假设停在铁路调度站入口处的车厢序列的编号一次为 1,2,3，……，n。设计一个程序，求出所有可能由此输出的长度为n的车厢序列；

Ⅱ、设计进度及完成情况

[1] 严蔚敏 数据结构（C语言版）清华大学出版社 1999

[2] 严蔚敏 数据结构题集（C语言版）清华大学出版社 1999

[3] 谭浩强  C语言程序设计  清华大学出版社

[4] 与所用编程环境相配套的C语言或C++相关的资料

源代码

#include

#include

#include

#define STACK_INIT_SIZE 100

#define STACKINCREMENT 10

#define ERROR 0

#define OK 1

#define OVERFLOW -2

typedef int Status;

typedef struct{

 int *base; //栈底指针

 栈顶指针

 栈空间大小

}SqStack;

Status InitStack(SqStack &S)

{

 S.base=(int*)malloc(STACK_INIT_SIZE*sizeof(int));

 if(!S.base)exit(OVERFLOW);

 S.top=S.base;

 S.stacksize=STACK_INIT_SIZE;

 return OK;

}创栈

Status Push(SqStack &S,int e)

{

if((S.top-S.base)>=S.stacksize)

 {

  S.base=(int*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(int));

  if(!S.base)exit(OVERFLOW);

  S.top=S.base+S.stacksize;

  S.stacksize+=STACKINCREMENT;

  }

 *S.top++=e;

 return OK;

}  //进栈

Status Pop(SqStack &S,int &e)

{

 if(S.top==S.base)return ERROR;

 e=*--S.top;

 return OK;

}  //出栈

Status StackEmpty(SqStack &S)

{

 if(S.top==S.base)

 return 1;

 else return 0;

}判断空栈

void print(int b[],int n)

{

 int k;

for(k=0;k printf("%d ",b[k]);

 printf("\\n");

}

void f(SqStack S,int a[],int b[],int p,int q,int n)

{

if(p{

 递归进栈

 f(S,a,b,p+1,q,n);

 Pop(S,b[q]);

}

 if(!StackEmpty(S))

 {

 递归出栈

  f(S,a,b,p,q+1,n);

  Push(S,b[q]);

  }

  if(q>=n&&StackEmpty(S))print(b,n); //出栈完输出序列号

 }

int main()

{ int i,n,a[STACK_INIT_SIZE],b[STACK_INIT_SIZE];

  printf("请输入待调车厢数:\\n");

  scanf("%d",&n);

  SqStack S;

  InitStack(S);

for(i=0;i  a[i]=i+1;

  printf("输出序列号为:\\n");

  f(S,a,b,0,0,n);

  return 0;

}