目录

利用顺序栈输出对应的二进制数

代码： 

运行结果： 

找迷宫出口

代码： 

图解： 

运行结果：

---

利用顺序栈输出对应的二进制数

键盘输入一个十进制正整数89，用C语言设计一个算法，利用顺序栈输出对应的二进制数。

代码： 

#include <stdio.h>
#include <malloc.h>
#define MAXSIZE 100
typedef int ElemType;//定义顺序栈结构
//里面有一个数组和一个栈指针
typedef struct 
{	ElemType data[MAXSIZE];int top;				//栈指针
} SqStack;					//顺序栈类型// 初始化栈
void InitStack(SqStack *S) {S->top = -1;  // 栈顶初始指向-1，表示栈为空
}// 入栈
void Push(SqStack *S, int value) {//栈已满，直接返回if (S -> top == MAXSIZE - 1) {printf("栈已满!\n");return;}//栈未满，让栈指针加一并且将值放在栈顶指针处S -> top++;S -> data[S -> top] = value;
}// 取栈顶元素并且出栈
int Pop(SqStack *S) {//栈为空，直接返回falseif (S->top == -1) {printf("栈为空!\n");return false;}//让栈顶指针减一并且返回栈顶指针指向的值int e = S -> data[S -> top];S -> top--;return e;
}// 判断栈是否为空
bool IsEmpty(SqStack *S) {if(S -> top == -1)return true;else return false;
}// 主函数
int main() {int num = 89;  //输入的十进制数89//初始化栈SqStack binStack;InitStack(&binStack);// 将十进制数转换为二进制，并压入栈中do {Push(&binStack, num % 2);  // 将该数除以二的余数入栈num /= 2;  // 再让该数变为它除以二之后的数} while (num > 0);// 输出二进制数printf("89的二进制数为: ");//只要栈不为空就输出栈顶元素while (!IsEmpty(&binStack)) {int digit = Pop(&binStack);printf("%d", digit);}printf("\n");return 0;
}

运行结果： 

找迷宫出口

有一个迷宫如下图所示：

利用顺序栈求一个从指定入口（1,1）到出口（4,4）的路径。

代码： 

#include <stdio.h>
#include <stdlib.h>typedef struct {int i,j;int di;//i为行，j为列号，di是走到下一相邻方块的方位号
} box;//表示这是一个方块类型// 定义顺序栈结构
typedef struct {box data[50];int top;//栈顶指针
} stack;// 初始化栈
void InitStack(stack * &S) {S = (stack *)malloc(sizeof(stack));S -> top = -1;  // 栈顶初始指向-1，表示栈为空
}// 入栈
bool push(stack * &s,box b) {s -> top++;s -> data[s -> top] = b;return true;
}// 出栈
bool pop(stack * &s,box &b) {b = s -> data[s -> top];s -> top--;//用b存放栈顶元素，栈顶指针减一return true;
}//取栈顶元素
bool gettop(stack *s,box &b) {b = s -> data[s -> top];return true;
}bool isempty(stack *s) {if(s -> top == -1)return true;else return false;
}const int m = 4,n = 4;
//这表示这是一个4乘4大小的迷宫。
int maze[m + 2][n + 2] = {//要给迷宫加上一道围墙，所以行和列都要加2//墙初始化为1，没墙初始化为0{1, 1, 1, 1, 1, 1},{1, 0, 0, 0, 1, 1},{1, 0, 1, 0, 0, 1},{1, 0, 0, 0, 1, 1},{1, 1, 0, 0, 0, 1},{1, 1, 1, 1, 1, 1}};bool mgpath(int xi,int yi,int xe,int ye) {//求解路径为xiyi到xeyebox path[50],e;int i,j,di,i1,j1,k;bool find;stack *s;InitStack(s); //初始化栈e.i = xi,e.j = yi,e.di = -1; //设置e为入口push(s,e); //e入栈maze[xi][yi] = -1; //将迷宫入口设置为-1while(!isempty(s)) {//只要栈不为空就进行如下循环gettop(s,e); //得到栈顶元素i = e.i,j = e.j,di = e.di;if(i == xe && j == ye) {//找到出口printf("找到了一条走到终点的路径为：\n");k = 0;while(!isempty(s)) {pop(s,e);path[k++] = e;//将e添加到path数组}while(k > 0) {printf("\t(%d,%d)",path[k - 1].i,path[k - 1].j);if((k + 1) % 5 == 0)printf("\n");k--;//每5行换一行}printf("\n");return true;}find = false;while(di < 4 && !find) {//di表示4个方向，向上为0//向右为1，向下位为2，向左为3di++;//每次让di+1表示换一个方向switch(di) {case 0:i1 = i - 1,j1 = j    ;break;case 1:i1 = i    ,j1 = j + 1;break;case 2:i1 = i + 1,j1 = j    ;break;case 3:i1 = i    ,j1 = j - 1;break;//上右下左4个方向}if(maze[i1][j1] == 0)find = true;//为0表示可以走}if(find) {s -> data[s -> top].di = di;//修改栈顶di值e.i = i1,e.j = j1,e.di = -1;push(s,e); //相邻可走方块入栈maze[i1][j1] = -1;//将走过的位置设置为-1，防止重复走}else{pop(s,e);maze[e.i][e.j] = 0;//每找到路径，就回溯，出栈并且使走过的位置重新变为0}}return false;//表示没有路径可以走
}int main() {if(!mgpath(1,1,4,4))//传入出口位置和出口位置printf("该迷宫问题没有解");return 0;
}

图解： 

运行结果：