数据结构课程设计说明书
车厢调度问题摘要：实现栈的基本操作，即实现类型。程序对栈的任何存取，即更改，读取和 状态判别等操作，必须借助于基本操作。在操作过程中的任何状态下都有两种可 能的操作：“入”“出”。每个状态下处理问题的方法都是相同的，具有递归特性。关键字:栈递归打印0.引言数据结构是计算机科学与技术、软件工程及相关学科的专业基础课，也 是软件设计的技术基础。数据结构课程的教学要求之一是训练学生进行复杂 的程序设计的技能和培养良好程序设计的风格，其重要程度决不亚于理论知识的 传授，因此课程设计环节是一个至关重要的环节，是训练学生从事工程科技的基本能力，是培养创新意识和创新能力的极为重要的环节。基本要求如下：(1) 熟练掌握基本的数据结构；(2) 熟练掌握各种算法；(3) 运用高级语言编写质量高、风格好的应用程序。1. 需求分析(1) 这个实验要求我用栈实现车厢调度.(2) 车厢的个数是由用户输入的.(3) 程序会自动给车厢进行从1到n的编号.用户输入车厢个数后，程序打印出所有可能的车厢出站顺序.2. 数据结构设计在这个程序中存储结构是栈，对于栈的声明和定义如下：typedef struct SqStackint *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栈的基本操作构造一个栈voidIn itStack2(SqStack*S,i ntbase_size)S->base=(i nt*)malloc(base_size * sizeof(i nt);if(!S->base)puts("ERROR!");return ;S->top=S->base;S->stacksize=base_size; /*构造一个空栈*/插入新的栈顶元素void Push2(SqStack *S, int e)*(S->top+)=e;/*插入元素e为新的栈顶元素*/输出栈顶元素void Pop2(SqStack *S)int e;if(S->top=S->base)puts("ERROR");return ;e=*-S->top;prin tf("%d",e);/*若栈不空,则删除s的栈顶元素,用e返回其值*/3.3输入车厢数并给车厢编号prin tf("please in put the nu mber of the train s:");scan f("%d", &trai nsize);if(tra in size<=0|train size>=33)puts("the nu mber is wron g!");return;for(i=0;i <trai nsize;i+)的编号*/trai nsourcei=i+1;/* 给火车贴上从 1 到 train size4程序实现4.1源代码#i nclude <stdio.h> #i nclude <stdlib.h>typedef struct SqStackint *top;int *base;int stacksize;SqStack;struct SqStack stack; /* 定义一个栈变量 */int trainsize; /* 车厢个数 */int trainsource33; /* 车厢数组 */void Show(intlist_in); /* 打印 */list_ nu m);voidSchedule(i ntlist_i n,i ntsource_ nu m,i nt/*对第source_num号车厢进行处理*/void In itStack2(SqStack *S,i nt base_size)S->base=(i nt *)malloc(base_size *sizeof(i nt);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;prin tf("%d",e);voidTrain Schedule。int i;inttrai nl ist66;prin tf("please in put the nu mber of the train s:");scan f("%d", &trai nsize);if(tra in size<=0 | train size>=33)puts("WRONG LENGTH!");return;for(i=0;i < trai nsize;i+)trai nsourcei=i+1;Schedule(trai nlist,1,0);list_ num)void Schedule(i ntlist_i n,i ntsource_ nu m,i nt/*对当前第source_num号车厢的处理用到了递归*/int i;int sum=O;int judge;int trai nl ist50;if(source_ num>trai nsize)return;for(i=0;i<50;i+)trainl isti=-1;for(i=0;i<=list_ nu m-1;i+)trai nl isti=list_i ni;sum=sum+trai nlisti;if(sum !=0)trai nlistlist_ nu m=1;Schedule(trainlist,source_num+1,list_num+1)/* 对下一车厢进行处理 */for(i=0,judge=0;i<tra in size*2;i+)judge=judge+tra in listi;if(source_ num = trai nsize && judge =0)Show(trainlist); /*打印出可能的列车序列*/trai nlistlist_ nu m=-1;Schedule(trai nlist,source_ nu m,list_ nu m+1);for(i=0,judge=0;i<tra in size*2;i+)judge=judge+tra in listi;if(source_ num = trai nsize && judge =0)Show(trainlist); /*打印出可能的列车序列*/elsetrai nlistlist_ nu m=1;Schedule(trai nlist,source_ nu m+1,list_ nu m+1);for(i=0,judge=0;i<tra in size*2;i+)judge=judge+tra in listi;if(source_ num = trai nsize && judge =0)Show(trai nlist);voidShow(intlist_in) /*输出可能的车厢序列*/int i,cur=0;int len gth;SqStack stack;In itStack2(&stack,trai nsize);len gth=trai nsize*2;for(i=0;i<le ngth;i+)if(list_i n i=1)Push2(&stack,trai nsourcecur+);else if(list_i n i=-1)Pop2(& stack);elseputs("error!");puts("");int main()Trai nSchedule();getchar();getchar();4.2运行结果运行结果如下：畐 C:Win - TCpro)ectscKdd2.eMeeS34224331143322al:leV43332222211111input22nunkier- oftlie tra ins : 41114-114342 2 434不足之处在于对车厢个数进行了限制，车厢数越小越稳定.还有就是一次只 能对一组车厢进行调度.5. 设计体会在进行课程设计的过程中，先把问题具体化，再进行编程车厢调度问题是个 很老的问题，它的难点在于车厢进栈出栈的递归算法.经过这次课程设计，我加深 了对栈的操作的熟练程度，对递归有了更深刻的理解，递归算法有点难度6. 结束语课程设计终于完成了 ，总的来说，栈是个很实用的存储结构.递归算法也很重 要.我对数据结构有了进一步的掌握.参考文献1 严蔚敏,吴伟民数据结构，清华大学出版社，2001年1月.2 谭浩强.C程序设计，清华大学出版社，1999年12月.
