数据结构-栈和队列应用之八皇后与表达式求值
八皇后问题
/*
八皇后问题是在8x8的国际象棋棋盘上，安放8个皇后，要求没有一个皇后能够"吃掉"任何其他一个皇后，
即没有两上或两个以上的皇后占据棋盘上的同一行、同一列或同一条对角线。
算法描述：
1.置当前行当前列均为1;
2.while(当前行号<=8)
3.{检查当前行，从当前列起逐列试探，寻找安全列号;
4. if(找到安全列号)
5. 放置皇后，将列号记入栈中，并将下一行置成当前行，第1列置为当前列;
6. esle
7. 退栈回溯到上一行，移去该行放置的皇后，以该皇后所在列的下一列作为当前列;
8.}结束程序。
1.当前行和列用i和j表示。若皇后放在位置(i,j)上，则将j压入栈中，即s[i]=j.
2.添加三个布尔数组(初始值为真)，用于保存与检查有关的信息。
enum boolean {false,true};
enum boolean a[9],a[17],a[17];
int s[9];
1.其中 a[j]为真时，表示第j列上无皇后。
2.b[k]:表示 "/"方向的第 k 条对角线上无皇后。
3.c[k]:表赤 "\"方向的第 k 条对角线上无皇后。
位于同一条 "/"方向的对角线上的诸方格，其行、列坐标之和 i+j 是相等的，这种方向的对角线有15条，
其行列坐标之和分别为2至16，因此用b[2...16]标记该方向的诸对角线上有无皇后，b[k]为真时表
示该方向的第 k 条对角线上无皇后。
行列坐标之差 i-j 相等的诸方格在同一条 "\"方向以对角线上，该类对角线有15条，其行列坐标之差分
别是 -7到7 ，因为C语言数组下标是从0开始，所以用 c[2...16]标记这种方向的诸对角线上有无皇后，
c[k](k=i-j+9,使其取值范围为2到16)，为真时表示该方向的第 k 条对角线上无皇后。
所以 b[i+j]和c[i-j+9]真假就分别表示了通过位置(i,j)的两条对角线上有无皇后。因此，位置 (i,j) 的
"安全" 性可用逻辑表达示：
a[j] && b[i+j] && c[i-j+9]
来表示。在位置 (i,j) 上放置皇后后，相当于将 a[j],b[i+j]和 c[i-j+9]置为假;移去 (i,j)上的皇后相当
于将 a[j],b[i+j]和 c[i-j+9]置为真。
*/
enum boolean {false,true};
enum boolean a[9],b[17],c[17];
int s[9];
#include<stdio.h>
void main()
{
void print(),movequeen(),eightqueen(); //函数声明
eightqueen(); //求解八皇后
}
/*******************************************/
/** 求解八皇后 **/
/*******************************************/
void eightqueen()
{
int i,j;
for(i=2;i<=16;i++) //将棋盘上的所有格子都置为真
{
if(i>=2 && i<=9)
a[i-1]=true; //将第j列置为真 , 设置成无皇后
b[i]=true; //将"/"方向的第 i 条对角线置为真 , 设置成无皇后
c[i]=true; //将"\"方向的第 i 条对角线置为真 , 设置成无皇后
}
i=1;j=1; //置当前行当前列均为1
while(i>=1) //当i等于0时终止循环
{
while(j<=8) //在当前行i上寻找安全位置
{
if(a[j] && b[i+j] && c[i-j+9])
break;
j++;
}
if(j<=8) //找到安全位置(i,j)
{
a[j]=false;
b[i+j]=false;
c[i-j+9]=false;
s[i]=j; //皇后位置入栈
if(i==8) //找到一个解，输出解
{
print(); //打印输出一个解
movequeen(i,j); //移去位置(i,j)上的皇后
i=i-1;
j=s[i]; //退栈，回溯到上一个皇后
movequeen(i,j); //移去位置(i,j)上的皇后
j++;
}
else
{
i++; //准备放置下一个皇后
j=1;
}
}
else
{
i--; //退栈
if(i>=1) //栈不为空，移去皇后
{
j=s[i];
movequeen(i,j); //移去皇后
j++;
}
}
}
}
/*******************************************/
/** 打印输出一具解的函数 **/
/*******************************************/
void print()
{
int k;
printf("\n行号: 1 2 3 4 5 6 7 8\n");
printf("列号：");
for(k=1;k<=8;k++)
printf("%4d",s[k]);
printf("\n\n");
}
/*******************************************/
/** 移去位置(i,j)上的皇后的函数 **/
/*******************************************/
void movequeen(int i,int j)
{
a[j]=true;
b[i+j]=true;
c[i-j+9]=true;
}
表达式求值
#include<stdio.h>
#define StackSize 100
#define QueueSize 100
/*队列的相关操作*/
typedef char DataType;
typedef struct
{
char data[100];
int front,rear;
}SeqQueue; //定义队列类型
void InitQueue(SeqQueue *Q) //初始化队列
{
Q->front=0;
Q->rear=0;
}
int QueueEmpty(SeqQueue *Q) //判断空队列
{
return Q->rear==Q->front;
}
void EnQueue(SeqQueue *Q,DataType x) //入队列
{
if((Q->rear+1)%QueueSize==Q->front)
printf("Queue overflow\n");
else
{
Q->data[Q->rear]=x;
Q->rear=(Q->rear+1)%QueueSize;
}
}
DataType DeQueue(SeqQueue *Q) //出队列
{
DataType x;
if(QueueEmpty(Q))
{
printf("Queue Empty\n");
return 0;
}
else
{
x=Q->data[Q->front];
// free(Q->data[Q->front]);
Q->front=(Q->front+1);
return x;
}
}
/*栈的相关操作*/
typedef struct
{
DataType data[100];
int top;
}SeqStack; //栈类型的定义
void InitStack(SeqStack *s) //初始化栈
{
s->top=-1;
}
void Push(SeqStack *s,DataType x) //入栈
{
if(s->top==StackSize-1)
{
printf("stack overflow");
return;
}
else
{
s->top=s->top+1;
s->data[s->top]=x;
}
}
DataType Pop(SeqStack *s) //退栈
{
if(s->top==-1)
{
printf("stack underflow");
return 0;
}
else
return s->data[s->top--];
}
DataType GetTop(SeqStack *s) //取栈顶元素
{
if(s->top==-1)
{
printf("stack empty");
return 0;
}
else
return s->data[s->top];
}
/*求运算符优先级函数*/
int Priority(DataType op)
{
switch(op)
{
case '(':
case '#':return(0);
case '-':
case '+':return(1);
case '*':
case '/':return(2);
}
}
void CTPostExp(SeqQueue *Q)
{
SeqStack OS;
char c,t;
SeqStack *S;
S=&OS;
InitStack(S); //初始化栈
Push(S,'#'); //压入栈底元素 '#'
do //扫描中缀表达式
{
c=getchar();
switch(c)
{
case ' ':break; //去除空格
case '1':
case '2':
case '3':
case '4':
case '5':
case '6':
case '7':
case '8':
case '9':
EnQueue(Q,c);
break;
case '(':
Push(S,c);
break;
case ')':
case '#':
do
{
t=Pop(S);
if(t!='('&&t!='#')
EnQueue(Q,t);
}while(t!='('&&S->top!=-1);
break;
case '+':
case '-':
case '*':
case '/':
while(Priority(c)<=Priority(GetTop(S)))
{
t=Pop(S);
EnQueue(Q,t);
}
Push(S,c);
break;
}
}while(c!='#'); //以'#'号结束表达式扫描
}
int CPostExp(SeqQueue *Q)
{
SeqStack VS,*S;
char ch;
int x,y;
S=&VS;
InitStack(S);
while(!QueueEmpty(Q))
{
ch=DeQueue(Q);
if(ch>='0'&&ch<='9')
Push(S,ch-'0');
else
{
y=Pop(S);
x=Pop(S);
switch(ch)
{
case '+':
Push(S,x+y);
break;
case '-':
Push(S,x-y);
break;
case '*':
Push(S,x*y);
break;
case '/':
Push(S,x/y);
break;
}
}
}
return GetTop(S);
}
void main()
{
SeqQueue *Q;
SeqQueue PostQ,PostQ2; //定义队列，存放后缀表达式
Q=&PostQ;
printf("请输入中缀表达式(以#号结束)：");
InitQueue(Q); //初始化队列
CTPostExp(Q); //调用转换函数将中缀表式转换成后缀表达式
PostQ2=PostQ;
printf("后缀表达式为：");
while(!QueueEmpty(Q)) //输出后缀表达式
printf("%2c",DeQueue(Q));
printf("\n");
printf("计算结果为%4d\n",CPostExp(&PostQ2));
}