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

XVIII

数据结构课程设计

资 料 袋

计算机与通信 学院（系、部）2009 ~ 2010 学年第 二 学期

课程名称 数据结构 指导教师 职称 博士

学生姓名 专业班级 通信工程 学号

题 目 编制车厢调度的程序

成 绩

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

目 录 清 单

序号
材 料 名 称
资料数量
备 注
1
课程设计任务书
1

2
课程设计说明书
1

3
课程设计图纸
1

张
4

5

6

课程设计任务书

2009 —2010 学年第 二 学期

计算机与通信 学院（系、部） 通信工程 专业 092 班级

课程名称： 数据结构

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

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

内
容
及
任
务

一、设计的主要技术参数
使用栈机制模拟迷宫的寻路过程, 图的DFS 自动生成随机迷宫地图。

二、设计任务
使用C语言实现各个模块的功能。

三、设计工作量
王灿阳负责对栈的基本操作，我实现车厢的调度的进和出，以及状态的变化。
进
度
安
排
起止日期
工作内容
2010-6-28
设计本程序思路
2010-6-30
实现子程序模块函数
2010-7-6
将子程序和主程序构建成完整的C源程序，并且进行相关编译调试
2010-7-7
数据测试、形成文档

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

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

2

数据结构
设计说明书

数据结构课程设计
编制一个车厢调度的程序

起止日期： 2010 年 6 月 28日 至 2010年 7 月 10 日
学生 姓名

班级
通信092班
学号

成绩

指导教师(签字)

计算机与通信学院（部）
年 月 日
湖南工业大学课程设计情况分析表
课程设计名称
数据结构
设计周数
17周
学院（部）
计算机与通信学院
系（教研室）
通信工程系
指导教师
文志诚
学生专业、班级
通信工程0901
选题

车厢调度
成绩分布

优
良
中
及格
不及格
学生数

百分比

学生课程设计存在的主要问题

改进措施及建议

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

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

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

目录

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");
printf(" || \n");
printf(" |数据结构课程设计|\n");
printf(" | |\n");
printf(" | 铁路调度站模拟 |\n");
printf(" | |\n");
printf(" | 11级软件工程|\n");
printf(" || \n");
printf(" ----------------------------\n");
printf(" 按任意键继续 \n");
if(ch=getch());

do {
// system("cls"); //停顿
printf("\n\n\n ************************* \n");
printf(" * 1:请输入火车的长度: *\n");
printf(" * *\n");
printf(" * 2:输出所有可能序列: *\n");
printf(" * *\n");
printf(" * 3:退出本程序: *\n");
printf(" ************************ \n");
printf(" 请你根据需要选择序号\n");

scanf("%d",&m);
if(m==1)
{
printf("请输入车厢长度:\n");
scanf("%d",&n);
printf("车厢长度已输入!\n");
getchar();//停止
getchar();
}
if(m==2)
{
Initstack();
push(1);
printf("所有输出序列:\n");
process(1,path,0); //从1 开始，递归处理所有元素
getchar();//停止
getchar();
}
if(m==3)
printf("欢迎退出!\n");
printf("\n");
if(m!=1&&m!=2&&m!=3)
{
printf("\n输入有误!请重新输入!");
getchar();//停止
getchar();
}
}while(m!=3);
}

四:调试分析

1. 做本次课设, 刚开始写的代码中虽然用到了递归去求解函数，但是不能很好的输完整结果，但是栈的相关操作是正确的,后来发现是由于调度递归算法中元素出栈后没有继续让其进栈。经改后恢复正常。

2. 在设计调度初始化函数的时候,参数的传递出现错误,主要是对指针和引用的理解出现混淆,通过查阅相关资料, 弄清楚了两者之间的区别,指针是用于指向一个变量的地址,而引用只是对一个已存在变量的一个重命名.
3.用printf函数输出标志信息跟踪函数调用,收到了显著的效果,大大提高了调
试效率, 有利于以后的代码调试.
4. 在实现调度功能时发现,每次调用system("cls")函数时都进行清屏操作,屏
幕只出现当前的操作目标,一目了然。用户进入系统只需按要求进行，操作时简洁清晰.
代码中的主要算法://输出一种可能的for(i=0;i<curp;i++)的时间复杂度为 O( n ).
5. 经验体会: 参考书本的代码进行改进，使用模块化操作易于代码的调试和修改,而且易于阅读.在设计实现过程中虽然遇到了很多问题,但是在解决这些问题的过程中,巩固和加深了我们对已学知识的理解,对团队合作有了一个比较基础的认识,为以后的工作实践打下了基础，同时也增加了我们对这门课的认识.

五.用户手册
1.本程序的运行环境为 DOS 操作系统, 执行文件为Programming.exe.
2.进入演示程序后 , 即显示文本方式的用户界面:
操作提示信息
键入选择

3. 进入”建立自定义调度系统” 命令后, 根据提示输入你需要选择的序号,回车后即可得到”调度建立完成”的提示信息.
操作命令清单

4. 数据不合要求则会提示:

5. 进入 “试测模拟调度” 命令后, 用户只需根据要求一步步的输入,按Enter键后.完成后,输出可能的结果。

6. 输入 “3” 即可退出此演示程序.

六. 测试结果
1. 根据提示输入

2. 输入第二组测试数据 ：3

七、附录 完整的程序清单:
#include"stdlib.h"
#include"stdafx.h"
#include"stdio.h"
#include <conio.h>
#include"windows.h"
#define MaxLen 100
struct snode
{
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;
}
/*
每次调用求值阶段包含两重递归，只有全部返回，才表示本pos 处理完，可以对上一个元素求值，
process 就是找出当前元素进栈后所有可能的操作，即在当前元素进栈后各种情况下，
包括不出栈，立即出栈，出栈后继续出栈情况(出栈递归)下，继续处理下一个元素(入栈递归)
*/
void process(int pos,int path[],int curp)//当前处理位置pos的元素
{
int m,i;
if(pos<n)//编号进栈递归
{
push(pos+1);//当前元素进栈后下一个元素继续进栈
process(pos+1,path,curp); //处理下一个元素，返回表明下一个元素进栈的情况处理完了,这里用递归将2,3,4....n压入栈
pop(); //下一个元素处理完后，pop 掉，准备处理直接出栈
}

if(!Emptys())//递归处理出栈
{
m=pop();
path[curp]=m; //数组存放出栈元素
curp++;
process(pos,path,curp);//出栈后处理下一个素继续进栈, 用递归将n,....4,3,2,1压入栈
push(m);// 递归完后又按原顺序将1,2,3,4....n压入栈
}
if(pos==n&&Emptys())//输出一种可能的方案
{
for(i=0;i<curp;i++)
printf("%2d",path[i]);
printf("\n");
}
}
void main()
{
int path[MaxLen];
int m;
char ch;
printf(" \n\n\n ---------------------------- \n");
printf(" || \n");
printf(" |数据结构课程设计|\n");
printf(" | |\n");
printf(" | 铁路调度站模拟 |\n");
printf(" | |\n");
printf(" | 11级软件工程|\n");
printf(" || \n");
printf(" ----------------------------\n");
printf(" 按任意键继续 \n");
if(ch=getch());

do {
system("cls"); //停顿
printf("\n\n\n ************************* \n");
printf(" * 1:请输入火车的长度: *\n");
printf(" * *\n");
printf(" * 2:输出所有可能序列: *\n");
printf(" * *\n");
printf(" * 3:退出本程序: *\n");
printf(" ************************ \n");
printf(" 请你根据需要选择序号\n");

scanf("%d",&m);
if(m==1)
{
printf("请输入车厢长度:\n");
scanf("%d",&n);
printf("车厢长度已输入!\n");
getchar();//停止
getchar();
}
if(m==2)
{
Initstack();
push(1);
printf("所有输出序列:\n");
process(1,path,0); //从1 开始，递归处理所有元素
getchar();//停止
getchar();
}
if(m==3)
printf("欢迎退出!\n");
printf("\n");
if(m!=1&&m!=2&&m!=3)
{
printf("\n输入有误!请重新输入!");
getchar();//停止
getchar();
}
}while(m!=3);
}

参考书：
<<面向对象C语言程序设计>>，<<数据结构（C语言版）>>,<<图算法>>,<<Windows系统编程-第三版>>

XVIII