课程设计报告.docx
《课程设计报告.docx》由会员分享，可在线阅读，更多相关《课程设计报告.docx（19页珍藏版）》请在冰点文库上搜索。
课程设计报告
数据结构课程设计报告
项目：
专业：
班级：
学号：
姓名：
指导老师：
2006～2007学年第二学期
一、问题描述：
有一个渡口，每条渡轮一次能装载10辆汽车过江，过江车辆分为客车和货车两类，上渡轮有如下规定：
（1）同类汽车先到先上船。
（2）客车先与货车上船。
（3）每上4辆客车才允许上一辆货车，但若等待的客车不足4辆则用货车填补，反过来，若没有货车等待则用客车填补。
（4）装满10辆后则自动开船，当等待时间较长时车辆不足10辆也应人为控制发船。
二、算法思想：
此问题应建立和使用两个队列，一个为客车队列，另一个为货车队列，到渡口需过江的汽车分别进入到相应队列中。
当渡口有渡轮时先让客车队列中的4个车辆出队并开进渡轮，再让货车队列中的一个车辆出队并开进渡轮，若某一类车辆队列为空则从另一个队列中补充。
当渡轮上的车辆已满则自动开船，此时应打印出已装车辆的每个车号。
若装载不足10辆，但两个车辆队列全为空，应继续等待一段时间，若等待时间较长，仍不满载则应人为控制开船。
三、基本要求：
总体原则是客车优先于货车，比例为4：
1，但能根据实际情况，灵活调整装载的汽车以及发船的控制。
四、模块划分：
（1）流程图
123456
（2）具体应用模块：
1．队列的相关运算：
（存于单独源文件“链式队列.cpp”中）
voidInitQueue（LinkQueue&Q）//初始化队列
voidEnQueue（LinkQueue&Q,ElemTypeitem）//向队列中插入一个元素
ElemTypeOutQueue（LinkQueue&Q）//从队列中删除一个元素
voidClearQueue（LinkQueue&Q）//清除队列中的所有元素，使之变成空队
boolEmptyQueue（LinkQueue&HQ）//检查队列是否为空
2．渡轮输出相关模块：
voidPrint（inta[],intn）//输出本次轮渡所载汽车编号
voidOutputQueue（constLinkQueue&q1,constLinkQueue&q2）
//输出汽车排队等待的情况
五、数据结构：
建立两个链接队列，一个为客车队列，另一个为货车队列，到渡口需过江的汽车分别进入到相应队列中。
链接队列的定义为：
structLinkQueue
{
LNode*front;//队首指针
LNode*rear;//队尾指针
};
主函数中使用switch（）函数，将功能表中的六种选择分别表示为case1~case6。
具体表示：
swtch（flag）//falg为输入的功能序号
case1:
//车到渡口进行登记
…
case2:
//轮渡到渡口进行登记
…
case3:
//汽车上轮渡
…
case4:
//命令轮渡起航
…
case5:
//输出当前汽车排队情况
…
case6:
//结束程序运行
…
六、源程序：
链式队列.cpp
voidInitQueue（LinkQueue&Q）//初始化队列
{
Q.front=Q.rear=NULL;
}
voidEnQueue（LinkQueue&Q,ElemTypeitem）//向队列中插入一个元素
{
LNode*newptr=newLNode（）;
newptr->data=item;
newptr->next=NULL;
if（Q.rear==NULL）//若队列为空，则新结点既是队首又是队尾
Q.front=Q.rear=newptr;
Q.rear->next=newptr;//若队列非空，则新结点被链接到队尾
Q.rear=newptr;
}
ElemTypeOutQueue（LinkQueue&Q）//从队列中删除一个元素
{
if（Q.front==NULL）//若队列为空则终止运行
{
cout<<"Empty!
"<exit
（1）;
}
LNode*p;//暂存队首元素以便返回
p=Q.front;//暂存队首指针以便回收队首结点
ElemTypea=p->data;//使队首指针指向下一个结点
Q.front=p->next;//若删除后队列为空，则使队尾指针为空
if（Q.front==NULL）
Q.rear=NULL;
deletep;
returna;//返回删除的队首元素
}
voidClearQueue（LinkQueue&Q）//清除队列中的所有元素，使之变成空队
{
LNode*b;//对首时针赋给p
b=Q.front;
while（Q.front!
=NULL）//依次删除队列中的每个元素
{
Q.front=b->next;
deleteb;
b=Q.front;
}
Q.rear=NULL;//置队尾指针为空
}
boolEmptyQueue（LinkQueue&HQ）//检查队列是否为空
{
returnHQ.front==NULL;
}
轮渡.cpp
#include
#include
#include//此头文件包含有上time函数和ctime函数的
typedefintElemType;
structLNode{
ElemTypedata;//值域
LNode*next;//链接指针域
};
structLinkQueue
{
LNode*front;//队首指针
LNode*rear;//队尾指针
};
#include"链接队列.cpp"
//输出本次轮渡所载汽车编号
voidPrint（inta[],intn）
{
longt;
t=time（0）;//当前机器系统时间被保存到t中，单位为秒
cout<cout<<"轮渡开始起航->"<cout<<"本次过江的时间:
"<//ctime（&t）函数的值为根据参数t转换得到的日期和时间的字符串
cout<<"本次轮渡所载汽车:
";
for（inti=0;icout<}
//输出汽车排队等待的情况
voidOutputQueue（constLinkQueue&q1,constLinkQueue&q2）
{
cout<<"客车等候的情况:
";
LNode*p=q1.front;
if（p==NULL）cout<<"暂时无客车等候."<while（p!
=NULL）
{
cout<data<<'';
p=p->next;
}
cout<cout<<"货车排队的情况:
";
p=q2.front;
if（p==NULL）cout<<"暂时无货车等候."<while（p!
=NULL）
{
cout<data<<'';
p=p->next;
}
cout<}
voidmain（）
{
//q1和q2队列用来分别存储待渡江的客车和货车
LinkQueueq1,q2;
//对q1和q2进行初始化
InitQueue（q1）;
InitQueue（q2）;
//用flag保存用户选择，用mark登记轮渡到渡口
intflag,mark=0;
//用数组a记录轮渡上的每个汽车号，用n记录汽车的个数
inta[10],n=0;
//用t1和t2登记时间
longt1,t2;
//程序处理结果
do
{
//显示功能表并接受用户选择
L1:
cout<<"功能表:
"<cout<<"1---车到渡口进行登记"<cout<<"2---轮渡到渡口进行登记"<cout<<"3---汽车上轮渡"<cout<<"4---命令轮渡起航"<cout<<"5---输出当前汽车排队情况"<cout<<"6---结束程序运行"<cout<<"请输入你的选择（1-6）：
";
do
{
cin>>flag;
if（flag<1||flag>6）cout<<"输入功能号错，重输:
";
}while（flag<1||flag>6）;
intx,i;
//根据不同选择进行相应处理
switch（flag）{
case1:
cout<<"输入车辆号，假定小于100为客车，否则为货车，"<cout<<"可以输入多辆车，用空格分开，直到输入-1为止。
"<while
（1）{
cin>>x;
if（x==-1）break;
if（x<100）EnQueue（q1,x）;//客车进q1队
elseEnQueue（q2,x）;//货车进q2队
}
break;//结束switch语句
case2:
if（mark==1）{
cout<<"渡轮已在渡口等待，不要重复登记！
"<break;//结束switch语句
}
mark=1;//渡轮到口岸登记
cout<<"渡轮已到渡口，可以上船！
"<n=0;//装载车辆数初始为0；
t1=time（0）;//登记渡轮到渡口时间，单位为秒
break;//结束switch语句
case3:
if（EmptyQueue（q1）&&EmptyQueue（q2））{
cout<<"暂无汽车过江！
"<if（mark==1&&n!
=0）{
t2=time（0）-t1;//计算到目前为止渡轮等待时间的秒数
cout<<"轮渡未满，有车"<cout<"<}
break;//结束switch语句
}
if（mark!
=1）{
cout<<"渡轮未到，请汽车稍后上渡轮！
"<break;//结束switch语句
}
do{
i=0;
//首先上4辆客车
while（!
EmptyQueue（q1）&&n<10&&i<4）{
a[n++]=OutQueue（q1）;
i++;
}
//满10辆开船，打印车辆号，重新对mark和n清0，转功能号表
if（n==10）{Print（a,n）;mark=0;n=0;gotoL1;}
//进4辆客车则接着进一辆货车，不满4辆则由货车补
if（i==4）{
if（!
EmptyQueue（q2））a[n++]=OutQueue（q2）;
}
else{
while（!
EmptyQueue（q2）&&n<10&&i<5）{
a[n++]=OutQueue（q2）;
i++;
}
}
//满10辆则开船
if（n==10）{Print（a,n）;mark=0;n=0;gotoL1;}
}while（!
EmptyQueue（q1）||!
EmptyQueue（q2））;
//只要客车或货车队列不全为空，则继续执行do循环
t2=time（0）-t1;//登记渡轮已经等待时间的秒数
cout<<"渡轮上有车"<cout<<"秒，等候其他汽车上渡轮！
"<break;//结束switch语句
case4:
if（n==0||mark==0）
cout<<"轮渡上无车过江或根本无渡轮！
不需要起航！
"<else{
Print（a,n）;mark=0;n=0;
}
break;
case5:
OutputQueue（q1,q2）;
break;//结束switch语句
case6:
if（!
EmptyQueue（q1）||!
EmptyQueue（q2））{
cout<<"还有汽车未渡江，暂不能结束！
"<break;//结束switch语句
}
if（n!
=0）{
cout<<"渡轮上有车，不能结束，需命令开渡轮！
"<break;//结束switch语句
}
cout<<"程序运行结束！
"<return;//执行结束返回
}//switch语句终端位置
}while
（1）;//外层do循环终端位置
ClearQueue（q1）;
ClearQueue（q2）;
}
//主函数结束位置
七、测试数据：
C:
\“*.\**\轮渡.exe”
功能表:
1---车到渡口进行登记
2---轮渡到渡口进行登记
3---汽车上轮渡
4---命令轮渡起航
5---输出当前汽车排队情况
6---结束程序运行
请输入你的选择（1-6）：
1
输入车辆号，假定小于100为客车，否则为货车，
可以输入多辆车，用空格分开，直到输入-1为止。
45786723832109321235874919391894562031425388-1
功能表:
1---车到渡口进行登记
2---轮渡到渡口进行登记
3---汽车上轮渡
4---命令轮渡起航
5---输出当前汽车排队情况3
6---结束程序运行
请输入你的选择（1-6）：
2
渡轮已到渡口，可以上船！
功能表:
1---车到渡口进行登记
2---轮渡到渡口进行登记
3---汽车上轮渡
4---命令轮渡起航
5---输出当前汽车排队情况
6---结束程序运行
请输入你的选择（1-6）：
3
轮渡开始起航->
本次过江的时间:
WedJul0418:
23:
372007
本次轮渡所载汽车:
4578673223832123587109
功能表:
1---车到渡口进行登记
2---轮渡到渡口进行登记
3---汽车上轮渡
4---命令轮渡起航
5---输出当前汽车排队情况
6---结束程序运行
请输入你的选择（1-6）：
2
渡轮已到渡口，可以上船！
功能表:
1---车到渡口进行登记
2---轮渡到渡口进行登记
3---汽车上轮渡
4---命令轮渡起航
5---输出当前汽车排队情况
6---结束程序运行
请输入你的选择（1-6）：
3
渡轮上有车9辆，已等待0分10秒，等候其他汽车上渡轮！
功能表:
1---车到渡口进行登记
2---轮渡到渡口进行登记
3---汽车上轮渡
4---命令轮渡起航
5---输出当前汽车排队情况
6---结束程序运行
请输入你的选择（1-6）：
4
轮渡开始起航->
本次过江的时间:
WedJul0418:
27:
352007
本次轮渡所载汽车:
4919395318988456203142
功能表:
1---车到渡口进行登记
2---轮渡到渡口进行登记
3---汽车上轮渡
4---命令轮渡起航
5---输出当前汽车排队情况
6---结束程序运行
请输入你的选择（1-6）：
5
客车等候的情况:
暂时无客车等候.
货车排队的情况:
暂时无货车等候.
功能表:
1---车到渡口进行登记
2---轮渡到渡口进行登记
3---汽车上轮渡
4---命令轮渡起航
5---输出当前汽车排队情况
6---结束程序运行
请输入你的选择（1-6）：
6
程序运行结束！
Pressanykeytocontinue
八、结果分析：
选择“1”时，输入车辆号：
45786723832109321235874919391894562031425388
选择“2”时，说明轮渡已经到了渡口，汽车可以进入轮渡。
显示“渡轮已到渡口，可以上船！
”，说明轮渡已到渡口。
选择“3”时，让汽车按照要求进入轮渡，如果装载满了（10辆），就立刻发船，不满则等待。
显示“轮渡开始起航->
本次过江的时间:
WedJul0418:
23:
372007
本次轮渡所载汽车:
4578673223832123587109”，
说明已经装满10辆车，立刻启航。
再次选择“2”时，另一艘渡轮到渡口，汽车可以进入渡轮了。
再次选择“3”时，让汽车进入轮渡。
显示“渡轮上有车9辆，已等待0分10秒，等候其他汽车上渡轮！
”，渡轮没有装满，要等待其他车辆。
选择“4”时，认为让轮渡启航。
显示“轮渡开始起航->
本次过江的时间:
WedJul0418:
27:
352007
本次轮渡所载汽车:
4919395318988456203142”。
选择“5”时，输出当前车辆排队情况。
因为由于上面两次，车辆已经全部上了渡轮，所以显示“客车等候的情况:
暂时无客车等候.货车排队的情况:
暂时无货车等候.”。
选择“6”时，退出运行。
显示“程序运行结束！
”。
九、心得体会：
通过这次课程设计，使我对《数据结构》这门课程有了更深一步的了解。
它是计算机程序设计的重要理论技术基础，在我们计算机专业的学习中占据着十分重要的地位。
同时也使我们知道，要学好这门课程，仅学习书本上的知识是不够的，还要有较强的实践能力。
因为我们学习知识就是为了实践。
而只有多实践，多编写程序，才能更好的理解与掌握书本上的东西。
升级会员 