C语言版数据结构课程设计

数据结构课程设计

资 料 袋

学院（系、部）学年第学期 课程名称 数据结构 指导教师 职称 博士 学生姓名 专业班级 通信工程 学号 题 目 编制车厢调度的程序 成 绩

起止日期 2010年 6 月 28日～ 2010年 7 月 10 日

目 录 清 单

课程设计任务书

2009 —2010 学年第 二 学期

课程名称： 数据结构

设计题目： 编制一个车厢调度的程序

完成期限：自 2010 年 6 月 28日至 2010 年 7 月 10 日共 一 周

指导教师（签字）： 年 月 日

系（教研室）主任（签字）： 年 月 日

数据结构

设计说明书

数据结构课程设计

编制一个车厢调度的程序

起止日期： 2010 年 6 月 28日 至 2010年 7 月 10 日

学生 姓名 班学成

级 号 绩

通信092班

指导教师(签字)

计算机与通信学院（部）

年 月 日

湖南工业大学课程设计情况分析表

指导教师（签字）： 年 月 日

系（教研室）主任（签字）： 年 月 日

备注：本表在课程设计完成后由指导教师填写，与课程设计资料一起存档。

目录

1. 题目 VI

2. 概要设计 VII

3. 功能函数设计 XI

4. 调试分析 XIX

5. 用户手册 XXI

6. 测试结果 XIV

7. 附录 完整的程序清单 XV 一、题目:

编制一个车厢调度的程序.

扩展:

增加清屏函数；; 增选择的功能;

可显示所有的运行结果.

需求分析

( 1 )在教材书3.1.2节中提供的栈的顺序存储结构SqStack之上实现栈的基本操作，即实现栈类型。

( 2 )程序对任何栈的任何存取（即更改、读取和状态判别等操作）必须借助于基本操作执行。

( 3 ) 用户可以自己输入调度的大小 , 然后由程序自动生成结果.

二、概要设计

1. 设定栈的抽象数据类型定义 : ADT Stack {

数据对象 : D={ai|ai∈ADT MazeType , i = 0,1,2 n , n≥0}

数据关系 : R1={ <ai-1,ai> | ai-1,ai ∈D,i=2, n } 基本操作 :

InitStack(SqStack &s)

操作结果 : 构造一个空栈

GetTop(SqStack s,SElemType &e) 初始条件 : 栈 s 以存在

操作结果 : 获取栈顶元素

Push(SqStack &s,SElemType &e)

初始条件 : 栈 s 以存在

操作结果 : 在栈顶插入新元素

Pop(SqStack &s,SElemType &e)

初始条件 : 栈 s 以存在

操作结果 : 删除栈顶元素,并删除e值

StackEmpty(SqStack s)

初始条件 : 栈 s 以存在

操作结果 : 判断栈是否为空

ClearStack(SqStack &s) 初始条件 : 栈 s 以存在

操作结果 : 将栈置为空栈

} ADT SqStack;

2. 设定车厢调度的抽象数据类型 ADT MazeType{

数据对象 : D={ai,j|ai,j∈{‘ ’,‘#’、‘@’、‘*’}，0<=i<=m+1, 0<=j<=n+1,m,n<=10} 数据关系 : R={M,N}

M={<a i-1,j,ai,j>|ai-1,j,ai,j∈D,i=1, ,m+1,j=0, ,n+1} N={<a i-1,j,ai,j>|ai-1,j,ai,j∈D,i=1, ,m+1,j=0, ,n+1}

基本操作 :

void process(int pos,int path[],int curp)//当前处理位置pos的元素 {

定一两个变量

if(pos<n)//编号进栈递归 {

push(pos+1);//当前元素进栈后下一个元素继续进栈 process(pos+1,path,curp); //处理下一个元素，返回表明下一个元素进栈的情况处理完了

pop(); //下一个元素处理完后，pop 掉，准备处理直接出栈 }

if(!Emptys())//递归处理出栈 {

m=pop();

path[curp]=m; //数组存放出栈元素 curp++;

process(pos,path,curp);//出栈后处理下一个素继续进栈 push(m); }

if(pos==n&&Emptys())//输出一种可能的方案 {

for(i=0;i<curp;i++) printf("%2d",path[i]);

printf("\n"); } }

3.本程序包含6个模块

1) 主程序模块:

int main() {

主菜单函数, 实现时间循环. return 0; }//主函数

2) 栈模块----实现栈抽象数据类型

3) 递归模块----实现调度迷宫抽象数据类型

4) 选择生成模块----用户自定义菜单的生成

5) 调度模块----实现车站的模拟

各模块之间的调用如下:

主程序模块

选择模块

4.求解调度通路的伪码算法:

设定当前位置的初值为入口位置; Do {

若当前位置可通,按任意键进行，同时选择你需要的功能 if(m==1) {

输入你的你的车厢长度

}

if(m==2)

{

调用递归函数，输出所有可能的序列

} if(m==3) {

欢迎你使用，系统

}

}while ( 栈不空 ); { 栈空说明没有路径存在 }

三、功能函数设计

本系统主要是考虑对栈的使用，循环队列和双向链表的运用。

--------------------------头文件设计(部分)--------------------- 本部分是讲述栈的相关操作：

#include"stdlib.h" #include"stdafx.h" #include <windows.h> #include"stdio.h"

#include <conio.h>

#define MaxLen 100 struct Stack_node {

int data[MaxLen]; int top;

}s; //定义一个栈指针

int n;//定义输入序列总个数 //----------------栈的基本操作---------------- void Initstack() {

s.top=-1; }

void push(int q)//元素n进栈 {

s.top++;

s.data[s.top]=q; }

int pop()//出栈 {

int temp;

temp=s.data[s.top]; s.top--; return temp; }

int Emptys()//判断栈空 {

if(s.top==-1) return 1; else

return 0; }

------------------------实现文件(部分)---------------------------

本部分是主控函数，函数的调用以及菜单的选择：

main.cpp 主函数

void main() {

int path[MaxLen]; int m; char ch;

printf(" \n\n\n ---------------------------- \n"); …… 此处隐藏：3917字，全部文档内容请下载后查看。喜欢就下载吧 ……