数据结构课程设计(火车进出栈)

1、课程设计（论文）任务书软件学院学 院软件工程专 业2011=_8班一、 课程设计（论文）题目车厢调度问题二、课稈设计（论文）工作自2012 年 12月19 日起至2012年12月 24 日止三、 课程设计（论文）地点：创新大楼机房四、课程设计（论文）内容要求：1. 本课程设计的目的训练学生灵活应用所学数据结构知识，独立完成问题分析，结合数据结构理论知识， 编写程序求解指定问题;初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；提高综合运用所学的理论知识和方法独立分析和解决问题的能力，巩固、深化学生 的理论知识，提升编程水平。2. 课程设计的任务及要求1）基本要求:要求从分析题目的需求入手，按设计抽象数据类型、构思算法、通过设计实现抽象 数据类型、编写上机程序和上机调试等若干步骤完成题目，最终写出完整的报告；在程序设计阶段应尽量利用已有的标准函数，加大代码的重用率;程序设计语言推荐使用C/C+，程序书写规范，源程序需加必要的注释;每位同学需提交可独立运行的程序和规范的课程设计报告。2） 课程设计论文编写要求理论设计部分以课程设计论文的形式提交，格式必须按照课程设计

2、论文标准格式进 行书写和装订；课程设计报告（论文）包括中文目录、设计任务、需求分析、概要设计、详细设计、 编码实现、调试分析、课设总结、谢辞、参考文献、附录等;设计部分应包含系统功能模块图，调试分析应包括运行截图等。3） 课程设计评分标准：学习态度：10分;系统设计：20分；编程调试： 20分;回答问题：20分；论文撰写：30分。4）参考文献：严蔚敏，吴伟民.数据结构（C语言版）M.清华大学出版社.2010.3严蔚敏，吴伟民.数据结构题集（C语言版）M.清华大学出版社.1999.2何钦铭，冯燕等.数据结构课程设计M.浙江大学出版社.2007.85）课程设计进度安排准备阶段（4学时）：选择设计题目、了解设计目的要求、查阅相关资料；程序模块设计分析阶段（4学时）：程序概要设计、详细设计；代码编写调试阶段（8学时）：程序模块代码编写、调试、测试；撰写论文阶段（4学时）：总结课程设计任务和设计内容，撰写课程设计论文。学生签名：2012 年 月 日6）课程设计题目具体要求:假设停在铁路调度站（如教科书中图3.1（b）所示）入口处的车厢系列的编号依次为1,2, 3,n。设计一个程序，求出所有可能由

3、此输出的长度为n的车厢系列。 计一个程序，求出由一个编号依次为1, 2,、，n的车厢序列可能产生的所有 出栈系列。利用双向栈存储结构实现调度站和输出序列这两个栈的空间共享。对于每个输出序列演示出所有操作序列的变化过程。课程设计（论文）评审意见（1）学习态度（10分）：优（）、良（）、中（）、一般（）、差（）；（2）系统设计（20分）：优（）、良（）、中（）、一般（）、差（）；（3）编程调试（20分）：优（）、良（）、中（）、一般（）、差（）；（4）回答问题（20分）：优（）、良（）、中（）、一般（）、差（）；（5）论文撰写（30分）：优（）、良（）、中（）、一般（）、差（）；6）格式规范性及考勤是否降等级：是（ ）、否（ ）评阅人：职称：一讲师2012 年 10 月 1 日车厢调度一问题描述 ：1、用编号依次为1, 2, 3,，n表示停在铁路调度站入口处的车厢序列。2、用一个栈形象地表示为火车的调度站。3、利用栈先进后出的性质，结合递归，实现编号1n的车厢的所有可能的 序列。二设计：为了使车厢能够调度，需要定义一个栈，利用栈先进后出的性质，改变车厢的顺序。 对栈的抽象数据类型进行定义存

4、储情况如下：把左栈的数据输到右栈再输出数据对象：D=ai I aiCharSet, i=1, 2, ,n, n0数据关系；R=vai-1,ai I ai-1,ai$D,i=2, ,nMakeEmpty()： 操作结果：构造一个空栈 S。IsEmpty()：判断栈是否为空栈，若 s 为空栈，则返回 1，否则返回 0Push_2(int item)：在栈 s 的 2 栈顶插入新的栈顶元素 item。Push_1(int item)：在栈 s 的 1 栈顶插入新的栈顶元素 item。Pop()：删除 s 的栈顶元素并返回其值。 以上定义的详细设计如下代码所示 struct StackNode int datamaxSize;int top_1;int top_2;s;int n;void MakeEmpty() 置空栈s.top_1=0;.s.top_2=maxSize-1;int IsEmpty()/判右侧栈空否 if(s.top_2= maxSize-1) return 1;elsereturn 0;void Push_2(int item) /从右侧进栈s.top_2 - -;s.da

5、tas.top_2=item;void Push_1(int item) /从左侧进栈s.top_1+;s.datas.top_1=item;int Pop() /出右侧栈并取栈顶int temp;temp=s.datas.top_2;s.top_2+;return temp;三函数流程图如下：开始a=1top是否出栈.否右栈是否空是否a=n&IsEmpty()是结束是,a+输出右栈提示输入车厢节数n构造双向栈* a进右栈a进左栈否,a+四生成输出序列的函数的伪码算法如下：void OutPut(int pp,int c)if(ppn) 一个数进栈后,有两种处理方式： 要么立刻出栈,要么进行下一个数的进栈； if(!IsEmpty() 一个数出栈后,有两种处理方式： 要么继续出栈,要么继续下一个数的进栈 if(pp=n&IsEmpty() 一种可能输出序列产生，输出 该函数详细代码如下： void OutPut(int pp,int cc)int m,i;if(ppvn) 一个数进栈后，有两种处理方式：要么立刻出栈，要么进行下一 个数的进栈 Push_2(pp+1); OutPut(p

6、p+1，cc);Pop();if(!IsEmpty()一个数出栈后，有两种处理方式：要么继续出栈，要么继续 下一个数的进栈m=Pop();s.datacurp=m; cc+;OutPut(pp，cc);Push_2(m);if(pp=n&IsEmpty() 一种可能输出序列产生，输出for(i=0;icurp;i+) printf(%4d,s.datai);printf(n); 主函数如下：int mainprintf(输入要调度车厢总数:)； scanf_s(%d,&n);MakeEmpty ();Push_2(1); printf (所有输出序列:n);OutPut (1,0);/ 从 1 开始，递归处理所有五运彳丁结果输入 3 结果为：输入4结果为：33 C:Wi n dcwsVEyste m 3 2cnncl.eKeIo%114 31丄1请詁任意犍堆续-六总结 本程序的栈其实也是一个简单的数组，它存储先后进入该栈的数，然后 输出各个不同的序列。由于此程序比较简单明了，不是很复杂，按照概要设 计来进行代码设计的时候基本没有什么问题。在调试过程中，主要是在主要 的递归函数设计过程中

7、遇到了不小的麻烦，二者主要的原因就在于对递归的 调用算法没有钻研所致，在此过程中借助于课本上以及网上查到的关于递归 的资料才算勉强完成这个函数。通过这次课程设计，我对于将课本上的知识运用到实际生活中的整个过 程深有体会了，不像之前对知识单纯的停留在课本及考试的要求上。对于我 们学过的知识，我们要尽量深入而透彻地去理解以及渗透，因为，在我看来， 只有充分的了解渗透才能更好的将课本所学的知识运用到实验和生活中去。 这次课程设计，我受益匪浅。感谢老师的辛勤指导。参考文献1 严蔚敏,吴伟民.2 严蔚敏,吴伟民.3 何钦铭,冯燕等.数据结构（C语言版）M.清华大学出版社.2010.3 数据结构题集（C语言版）M.清华大学出版社.1999.2 数据结构课程设计M.浙江大学出版社.2007.8详细代码： #includestdio.h #define maxSize 10 struct snodeint datamaxSize; int top_1;int top_2;s；/定义一个栈指针 intn;/定义输入序列总个数void Initstack()s.top_1=-1; s.top_2=maxS

8、ize;voidpush_l(intp)/元素 n 进栈s.top_1+; s.datas.top_1=p;voidpush_2(intq)/元素 n 进栈s.top_2-; s.datas.top_2=q;intpop()/出栈int temp; temp=s.datas.top_2; s.top_2+; return temp;intEmpt ys()/判断栈空if(s.top_2=maxSize)return 1;elsereturn 0;/*33每次调用求值阶段包含两重递归，只有全部返回，才表示本pos处理完, 可以对上一个元素求值,process就是找出当前元素进栈后所有可能的操作, 即在当前元素进栈后各种情况下，34. 包括不出栈，立即出栈，出栈后继续出栈情况(出栈递归)下，继续处理下 一个元素(入栈递归)35.35. */voidprocess(intpos,intcurp)/当前处理位置 pos 的元素int m,i;if(posn)/编号进栈递归push_2(pos+l);/当前元素进栈后下一个元素继续进栈 process(pos+1, curp); /处理下一个元素，返回表明下一个元 素进栈的情况处理完了pop(); /下一个元素处理完后，pop掉，准备处理

《数据结构课程设计(火车进出栈)》由会员m****分享，可在线阅读，更多相关《数据结构课程设计(火车进出栈)》请在金锄头文库上搜索。