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

山东理工大学计算机学院

课 程 设 计

（数据结构）

计科1002 班 级

宫欣海 姓 名

1011051029 学 号

刘晓红 指导教师

二○一一年一月十日

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

课题名称 车厢调度

Ⅰ、题目的目的和要求：

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

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

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

Ⅱ、设计进度及完成情况

日 期 内 容 1.2-1.3 1.4~1.5 1.6~1.7 1.9 选取参考书，查阅有关文献资料，完成资料搜集和系统分析工作。 创建相关数据结构,录入源程序。 调试程序并记录调试中的问题，初步完成课程设计报告。 上交课程设计报告打印版并进行课程设计答辩，要求每个同学针对自己的设计回答指导教师3-4个问题。 考核结束后将课程设计报告和源程序的电子版交班长统一刻光盘上交。

Ⅲ、主要参考文献及资料

[1] 严蔚敏 数据结构（C语言版）清华大学出版社 1999 [2] 严蔚敏 数据结构题集（C语言版）清华大学出版社 1999 [3] 谭浩强 C语言程序设计 清华大学出版社 [4] 与所用编程环境相配套的C语言或C++相关的资料

Ⅳ、成绩评定：

设计成绩：

指导老师：

（教师填写）刘晓红 （签字）二○一一 年 一 月 十

日

目 录

第一章 概述„„„„„„„„„„„„„„„„„„„„„„„1 第二章 系统分析„„„„„„„„„„„„„„„„„„„„„2 第三章 概要设计„„„„„„„„„„„„„„„„„„„„„ 第四章 详细设计„„„„„„„„„„„„„„„„„„„„„ 第五章 运行与测试„„„„„„„„„„„„„„„„„„„„ 第六章 总结与心得„„„„„„„„„„„„„„„„„„„„ 参考文献„„„„„„„„„„„„„„„„„„„„„„„„

第一章 概述

课程设计是实践性教学中的一个重要环节，它以某一课程为基础，可以涉及和课程相关的各个方面，是一门独立于课程之外的特殊课程。课程设计是让同学们对所学的课程更全面的学习和应用，理解和掌握课程的相关知识。《数据结构》是一门重要的专业基础课，是计算机理论和应用的核心基础课程。

数据结构课程设计，要求学生在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面，加深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。

在这次的课程设计中我选择的题目是车厢调度。首先在教科书3.1.2节中提供的栈的顺序存储结构SqStack之上实现栈的基本操作，即实现栈的类型。程序对栈的任何存取（即更改，读取和状态判别等操作）必须借助于基本操作进行。一般的说，在操作过程的任何状态下都有两种可能的操作：“入”和“出”。每个状态下处理问题的发发是相同的，这说明问题本身具有天然的递归性，可以参考用递归的算法实现。输入序列可以仅由一对整型变量表示，即给出序列头/尾编号。输出序列用栈实现是方便的，只要再定义一个栈打印操作print（s），自低至顶顺序地印出栈元素的值。

本部分主要说明：课程设计的目的意义；对自己题目的问题描述；以上为样例，特别是字体，字号，行间距等均参照样例，以下同。

1

第二章 系统分析

1.问题分析：

可假设对二叉树的n个结点从1到n编号，且令其先序序列为1，2，„„，n，则不同的二叉树所得到的中序序列不同。这样，不同形态的二叉树的数目正好是先序序列均为1，2，„„，n的二叉树所能得到的中序序列的数目，而中序遍历的过程实际上是一个结点进栈和出栈的过程。因此，序列1，2，„„，n按不同顺序进栈和出栈所能得到的排列的数目正好是由先序序列为1，2，„„，n所能得到的中序序列的数目，也就是先序序列为1，2，„„，n的不同形态的二叉树的数目，其数目为 ： 1 （2n）！ Cn== ------ * -------- n+1 n！*n！ 2.设计内容：

现有n节车厢，按不同的顺序进栈和出栈，计算出所有的出栈序列并输出。 例如：有4节车厢则输出：

4 3 2 1 2 3 4 1 1 3 4 2 3 4 2 1 2 3 1 4 1 3 2 4 3 2 1 4 2 1 4 3 1 2 4 3 3 2 1 4 2 1 3 4 1 2 3 4 2 4 3 1 1 4 3 2

本部主要说明题目的基本要求，注意对题目的基本要求进行详细分析，尽量细化到程序中每个函数实现的功能都能在此处说明。

2

第三章 概要设计

1．设定栈的抽象数据类型定义： ADT Stack {

数据对象：D={ai|ai∈CharSet,i=1,2,...,n,,n≥0}

数据关系：R1={操作结果：构造一个空栈S。 DestroyStack(&S)

初始条件：栈S已存在。 操作结果：销毁栈S。 ClearStack(&S)

初始条件：栈S已存在。 操作结果：将栈S清为空栈。 Sta

初始条件：栈S已存在。 操作结果：返回栈S的长度。 StackEmpty(S)

初始条件：栈S已存在。

操作结果：若S为空栈，则返回TURE，否则返回FALSE。 GetTop(S,&e)

初始条件：栈S已存在。

操作结果：若S不空，则e返回栈顶元素。 Push（&S，&e）

初始条件：栈S已存在。

操作结果：在s的栈顶插入新的栈顶元素e。 Pop(&S,&e)

初始条件：栈S已存在。

操作结果：删除S的栈顶元素，并以e返回其值。 StackTraverse（S，visit（）） 初始条件：栈S已存在。

操作结果：从栈底到栈顶依次对S中的每个元素调用函数visit（）。 }ADT Stack

2.本程序包含两个模块 1）主程序模块： Void main() {

初始化; For循环 }

3

2）栈模块——实现栈的抽象数据类型 各模块之间的调用关系如下：

主程序模块

栈模块

本章主要介绍

1、数据结构的设计

主要介绍在实验中采用（或设计）的数据结构以及原因。 2、算法的设计

主要说明本设计从总体上划分几个模块，每个模块需要完成的功能是什么？定义每个模块对应的函数接口，用伪代码（类C或C++）设计每个模块对应的算法。 3、抽象数据类型的 设计

根据所设计的数据结构和接口函数，写出抽象数据类型定义或者简单类定义。

4

第四章 详细设计

1）栈类型；

typedef struct stacklist {

SElemType *base; SElemType *top; int stacksize; }SqStack;

栈的基本操作设置如下：

void Stack_init(SqStack *s)//初始化，设s为空栈

void Stack_Push(SqStack *s,SElemType e)//若分配空间成功，则在s的栈顶插入新的元素e，并返回TRUE //若栈不变，并返回FALSE SElemType Stack_Pop(SqStack *s) Status Stack_Empty(SqStack *s) Status Stack_Full(SqStack *s) void Stack_printreverse(SqStack s)

void search(SqStack *inputPoint,SqStack *tempPoint,SqStack *outputPoint) 2)代码

#include using namespace std; typedef int SElemType; typedef int Status;

int end;/*最后一个车厢的号码*/ long total=0;/*总的组合方案数目*/ typedef struct stacklist

5

{

SElemType *base; SElemType *top; int stacksize; }SqStack;

void Stack_init(SqStack *s) {

s->base=(SElemType *)malloc(end*sizeof(int)); if(!s->base) exit(0); s->top=s->base; s->stacksize=end; }

void Stack_Push(SqStack *s,SElemType e) {

*(s->top)++=e; }

SElemType Stack_Pop(SqStack *s) {

if(s->top==s->base) return 0;

return *(--(s->top)); }

Status Stack_Empty(SqStack *s) {

if(s->top==s->base) return 1; return 0; }

Status Stack_Full(SqStack *s) {

6

if(s->top-s->base==end) return 1; return 0; }

void Stack_printreverse(SqStack s) { int *po; po=s.base;

printf(\"\[%ld]: \for(;po!=s.top;) printf(\"%d \printf(\"\\n\"); }

void search(SqStack *inputPoint,SqStack *tempPoint,SqStack *outputPoint) {

if(!Stack_Empty(inputPoint)) {

Stack_Push(tempPoint,Stack_Pop(inputPoint)); search(inputPoint,tempPoint,outputPoint); Stack_Push(inputPoint,Stack_Pop(tempPoint)); }

if(!Stack_Empty(tempPoint)) {

Stack_Push(outputPoint,Stack_Pop(tempPoint)); search(inputPoint,tempPoint,outputPoint); Stack_Push(tempPoint,Stack_Pop(outputPoint)); }

if(Stack_Full(outputPoint)) {

7

total++;

Stack_printreverse(*outputPoint); } } 主函数： void main() {

SqStack input,temp,output; int i;

printf(\"\\n\\n\\\\车厢调度\\n\"); printf(\"\\n\请输入车厢长度: \"); scanf(\"%d\/*初始化三个栈*/ Stack_init(&input); Stack_init(&temp); Stack_init(&output); /*将车厢号码进栈*/ for(i=end;i>=1;i--) Stack_Push(&input,i); search(&input,&temp,&output); }

1、 设计抽象数据类型对应的类定义。（如用2、 设计每个成员函数； 3、 设计主函数

C实现则没有这项）8

第五章 运行与测试

输入3，结果如下：

输入4，结果如下：

9

第六章 总结与心得

通过对本学期的数据结构课程的学习，我完成了本次的课程设计报告，其中得到了很多的体会，也了解到很多的知识点。我明白了课程设计是大学教育中一个重要的实践教学环节。在课程设计过程中,我根据具体设计题目，运用自己所学的知识，独立地进行设计和实验。除了巩固、加深和融合自己所学的数据结构专业课程知识外，更重要的是培养了我多方面的能力，如独立思考能力、综合设计能力、实践动手能力、开拓创新能力、自学能力、文献检索能力等等。通过这次的课程设计，我也了解到自己所学的一些不足之处，以及一些还不了解的知识点，以后会加强学习，把不懂的弄懂

主要说明设计完成后的总结与思考，完成任务情况，收获，意见和建议等。

参考文献:

[1] 严蔚敏、吴伟民主编 《数据结构》（C语言版） 清华大学出版社 2002 [2] 殷人昆等著 《数据结构》（C++版） 清华大学出版社 2001 [3] 金远平著 《数据结构》（C++描述） 清华大学出版社 2005 [4] 许卓群等著 《数据结构与算法》 高等教育出版社 2004 [5] Frank M.Carrano 等著 《数据结构与Ｃ++高级教程》清华大学出版社 2004 [6] 严蔚敏、吴伟民 《数据结构习题集》（C语言版）清华大学出版社

10