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");elsesstack->top = sstack->top - 1; //栈顶减1
}DataType Top_seq(SeqStack sstack) //读取栈顶元素的值
{if (IsNullStack_seq(sstack)) //判断栈是否为空{printf("it is empty");return 0;}elsereturn 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");elsesstack->top = sstack->top - 1;
}
DataType Top_seq(SeqStack sstack)
{if (IsNullStack_seq(sstack)){printf("it is empty");return 0;}elsereturn 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;elsereturn 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;}elsereturn 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号方向开始搜索}elsemov++; //换个方向试试}}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;}elseprintf("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");}elsereturn (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!");elsereturn 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初始化为-1status[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);}}elseprintf("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;elsereturn 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;elsea = 2;
//调用递归函数，第一个参数为最小数，第二个参数为中间数
//a为最小值编号，b为中间值编号，c为最大值编号 result = times(arr[a-1],arr[b-1],a,b,c);printf("%d",result);return 0;
}
