机软二次作业.docx

1、机软二次作业 计算机软件基础实验报告/* 停车场管理的简单模拟 */#define N 4 /* 停车场容量 */#define M 5 /* 收费单价/单位时间 */#define True 1#define False 0#define Null 0#include #include #include typedef struct element int num; int arrtime;|*定义整形变量车的数目和到达时间*| ElemType;typedef struct stacktag ElemType stackN; int top;|*建立链棧并定义头指针*| STACK;typ

2、edef struct nodetag int num; struct nodetag *next; QUEUE;typedef struct queuetag QUEUE *front,*rear;|*定义队头和队尾*|LinkedQueTp;void IniStack(STACK *s);int Push(STACK *s,ElemType x);ElemType Pop(STACK *s);void IniLinkedQue(LinkedQueTp *s);|*链棧的建立*|void EnLinkedQue(LinkedQueTp *s,int num1);|*车辆进入停车场*|int

3、DeLinkedQue(LinkedQueTp *s);|*车辆开出停车场*|void Arrive(STACK *s1,LinkedQueTp *p,ElemType x);|*车辆到达处理*|void Delive(STACK *s1,STACK *s2,LinkedQueTp *p,ElemType x);|*离开处理 void IniStack(STACK *s) s-top=-1;|*栈空*| return;int Push(STACK *s,ElemType x) |*判断是否栈满*| if(s-top=N-1) printf(nStack Overflow!n); return

4、(False); else s-top+; |*新节点指向栈顶并将其数据赋值*|s-stacks-top=x; return (True); /* Initialize Stack */ElemType Pop(STACK *s) ElemType x; int i; if(s-toptop-; |*后面的 车依次开出*| i=s-top+1; x=s-stacki;|*该走的车开出后其余的车依原来的次序进场*| return x; /* Pop */void IniLinkedQue(LinkedQueTp *s) QUEUE *p1; s-front=(QUEUE *)malloc(siz

5、eof(QUEUE);|*申请新节点*| s-rear=s-front;|*队空*| p1=s-front; p1-next=Null; /* 头结点指针域初始化 */ p1-num=0; /* 头结点数据域初始化 */* IniLinkedQue */void EnLinkedQue(LinkedQueTp *s,int num1) /* 数据入队列（链接式循环队列） */ QUEUE *p,*p1; p=(QUEUE *)malloc(sizeof(QUEUE); /* 产生一个新节点 */ p-num=num1; p-next=Null; p1=s-rear; /* 加入队尾 */ p1

6、-next=p; s-rear=p; p1=s-front; p1-num+; /* 修改保存在头结点数据域中的车辆数 */* EnLinkedQue */int DeLinkedQue(LinkedQueTp *s) /* 数据节点出队列 */ QUEUE *p; int n; 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

7、; free(p);|*释放节点p*| s-front-num-;|*s指向队头数量递减*| return (n); /* DeLinkedQue */void Arrive(STACK *s1,LinkedQueTp *p,ElemType x) /* 车辆到达处理 */ int f,no1,no2; /* 可以删去 */ f=Push(s1,x); /* 新到车辆进入停车场栈 */ if(f=False) /* 如停车场满, 就进入便道队列等待 */ EnLinkedQue(p,x.num);no1=p-front-num; /* 可以删去 */printf(第%d号车停在便道的第%d号车

8、位上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 */void Delive(STACK *s1,STACK *s2,LinkedQueTp *p,ElemType x) /*

9、离开处理 */ int n,f=False; ElemType y,z; /* 增加z */ QUEUE *q; while(s1-top-1) & (f!=True) /* 在停车场中寻找要离开的车辆 */ y=Pop(s1); if(y.num!=x.num) /* 如果栈顶元素不是要离开的车辆,就将其放如车辆规闭所*/ n=Push(s2,y); else f=True; /*/ if(y.num=x.num) /*在停车场中找到要离开的车辆*/ printf(第%d号车应收费%d元,y.num,(x.arrtime-y.arrtime)*M); while(s2-top-1) whil

10、e(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=F

11、alse & 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); void main() /* 停车场模拟管理程序 */ char

12、 ch1,ch2; STACK *s1,*s2; LinkedQueTp *p; ElemType x; int flag,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(); pr

13、intf(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(nPress any key to continue.n); getch(); break; case d: case D: Delive(s1,s2,p,x); printf(nPress an

14、y key to continue.n); getch(); break; case e: case E: flag=False; printf(n程序正常结束n); break; default: printf(n输入数据错误，重新输入n); printf(nPress any key to continue.n); getch(); break; if(flag=False) break; /* 退出循环 */ return; /*迷宫问题*/#define M2 12#define N2 11#define MAXLEN M2#define True 1#define False 0#d

15、efine Null 0#include #include #include #include int M=M2-2,N=N2-2;typedef struct elem int x,y,dir; ElemType;typedef struct stktag ElemType stackMAXLEN;|*存放站的数据元素*| int top;|*棧顶指针用来存放棧顶元素在数组中的下标*| STACK;typedef struct moved int dx,dy;MOVE;void IniMaze(int mazeN2); /*初始化迷宫*/void IniMove(MOVE move); |*

16、移动位置*|void IniStack(STACK *s); |*初始化棧s*|int Push(STACK *s,ElemType x);|*进栈*|ElemType Pop(STACK *s);void path(int mazeN2,MOVE move,STACK *s);|*初始化路径*|void draw(int mazeN2,STACK *s);|*初始化迷宫数组*|void main() /* 寻找迷宫通路程序*/ STACK *s; int mazeM2N2; MOVE move8; IniMaze(maze); /* 初始化迷宫数组 */ getch(); s=(STACK

17、*)malloc(sizeof(STACK);|*申请新节点*| IniStack(s);|*初始化棧s为空栈*| IniMove(move);|*移动位置*| path(maze,move,s);|迷宫路径*| draw(maze,s);/* main */void IniMaze(int mazeN2) /*初始化迷宫*/ int i,j,num; for(i=0,j=0;i=M+1;i+) mazeij=1; for(i=0,j=N+1;i=M+1;i+) mazeij=1;|*沿数组横向移动*| for(i=0,j=0;j=N+1;j+) mazeij=1; for(i=M+1,j=0

18、;j=N+1;j+) mazeij=1;|*沿数组纵向移动*| for(i=1;i=M;i+) for(j=1;j=N;j+) num=(800*(i+j)+1500) % 327;|*将0和1散乱分布*| if (num150)&(i!=M|j!=N) mazeij=1; else mazeij=0; printf(n); for(i=0;i=M+1;i+) printf(n); for(j=0;jtop=-1;|*顺序棧的棧顶指针*|/* IniStack */int Push(STACK *s,ElemType x) if(s-top=MAXLEN-1) return (False);|

19、*判断是否棧满*| else s-stack+s-top=x;|*s进棧并将其赋值为x*| return (True); /* Push */ElemType Pop(STACK *s) |*出棧*| ElemType elem; if(s-toptop-;|*从棧顶出棧*| return (s-stacks-top+1); /* pop */void path(int mazeN2,MOVE move,STACK *s) |*移动路径*| int i,j,dir,x,y,f; ElemType elem; i=1; j=1; dir=0; maze11=-1; /* 设11为入口处 */ d

20、o x=i+movedir.dx; /* 求下一步可行的到达点的坐标 */ y=j+movedir.dy; if(mazexy=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; mazexy=-1; else if(dirtop=-1) & (dir=7) | (x=M)&(y=N)&(mazexy=-1); if(s-top=-1) printf(此迷宫无路n); else elem.x=x;elem.y=y;elem.dir=dir; f=Pus

21、h(s,elem);|*进棧函数*| printf(n迷宫的通路是:n); i=0; while(itop) printf(%d,%d),s-stacki.x,s-stacki.y); /* 显示迷宫通路 */ if(i!=s-top) printf(-);|*非空*| if(i+1)%4=0) printf(n); i+; printf(n); /* path */void draw(int mazeN2,STACK *s) |*初始化路径数组*| int i,j; ElemType elem; for(i=1;i=M;i+) /* 将迷宫中全部的-1值恢复为0值 */ for(j=1;jt

22、op-1) /* 根据栈中元素的坐标,将通路的各个点的值改为8 */ elem=Pop(s); i=elem.x; j=elem.y; mazeij=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); else if(mazeij=8) printf( %c,*);|*再通路标记*| else printf(%3d,mazeij); /* 显示已标记通路的迷宫 */ printf(n); printf(n);/* draw */ /* 迷宫2-最短路线 */#define M2

23、12#define N2 11#define MAXLEN M2*N2#define True 1#define False 0#define Null 0#include #include #include #include int M=M2-2,N=N2-2;typedef struct elem /* 定义栈元素的数据类型 */ int x,y; int dir; ElemType;typedef struct stktag /* 定义顺序栈结构 */ ElemType stackMAXLEN;|*存放棧的数据元素*| int top;|*棧顶指针用来存放棧顶元素在数组中的下标*| ST

24、ACK;typedef struct QueEle /* 定义队列元素的数据类型 */ int x,y; int pre; QueElem;typedef struct QueTag QueElem queueMAXLEN; int front,rear;|*定义队头队尾*| QUEUE;typedef struct moved /* 定义方向位移数组元素的类型 */ int dx,dy; MOVE;void IniMaze(int mazeN2); /*初始化迷宫*/void IniMove(MOVE move);|8初始化移动方位*|void IniStack(STACK *s);|*初始

25、化s为空棧*|int Push(STACK *s,ElemType x);|*x进棧*|ElemType Pop(STACK *s);|*出栈函数*|int shortpath(int mazeN2,MOVE move,QUEUE *p);void draw(int mazeN2,STACK *s);void IniQueue(QUEUE *s); /* 初始化队列 */void printpath(QUEUE *p,STACK *s); /* 显示迷宫通路 */void main() /* 寻找迷宫通路程序*/ STACK *s; QUEUE *p; int mazeM2N2,f; MOVE move8; IniMaze(maze);