PTA数据结构作业二
6-6 循环队列入队出队
本题要求实现队列的顺序存储表示，包括入队、出队和取队头操作
函数接口定义：
void EnQueue_seq(SeqQueue squeue, DataType x) ; void DeQueue_seq(SeqQueue squeue) ; DataType FrontQueue_seq(SeqQueue squeue) ;
其中，squeue 是操作的队列，x是入队的元素
普通的顺序存储的队列因其存储方式的问题出现假溢出的现象，即队头不在存储空间开始的位置，而队尾在存储空间的结束的位置，此时无法再入队新元素，但存储空间还未满。为了解决假溢出现象并使得队列空间得到充分利用，一个较巧妙的方法是将顺序队列看成一个环状的空间，即规定最后一个单元的后继为第一个单元，形象地称之为循环队列。
入队出队实现流程：
(1) 入队操作：首先检查队列是否满，如果不满，则在队尾插入元素，并修改队尾指针。
①if((squeue->r+1)%squeue->Max== squeue->f); //队列满
②squeue->elem[squeue->r]=x; //队列未满先存储元素，再修改队尾指针
③squeue->r=(squeue->r+1)%(squeue->Max);
(2) 出队操作：首先检查队列是否为空，若队列非空，则删除队头元素，修改队头指针。
① if (IsNullQueue_seq(squeue))
② squeue->f =( squeue->f+1)%(squeue->Max);
(3) 取对头元素：检查队列是否为空，若队列非空，返回对头元素。
① if (squeue->r==squeue->f)
② return (squeue->elem[squeue->f])
#include <stdio.h>
#include <stdlib.h>
typedef char DataType; //循环队列的定义
struct Queue
{
int Max; //循环队列的最大容量
int f; //队首/队头
int r; //队尾
DataType *elem; //队列元素起始位置
};
typedef struct Queue *SeqQueue;
SeqQueue SetNullQueue_seq(int m) //创建空队列
{
SeqQueue squeue;
squeue = (SeqQueue)malloc(sizeof(struct Queue));
if (squeue == NULL)
{
printf("Alloc failure.\n");
return NULL;
}
squeue->elem = (char*)malloc(sizeof(DataType)*m);
if (squeue->elem != NULL)
{
squeue->Max = m; //设置循环队列所占空间，实际可存储m-1个元素
squeue->f = 0; //队首/队头初始位置
squeue->r = 0; //队尾初始位置
return squeue;
}
}
int IsNullQueue_seq(SeqQueue squeue) //判断队列是否为空
{
return (squeue->f == squeue->r);
}
void EnQueue_seq(SeqQueue squeue, DataType x) { //新元素x在队尾入队
if((squeue->r+1)%squeue->Max!=squeue->f){ //队列未满
squeue->elem[squeue->r]=x; //将新元素x插入队尾
squeue->r=(squeue->r+1)%squeue->Max; //队尾指针+1
}
else printf("It is FULL Queue!"); //队列满
}
void DeQueue_seq(SeqQueue squeue){ //弹出队首元素
if(squeue->r!=squeue->f){ //队列非空
squeue->f=(squeue->f+1)%squeue->Max; //队首指针+1
}
}
DataType FrontQueue_seq(SeqQueue squeue){ //读取队首元素
if(squeue->r==squeue->f) //空队列
printf("It is empty queue!");
return squeue->elem[(squeue->f)%squeue->Max]; //队列非空时，输出首元素
}
int main()
{
char ch;
SeqQueue queueA = SetNullQueue_seq(5); //循环队列所占空间为5，实际可存储4个元素
ch = getchar();
while (ch != '#')
{
EnQueue_seq(queueA, ch); //入队
ch = getchar();
}
DeQueue_seq(queueA); //出队
printf("%c" ,FrontQueue_seq(queueA)); //读取队首元素
return 0;
}
6-7 进制转换（10->16）
本题要求实现十进制到十六进制的转换，用户输入10进制的数，要求输出该数的16进制表示
函数接口定义：
void Push_seq(SeqStack sstack, int x) void Hexconversion(SeqStack sstack, int n);
其中Push_seq（）是入栈函数，其中，sstack是顺序栈，x是待进制的元素；
Hexconversion（）是进制转换函数，其中，sstack是需要的栈，n是待转换的十进制的数。
解法一：
本题要求实现十进制到十六进制的转换，用户输入10进制的数，要求输出该数的16进制表示。
解题思路：十进制转化成十六进制可以利用“除十六取余，逆序排序”法。具体而言，利用算法，用十进制数除以16得到商和余数，把余数压入栈中，再将余数除以16，如此循环下去，直至商为0的时候，将此时的余数输出，再将栈中的其他余数输出，得到的就是16进制数。
注意：当余数大于10时，要用ABCDEF来表示。在输出结果时也需要A-F，所以在算法中需要做特殊处理，可以用switch…case语句。
裁判测试程序样例：
#include <stdio.h>
#include <stdlib.h>
typedef int DataType;
struct SeqStackNode
{
int MAX; //最大容量
int top; //栈顶指针
DataType *elem; //存放元素的起始指针
};
typedef struct SeqStackNode *SeqStack;
SeqStack SetNullStack_Seq(int m) //创建空顺序栈
{
SeqStack sstack = (SeqStack)malloc(sizeof(struct SeqStackNode));
if (sstack != NULL) {
sstack->elem = (int*)malloc(sizeof(int)*m);
if (sstack->elem != NULL) {
sstack->MAX = m;
sstack->top = -1;
return(sstack);
}
else {
free(sstack);
return NULL;
}
}
else {
printf("out of space");
return NULL;
}
}
int IsNullStack_seq(SeqStack sstack)
{//判断top值是否为-1来判空，因为一般栈的首元素插入都是在‘0’位置，就像插入数组的第一位。
return(sstack->top == -1);
}
void Push_seq(SeqStack sstack, int x) //入栈
{
if (sstack->top >= (sstack->MAX - 1)) //检查栈是否满
printf("overflow!\n");
else{
sstack->top = sstack->top + 1; //若不满，先修改栈顶变量
sstack->elem[sstack->top] = x; //把元素x放到栈顶变量的位置中
}
}
void Pop_seq(SeqStack sstack) //出栈
{
if (IsNullStack_seq(sstack)) //判断栈是否为空
printf("Underflow!\n");
else
sstack->top = sstack->top - 1; //栈顶减1
}
DataType Top_seq(SeqStack sstack) //读取栈顶元素的值
{
if (IsNullStack_seq(sstack)) //判断栈是否为空
{
printf("it is empty");
return 0;
}
else
return sstack->elem[sstack->top]; //读取栈顶元素的值
}
void Hexconversion(SeqStack sstack, int n)
{
while(n) //入栈
{
Push_seq(sstack, n % 16); //余数入栈
n = n / 16; //除数
}
while(!IsNullStack_seq(sstack)) //出栈
{
switch(Top_seq(sstack)) // switch(expression)函数根据expression表达式进行判断，若expression表达式符合case 1的情况，则执行case 1后面的语句，若符合case 2 的情况则执行case 2后面的语句，直到break结束，若以上所有case都不符合，则执行default后面的语句。break结束后，跳出switch()函数体。
{
case 0:
case 1:
case 2:
case 3:
case 4:
case 5:
case 6:
case 7:
case 8:
case 9:printf("%d",sstack->elem[sstack->top]);break;
case 10:printf("A");break;
case 11:printf("B");break;
case 12:printf("C");break;
case 13:printf("D");break;
case 14:printf("E");break;
case 15:printf("F");break;
}
Pop_seq(sstack);
}
}
int main()
{
SeqStack mystack = NULL;
int n;
mystack = SetNullStack_Seq(4);
scanf("%d", &n);
Hexconversion(mystack, n);
return 0;
}
解法二：
该程序的主要思想在于：
1、设置最大可输入的十进制数
2、将十进制数转换成十六进制数后放入栈中
3、将栈中的元素一一输出，根据栈的特性，便可得到想要的十六进制数
#include <stdio.h>
#include <stdlib.h>
typedef int DataType;
struct SeqStackNode
{
int MAX;
int top;
DataType *elem;
};
typedef struct SeqStackNode *SeqStack;
SeqStack SetNullStack_Seq(int m)
{
SeqStack sstack = (SeqStack)malloc(sizeof(struct SeqStackNode));
if (sstack != NULL) {
sstack->elem = (int*)malloc(sizeof(int)*m);
if (sstack->elem != NULL) {
sstack->MAX = m;
sstack->top = -1;
return(sstack);
}
else {
free(sstack);
return NULL;
}
}
else {
printf("out of space");
return NULL;
}
}
int IsNullStack_seq(SeqStack sstack)
{
return(sstack->top == -1);
}
void Push_seq(SeqStack sstack, int x)
{
if(sstack->top + 1 == sstack->MAX)
printf("overflow!\n");
else
{
sstack->top = sstack->top + 1;
sstack->elem[sstack->top] = x;
}
}
void Pop_seq(SeqStack sstack)
{
if (IsNullStack_seq(sstack))
printf("Underflow!\n");
else
sstack->top = sstack->top - 1;
}
DataType Top_seq(SeqStack sstack)
{
if (IsNullStack_seq(sstack))
{
printf("it is empty");
return 0;
}
else
return sstack->elem[sstack->top];
}
void Hexconversion(SeqStack sstack, int n)
{
while(n)
{
Push_seq(sstack,n % 16);
n = n / 16;
}
while(!IsNullStack_seq(sstack))
{
switch(sstack->elem[sstack->top])
{
case 0:
case 1:
case 2:
case 3:
case 4:
case 5:
case 6:
case 7:
case 8:
case 9:printf("%d",sstack->elem[sstack->top]);break;
case 10:printf("A");break;
case 11:printf("B");break;
case 12:printf("C");break;
case 13:printf("D");break;
case 14:printf("E");break;
case 15:printf("F");break;
}
sstack->top = sstack->top - 1;
}
}
int main()
{
SeqStack mystack = NULL;
int n;
mystack = SetNullStack_Seq(4);
scanf("%d", &n);
Hexconversion(mystack, n);
return 0;
}
7-2 迷宫-深度策略
一个陷入迷宫的老鼠如何找到出口的问题。老鼠希望系统性地尝试所有的路径之后走出迷宫。如果它到达一个死胡同，将原路返回到上一个位置，尝试新的路径。在每个位置上老鼠可以向八个方向运动，顺序是从正东开始按照顺时针进行。无论离出口多远，它总是按照这样的顺序尝试，当到达一个死胡同之后，老鼠将进行“回溯”。迷宫只有一个入口，一个出口，设计程序要求输出迷宫的一条通路。迷宫用二维存储结构表示，1表示障碍，0表示通路；采用回溯法设计求解通路的算法。要求如下：
1、实现栈的相关操作；
2、利用栈实现回溯算法输出路径；
输入格式:
输入包括三部分：
第一个输入是迷宫大小；第二个输入是迷宫的状态；第三个输入是入口和出口位置
输出格式:
反向输出探索的路径，注意包括入口和出口位置。每个位置之间用分号;分隔。
输入样例:
9
1 1 1 1 1 1 1 1 1
1 0 0 1 1 0 1 1 1
1 1 0 0 0 0 0 0 1
1 0 1 0 0 1 1 1 1
1 0 1 1 1 0 0 1 1
1 1 0 0 1 0 0 0 1
1 0 1 1 0 0 0 1 1
1 1 1 1 1 1 1 0 1
1 1 1 1 1 1 1 1 1
1 1 7 7
输出样例:
7 7;6 6;5 7;4 6;4 5;3 4;2 5;2 4;2 3;1 2;1 1;主要思想：
1、将迷宫中所有元素标记为未走过
2、从出口开始尝试八个方向，一旦找到，就沿该方向一直走下去，并对走过的路径进行标记
3、若是出口，就将该位置入栈；若不是，就出栈
4、按照栈的特性，从出口逆着输出出来
实现流程：
(1) 创建两个空栈StackX和StackY。
(2) 将入口entryX和entryY分别压入栈StackX和StackY中。
(3) While(栈不空)
①取栈顶元素，出栈，当前位置为栈顶元素；
②while(mov<8)，即还存在探索的方向。
a. 按照顺时针依次探索各个位置(posX,posY)
b. 按照(posX,posY)是出口，输出路径，返回1；
c. 如果(posX,posY)是没有走过的通路
l 设置标志位mark[posX][posY]=1。
l 当前位置进栈。
l 将(posX,posY)设置为当前位置；
l 设置mov=0。
d. 否则（如果(X,Y)是没有走过的通路），mov++。
#include<stdio.h>
#include<stdlib.h>
typedef int DataType;
struct Maze //迷宫
{
int size;
DataType** data;
};
typedef struct Maze *SeqQueue;
struct Node //节点
{
DataType data;
struct Node* next;
};
typedef struct Node *LinkStack;
typedef struct Node *PNode;
SeqQueue SetNullQueue_seq(int m)
{
SeqQueue squeue;
squeue = (SeqQueue)malloc(sizeof(struct Maze));
if (squeue == NULL)
{
printf("Alloc failure\n");
return NULL;
}
squeue->data = (int**)malloc(sizeof(DataType*)*m); //申请指针数组（不是数组指针）int *，既然是指针数组，存放的都是指针，就可以在此基础上继续开辟m个内存空间。注意：这种方法每一行元素地址连续，但是不能保证上一行的尾和下一行的开头连续。
if (squeue->data != NULL)
{
squeue->size = m;
for(int i = 0; i<m; i++)
squeue->data[i] = (int*)malloc(sizeof(int)*m); //再申请内存空间
return squeue;
}
}
LinkStack SetNullStack_Link()
{
LinkStack top = (LinkStack)malloc(sizeof(LinkStack));
if (top != NULL)
top->next = NULL;
else printf("Alloc failure");
return top;
}
int IsNullStack_link(LinkStack top)
{
if (top->next == NULL)
return 1;
else
return 0;
}
void Push_link(LinkStack top, DataType x)
{
PNode p;
p = (PNode)malloc(sizeof(struct Node));
if (p == NULL)
printf("Alloc failure");
else
{
p->data = x;
p->next = top->next;
top->next = p;
}
}
void Pop_link(LinkStack top)
{
PNode p;
if (top->next == NULL)
printf("it is empty stack!");
else
{
p = top->next;
top->next = p->next;
free(p);
}
}
DataType Top_link(LinkStack top)
{
if (top->next == NULL)
{
printf("It is empty stack!");
return 0;
}
else
return top->next->data;
}
int main()
{
int size;
scanf("%d",&size);
SeqQueue maze = SetNullQueue_seq(size);
for(int i = 0;i<maze->size;i++)
{
for(int j = 0;j<maze->size;j++)
scanf("%d",&maze->data[i][j]);
}
int entryX,entryY,exitX,exitY; //迷宫入口、出口
scanf("%d %d %d %d",&entryX,&entryY,&exitX,&exitY);
int direction[8][2] = {{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1}};
LinkStack linkStackX = NULL; //两个栈，分别保存路径中点（x，y）值
LinkStack linkStackY = NULL;
int posX,posY;
int preposX,preposY;
int **mark; //标记二维数组，标记哪些点走过，不再重复走
int mov; //移动的方向
mark = (int**)malloc(sizeof(int*)*maze->size); // 给做标记的二维数组分配空间，并赋初值
for(int i = 0; i<maze->size; i++)
mark[i] = (int*)malloc(sizeof(int)*maze->size);
for(int i = 0; i<maze->size; i++)
{
for(int j = 0; j<maze->size; j++)
mark[i][j] = 0; //给所有元素设置初值
}
linkStackX = SetNullStack_Link();//初始化栈
linkStackY = SetNullStack_Link();//初始化栈
mark[entryX][entryY] = 1; //入口点设置标志位
Push_link(linkStackX,entryX); //入口点入栈
Push_link(linkStackY,entryY); //入口点入栈
while(!IsNullStack_link(linkStackX)) //如果栈不为空
{
preposX = Top_link(linkStackX); //读取栈顶元素
preposY = Top_link(linkStackY); //读取栈顶元素
Pop_link(linkStackX); //弹出栈顶元素
Pop_link(linkStackY); //弹出栈顶元素
mov = 0;
while(mov < 8)
{
posX = preposX + direction[mov][0];
posY = preposY + direction[mov][1];
if(posX == exitX && posY == exitY) //到达终点
{
Push_link(linkStackX,preposX); //出口点入栈
Push_link(linkStackY,preposY); //出口点入栈
printf("%d %d;",exitX,exitY);
while(!IsNullStack_link(linkStackX)) //将路径逆序输出
{
posX = Top_link(linkStackX);
posY = Top_link(linkStackY);
Pop_link(linkStackX);
Pop_link(linkStackY);
printf("%d %d;",posX,posY);
}
return 0;
}
if(maze->data[posX][posY] == 0 && mark[posX][posY] == 0) //新位置可走，并且未被探索过
{
mark[posX][posY] = 1;
Push_link(linkStackX,preposX);
Push_link(linkStackY,preposY);
preposX = posX;
preposY = posY;
mov = 0; //已经往前走了，因此方向重新从0号方向开始搜索
}
else
mov++; //换个方向试试
}
}
return 0;
}7-2 迷宫-广度策略
一个陷入迷宫的老鼠如何找到出口的问题。老鼠希望系统性地尝试所有的路径之后走出迷宫。如果它到达一个死胡同，将原路返回到上一个位置，尝试新的路径。在每个位置上老鼠可以向八个方向运动，顺序是从正东开始按照顺时针进行。无论离出口多远，它总是按照这样的顺序尝试，当到达一个死胡同之后，老鼠将进行“回溯”。迷宫只有一个入口，一个出口，设计程序要求输出迷宫的一条通路。迷宫采用二维存储结构表示，1表示障碍，0表示通路；要求如下： 1、实现队列的相关操作； 2、利用队列进行广度策略搜索算法输出路径；
输入格式:
输入包括三部分： 第一个输入是迷宫大小；第二个输入是迷宫的状态；第三个输入是入口和出口位置
输出格式:
反向输出探索的路径，注意包括入口和出口位置。每个位置之间用分号;分隔。
输入样例:
9
1 1 1 1 1 1 1 1 1
1 0 0 1 1 0 1 1 1
1 1 0 0 0 0 0 0 1
1 0 1 0 0 1 1 1 1
1 0 1 1 1 0 0 1 1
1 1 0 0 1 0 0 0 1
1 0 1 1 0 0 0 1 1
1 1 1 1 1 1 1 0 1
1 1 1 1 1 1 1 1 1
1 1 7 7
输出样例:
7 7;6 6;5 6;4 5;3 4;2 3;1 2;1 1;解题思路：
1.创建两个空队列LinkQueueX和LinkQueueX
2.将入口entreX和entryY分别压入队列LinkQueueX和LinkQueueX。
3.当队列不空
①取队头元素，出队
②for(mov=0;mov<8;mov++),即还存在可以探索的相邻的方向。
a.按照顺时针依次探索各个位置（X,Y）。
b.如果（posX,posY）是出口，则输出路径，返回。
c.如果（posX,posY）是没有走过的通路；
设置标志位mark[posX][posY]=1。
当前位置入队。
记录前驱位置，方便输出路径。
#include<stdio.h>
#include<stdlib.h>
typedef int DataType;
struct Maze //迷宫
{
DataType** data;
int size;
};
typedef struct Maze *SeqQueue;
struct Node //节点
{
DataType data;
struct Node* next;
};
typedef struct Node *PNode;
struct Queue //对列
{
PNode f;
PNode r;
};
typedef struct Queue *LinkQueue;
SeqQueue SetNullQueue_seq(int m)
{
SeqQueue squeue;
squeue = (SeqQueue)malloc(sizeof(struct Maze));
if (squeue == NULL)
{
printf("Alloc failure\n");
return NULL;
}
squeue->data = (int**)malloc(sizeof(DataType*)*m); //申请指针数组（不是数组指针）int *，既然是指针数组，存放的都是指针，就可以在此基础上继续开辟m个内存空间。注意：这种方法每一行元素地址连续，但是不能保证上一行的尾和下一行的开头连续。
if (squeue->data != NULL)
{
squeue->size = m;
for(int i = 0;i<m;i++)
squeue->data[i] = (int*)malloc(sizeof(DataType)*m); //再申请内存空间
return squeue;
}
}
LinkQueue SetNullQueue_Link()
{
LinkQueue lqueue;
lqueue = (LinkQueue)malloc(sizeof(struct Queue));
if (lqueue != NULL)
{
lqueue->f = NULL;
lqueue->r = NULL;
}
else
printf("Alloc failure! \n");
return lqueue;
}
int IsNullQueue_link(LinkQueue lqueue)
{
return (lqueue->f == NULL);
}
void EnQueue_link(LinkQueue lqueue, DataType x)
{
PNode p;
p = (PNode)malloc(sizeof(struct Node));
if (p == NULL)
printf("Alloc failure!");
else {
p->data = x;
p->next = NULL;
if (lqueue->f == NULL)
{
lqueue->f = p;
lqueue->r = p;
}
else
{
lqueue->r->next = p;
lqueue->r = p;
}
}
}
void DeQueue_link(LinkQueue lqueue)
{
struct Node * p;
if (lqueue->f == NULL)
printf("It is empty queue!\n ");
else
{
p = lqueue->f;
lqueue->f = lqueue->f->next;
free(p);
}
}
DataType FrontQueue_link(LinkQueue lqueue)
{
if (lqueue->f == NULL)
{
printf("It is empty queue!\n");
}
else
return (lqueue->f->data);
}
int main()
{
int size;
scanf("%d",&size);
SeqQueue maze = SetNullQueue_seq(size);
for(int i = 0;i<maze->size;i++)
{
for(int j = 0;j<maze->size;j++)
scanf("%d",&maze->data[i][j]);
}
int entryX,entryY,exitX,exitY; //迷宫入口、出口
scanf("%d %d %d %d",&entryX,&entryY,&exitX,&exitY);
int direction[8][2] = {{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1}};
LinkQueue linkQueueX = NULL; //两个对列，分别保存路径中点（x，y）值
LinkQueue linkQueueY = NULL;
int posX,posY;
int preposX,preposY;
int** preposMarkX; //记录迷宫行走过程中的前驱
int** preposMarkY;
int **mark; //标记二维数组，标记哪些点走过，不再重复走
int i,j,mov;
preposMarkX = (int**)malloc(sizeof(int*) * maze->size); //给存放前驱x值的数组分配空间
for(i = 0; i<maze->size; i++)
{
preposMarkX[i] = (int*)malloc(sizeof(int)*maze->size);
}
preposMarkY = (int**)malloc(sizeof(int*) * maze->size); //给存放前驱y值的数组分配空间
for(i = 0; i<maze->size; i++)
{
preposMarkY[i] = (int*)malloc(sizeof(int)*maze->size);
}
mark = (int**)malloc(sizeof(int*) * maze->size); //给标记二维数组分配空间，并赋初值
for(i = 0; i<maze->size; i++)
{
mark[i] = (int*)malloc(sizeof(int)*maze->size);
}
for(i = 0; i<maze->size; i++) //给所有元素赋初值
{
for(j = 0; j<maze->size; j++)
{
preposMarkX[i][j] = -1;
preposMarkY[i][j] = -1;
mark[i][j] = 0;
}
}
linkQueueX = SetNullQueue_Link(); //创建空队列
linkQueueY = SetNullQueue_Link(); //
EnQueue_link(linkQueueX,entryX); //迷宫入口入队
EnQueue_link(linkQueueY,entryY); //
mark[entryX][entryY] = 1; //入口点设置标志位，表示已被探索过。
while(!IsNullQueue_link(linkQueueX)) //如果队列不为空，且没有找到迷宫出口点
{
preposX = FrontQueue_link(linkQueueX); //取队头
DeQueue_link(linkQueueX); //出队/弹出
preposY = FrontQueue_link(linkQueueY); //取队头
DeQueue_link(linkQueueY); //出队/弹出
for(mov = 0;mov<8;mov++) //将与当前点相邻接且满足一定条件的点放入队列
{
posX = preposX + direction[mov][0];
posY = preposY + direction[mov][1];
if(posX == exitX && posY == exitY) //到达出口点
{
preposMarkX[posX][posY] = preposX;
preposMarkY[posX][posY] = preposY;
printf("%d %d;",posX,posY);
//将路径逆序输出
while(!(posX == entryX && posY == entryY)) //未到达入口，则继续往前寻找前驱
{
preposX = preposMarkX[posX][posY];
preposY = preposMarkY[posX][posY];
posX = preposX;
posY = preposY;
printf("%d %d;",posX,posY);
}
return 0;
}
if(maze->data[posX][posY] == 0 && mark[posX][posY] == 0) //如果能走，且没有被扩展过（此处体现广度优先）
{
EnQueue_link(linkQueueX,posX);
EnQueue_link(linkQueueY,posY);
mark[posX][posY] = 1;
preposMarkX[posX][posY] = preposX;
preposMarkY[posX][posY] = preposY;
}
}
}
return 0;
}7-3 农夫过河-广度策略
一个农夫带着一只狼、一只羊和一棵白菜，身处河的南岸。他要把这些东西全部运到北岸。遗憾的是他只有一只小船，小船只能容下他和一件物品。这里只能是农夫来撑船。同时因为狼吃羊，而羊吃白菜，所以农夫不能留下羊和狼或者羊和白菜单独在河的一边，自己离开。好在狼属于肉食动物，不吃白菜。农夫怎样才能把所有的东西安全运过河呢？
为了表示每个物品的位置，采用二进制位来区分南岸和北岸，0表示在南岸，1表示在北岸。用四个二进制位XXXX分别表示农夫、狼、菜和羊四个物品所在的位置。例如1110表示农夫、狼和菜在北岸，菜在南岸。农夫过河问题的初始状态为0000，结束状态为1111。
输入格式:
无输入
输出格式:
输出农夫移动物品的中间状态的逆序
输入样例:
输出样例:
15 6 14 2 11 1 9 0 题目：一个农夫带着一只狼、一只羊和一棵白菜，身处河的南岸。他要把这些东西全部运到北岸。遗憾的是他只有一只小船，小船只能容下他和一件物品。这里只能是农夫来撑船。同时因为狼吃羊，而羊吃白菜，所以农夫不能留下羊和狼或者羊和白菜单独在河的一边，自己离开。好在狼属于肉食动物，不吃白菜。农夫怎样才能把所有的东西安全运过河呢？ 为了表示每个物品的位置，采用二进制位来区分南岸和北岸，0表示在南岸，1表示在北岸。用四个二进制位XXXX分别表示农夫、狼、菜和羊四个物品所在的位置。例如1110表示农夫、狼和菜在北岸，菜在南岸。农夫过河问题的初始状态为0000，结束状态为1111。
审题：使用顺序队列算法。
程序设计思想：
1、从起点开始，用十六进制数一一穷举
2、判断穷举出的元素是否符合安全且不重复
3、将符合的元素放入队列中并一一输出出来
实现流程：
(1) 初始状态0000入队
(2) 当队列不空且没有到达结束状态1111时循环以下操作：
①队头状态出队。
②按照农夫一个人走、农夫分别带上3个走循环以下操作：
l 如果农夫和他们在同一岸，则计算新的状态。
l 如果新的状态是安全的并且是没有处理过的，则更新status[ ]，并将新状态入队。
③当状态为1111时逆向输出staus[ ]数组。
需要注意的是状态能否入队，要判断以下3条，满足任何一条都不能入队。
u 不可能：通过判断是否在同一岸；
u 不安全：通过安全函数判断；
u 处理过：记录处理过的状态。
#include<stdio.h>
#include<stdlib.h>
//四者的位置为农夫 狼 白菜 羊
typedef char DataType;
struct Queue //队列
{
int Max;
int f;
int r;
DataType *elem;
};
typedef struct Queue *SeqQueue;
struct Node //结点
{
DataType data;
struct Node* next;
};
typedef struct Node *PNode;
SeqQueue SetNullQueue_seq(int m)
{
SeqQueue squeue;
squeue = (SeqQueue)malloc(sizeof(struct Queue));
if (squeue == NULL)
{
printf("Alloc failure\n");
return NULL;
}
squeue->elem = (char*)malloc(sizeof(DataType)*m);
if (squeue->elem != NULL)
{
squeue->Max = m;
squeue->f = 0;
squeue->r = 0;
return squeue;
}
}
int IsNullQueue_seq(SeqQueue squeue)
{
return (squeue->f == squeue->r);
}
void EnQueue_seq(SeqQueue squeue, DataType x)
{
if((squeue->r+1)%(squeue->Max) == (squeue->f))
printf("It is FULL Queue!");
else{
squeue->elem[squeue->r] = x;
squeue->r = (squeue->r+1) % (squeue->Max);
}
}
void DeQueue_seq(SeqQueue squeue)
{
if(IsNullQueue_seq(squeue))
printf("It is empty queue!");
else
{
squeue->f = (squeue->f+1) %(squeue->Max);
}
}
DataType FrontQueue_seq(SeqQueue squeue)
{
DataType result;
if(IsNullQueue_seq(squeue))
printf("It is empty queue!");
else
return squeue->elem[squeue->f];
}
int FarmerOnRight(int status) //判断当前状态下农夫是否在右岸
{
return (0 != (status & 0x08)); // status为int型（2个字节，16位），0000 1000，&为按位与操作
}
int WolfOnRight(int status) //判断当前状态下狼是否在右岸
{
return (0 != (status & 0x04)); //0000 0100
}
int CabbageOnRight(int status) //判断当前状态下白菜是否在右岸
{
return (0 != (status & 0x02)); //0000 0010
}
int GoatOnRight(int status) //判断当前状态下羊是否在右岸
{
return (0 != (status & 0x01)); //0000 0001
}
int IsSafe(int status)
{
if((GoatOnRight(status) == CabbageOnRight(status)) && (GoatOnRight(status) != FarmerOnRight(status)))
return (0); /* 羊吃白菜*/
if((GoatOnRight(status) == WolfOnRight(status)) && (GoatOnRight(status) != FarmerOnRight(status)))
return (0); /* 狼吃羊*/
return (1); /* 其他状态是安全的*/
}
int main()
{
int i,movers,nowstatus,newstatus;
int status[16]; //用于记录已考虑的状态路径
SeqQueue moveTo; //用于记录可以安全到达的中间状态
moveTo = SetNullQueue_seq(20); //创建空队列
EnQueue_seq(moveTo,0x00); //初始状态时所有物品在右岸，初始状态0000入队
for(i = 0;i<16;i++) //数组status初始化为-1
status[i] = -1;
status[0] = 0;
while(!IsNullQueue_seq(moveTo) && (status[15] == -1)) //队列非空且没有到达结束状态
{
nowstatus = FrontQueue_seq(moveTo); //取队头状态为当前状态
DeQueue_seq(moveTo);
for(movers = 1;movers<=8;movers <<= 1) //遍历三个要移动物品，<<=为左移运算
//考虑各种物品移动
if((0 != (nowstatus & 0x08)) == (0 != (nowstatus & movers))) //农夫与移动的物品在同一侧
{
newstatus = nowstatus ^ (0x08|movers); //计算新状态。^为按位异或运算操作符，相同为0、相异为1；|为按位或运算操作符，只要有1就是1，两个都是0才是0。
if(IsSafe(newstatus) && (status[newstatus] == -1)) //新状态是安全的且之前没有出现过
{
status[newstatus] = nowstatus; //记录新状态
EnQueue_seq(moveTo,newstatus); //新状态入队
}
}
}
if(status[15] != -1) //到达最终状态，输出经过的状态路径
{
for(nowstatus = 15;nowstatus >= 0;nowstatus = status[nowstatus])
{
printf("%d ",nowstatus);
if(nowstatus == 0)
exit(0);
}
}
else
printf("No solution.\n"); //问题无解
return 0;
}7-4 "聪明的学生"
问题描述：一位逻辑学的教授有三个非常聪明善于推理且精于心算的学生，Alice、Bob和Charles。一天教授给他们出了一个题。教授在每个人脑门上帖了一个纸条，每个纸条上写了一个正整数，Alice、Bob和Charles分别是3，5，8，并且告诉学生某两个数的和等于第三个，每个学生只能看见另外两个同学头上的正整数，但是看不见自己的。
教授问的顺序是Alice---Bob—Charles—Alice……经过几次提问后，当教授再次询问到Charles时，Charles露出了得意的笑容，准确的报出了自己头上的数。
输入格式:
本题输入为Alice、Bob和Charles头上的数字
输出格式:
教授在第几次提问时，轮到回答问题的那个人猜出了自己头上的数（要求用递归程序解决）。
输入样例:
在这里给出一组输入。例如：
3,5,8
输出样例:
在这里给出相应的输出。例如：
6
#include<stdio.h>
#include<stdlib.h>
int step(int t1,int t2) //找出t1到t2的最小提问次数
{
if(t2 > t1)
return t2 - t1;
else
return t2 + 3 - t1;
}
int times(int i,int j,int t1,int t2,int t3) //教授提问多少次时t3能够回答
{
int k;
k = i - j;
if(k == 0)
{
return t3;
}
if(k > 0)
{
return times(j,i-j,t2,t3,t1) + step(t1,t3);
}
if(k < 0)
{
return times(i,j-i,t1,t3,t2) + step(t2,t3);
}
}
int main()
{
int result;
int a = 1,b = 2,c = 3;
int arr[3];
scanf("%d,%d,%d",&arr[0],&arr[1],&arr[2]);
int index = 0;
int max_num = -1,mid_num = -1; //保留存储第一大和第二大的数
int max_index = -1, mid_index = -1; //保留存储第一大和第二大数的下标
for(;index < 3;index++) //找到第一大和第二大数及其下标
{
if(max_num < arr[index])
{
mid_num = max_num;
mid_index = max_index;
max_num = arr[index];
max_index = index;
}
if(mid_num <arr[index] && arr[index] != max_num)
{
mid_num = arr[index];
mid_index = index;
}
}
c = max_index + 1; //将0-based转换为1-based，c为最大值编号，b为中间值编号
b = mid_index + 1;
if((c == 1 && b == 2) || (c == 2 && b == 1)) //根据取值大小间的关系，确立a取值
a = 3;
else if((c == 2 && b == 3) || (c == 3 && b == 2))
a = 1;
else
a = 2;
//调用递归函数，第一个参数为最小数，第二个参数为中间数
//a为最小值编号，b为中间值编号，c为最大值编号
result = times(arr[a-1],arr[b-1],a,b,c);
printf("%d",result);
return 0;
}