四叉树问题.docx

四叉树问题编写人：张天骥，景宇轩，张华添，刘凤麟，周弋涛，熊林学号：008120040081200500812008120230081202300812030编写时间：09-5-11一、问题描述使用四叉树来存储栅格图像耍求：（1）能够用四叉树存储给定的黑白图像并能显示图像；（2）图像的格式：bmp格式的黑白图像。（bmp格式见文件"BMP文件格式说明.p<r）；对于图像的显示可以分别用两个不同的字符来表示黑点和白点，比方上面的字母'A，可以这样显示：二、问题分析和数据结构算法的设计程序应有三个局部：读取文件头的必要信息，构建四叉树，在控制台输出。三个局部按顺序进行。为了使四叉树能够表示各个子图像的大小，位置，必须要有其左下角的坐标和各级节点的层数，其结构设计如下：typedefstructfour_branches_tree四叉树结构intxx,yy;/结点的坐标，是子图像左下角的坐标，最顶层根节点是（0,0）ShortintIayerM/四叉树层数,可用来计算子图像长宽，顶层为0,表示整个图像ShOrtintValUe;该值为1时表示该子图像的所有像素白色，0为黑色，2那么黑白都有，需要有子结点four_branches_tree*next;连接子结点，仅当value=2时才有，否那么值为NULL）FBT,*PFBT;要处理图像，首先要知道图像中数据的大小size,宽Wid,高hei,bmp文件中文件头的长度（黑白图像为十六进制的3E）每行像素的实际位数为W（W=（SiZe-3E）*8hei,3E是文件头的长度，和SiZe都以字节为单位，故乘以8表示位数），这样才能用坐标方式进行处理。而对于构建四叉树，其根本原理是：图像按四角均分成四块子图像（子图像wid,hei相等且均为2=的大小），每块从该子图像左下角（因为bmp图像数据是从左下角开始一行一行存起的）一行一行比拟像素；均为黑/白时赋值0/1,不均为黑白时，赋值2,并进一步再分为四块，直到子图像均为纯黑/纯白。这个过程中需要递归，但系统栈空间显然缺乏，所以程序用栈结构，其结构如下：typedefstructstacknode以下为链栈，用于构建四叉树和输出（PFBTs;structstacknode*next;ST,*PST;typedefstruct!stackPSTtop;*PLST.LST;先将每次处理时，从栈中取出新节点，假设需再分那么构建四个子结点并将之压入栈中。这是构建二叉树的主循环。由以上概述知，程序最关键的地方在于构建逻辑坐标和实际图像文件中该点像素位置处的映射。而在操作中有两处难点：一，黑白图像一个字节代表一像素，但最小读取单位是byte,所以不但要读该像素所在字节byte,还要读该像素所在字节的bit（0-7）；二，对于非整"n长宽的普通图像，应当将其逻辑上用"白像素"补足为2N长宽的图像，而那些虚拟的像素是不能与文件对应的，构建四叉树时必须考虑这种特殊情况。在理想的宽高都是"n的图像中，设取出栈后的子图像S节点坐标（x,y）（x,y均从0记起），该子图像的宽高为q=hei/QAS.layer）,该节点起始像素在文件中的字节的位置是：B=（x+y*w）8（取整），而在该字节中从左数的位数bit,那么是：bit=（x+y*w）mod8（0-7位），按照这个方法读取该像素位置后，为便于比拟，应将对该像素位操作使该字节其它的像素除去，该像素那么移到本字节最后一位上（让十六进制数m=80右移bit位和byte按位与操作，再将m右移7-bit位），得到m=0或1（黑伯）。然后进行两层循环（设循环变量分别为ij）,从零起均循环q次，每次外层循环重新定位图像该行第个像素B=（x+（y+i）*w）8（取整），bit=（x+（y+i）*w）mod8,内层那么每次都让bit+假设bit>7,那么清零并读取下一个byte）,用处理m的方法给n赋值（易知这里n指（X+i,y+j）处像素的值），与m异或运算，为0那么继续直到循环结束将m值赋给S.value,为I时即图像非全黑/全白）跳出这两层循环并让S.value=2,然后创立四个子结点坐标分别为（S->xx+directionjO*lencal（t->layer）,S->yy+directionj1*lencal（t->layer）（j是-个四次循环的变量，direction=0,0,l,0,0,l,1,1）,layer值是原结点Iayer+1,分别与原结点nextj指针连接。对于长宽度非2=的图像，计算一个"n的Ien作“虚拟长宽"，用同种方法比拟。不同的是，当整个子图像在实际图像之外时（x>=wid,y>=len）,将其当成白色处理（即赋S.value=l仅仅是局部"像素"在实际图像时，对于该像素（xl,yl）（刚好循环到这个在实际像素之外的坐标时），假设yl>len,那么直接将m与1比拟，相同那么整个子图像均为白色（由于循环外层y,内层X顺序的缘故，yl>len,必然此后的像素均在实际图像外），不同那么无需进一步比拟，直接再分；假设xl>len,那么也将m和1比拟，不同的是假设相同就跳到下-行的第一个像素继续比拟，而不是跳出循环再分子图像。输出图像时，本程序仅将具有实际像素的子图像输出（x<wid,y<len）。为遍历各个节点，需再次用到栈（具体略）。对于每个应输出的子图像，其各个像素（xl,yl）,Xl对应于控制台原坐标位置，yl那么输出在y2=hei-l-yl-i（i指该像素在图像第几行，这个变换是因为控制台的坐标以左上角为原点）。流程图见报告后三、程序设计/FCT.cpp:Definestheentrypointfortheconsoleapplication.四叉树存储输出黑白图像演示程序/组员：张天骥（组长）、张华添、周弋涛、熊林、刘凤麟、景宇轩程序全组共同设计，张天骥编写tree,out函数，控制台控制代码，刘凤麟编写main函数，界面优化与时间输出的代码，熊林、景宇轩设计栈局部，周弋涛、张华添完成测试。创立口期：09-4-28,最后修改日期:09-5-21数据结构在stdafx.h中，用到四叉树与链栈结构#includc"stdafx.h"#include"stdio.h"include"windows.h"includc"maJloc.h,'#include"stdlib.h"#include"time.h"#includc"math.h"#defineTRUE1#defineINSURE20用于调节控制台大小时加额外大小，确保图像输出结果保存#defineDEFAUErWlD80#defineDEFAULTHE1300控制台窗口默认大小80*300PLSTCreateSi()建栈PLSTplst=(PLST)malloc(sizeof(LST);if(st)puts(,NoSpace,);returnNULL;Ielseplst->top=NULL;returnplst;voidpush(PLSTplst,PFBTx)进栈PSTp;p=(PST)malloc(sizeof(ST);if(p!=NULL)p->s=x;p->next=plst->top:plst->top=p;)dseputs(,TULL!);voidpop(PLSTPkt)出栈PSTp;if(pkt>top=NULL)puts("Empty");elsep=plst->top:plst->top=plst->top->ncxt;frec(p);PFBTtop(PLSTkt)取栈顶元素if(1st->top=NULL)puts(mEmptyn,');return(lst->top->s);intgo(intw,inth)计算leu,Ien见说明intm,k;m=w>h?w:h;for(k=l;m;m»=l,k«=l);returnk;PFBTtree(intwidjntheitintIenjinsignedlongintoffset,unsignedlongintsize,charfilename)WOffSet是文件中图像数据到开头的长度，这是用来读取图像内容的intXn=O,yn=0,w,direction=O,O,l,O,O,l,1,1;同迷宫问题，构建图像的循环要用FILE*fp;BYTEm,n,byte;BYTEbit;/m是子图像左下角像素值m是子图像某像素的值,byte是某像素位与文件中的字节,bit是该像素在byte中左数第几位intij,k;循环longintB;/PFBTth.S,t;PLST1st;)st=createst()/创立栈if(lst=NULL)Printfe栈建立失败!")；returnNULL;th=(PFBT)malbc(sizeof(FBT);/初始化根节点th->xx=O;th->yy=O;th->layer=O;S=th;W=(SiZe.0x3E/8/hei;每行在文件中的实际宽度push(lst,th);fp=fbpcn(filename,',r");WhilC(ISt>top!=NULL)开始构建S=top(lst);pop(lst);xn=S->xxxn,yn表示结点左下角坐标简化程序之用，无其他意义yn=S->yy;if(xn>wid/1卜*2.1讨.>辿11片1;如果该结点坐标超出实际长宽(是用2M长宽补足的坐标)，默认该结点代表的这些地方都是白色CISC/在实际图像中k=len(int)pow(2S>layer);"计算该结点代表的子图像长宽B=(Iong)(Xn+yn*w)/8;"左下角像素对应文件中该字节的位置bit=(BYTE)(xn+yn*w)%8);"左下角像素对应该字节的第几位，从左往右0-7位的哪位？fscck(fp,B+offsct,SEEK_SET);校正位置，读取字节byte=fgetc(fp);m=0x80;/(l(X)OOOOO)binarym>>=bit;m=m&byte;m>>=7.bit;这几个位运算是只把左下角该像素值保存，移到m中，用于以后比拟子图像是否所有像素均为此值S>value=m;以后跳出循环便利之用,不同还可以再改for(i=0;i<=kl;i+H子图像列洌的循环B=(Iong)(Xn+(yn+i)*w)/8;与上类似，读取子图像该列第一个像素位置bit=(BYTE)(xn+(yn+i)*w)%8);fseek(fp,B÷offset,SEEK-SET);byte=fgetc(fp);if(yn+i>hei-l)如果该列超出了实际高度n=l，以下虚拟的"像素"默认为白色，直接比拟，异或运算，相同为0不同为Iif(mAn)S->value=2;elseS->value=l;break;以下步骤也不必进行j=0；while(j<k)(行的循环if(xn+j>wid-l)同y,判断横坐标是否超出实际宽度，是那么比拟n=l;if(m