数据结构（C语言）代码实现（九）——迷宫探路表达式求值

2024-02-28 17:52
文章标签 语言 代码 实现 数据结构 求值 表达式 迷宫 探路

本文主要是介绍数据结构（C语言）代码实现（九）——迷宫探路表达式求值，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

参考资料

迷宫探路

顺序栈头文件SqStack.h

顺序栈函数实现SqStack.cpp

迷宫探路主函数

表达式求值

链式顺序栈头文件LinkStack.h 

链式顺序栈函数实现LinkStack.cpp

表达式求值主函数

测试结果

参考资料

数据结构严蔚敏版

2021-9-22【数据结构/严蔚敏】【顺序栈&链式栈&迷宫求解&表达式求值】【代码实现算法3.1-3.5】_数据结构表达式求值代码严老师-CSDN博客

栈和队列-数据结构与算法(C语言版)_调用pop(&s,&e)函数,让队头数据出队,赋值给参数e,printf输出e-CSDN博客

迷宫探路

顺序栈头文件SqStack.h

#pragma once
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;//Status是函数的类型，其值是函数结果状态代码/*宏函数*/
//函数暂停一段时间
#define Wait(x)\{\double _Loop_Num_;\for(_Loop_Num_=0.01; _Loop_Num_<=100000.0*x; _Loop_Num_+=0.01)\;\}//设立一个空循环 typedef struct {int x;int y;
}PosType;//坐标位置
typedef struct {int ord;      //通道块在路径上的“序号”PosType seat; //通道块在迷宫中的“坐标位置”int di;       //从此通道块走向下一通道块的“方向”
}SElemType;//-----栈的顺序存储表示-----
#define STACK_INIT_SIZE 100  //存储空间初始分配量
#define STACKINCREMENT 10    //存储空间分配增量
typedef struct SqStack {SElemType* base;//在栈构造之前和销毁之后，base的值为NULLSElemType* top; //栈顶指针int stacksize;  //当前已分配的存储空间，以元素为单位
}SqStack;
//-----基本操作的函数原型说明-----
Status InitStack(SqStack& S);
//构造一个空栈S
Status DestroyStack(SqStack& S);
//销毁栈S，S不再存在
Status ClearStack(SqStack& S);
//把S置为空栈
Status StackEmpty(SqStack S);
//若栈S为空栈，则返回TRUE,否则返回FALSE
int StackLength(SqStack S);
//返回S的元素个数，即栈的长度
Status GetTop(SqStack S, SElemType& e);
//若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR
Status Push(SqStack& S, SElemType e);
//插入元素e为新的栈顶元素
Status Pop(SqStack& S, SElemType& e);
//若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR
Status StackTraverse(SqStack S, void(*visit)(SElemType));
//从栈顶到栈底依次对栈中每个元素调用函数visit()。一旦visit()失败，则操作失败

顺序栈函数实现SqStack.cpp

#include "SqStack.h"//-----基本操作的函数算法描述（部分）-----
Status InitStack(SqStack& S) {//构造一个空栈SS.base = (SElemType*)malloc(STACK_INIT_SIZE * sizeof(SElemType));if (!S.base)exit(OVERFLOW);//存储分配失败，警告C6011S.top = S.base;S.stacksize = STACK_INIT_SIZE;return OK;
}Status DestroyStack(SqStack& S) {free(S.base);S.top = S.base = NULL;S.stacksize = 0;return OK;
}Status ClearStack(SqStack& S) {if (!S.base)return ERROR;S.top = S.base;return OK;
}Status StackEmpty(SqStack S) {if (S.base == S.top)return OK;return ERROR;
}int StackLength(SqStack s) {if (!s.base)return ERROR;return (int)(s.top - s.base);
}Status GetTop(SqStack s, SElemType& e) {//若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERRORif (s.base == s.top)return ERROR;e = *(s.top - 1);return OK;
}Status Push(SqStack& s, SElemType e) {//插入元素e为新的栈顶元素if (!s.base)return ERROR;if (s.top - s.base >= s.stacksize) {//栈满，追加存储空间s.base = (SElemType*)realloc(s.base, (s.stacksize + STACKINCREMENT) * sizeof(SElemType));if (!s.base)exit(_OVERFLOW);//存储分配失败s.top = s.base + s.stacksize;s.stacksize += STACKINCREMENT;}*s.top++ = e;//*s.top=e; s.top++;return OK;
}Status Pop(SqStack& s, SElemType& e) {//若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERRORif (!s.base || s.top == s.base) return ERROR;e = *--s.top;//--s.top; e=*s.top;return OK;
}Status StackTraverse(SqStack s, void (*visit)(SElemType)) {SElemType* p = s.base;if (!s.base)return ERROR;while (p < s.top)visit(*p++);printf("\n");return OK;
}

迷宫探路主函数

#include "SqStack.h"#define MAXSIZE 15
#define X 4
#define SleepTime 3
/* 迷宫类型定义 */
typedef enum {Wall,       // 外墙Obstacle,   // 迷宫内部障碍Way,        // 通路Impasse,    // 死胡同East, South, West, North //当前探索方向：东南西北
} CellType;typedef int MazeType[MAXSIZE][MAXSIZE];//用到的函数
SElemType Construct(int ord, PosType seat, int di);
//创建通道块信息并返回，序号、坐标位置和下一个访问方向
PosType NextPos(PosType seat, int di);
//获得下一个应当探索的位置
Status MazePath(MazeType maze, PosType start, PosType end);
//迷宫寻路主函数，第一个变量类型为int*，是地图的首地址。
void InitMaze(MazeType maze, PosType& start, PosType& end);
//初始化迷宫，start和end分别为迷宫的入口坐标和出口坐标
Status Pass(MazeType maze, PosType seat);
//判断当前位置是否为首次探索
void FootPrint(MazeType maze, PosType seat);
//留下初始访问足迹，初始访问足迹即向东访问
void MarkPrint(MazeType maze, PosType seat, int mark);
//留下标记+绘制迷宫
Status Equals(PosType a, PosType b);
//比较两个结构体
void PaintMaze(MazeType maze);
//绘制迷宫，以图形的方式呈现迷宫当前的状态Status MazePath(MazeType maze, PosType start, PosType end) {//若迷宫maze中存在从入口start到出口end的通道，则求得一条存放在栈中//（从栈底到栈顶），并返回TRUE；否则返回FALSESqStack S;       //存储探索过的通道块PosType curpos;  //当前位置SElemType e;     //当前通道块信息int curstep;     //当前通道块序号InitStack(S);curpos = start;//设定“当前位置”为“入口位置”curstep = 1;            //探索第一步do {if (Pass(maze, curpos)) {//当前位置可以通过，即是未曾走到过的通道块FootPrint(maze, curpos);//留下足迹e = Construct(curstep, curpos, East);Push(S, e);             //加入路径if (Equals(curpos, end) == TRUE) {printf("\n寻路成功\n\n");return TRUE;        //到达终点(出口)}curpos = NextPos(curpos, East);//下一位置是当前位置的东邻curstep++;              //探索下一步}else {//当前位置不能通过if (!StackEmpty(S)) {Pop(S, e);while (e.di == North && !StackEmpty(S)) {MarkPrint(maze, e.seat, Impasse);Pop(S, e);}if (e.di < North) {e.di++;MarkPrint(maze, e.seat, e.di);Push(S, e);curpos = NextPos(e.seat, e.di);//不需要curstep++，因为还是上次入栈的位置块}}}} while (!StackEmpty(S));printf("\n寻路失败！！\n\n");return FALSE;
}//初始化一个规模为N*N迷宫
//start和end分别为迷宫的入口坐标和出口坐标
//注：教材中无此操作，但该操作是必须存在的
void InitMaze(MazeType maze, PosType& start, PosType& end) {int i, j, tmp;srand((unsigned)time(NULL));//用系统时间做随机数种子for (i = 0;i < MAXSIZE;i++) {for (j = 0;j < MAXSIZE;j++) {//边缘部分设置围墙if (i == 0 || j == 0 || i == MAXSIZE - 1 || j == MAXSIZE - 1) {maze[i][j] = Wall;}else {//生成随机数[0,X-1]填充迷宫tmp = rand() % X;//1/X之一的概率生成障碍，否则生成通路块if (tmp == 0)maze[i][j] = Obstacle;elsemaze[i][j] = Way;}}}//迷宫内部设障完毕start.x = 1;start.y = 0;end.x = MAXSIZE - 2;end.y = MAXSIZE - 1;maze[1][0] = maze[MAXSIZE - 2][MAXSIZE - 1] = Way;//显示迷宫的初始状态PaintMaze(maze);
}Status Pass(MazeType maze, PosType seat) {int x = seat.x;int y = seat.y;if (x<0 || y<0 || x>MAXSIZE - 1 || y>MAXSIZE - 1)return FALSE;if (maze[x][y] != Way)return FALSE;return TRUE;
}PosType NextPos(PosType seat, int di) {PosType tmp = seat;switch (di) {case East:tmp.y++;//向东break;case South:tmp.x++;//向东break;case West:tmp.y--;//向东break;case North:tmp.x--;//向东break;}return tmp;
}void FootPrint(MazeType maze, PosType seat) {MarkPrint(maze, seat, East);
}void MarkPrint(MazeType maze, PosType seat, int mark) {maze[seat.x][seat.y] = mark;PaintMaze(maze);
}SElemType Construct(int ord, PosType seat, int di) {SElemType e;e.di = di;e.seat = seat;e.ord = ord;return e;
}Status Equals(PosType a, PosType b) {if (a.x == b.x && a.y == b.y)return TRUE;elsereturn FALSE;
}
/** 绘制迷宫* 以图形的方式呈现迷宫当前的状态**【注】* 教材中无此操作* 此处增加该操作的目的是观察寻路过程的每一步*/
void PaintMaze(MazeType maze) {int i, j;Wait(SleepTime);system("cls");                           //清空，下面是重新打印for (i = 0; i < MAXSIZE; i++) {for (j = 0; j < MAXSIZE; j++) {if (maze[i][j] == Wall) {                   // 外墙printf("▇");}else if (maze[i][j] == Obstacle) {        // 迷宫内部的障碍printf("X");}else if (maze[i][j] == East) {            // 正在朝东探索printf("→");}else if (maze[i][j] == South) {           // 正在朝南探索printf("↓");}else if (maze[i][j] == West) {            // 正在朝西探索printf("←");}else if (maze[i][j] == North) {           // 正在朝北探索printf("↑");}else if (maze[i][j] == Impasse) {         // 死胡同，即四个方向都探索过，但无法通过的位置printf("★");}else {                                   // 还未探索过的路径结点printf(" ");}if (j != 0 && j % (MAXSIZE - 1) == 0) {           // 每隔N个结点换行printf("\n");}}}printf("\n");
}int main(int argc, char* argv[]){MazeType maze;PosType start, end;char ch,Re = 'Y';while (Re == 'Y' || Re == 'y') {InitMaze(maze, start, end);    // 初始化迷宫，包括出入口MazePath(maze, start, end);      // 迷宫寻路printf("重置？（Y/N）：");scanf_s("%c", &Re, 1);ch = getchar();printf("\n");}return 0;
}

表达式求值

链式顺序栈头文件LinkStack.h 

#pragma once
#pragma once
#include <cstdio>
#include <cstdlib>
#include <cstring>#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;//Status是函数的类型，其值是函数结果状态代码
typedef char SElemType;//-----栈的顺序存储表示-----
#define STACK_INIT_SIZE 100  //存储空间初始分配量
#define STACKINCREMENT 10    //存储空间分配增量
typedef struct SNode {SElemType data;//数据域struct SNode* next;//
}SNode,*LinkStack;
//-----基本操作的函数原型说明-----
Status InitStack(LinkStack& S);
//构造一个空栈S
Status DestroyStack(LinkStack& S);
//销毁栈S，S不再存在
Status ClearStack(LinkStack& S);
//把S置为空栈
Status StackEmpty(LinkStack S);
//若栈S为空栈，则返回TRUE,否则返回FALSE
int StackLength(LinkStack S);
//返回S的元素个数，即栈的长度
Status GetTop(LinkStack S, SElemType& e);
//若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR
Status Push(LinkStack& S, SElemType e);
//插入元素e为新的栈顶元素
Status Pop(LinkStack& S, SElemType& e);
//若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR
Status StackTraverse(LinkStack S, void(*visit)(SElemType));
//从栈底到栈顶依次对栈中每个元素调用函数visit()。一旦visit()失败，则操作失败
Status StackTraverse_Top(LinkStack S, Status(*pfn_visit)(SElemType));
//从栈顶到栈底依次对栈中每个元素调用函数visit()。一旦visit()失败，则操作失败

链式顺序栈函数实现LinkStack.cpp

#include "LinkStack.h"Status InitStack(LinkStack& S) {S = (LinkStack)malloc(sizeof(SNode));if (!S)exit(OVERFLOW);S->next = NULL;return OK;
}Status DestroyStack(LinkStack& S) {LinkStack p = S->next, pp;while (p) {pp = p->next;free(p);p = pp;}free(S);return OK;
}Status ClearStack(LinkStack& S) {LinkStack p = S->next, pp;while (p) {pp = p->next;free(p);p = pp;}S->next = NULL;return OK;
}Status StackEmpty(LinkStack S) {if (S->next == NULL)return OK;elsereturn FALSE;
}int StackLength(LinkStack S) {int n = 0;LinkStack p = S->next;while (p) {n++;p = p->next;}return n;
}Status GetTop(LinkStack S, SElemType& e) {if (S->next == NULL)return ERROR;e = S->next->data;return OK;
}Status Push(LinkStack& S, SElemType e) {LinkStack p = (LinkStack)malloc(sizeof(SNode));p->data = e;p->next = S->next;S->next = p;return OK;
}Status Pop(LinkStack& S, SElemType& e) {if (S->next == NULL)return ERROR;e = S->next->data;LinkStack pp = S->next->next;free(S->next);S->next = pp;return OK;
}Status StackTraverse(LinkStack S, void(*visit)(SElemType)) {if (S->next == NULL) {printf("栈为空！\n");return ERROR;}for (int i = StackLength(S);i > 0;i--) {LinkStack p = S->next;int j = 1;while (p && j < i) {p = p->next;++j;}visit(p->data);}printf("\n");return OK;
}Status StackTraverse_Top(LinkStack S, Status(*pfn_visit)(SElemType)) {if (S->next == NULL) {printf("栈为空！\n");return ERROR;}LinkStack p = S->next;while (p) {pfn_visit(p->data);p = p->next;}printf("\n");return OK;
}

表达式求值主函数

#include "LinkStack.h"
#define OperandType charStatus visit(SElemType e) {printf(" %c", e);return OK;
}//-----算法部分-----
//判定运算符栈的（栈顶运算符Θ1）与（读入的运算符Θ2）之间的优先关系SElemType Precede(SElemType t1, SElemType t2) {SElemType t;switch (t1) {case '+':case '-':if (t2 == '*' || t2 == '/' || t2 == '(')t = '<';else t = '>';break;case '*':case '/':if (t2 == '(')t = '<';else t = '>';break;case '(':if (t2 == ')')t = '=';else if (t2 == '#')return ERROR;else t = '<';break;case ')':if (t2 == '(')return ERROR;else t = '>';break;case '#':if (t2 == ')')return ERROR;else if (t2 == '#')t = '=';else t = '<';break;}return t;
}//进行二元运算aΘb
SElemType Operator(SElemType a, SElemType theta, SElemType b) {SElemType ret;switch (theta){case '+':ret = (a - 48) + (b - 48) + 48;break;case '-':ret = (a - 48) - (b - 48) + 48;break;case '*':ret = (a - 48) * (b - 48) + 48;break;case '/':ret = (a - 48) / (b - 48) + 48;break;default:return NULL;}return ret;
}Status In(SElemType c) {switch (c) {case'+':case'-':case'*':case'/':case'(':case')':case'#':case'=':return OK;break;default:return ERROR;}
}//算法3.4
OperandType EvaluateExpression() {//算术表达式求值的算符优先算法。//设OPTR和OPND分别为运算符栈和运算数栈，OP为运算符集合。LinkStack OPTR;//运算符栈：寄存运算符LinkStack OPND;//运算数栈：寄存操作数或运算结果//VS中变量上加注释，当鼠标移到下一次同变量的地方会显示注释char c, x, theta, a, b, e;InitStack(OPTR);InitStack(OPND);Push(OPTR, '#');c = getchar();GetTop(OPTR, e);while (c != '#' || e != '#') {if (!In(c)) {//运算数Push(OPND, c);c = getchar();}else {//运算符GetTop(OPTR, e);switch (Precede(e, c)) {case '<'://栈顶元素优先权低Push(OPTR, c);c = getchar();break;case '='://脱括号并接受下一个字符Pop(OPTR, x);c = getchar();break;case '>'://退栈并将运算结果入栈Pop(OPTR, theta);Pop(OPND, b);Pop(OPND, a);Push(OPND, Operator(a, theta, b));break;}}GetTop(OPTR, e);}GetTop(OPND, e);return e;
}//运算数只能是一位自然数
int main(int argc, char** argv) {char c;c = EvaluateExpression();//3*5#=15printf("%d", c - 48);return 0;
}

测试结果

 

这篇关于数据结构（C语言）代码实现（九）——迷宫探路表达式求值的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/756189。

相关文章

Java根据IP地址实现归属地获取

Java根据IP地址实现归属地获取

《Java根据IP地址实现归属地获取》Ip2region是一个离线IP地址定位库和IP定位数据管理框架,这篇文章主要为大家详细介绍了Java如何使用Ip2region实现根据IP地址获取归属地,感兴趣... 目录一、使用Ip2region离线获取1、Ip2region简介2、导包3、下编程载xdb文件4、J
阅读更多...
PyQt5+Python-docx实现一键生成测试报告

PyQt5+Python-docx实现一键生成测试报告

《PyQt5+Python-docx实现一键生成测试报告》作为一名测试工程师,你是否经历过手动填写测试报告的痛苦,本文将用Python的PyQt5和python-docx库,打造一款测试报告一键生成工... 目录引言工具功能亮点工具设计思路1. 界面设计：PyQt5实现数据输入2. 文档生成：python-
阅读更多...
Android实现一键录屏功能(附源码)

Android实现一键录屏功能(附源码)

《Android实现一键录屏功能(附源码)》在Android5.0及以上版本,系统提供了MediaProjectionAPI,允许应用在用户授权下录制屏幕内容并输出到视频文件,所以本文将基于此实现一个... 目录一、项目介绍二、相关技术与原理三、系统权限与用户授权四、项目架构与流程五、环境配置与依赖六、完整
阅读更多...
浅析如何使用xstream实现javaBean与xml互转

浅析如何使用xstream实现javaBean与xml互转

《浅析如何使用xstream实现javaBean与xml互转》XStream是一个用于将Java对象与XML之间进行转换的库,它非常简单易用,下面将详细介绍如何使用XStream实现JavaBean与... 目录1. 引入依赖2. 定义 JavaBean3. JavaBean 转 XML4. XML 转 J
阅读更多...
Flutter实现文字镂空效果的详细步骤

Flutter实现文字镂空效果的详细步骤

《Flutter实现文字镂空效果的详细步骤》：本文主要介绍如何使用Flutter实现文字镂空效果,包括创建基础应用结构、实现自定义绘制器、构建UI界面以及实现颜色选择按钮等步骤,并详细解析了混合模... 目录引言实现原理开始实现步骤1：创建基础应用结构步骤2：创建主屏幕步骤3：实现自定义绘制器步骤4：构建U
阅读更多...
SpringBoot中四种AOP实战应用场景及代码实现

SpringBoot中四种AOP实战应用场景及代码实现

《SpringBoot中四种AOP实战应用场景及代码实现》面向切面编程(AOP)是Spring框架的核心功能之一,它通过预编译和运行期动态代理实现程序功能的统一维护,在SpringBoot应用中,AO... 目录引言场景一：日志记录与性能监控业务需求实现方案使用示例扩展：MDC实现请求跟踪场景二：权限控制与
阅读更多...
Android实现定时任务的几种方式汇总(附源码)

Android实现定时任务的几种方式汇总(附源码)

《Android实现定时任务的几种方式汇总(附源码)》在Android应用中,定时任务（ScheduledTask）的需求几乎无处不在：从定时刷新数据、定时备份、定时推送通知,到夜间静默下载、循环执行... 目录一、项目介绍1. 背景与意义二、相关基础知识与系统约束三、方案一：Handler.postDel
阅读更多...
使用Python实现IP地址和端口状态检测与监控

使用Python实现IP地址和端口状态检测与监控

《使用Python实现IP地址和端口状态检测与监控》在网络运维和服务器管理中,IP地址和端口的可用性监控是保障业务连续性的基础需求,本文将带你用Python从零打造一个高可用IP监控系统,感兴趣的小伙... 目录概述：为什么需要IP监控系统使用步骤说明1. 环境准备2. 系统部署3. 核心功能配置系统效果展
阅读更多...
Python实现微信自动锁定工具

Python实现微信自动锁定工具

《Python实现微信自动锁定工具》在数字化办公时代,微信已成为职场沟通的重要工具,但临时离开时忘记锁屏可能导致敏感信息泄露,下面我们就来看看如何使用Python打造一个微信自动锁定工具吧... 目录引言：当微信隐私遇到自动化守护效果展示核心功能全景图技术亮点深度解析1. 无操作检测引擎2. 微信路径智能获
阅读更多...
Python中pywin32 常用窗口操作的实现

Python中pywin32 常用窗口操作的实现

《Python中pywin32常用窗口操作的实现》本文主要介绍了Python中pywin32常用窗口操作的实现,pywin32主要的作用是供Python开发者快速调用WindowsAPI的一个... 目录获取窗口句柄获取最前端窗口句柄获取指定坐标处的窗口根据窗口的完整标题匹配获取句柄根据窗口的类别匹配获取句
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2