数据结构专业课程设计项目说明指导书.doc

车厢调度问题
摘要: 实现栈基础操作,即实现类型。程序对栈任何存取，即更改，读取和状态判别等操作，必需借助于基础操作。在操作过程中任何状态下全部有两种可
能操作：“入”“出”。 每个状态下处理问题方法全部是相同，含有递归特征 。
关键字:栈 递归 打印
0.引言
《数据结构》是计算机科学和技术、软件工程及相关学科专业基础课，也是软件设计技术基础。《数据结构》课程教学要求之一是训练学生进行复杂程序设计技能和培养良好程序设计风格，其关键程度决不亚于理论知识传授，所以课程设计步骤是一个至关关键步骤，是训练学生从事工程科技基础能力，是培养创新意识和创新能力极为关键步骤。基础要求以下：
(1) 熟练掌握基础数据结构；
(2) 熟练掌握多种算法；
(3) 利用高级语言编写质量高、风格好应用程序。
1.需求分析
(1)这个试验要求我用栈实现车厢调度.
(2)车厢个数是由用户输入.
(3)程序会自动给车厢进行从1到 n编号.
(4)用户输入车厢个数后,程序打印出全部可能车厢出站次序.
2.数据结构设计
在这个程序中存放结构是栈,对于栈申明和定义以下:
typedef struct SqStack
{
int *top; /*栈顶指针*/
int *base; /*在栈结构之前和销毁以后.base值为NULL*/
int stacksize; /*目前分配存放空间*/
}SqStack; /*次序栈结构体申明和定义*/
3.算法设计
3.1 对算法简单描述
这个试验中, 要求用到栈. 实现栈基础操作,即实现类型。程序对栈任何存取（即更改，读取和 状态判别等操作）必需借助于基础操作。在操作过程中任何状态下全部有两种可能操作：“入”“出”。 每个状态下处理问题方法全部是相同，含有递归特征 。栈实现是方便
不管怎样调度，我们操作全部是入栈和出栈，设定入栈为1，出栈为-1，对n列车 厢有2n次这么操作，比如n=4，则有操作1111-1-1-1-1、1-11-11-11-1等.所以还要结构一个操作命令队列trainlist[]。
在算法中还要用到递归算法,其本质为:
一个数进栈以后 有两种处理方法： 要么立即出栈，或下一个数进栈。
一个数出栈以后 也有两种处理方法：要么继续出栈（栈不为空），或下一个数入栈。
3.2栈基础操作
3.2.1结构一个栈
void InitStack2(SqStack *S,int base_size)
{
S->base=(int *)malloc(base_size * sizeof(int));
if(!S->base)
{
puts("ERROR!");
return ;
}
S->top=S->base;
S->stacksize=base_size;
} /*结构一个空栈*/
3.2.2 插入新栈顶元素
void Push2(SqStack *S, int e)
{
*(S->top++)=e;
} /*插入元素e为新栈顶元素*/
3.2.3 输出栈顶元素
void Pop2(SqStack *S)
{
int e;
if(S->top==S->base)
{
puts("ERROR");
return ;
}
e=*--S->top;
printf("%d ",e);
} /*若栈不空,则删除s栈顶元素,用e返回其值*/
3.3 输入车厢数并给车厢编号
printf("please input the number of the trains:");
scanf("%d",&trainsize);
if(trainsize<=0 || trainsize>=33)
{
puts("the number is wrong!");
return;
}
for(i=0;i < trainsize;i++)
trainsource[i]=i+1; /*给火车贴上从1到trainsize编号*/
4 程序实现
4.1 源代码
#include <stdio.h>
#include <stdlib.h>
typedef struct SqStack
{
int *top;
int *base;
int stacksize;
}SqStack;
struct SqStack stack; /*定义一个栈变量*/
int trainsize; /*车厢个数*/
int trainsource[33]; /*车厢数组*/
void Show(int list_in[]);/*打印*/
void Schedule(int list_in[],int source_num,int list_num); /*对第source_num 号车厢进行处理*/
void InitStack2(SqStack *S,int base_size)
{
S->base=(int *)malloc(base_size * sizeof(int));
if(!S->base)
{
puts("ERROR!");
return ;
}
S->top=S->base;
S->stacksize=base_size;
}
void Push2(SqStack *S, int e)
{
*(S->top++)=e;
}
void Pop2(SqStack *S)
{
int e;
if(S->top==S->base)
{
puts("");
return ;
}
e=*--S->top;
printf("%d ",e);
}
void TrainSchedule()
{
int i;
int trainlist[66];
printf("please input the number of the trains:");
scanf("%d",&trainsize);
if(trainsize<=0 || trainsize>=33)
{
puts("WRONG LENGTH!");
return;
}
for(i=0;i < trainsize;i++)
trainsource[i]=i+1;
Schedule(trainlist,1,0);
}
void Schedule(int list_in[],int source_num,int list_num) /*对目前第source_num号车厢处理用到了递归*/
{
int i;
int sum=0;
int judge;
int trainlist[50];
if(source_num > trainsize)
return;

for(i=0;i<50;i++)
trainlist[i]=-1;
for(i=0;i<=list_num-1; i++)
{
trainlist[i]=list_in[i];
sum=sum+trainlist[i];
}
if(sum != 0)
{
trainlist[list_num]=1;
Schedule(trainlist,source_num+1,list_num+1);/*对下一车厢进行处理*/
for(i=0,judge=0;i<trainsize*2;i++)
judge=judge+trainlist[i];
if(source_num == trainsize && judge == 0)
Show(trainlist); /*打印出可能列车序列*/
trainlist[list_num]=-1;
Schedule(trainlist,source_num,list_num+1);
for(i=0,judge=0;i<trainsize*2;i++)
judge=judge+trainlist[i];
if(source_num == trainsize && judge == 0)
Show(trainlist); /*打印出可能列车序列*/
}
else
{
trainlist[list_num]=1;
Schedule(trainlist,source_num+1,list_num+1);
for(i=0,judge=0;i<trainsize*2;i++)
judge=judge+trainlist[i];
if(source_num == trainsize && judge == 0)
Show(trainlist);
}
}
void Show(int list_in[]) /*输出可能车厢序列*/
{
int i,cur=0;
int length;
SqStack stack;
InitStack2(&stack,trainsize);
length=trainsize*2;
for(i=0;i<length;i++)
{
if(list_in[i]==1)
Push2(&stack,trainsource[cur++]);
else if(list_in[i]==-1)
Pop2(&stack);
else
puts("error!");
}
puts("");
}
int main()
{
TrainSchedule();
getchar();
getchar();
}
4.2 运行结果

运行结果以下:

不足之处于于对车厢个数进行了限制,车厢数越小越稳定.还有就是一次只能对一组车厢进行调度.
5.设计体会
在进行课程设计过程中,先把问题具体化,再进行编程.车厢调度问题是个很老问题,它难点在于车厢进栈出栈递归算法.经过这次课程设计,我加深了对栈操作熟练程度,对递归有了更深刻了解,递归算法有点难度.
6.结束语
课程设计最终完成了,总来说,栈是个很实用存放结构.递归算法也很关键.我对数据结构有了深入掌握.

参考文件
[1] 严蔚敏,吴伟民.《数据结构》,清华大学出版社,1月.
[2] 谭浩强.《C程序设计》,清华大学出版社,1999年12月.