1、 题目： 问题描述：在某操作系统中打开了 N 个窗口,每个窗口都是一个矩形区域。窗口之间有层次的区别,在多于一个窗口重叠的区域里,只会显示位于顶层的窗口里的内容。当你点击屏幕上一个点的时候,你就选择了处于被点击位置的最顶层窗口,并且这个窗口就会被移到所有窗口的最顶层,而剩余的窗口的层次顺序不变。如果你点击的位置不属于任何窗口,则系统会忽略你这次点击。现在我们希望你写一个程序模拟点击窗口的过程 算法思想： 由于在某一次点开的网页所在的层数我们是不知道的，因此这道题并不方便采用栈或者队列，由于这里涉及到了较多的删除，插入操作，所以最终我决定采用链表来处理这道题，我用了一个链表来进行网页的存储，链表里面包含了网页的层数和位置信息，然后我们来用遍历的方式来判断点击的网页，如果找到了点击的网页，那么我们就将这个网页先从链表中拆下来，然后插入到头节点后面，如果点击的位置没有对应的网页，那么我们就输出IGNORED。 当然我们的输出没有阳按照老师的样例程序进行，因为考虑到，我们在输入信息时，需要一些提示性信息，比如，"请输入网页数量N，和操作次数M: "，"请依次输入x1,y1,x2,y2: \n"等等。 我们算法的空间复杂度为：O(n)，因为取决于我们所输入的网页的数量n，我们算法的时间复杂度为：O(mn)，因为每一次操作都需要遍历这个链表，一共有m次操作，那么最坏的情况就是每一次都是需要完全遍历，那么就是需要比较次mn，因此们算法的时间复杂度为：O(mn) 运行结果：
结果分析： 结果是正确的，除了我的输出结果有一些提示性信息以外，都和老师的要求是吻合的，当然这些提示性信息并不影响。 附源程序：
#include "stdlib.h" #include "math.h" #include "stdio.h" typedef struct node { int x1; int y1; int x2; int y2; int num; //网页的编号 struct node *next; }LI; void Get_page(LI *T,int x,int y); //输入链表T，鼠标点击位置x，y得到应该的网页编号，并且改变他的位置 main() { LI *A,*q; int x1,x2,y1,y2; //给网页赋值 int N,M,i; //N为网页数量，M为操作次数，i用来生成N个网页以及遍历所有鼠标点击位置 int x,y; //鼠标点击的位置 A = (LI*)malloc(sizeof(LI)); A->next = NULL; printf("请输入网页数量N，和操作次数M: "); scanf("%d%d",&N,&M); for(i = 1;i <= N; i++) { q = (LI*)malloc(sizeof(LI)); printf("请依次输入x1,y1,x2,y2: \n"); scanf("%d%d%d%d",&x1,&y1,&x2,&y2); if(x1>=x2) { printf("x2要比x1大!\n"); exit(0); } else if(y1>=y2) { printf("y2要比y1大!\n"); exit(0); } else { printf(" \"上方是编号为%d的窗口\"\n",i); q->x1 = x1; q->x2 = x2; q->y1 = y1; q->y2 = y2; q->num = i; } q->next = A->next; A->next = q; } for(i = 1;i <=M ;i++) { printf("请输入鼠标点击位置x,y: "); scanf("%d%d",&x,&y); Get_page(A,x,y); } } void Get_page(LI *T,int x,int y) { LI *p,*p1; LI *q; p1 = T; p = p1->next; while(p) { if((x >= p->x1 )&&(x <= p->x2 )&&(y >= p->y1 )&&(y <= p->y2 )) { printf("%d\n",p->num); q = p; p1->next = p->next; q->next = T->next; T->next = q; break; } else { p1 = p; p = p->next; } } if(p == NULL) printf("IGNORED"); }2、 题目： 利用栈模拟实现N个盘子的汉诺塔问题（非递归算法实现） 算法思想： 1、将1号盘子按照顺时针顺序从当前栈移动到下一个栈(从当前站pop，然后push进下一个栈)，sum++,如果sum已经等于，结束; 2、观察没有1号盘子的那两个栈 -如果其中一个为空，那么将另一个非空栈的栈顶盘子移动到这个空栈 上; -如果两个都不，那么看谁的栈顶的盘子比较小把小盘子移动到栈顶盘子较大的那个栈上; -之后，sum++，如果sum已经达到数量，结束.否则继续执行第1步 总的思路很简单，就是按照老师ppt上面给的思路写就行了，因为有了老师的思路，所以没有什么难度。空间复杂度为：O(n)，取决于汉诺塔中圆盘的数量，算法的时间复杂度为：O(2的n次方)，因为我们需要对其中的圆盘进行次2^n-1的移动。
运行结果： N = 2；
N = 3
N = 4
结果分析： 结构运行非常正确，而且在不是很大的前提下，我们速度还是可以的，但是由于我们的算法的时间复杂度为：，所以当较大时，算法还是比较慢的。 附源程序:
void hanio(ST *T,int n)//移动盘子的时候要输出将几号盘子从哪儿移动到了哪儿 { int sum=0,k=pow(2,n)-1,i=0; while(1) { sum++; printf("Step %d : Plate %d From %c To %c\n",sum,gettop(&T[i%3]),T[i].name,T[(i+1)%3].name); push(&T[(i+1)%3],pop(&T[i])); i = (i+1)%3; if (sum==k) break; sum++; if (isempty(&T[(i+1)%3])) { printf("Step %d : Plate %d From %c To %c\n",sum,gettop(&T[(i+2)%3]),T[(i+2)%3].name,T[(i+1)%3].name); push(&T[(i+1)%3],pop(&T[(i+2)%3])); } else if (isempty(&T[(i+2)%3])) { printf("Step %d : Plate %d From %c To %c\n",sum,gettop(&T[(i+1)%3]),T[(i+1)%3].name,T[(i+2)%3].name); push(&T[(i+2)%3],pop(&T[(i+1)%3])); } else if (gettop(&T[(i+1)%3])<gettop(&T[(i+2)%3])) { printf("Step %d : Plate %d From %c To %c\n",sum,gettop(&T[(i+1)%3]),T[(i+1)%3].name,T[(i+2)%3].name); push(&T[(i+2)%3],pop(&T[(i+1)%3])); } else { printf("Step %d : Plate %d From %c To %c\n",sum,gettop(&T[(i+2)%3]),T[(i+2)%3].name,T[(i+1)%3].name); push(&T[(i+1)%3],pop(&T[(i+2)%3])); } } }题目：（关于迷宫四个情况判断的写法是在王铭宇同学的帮助下写出来的，因为在写这道题的时候还没有讲队列和这种题目的思路，所以询问了他人，但是现在我可以自己独立写出来了） 根据给定的迷宫入口和出口位置，利用队列，输出迷宫中的所有最短路径，以及路径长度（路径中包含的点的数量） 算法思想： 我用队列来寻找最短路径，我的队列中存储点的坐标,以及该队列的头部和尾部，让后开始从初始位置开始走，他有四个方向可以选择，我们就把可行的都存到队列中去，然后找出最先到达目标位置的，然后我们之前用了一共数组来存储每一步的上一步的标号，我们只需要遍历一下这个数组就可以得到我们的最短路径了。由于我们需要存储我们的位置坐标,而他们的数量由点的个数来确定，所以我们的空间复杂度为：O(n2)，我们的时间复杂度为：O(n2)，因为可能会遍历迷宫中所有的点。 运行结果：
结果分析： 运行结果是正确的，就是我们的最短路径，我所采用的算法可以找到这条最短路径，但是存在一共问题，就是如果最短路径不唯一，那么我们如何找到所有的最短路径呢，我想我们可以用栈来解决，由于这道题要求是队列，所以就不往下考虑了。 附源代码：
#include "stdio.h" #include "stdlib.h" #include "math.h" #define start_x 1//入口行号 #define start_y 1//入口列号 #define end_x 8//出口行号 #define end_y 8//出口列号 #define N 100 int mg[10][10]={ {1,1,1,1,1,1,1,1,1,1}, {1,0,0,1,0,0,0,1,0,1}, {1,0,0,1,0,0,0,1,0,1}, {1,0,0,0,0,1,1,0,0,1}, {1,0,1,1,1,0,0,0,0,1}, {1,0,0,0,1,0,0,0,0,1}, {1,0,1,0,0,0,1,0,0,1}, {1,0,1,1,1,0,1,1,0,1}, {1,1,0,0,0,0,0,0,0,1}, {1,1,1,1,1,1,1,1,1,1}, };//用二维数组表示迷宫，“0”表示该点可行，“1”表示该点不可行 typedef struct queue { int x[N],y[N]; int front; int rear; }MG; void initial(MG *M); //初始化队列MG void Queue(MG *M); void Push(MG *M,int i,int j); //入队操作 void show(int a[],int b[],int n); int main() { MG M; //队列 initial(&M); Queue(&M); } void initial(MG *M) { M->x[0]=start_x; M->y[0]=start_y; M->front=0; M->rear=M->front+1; mg[start_x][start_y]=1; } void Push(MG *M,int i,int j) { if(M->front==(M->rear+1)) { printf("队列已经满了，不能再插入数据!"); exit(0); } M->x[M->rear]=i; M->y[M->rear]=j; M->rear++; } void Queue(MG *M) { int i,j,i1,j1; //i,j来遍历整个迷宫；i1，j1用来判断行走的四个方向 int next,step=-1,active=0; int save_x[N],save_y[N]; //保存路径 for(i=start_x,j=start_y;i!=end_x || j!=end_y;) { if(step==-1 || active!=0) M->front=M->rear; //第一步和上一步寻找到可行点时更新队头元素 active=0; if(save_x[step]!=i || save_y[step]!=j) //当此时的路径与上一步的路径不一样时保存路径 { step++; save_x[step]=i; save_y[step]=j; } else //否则说明上一步路径出错，删除上一步的路径 step--; for(next=0;next<4;next++) { switch(next) { case 0: //向前 i1=i; j1=j+1; break; case 1: //向后 i1=i; j1=j-1; break; case 2: //向上 j1=j; i1=i-1; break; case 3: //向下 j1=j; i1=i+1; break; } if(mg[i1][j1]==0) //某个方向可行时将其加入队列 { Push(M,i1,j1); mg[i1][j1]=1; active=1; } } if(active==1) //若有可行方向则选取最后一个可行方向前进 { i=M->x[(M->rear)-1]; j=M->y[(M->rear)-1]; } else //未找到可行方向就将队头回溯到上一条路径 { M->front--; i=M->x[M->front]; j=M->y[M->front]; } } step++; save_x[step]=end_x; //最后将出口加入队列 save_y[step]=end_y; step++; show(save_x,save_y,step); } void show(int a[],int b[],int n) { int i; printf("走出迷宫的最短路径为：\n"); for(i=0;i<n;i++) { printf("(%d,%d) ",a[i],b[i]); if(i<n-1) printf("-->"); } printf("\n结点数为%d",n); printf("\n\n"); }