数据结构（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的值为NULL
	SElemType* 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) {
	//构造一个空栈S
	S.base = (SElemType*)malloc(STACK_INIT_SIZE * sizeof(SElemType));
	if (!S.base)exit(OVERFLOW);//存储分配失败，警告C6011
	S.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；否则返回ERROR
	if (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；否则返回ERROR
	if (!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；否则返回FALSE
    SqStack 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;
                else
                    maze[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;
    else
        return 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;
	else
		return 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 char

Status 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#=15
	printf("%d", c - 48);
	return 0;
}