04-《数据结构实现》实验指导(实验四).pdf

《数据结构实现》实验指导 实验总时数：40 学时 实验四 利用顺序栈结构处理迷宫求解 一、实验目的 掌握栈的基本结构和操作方法，培养学生灵活使用结构解决实际问题的能力。 二、实验内容： 通过VC++ 6.0 实现以下程序，熟练掌握每行代码的具体功能。 #include string.h #include ctype.h #include malloc.h /* malloc()等 */ #include limits.h /* INT_MAX 等 */ #include stdio.h /* EOF(=^Z 或F6),NULL */ #include stdlib.h /* atoi() */ #include io.h /* eof() */ #include math.h /* floor(),ceil(),abs() */ #include process.h /* exit() */ /* 函数结果状态代码 */ #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 typedef int Status; /* Status 是函数的类型，其值是函数结果状态代码，如OK 等 */ typedef int Boolean; /* Boolean 是布尔类型，其值是TRUE 或FALSE */ typedef struct /* 迷宫坐标位置类型 */ { int x; /* 行值 */ int y; /* 列值 */ }PosType; typedef struct /* 栈的元素类型 */ { int ord; /* 通道块在路径上的＂序号＂ */ PosType seat; /* 通道块在迷宫中的＂坐标位置＂ */ int di; /* 从此通道块走向下一通道块的＂方向＂(0～3 表示东～北) */ }SElemType; #define MAXLENGTH 25 /* 设迷宫的最大行列为25 */ typedef int MazeType[MAXLENGTH][MAXLENGTH]; /* 迷宫数组[行][列] */ /* 全局变量 */ 1 MazeType m; /* 迷宫数组 */ int curstep=1; /* 当前足迹，初值为1 */ #define STACK_INIT_SIZE 10 /* 存储空间初始分配量 */ #define STACKINCREMENT 2 /* 存储空间分配增量 */ typedef struct SqStack { SElemType *base; /* 在栈构造之前和销毁之后，base 的值为NULL */ SElemType *top; /* 栈顶指针 */ int stacksize; /* 当前已分配的存储空间，以元素为单位 */ }SqStack; /* 顺序栈 */ Status InitStack(SqStack *S) { /* 构造一个空栈S */ (*S).base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!(*S).base) exit(OVERFLOW); /* 存储分配失败 */ (*S).top=(*S).base; (*S).stacksize=STACK_INIT_SIZE; return OK; } Status DestroyStack(SqStack *S) { /* 销毁栈S，S 不再存在 */ fr