C语言数据结构之迷宫问题

本文实例为大家分享了数据结构c语言版迷宫问题栈实现的具体代码,供大家参考,具体内容如下

程序主要参考自严蔚敏老师的数据结构c语言版,在书中程序的大体框架下进行了完善。关于迷宫问题的思路可查阅原书。

#include<iostream>

using namespace std;

#define MAXSIZE 10
typedef int Status;
typedef struct{
 int x;
  int y;
}Postype;
typedef struct{
 int ord;
 Postype seat;
 int dir;
}SElemType;//栈的元素类型
typedef struct{
 //SElemType data[MAXSIZE];
 SElemType* top;
 SElemType* base;
}Stack;//栈的结构类型
typedef struct{
 char arr[MAXSIZE][MAXSIZE];
}MAZETYPE;//迷宫结构体

MAZETYPE maze;
void InitMaze()
{
 maze.arr[0][0] = maze.arr[0][1] = maze.arr[0][2] = maze.arr[0][3] = maze.arr[0][4] = maze.arr[0][5] = maze.arr[0][6] = maze.arr[0][7] = maze.arr[0][8] = maze.arr[0][9] = '1';
 maze.arr[1][0] = maze.arr[1][3] = maze.arr[1][7] = maze.arr[1][9] = '1';
 maze.arr[1][1] = maze.arr[1][2] = maze.arr[1][4] = maze.arr[1][5] = maze.arr[1][6] = maze.arr[1][8] = '0';
 maze.arr[2][0] = maze.arr[2][3] = maze.arr[2][7] = maze.arr[2][9] = '1';
 maze.arr[2][1] = maze.arr[2][2] = maze.arr[2][4] = maze.arr[2][5] = maze.arr[2][6] = maze.arr[2][8] = '0';
 maze.arr[3][0] = maze.arr[3][5] = maze.arr[3][6] = maze.arr[3][9] = '1';
 maze.arr[3][1] = maze.arr[3][2] = maze.arr[3][3] = maze.arr[3][4] = maze.arr[3][7] = maze.arr[3][8] = '0';
 maze.arr[4][0] = maze.arr[4][2] = maze.arr[4][3] = maze.arr[4][4] = maze.arr[4][9] = '1';
 maze.arr[4][1] = maze.arr[4][5] = maze.arr[4][6] = maze.arr[4][7] = maze.arr[4][8] = '0';
 maze.arr[5][0] = maze.arr[5][4] = maze.arr[5][9] = '1';
 maze.arr[5][1] = maze.arr[5][2] = maze.arr[5][3] = maze.arr[5][5] = maze.arr[5][6] = maze.arr[5][7] = maze.arr[5][8] = '0';
 maze.arr[6][0] = maze.arr[6][2] = maze.arr[6][6] = maze.arr[6][9] = '1';
 maze.arr[6][1] = maze.arr[6][3] = maze.arr[6][4] = maze.arr[6][5] = maze.arr[6][7] = maze.arr[6][8] = '0';
 maze.arr[7][0] = maze.arr[7][2] = maze.arr[7][3] = maze.arr[7][4] = maze.arr[7][6] = maze.arr[7][9] = '1';
 maze.arr[7][1] = maze.arr[7][5] = maze.arr[7][7] = maze.arr[7][8] = '0';
 maze.arr[8][0] = maze.arr[8][1] = maze.arr[8][9] = '0';
 maze.arr[8][2] = maze.arr[8][3] = maze.arr[8][4] = maze.arr[8][5] = maze.arr[8][6] = maze.arr[8][7] = maze.arr[8][8] = '0';
 maze.arr[9][0] = maze.arr[9][1] = maze.arr[9][2] = maze.arr[9][3] = maze.arr[9][4] = maze.arr[9][5] = maze.arr[9][6] = maze.arr[9][7] = maze.arr[9][8] = maze.arr[9][9] = '1';
}
Status initStack(Stack &s)
{
 s.base = (SElemType*)malloc(MAXSIZE*sizeof(SElemType));
 if (!s.base) return 0;
 s.top = s.base;
 return 1;
}
void Push(Stack &s, SElemType e)
{
 *s.top++ = e;
}
void Pop(Stack &s, SElemType &e)
{
 e = *--s.top;
}
Status StackEmpty(Stack &s)
{
 if (s.top == s.base) return 1;
 else return 0;
}
Status Pass(Postype curpos)
{
 if (maze.arr[curpos.x][curpos.y] == '0')
 return 1;
 else return 0;
}
void Foot(Postype curpos)
{
 maze.arr[curpos.x][curpos.y] = '*';
}
void MarkPrint(Postype curpos)
{
 maze.arr[curpos.x][curpos.y] = '!';
}
Status StructCmp(Postype a, Postype b)
{
 if (a.x = b.x&&a.y == b.y) return 1;
 else return 0;
}
//下一个位置
Postype NextPos(Postype CurPos, int Dir)
{
 Postype ReturnPos;
 switch (Dir)
 {
 case 1:
 ReturnPos.x = CurPos.x;
 ReturnPos.y = CurPos.y + 1;
 break;
 case 2:
 ReturnPos.x = CurPos.x + 1;
 ReturnPos.y = CurPos.y;
 break;
 case 3:
 ReturnPos.x = CurPos.x;
 ReturnPos.y = CurPos.y - 1;
 break;
 case 4:
 ReturnPos.x = CurPos.x - 1;
 ReturnPos.y = CurPos.y;
 break;
 }
 return ReturnPos;
}

Status MazePath(Postype start, Postype end)
{
 Stack s;
 SElemType e;
 initStack(s);
 Postype curpos = start;
 int curstep = 1;
 do{
 if (Pass(curpos))
 {
  Foot(curpos);
  e = { curstep, curpos, 1 };
  Push(s, e);
  if (StructCmp(curpos, end)) return 1;
  curpos = NextPos(curpos, 1);
  curstep++;
 }
 else
 {
  if (!StackEmpty(s))
  {
  Pop(s, e);
  while (e.dir ==4 &&!StackEmpty(s))
  {
   MarkPrint(e.seat); Pop(s, e);
  }
  if (e.dir < 4 && !StackEmpty(s))
  {
   e.dir++;
   Push(s, e);
   curpos = NextPos(e.seat, e.dir);
  }
  }

 }

 } while (!StackEmpty(s));
 return 0;

}

int main()
{
 InitMaze();
 Postype s, e;
 s.x = s.y = 1;
 e.x = e.y = 8;
 if (MazePath(s, e))
 printf("迷宫成功解密!\n");
 else
 printf("解密失败\n");
 for (int i = 0; i < 10; i++)
 {
 for (int j = 0; j < 10; j++)
  {
  printf("%c ", maze.arr[i][j]);
  }
 printf("\n");
  }
 cout << "-=================================" << endl;
 for (int i = 0; i < 10; i++)
 {
 for (int j = 0; j < 10; j++)
 {
  if (maze.arr[i][j] == '*' || maze.arr[i][j] == '!')
  printf("%c ", maze.arr[i][j]);
  else cout << " ";
 }
 printf("\n");
 }
}

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。

(0)

相关推荐

  • C语言实现小学生计算机辅助教学系统

    开发一个小学生计算机辅助教学系统.使用随机书产生函数产生1~10之间的随机数作为操作数,随机产生一道四则运算题,配合使用switch语句和print()函数调用,来为学生输入的正确或者错误的答案输出不同的评价.若10道题做完之后正确率低于75%,则重新做10道题,直到回答正确率高于75%时才退出程序.要求用模块化程序设计方法来编程. #include<stdio.h> #include<stdlib.h> #include<time.h> int Calculate(i

  • C语言实现数据结构迷宫实验

    本文实例为大家分享了C语言实现简单的数据结构迷宫实验,供大家参考,具体内容如下 分析:迷宫实验主要有两部分操作,其一是对迷宫的生成,其二是寻路使用栈的操作. 步骤: 一..h文件 1.首先是迷宫的生成,可以使用随机数种子生成,但主要逻辑部分并不在此,所以在这里直接写死,固定下来. 定义一个坐标类型的结构体,和二维数组迷宫: typedef struct { int x; int y; }Pos; //迷宫类型 typedef struct { int square[10][10] = { {1,

  • C语言数据结构之迷宫求解问题

    现在网上各种对于迷宫的求解,版本多的数不胜数.本人小白一枚,贴上自己对迷宫的求解这个小项目,自己写的.望能帮助一些同样有困难的人,毕竟我当时费解了好一会儿时间呢. 首先,先标明对于迷宫求解这个项目,首先我提出自己的思路,利用"穷举求解"的方法(严蔚敏老师数据结构一书中提到,一开始不知方法其名.)其实简单来说就是一条路一条路去试,当然不能随便试,我的方法是按照从入口出发,顺一个方向向前探索,走得通就继续向前走:否则留下标记沿原路退回并换一个方向继续探索,直到所有的路都走完为止.还是用栈的

  • C语言实现歌手大奖赛计分程序

    本文实例为大家分享了C语言实现歌手大奖赛计分程序的具体代码,供大家参考,具体内容如下 1. 题目描述 编写一个程序,用户输入评委人数和分数后,程序可以计算去掉一个最高分和最低分后的平均成绩.可多次输入选手成绩,输入N时退出程序. 2. 源代码 #include <stdio.h> #include <stdlib.h> float score[99];//成绩数据 int num=0;//评委数目 float sum=0;//总分 //输入打分数据并输出结果 void inputS

  • C语言实现小学生随机出题测试计分

    本文实例为大家分享了C语言实现随机出题测试计分的具体代码,供大家参考,具体内容如下 #include <stdio.h> #include <stdlib.h> #include <time.h> int test(); int checknum(int a, int b); int checkresult(int x); int a = -1, b, c, x; static int k = 0, grade; void main() { printf("请

  • C语言实现无规律数据加密、解密功能

    在网络传输重要信息或存储重要文件信息时,大部分会对数据加密,保证数据的安全性.互联网上流行的可逆加密方式对数据的安全性没有保证,便自己写了一套安全性极高加密.解密方法. 方法的实现方式及特点: 1.采用指定单个字节加密转换(转换形式为ascll码表中0-128的形式,由1个字节拆分为三个字节,下面说明拆分方式): 2.采用数组中随机数据减指定加密字节(比如当前数据ascll码为121,当前数组中的数据为222,结果为222-121=101,当然这个只是参考实例): 3.采用随机指定数组方式(如果

  • C语言清除scanf()缓存的案例讲解

    又重新过一遍C语言,感觉每次重学C语言都有不同的感受,遇到了一个问题,就是scanf()这个问题,其实细究起来,也有很多可以值得深挖的,实际上每次细细的挖掘的话,都是对C语言的更透彻的认识. 那么下面我就对scanf()中清除输入缓冲区的方法讲解: 应用场景:我们使用多个scanf()的时候,如果输入缓冲区还有数据的话,那么scanf()就不会询问用户输入,而是直接就将输入缓冲区的内容拿出来用了,这就导致了前面的错误影响到后面的内容,为了隔离这种问题, 总的思想:通过各种方法将输入缓冲区的内容读

  • C语言链表实现歌手评分系统

    本文实例为大家分享了C语言链表实现歌手评分系统的具体代码,供大家参考,具体内容如下 此程序可以添加文件操作用于保存歌手得分等信息,此程序实现了链表的增删查和链表冒泡排序交换节点功能 #include <stdio.h> #include <stdlib.h> #include <string.h> //创建结构体及其成员 typedef struct Node { int num;//编号 char name[20];//姓名 float grade[10];//评委评

  • C语言实现小学生考试系统

    本文实例为大家分享了C语言实现小学生考试系统的具体代码,供大家参考,具体内容如下 问题及代码: /*烟台大学计算机学院 题目描述:做一个小学生考试系统,功能包括: (1)利用随机数出10道加法题: (2)小学生用户答题给出每道题的答案: (3)对小学生的答题进行评判: (4)计算出小学生答题正确率. 作者:景怡乐 完成时间:2016年12月29日 */ #include <stdio.h> #include <stdlib.h> #include <time.h> in

  • C语言实现小型电子词典

    本文实例为大家分享了C语言实现小型词典系统,供大家参考,具体内容如下 1. 题目描述 用C语言编写一个小型词典,用户可以进行英译汉.汉译英.删除修改单词.添加单词等功能. 2.源代码 /* 小型词典系统 版本:0.9 作者:个快快 应用模型:文件增删改查 */ #include <stdio.h> #include <string.h> int worsNumber = 0; //单词数目 //---------------------- //定义结构体存储词典数据 //-----

随机推荐