数据结构课程设计-车厢调度

课程设计(论文)任务书软件学院软件工程专业2011-1班一、课程设计(论文)题目数据结构课程设计二、课程设计(论文)工作自2012年12月17日起至2012年12月18日止。三、课程设计(论文)地点:软件工程实训中心四、课程设计(论文)内容要求：1．本课程设计的目的（1）使学生熟练掌握抽象数据类型的组织和定义；（2）使学生熟练掌握数据类型的定义和实现；（3）培养学生组织和分析数据的能力；（4）培养学生分析和应用基于不同数据结构的算法的能力；（5）提高学生的科技论文写作能力。2．基本要求：每位同学在以下题目中任选一题（在方框中打勾），独立完成课程设计：□击鼓传花：编号为1，2，……，n的n个人按顺时针方向围坐一圈。一开始第一个人持有一个“花”，然后按顺时针方向自1开始顺序传递“花”，经过m个人（m是随机数）后停止。访问停止时，持有“花”的人必须输出一条信息：“名字：Igottheflower”。随后从此人开始继续按顺时针方向传递“花”……直到游戏结束。□全国交通咨询模拟：参见《数据结构题集》P153。□车厢调度：参见《数据结构题集》P98。3．课程设计论文编写要求（1）要按照书稿的规格打印誊写课设报告；（2）报告分为封面、任务书（本文档）、正文、课程设计体会和参考文献四部分；学生签名：年月日课程设计(论文)评审意见（1）题目分析（20分）：优（）、良（）、中（）、一般（）、差（）；（2）流程分析（30分）：优（）、良（）、中（）、一般（）、差（）；（3）数据定义（30分）：优（）、良（）、中（）、一般（）、差（）；（4）代码编写（10分）：优（）、良（）、中（）、一般（）、差（）；（5）创新能力（10分）：优（）、良（）、中（）、一般（）、差（）；（6）格式规范性、设计态度及考勤是否降等级：是（）、否（）评阅人：职称：讲师年月日3正文一、数据结构定义1.抽象数据类型本设计中用到的数据结构ADT定义如下：ADTStack{数据对象：D={iiaa|∈CharSet,i=1,2,...,n,,n≥0}数据关系：R1={iiiiaaaa,|,11∈D,i=2,...,n}基本操作：InitStack(&S)操作结果：构造一个空栈S。DestroyStack(&S)初始条件：栈S已存在。操作结果：销毁栈S。ClearStack(&S)初始条件：栈S已存在。操作结果：将栈S清为空栈。StackLength(S)初始条件：栈S已存在。操作结果：返回栈S的长度。StackEmpty(S)初始条件：栈S已存在。操作结果：若S为空栈，则返回TURE，否则返回FALSE。GetTop(S,&e)初始条件：栈S已存在。操作结果：若S不空，则e返回栈顶元素。Push（&S，&e）初始条件：栈S已存在。操作结果：在s的栈顶插入新的栈顶元素e。4Pop(&S,&e)初始条件：栈S已存在。操作结果：删除S的栈顶元素，并以e返回其值。StackTraverse（S，visit（））初始条件：栈S已存在。操作结果：从栈底到栈顶依次对S中的每个元素调用函数visit（）。}ADTStack2.存储结构定义数据存储结构的C语言定义如下：typedefintSElemType;typedefintStatus;intfinish;//最后一个车厢号码typedefstructSNode{SElemType*base;SElemType*top;intstacksize;}SqStack;3.基本操作数据结构的基本操作实现如下：voidInitStack(SqStack*s)//初始化，设s为空栈voidPush(SqStack*s,SElemTypee)//若分配空间成功，则在s的栈顶插入新的元素e，并返回TRUE，若栈不变，并返回FALSESElemTypePop(SqStack*s)5StatusStackEmpty(SqStack*s)StatusFull(SqStack*s)voidPrintreverse(SqStacks)voidSearch(SqStack*InputPoint,SqStack*TempPoint,SqStack*OutputPoint)二、解题过程1.问题分解该问题主要应实现以下功能：1.栈的初始化2.函数的递归调用3.进栈出栈3.栈的打印2.模块结构系统主要由两个模块组成，分别是：1.主程序模块2.栈模块模块之间的结构如下：主程序3.解题思路各模块的实现步骤为：1.栈的存储定义，输出操作信息，并输入数据主程序栈62.初始化三个栈Input,Temp,Output3.for循环控制输出语句，车厢号依次进栈4.输出所有情况三、实现#includestdio.h#includemalloc.htypedefintSElemType;typedefintStatus;intfinish;//最后一个车厢号码typedefstructSNode{SElemType*base;SElemType*top;intstacksize;}SqStack;voidInitStack(SqStack*s){s-base=(SElemType*)malloc(finish*sizeof(int));if(!s-base)exit(0);s-top=s-base;s-stacksize=finish;}voidPush(SqStack*s,SElemTypee)//插入{7*(s-top)++=e;}SElemTypePop(SqStack*s)//删除{if(s-top==s-base)return0;return*(--(s-top));}StatusStackEmpty(SqStack*s)//判断{if(s-top==s-base)return1;return0;}StatusFull(SqStack*s){if(s-top-s-base==finish)return1;return0;}voidPrintreverse(SqStacks){int*p;p=s.base;for(;p!=s.top;)8printf(%d,*p++);printf(\n);}voidSearch(SqStack*InputPoint,SqStack*TempPoint,SqStack*OutputPoint){if(!StackEmpty(InputPoint)){Push(TempPoint,Pop(InputPoint));Search(InputPoint,TempPoint,OutputPoint);Push(InputPoint,Pop(TempPoint));}if(!StackEmpty(TempPoint)){Push(OutputPoint,Pop(TempPoint));Search(InputPoint,TempPoint,OutputPoint);Push(TempPoint,Pop(OutputPoint));}if(Full(OutputPoint)){Printreverse(*OutputPoint);}}intmain(){SqStackInput,Temp,Output;inti;9printf(请输入车厢长度:);scanf(%d,&finish);InitStack(&Input);//初始化InitStack(&Temp);InitStack(&Output);for(i=finish;i=1;i--)//进栈Push(&Input,i);Search(&Input,&Temp,&Output);//输出所有可能存在的情况}四、实验结果1.实验数据车厢的长度：3，52.实验结果1011五、实验小结1.数据结构使用小结栈作为一种数据结构，是一种只能在一端进行插入和删除操作的特殊线性表。它按照后进先出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。栈具有记忆作用，对栈的插入与删除操作中，不需要改变栈底指针。栈是允许在同一端进行插入和删除操作的特殊线性表。允许进行插入和删除操作的一端称为栈顶(top)，另一端为栈底(bottom)；栈底固定，而栈顶浮动；栈中元素个数为零时称为空栈。插入一般称为进栈（PUSH），删除则称为退栈（POP）。栈也称为后进先出表。栈可以用来在函数调用的时候存储断点，做递归时要用到栈！2.需完善之处此程序不能让人清除的观察到操作的状态与变化过程，这点需要改进12课程设计体会通过此次课程设计，使我了解自己还有许多方面有些不足，自己需要改进，另外在实验中遇到了许多问题，但是最终都能够通过一些工具解决，自己也感觉很兴奋，数据结构是一门比较难的课程。需要多花时间上机练习。这次的课程设计培养了我实际分析问题、编程和动手能力，使我掌握了程序设计的基本技能，提高了我实践编程的能力。总的来说，这次课程设计让我获益匪浅，对数据结构也有了进一步的理解和认识。13参考文献1.严蔚敏数据结构（C语言版）清华大学出版社2.严蔚敏数据结构题集（C语言版）清华大学出版社3.谭浩强C语言程序设计清华大学出版社