四叉树问题.docx

《四叉树问题.docx》由会员分享，可在线阅读，更多相关《四叉树问题.docx（12页珍藏版）》请在第一文库网上搜索。

1、四叉树问题编写人：张天骥，景宇轩，张华添，刘凤麟，周弋涛，熊林学号：008120040081200500812008120230081202300812030编写时间：09-5-11一、问题描述使用四叉树来存储栅格图像要求：(1)能够用四叉树存储给定的黑白图像并能显示图像；(2)图像的格式：bmp格式的黑白图像。(bmp格式见文件“BMP文件格式说明W);对于图像的显示可以分别用两个不同的字符来表示黑点和白点，比方上面的字母，A，可以这样显示：二、问题分析和数据结构算法的设计程序应有三个局部：读取文件头的必要信息，构建四叉树，在控制台输出。三个局部按顺序进行。为了使四叉树能够表示各个子图像的大

2、小，位置，必须要有其左下角的坐标和各级节点的层数，其结构设计如下：tyedefstructfour_branches_tree四叉树结构intxx,yy;/结点的坐标，是子图像左下角的坐标，最顶层根节点是(0,0)ShortintIayer;四叉树层数,可用来计算子图像长宽，顶层为0,表示整个图像ShOrtintVakie;该值为1时表示该子图像的所有像素白色，0为黑色，2那么黑白都有，需要有子结点four_branches_tree*next4;连接子结点，仅当va1ue=2时才有，否那么值为NU11FBT,*PFBT;要处理图像，首先要知道图像中数据的大小size,宽wid,高hei,bm

3、p文件中文件头的长度(黑白图像为十六进制的3E)每行像素的实际位数为W(w=(size-3E)*8hei,3E是文件头的长度，和SiZe都以字节为单位，故乘以8表示位数)，这样才能用坐标方式进行处理。而对于构建四叉树，其根本原理是：图像按四角均分成四块子图像(子图像wid,hei相等且均为2=的大小)，每块从该子图像左下角(因为bmp图像数据是从左下角开始一行一行存起的)一行一行比拟像素；均为黑/白时赋值0/1,不均为黑白时，赋值2,并进一步再分为四块，直到子图像均为纯黑/纯白。这个过程中需要递归，但系统栈空间显然缺乏，所以程序用栈结构，其结构如下：tyedefstructstacknode以

4、下为链栈，用于构建四叉树和输出PFBTs；structstacknode*next;)ST,*PST;typedefstruct!stackPSTtop;）*P1ST,1ST;先将每次处理时，从栈中取出新节点，假设需再分那么构建四个子结点并将之压入栈中。这是构建二叉树的主循环。由以上概述知，程序最关键的地方在于构建逻辑坐标和实际图像文件中该点像素位置处的映射。而在操作中有两处难点：一，黑白图像一个字节代表一像素，但最小读取单位是byte,所以不但要读该像素所在字节byte,还要读该像素所在字节的bit（0-7）；二，对于非整2长宽的普通图像，应当将其逻辑上用“白像素补足为2徇长宽的图像，而那些

5、虚拟的像素是不能与文件对应的，构建四叉树时必须考虑这种特殊情况。在理想的宽高都是2的图像中，设取出栈后的子图像S节点坐标（x,y）（x,y均从。记起），该子图像的宽高为q=heiQAS.1ayer）,该节点起始像素在文件中的字节的位置是：B=（x+y*w）8（取整），而在该字节中从左数的位数bit,那么是：bit=（x+y*w）mod8（07位），按照这个方法读取该像素位置后，为便于比拟，应将对该像素位操作使该字节其它的像素除去，该像素那么移到本字节最后一位上（让十六进制数m=80右移bit位和byte按位与操作，再将m右移7bit位），得至IJm=O或1（黑/白）。然后进行两层循环（设循环变

6、量分别为i,j）,从零起均循环q次，每次外层循环重新定位图像该行第一个像素B=（x+（y+i）*w）8,bit=（x+（y+i）*w）mod8,内层那么每次都让bit+（假设bit7,那么清零并读取下一-个byte）,用处理m的方法给n赋值（易知这里n指（x+i,y+j）处像素的值），与m异或运算，为0那么继续直到循环结束将m值赋给S.va1ue,为1时（即图像非全黑/全白）跳出这两层循环并让S.va1ue=2,然后创立四个子结点坐标分别为（S-xx+directionj0*Ienca1（t-Iayer）,S-yy+directionj1*1enca1（t-1ayer）（j是一个四次循环的变量

7、,direction4=0,0,1,0,0J,1J）,1ayer值是原结点1ayer+1,分别与原结点nextj指针连接。对于长宽度非2的图像，计算一个2的Ien作“虚拟长宽”，用同种方法比拟。不同的是，当整个子图像在实际图像之外时（x=wid,y=Ien）,将其当成白色处理（即赋Sva1ue=1仅仅是局部“像素”在实际图像时，对于该像素（x1,y1）（刚好循环到这个在实际像素之外的坐标时），假设y11en,那么直接将m与1比拟，相同那么整个子图像均为白色（由于循环外层y,内层X顺序的缘故，y11en,必然此后的像素均在实际图像外），不同那么无需进一步比拟，直接再分；假设x11en,那么也将m

8、和1比拟，不同的是假设相同就跳到下一行的第一个像素继续比拟，而不是跳出循环再分子图像。输出图像时，本程序仅将具有实际像素的子图像输出（xwid,ytop=NU11;returnp1st;Ivoidpush(P1STp1st,PFBTx)进栈(PSTp;p=(PST)ma11oc(sizcof(ST);if(p!=NU11)(p-s=x;p-next=p1st-top;p1st-top=p;)e1seputsCFU11!,1);)voidpop(P1STp1st)/出栈(PSTp;if(p1st-top=NU11)puts(Empty);e1se(p=p1st-top;p1st-top=p1st

9、-top-ncxt;frec(p);I)PFBTtop(P1ST1st)/取栈顶元素if(1st-top=NU11)puts(,Emptyn);return(1st-top-s);)intgo(intw,inth)计算Ien,Ien见说明(intm,k;m=wh?w:h;for(k=I;m;m=1,kxx=O;th-yy=O;th-1ayer=O;S=th;W二(SiZe0x3E)*8hei;每行在文件中的实际宽度push(1st,th);fp=fbpen(fi1ename,f);Whi1e(ISt-top!=NU11)开始构建S=top(1st);pop(Ist);xn=S-xxxn,yn表

10、示结点左下角坐标简化程序之用，无其他意义yn=S-yy;if(xnwid/IIynAhei-DS-Xakie=I;如果该结点坐标超出实际长宽(是用2、长宽补足的坐标)，默认该结点代表的这些地方都是白色e1se在实际图像中k=1en(int)pow(2,S-1ayer);计算该结点代表的子图像长宽B=(IOng)(Xn+yn*w)8;左下角像素对应文件中该字节的位置bit=(BYTE)(xn+yn*w)%8);/左下角像素对应该字节的第几位，从左往右07位的哪位？fseek(fp,B+offset,SEEK_SET);校正位置，读取字节byte=fgetc(fp);m=0x80(1OOOOOOO

11、)binarym=bit;m=m&byte;m=7bit;这几个位运算是只把左下角该像素值保存，移到m中，用于以后比拟子图像是否所有像素均为此值Sva1ue=m;/以后跳出循环便利之用,不同还可以再改for(i=0;iv=k-1;i+)子图像-列列的循环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+ihei1)/如果该列超出了实际高度n=1;以下虚拟的“像素”默认为白色，直接比拟，异或运算，相同为O不同为1if(mn)S-va1uc=2;e1seS-va1ue=1;break;以下步骤也不必进行了1j=0;WhiIeowid-1)同y