数据结构实验2--栈和队列
本系列文章广泛借鉴了各种教材和博客文章，由于完成时间比较久远，如果有遗漏标注的请联系我补充或删除解答。本文中解答仅供参考学习。
其他章节实验见：分类 - 数据结构 - Loststar’s blog
商场停车场
题目
某商场有一个100个车位的停车场，当车位未满时，等待的车辆可以进入并计时；当车位已满时，必须有车辆离开，等待的车辆才能进入；当车辆离开时计算停留的的时间，并且按照每小时1元收费。
汽车的输入信息格式可以是（进入/离开，车牌号，进入/离开时间），要求可以随时显示停车场内的车辆信息以及收费历史记录。
解答
#include<stdio.h>
#include<time.h>
#include<stdlib.h>
#include<string.h>
#define MAXSPACE 100
#define PRICEPERSECOND 1
typedef struct vehicle //车辆信息
{
char carNumber[8]; //车牌号码
time_t parkTime; //停车时间
}Vehicle;
typedef struct space //车位信息
{
Vehicle carInfo; //车位里停的车
int isParked; //车位状态
}Space;
typedef struct lot //停车场信息
{
Space* allSpace; //所有车位
int emptySpace; //剩余车位数
} Lot;
typedef struct history //收费记录
{
char carNumber[8];
time_t parkTime;
time_t leaveTime;
int price;
struct history *next;
}History;
void printLot(Lot parkingLot)
{
printf("=================================================\n现在时间：%lld\n停车场剩余空位%d个\n", time(NULL), parkingLot.emptySpace);
for (int i = 0; i < MAXSPACE; i++)
{
if (parkingLot.allSpace[i].isParked == 1)
{
printf("---------------------\n车牌：%s\n停车时间：%lld\n", parkingLot.allSpace[i].carInfo.carNumber, parkingLot.allSpace[i].carInfo.parkTime);
}
}
printf("---------------------\n=================================================\n");
}
void printHistory(History *head)
{
History *temp = head;
int i = 1;
if (temp->price != 0)
{
printf("第%d笔，车牌号：%s，收费：%d元\n", 1, temp->carNumber, temp->price);
while (temp->next!=NULL)
{
temp = temp->next;
i++;
printf("第%d笔，车牌号：%s，收费：%d元\n", i, temp->carNumber, temp->price);
}
}
}
Lot parkVehicle(Lot parkingLot)
{
if (parkingLot.emptySpace == 0)
{
printf("车位满，请离开");
return parkingLot;
}
for (int i = 0; i < MAXSPACE; i++)
{
if (parkingLot.allSpace[i].isParked == 0) //找到空车位
{
printf("请输入7位车牌号（例：JA10086）：\n");
scanf("%s", parkingLot.allSpace[i].carInfo.carNumber);
parkingLot.allSpace[i].carInfo.parkTime= time(NULL);
parkingLot.allSpace[i].isParked = 1;
parkingLot.emptySpace--;
printf("现在时间%lld,%s停车成功\n", parkingLot.allSpace[i].carInfo.parkTime,parkingLot.allSpace[i].carInfo.carNumber);
return parkingLot;
}
}
}
Lot leaveVehicle(Lot parkingLot, History* head)
{
if (parkingLot.emptySpace == MAXSPACE)
{
printf("停车场空\n");
return parkingLot;
}
char carNumber[8];
time_t nowTime;
int parkingFee;
printf("请输入7位车牌号（例：JA10086）：\n");
scanf("%s", carNumber);
for (int i = 0; i < MAXSPACE; i++)
{
if (strcmp(parkingLot.allSpace[i].carInfo.carNumber,carNumber)==0)
{
parkingLot.allSpace[i].isParked = 0;
parkingLot.emptySpace++;
nowTime = time(NULL);
parkingFee = PRICEPERSECOND * (nowTime - parkingLot.allSpace[i].carInfo.parkTime);
printf("%s离开成功，收费%d元\n", parkingLot.allSpace[i].carInfo.carNumber, parkingFee);
//储存收费记录
if (head->price == 0)
{
strcpy(head->carNumber, parkingLot.allSpace[i].carInfo.carNumber);
head->parkTime = parkingLot.allSpace[i].carInfo.parkTime;
head->leaveTime = nowTime;
head->price = parkingFee;
}
else
{
History *temp = head;
while (temp->next!=NULL)
{
temp = temp->next;
}
temp->next = (History*)malloc(sizeof(History));
temp = temp->next;
strcpy(temp->carNumber, parkingLot.allSpace[i].carInfo.carNumber);
temp->parkTime = parkingLot.allSpace[i].carInfo.parkTime;
temp->leaveTime = nowTime;
temp->price = parkingFee;
temp->next = NULL;
}
return parkingLot;
}
}
}
void startSystem(Lot parkingLot, History* head)
{
while (true)
{
int i;
printf("1.停车\n2.离开\n3.打印停车场状态\n4.打印收费历史\n");
scanf("%d", &i);
switch (i)
{
case 1:
parkingLot = parkVehicle(parkingLot);
break;
case 2:
parkingLot = leaveVehicle(parkingLot, head);
break;
case 3:
printLot(parkingLot);
break;
case 4:
printHistory(head);
break;
default:
break;
}
}
}
int main()
{
Lot parkingLot;
parkingLot.allSpace = (Space*)malloc(MAXSPACE * sizeof(Space));
parkingLot.emptySpace = MAXSPACE;
for (int i = 0; i < MAXSPACE; i++)
{
parkingLot.allSpace[i].isParked = 0;
}
History* head = (History*)malloc(sizeof(History));
head->price = 0;
head->next = NULL;
startSystem(parkingLot, head);
}运行结果
银行营业厅
题目
某银行营业厅共有6个营业窗口，设有排队系统广播叫号，该银行的业务分为公积金、银行卡、理财卡等三种。公积金业务指定1号窗口，银行卡业务指定2、3、4号窗口，理财卡业务指定5、6号窗口。但如果5、6号窗口全忙，而2、3、4号窗口有空闲时，理财卡业务也可以在空闲的2、3、4号窗口之一办理。
客户领号、业务完成可以作为输入信息，要求可以随时显示6个营业窗口的状态。
解答
#include<stdio.h>
#include<stdlib.h>
int windows[7] = { 0 };
int number = 0; //顾客领取的号码
typedef struct QNode
{
int data;
struct QNode *next;
}QNode;
typedef struct LinkQueue
{
QNode *front;
QNode *rear;
}LinkQueue;
int initQueue(LinkQueue &Q)
{
Q.front = Q.rear = (QNode*)malloc(sizeof(QNode));
if (!Q.front)
{
return -1;
}
Q.front->next = NULL;
return 0;
}
int enQueue(LinkQueue &Q, int data)
{
QNode *p = (QNode*)malloc(sizeof(QNode));
if (!p)
{
return -1;
}
p->data = data;
p->next = NULL;
Q.rear->next = p;
Q.rear = p;
return 0;
}
int deQueue(LinkQueue &Q,int &data)
{
if (Q.front == Q.rear)
{
return -1;
}
QNode *p = Q.front->next;
data = p->data;
Q.front->next = p->next;
if (p == Q.rear)
{
Q.rear = Q.front;
free(p);
}
return 0;
}
int isEmpty(LinkQueue &Q)
{
if (Q.front == Q.rear)
{
return 1;
}
return 0;
}
void print(LinkQueue *Q) //输出队列中的元素
{
QNode *p;
p = Q->front->next; //p结点指向链队列中存放第一个元素的结点
while (p) //沿链队列从队头到队尾的方向依次输出元素的值
{
printf("%d ", p->data);
p = p->next;
}
}
void entryBank(LinkQueue &gjj, LinkQueue &yhk, LinkQueue &lck, LinkQueue &customer1, LinkQueue &customer2, LinkQueue &customer3)
{
int i,data;
printf("请输入要办理的业务：\n1.公积金\n2.银行卡\n3.理财卡\n");
scanf("%d", &i);
number++;
switch (i)
{
case 1:
if (!isEmpty(gjj))
{
deQueue(gjj,data);
windows[data] = 1;
printf("%d号顾客到%d号柜台办理\n", number, data);
}
else
{
enQueue(customer1,number);
printf("%d号顾客到队列1等待\n", number);
}
break;
case 2:
if (!isEmpty(yhk))
{
deQueue(yhk, data);
windows[data] = 1;
printf("%d号顾客到%d号柜台办理\n", number, data);
}
else
{
enQueue(customer2, number);
printf("%d号顾客到队列2等待\n", number);
}
break;
case 3:
if (!isEmpty(lck))
{
deQueue(lck, data);
windows[data] = 1;
printf("%d号顾客到%d号柜台办理\n", number, data);
}
else if(!isEmpty(yhk))
{
deQueue(yhk, data);
windows[data] = 1;
printf("%d号顾客到%d号柜台办理\n", number, data);
}
else
{
enQueue(customer3, number);
printf("%d号顾客到队列3等待\n", number);
}
default:
break;
}
}
void leaveBank(LinkQueue &gjj, LinkQueue &yhk, LinkQueue &lck, LinkQueue &customer1, LinkQueue &customer2, LinkQueue &customer3)
{
int i,number;
printf("请输入办理完成的窗口（1-6）\n");
scanf("%d", &i);
switch (i)
{
case 1:
if (!isEmpty(customer1))
{
deQueue(customer1, number);
printf("%d号顾客到%d号柜台办理\n", number, i);
}
else
{
enQueue(gjj, i);
windows[i] = 0;
}
break;
case 2:
case 3:
case 4:
if (!isEmpty(customer2))
{
deQueue(customer2, number);
printf("%d号顾客到%d号柜台办理\n", number, i);
}
else if (!isEmpty(customer3))
{
deQueue(customer3, number);
printf("%d号顾客到%d号柜台办理\n", number, i);
}
else
{
enQueue(yhk, i);
windows[i] = 0;
}
break;
case 5:
case 6:
if (!isEmpty(customer3))
{
deQueue(customer3, number);
printf("%d号顾客到%d号柜台办理\n", number, i);
}
else
{
enQueue(lck, i);
windows[i] = 0;
}
break;
default:
break;
}
}
void startSystem(LinkQueue &gjj, LinkQueue &yhk, LinkQueue &lck, LinkQueue &customer1, LinkQueue &customer2, LinkQueue &customer3)
{
int i;
printf("请输入顾客行为：\n1.进入\n2.离开\n3.查看窗口状态\n");
scanf("%d", &i);
switch (i)
{
case 1:
entryBank(gjj, yhk, lck, customer1, customer2, customer3);
break;
case 2:
leaveBank(gjj, yhk, lck, customer1, customer2, customer3);
break;
case 3:
for (int j = 1; j < 7; j++)
{
windows[j] ? printf("%d号窗口有人\n", j) : printf("%d号窗口无人\n", j);
}
break;
default:
break;
}
}
int main()
{
LinkQueue gjj, yhk, lck; //窗口队列
LinkQueue customer1, customer2, customer3; //顾客队列
//窗口队列初始化
initQueue(gjj);
enQueue(gjj, 1);
initQueue(yhk);
enQueue(yhk, 2);
enQueue(yhk, 3);
enQueue(yhk, 4);
initQueue(lck);
enQueue(lck, 5);
enQueue(lck, 6);
//窗口队列初始化完毕
//顾客队列初始化
initQueue(customer1);
initQueue(customer2);
initQueue(customer3);
//顾客队列初始化完毕
while (true)
{
startSystem(gjj, yhk, lck, customer1, customer2, customer3);
}
}运行结果
4阶斐波那契序列
题目
4阶斐波那契序列如下：f0=f1=f2=0, f3=1,…,fi=fi-1+fi-2+fi-3+fi-4，
利用容量为k=4的循环队列，构造序列的前n+1项（f0, f1 , f2 ,… fn ），要求满足fn ≤200而fn+1 >200。
解答
#include<stdio.h>
#define kk 4
#define max 200
struct queue
{
int elem[kk];
int rear;
}cq;
int f[100], n;
void fb(int k)
{
int i, j;
for (i = 0; i <= k - 2; i++)
{
f[i] = 0; cq.elem[i] = 0;
}
cq.elem[k - 1] = f[k - 1] = 1; //为第k个元素赋值，并放入队列cq
cq.rear = k - 1;
n = k;
while (cq.elem[cq.rear] < max) //利用循环队列依次求f[n]
{
f[n] = 0;
for (j = 0; j < k; j++)
{
f[n] = f[n] + cq.elem[j];
}
cq.rear = (cq.rear + 1) % k;
cq.elem[cq.rear] = f[n];
n++;
} //利用循环队列依次求f[n]
if (cq.elem[cq.rear] > max)
n = n - 2;
else
n = n - 1;
}
int main()
{
int i;
fb(kk);
for (i = 0; i <= n; i++)
printf(" %d ", f[i]);
return 0;
}运行结果
八皇后问题
题目
八皇后问题：设8皇后问题的解为 (x1, x2, x3, …,x8), 约束条件为：在8x8的棋盘上，其中任意两个xi 和xj不能位于棋盘的同行、同列及同对角线。要求用一位数组进行存储，输出所有可能的排列。
解答
#include<stdio.h>
#include<math.h>
#define N 8
int count = 0, position[N];
int isLegal(int i, int j) //检查(i,j)上能否放棋子
{
int j1 = j,i1 = i,ok1 = 1; //检查第i行上能否放棋子
while ((j1 > 1) && ok1)
{
j1--;
ok1 = position[j1] != i;
}
j1 = j;
i1 = i; //检查对角线上能否放棋子
while ((j1 > 1) && (i1 > 1) && ok1)
{
j1--;
i1--;
ok1 = position[j1] != i1;
}
j1 = j;
i1 = i; //检查另一对角线上能否放棋子
while ((j1 > 1) && (i1 < N) && ok1)
{
j1--;
i1++;
ok1 = position[j1] != i1;
}
return ok1;
}
int queen(int j) //从第j列开始逐个试探
{
if (j > N)
{
count++;
printf("count=%d ", count);
for (int i = 1; i <= N; i++)
printf(" %d", position[i]);
printf("\n");
}
else
for (int i = 1; i <= N; i++)
if (isLegal(i,j)) //检查(i,j)上能否放棋子
{
position[j] = i; //在(i,j)上放一个棋子
queen(j + 1);
}
return 0;
}
int main()
{
queen(1);
}运行结果
一共92种，比较多，就不截图了
count=1 1 5 8 6 3 7 2 4
count=2 1 6 8 3 7 4 2 5
count=3 1 7 4 6 8 2 5 3
count=4 1 7 5 8 2 4 6 3
count=5 2 4 6 8 3 1 7 5
count=6 2 5 7 1 3 8 6 4
count=7 2 5 7 4 1 8 6 3
count=8 2 6 1 7 4 8 3 5
count=9 2 6 8 3 1 4 7 5
count=10 2 7 3 6 8 5 1 4
count=11 2 7 5 8 1 4 6 3
count=12 2 8 6 1 3 5 7 4
count=13 3 1 7 5 8 2 4 6
count=14 3 5 2 8 1 7 4 6
count=15 3 5 2 8 6 4 7 1
count=16 3 5 7 1 4 2 8 6
count=17 3 5 8 4 1 7 2 6
count=18 3 6 2 5 8 1 7 4
count=19 3 6 2 7 1 4 8 5
count=20 3 6 2 7 5 1 8 4
count=21 3 6 4 1 8 5 7 2
count=22 3 6 4 2 8 5 7 1
count=23 3 6 8 1 4 7 5 2
count=24 3 6 8 1 5 7 2 4
count=25 3 6 8 2 4 1 7 5
count=26 3 7 2 8 5 1 4 6
count=27 3 7 2 8 6 4 1 5
count=28 3 8 4 7 1 6 2 5
count=29 4 1 5 8 2 7 3 6
count=30 4 1 5 8 6 3 7 2
count=31 4 2 5 8 6 1 3 7
count=32 4 2 7 3 6 8 1 5
count=33 4 2 7 3 6 8 5 1
count=34 4 2 7 5 1 8 6 3
count=35 4 2 8 5 7 1 3 6
count=36 4 2 8 6 1 3 5 7
count=37 4 6 1 5 2 8 3 7
count=38 4 6 8 2 7 1 3 5
count=39 4 6 8 3 1 7 5 2
count=40 4 7 1 8 5 2 6 3
count=41 4 7 3 8 2 5 1 6
count=42 4 7 5 2 6 1 3 8
count=43 4 7 5 3 1 6 8 2
count=44 4 8 1 3 6 2 7 5
count=45 4 8 1 5 7 2 6 3
count=46 4 8 5 3 1 7 2 6
count=47 5 1 4 6 8 2 7 3
count=48 5 1 8 4 2 7 3 6
count=49 5 1 8 6 3 7 2 4
count=50 5 2 4 6 8 3 1 7
count=51 5 2 4 7 3 8 6 1
count=52 5 2 6 1 7 4 8 3
count=53 5 2 8 1 4 7 3 6
count=54 5 3 1 6 8 2 4 7
count=55 5 3 1 7 2 8 6 4
count=56 5 3 8 4 7 1 6 2
count=57 5 7 1 3 8 6 4 2
count=58 5 7 1 4 2 8 6 3
count=59 5 7 2 4 8 1 3 6
count=60 5 7 2 6 3 1 4 8
count=61 5 7 2 6 3 1 8 4
count=62 5 7 4 1 3 8 6 2
count=63 5 8 4 1 3 6 2 7
count=64 5 8 4 1 7 2 6 3
count=65 6 1 5 2 8 3 7 4
count=66 6 2 7 1 3 5 8 4
count=67 6 2 7 1 4 8 5 3
count=68 6 3 1 7 5 8 2 4
count=69 6 3 1 8 4 2 7 5
count=70 6 3 1 8 5 2 4 7
count=71 6 3 5 7 1 4 2 8
count=72 6 3 5 8 1 4 2 7
count=73 6 3 7 2 4 8 1 5
count=74 6 3 7 2 8 5 1 4
count=75 6 3 7 4 1 8 2 5
count=76 6 4 1 5 8 2 7 3
count=77 6 4 2 8 5 7 1 3
count=78 6 4 7 1 3 5 2 8
count=79 6 4 7 1 8 2 5 3
count=80 6 8 2 4 1 7 5 3
count=81 7 1 3 8 6 4 2 5
count=82 7 2 4 1 8 5 3 6
count=83 7 2 6 3 1 4 8 5
count=84 7 3 1 6 8 5 2 4
count=85 7 3 8 2 5 1 6 4
count=86 7 4 2 5 8 1 3 6
count=87 7 4 2 8 6 1 3 5
count=88 7 5 3 1 6 8 2 4
count=89 8 2 4 1 7 5 3 6
count=90 8 2 5 3 1 7 4 6
count=91 8 3 1 6 2 5 7 4
count=92 8 4 1 3 6 2 7 5数据结构实验2--栈和队列
https://blog.loststar.tech/posts/959bb1f8/