数据结构有关栈的题目
3.2 某商场有一个100个车位的停车场，当车位未满时，车辆可以进入；当车位已满时，车辆需排队等待，当有车辆离开后，等待的车辆才能进入。要求实现车辆进入和离开停车场的功能，并可以显示停车场内的车辆信息。
3.3 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。
3.4 迷宫求解：用二维矩阵表示迷宫，自动生成或者直接输入迷宫的格局，确定迷宫是否能走通，如果能走通，输出行走路线。
解答：
第3.2题解答：
思路：停车场我采用了顺序表的存储方式，等待的车辆需要用到队列的算法，先入先出，后入后出，对于进入，先判断停车场是否有空位，若无则入列等待，每当有车离开时，队列的头位车辆自动进入停车场。下面是详细的代码：
//main.h
#define MAIN_H_INCLUDED
#define MAX 100
#define QueueSize 30
typedef struct {
char data[50];
int num;
}Parking;
typedef struct {
//存储空间基址
Parking *elem;
//表中的元素个数
int length;
//表容量的大小
int listsize;
}SqList;
//构造排队单链表；
typedef struct QNode {
char data[50];
struct QNode *next;
}QNode, *QueuePtr;
//定义队列；
typedef struct {
QueuePtr front;
QueuePtr rear;
}Carqueue;
//初始化停车场；
void InitList_Sq(SqList &L);
//控制台打印输出逆置后的顺序表元素(遍历函数)；
void Display(Carqueue &Q, SqList &L);
//构造一个空队列；
void InitQueue(Carqueue &Q);
//判断是否为空队列；
int IsEmpty(Carqueue &Q);
//插入元素e为队列新的队尾元素；
void EnQueue(Carqueue &Q, char &c);
//若队列不为空，则删除Q的队头元素；
int DeQueue(Carqueue &Q);
//车辆进入；
void EnCar(Carqueue &Q, SqList &L);
//车辆离开；
void DeCar(Carqueue &Q, SqList &L);
void menu();
#endif // MAIN_H_INCLUDED
//parking.cpp
#include"main.h"
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include <string>
//创建一个新的顺序表
void InitList_Sq(SqList &L)
{
//分配存储空间基址，初始化数组元素个数以及容量大小
L.elem = (Parking*)malloc(MAX * sizeof(Parking));
L.length = 0;
for (int i = 0; i < MAX; i++) {
L.elem[i].num = i + 1;
strcpy(L.elem[i].data,"0");
}
}
//判断是否为空队列；
int IsEmpty(Carqueue &Q)
{
return Q.front == Q.rear;
}
//构造一个空队列；
void InitQueue(Carqueue &Q)
{
Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));
if (!Q.front)
exit(0);
Q.front->next = NULL;
}
//插入元素e为队列新的队尾元素；
void EnQueue(Carqueue &Q, char &c)
{
QueuePtr p = (QueuePtr)malloc(sizeof(QNode));
if (!p)
exit(0);
strcpy(p->data , &c);
if (Q.front == Q.rear&&Q.rear->next == NULL)
{
Q.front = Q.rear = p;
}
else {
Q.rear->next = p;
Q.rear = Q.rear->next;
Q.rear->next = NULL;
}
}
//若队列不为空，则删除Q的队头元素；
int DeQueue(Carqueue &Q)
{
if (Q.front == Q.rear)
return 0;
QueuePtr p = Q.front;
//e=p->data;
Q.front = p->next;
if (Q.rear == p)Q.rear = Q.front;
free(p);
return 1;
}
//车辆进入；
void EnCar(Carqueue &Q, SqList &L)
{
char c[50];
printf("请输入车牌号:\n");
scanf("%s", &c);
if (L.length < MAX)
{
if (IsEmpty(Q)) {
strcpy(L.elem[L.length].data, c);
L.length++;
}
else {
for (int i = 0; i < L.length; i++) {
if (strcmp(L.elem[i].data,"0")==0) {
strcpy(L.elem[i].data,Q.front->data);
L.length++;
DeQueue(Q);
break;
}
}
}
}
else {
EnQueue(Q, *c);
printf("进入排队队列\n");
}
}
//车辆离开；
void DeCar(Carqueue &Q, SqList &L)
{
printf("请输入将离开的车的车牌号：\n");
char c[50];
scanf("%s", &c);
for (int i = 0; i < L.length; i++)
{
if (strcmp(L.elem[i].data, c) == 0)
{
if (IsEmpty(Q)) {
strcpy(L.elem[i].data, "0");
}
else {
strcpy(L.elem[i].data, Q.front->data);
DeQueue(Q);
}
}
}
}
void Display(Carqueue &Q, SqList &L)
{
printf("------------停车场车位情况------------\n");
printf("车位\t车牌号\n");
for (int i = 0; i < L.length; i++)
{
printf("%d\t%s\n", L.elem[i].num, L.elem[i].data);
}
printf("------------排队车位情况------------\n");
printf("序号\t车牌号\n");
int i = 1;
for (QueuePtr index = Q.front; index != NULL; index=index->next)
{
printf("%d\t%s\n", i,index->data);
i++;
}
}
void menu()
{
printf("停车场管理系统菜单\n");
printf("1.新车辆进入\n");
printf("2.车辆离开\n");
printf("3.显示停车场内信息\n");
printf("4.退出系统\n");
}
//main.cpp
#include <iostream>
#include"main.h"
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include <string>
using namespace std;
int main()
{
int choice;
SqList nelist;
Carqueue Qu;
InitList_Sq(nelist);
InitQueue(Qu);
do {
menu();
scanf_s("%d", &choice);
switch (choice) {
case 1:
EnCar(Qu, nelist);
break;
case 2:
DeCar(Qu, nelist);
break;
case 3:
Display(Qu, nelist);
case 4:
break;
}
} while (choice != 4);
return 0;
}
程序执行结果如下：(由于100个车位演示起来不方便，下面代码执行的是停车场共有5个车位时的情况)
第3.3题解答：
思路：设置一个队列长度为4的循环队列，先将前四个数字初始化设成0，0，0，1，通过不断地出队入队计算斐波那契数列的值，判断直到FN大于200结束，具体代码如下：
//main.cpp
#include<stdio.h>
#include<stdlib.h>
#define kk 4
#define max 200
struct queue
{
int elem[kk]; int rear;
} cq; // rear指向队尾元素
int f[100], n; //用数组f存放所求序列中的所有元素
void fb(int k)
{
int i, j;
for (i = 0; i <= k - 2; i++) { f[i] = 0; cq.elem[i] = 0; } //为前k-1个元素赋初值0，并放入队列cq
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 \n", f[i]);
system("pause");
}
代码结果运行如下：
第3.4题解答：
思路：使用二维数组来表示迷宫，通过用户输入命令行参数判断迷宫的行数和列数，在命令行窗口直接输入迷宫的格局，通过将其他的位置设置成障碍防止迷宫越界，在走过的地方，或者死路留下标记，防止再次踏入，通过出栈压栈的操作方式寻找正确的路径，栈的操作与之前操作类似，主要是实现对判断迷宫走向函数功能，以及记录路径功能的实现，最后输出得到的结果图，详细的代码如下：
//maze.h
#ifndef MAZE_H_INCLUDED
#define MAZE_H_INCLUDED
#define ok 1
#define error 0
#define STACK_INIT_SIZE 100 //存储空间初始分配量
#define STACKINCREMENT 10// 存储空间分配增量
typedef int Status;
//迷宫坐标；
typedef struct
{
int x;
int y;
}PosType;
//迷宫大小和类型；
typedef struct
{
int row, col;
int a[50][50];
}MazeType;
//栈的元素类型
typedef struct
{
//通道块在路径上的序号
int numb;
//通道块在迷宫中的"坐标位置"
PosType locat;
//从此通道块走向下一个通道块的方向
int nexd;
}SElemType;
//栈结构体
typedef struct
{
SElemType *base;
SElemType *top;
int Stacksize;
}SqStack;
//初始化栈
Status InitStack(SqStack &S);
//压栈操作
Status Push(SqStack &S, SElemType e);
//若栈不空，则删除S的栈顶元素，用e返回其值
Status Pop(SqStack &S, SElemType &e);
//判断栈是否为空
bool StackEmpty(SqStack S);
//初始化迷宫
Status InitMaze(MazeType &maze);
//判断道路的可行性
bool Pass(MazeType maze, PosType curpos);
//留下足迹
Status Sign_Locate(MazeType &maze, PosType curpos);
//创造一个栈元素
SElemType NewElem(int step, PosType pos, int nexd);
//方向判断
PosType Chose_Direction(PosType curpos, int nexd);
//寻找路径
Status Search_Load(MazeType &maze, PosType start, PosType end);
//判断是否结束
bool IsEnd(PosType pos1, PosType pos2);
//打印输出
Status Display_Maze(MazeType maze);
#endif // MAZE_H_INCLUDED
//maze.cpp
#include <stdio.h>
#include <stdlib.h>
#include"maze.h"
//初始化栈
Status InitStack(SqStack &S)
{
S.base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType));
if (!S.base) exit(-1);
S.top = S.base;
S.Stacksize = STACK_INIT_SIZE;
return ok;
}
//插入元素e为新的栈顶元素
Status Push(SqStack &S, SElemType e)
{
if (S.top - S.base >= S.Stacksize)
{
S.base = (SElemType *)realloc(S.base, (S.Stacksize + STACKINCREMENT) * sizeof(SElemType));
if (!S.base) exit(-1);
S.top = S.base + S.Stacksize;
S.Stacksize += STACKINCREMENT;
}
*S.top++ = e;
return ok;
}
//若栈不空，则删除S的栈顶元素，用e返回其值
Status Pop(SqStack &S, SElemType &e)
{
if (S.top == S.base) return error;
e = *--S.top;
return ok;
}
//判断栈是否为空
bool StackEmpty(SqStack S)
{
if (S.top == S.base)
return ok;
else return error;
}
//初始化迷宫
Status InitMaze(MazeType &maze)
{
int i, j;
for (j = 0; j < maze.col + 2; j++)
maze.a[0][j] = 1;
for (i = 1; i < maze.row + 1; i++)
{
maze.a[i][0] = 'x';
maze.a[i][maze.col + 1] = 1;
for (int j = 1; j < maze.col + 1; j++)
scanf("%d", &maze.a[i][j]);
}
for (j = 0; j < maze.col + 2; j++)
maze.a[maze.row + 1][j] = 1;
return ok;
}
//判断是否可以通过
bool Pass(MazeType maze, PosType curpos)
{
return maze.a[curpos.x][curpos.y] == 0;
}
//留下足迹
Status Sign_Locate(MazeType &maze, PosType curpos)
{
maze.a[curpos.x][curpos.y] = 9;
return ok;
}
//创造一个栈类型的元素
SElemType NewElem(int step, PosType pos, int nexd)
{
SElemType e;
e.numb = step;
e.locat = pos;
e.nexd = nexd;
return e;
}
//判断是否结束
bool IsEnd(PosType pos1, PosType pos2)
{
return pos1.x == pos2.x&&pos1.y == pos2.y;
}
//方向判断
PosType Chose_Direction(PosType curpos, int nexd)
{
PosType pos = curpos;
switch (nexd)
{
case 1:pos.x++; break;//向东
case 2:pos.y++; break;//向南
case 3:pos.x--; break;//向西
case 4:pos.y--; break;//向北
}
return pos;
}
//寻找路径
Status Search_Load(MazeType &maze, PosType start, PosType end)
{
SqStack S;
SElemType e;
InitStack(S);
//设定当前位置为入口位置
PosType curpos = start;
//探索第一步
int curstep = 1;
do {
if (Pass(maze, curpos))
{
//标记走过的位置
Sign_Locate(maze, curpos);
e = NewElem(curstep, curpos, 1);
//压栈
Push(S, e);
if (IsEnd(curpos, end))
return ok;//达到终点
curpos = Chose_Direction(curpos, 1);
curstep++;
}
//无法通过时
else
{
if (!StackEmpty(S))
{
//Pop(S, e);
while (e.nexd == 4 && !StackEmpty(S))
{
Pop(S, e);
}
if (e.nexd < 4)
{
//改变方向
e.nexd++;
Push(S, e);
curpos = Chose_Direction(e.locat, e.nexd);
}
}
}
} while (!StackEmpty(S));
return error;
}
//打印输出
Status Display_Maze(MazeType maze)
{
int i, j;
for (i = 1; i < maze.row + 1; i++)
{
for (j = 1; j < maze.col + 1; j++)
printf("%d ", maze.a[i][j]);
printf("\n");
}
return ok;
}
//main.cpp
#include"maze.h"
#include <stdio.h>
#include <stdlib.h>
int main()
{
MazeType maze;
printf("--------------二维数组迷宫--------------\n");
printf("请输入需要创建的迷宫的行数和列数:\n");
scanf("%d %d", &maze.row, &maze.col);
printf("请输入迷宫数据，0为通道，1为障碍：\n");
InitMaze(maze);
PosType start, end;
start.x = 1; start.y = 1;
end.x = maze.row; end.y = maze.col;
if (Search_Load(maze, start, end))
{
printf("可得到以下结果（9为路径）\n");
Display_Maze(maze);
}
else
printf("没有找到通路!\n");
system("pause");
return 0;
}