机软二次作业.docx
《机软二次作业.docx》由会员分享，可在线阅读，更多相关《机软二次作业.docx（24页珍藏版）》请在冰点文库上搜索。
机软二次作业
计算机软件基础实验报告
/*停车场管理的简单模拟*/
#defineN4/*停车场容量*/
#defineM5/*收费单价/单位时间*/
#defineTrue1
#defineFalse0
#defineNull0
#include
#include
#include
typedefstructelement{
intnum;
intarrtime;|*定义整形变量车的数目和到达时间*|
}ElemType;
typedefstructstacktag{
ElemTypestack[N];
inttop;|*建立链棧并定义头指针*|
}STACK;
typedefstructnodetag{
intnum;
structnodetag*next;
}QUEUE;
typedefstructqueuetag{
QUEUE*front,*rear;|*定义队头和队尾*|
}LinkedQueTp;
voidIniStack（STACK*s）;
intPush（STACK*s,ElemTypex）;
ElemTypePop（STACK*s）;
voidIniLinkedQue（LinkedQueTp*s）;|*链棧的建立*|
voidEnLinkedQue（LinkedQueTp*s,intnum1）;|*车辆进入停车场*|
intDeLinkedQue（LinkedQueTp*s）;|*车辆开出停车场*|
voidArrive（STACK*s1,LinkedQueTp*p,ElemTypex）;|*车辆到达处理*|
voidDelive（STACK*s1,STACK*s2,LinkedQueTp*p,ElemTypex）;|*离开处理
voidIniStack（STACK*s）{
s->top=-1;|*栈空*|
return;
}
intPush（STACK*s,ElemTypex）{|*判断是否栈满*|
if（s->top==N-1）{
printf（"\nStackOverflow!
\n"）;
return（False）;}
else{
s->top++;|*新节点指向栈顶并将其数据赋值*|
s->stack[s->top]=x;
return（True）;}
}/*InitializeStack*/
ElemTypePop（STACK*s）{
ElemTypex;
inti;
if（s->top<0）{
x.num=Null;
x.arrtime=Null;
return（x）;}
else{
s->top--;|*后面的车依次开出*|
i=s->top+1;
x=s->stack[i];|*该走的车开出后其余的车依原来的次序进场*|
returnx;}
}/*Pop*/
voidIniLinkedQue（LinkedQueTp*s）{
QUEUE*p1;
s->front=（QUEUE*）malloc（sizeof（QUEUE））;|*申请新节点*|
s->rear=s->front;|*队空*|
p1=s->front;
p1->next=Null;/*头结点指针域初始化*/
p1->num=0;/*头结点数据域初始化*/
}/*IniLinkedQue*/
voidEnLinkedQue（LinkedQueTp*s,intnum1）{/*数据入队列（链接式循环队列）*/
QUEUE*p,*p1;
p=（QUEUE*）malloc（sizeof（QUEUE））;/*产生一个新节点*/
p->num=num1;
p->next=Null;
p1=s->rear;/*加入队尾*/
p1->next=p;
s->rear=p;
p1=s->front;
p1->num++;/*修改保存在头结点数据域中的车辆数*/
}/*EnLinkedQue*/
intDeLinkedQue（LinkedQueTp*s）{/*数据节点出队列*/
QUEUE*p;
intn;
if（s->front==s->rear）return（Null）;|*判断是否队空*|
else{
p=s->front->next;|*令p指向头指针的前一个*|
s->front->next=p->next;|*删除节点p*|
if（p->next==Null）s->rear=s->front;|*判断是否为空*|
n=p->num;
free（p）;|*释放节点p*|
s->front->num--;|*s指向队头数量递减*|
return（n）;}
}/*DeLinkedQue*/
voidArrive（STACK*s1,LinkedQueTp*p,ElemTypex）{/*车辆到达处理*/
intf,no1,no2;/*可以删去*/
f=Push（s1,x）;/*新到车辆进入停车场栈*/
if（f==False）{/*如停车场满,就进入便道队列等待*/
EnLinkedQue（p,x.num）;
no1=p->front->num;/*可以删去*/
printf（"第%d号车停在便道的第%d号车位上\n",x.num,no1）;/*改为：
printf（"第%d号车停在便道的第%d号车位上\n",x.num,p->front->num）;*/
}
else{/*新到车辆进入停车场*/
no1=s1->top+1;/*可以删去*/
no2=x.num;/*可以删去*/
printf（"第%d号车停在停车场的第%d号车位上\n",no2,no1）;/*改为：
printf（"第%d号车停在停车场的第%d号车位上\n",x.num,s1->top+1）;*/
}
}/*Arrive*/
voidDelive（STACK*s1,STACK*s2,LinkedQueTp*p,ElemTypex）{/*离开处理*/
intn,f=False;
ElemTypey,z;/*增加z*/
QUEUE*q;
while（（s1->top>-1）&&（f!
=True））{/*在停车场中寻找要离开的车辆*/
y=Pop（s1）;
if（y.num!
=x.num）/*如果栈顶元素不是要离开的车辆,就将其放如车辆规闭所*/
n=Push（s2,y）;
elsef=True;}
/******/
if（y.num==x.num）{/*在停车场中找到要离开的车辆*/
printf（"第%d号车应收费%d元",y.num,（x.arrtime-y.arrtime）*M）;
while（s2->top>-1）{
while（s2->top>-1）{/*调整到*****处，将y改为z*/
y=Pop（s2）;
f=Push（s1,y）;}
n=DeLinkedQue（p）;
if（n!
=Null）{/*有车在队列中等待*/
y.num=n;
y.arrtime=x.arrtime;
f=Push（s1,y）;
printf（"第%d号车停在停车场第%d号车位上\n",y.num,s1->top+1）;}
}
else{/*在停车场中没有找到要离开的车辆*/
while（s2->top>-1）{/*删除*/
y=Pop（s2）;
f=Push（s1,y）;}
q=p->front;/*指向队头*/
f=False;
while（f==False&&q->next!
=Null）/*在便道上寻找要离开的车辆*/
if（q->next->num!
=x.num）q=q->next;
else{
q->next=q->next->next;/*在便道上找到该车辆*/
p->front->num--;
if（q->next==Null）p->rear=q;/*=p->front是错误的*/
printf（"第%d号车离开便道\n",x.num）;/*该车离开便道,但不收费*/
f=True;}
if（f==False）
printf（"输入数据错误,停车场和便道上均无第%d号车\n",x.num）;
}
}
voidmain（）{/*停车场模拟管理程序*/
charch1,ch2;
STACK*s1,*s2;
LinkedQueTp*p;
ElemTypex;
intflag,t1,t2;
s1=（STACK*）malloc（sizeof（STACK））;
s2=（STACK*）malloc（sizeof（STACK））;
p=（LinkedQueTp*）malloc（sizeof（LinkedQueTp））;
IniStack（s1）;/*初始化停车场栈*/
IniStack（s2）;/*初始化车辆规避所栈*/
IniLinkedQue（p）;/*初始化便道队列*/
flag=True;
for（;;）{
clrscr（）;
printf（"\n输入数据：
'A'/'D',车牌号，到达时间/离开时间\n"）;
printf（"E---退出。
\n"）;
scanf（"%c,%d,%d",&ch1,&t1,&t2）;
x.num=t1;
x.arrtime=t2;/*只记录小时值，没有考虑分钟*/
ch2=getchar（）;/*清空输入缓冲区*/
switch（ch1）{
case'a':
case'A':
Arrive（s1,p,x）;
printf（"\nPressanykeytocontinue...\n"）;
getch（）;
break;
case'd':
case'D':
Delive（s1,s2,p,x）;
printf（"\nPressanykeytocontinue...\n"）;
getch（）;
break;
case'e':
case'E':
flag=False;
printf（"\n程序正常结束\n"）;
break;
default:
printf（"\n输入数据错误，重新输入\n"）;
printf（"\nPressanykeytocontinue...\n"）;
getch（）;
break;
}
if（flag==False）break;/*退出循环*/
}
return;
}
/*迷宫问题*/
#defineM212
#defineN211
#defineMAXLENM2
#defineTrue1
#defineFalse0
#defineNull0
#include
#include
#include
#include
intM=M2-2,N=N2-2;
typedefstructelem{
intx,y,dir;
}ElemType;
typedefstructstktag{
ElemTypestack[MAXLEN];|*存放站的数据元素*|
inttop;|*棧顶指针用来存放棧顶元素在数组中的下标*|
}STACK;
typedefstructmoved{
intdx,dy;
}MOVE;
voidIniMaze（intmaze[][N2]）;/*初始化迷宫*/
voidIniMove（MOVEmove[]）;|*移动位置*|
voidIniStack（STACK*s）;|*初始化棧s*|
intPush（STACK*s,ElemTypex）;|*进栈*|
ElemTypePop（STACK*s）;
voidpath（intmaze[][N2],MOVEmove[],STACK*s）;|*初始化路径*|
voiddraw（intmaze[][N2],STACK*s）;|*初始化迷宫数组*|
voidmain（）{/*寻找迷宫通路程序*/
STACK*s;
intmaze[M2][N2];
MOVEmove[8];
IniMaze（maze）;/*初始化迷宫数组*/
getch（）;
s=（STACK*）malloc（sizeof（STACK））;|*申请新节点*|
IniStack（s）;|*初始化棧s为空栈*|
IniMove（move）;|*移动位置*|
path（maze,move,s）;|迷宫路径*|
draw（maze,s）;
}/*main*/
voidIniMaze（intmaze[][N2]）{/*初始化迷宫*/
inti,j,num;
for（i=0,j=0;i<=M+1;i++）maze[i][j]=1;
for（i=0,j=N+1;i<=M+1;i++）maze[i][j]=1;|*沿数组横向移动*|
for（i=0,j=0;j<=N+1;j++）maze[i][j]=1;
for（i=M+1,j=0;j<=N+1;j++）maze[i][j]=1;|*沿数组纵向移动*|
for（i=1;i<=M;i++）{
for（j=1;j<=N;j++）{
num=（800*（i+j）+1500）%327;|*将0和1散乱分布*|
if（（num<150）&&（i!
=M||j!
=N））maze[i][j]=1;
elsemaze[i][j]=0;
}
}
printf（"\n"）;
for（i=0;i<=M+1;i++）{
printf（"\n"）;
for（j=0;j<=N+1;j++）{
if（（i==0）&&（j==0）||（i==M+1）&&（j==N+1））printf（"%3d",0）;
elseprintf（"%3d",maze[i][j]）;|*输出坐标*|}
}
}/*IniMaze*/
voidIniMove（MOVEmove[]）{
move[0].dx=0;move[0].dy=1;/*North*/
move[1].dx=1;move[1].dy=1;/*North-East*/
move[2].dx=1;move[2].dy=0;/*East*/
move[3].dx=1;move[3].dy=-1;SouthEast*/
move[4].dx=0;move[4].dy=-1;South*/
move[5].dx=-1;move[5].dy=-1;/*SouthWest*/
move[6].dx=-1;move[6].dy=0;/*West*/
move[7].dx=-1;move[7].dy=1;/*NorthWest*/
}/*IniMove*/
voidIniStack（STACK*s）{|*初始化s棧*|
s->top=-1;|*顺序棧的棧顶指针*|
}/*IniStack*/
intPush（STACK*s,ElemTypex）{
if（s->top==MAXLEN-1）return（False）;|*判断是否棧满*|
else{
s->stack[++s->top]=x;|*s进棧并将其赋值为x*|
return（True）;}
}
/*Push*/
ElemTypePop（STACK*s）{|*出棧*|
ElemTypeelem;
if（s->top<0）{
elem.x=Null;
elem.y=Null;
elem.dir=Null;
return（elem）;|*判断是否为空栈*|
}
else{
s->top--;|*从棧顶出棧*|
return（s->stack[s->top+1]）;}
}/*pop*/
voidpath（intmaze[][N2],MOVEmove[],STACK*s）{|*移动路径*|
inti,j,dir,x,y,f;
ElemTypeelem;
i=1;j=1;
dir=0;
maze[1][1]=-1;/*设[1][1]为入口处*/
do{
x=i+move[dir].dx;/*求下一步可行的到达点的坐标*/
y=j+move[dir].dy;
if（maze[x][y]==0）{
elem.x=i;elem.y=j;
elem.dir=dir;
f=Push（s,elem）;
if（f==False）printf（"栈长度太短\n"）;
i=x;j=y;
dir=0;
maze[x][y]=-1;}
elseif（dir<7）dir++;
else{/*8个方向都不可行,就退回一步*/
elem=Pop（s）;
if（elem.x!
=Null）{
i=elem.x;j=elem.y;
dir=elem.dir+1;}
}
}while（!
（（s->top==-1）&&（dir>=7）||（x==M）&&（y==N）&&（maze[x][y]==-1）））;
if（s->top==-1）printf（"此迷宫无路\n"）;
else{
elem.x=x;elem.y=y;elem.dir=dir;
f=Push（s,elem）;|*进棧函数*|
printf（"\n迷宫的通路是:
\n"）;
i=0;
while（i<=s->top）{
printf（"（%d,%d）",s->stack[i].x,s->stack[i].y）;/*显示迷宫通路*/
if（i!
=s->top）printf（"-->"）;|*非空*|
if（（i+1）%4==0）printf（"\n"）;
i++;}
printf（"\n"）;
}
}/*path*/
voiddraw（intmaze[][N2],STACK*s）{|*初始化路径数组*|
inti,j;
ElemTypeelem;
for（i=1;i<=M;i++）/*将迷宫中全部的-1值恢复为0值*/
for（j=1;j<=N;j++）
if（maze[i][j]==-1）maze[i][j]=0;
while（s->top>-1）{/*根据栈中元素的坐标,将通路的各个点的值改为8*/
elem=Pop（s）;
i=elem.x;j=elem.y;
maze[i][j]=8;}
for（i=0;i<=M+1;i++）{
for（j=0;j<=N+1;j++）{
if（（i==0）&&（j==0）||（i==M+1）&&（j==N+1））printf（"%3d",0）;
elseif（maze[i][j]==8）printf（"%c",'*'）;|*再通路标记**|
elseprintf（"%3d",maze[i][j]）;/*显示已标记通路的迷宫*/
}
printf（"\n"）;
}
printf（"\n"）;
}/*draw*/
/*迷宫2---最短路线*/
#defineM212
#defineN211
#defineMAXLENM2*N2
#defineTrue1
#defineFalse0
#defineNull0
#include
#include
#include
#include
intM=M2-2,N=N2-2;
typedefstructelem{/*定义栈元素的数据类型*/
intx,y;
intdir;
}ElemType;
typedefstructstktag{/*定义顺序栈结构*/
ElemTypestack[MAXLEN];|*存放棧的数据元素*|
inttop;|*棧顶指针用来存放棧顶元素在数组中的下标*|
}STACK;
typedefstructQueEle{/*定义队列元素的数据类型*/
intx,y;
intpre;
}QueElem;
typedefstructQueTag{
QueElemqueue[MAXLEN];
intfront,rear;|*定义队头队尾*|
}QUEUE;
typedefstructmoved{/*定义方向位移数组元素的类型*/
intdx,dy;
}MOVE;
voidIniMaze（intmaze[][N2]）;/*初始化迷宫*/
voidIniMove（MOVEmove[]）;|8初始化移动方位*|
voidIniStack（STACK*s）;|*初始化s为空棧*|
intPush（STACK*s,ElemTypex）;|*x进棧*|
ElemTypePop（STACK*s）;|*出栈函数*|
intshortpath（intmaze[][N2],MOVEmove[],QUEUE*p）;
voiddraw（intmaze[][N2],STACK*s）;
voidIniQueue（QUEUE*s）;/*初始化队列*/
voidprintpath（QUEUE*p,STACK*s）;/*显示迷宫通路*/
voidmain（）{/*寻找迷宫通路程序*/
STACK*s;
QUEUE*p;
intmaze[M2][N2],f;
MOVEmove[8];
IniMaze（maze）;
升级会员 