数据结构与算法分析课程设计之数据结构停车场管理系统设计。主要应用到数据结构中的栈与队列。运用到的编程语言为C++。
目录
一 设计要求
二 思路分析
三 设计流程
先附上完整代码:
#include#include #include using namespace std; int position = 0;//便道内位置 typedef struct CarData { char ch;//车辆的识别符,到达or离去 int cartime[100];//车辆停车时间 int carnumber[100];//车辆车牌号 int top; int n;//容量 }cardata; //队列 typedef struct qNode { int carnumber; int cartime; struct qNode* next; }qNode, * queue; typedef struct { queue front; queue rear; }Queue; //栈********* //初始化栈 void initStack(cardata &S, int n) { S.top = -1; S.n = n; } //判断栈是否为空 int stackempty(cardata &S) { if (S.top == -1) return false; else return true; } //判断栈是否为满 int stackfull(cardata &S) { if (S.top == S.n - 1) { return true; } else { return false; } } //入栈 void push(cardata &S, int carnumber, int cartime) { S.top++; S.carnumber[S.top] = carnumber; S.cartime[S.top] = cartime; } //出栈 void pop(cardata& S, int &carnumber, int &cartime) { carnumber = S.carnumber[S.top]; cartime = S.cartime[S.top]; S.top--; } //判断栈内是否有该车 int ifthecar(cardata& S, int carnumber) { for (int i = 0; i <= S.top; i++) { if (S.carnumber[i] == carnumber) { return 1; } else { cout << "停车场无车牌号为 " << carnumber << " 的车!" << endl; return 0; } } } //队列********* //初始化队列 void initQueue(Queue& Q) { Q.front = Q.rear = (queue)malloc(sizeof(qNode));//队头指针、队尾指针指向同一空结点 ,队列为空。 if (!Q.front) { exit(-1);//内存分配失败,退出 } Q.front->next = NULL; } //判断队列是否为空 bool emptyQueue(Queue& Q) { if (Q.front == Q.rear) { return false; } else { return true; } } //入队列 void inQueue(Queue& Q, int carnumber, int cartime) { queue p; p = (queue)malloc(sizeof(qNode));//分配一个辅助结点空间 p->carnumber = carnumber; p->cartime = cartime; p->next = NULL; Q.rear->next = p;//队尾指针指向p Q.rear = p;//队尾指针后移一位 position++; } //出队列 void outQueue(Queue& Q, int &carnumber, int &cartime) { queue p; p = (queue)malloc(sizeof(qNode));//分配一个结点空间 p = Q.front->next;//指定一个新的结点指向队头指针指向的结点 carnumber = p->carnumber;//返回结点数据值 cartime = p->cartime; Q.front->next = p->next;//将p指向的下一数据给队头指针,令下一数据前移到队头 if (Q.rear == p) { Q.rear = Q.front;//使队尾指针回到初始位置 } delete(p);//释放p所指结点空间 position--; } //进入和离开******************* //车辆进入停车场 void arrive(cardata& S,Queue& Q, int carnumber, int cartime) { if (!stackfull(S)) { push(S, carnumber, cartime);//进入停车场 cout << "车牌号是 " << carnumber << " 的车停在停车场的位置是 " << S.top + 1 << endl; } else { inQueue(Q, carnumber, cartime);//进入便道 cout << "车牌号是 " << carnumber << " 的车在便道的位置是 " << position << endl; } } //车辆离开停车场 void live(cardata& S, cardata& W, Queue& Q, int carnumber, int cartime, int fee) { int y2 = 0;//车辆是否可以直接驶离栈,需保证车辆后方没有车。 int leaveTime = cartime; for (int j = S.top; j >= 0; j--) { if (!ifthecar(S,carnumber)) { break; } if (ifthecar(S, carnumber))//未找到该车,将该车后面的车移入临时栈中 { pop(S, carnumber, cartime); push(W, carnumber, cartime); if (S.top == 0)//停车场只有一辆车,跳出 { y2 = 1; break; } } else { y2 = 1; break; } } if (y2) { //找到了该车 pop(S, carnumber, cartime);//该车离开停车场 cout << "车牌号是 " << carnumber << " 的车离开停车场,停留时间是:" << (leaveTime - cartime) << "小时,共花费了 " << fee * (leaveTime - cartime) << " 元。" << endl; //将临时栈里的车放进停车场 while (stackempty(W)) { pop(W, carnumber, cartime); push(S, carnumber, cartime); } //如果便道上有车,进停车场 if (emptyQueue(Q)) { outQueue(Q, carnumber, cartime); push(S, carnumber, cartime); } } } //主函数******************* int main() { //定义所需变量,栈,以及队列 int carnumber,cartime,n, fee;//n停车场容量,fee每小时停车费 char ch; cardata S, W;//S指停车场,W指临时栈 Queue Q;//队列(便道) //输入变量 cout << "请输入停车场最大容量(/小时)以及车在停车场每小时的费用(/元):" << endl; cin >> n >> fee; //初始化停车场 initStack(S, n); initStack(W, n); //初始化便道 initQueue(Q); cout << "请输入车的状态(A进站/D出站),车牌号和时间(进站时间/出站时间):" << endl; cin >> ch >> carnumber >> cartime; while(ch != 'E' && time != 0) { if (ch == 'A')//进入 { arrive(S, Q, carnumber, cartime); } else if (ch == 'D')//离开 { live(S,W,Q, carnumber, cartime,fee); } else { printf("请输入正确的编号,A是进库,D是出库!\n"); } cin >> ch >> carnumber >> cartime; } return 0; }
运行结果图:
一 设计要求
1.1 问题描述:设停车场是一个可停放n辆车的狭长通道,且只有一个大门可供汽车进出。汽车在停车常内按车辆到达时间的先后顺序,依次由北向南排列(大门在最南端,最先到达的第1辆车停放在车场的最北端),若车场内以停满n辆汽车,则后来的汽车只能在门外的便道上候车,一旦有车开走,则排在便道上的第一辆车即可开入;当停车场内某辆车要离开时,在它之后进入的车辆必须先退出车厂为它让路,待该辆车开出大门外,其他车辆再按原次序进入车厂。每辆停放在车场的车在它离开停车场时必须按照它停留的时间长短缴纳费用。试为停车场编制按上述要求进行管理的模拟程序。
1.2 基本要求:以栈模拟停车场,以队列模拟车场外的便道,按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项:汽车“到达”或“离去”信息、车牌号以及到达或离开时间。对每一组输入数据进行操作后的输出信息为:若是车辆到达,则输出汽车在停车场内或便道上的停车位置;若是车辆离开,则输出汽车在停车场内停留的时间和应缴纳费用。栈以顺序结构实现,队列以链表结构实现。
1.3 测试数据:设n=2,输入(A,1,5),(A,2,10),(D,1,5),(A,3,20),(A,4,25),(A,5,30),(D,4,40),(E,0,0)。其中A表示到达,D表示离开,E表示输入结束。
1.4 实现提示:需另设一个栈,临时停放为给离去的汽车让路,而从停车场退出来的汽车,也用顺序存储结构存储,便道用队列实现。
二 思路分析
因为停车场中的车辆离开时,其后面的车辆要全部暂时驶离停车场,符合栈先进后出的特点。暂时驶离停车场的车辆之后要按照顺序进入停车场,于是再另外建立一个栈,用于存放临时驶离的车辆,这样暂时驶离的车辆回到停车场时还是原来的的顺序。而便道使用队列,是因为其先进先出的特点,保证先到的车辆可以先进入停车场。
流程图:
三 设计流程
第一步定义栈和队列的结构
typedef struct CarData { char ch;//车辆的识别符,到达or离去 int cartime[100];//车辆停车时间 int carnumber[100];//车辆车牌号 int top; int n;//容量 }cardata; //队列 typedef struct qNode { int carnumber; int cartime; struct qNode* next; }qNode, * queue; typedef struct { queue front; queue rear; }Queue;
2.2第二步编写栈的基本处理,包括初始化栈,判断栈是否为空,判断栈是否为满,入栈和出栈
//初始化栈 void initStack(cardata &S, int n) { S.top = -1; S.n = n; } //判断栈是否为空 int stackempty(cardata &S) { if (S.top == -1) return false; else return true; } //判断栈是否为满 int stackfull(cardata &S) { if (S.top == S.n - 1) { return true; } else { return false; } } //入栈 void push(cardata &S, int carnumber, int cartime) { S.top++; S.carnumber[S.top] = carnumber; S.cartime[S.top] = cartime; } //出栈 void pop(cardata& S, int &carnumber, int &cartime) { carnumber = S.carnumber[S.top]; cartime = S.cartime[S.top]; S.top--; }
第三步编写队列的基本操作,包括队列的初始化,判断队列是否为空,入队列和出队列。
//初始化队列 void initQueue(Queue& Q) { Q.front = Q.rear = (queue)malloc(sizeof(qNode));//队头指针、队尾指针指向同一空结点 ,队列为空。 if (!Q.front) { exit(-1);//内存分配失败,退出 } Q.front->next = NULL; } //判断队列是否为空 bool emptyQueue(Queue& Q) { if (Q.front == Q.rear) { return false; } else { return true; } } //入队列 void inQueue(Queue& Q, int carnumber, int cartime) { queue p; p = (queue)malloc(sizeof(qNode));//分配一个辅助结点空间 p->carnumber = carnumber; p->cartime = cartime; p->next = NULL; Q.rear->next = p;//队尾指针指向p Q.rear = p;//队尾指针后移一位 position++; } //出队列 void outQueue(Queue& Q, int &carnumber, int &cartime) { queue p; p = (queue)malloc(sizeof(qNode));//分配一个结点空间 p = Q.front->next;//指定一个新的结点指向队头指针指向的结点 carnumber = p->carnumber;//返回结点数据值 cartime = p->cartime; Q.front->next = p->next;//将p指向的下一数据给队头指针,令下一数据前移到队头 if (Q.rear == p) { Q.rear = Q.front;//使队尾指针回到初始位置 } delete(p);//释放p所指结点空间 position--; }
第四步,自定义几个所需的函数,包括判断停车场内是否有该车,车辆进入停车场和车辆驶离停车场。
//判断停车场内是否有该车 int ifthecar(cardata& S, int carnumber) { for (int i = 0; i <= S.top; i++) { if (S.carnumber[i] == carnumber) { return 1; } else { cout << "停车场无车牌号为 " << carnumber << " 的车!" << endl; return 0; } } } //车辆进入停车场 void arrive(cardata& S,Queue& Q, int carnumber, int cartime) { if (!stackfull(S)) { push(S, carnumber, cartime);//进入停车场 cout << "车牌号是 " << carnumber << " 的车停在停车场的位置是 " << S.top + 1 << endl; } else { inQueue(Q, carnumber, cartime);//进入便道 cout << "车牌号是 " << carnumber << " 的车在便道的位置是 " << position << endl; } } //车辆离开停车场 void live(cardata& S, cardata& W, Queue& Q, int carnumber, int cartime, int fee) { int y2 = 0;//车辆是否可以直接驶离栈,需保证车辆后方没有车。 int leaveTime = cartime; for (int j = S.top; j >= 0; j--) { if (!ifthecar(S,carnumber)) { break; } if (ifthecar(S, carnumber))//未找到该车,将该车后面的车移入临时栈中 { pop(S, carnumber, cartime); push(W, carnumber, cartime); if (S.top == 0)//停车场只有一辆车,跳出 { y2 = 1; break; } } else { y2 = 1; break; } } if (y2) { //找到了该车 pop(S, carnumber, cartime);//该车离开停车场 cout << "车牌号是 " << carnumber << " 的车离开停车场,停留时间是:" << (leaveTime - cartime) << "小时,共花费了 " << fee * (leaveTime - cartime) << " 元。" << endl; //将临时栈里的车放进停车场 while (stackempty(W)) { pop(W, carnumber, cartime); push(S, carnumber, cartime); } //如果便道上有车,进停车场 if (emptyQueue(Q)) { outQueue(Q, carnumber, cartime); push(S, carnumber, cartime); } } }
最后,定义主函数即可。
int main() { //定义所需变量,栈,以及队列 int carnumber,cartime,n, fee;//n停车场容量,fee每小时停车费 char ch; cardata S, W;//S指停车场,W指临时栈 Queue Q;//队列(便道) //输入变量 cout << "请输入停车场最大容量(/小时)以及车在停车场每小时的费用(/元):" << endl; cin >> n >> fee; //初始化停车场 initStack(S, n); initStack(W, n); //初始化便道 initQueue(Q); cout << "请输入车的状态(A进站/D出站),车牌号和时间(进站时间/出站时间):" << endl; cin >> ch >> carnumber >> cartime; while(ch != 'E' && time != 0) { if (ch == 'A')//进入 { arrive(S, Q, carnumber, cartime); } else if (ch == 'D')//离开 { live(S,W,Q, carnumber, cartime,fee); } else { printf("请输入正确的编号,A是进库,D是出库!\n"); } cin >> ch >> carnumber >> cartime; } return 0; }