停车场以及迷宫问题(页 1) - 数据结构与算法 - 编程论坛

lauyeah 发表于 2005-12-26 12:33

停车场以及迷宫问题

停车场以及迷宫问题求助! 请个位大侠帮帮忙，说一下思路以及结构体的写法! [em04] 先谢谢了!

lauyeah 发表于 2005-12-26 12:38

停车场管理: [问题描述] 设停车场内只有一个可停放n辆汽车的狭长通道,且只有一个大门可供汽车进出;汽车在停车场内按车辆到达时间的先后顺序,依次由北向南排列(大门在最南端,最先到达的第一辆车停放在车场的最北端),若车场内已停滞n辆汽车,则后来的汽车只能在门外的便道上等候,一旦有车开走,则排在便道上的第一辆车即可开入:当停车场内某辆车要离开时,在它之后开入的车辆必须先退出车场为它让路,待该辆车开出大门外,其他车辆再按原次序进入车场,每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用.试为停车场编制按上述要求进行管理的模拟程序. [基本要求] 以栈模拟停车场,以队列模拟车场外的便道,按照从终端读入的输入数据序列进行模拟管理.每一组输入数据包括三个数据项:汽车"到达"或"离去"信息、汽车牌照号码及到达或离去的时刻，对每一组输入数据进行操作后的输出数据为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车辆离去，则输出汽车在停车场内停留的时间及应交纳的费用（在便道上停留的时间不收费）。栈以顺序结构实现，队列以链式结构实现。

lauyeah 发表于 2005-12-26 12:43

#include<stdio.h> #include<stdlib.h> #include<string.h> /*----------------------结构定义--------------------------------*/ #define MAX 2 /*车库容量*/ #define price 0.05 /*每车每分钟费用*/ typedef struct time{ int hour; int min; }Time; /*时间结点*/ typedef struct node{ char num[10]; Time reach; Time leave; }CarNode; /*车辆信息结点*/ typedef struct NODE{ CarNode *stack[MAX+1]; int top; }SeqStackCar; /*模拟车站*/ typedef struct car{ CarNode *data; struct car *next; }QueueNode; typedef struct Node{ QueueNode *head; QueueNode *rear; }LinkQueueCar; /*模拟通道*/ /*-------------------初始化函数----------------------------------*/ void InitStack(SeqStackCar *); /*初始化栈*/ int InitQueue(LinkQueueCar *); /*初始化便道*/ int Arrival(SeqStackCar *,LinkQueueCar *); /*车辆到达*/ void Leave(SeqStackCar *,SeqStackCar *,LinkQueueCar *); /*车辆离开*/ void List(SeqStackCar,LinkQueueCar); /*显示存车信息*/ /*----------------------子函数-------------------------------------*/ void main() { SeqStackCar Enter,Temp; LinkQueueCar Wait; int ch; InitStack(&Enter); /*初始化车站*/ InitStack(&Temp); /*初始化让路的临时栈*/ InitQueue(&Wait); /*初始化通道*/ while(1) { printf("\n1. The car arrived:"); printf(" 2. The car leave:"); printf(" 3. Show the list:"); printf(" 4. Exit the OS:\n"); while(1) { scanf("%d",&ch); if(ch>=1&&ch<=4)break; else printf("\nPlease chose： 1|2|3|4."); } switch(ch) { case 1:Arrival(&Enter,&Wait);break; /*车辆到达*/ case 2:Leave(&Enter,&Temp,&Wait);break; /*车辆离开*/ case 3:List(Enter,Wait);break; /*列表打印信息*/ case 4:exit(0); /*退出主程序*/ default: break; } } } /*----------------出站车函数----------------------------------------*/ void InitStack(SeqStackCar *s) /*初始化栈*/ { int i; s->top=0; for(i=0;i<=MAX;i++) s->stack[s->top]=NULL; } int InitQueue(LinkQueueCar *Q) /*初始化便道*/ { Q->head=(QueueNode *)malloc(sizeof(QueueNode)); if(Q->head!=NULL) { Q->head->next=NULL; Q->rear=Q->head; return(1); } else return(-1); } void PRINT(CarNode *p,int room) /*打印出站车的信息*/ { int A1,A2,B1,B2; printf("\nInput the left time:/**:**/"); scanf("%d:%d",&(p->leave.hour),&(p->leave.min)); printf("\nNo.of the left car:"); puts(p->num); printf("\nArrival time: %d:%d",p->reach.hour,p->reach.min); printf("Left time: %d:%d",p->leave.hour,p->leave.min); A1=p->reach.hour; A2=p->reach.min; B1=p->leave.hour; B2=p->leave.min; printf("\nCharge: %2.1f元",((B1-A1)*60+(B2-A2))*price); free(p); } int Arrival(SeqStackCar *Enter,LinkQueueCar *W) /*车辆到达*/ { CarNode *p; QueueNode *t; p=(CarNode *)malloc(sizeof(CarNode)); flushall(); printf("\nInput car number(eg:SHANA1234):"); gets(p->num); if(Enter->top<MAX) /*车场未满，车进车场*/ { Enter->top++; printf("\nThe car's position is %d/n.",Enter->top); printf("\nInput arrival time:/**:**/"); scanf("%d:%d",&(p->reach.hour),&(p->reach.min)); Enter->stack[Enter->top]=p; return(1); } else /*车场已满，车进便道*/ { printf("\nMust wait at sidewalk!"); t=(QueueNode *)malloc(sizeof(QueueNode)); t->data=p; t->next=NULL; W->rear->next=t; W->rear=t; return(1); } } void Leave(SeqStackCar *Enter,SeqStackCar *Temp,LinkQueueCar *W) { /*车辆离开*/ int i, room; CarNode *p,*t; QueueNode *q; /*判断车场内是否有车*/ if(Enter->top>0) /*有车*/ { while(1) /*输入离开车辆的信息*/ { printf("\nInput the position of this car:/1--%d/：",Enter->top); scanf("%d",&room); if(room>=1&&room<=Enter->top) break; } while(Enter->top>room) /*车辆离开*/ { Temp->top++; Temp->stack[Temp->top]=Enter->stack[Enter->top]; Enter->stack[Enter->top]=NULL; Enter->top--; } p=Enter->stack[Enter->top]; Enter->stack[Enter->top]=NULL; Enter->top--; while(Temp->top>=1) { Enter->top++; Enter->stack[Enter->top]=Temp->stack[Temp->top]; Temp->stack[Temp->top]=NULL; Temp->top--; } PRINT(p,room); /*判断通道上是否有车及车站是否已满*/ if((W->head!=W->rear)&&Enter->top<MAX) /*便道的车辆进入车场*/ { q=W->head->next; t=q->data; Enter->top++; printf("\n%scar in sidewalk enter the parkseat%d.",t->num,Enter->top); printf("\nInput now time/**:**/:"); scanf("%d:%d",&(t->reach.hour),&(t->reach.min)); W->head->next=q->next; if(q==W->rear) W->rear=W->head; Enter->stack[Enter->top]=t; free(q); } else printf("\nNo car at sidewalk.\n"); } else printf("\nNo car in the park."); /*没车*/ } void List1(SeqStackCar *S) /*列表显示车场信息*/ { int i; if(S->top>0) /*判断车站内是否有车*/ { printf("\nPark:"); printf("\n Position Arrivaltime CarNo.\n"); for(i=1;i<=S->top;i++) { printf(" %d ",i); printf("%d:%d ",S->stack->reach.hour,S->stack->reach.min); puts(S->stack->num); } } else printf("\nNo car in the park"); } void List2(LinkQueueCar *W) /*列表显示便道信息*/ { QueueNode *p; p=W->head->next; if(W->head!=W->rear) /*判断通道上是否有车*/ { printf("\nWaiting car number:"); while(p!=NULL) { puts(p->data->num); p=p->next; } } else printf("\nNo car at the sidewalk."); } void List(SeqStackCar S,LinkQueueCar W) { int flag,tag; flag=1; while(flag) { printf("\nChose 1|2|3:"); printf("\n1.Park\n2.Sidewalk\n3.Back\n"); while(1) { scanf("%d",&tag); if(tag>=1||tag<=3) break; else printf("\nChose 1|2|3:"); } switch(tag) { case 1:List1(&S);break; /*列表显示车场信息*/ case 2:List2(&W);break; /*列表显示便道信息*/ case 3:flag=0;break; default: break; } } }

yfzsj 发表于 2005-12-26 15:11

那么迷宫问题呢？

Liming_686 发表于 2007-1-3 10:35

支持啊,我就想要它啊!

Liming_686 发表于 2007-1-3 10:38

顶了,正是我想要的啊!

soft_wind 发表于 2007-1-3 12:50

程序是用来演示迷宫走法的，图形模式。 TC下运行。 从文件读入，文件如下： maze.txt 
<DIV class=htmlcode>1 0 0 0 1 1 0 1 1 0 0 1 1 0 0 0 0 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 0 1 0 0 1 1 1 1 0 0 1 1 0 1 1 0 1 0 0 1 1 1 1 0 0 1 1 1 0 0 1 1 0 1 0 0 1 1 1 1 0 0 0 1 0 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 0 0 1 1 1 1 0 1</DIV>
<DIV class=htmlcode>
#include "Stdio.h" #include "Conio.h" #include "Stack.h" #include "graphics.h" #include "dos.h" #define N 10 /*为迷宫每个点的信息处理重命名*/ typedef struct INFOR { int num; /*迷宫的点是可通过（1）还是不可通过（0）*/ int flag; /*迷宫的点是否被走过*/ }info; /*迷宫点的坐标和判断节点是否可行*/ typedef struct MAZE { cod point; int tag; }maze;
maze search(info a[][N+2],int x,int y); void draw_maze(info a[][N+2]); void draw_way(int way[][2],int i);
int main(void) { list_stack *s=NULL; info arr[N+2][N+2]; FILE *fp; int i,j; int way[100][2]={0}; int gdriver=DETECT,gmode; cod cur; /*初始化链栈*/ InitialStack(s); /*从文件中读取数据*/ fp=fopen("MAZE.TXT","r"); if(fp==NULL) exit(1); for(i=0;i<N+2;i++) for(j=0;j<N+2;arr[i][j].num=arr[i][j].flag=0,j++); for(i=1;i<=N;i++) for(j=1;j<=N;fscanf(fp,"%d",&arr[i][j].num),j++); fclose(fp); /*由于是回溯寻找，所以从出口开始往回找*/ cur.x=cur.y=10; arr[10][10].flag=1; push(s,cur); do { maze var; var=search(arr,cur.x,cur.y); /*如果返回的是tag==1,说明该迷宫点不通*/ if(var.tag) { /*取出栈顶第一个元素，并弹出*/ cur=GetTop(s); pop(s); } else { /*否则压入栈，把当前的坐标替换*/ push(s,var.point); cur=var.point; } }while(cur.x!=1||cur.y!=1);/*出口的条件*/ s=s->link; i=1; /*打印栈里的内容*/ while(s->link->link) { way[i][0]=s->xy.x;way[i][1]=s->xy.y; printf("(%d,%d)->",s->xy.x,s->xy.y); s=s->link; i++; } printf("(%d,%d)",10,10); way[i][0]=way[i][1]=10; getch(); /*建立独立图形运行程序*/ registerbgidriver(EGAVGA_driver); initgraph(&gdriver,&gmode,"c:\\turboc2"); /*输出迷宫图*/ draw_maze(arr); draw_way(way,i); getch(); closegraph(); return 0; } /* 函数功能：查找8个方向的位置。 */ maze search(info a[][N+2],int x,int y) { maze var; /*左*/ if(a[x][y-1].num==1&&a[x][y-1].flag==0) { a[x][y-1].flag=1; var.point.x=x; var.point.y=y-1; var.tag=0;/*表示还可继续查询*/ return var; } /*左上*/ if(a[x-1][y-1].num==1&&a[x-1][y-1].flag==0) { a[x-1][y-1].flag=1; var.point.x=x-1; var.point.y=y-1; var.tag=0;/*表示还可继续查询*/ return var; } /*上*/ if(a[x-1][y].num==1&&a[x-1][y].flag==0) { a[x-1][y].flag=1; var.point.x=x-1; var.point.y=y; var.tag=0;/*表示还可继续查询*/ return var; } /*右上*/ if(a[x-1][y+1].num==1&&a[x-1][y+1].flag==0) { a[x-1][y+1].flag=1; var.point.x=x-1; var.point.y=y+1; var.tag=0;/*表示还可继续查询*/ return var; } /*右*/ if(a[x][y+1].num==1&&a[x][y+1].flag==0) { a[x][y+1].flag=1; var.point.x=x; var.point.y=y+1; var.tag=0;/*表示还可继续查询*/ return var; } /*右下*/ if(a[x+1][y+1].num==1&&a[x+1][y+1].flag==0) { a[x+1][y+1].flag=1; var.point.x=x+1; var.point.y=y+1; var.tag=0;/*表示还可继续查询*/ return var; } /*下*/ if(a[x+1][y].num==1&&a[x+1][y].flag==0) { a[x+1][y].flag=1; var.point.x=x+1; var.point.y=y; var.tag=0;/*表示还可继续查询*/ return var; } /*左下*/ if(a[x+1][y-1].num==1&&a[x+1][y-1].flag==0) { a[x+1][y-1].flag=1; var.point.x=x+1; var.point.y=y-1; var.tag=0;/*表示还可继续查询*/ return var; } var.tag=1; return var; } /* 函数功能：打印整个迷宫图。 */ void draw_maze(info a[][N+2]) { int i,j; for(i=0;i<N+2;i++) for(j=0;j<N+2;j++) if(a[i][j].num==1) { setfillstyle(1,WHITE); bar(140+j*20-9,80+i*20-9,140+j*20+9,80+i*20+9); } else { setfillstyle(1,BLUE); bar(140+j*20-9,80+i*20-9,140+j*20+9,80+i*20+9); } } /* 函数功能：打印出迷宫出路。 */ void draw_way(int way[][2],int i) { int j; setfillstyle(1,RED);/*红色输出走的具体路线*/ for(j=1;j<=i;j++) { bar(140+way[j][1]*20-9,80+way[j][0]*20-9,140+way[j][1]*20+9,80+way[j][0]*20+9); sleep(1); } setcolor(GREEN); settextstyle(0,0,2); outtextxy(165,330,"Find a way!"); }</DIV>

桥青轻 发表于 2008-2-28 16:21

hao hao good!!good!! very good!!

sunkaidong 发表于 2008-2-28 20:30

迷宫问题是程序员的教材上得

随心发表于 2008-2-29 19:14

停车场用栈和队列应该可以了

页: [1]

编程论坛's Archiver

停车场以及迷宫问题