数据结构C语言版_非循环顺序队列求解迷宫问题.doc

/* 数据结构C语言版 非循环顺序队列求解迷宫问题 利用非循环顺序队列采用广度有哪些信誉好的足球投注网站法求解迷宫问题(一条路径) 编译环境：Dev-C++ 4.9.9.2 日期：2011年2月12日 */ #include stdio.h #include malloc.h #define M 5 // 迷宫行数(包括外墙) #define N 5 // 迷宫列数(包括外墙) #define D 4 // 移动方向数,只能取4和8。(8个,可斜行;4个,只可直走) // 移动数组,移动方向由正东起顺时针转 struct { int x,y; #if D==8 }move[D]={{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1}}; #endif #if D==4 }move[D]={{0,1},{1,0},{0,-1},{-1,0}}; #endif // 定义栈元素类型和队列元素类型，两者为相同类型。 typedef struct { int x,y; // 当前点的行值，列值 int pre; // 前一点在队列中的序号 } SElemType, QElemType; #define STACK_INIT_SIZE 10 // 存储空间初始分配量 #define STACKINCREMENT 2 // 存储空间分配增量 // 栈的顺序存储表示 P46 typedef struct SqStack { SElemType *base; // 在栈构造之前和销毁之后，base的值为NULL SElemType *top; // 栈顶指针 int stacksize; // 当前已分配的存储空间，以元素为单位 }SqStack; // 顺序栈 // 顺序队列(非循环，因为是非循环的，所以需要判断是否溢出 #define MAXQSIZE 5 // 最大队列长度(对于循环队列，最大队列长度要减1) typedef struct { QElemType *base;// 初始化的动态分配存储空间 相当于一个数组 // 头指针,若队列不空,指向队列头元素，相当于一个数组下标 int front; // 尾指针,若队列不空,指向队列尾元素的下一个位置 相当于一个数组下标 int rear; }SqQueue; // 构造一个空队列Q int InitQueue(SqQueue *Q) { //分配定长的空间，相当于一个数组 (*Q).base=(QElemType *)malloc(MAXQSIZE*sizeof(QElemType)); if(!(*Q).base) // 存储分配失败 exit(0); (*Q).front=(*Q).rear=0; //初始化下标 return 1; } // 销毁队列Q,Q不再存在 int DestroyQueue(SqQueue *Q) { if((*Q).base) free((*Q).base); (*Q).base=NULL; (*Q).front=(*Q).rear=0; return 1; } // 若队列Q为空队列,则返回1,否则返回0 int QueueEmpty(SqQueue Q) { if(Q.front==Q.rear) // 队列空的标志 return 1; else return 0; } // 插入元素e为Q的新的队尾元素 int EnQueue(SqQueue *Q,QElemType e) { if((*Q).rear=MAXQSIZE) { // 队列满，增加1个存储单元 (*Q).base=(QElemType *)realloc((*Q).base, ((*Q).rear+1)*sizeof(QElemType)); if(!(*Q).base) // 增加单元失败 return 0; } *((*Q).base+(*Q).rear)=e; (*Q).rear++; return 1; } // 若队列不空,则删除Q的队头元素,用e返回其值,并返回1,否则返回0 int DeQueue(SqQueue *Q,QElemType *e) { if((*Q).front==(*Q).rear) // 队列空 return 0; *e=(*Q).base[(*Q).front]; (*Q).front=(*Q).front+1; return 1; } // 构造一个空栈S。 int InitStack(SqStack *S) { // 为栈底分配一个指定