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");
}
文章浏览阅读1k次。通过使用ajax方法跨域请求是浏览器所不允许的,浏览器出于安全考虑是禁止的。警告信息如下:不过jQuery对跨域问题也有解决方案,使用jsonp的方式解决,方法如下:$.ajax({ async:false, url: 'http://www.mysite.com/demo.do', // 跨域URL ty..._nginx不停的xhr
文章浏览阅读2k次。关于在 Oracle 中配置 extproc 以访问 ST_Geometry,也就是我们所说的 使用空间SQL 的方法,官方文档链接如下。http://desktop.arcgis.com/zh-cn/arcmap/latest/manage-data/gdbs-in-oracle/configure-oracle-extproc.htm其实简单总结一下,主要就分为以下几个步骤。..._extproc
文章浏览阅读1.5w次。linux下没有上面的两个函数,需要使用函数 mbstowcs和wcstombsmbstowcs将多字节编码转换为宽字节编码wcstombs将宽字节编码转换为多字节编码这两个函数,转换过程中受到系统编码类型的影响,需要通过设置来设定转换前和转换后的编码类型。通过函数setlocale进行系统编码的设置。linux下输入命名locale -a查看系统支持的编码_linux c++ gbk->utf8
文章浏览阅读750次。今天准备从生产库向测试库进行数据导入,结果在imp导入的时候遇到“ IMP-00009:导出文件异常结束” 错误,google一下,发现可能有如下原因导致imp的数据太大,没有写buffer和commit两个数据库字符集不同从低版本exp的dmp文件,向高版本imp导出的dmp文件出错传输dmp文件时,文件损坏解决办法:imp时指定..._imp-00009导出文件异常结束
文章浏览阅读143次。当下是一个大数据的时代,各个行业都离不开数据的支持。因此,网络爬虫就应运而生。网络爬虫当下最为火热的是Python,Python开发爬虫相对简单,而且功能库相当完善,力压众多开发语言。本次教程我们爬取前程无忧的招聘信息来分析Python程序员需要掌握那些编程技术。首先在谷歌浏览器打开前程无忧的首页,按F12打开浏览器的开发者工具。浏览器开发者工具是用于捕捉网站的请求信息,通过分析请求信息可以了解请..._初级python程序员能力要求
文章浏览阅读7.6k次,点赞2次,收藏6次。@Service标注的bean,类名:ABDemoService查看源码后发现,原来是经过一个特殊处理:当类的名字是以两个或以上的大写字母开头的话,bean的名字会与类名保持一致public class AnnotationBeanNameGenerator implements BeanNameGenerator { private static final String C..._@service beanname
文章浏览阅读6.9w次,点赞73次,收藏463次。1.前序创建#include<stdio.h>#include<string.h>#include<stdlib.h>#include<malloc.h>#include<iostream>#include<stack>#include<queue>using namespace std;typed_二叉树的建立
文章浏览阅读7.1k次。在Asp.net上使用Excel导出功能,如果文件名出现中文,便会以乱码视之。 解决方法: fileName = HttpUtility.UrlEncode(fileName, System.Text.Encoding.UTF8);_asp.net utf8 导出中文字符乱码
文章浏览阅读2.1k次,点赞4次,收藏23次。第一次实验 词法分析实验报告设计思想词法分析的主要任务是根据文法的词汇表以及对应约定的编码进行一定的识别,找出文件中所有的合法的单词,并给出一定的信息作为最后的结果,用于后续语法分析程序的使用;本实验针对 PL/0 语言 的文法、词汇表编写一个词法分析程序,对于每个单词根据词汇表输出: (单词种类, 单词的值) 二元对。词汇表:种别编码单词符号助记符0beginb..._对pl/0作以下修改扩充。增加单词
文章浏览阅读773次。我在使用adb.exe时遇到了麻烦.我想使用与bash相同的adb.exe shell提示符,所以我决定更改默认的bash二进制文件(当然二进制文件是交叉编译的,一切都很完美)更改bash二进制文件遵循以下顺序> adb remount> adb push bash / system / bin /> adb shell> cd / system / bin> chm..._adb shell mv 权限
文章浏览阅读6.8k次,点赞12次,收藏125次。1. 单目相机标定引言相机标定已经研究多年,标定的算法可以分为基于摄影测量的标定和自标定。其中,应用最为广泛的还是张正友标定法。这是一种简单灵活、高鲁棒性、低成本的相机标定算法。仅需要一台相机和一块平面标定板构建相机标定系统,在标定过程中,相机拍摄多个角度下(至少两个角度,推荐10~20个角度)的标定板图像(相机和标定板都可以移动),即可对相机的内外参数进行标定。下面介绍张氏标定法(以下也这么称呼)的原理。原理相机模型和单应矩阵相机标定,就是对相机的内外参数进行计算的过程,从而得到物体到图像的投影_相机-投影仪标定
文章浏览阅读2.2k次。文章目录Wayland 架构Wayland 渲染Wayland的 硬件支持简 述: 翻译一篇关于和 wayland 有关的技术文章, 其英文标题为Wayland Architecture .Wayland 架构若是想要更好的理解 Wayland 架构及其与 X (X11 or X Window System) 结构;一种很好的方法是将事件从输入设备就开始跟踪, 查看期间所有的屏幕上出现的变化。这就是我们现在对 X 的理解。 内核是从一个输入设备中获取一个事件,并通过 evdev 输入_wayland